To continue the guided tour go back where You came from
Continue reading the hints in German (...)

Dieser Hinweis ist aus der Übung im WS 1994/95 oder aus einer noch älteren Übung oder war nie Teil einer Übung und ist daher möglicherweise für spätere Übungen nicht gültig!

      Wie kann man allgemein Iterationen
            in Prolog darstellen?

Die make/next/done-Konvention eignet sich sehr
gut, allgemeine Interationen darzustellen.
Hier ein kleines recht bekanntes Beispiel.

Gegeben ist das Prädikat nextspec(I0,I), das
eine Funktion darstellt. (Für ein gegebenes I0
findet sich also genau ein I). Diese Funktion
bildet eine Zahl größer 1 auf eine andere Zahl
wie folgt ab:

nextspec(I0, I) :-
	I0 > 1,
	0 is Zahl0 mod 2, % also gerade
	I is I0 // 2.
nextspec(I0, I) :-
	I0 > 1,
	1 is Zahl0 mod 2, % also ungerade
	I is 3 * I0 + 1.

Diese Funktion wird solange auf das Ergebnis
angewandt, bis sich die Zahl 1 (wenn überhaupt)
ergibt. Die Lösung dazu wäre etwa (ohne
genauere Fehlerüberprüfungen).

iterspec(1).
iterspec(N0) :-
	N0 > 1,
	nextspec(N0, N),
	iterspec(N).

Dieses Prädikat ist wahr, wenn man von einer
gegebenen Zahl aus  1 findet. Sonst aber
terminiert dieses Prädikat nicht. Es ist
insofern nicht sonderlich informativ.

In einem prozeduralen Programm würde man etwa
print Anweisungen einfügen, um eine länger
dauernde Iteration beobachten zu können, und
sich dadurch über den Fortgang Gedanken machen
zu können. Wie kann man so etwas in einer
völlig seiteneffektfreien Umgebung erreichen?

Die Idee ist, das Prädikat zu verallgemeinern.
Statt sich mit der Antwort ja/Endlosschleife
zu begnügen, erweitert man das Prädikat um ein
weiteres Argument, das den momentanen Zustand
zeigt.

iteration(N, S) :-
	make(N, S0),
	iterate(S0, S).

iterate(S, S).
iterate(S0, S) :-
	next(S0, S1),
	iterate(S1, S).

Nach jedem Schritt next/2 findet sich also eine
Lösung. Zwar nicht die endgültige, aber
immerhin.

Der Zustand innerhalb der Iteration wird
z.B. durch eine Strukur -/2 dargestellt:

is_state(MomentaneZahl-Schrittebisdahin) :-
	integer(MomentaneZahl),
	integer(Schrittebisdahin).

make(Zahl, Zahl-0) :-
	integer(Zahl),
	Zahl > 0,
	!.
make(Zahl, _) :-
	fehler('Es wird eine positive Ganzzahl erwartet, gefunden wurde aber': Zahl).

next(Zahl0-Schritt0, Zahl-Schritt) :-
	Zahl0 > 1,
	Mod2 is Zahl0 mod 2,
	Schritt is Schritt0 + 1,
	nextstep(Mod2, Zahl0, Zahl).

nextstep(0, Zahl0, Zahl) :-
	Zahl is Zahl0 // 2.
nextstep(1, Zahl0, Zahl) :-
	Zahl is (3 * Zahl0 + 1) // 2.
% Da 3*Zahl0 + 1 immer gerade ist, wird
% Division gleich hier ausgeführt.

done(1 - _).

diesezahl(N, N - _Schritt).
dieserschritt(Schritt, _N - Schritt).

% Hilfsprädikate

zahl(N) :-
	integer(N),
	N > 0.
zahl(V) :-
	var(V),
	zähle(1,V).

zähle(N,N).
zähle(N0, N) :-
	N1 is N0 + 1,
	zähle(N1, N).


% Terminiert N = 112?
:- N = 112, iteration(N, S), done(S).

Welche Zahlen benötigen mehr als 100 Schritte?
:- zahl(N), iteration(N, S), dieserschritt(Schritt,S), Schritt > 100, done(S).
Wann gibt es Zwischenergebnisse größer 10000?
:- zahl(N), iteration(N, S), diesezahl(Zahl, S), Zahl > 10000.

Natürlich ist es sinnvoll, das Verfahren zu
verfeinern und zu beschleunigen. So kann man
den Zustand erweitern, indem man zusätzlich
eine untere Grenze einführt, damit die
iteration früher abbricht, etc.etc.

Das, was Sie an dem Beispiel sehen sollen, ist,
daß sich sehr wohl auch Iterationen, die man
oft mit Seiteneffekten zupflastert, auf völlig
seiteneffektfreie Weise darstellen lassen.
Dadurch ist es oft möglich, relativ komplexe
Anfragen sehr kompakt darzustellen.

Zudem kann man immer Zusicherungen hinzufügen,
die ,,die Ausgabe testen``. Das ist in einem
prozeduralen Programm nur mit äußerst hohem
Aufwand zu erreichen.

        \hinweis{PrologAllgemein}
Zurück: \hinweis{init}

To continue the guided tour go back where You came from
Continue reading the hints in German