🗊Презентация Сентенциальное программирование: PROLOG

Лекция 5. Сентенциальное программирование: PROLOG Общие концепции Язык логического программирования PROLOG представляет собой одну из моделей сентенциального программирования. Первой находкой создателей языка PROLOG явилось понятие унификации, изобретенное в методе резолюций для доказательства формул классической логики предикатов. Два выражения называются унифицируемыми, если они могут быть приведены к одному и тому же виду подстановкой значений вместо свободных переменных. Унификация—вид конкретизации, при котором границы всех синтаксических единиц фиксированы, структура выражения однозначно определена и подстановка, приводящая два выражения к одному и тому же виду, вычисляется рекурсивно. Второй находкой, перенесенной авторами языка PROLOG из специализированных программ (для логики и искусственного интеллекта) в языки программирования, стала система обработки неудач. Успешно произведенная унификация является лишь разрешением выполнить некоторое действие. После проверки других условий, возможно, мы будем вынуждены вернуться и выбрать другой вариант.

Общие концепции Третья находка языка PROLOG, перенесенная в программирование из метода резолюций, — это стандартизация цели. Целью доказательства в методе резолюций всегда является получение пустого дизъюнкта, то есть стирание доказываемого выражения (с логической точки зрения, приведение его к абсурду). Точно так же и в языке PROLOG: успешное исполнение программы означает стирание поля зрения. Четвертая находка создателей языка PROLOG взята из ограничения классической логики. Хорновские формулы обладают важным свойством. Для нахождения вывода в системе хорновских формул достаточно производить так называемую линейную резолюцию, когда на каждом шаге делается вывод из исходной формулы и наследника цели. Никаких сочетаний исходных формул между собой либо различных вариантов раскрытия цели между собой делать, в принципе, не нужно.

Поле зрения, поле памяти и PROLOG-программа Когда рассматривается исполнение программы в нетрадиционном языке (например, PROLOG-программы), то естественно воспринимать конкретную реализацию языка как новую машину нетрадиционной архитектуры с высокоуровневыми командами (в данном случае как PROLOG-машину). Данные, используемые PROLOG-машиной, размещаются во всех частях поля памяти и имеют общую структуру. Рассмотрим на уровне абстрактного синтаксиса структуру данных, обрабатываемых языком PROLOG. Все данные языка PROLOG являются термами. Термы построены из атомов при помощи функциональных символов. Атомами могут быть переменные и константы, в свою очередь, делящиеся на имена и числа. Функциональные символы являются именами и называются функторами. Среди функторов выделяются детерминативы, которые в реализации делятся на предикаты и встроенные функции (функции обычно используются внутри выражений, а предикаты являются основными единицами управления и обычно используются вне скобок как основной функциональный символ выражения). Детерминативы должны быть описаны в программе, а остальные функторы рассматриваются просто как структурные единицы и могут оставаться неописанными.

Поле зрения, поле памяти и PROLOG-программа В поле памяти выделяется поле зрения, содержащее непосредственно обрабатываемые программой данные. Оно называется также целью и состоит из последовательности термов. Поле памяти имеет скрытую (при использовании стандартных возможностей языка) часть, в которой прослеживается история выполнения программы с тем, чтобы в случае необходимости произвести обработку неудачи. И, наконец, в поле памяти помещается сама PROLOG-программа, которая естественно структурируется на две части, нередко перемешанные в тексте самой программы, но обычно разделяемые при использовании внешней памяти: база данных и база знаний. База данных состоит из фактов, представляющих собой предикат, примененный к термам. База знаний состоит из предложений (клауз). Каждое предложение имеет вид, подобный хорновской формуле grandfather(X,Z) :- parent(X,Y), father(Y,Z).

Поле зрения, поле памяти и PROLOG-программа