57 (Вопросы по разным темам с ответами (программирование))

57. Основные синтаксические конструкции языка ПРОЛОГ. Декларативный принцип записи логических программ.

Название языка "Пролог" происходит от слов ЛОГическое ПРОграммирование (PROgrammation en LOGique во французском варианте и PROgramming in LOGic — в английском).

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

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

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

Соответственно и языки программирования делят на императивные и декларативные.

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

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

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

Далее конструкции представлены в так называемой нормальной формой Бэкуса-Наура (БНФ.

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

Предложения бывают двух видов: факты, правила.

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

A:-

B₁,... , B_n.

A называется заголовком или головой предложения, а B₁,..., B_n - телом.

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

Например, известный нам факт, что Наташа является мамой Даши, может быть записан в виде:

мама(Наташа, Даша).

Факт представляет собой безусловно истинное утверждение.

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

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

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

Некоторые предикаты уже известны системе, они называются стандартными или встроенными.

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

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

В нотации БНФ правило будет иметь вид:

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

Пример. Известно, что бабушка человека - это мама его мамы или мама его папы.

бабушка(X,Y):-

мама(X,Z),мама(Z,Y).

бабушка(X,Y):-

мама(X,Z),папа(Z,Y).

Символ ":-" означает "если", и вместо него можно писать if.

Символ "," - это логическая связка "и" или конъюнкция, вместо него можно писать and.

В данном примере X, Y и Z - это переменные.

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

Переменные могут быть свободными или связанными.

Свободная переменная - это переменная, которая еще не получила значения. Она не равняется ни нулю, ни пробелу; у нее вообще нет никакого значения. Такие переменные еще называют неконкретизированными.

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

Областью действия переменной в Прологе является одно предложение. В разных предложениях может использоваться одно имя переменной для обозначения разных объектов. Исключением из правила определения области действия является анонимная переменная, которая обозначается символом подчеркивания "_". Анонимная переменная применяется в случае, когда значение переменной не важно. Каждая анонимная переменная - это отдельный объект.

Третьим специфическим видом предложений Пролога можно считать вопросы.

Вопрос состоит только из тела и может быть выражен с помощью БНФ в виде:

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

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

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

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

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

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

Можно сказать, что утверждение - это правило, а факт или вопрос - это его частный случай.

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

мама("Наташа","Даша").

мама("Даша","Маша").

Можно спросить у системы, является ли Наташа мамой Даши. Этот вопрос можно ввести в виде:

мама("Наташа","Даша")

Найдя соответствующий факт в программе, система ответит "Yes" (то есть "Да"). Если мы спросим:

мама("Наташа","Маша")

то получим ответ "No" (то есть "Нет"). Можно также попросить вывести имя мамы Даши:

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

Система сопоставит вопрос с первым фактом, конкретизирует переменную X значением "Наташа" и выдаст ответ:

X=Наташа

1 Solution

Если надо получить ответ на вопрос: есть ли информация о людях, находящихся в отношении "мама - дочка", то его можно сформулировать в виде:

мама(_,_),

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

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

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

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

Пример:

max2(X,Y,X):-

X>Y,!./* если первое число больше второго,

то первое число - максимум */

max2(_,Y,Y). /* в противном случае максимумом будет

второе число */

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

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

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

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

Процедура

S:-

<условие>,!,P.

S :-

P2.