Otto-von-Guericke-Universität
Magdeburg
Fakultät für Informatik
Institut für Verteilte Systeme
AG Softwaretechnik
Analyse von Prolog-Programmen
Türme von Hanoi:
Etwas Allgemeines zu den Türmen 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:
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
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
Prozeduren:
Das PMT-Programm ermittelte folgende Bewertung der Prozeduren:
name/arity NG ID OD IC OC NR DGMc DGMs Cut NoC NoR move/4
Klauseln:
Die durch das PMT-Programm ermittelte Bewertung der Klauseln:
name/arity/number NG NC NR DGMc DGMs Cut Typ move/4/1 move/4/2
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: