Основные парадигмы программирования

Разработка языка Prolog (Пролог) началась в 1970 г. Аланом Колмероэ и Филиппом Русселом. Они хотели создать язык, который мог бы делать логические заключения на основе заданного текста. Название является сокращением от "PROgramming in LOGic". Этот язык был разработан в Марселе в 1972г.

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

При использовании ЭВМ для решения задач можно выделить два взаимосвязанных способа представления знания:

1) процедурное представление, т. е. определение алгоритма обработки данных;

2) декларативное представление, т. е. определение отдельных понятий, их состояния в конкретные моменты времени и связей между ними.

Традиционные алгоритмические языки (Бэйсик, Паскаль, Си, Фортран) являются процедурными, поскольку их цель – описание алгоритма. Но они содержат и декларативные компоненты (описание переменных).

В языке Пролог, напротив, основной является декларативная компонента, так что он предназначен не столько для обработки данных, как для обработки фактов и декларативных правил.

Факты представляют собой логические формулы. База знаний (БЗ) задается совокупностью таких формул. Логические методы обеспечивают получение новых фактов из фактов, представленных в БЗ.

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

Пролог может использоваться при разработке экспертных систем, а также для следующих задач:

– доказательства теорем и вывода решений в задачах;

– создания пакетов символьной обработки при решении уравнений,

дифференцировании, интегрировании и т. д.;

– разработки упрощенных версий систем ИИ;

– создания естественно-языковых интерфейсов для существующих

программ;

– перевода текстов с одного языка на другой, в том числе – с одного

языка программирования на другой.

Программирование на языке Пролог состоит из следующих этапов:

• объявления некоторых фактов об объектах и отношениях между ними,

• определения некоторых правил об объектах и отношениях между ними;

• формулировки вопросов об объектах и отношениях между ними.

Понятие предиката

Теоретической основой Пролога является раздел символьной логики, называемый исчислением предикатов. Предикат - это логическая функция, которая выражает некоторое отношение между своими аргументами и принимает значение "истина", если это отношение имеется или "ложь", если оно отсутствует.

Рассмотрим понятие предиката в Прологе на примере родословной Рюриковичей.

Вначале запишем отношения типа родитель – ребенок. В синтаксисе Пролога выражение «Игорь является родителем Святослава» выглядит следующим образом:

parent (игорь, святослав).

 

Здесь родитель parent – это имя предиката, а «игорь» и «святослав» – аргументы. Аргументы игорь и святослав являются константами, поэтому записаны строчными буквами. С прописной буквы в Прологе начинаются переменные. Точка означает конец предиката, так же, как и конец предложения на естественном языке.

 

Рис. 1.1. Родословная Рюриковичей

 

 

Запишем также родительские отношения для других членов генеалогического дерева:

parent(рюрик, игорь). parent(ефанда, игорь).

parent(ольга, святослав). parent (игорь, святослав).

parent(святослав, святополк).parent(куно, святополк). и т.д.

Полученный набор предикатов образует базу знаний.

В Прологе запрос на извлечение знаний описывается такими же предикатами, какими эти знания представляются. Если мы подставим Прологу такой предикат цели:

? parent(ефанда, игорь).

Эта цель может быть прочитана следующим образом: Является ли Ефанда родителем Игоря? Сопоставив эту цель с содержимым базы знаний, Пролог установит, что данное утверждение истинно и сообщит об этом.

Запрос «Кто является родителями Игоря?» в Прологе выглядит следующим образом:

? parent(X, игорь).

Здесь X является переменной, которой должны быть присвоены искомые значения. Переменная в Прологе является аналогом местоимения или вопросительного слова. Из приведенной выше базы знаний Пролог извлечет два ответа:

X = рюрик

X = ефанда

Мы можем сформулировать вопрос следующим образом: Есть ли у Игоря родители?

parent(_, игорь).

Пролог выдаст ответ: Yes.

Переменная, начинающаяся со знака подчеркивания называется анонимной переменной и может принимать любые значения (аналог местоимения некто).

Для более сложных запросов в Прологе используются цели, состоящие из нескольких предикатов. Давайте найдем, чьим внуком является Ярослав Мудрый.

Запрос будет выглядеть следующим образом:

? parent(X, ярослав), parent(Y, X).

Данная запись означает: Найти Y, являющийся родителем X, который, в свою очередь, является родителем Ярослава. Запятая в прологе идентична союзу "И" или конъюнкции. В ответ на такой запрос Пролог выдаст следующий ответ:

X = святослав

Y = малуша

Можно выдать следующий запрос:

? parent(ольга, _).

Теперь анонимная переменная использована в качестве второго аргумента.

Этот запрос можно прочитать следующим образом: Есть ли у Ольги дети?

Пролог выдаст ответ: Yes.

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

Таким образом, программа на Прологе состоит из предикатов.

Программа на Прологе и база знаний - синонимы. Цель формулируется также в виде предикатов. Выполнение программы на Прологе – это резолюция цели.