Краткие сведения. Пролог, родившийся, как и многие языки программирования, в начале 70-х годов, к настоящему времени так и не стал промышленным языком программиро­вания: для

Пролог, родившийся, как и многие языки программирования, в начале 70-х годов, к настоящему времени так и не стал промышленным языком программиро­вания: для написания прикладных систем Пролог используется крайне редко. В своем большинстве программисты-практики Пролога не знают или оценивают его невысоко. Еще в конце 80-х годов такие крупные фирмы программного обеспе­чения, выпускающие системы программирования, как Вог1апс1 1п1егпаИопа1,

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

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

1) объявление фактов об объектах и отношениях между ними;

2) определение правил взаимосвязи объектов и отношений между ними;

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

Основная операция, выполняемая в языке Пролог, — это операция сопоставле­ния (называемая также унификацией или согласованием). Операция сопоставления может быть успешной, а может закончиться неудачно, и определяется так:

1) константа сопоставляется только с равной ей константой;

2) идентичные структуры сопоставляются друг с другом;

3) переменная сопоставляется с константой или с ранее связанной перемен­ной (и становится связанной с соответствующим значением);

4) две свободные переменные могут сопоставляться (и связываться) друг с дру­гом; с момента связывания они трактуются как одна переменная: если одна из них принимает какое-либо значение, то вторая немедленно принимает то же значение.

Факты — это предикаты с аргументами-константами, обозначающие отноше­ния между объектами или свойства объектов, именованные этими константами. Факты в программе считаются всегда и безусловно истинными и таким образом служат основой доказательства, происходящего при выполнении программы.

Правила — это хорновские фразы с заголовком и одной или несколькими под­целями-предикатами. Правила имеют форму

< голова правила>: - < список подцелей>

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

Переменные в Прологе получают свои значения в результате сопоставления с константами в фактах и правилах.

Вопрос — отправная точка логического вывода, происходящего при выполне­нии программы. На любой вопрос компьютер будет пытаться дать ответ «Да» или «Нет» в зависимости от того, согласуется или нет утверждение, стоящее в вопро­се, с фактами и правилами базы знаний. Вопрос, не содержащий переменных, является общим: «имеет ли место факт...?».

Вопрос, в котором имеются переменные, является частным: «для каких зна­чений переменных факт... имеет место?». В процессе сопоставлений при выпол­нении программы переменные конкретизируются — получат значения тех кон­стант, для которых сопоставление запроса в целом успешно, и будут выведены на экран. Для интерпретатора Пролога существенны только совпадения и разли­чия имен, а также связи между предикатами, устанавливаемые с помощью конъ­юнкций и импликаций. Однако в Прологе существуют предопределенные имена (встроенные предикаты), которые позволяют выполнить арифметические опера­ции, сравнения, графические построения, ввод-вывод и другие полезные опера­ции как побочный продукт выполнения программы. Встроенные предикаты Ап1у- Рго1о§ описаны в справке по системе программирования, вызываемой нажатием клавиши Р1.

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

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

В системах логического программирования рекурсия служит также для описа­ния циклов, повторений и является важнейшим методом программирования.

В общем виде рекурсия на Прологе выглядит так:

Р(1,. •.).

Р(п,...): - 01/..., 0п, Р(п-1,...), К1,...Кш.

Правило Р обращается само к себе, при этом происходит углубление рекурсии. Предикаты (Л,..., 0п выполняются на прямом ходе рекурсии, а Р1,..., Кт — на обратном; п — это некоторый условный параметр, входящий в условие продолже­ния рекурсии, а Р(1,...) — факт, завершающий процесс рекурсии.

Особенно простым случаем рекурсии является простое циклическое повторе­ние. Один из способов организации повторения связан с наличием в базе знаний процедуры вида

гереа-Ь.

гереа" Ь: - гереа" Ь.

Использование гереШ в качестве подцели некоторого правила приводит к мно­гократному повторению остальных подцелей этого правила.

Управление процессом просмотра предложений является важным аспектом программирования на Прологе. Это осуществляется с помощью специальной встро­енной функции «резать», обозначаемой символом «!».

Данная встроенная функция может быть использована для достижения следую­щих трех целей:

1) исключения бесконечной петли при выполнении программы;

2) программирования взаимоисключающих утверждений;

3) блокирования просмотра целей.

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

Список можно задать перечислением элементов. Например, имена учеников класса:

[саша, петя, дима, ксюша, лена].

Элементами списка могут быть не только атомы, но и функции и вообще лю­бые элементы, даже списки. Заранее дайна списка не задается, и в ходе выполне­ния программы она может меняться.

Альтернативный способ задания списка использует понятия головы и хвоста списка. Например, в списке [х | У] х — это голова списка, а у — его хвост. Хвост списка по определению также является списком.

Теперь список может быть определен рекурсивно:

пустой список [] —список;

[Х|У] — список, если у — список.

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

1) из факта, ограничивающего рекурсию и описывающего операцию для пус­того списка;

2) из рекурсивного правила, определяющего операцию над списком, состоящим из головы и хвоста (в голове правила), через операцию над хвостом (в подцели).

Арифметические операторы. Арифметическое выражение состоит из функтора и его аргументов. Функтор — арифметическая операция; аргументы — целые или переменные, они являются операндами для функтора. Например: + (х, 1). Пролог позволяет использовать инфиксную нотацию. Например: х+1. Можно использовать арифметические выражения вида: х+у, х-у, х*у, х/у (обычное деление, результат — действительное число), х//у (целое деление, ре­зультат — целое число), х^ау (возведение в степень); - х;

х/\у (конъюнкция; только т!) (аыэ), х\/у (дизъюнкция; т{) (ок),

\ (X) - ЮТ (только 1п1),

х< < у — смещение х влево на у позиций (л.п*:), х> > у — смещение х вправо (л.п*:), [X] — оценить (приблизительное вычисление) х, х гсюс! у — выдает остаток от деления х на у, аЪз(X) — абсолютное значение (х),

асоз(X) — агссоз (X) аз1П (X) — агсзл_п(Х) а-Ьап(Х) — агс-Ьд(Х), соз(Х), ехр (X), 1п (X), 1од(Х), 31П (X), здгЪ(X), Ъд(Х), гоипс! (X, ы) — округление х до N символов после запятой, (N< =15).

Предикаты сравнения (Е1 и Е2 — арифметические выражения). Е1> Е2 проверяет, больше ли значение Е1 значения Е2; аналогично: Е1< Е2, Е1> =Е2, Е1< =Е2;

х 15 Е1 — Е1 вычисляется и сопоставляется с х; Е1=: =Е2 — вычисляются Е1 и Е2 и проверяются на эквивалентность; Е1=\=Е2 — вычисляются Е1 и Е2 и проверяются на неравенство; гапс1от15е (+5еес1) — переустановка генератора случайных чисел (аргумент 5еес1 — целый);

1пс (+х, -У) — увеличение целого х и возврат в у; с1ес (+х/-у) — уменьшение целого х и возврат в у.

Контрольные вопросы

1. Каковы отличия программы на Прологе от программ на процедурных языках программирования?

2. Какова сфера применения языка Пролог?

3. Каковы основные элементы программы на Прологе?

4. Какие типы данных используются в Прологе?

5. Что такое имена? переменные'?

6. Что такое факт, что он выражает? Приведите примеры.

7. Что такое правило, что оно выражает? Приведите примеры.

8. Какова роль вопроса в программе на Прологе?

9. Что такое сопоставление'?

10. Что такое конкретизация переменных?

11. Какая стратегия логического вывода реализована в Прологе?

12. Какова роль рекурсии в программах на Прологе?

13. Для чего служат списки в программах на Прологе?

14. Каким образом можно управлять процессом логического вывода при реше­нии задачи на Прологе?