otto

Otto-von-Guericke-Universität Magdeburg
Fakultät für Informatik
Institut für Verteilte Systeme
AG Softwaretechnik

Analyse von Prolog-Programmen

Sebastian Nusser

Türme von Hanoi:

Etwas Allgemeines zu den Türmen von Hanoi:

türme von hanoi

Die obenstehenden Zeichnung verdeutlicht das rekursive Lösungsschema für das Problem der Türme von Hanoi mit drei Scheiben.
Die drei Zahlen in den Kreisen geben an, auf welchem Stab welche Scheibe liegt. Die Stäbe sind von links nach rechts durchnumeriert. Die erste Zahl gibt den Stab an, auf dem die kleinste Scheibe liegt, die zweite Zahl den Stab, auf dem die mittlere Scheibe liegt und die dritte den Stab, auf dem die größte Scheibe liegt.

 

Programm:

Folgendes Prolog-Programm wurde mit dem Messtool PMT analysiert:

/* prolog tutorial 2.3 Towers of Hanoi puzzle */


move(1,X,Y,_) :-
write('Move top disk from '),
write(X),
write(' to '),
write(Y),
nl.
move(N,X,Y,Z) :-
N>1,
M is N-1,
move(M,X,Z,Y),
move(1,X,Y,_),
move(M,Z,Y,X).

 

Callgraph:

Das Programm liefert folgenden Call-Graphen:

screenshot

Die Schlinge am einzigen Knoten des Graphen (move/4) kennzeichnet den rekursiven Aufbau des Prädikats move.

 

Messungen:

Programm:

Folgende Kennzahlen wurden durch das PMT-Programm ermittelt:

Anzahl der Programmzeilen (brutto)

17

Anzahl der Programmzeilen (netto)

12

Anzahl der Kommentare

1

Kommentar-Code-Verhältnis

0.08333

Anzahl Prozeduren

1

Anzahl Klauseln

2

Anzahl Kommandos

0

Anzahl Ziele

0

Anzahl direkter rekursiver Aufrufe

3

Kantenanzahl des Call-Graphen

1

Knotenanzahl des Call-Graphen

1

Verbindungsdichte

1

Breite des Call-Graphen

1

Höhe des Call-Graphen

1

hierarchische Komplexität

1

strukturelle Komplexität

3

Fenton's Impurity-Metrik

0

Yin-Winchester-Metrik
0

 

Prozeduren:

Das PMT-Programm ermittelte folgende Bewertung der Prozeduren:

name/arity NG ID OD IC OC NR DGMc DGMs Cut NoC NoR
move/4
9
1
1
3
3
3
30
14
0
2
2

 

Klauseln:

Die durch das PMT-Programm ermittelte Bewertung der Klauseln:

name/arity/number NG NC NR DGMc DGMs Cut Typ
move/4/1
4
0
0
8
4
0
R
move/4/2
5
3
3
30
14
0
R

 

Erfahrungswerte:

Wert: Prozeduren: Klauseln:
DGMc:

28.996

8.589

DGMs:

13.345

4.131

Ausgangsgrad:

1.000

 

Eingangsgrad:

1.000

 

Teilziele:

8.193

3.607

Anzahl direkter Rekursionen:

2.716

0.065

Anzahl Cuts:

0.000

0.000

Die zulässige bzw. kritische Abweichung war jeweils 0.000.

 

Auswertung:

Programm:

Das Programm hat brutto 17 Zeilen, wovon netto noch 12 Zeilen gezählt werden. Da das Program nur aus zwei Regeln und einem Kommentar besteht, kann man daraus schließen, dass der Autor versucht hat, die Lesbarkeit des Programms zu erhöhen, indem er jeweils einen Teilausdruck in eine eigene Zeile schreibt. Das Verhältnis Kommentare zu Programmzeilen (0.08333) ist daher etwas irreführend. Andererseits dient der Kommentar lediglich als eine Versionsinformation und trägt nicht zum weiteren Verständnis des für sich schon leichtverständlichen Codes bei.

Die Anzahl direkt rekursiver Aufrufe und die strukturelle Komplexität haben den Zahlenwert 3; die Anzahlen für Callgraph-Ecken, Callgraph-Knoten, Verbindungsdichte usw. haben alle den Wert eins und die Anzahl der Ziele bzw. die Anzahl der Kommandos ist null.

Lediglich bei der Berechnung der Metriken scheint ein Fehler aufgetreten zu sein. Die Yin-Winchester-Metrik (definiert als kanten-knoten+1) sollte statt null den Wert (1 - 1 + 1 = 1) und die Fenton's Impurity-Metrik (definiert als 2*(kantenzahl-knotenzahl+1)/(n-1)(n-2)) sollte auch einen anderen Wert als null liefern.

 

Prozeduren:

Der Eingangsgrad bzw. der Ausgangsgrad beträgt jeweils eins; die Anzahl von rufenden, gerufenen Calls bzw. direkt rekursiver Calls ergibt drei. Es wird kein Cut-Operator benutzt, was man an Cut = 0 erkennen kann.

Das Programm besteht aus zwei Klauseln die gleichzeitig auch Regeln sind (NoC=NoR=2). Die Anzahl der Teilziele beträgt neun.

Die voreingestellten Erfahrungswerte entsprechen in etwa den gemessenen Werten.

 

Klauseln:

Bei der Auswertung der Klausel-Messung erkennt man leicht, dass beide Klauseln Regeln sind. Die erste Regel (move/4/1) hat vier Teilziele, keine Calls und keinen Cut-Operator. Die zweite Regel (move/4/2) besitzt fünf Teilziele, drei Aufrufe nutzerdefinierter Prozeduren, drei direkt rekursive Calls und auch keinen Cut-Operator.

Auch hier entsprechen die voreingestellten Erfahrungswerte in etwa den gemessenen Werten.

 

Bemerkungen:

Das PMT-Programm scheint als 16bit-Windows-Anwendung Probleme bei Rechnern mit viel Arbeitsspeicher zu haben. Bei dem Versuch eine Prolog-Datei auf solch einem Rechner zu öffnen, stürzt das Programm regelmäßig ab. Auf älteren Rechnern treten hingegen keine Probleme auf. Die Bedienung des Programmes ist weitgehend selbsterklärend.

Da das analysierte Programm relativ kurz und einfach ist, sind die Ergebnisse übersichtlich und leicht verständlich.

 

Legende:

NG: Anzahl der Teilziele
NC: Anzahl der Aufrufe nutzerdefinierter Prozeduren
ID: Eingangsgrad (Anzahl der rufenden Komponenten einer Prozedur)
OD: Ausgangsgrad (Anzahl der gerufenden Komponenten aus einer Prozedur)
IC: Anzahl der rufenden Calls insgesamt
OC: Anzahl der gerufenen Calls insgesamt
NR: Anzahl direkt rekursiver Calls
DGMc: Datengraphkomplexität
DGMs: Datengraphhöhe
Cut: Anzahl der Cuts
NoC: Anzahl der Klauseln
NoR: Anzahl der Regeln
Typ: Fakt (F) oder Regel (R)