(Obejrzany 31 razy)

Więcej o gramatykach metamorficznych możecie przeczytać w dziewiątym rozdziale książki W.F. Clocksin, C.S. Mellish. Programming in Prolog (odnośnik powinien działać również spoza kampusu PWr).

Tags: gramatyka bezkontekstowa, gramatyka metamorficzna, produkcja gramatyki, alfabet, symbole terminalne, symbole nieterminalne

(Obejrzany 22 razy)

Więcej o śledzeniu programów i szukaniu w nich błędów możecie przeczytać w ósmym rozdziale książki W.F. Clocksin, C.S. Mellish. Programming in Prolog (odnośnik powinien działać również spoza kampusu PWr).

Tags: śledzenie działania, niedeterminizm, punkt wyboru

(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