Вопрос1. Вычислительная модель программы на логическом языке. Согласование целевых утверждений. Сопоставление и унификация. Детерминизм.

Множество формул исчисления предикатов эквивалентное хорновским дизъюнктам называется логической программой, причем в данном множестве имеется в точности один негативный дизъюнкт и предполагается что все переменные универсально квантифицируемы. В терминологии логического программирования: точный дизъюнкт – правило (выражает знания о предметной области), универсальный дизъюнкт – факт (задают оперативные данные о состоянии предметной области), негативный дизъюнкт – цель (утверждение, которое необходимо доказать либо выяснить при каких значениях переменных оно следует из набора имеющихся фактов и правил). В логической программе цели записываются в виде перечисления литер без отрицания. Большинство интерпретаторов пролога в качестве алгоритмов рассуждений используют алгоритмы, рассмотренные ранее в комбинации с поиском в глубину дизъюнктов для очередной резолюции. Кроме того сохраняется последовательность используемых унификаций для извлечения ответа.Допустим, что в программе сформулирована некоторая цель, которая имеет два аргумента X и Y:

kniga(X,Y).

Пытаясь выполнить данное целевое утверждение, Пролог должен будет проверить каждое предложение kniga в программе. Сопоставляя аргументы X и Y с аргументами каждого предложения kniga, Пролог выполняет поиск от начала программы и до ее конца. Обнаружив предложение, соответствующее целевому утверждению, VP присваивает значения свободным переменным таким образом, что целевое утверждение и предложение становятся идентичными. В этом случае говорят, что утверждение унифицируется с предложением. Такая операция сопоставления называется унификацией.

Свободная переменная может быть унифицирована с любым другим аргументом и даже с другой свободной переменной.

Часто при решении какой-либо задачи мы придерживаемся определенного пути для ее логического завершения. Если полученный результат не дает искомого ответа, мы должны выбрать другой путь.

Visual Prolog при поиске решения задачи использует именно такой метод проб и возвращений назад. Этот метод называется поиск в возвратом. Если, начиная поиск решения задачи (или целевого утверждения), VP должен выбрать между альтернативными путями, то он ставит маркер у места ветвления (называемого точкой отката) и выбирает первую подцель, которую и станет проверять. Если данная подцель не выполнится (что эквивалентно достижению тупика в лабиринте), то VP вернется к точке отката и попробует проверить другую подцель.

Попытка согласования целевого утверждения начинается с вершины программы. Если соответствие обнаружено, то переменные целевого утверждения связываются с соответствующими значениями. В том случае, когда в программе существует более чем один возможный ответ на некоторое обращение, ставится точка возврата после соответствующего факта. Эта точка указывает на то место, откуда начнется поиск следующего возможного соответствия для некоторого предложения. Механизм возврата запускается тогда, когда  в программе не обнаруживается соответствующих предложений. Когда Пролог отступает к точке поиска с возвратом, он освобождает все переменные, связанные после этой точки, и ищет другое решение для исходного обращения.

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

    Вы можете превратить недетерминированные предложения в детерминированные, вставляя отсечения в тело правил, определяющих данный предикат. Например, помещение отсечений в предложения, определяющие предикат friend, делает этот предикат детерминированным, поскольку в данном случае обращение к friend может возвратить одно и только одно решение.