пролог - почему этот странный след - PullRequest
Новая
       7

пролог - почему этот странный след

2 голосов
/ 19 ноября 2009

вот код пролога (который я вроде как следую). 

len([],0).
len([_|T],N) :- len(T,X), N is X+1.

и вот его след (я использую Linux, SWI) 

    [trace]  ?- len([d,f,w,c],X).
   Call: (7) len([d, f, w, c], _G314) ? 
   Call: (8) len([f, w, c], _L182) ? 
   Call: (9) len([w, c], _L201) ? 
   Call: (10) len([c], _L220) ? 
   Call: (11) len([], _L239) ? 
   Exit: (11) len([], 0) ? 
^  Call: (11) _L220 is 0+1 ? 
^  Exit: (11) 1 is 0+1 ? 
   Exit: (10) len([c], 1) ? 
^  Call: (10) _L201 is 1+1 ? 
^  Exit: (10) 2 is 1+1 ? 
   Exit: (9) len([w, c], 2) ? 
^  Call: (9) _L182 is 2+1 ? 
^  Exit: (9) 3 is 2+1 ? 
   Exit: (8) len([f, w, c], 3) ? 
^  Call: (8) _G314 is 3+1 ? 
^  Exit: (8) 4 is 3+1 ? 
   Exit: (7) len([d, f, w, c], 4) ? 
X = 4.

Я знаю, что пролог работает по этим «деревьям», но у меня возникают проблемы с выяснением, почему приращение к переменной выполняется только при ее выходе - какие-либо объяснения механизма этого?

Большое спасибо!

1 Ответ

6 голосов
/ 19 ноября 2009

Причина этого в том, что N is X+1 является последней частью предиката.

Думайте об этом так: чтобы вычислить N is X+1, нам нужно знать значение X, которое вычисляется путем вызова len(T,X). Но процесс вычисления X требует еще одного вызова len, вплоть до ситуации, когда вы получите пустой список.

Именно в этот момент известна длина списка, а именно 0. Таким образом, это значение «возвращается». Только тогда 0 + 1 можно рассчитать и «вернуть». А потом 1 + 1 и т. Д.

Думая об этом по-другому , обратите внимание, что для любых двух предикатов a и b, a, b дает истину, если и a, и b верны. В Прологе b будет оцениваться только в том случае, если известно, что a является истинным (в противном случае нет смысла оценивать b, поскольку результат, как известно, является ложным).

В результате все добавления выполняются после рекурсивных вызовов len.

...