Основные понятия языка Prolog

Нормальная форма Бэкуса-Наура (БНФ), разработана в 1960 Джоном Бэкусом и Питером Науром и используется для формального описания синтаксиса языков программирования.

::= – "по определению" ("это", "есть"). Слева от разделителя располагается объясняемое понятие, справа - конструкция, разъясняющая его.

<> – для обозначения синтаксической конструкции

| – или

[] – необязательная конструкция

«-:» – если

«,» – и

«;» – или

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

1. Факты

2. Правила

Предложение имеет вид:

–заголовок, – тело.

Факт констатирует, что между объектами выполнено некоторое отношение. Он состоит только из заголовка. Можно считать, что факты – это предложения, у которого тело пустое. Факт представляет собой безусловно истинное утверждение. В Математической логике отношение называютпредикатами.

Предикат в форме БНФ:

<Предикат>::=<Имя> | <Имя>(<аргумент>[,<аргумент>]*),

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

Аргументов или параметром предиката может быть константа, переменная или составной объект. Число аргументов называется его арностью или местностью. Некоторые предикаты уже известны системе, они называются стандартными иливстроенными.

В turbo prolog предложения с одним и тем же предикатом в заголовке должны идти одно за другим. Такая совокупность предложений называется процедурой.

Правила - это предложения, истинность которого зависит от истинности одного или нескольких предложений. Обычно правила содержат несколько хвостовых целей, которые должны быть истинными для того, чтобы правило было истинным. В нотации БНФ правило будет иметь вид:

<Правило>::=<предикат>:-<предикат>[,<предикат>]*.

Примеры факта: мама("Наташа", "Даша").

Пример правила:

бабушка(X,Y):- мама(X,Z),мама(Z,Y).бабушка(X,Y):- мама(X,Z),папа(Z,Y).

– переменные.

Имя переменной в TP может состоять из букв латинского алфавита, цифр, знаков «_» и должно начинается с прописной буквы или «_». Переменная в прологе обозначает объект, а не некоторую область памяти. Пролог не поддерживает механизм деструктивного присваивания, позволяющего изменять значения инициализированной переменной, как в императивных языках. Переменные могут быть свободными или связанными.

Свободная переменная – та, которая еще не получила значение. У неё нет никакого значения (ни ноль ни символ пробела). Второе название – неконкретизированная.

Переменная, которая получила какое-то значение и оказалась связанной с определённым объектом называетсясвязанной.

Областью действия переменной в прологе является одно предложений. В разных предложениях может использоваться одно имя переменной для обозначения разных объектов.

Исключение из правила определения правила области действия является анонимная переменная, которая обозначается «_». Каждая анонимная переменная - это отдельный объект.

Третьим специфическим видом предложений пролога можно считать вопросы. Вопрос состоит только из тела и может быть выражен с помощью БНФ в следующем виде:

<Вопрос>::=<Предикат>[,<Предикат>]*

Вопросы используют для выяснения выполнимости некоторого отношения между описанными в программе объектами. Система рассматривает вопрос, как цель, к которой надо стремиться. Ответ на вопрос может оказаться положительным или отрицательным в зависимости от того, может ли быть достигнута соответствующая цель.

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

Если внутренней цели в программе нет, то после запуска программа выдает приглашение вводить вопросы в диалоговом режиме. Программа, компилируемая в исполняемый файл обязательно должна иметь внутреннюю цель.

Если цель достигнута, система отвечает, что у неё есть информация, позволяющая сделать вывод об истинности вопроса – «Yes». Если достичь цели не удалось, то система ответит «No». Если в вопросе содержатся переменные, то система выдает их значения, приводящее к решению, если решение существует, либо сообщает, что решение нет – «No solution». Можно сказать, что утверждение - это правило, а факты или вопросы – это его частный случай.

Вопрос:

мама(X,Даша).

Ответ:

X=Наташа1 Solution

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

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

Пример предиката, который будет находить максимум из двух чисел:

max(X,Y,X):- X>Y. /* если первое число больше второго, то первое число - максимум */ max(X,Y,Y):- X<Y. /* если первое число меньше второго, то второе число - максимум */ max(X,Y,Y):- X=Y. /* если первое число равно второму, возьмем в качестве максимума второе число */

Второй способ:

max(X,Y,X):- X>Y. /* если первое число больше второго, то первое число - максимум */ max(X,Y,Y):- X<=Y./* если первое число меньше или равно второму, возьмем в качестве максимума второе число */

В данной ситуации нам пригодится встроенный предикат «!», который называется cut (отсечение). Этот предикат предназначен для ограничения пространства поиска с целью повышения эффективности работы программ, он всегда завершается успешно. После того, как до него дошла очередь, он устанавливает «запор», который не даёт «откатится назад», чтобы выбрать альтернативные решения для уже «сработавших» подцелей, то есть для тех, которые расположены левее отсечения. На цели, расположенные правее отсечение не влияет. Кроме того, отсечение отбрасывает все предложения процедуры, расположенные после предложения, в котором расположено отсечение.

max2(X,Y,X):- X>Y,!./* если первое число больше второго, то первое число - максимум */max2(_,Y,Y). /* в противном случае максимумом будет второе число */

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

Примером красного отсечения имеется в реализации max2. Если убрать отсечение, предикат будет выдавать в качестве максимума 2 число, даже если оно меньше первого. Пример зелёного отсечения можно получить, если в запись с предикатом макс добавить отсечение. При их наличии предикат будет выдавать те же решения, что и без них.

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

S:- <условие>,!,P. S :- P2.