Введение в язык логического программирования ПРОЛОГ
Язык Пролог объединяет два подхода: логический и процедурный.
По мнению Дж. Робинсона в основе идеи логического программирования лежит принцип описания задачи при помощи совокупности утверждений на некотором формальном логическом языке и получение решения при помощи вывода в некоторой формальной системе. Основой языка Пролог является логика предикатов первого порядка.
Программа на Прологе включает в себя постановку задачи в виде множества фраз Хорна (раздел clauses) и описание цели (раздел goal), - формулировку теоремы, которую нужно доказать, исходя из множества правил и фактов, содержащихся в этой постановке.
Процесс поиска доказательства основан на методе линейной резолюции (дизъюнкты подбираются в порядке их следования в тексте программы).
Проиллюстрируем принцип логического программирования на простом примере: запишем известный метод вычисления наибольшего общего делителя двух натуральных чисел – алгоритм Евклида в виде Хорновских дизъюнктов. При этом примем новую форму записи фразы Хорна, например ШPЩШQЩШRЩS будем записывать как S: - P, Q, R. Тогда алгоритм Евклида можно записать в виде трех фраз Хорна:
1. NOD (x, x, x): -.
2. NOD (x, y, z): - B (x, y), NOD (f (x, y), y, z).
3. NOD (x, y, z): -B (y, x), NOD (x, f (y, x), z).
Предикат NOD – определяет наибольший общий делитель z для натуральных чисел x и y, предикат B – определяет отношение «больше», функция f – определяет операцию вычитания. Если мы заменим предикат B и функцию f обычными символами, то фразы примут вид:
1. NOD (x, x, x): -.
2. NOD (x, y, z): - x>y, NOD ((x- y), y, z).
3. NOD (x, y, z): -y>x, NOD ((x, y- x), z).
Для вычисления наибольшего общего делителя двух натуральных чисел, например 4 и 6, добавим к описанию алгоритма четвертый дизъюнкт:
4. я: - NOD (4, 6, z).
Последний дизъюнкт – это цель, которую мы будем пытаться вывести из первых трех дизъюнктов.
Язык программирования Пролог (PROgramming LOGic) предполагает получение решения задачи при помощи логического вывода из ранее известных фактов. Программа на языке Пролог не является последовательностью действий – она представляет собой набор фактов и правил, обеспечивающих получение логических заключений из данных фактов. Поэтому Пролог считается декларативным языком программирования.
Пролог базируется на фразах (предложениях) Хорна, являющихся подмножеством формальной системы, называемой логикой предикатов.
Пролог использует упрощенную версию синтаксиса логики предикатов, он прост для понимания и очень близок к естественному языку.
Пролог имеет механизм вывода, который основан на сопоставлении образцов. С помощью подбора ответов на запросы Пролог извлекает хранящуюся информацию. Пролог пытается ответить на запрос, запрашивая информацию, о которой уже известно, что она истинна.
Одной из важнейших особенностей Пролога является то, что он ищет не только ответ на поставленный вопрос, но и все возможные альтернативные решения. Вместо обычной работы программы на процедурном языке от начала и до конца, Пролог может возвращаться назад и просматривать все остальные пути при решении всех частей задачи.
Программист на Прологе описывает объекты и отношения, а также правила, при которых эти отношения являются истинными.
Объекты рассуждения в Прологе называются термами–синтаксическими объектами одной из следующих категорий:
· константы,
· переменные,
· функции (составные термы или структуры), состоящие из имени функции и списка аргументов-термов, имена функций начинаются со строчной буквы.
Константа в Прологе служит для обозначения имен собственных и начинается со строчной буквы.
Переменная в Прологе служит для обозначения объекта на который нельзя сослаться по имени.
