Выучить пролог, упражнение 2.3

Позвольте мне немного расширить то, что сказал Starblue.

Логически эта программа говорит, что любой набор из пяти вещей является предложением, если первое - артикль, второе - существительное, третье - глагол, четвертое - еще один артикль, а пятое - другое существительное. Магия Пролога в том, что вам не нужно указывать ему как получить ответ, например: «попробуйте каждую статью для первого слова, затем зациклите, проверяя каждое существительное для второго слова, и так вперед "; вместо этого вы просто декларативно формулируете проблему (первое слово - статья и т. д.), и Prolog ее разберет. Итак, если ваш вопрос сформулирован логически, вы должны (в конечном итоге) получить все возможные верные ответы.

Поскольку Prolog работает на реальном компьютере, он должен иметь реальную стратегию поиска ответов, и эта стратегия представляет собой поиск в глубину: он по очереди связывает каждую переменную, проверяя все возможности, пока не сможет унифицировать это. переменная, затем переходит к следующей переменной. Когда вы запрашиваете следующее решение, оно возвращается к последнему объединению, у которого были другие возможности, и пытается найти другое, удовлетворяющее предикату. Вот почему сгенерированные предложения появляются в том порядке, в котором они были: слово 5 объединено последним, поэтому, когда Prolog выполняет резервное копирование, он повторяет попытку слова 5. Когда он исчерпывает все возможные объединения для слова 5, он возвращается к слову 4 и затем перемещается. снова перейдем к слову 5. Так что в конечном итоге он будет пробовать все возможные варианты для всех пяти слов. Если вам не нравится порядок, в котором он пытается, вы можете изменить порядок, в котором вы привязываете переменные. Например, если вы хотите, чтобы он повторил первое слово, а затем второе, вы можете переписать программу так:

sentence(Word1,Word2,Word3,Word4,Word5) :-
    word(noun,Word5),
    word(article,Word4),
    word(verb,Word3),
    word(noun,Word2),
    word(article,Word1).

?- sentence(X,Y,Z,Q,A), write([X,Y,Z,Q,A]).
[a,criminal,eats,a,criminal] ;
[every,criminal,eats,a,criminal] ;
[a,big kahuna burger,eats,a,criminal]

Как и ожидалось, этим управляет стек. Большинство современных прологов реализованы с помощью техники, называемой WAM, абстрактной машиной Уоррена. WAM похож на большинство виртуальных машин на других языках программирования тем, что существует стек вызовов, но также есть второй стек, называемый следом, в который он помещает переменные при каждой привязке. Затем обратное отслеживание работает, удаляя последнюю переменную из следа и пытаясь объединить ее и возобновить оттуда. Если для этой переменной нет другой унификации, она извлекает другую переменную из стека и выполняет дальнейшее резервное копирование. Когда в Prolog заканчивается след, он просто возвращает false, потому что привязка невозможна.