Przykłady programów (7 kwietnia, wykład 6)

(Obejrzany 41 razy)

Jeśli kogoś interesuje jak działa WAM (Warren Abstract Machine) dla języka Prolog, to polecam raport Hassan Aït-Kaci Warren's Abstract Machine: A Tutorial Reconstruction.

DOPISANE

Jeszcze parę słów o złożoności obliczeniowej algorytmu unifikacji. Rozpatrzmy następujący przykład:

?- f(A, B, C, D) = f(a, g(A, A), g(B, B), g(C, C)).
A = a,
B = g(a, a),
C = g(g(a, a), g(a, a)),
D = g(g(g(a, a), g(a, a)), g(g(a, a), g(a, a))).

Wydawać by się mogło, że termy podstawiane pod kolejne zmienne A, B, C i D podwajają swoją długość. Sugerowałoby to wykładniczą złożoność pamięciową algorytmu unifikacji.

Jednak gdy przyjrzymy się algorytmowi unifikacji, to podczas jego działania nie są zajmowane nowe komórki pamięci. Jedynie przepinane są referencje prowadzące do miejsc zawierających struktury (unifikacja zmiennej i struktury) lub zmienne (unifikacja dwóch zmiennych).

Poniżej przedstawiona jest zawartość pamięci przed i po unifikacji termów f(A, B, C, D) i f(a, g(A, A), g(B, B), g(C, C)):



Powyższy rysunek w formacie PDF: unifikacja.pdf.

Tags: interpreter języka imperatywnego, interpreter języka deklaratywnego, unifikacja, maszyna abstrakcyjna, WAM, reprezentacja termów, predykat dynamiczny