SoftCraft
разноликое программирование

Отправная точка
Программирование
Windows API
Автоматы
Нейроинформатика
Парадигмы
Параллелизм
Проектирование
Теория
Техника кодирования
Трансляторы
Учебный процесс
Прочие вопросы

Разное

Беллетристика
Брюзжалки
Цели и задачи
Об авторе


Декларативное программирование


[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]


© 2003 И.А. Дехтяренко

6.1. Пролог

В целях природы обуздания,
В целях рассеять неученья
Тьму
Берем картину мирозданья - да!
И тупо смотрим, что к чему...

Аркадий и Борис Стругацкие

Разнообразие диалектов Пролога не столь велико, как у Лиспа и различия между ними не так существенны.  Для определенности будем использовать SWI-Prolog, который, как почти все реализации в основном следует знаменитому эдинбургскому Прологу для DEC-10.

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

?- true.

Yes

?- fail.

No

Встроенные предикаты true и fail представляют соответственно тождественно истинное и тождественно ложное высказывание. Ответ на первый вопрос всегда "да" , а на второй "нет". Говорят, что запрос true заканчивается успехом, а  fail - неудачей. Точно так же любой запрос завершается либо успехом, либо неудачей.

?- integer(1).

Yes

?- 3+4 < 3*2.

No

?- write('привет').
привет

Yes

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

Есть еще одна возможность - запрос может завершиться ошибкой.

?- abracadabra.
ERROR: Undefined procedure: abracadabra/0

?- 3/0 > 1.
ERROR: //2: Arithmetic: evaluation error: `zero_divisor'

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

Имея некоторый опыт работы с функциональными языками, мы можем попытаться найти сумму чисел

?- 2 + 3.
ERROR: Undefined procedure: (+)/2

и получаем сообщение об ошибке. Наш запрос не имеет формы предложения. Попробуем по другому.

?- write(2+3).

2+3
Yes

Система выводит выражение, даже не пытаясь что-нибудь вычислить. Может быть так?

?- X = 2+3.

X = 2+3
Yes

Снова неудача. Пролог разрабатывался прежде всего как язык обработки символьной информации и выражения вида "2+3" - это его объекты данных (они называются термами). Именно это выражение и присваивается переменной X. Но надо же как то выполнять арифметические  вычисления. Для этого предназначены специальные арифметические предикаты.

?- X is 2+3.

X = 5
Yes

Наконец то! Предикат is вычисляет значение выражения и присваивает его переменной. Запрос завершается  успехом и значение переменной выводится в качестве ответа.

Другие арифметические предикаты ( =:=, =\=, <, =<, >, >= ) вычисляют оба своих аргумента и сравнивают их значения.

?-  3 + 2 =:= 5.

Yes

?- 2 * 2 =:= 2 + 2 .

Yes

?- exp(2) >= sin(2) .

Yes

Другая разновидность примитивных объектов - атомы. Чаще всего они записываются как последовательности букв и цифр, начинающейся со строчной буквы. Это отличает их от переменных, которые начинаются с прописной буквы. Атомы можно сравнивать посредством предикатов  == , \==, @<, @=<, @>, @>= . Арифметические предикаты для этого не подходят, поскольку они попытаются вычислить арифметические значения атомов, что приведет к ошибке. А вот числа (но не значения выражений) можно сравнивать и теми и другими.

?- a @< b.
Yes

?- 1 @< 2.
Yes

?- 2 < a.
ERROR: Arithmetic: `a/0' is not a function

?- 2 < e.
Yes

Почему последний запрос успешен, догадайтесь сами.

?- X is 2+3.


X = 5
Yes

?- Y is X+1.
ERROR: Arguments are not sufficiently instantiated

В сообщение об ошибке указано что переменная(имеется в виду X) не конкретизирована. Но мы же только что присвоили ей значение! Дело в том, что это уже другая переменная. Область действия переменной распространяется только на один запрос. Но запросы могут быть и сложными, состоящими из нескольких целей.

?- X is 2+3, Y is X+1.

X = 5
Y = 6

Yes

Пока наша возможность задавать  вопросы ограничена. Чтобы задавать более интересные вопросы, надо загрузить какую-нибудь программу. Это можно процедурой consult, для которой придумано сокращение. Например, если программа находиться в файле 'my_program.pl', то ее можно загрузить, введя

?- consult(my_program).

или

?- [my_program].

А команда

?- [my_program,another_program,yet_another_program].

загрузит сразу все указанные программы. Но прежде чем загружать программу надо ее написать.

Программы.

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

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

Возьмем в качестве примера фрагмент базы данных небольшой компании Horns&Hoofs Ltd. Одноместный предикат employee устанавливает свойство "быть работником".

employee(anthony).
employee(barbara).
employee(charles).
employee(diana).
employee(edward).
employee(frederic).
employee(gregory).
employee(herbert).
employee(isabella).
employee(john).

Вообще то, имена собственные положено писать с прописной буквы, но в Прологе имена отношений и объектов должны начинаться со строчной буквы или заключаться в кавычки. Как правило, предпочитают обходится без кавычек. Программа может содержать предикаты с одинаковыми именами, но с разным количеством аргументов. Чтобы различать их употребляют имена состоящие из имени предиката и его арности. Полное имя только что определенного предиката: employee/1.

Предикат salary/2 устанавливает оклад каждого работника.

salary(anthony,500).
salary(barbara,200).
salary(charles,180).
salary(diana, 150).
salary(edward,150).
salary(frederic,140).
salary(gregory,150).
salary(herbert,100).
salary(isabella,90).
salary(john,160).

Предикат boss/2 устанавливает описывает организационную структуру компании. Утверждение boss(A,B) означает, что B - руководитель A.

boss(barbara, anthony).
boss(charles, anthony).
boss(diana,   barbara).
boss(edward,  barbara).
boss(frederic,charles).
boss(gregory, charles).
boss(herbert, charles).
boss(isabella,gregory).
boss(john,    gregory).

Загрузив программу, можно задавать вопросы, непосредственно к ней относящиеся.

?- [hh].
% hh compiled 0.00 sec, 0 bytes
Yes

?- employee(anthony).
Yes

?- employee(ronald).
No

?- boss(barbara, anthony).
Yes

Это простейший тип вопросов. Система просто проверяет записано ли некоторое предложение в программе и отвечает "да" если это так или "нет" в противном случае. Таким образом, предложение считается ложным, если явно не записано обратного.

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

?- salary(charles,S).

S = 180
Yes

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

?- boss(A,charles).

A = frederic
Yes

Но это не единственный ответ. Отвечая на вопросы с переменными система, выдав значение ждет нажатия на Enter. На самом деле, она интересуется нужны ли нам другие ответы. Нажимая на Enter мы говорим "спасибо, достаточно" и система отвечает Yes. Чтобы получить другие ответы надо ввести ";".

?- boss(A,charles).

A = frederic ;
A = gregory ;
A = herbert ;
No

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

?- boss(A,B).

A = barbara
B = anthony ;

A = charles
B = anthony ;

A = diana
B = barbara

Yes

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

?- boss(A,_).

A = barbara ;
A = charles ;
A = diana ;
A = edward
Yes

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

?- boss(A,B), salary(A,SA), salary(B,SB), SA > SB.

A = john
B = gregory
SA = 160
SB = 150 ;

No

и обнаружим непорядок: оклад Джона больше, чем у Грегори.

Кроме конъюнкции для соединения предложений можно применять и дизъюнкцию, которая обозначается точкой с запятой ";".

?- salary(X,S),(S<100;S>200).

X = anthony
S = 500 ;

X = isabella
S = 90 ;

No

Отрицание обозначается "\+" (или not, но эта форма, хотя и привычная, не рекомендуется).

?-  \+ employee(X).

No

Запрос означает "не существует ни одного работника", что, конечно, ложно.

?- \+ (employee(X),salary(X,300)).

X = _G157
Yes

А этот запрос "не существует ни одного работника с окладом 300". Таких работников, действительно, нет. Переменная X осталась свободной (не получила никакого значения), поэтому в качестве значения выводится нечто маловразумительное.

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

?- employee(X), \+ boss(_,X).

X = diana ;
X = frederic ;
X = herbert ;
X = isabella ;
X = john ;
No

?- employee(X), \+ boss(X,_).


X = anthony ;
No

Найдем самого высокооплачиваемого работника.

?- salary(A,Smax), \+ (salary(_,S), S>Smax).

A = anthony
Smax = 500
S = _G161

Yes

Интересное применение отрицания - конструкция (\+ (Q, \+ P)), которая проверяет, что все решения Q будут решениями для P. Например

?- \+ (employee(X), \+ salary(X,_)).

X = _G157
Yes

Это буквально означает "не существует работника, не имеющего оклада" или "все работники имеют оклады". В SWI-Prolog есть встроенный предикат forall, имеющий тот же смысл.

?- forall(employee(X), salary(X,_)).

X = _G157
Yes

Кроме фактов - безусловно истинных предложений, в программы можно включать и условные предложения - правила, которые определяют новые предикаты в терминах уже существующих. Каждое правило состоит из двух частей, разделенных символом ":-". Левая часть правила - заголовок описывает предикат, а правая - тело определяет условия, при которых он истинен. Телом может быть любой запрос, который и выполняется при вызове предиката, определенного в заголовке. Например, можно оформить в виде правил, вопросы, которые мы задавали.

all_paid :- forall(employee(X), salary(X,_)).

costly(A) :- boss(A,B), salary(A,SA), salary(B,SB), SA > SB.

noboss(A) :- employee(A), \+ boss(_,A).

boss(B) :-  boss(_,B).

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

?- all_paid.

Yes


?- costly(A).

A = john ;
No


?- noboss(A).

A = diana ;
A = frederic ;
A = herbert ;
A = isabella ;
A = john ;
No

?- boss(charles).

Yes

?- boss(B).

B = anthony ;
B = anthony ;
B = barbara ;
B = barbara ;
B = charles ;
B = charles ;
B = charles ;
B = gregory ;
B = gregory ;
No

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

Предикаты, которые мы определили очень похожи на представления, применяемые в реляционных СУБД. Представление или вид (view) хранится в базе как запрос, но обращаться с ним можно как с таблицей. Точно так же предикат определенный правилом, ничем не отличается от предиката определенного перечислением фактов. Например, определив

employee(anthony, none,    500).
employee(barbara, anthony, 200).
employee(charles, anthony, 180).
employee(diana,   barbara, 150).
employee(frederic,charles, 140).
employee(gregory, charles, 150).
employee(herbert, charles, 100).
employee(isabella,gregory, 90).
employee(john,    gregory, 160).

и затем

employee(A) :- employee(A,_,_).
salary(A,S) :- employee(A,_,S).
boss(A,B) :- employee(A,B,_),B \== none.

получим предикаты, неотличимые от тех, которые определили в начале.

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

near(A,B) :- boss(A,B).
near(A,B) :- boss(B,A).

Конечно, это можно записать и одним предложением

near(A,B) :- boss(A,B); boss(B,A).

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

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

employee(anthony) :- true.
employee(barbara) :- true.
...

До сих пор наши запросы находились в рамках реляционной алгебры. Теперь мы выйдем за эти границы. Отношение boss устанавливает непосредственного начальника работника. Но у этого же работника могут быть и другие начальники - начальник его начальника, начальник начальника его начальника и т.д. Определим отношение chief, обобщающее отношение boss.

chief(A,C) :- boss(A,C).
chief(A,C) :- boss(A,B), chief(B,C).

Это рекурсивно определенное отношение позволяет находить всех начальников.

?- chief(john,X).

X = gregory ;

X = charles ;

X = anthony ;

No

так же, как и всех подчиненных

?- chief(A,charles).

A = frederic ;

A = gregory ;

A = herbert ;

A = isabella ;

A = john ;

No

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

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

 birthday(anthony,1970,8,12).

Но Пролог позволяет нам объединить три элемента в одну структуру, которую назовем date.

 birthday(anthony,date(1970,8,12)).

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

?- birthday(anthony,D).

D = date(1970, 8, 12)

Yes

?- birthday(anthony,date(Y,_,_)).

Y = 1970

Yes

?- birthday(A,date(_,12,31)).

A = frederic

Yes

Имя date, как и порядок элементов выбрано произвольно. Можно было бы использовать и другие, например записывать дату как 12/8/1970 или 1970-8-12. Как мы уже могли убедиться, эти выражения, хотя и выглядят как арифметические, будут рассматриваться как структуры пока мы не применим к ним предикат is. И все же порядок год, месяц, число оказывается очень удобным. Дело в том, что предикаты типа @< позволяют сравнивать структуры, причем сначала выполняется сравнение первых компонент, затем если, они равны, вторых и т.д.

?- date(1970,8,20)@< date(1970,10,1).

Yes
Упражнение.
Определите отношение younger(A,B), означающее что A моложе B, для двух способов задания birthday.
Упражнение.
Пусть заданы три отношения
  1. haunt(Drinker, Bar) - Drinker посещает бар Bar;
  2. serves(Bar, Beer) - в баре Bar подают пиво сорта Beer;
  3. likes(Drinker, Beer) - Drinker любит пиво Beer.

Определите следующие предикаты

  1. happy(Drinker) - пиво, которое любит Drinker подают по крайней мере в одном из баров, которые он посещает.
  2. goodBar(Drinker, Bar) - здесь подают хотя бы один сорт хорошего пива.
  3. veryGoodBar(Bar) - все завсегдатаи этого бара найдут здесь пиво по вкусу.
  4. veryHappy(Drinker) - в любом баре, которые посещает Drinker, подают подходящее пиво.
  5. verySad(Drinker) - ни в одном из баров, где бывает Drinker, не подают приличного пива.
Еще раз о триггере.

Чтобы отвлечься от баз данных, рассмотрим задачу моделирования цифровых схем. Теперь мы не будем строить сомнительных предположений о характере изменения сигналов, а рассмотрим только устойчивые состояния схемы. Как и прежде будем представлять сигналы значениями 0 и 1. Элемент И-НЕ можно описать таблицей, связывающей значения двух входных сигналов с выходным.

nand(0,0,1).
nand(0,1,1).
nand(1,0,1).
nand(1,1,0).

Вместо проводов будем использовать переменные. Для того чтобы указать, что вход и выход элементов соединены, надо обозначить их одной переменной. Например, соединим выход элемента И-НЕ с одним из его входов, а на другой подадим сигнал 0.

?- nand(0,X,X).
X = 1
Yes

Теперь то же, но с 1.

?- nand(1,X,X).
No

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

Чтобы сконструировать RS-триггер достаточно взять два элемента И-НЕ и соединить их согласно схеме.

 rs(R,S,P,Q):- nand(S,P,Q), nand(R,Q,P).

Установив входные сигналы в 1 и 0, получим значения выходных.

?- rs(1,0,P,Q).
P = 0
Q = 1
Yes

Нетрудно найти и все устойчивые состояния триггера.

?- rs(R,S,P,Q).

R = 1
S = 1
P = 1
Q = 0 ;

R = 0
S = 1
P = 1
Q = 0 ;

R = 1
S = 1
P = 0
Q = 1 ;

R = 0
S = 0
P = 1
Q = 1 ;

R = 1
S = 0
P = 0
Q = 1 ;

No
Упражнение.
Как известно, "штрих Шеффера", реализуемый элементом И-НЕ образует полный базис системы булевых функций. Соберите из элементов И-НЕ элементы НЕ, И, ИЛИ. Из полученных частей соберите одноразрядный сумматор
add(A, B, CarryIn, Sum,CarryOut).
Соедините четыре таких сумматора в четырехразрядный сумматор.
Упражнение.
Наша модель не учитывает разницу между входными и выходными сигналами и дает возможность собирать "неправильные схемы", в которых выход одного элемента присоединен к выходу другого. Придумайте способ исправить это.

Синтаксис.

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

Обычно имеется два типа чисел: целые и вещественные. Кроме стандартного десятичного представления целых чисел, можно использовать двоичные, восьмеричные и шестнадцатеричные константы в духе Си (0b101, 0o777, 0xFFFF), а также запись с явным указанием основания (2'101, 8'777, 16'FFFF). Выражение вида 0'A представляет код символа A.

Атомы (или символы) представляют собой

  • последовательности произвольных знаков, заключенных в кавычки, или
  • последовательности букв, цифр и знаков подчёркивания, начинающейся со строчной буквы, или
  • последовательность специальных знаков (обычно ~@#$^&*-+=<>/\?), или
  • особые атомы: '!', '.', ',', ';', '[]', '{}'.

Как правило, в программах используются атомы без кавычек. Любой атом, который можно записать без кавычек, можно заключить в кавычки, получая при этом тот же атом.

Переменные - последовательности букв, цифр и знаков подчёркивания начинающиеся с прописной буквы или знака подчёркивания. Переменная, состоящая из единственного символа подчеркивания '_', называется анонимной переменной.

Составной терм (или структура) - запись вида атом(терм1,терм2,...термn).

Атом, стоящий перед скобками, называется функтором, а термы в скобках аргументами или компонентами. Число компонент называют арностью структуры. Названия "функтор" и "аргументы", как и форма записи связаны с естественной интерпретацией составного терма как имени объекта, полученного в результате применения функции к аргументам. Например, терм "+(2,3)" означает "результат применения операции + к числам 2 и 3". Однако, как мы уже убедились, это вовсе не "5" и даже не "сумма чисел 2 и 3". Пролог не приписывает определенного значения функторам и под "+" может подразумеваться что угодно. Составные термы можно рассматривать и как кортежи. Так терму "+(2,3)" соответствует кортеж {+,2,3} (в синтаксисе Erlang). Сложные термы удобно представлять в виде деревьев.

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

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

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

    Например, выражение a*1+b*2+c*3 будет прочитано как +( +( *(a,1), *(b,2)), *(c,3)), а выражение a,b;c,d как ;( ,(a,b), ,(c,d)). Обратите внимание на двоякое использование запятой в последнем выражении. Дополнительно можно уточнять структуру выражения посредством скобок.

  • Поскольку списки популярная и гибкая структура данных, Пролог обеспечивает систему обозначений для структур, которые представляют списки. Вообще, списки представляются структурами с функтором '.'. То есть, терм ".(H,T)" обозначает список, голова которого H а хвост T. Пустой список обозначается атомом []. Но дополнительно к этому используется система обозначений [H|T], которую можно рассматривать как синтаксический сахар.

    Список из атомов a, b и c может быть записан разными способами:

    • .(a, .(b, .(c, []))) - основное представление;
    • a. b. c. [] - используя объявление '.' как инфиксного оператора;
    • [a, b, c] - используя специальную нотацию для списков;
    • [a | [b | [c | []]]] - то же, но в развернутом виде.
  • Строки символов также популярная структура данных и для них тоже предусмотрена специальная нотация - вполне традиционная запись в двойных кавычках. Такая запись обозначает список кодов символов. Например, "string" - синтаксический сахар для [115,116,114,105,110,103], что в свою очередь - синтаксический сахар для .(115,.(116,.(114,.(105,.(110,.(103,[])))))).

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

?- display(8/12/1970).

/(/(8, 12), 1970)
Yes

?- display(a+b/c:[1,2,3]).

:(+(a, /(b, c)), .(1, .(2, .(3, []))))
Yes

Опрепаиоры часто используются, для того чтобы синтаксически соединять связанные термы. Например, предикат write выводит только один терм, но используя инфиксные операторы можно обойти это ограничение.

?- write(a=3:b->1:c-18).
a=3:b->1:c-18

Yes

Легко видеть, что синтаксис фактов практически не отличается от синтаксиса термов. Единственная разница - число не может быть фактом. Синтаксис правил также не отличается от синтаксиса термов, хотя на первый взгляд это не очевидно. Действительно, предложение a :- b,c,d может быть записано как :-(a, ,(b, ,(c,d))) и является лишь синтаксически подслащенной формой последнего. Одно и то же выражение может, в зависимости от контекста, обозначать как объект, так и отношение. Это важное свойство роднит Пролог с Лиспом.

Семантика

Семантику программы на Прологе можно определять с разных точек зрения.

Рассматривая программу как совокупность логических утверждений, получаем логическую или декларативную семантику программы. Любой основной запрос представляет собой некоторое утверждение. Это утверждение либо выводимо из программы (тогда оно полагается истинным), либо невыводимо (и значит ложно). Запрос, содержащий переменные, представляет экзистенциальное утверждение вида "существуют (x1,...xn), такие что Q(x1,...xn)", которое, опять же, может быть истинным или ложным. В первом случае найдутся некоторые термы, при подстановке которых вместо переменных получим истинное утверждение. Таким образом, декларативный смысл программы определяет, является ли данная цель истинной, и если - да, то при каких значениях переменных она превращается в истинное высказывание.

Операционная или процедурная семантика определяет процесс поиска ответа. Запрос рассматривается как последовательность целей, которые надо выполнить, а каждая процедура описывает как выполнить некоторую цель.

Наличие двух разных точек зрения на одну программу может показаться избыточным. Если нас интересует декларативный смысл программы, зачем вникать в подробности ее выполнения? Иногда в этом, действительно, нет необходимости. Но бывают и случаи, когда обойтись только декларативной семантикой невозможно.

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

Хуже того, программы могут оказаться не в сотоянии находить ответы. Изменим определение chief.

chief(X,Y):- chief(X,Z),boss(Z,Y).
chief(X,Y):- boss(X,Y).

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

?- chief(barbara,Y).
ERROR: Out of local stack

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

Некоторые процедуры вообще не имеют логического смысла и применяются исключительно ради побочного эффекта. Например, процедура на Прологе

sum :-
  read(A),
  read(B),
  C is A+B,
  write(C).

в целом соответствует процедуре на Паскале

proсedure sum;
var A,B,C :real;
begin
  read(A);
  read(B);
  C := A+B;
  write(C)
end;

Бесполезно пытаться определить логическую семантику предиката sum. Термин "предикат" в данном случае звучит несколько издевательски (так же, как и термин "функция" для print в Лиспе).

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

bonus(A,P) :- salary(A,S),percent(20,S,P).

можно записать как процедуру

proсedure bonus(var A:atom; var P:number);
var S :number;
begin
  salary(A,S);
  percent(20,S,P)
end;

или нарисовать схему

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

bonus(A,P) :- salary(A,S),merit(A),percent(20,S,P).

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

function bonus(var A:atom; var P:number):boolean;
var S :number;
begin
  bonus := salary(A,S) and merit(A) and percent(20,S,P);
end;

Новая схема предусматривает два выхода из каждой процедуры: успешный(exit) и неудачный(fail).

Пусть в базе записано

merit(gregory).

merit(herbert)

Рассмотрим выполнение запроса bonus(john,P). Получив этот запрос, Пролог ищет в базе данных предложения, относящиеся к bonus и обнаруживает правило, заголовок которого соответствует вопросу. Затем он вызывает процедуру bonus, передавая ей параметры, то есть переходит к цели salary(john,S), merit(john), percent(20,S,P). Теперь выполняется цель salary(john,S), в результате чего S получает значение 160. А вот вызов merit(john) завершается неудачей, а с ним неудачей завершается и весь запрос.

Теперь введем запрос bonus(A,P). Сначала он выполняется подобно предыдущему, но цель salary(A,S), оказывается недетерминированной: в базе присутствует несколько подходящих предложений. Поэтому, присвоив значения переменным {A=anthony,S=500}, Пролог запоминает что есть и другие возможности - создает точку выбора. Вторая цель принимает вид merit(anthony) и, поскольку такого предложения в базе нет, завершается неудачей. Но выполнение на этом не прекращается. Система совершает откат - отменяет присвоенные значения и повторно вызывает salary(A,S). Вот этого понятия повторного вызова процедуры и нет в Паскале. При повторном вызове salary возвратит пару {A=barbara,S=200}, затем {A=charles,S=180} и т.д. В конце концов будут получены значения {A=edward,S=150}. После этого вторая цель merit(edward) завершится успешно, также как и весь запрос. Но это еще не конец. Когда мы попросим Пролог выдать следующий ответ, снова включится механизм отката и будет повторно вызвана процедура bonus. Только после того как все возможные ответы исчерпаются, точка выбора будет удалена и произойдет окончательный выход из процедуры.

Чтобы отобразить эти процессы на схемах, добавим каждой процедуре еще один вход:redo, означающий повторный вызов процедуры. Этот вход соединяется с выходом fail следующей процедуры. Схема bonus приобретает вид

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

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

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

Многие предикаты устроены подобно true или == и не создают точек выбора. Предикат fail всегда завершается неудачно.

Рекурсивно определенные предикаты могут создавать бесконечные последовательности точек выбора, например.

repeat.
repeat :- repeat.

Предикат repeat всегда завершается удачно, а при повторном вызове вызывает сам себя. Это можно изобразить на схеме.

Запрос repeat,fail - надежное средство загнать программу в бесконечный цикл.

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

Встроенные предикаты.

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

Унификация.

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

?- 1 = 1.

Yes

?- a(1) = b(1).

No

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

?- X = 1.

X = 1
Yes

?- 2+3 = X.

X = 2+3
Yes

Как видно переменные могут находиться как слева, так и справа от знака '='.

?- X = 1, X = 1.

X = 1

Yes

?- X = 1, X = 2.

No

В первом примере переменная X сначала сопоставляется  с 1 и получает значение 1, затем это значение успешно сопоставляется  с 1 (1 = 1). Во втором примере X получает значение 1, которое затем сопоставляется с 2 (то есть фактически делается попытка унификации 2 = 1), что, конечно, завершается неудачей.

Возможно одновременное означивание нескольких переменных.

?- f(X,Y,Z) = f(a,b,g(c)).
X = a
Y = b
Z = g(c)
Yes

?- X+2 = 3+Y.

X = 3
Y = 2
Yes

Любая переменная сопоставляется сама с собой и не получает при этом никакого значения.

?- X = X.

X = _G160
Yes

Сопоставление двух различных переменных всегда успешно.

?- X = Y.

X = _G160
Y = _G160
Yes

Никаких значений переменные при этом не получают, но между ними устанавливается связь, таким образом, что в дальнейшем они будут выступать в качестве синонимов. Обратите внимание, что "значение" у X и Y одно и то же. Такие переменные называют сцепленными (не связанными, потому что "связанная переменная" означает то же что "конкретизированная" или "означенная" переменная, то есть "переменная, получившая значение").

?- X = Y, Y = Z, Z = a.

X = a
Y = a
Z = a
Yes

Здесь X связывается с Y, Y связывается с Z и, наконец, Z получает значение 'a'. После этого все три переменные имеют одно и то же значение 'a'.

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

  unify(X, X).

Отношение unify, определяемое этой программой ничем не отличается от '='.

?- unify( f(1,X), f(Y,2)).
X = 2
Y = 1
Yes

В действительности, предикат = обычно именно так и определяется .

  X = X.

Это просто означает, что механизм унификации встроен глубоко в недра Пролога.

Встроенный предикат \= сопоставляет два терма и успешен только в том случае если унификация невозможна.

?- X \= a.

No
Сравнение термов.

Предикаты  == , \== , @<, @=<, @>, @>= сравнивают любые термы. Для того, чтобы можно было сравнивать не только на равенство, на множестве всех термов определен стандартный порядок. Этот порядок устанавливается следующим образом.

  1. Переменные, упорядоченные "по возрасту". Переменная, которая встретилась первой будет меньше всех остальных.
  2. Атомы в лексикографическом порядке.
  3. Числа в арифметическом порядке.
  4. Составные термы, упорядоченные по арности, затем по имени функтора, затем по аргументам слева направо.

Место списков в этом порядке определяется их представлением как бинарных структур с функтором '.'

?- a @< -a .
Yes
?- f(a) @< [a] .
Yes
?- [a,b,c] @< f(a,b,c) .
Yes

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

?- sort([6,a,1,a,1,3,b,6],X).
X = [1,3,6,a,b]
Yes
?- msort([6,a,1,a,1,3,b,6],X).
X = [1, 1, 3, 6, 6, a, a, b]
Yes

Предикат keysort  обрабатывает списки, содержащие термы вида "ключ-значение". Он упорядочивает их по значениям ключей.

?- keysort([3-a,1-b,2-b,1-b],X).

X = [1-b,1-b,2-b,3-a]
Yes
Поиск всех решений.

Возможность получение различных ответов на вопрос путем отката полезна, но бывает недостаточной. Иногда требуется получить все ответы сразу. Для этого предназначены "множественные" предикаты findall, bagof и setof.

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

?- findall(A,boss(A,charles),L).

A = _G157
L = [frederic, gregory, herbert]

Yes

?- findall(A,boss(A,john),L).

A = _G157
L = []

Yes

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

?- findall(A=S,(boss(A,barbara),salary(A,S)),L).

A = _G157
S = _G158
L = [diana=150, edward=150]

Yes

?- findall(A,boss(A,B),L).

A = _G157
B = _G158
L = [barbara, charles, diana, edward, frederic, gregory,
herbert, isabella, john]

Yes

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

?- bagof(A,boss(A,B),L).

A = _G157
B = anthony
L = [barbara, charles] ;

A = _G157
B = barbara
L = [diana, edward] ;

A = _G157
B = charles
L = [frederic, gregory, herbert] ;

A = _G157
B = gregory
L = [isabella, john] ;

No

Свободная переменная B получает значения и для каждого из них выдается соответсвующий список значений A. Однако, bagof можно заставить выполняться подобно findall. Для этого надо явно указать какие переменные не должны получать значение.

?- bagof(A,B^boss(A,B),L).

A = _G157
B = _G158
L = [barbara, charles, diana, edward, frederic, gregory,
herbert, isabella, john]

Yes

Конструкция X^P действует подобно квантору существования ("существует некоторый X, такой что P").  Таким образом, запрос с findall выполняется так же как запрос с bagof, в котором все свободные переменные связаны квантором существования. Единственная разница: в случае отсутствия ответов bagof не возвращает пустой список, а завершается неудачей.

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

  setof(Var,Goal,Set) :- bagof(Var,Goal,Bag), sort(Bag,Set).

Сортировка выполняется потому, что упорядоченный список - общепринятое представление множеств в Прологе.

?- bagof(B,boss(B),L).

B = _G157
L = [anthony, anthony, barbara, barbara, charles, charles,
charles, gregory, gregory]

Yes

?- setof(B,boss(B),L).

B = _G157
L = [anthony, barbara, charles, gregory]

Yes
Упражнение.
Напишите запрос, который выдаст список пар (начальник-список его починенных).
Анализ термов.

Типовые предикаты позволяют проверить тип терма: является ли он составным (compound) или простым (atomic), а в последнем случае атом ли это (atom) или число (number), причем целое ли это число (integer) или вещественное (float).

?- atom(1).
No
?- atomic(1).
Yes
?- compound([1]).
Yes
?- compound([]).
No

Предикат var и его отрицание nonvar проверяют, является ли терм свободной переменной, а предикат ground - является ли терм основным.

?- var(X).
X = _G157 
Yes

?- X = a, var(X).
No

?- ground(a+X).
No

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

?- functor(a+b,F,A).
F = +
A = 2
Yes

?- arg(1,a+b,X).
X = a
Yes

functor(X,+,2), arg(1,X,2*a), arg(2,X,b).
X = 2*a+b
Yes

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

?- a + b =.. X.
X = [+, a, b]
Yes

?-  X =.. [f, 1, 2, 3].
X = f(1, 2, 3)
Yes

Еще один предикат - name позволяет делить неделимое. Он разбирает имя атома на отдельные символы или создает атом из списка символов.

?- name(atom,X).
X = [97,116,111,109]
Yes

?- name(A,"proton+electron").
A = 'proton+electron'
Yes
Металогические предикаты.

Предикаты findall, bagof и setof, так же как и \+ и forall основаны на унифицированном представлении термов и предложений. Они интерпретируют свои аргументы (которые являются термами, то есть объектами данных) как предложения (то есть как процедуры, подлежащие исполнению). Простейший предикат такого рода  call получает некоторый терм и вызывает его выполнение в качестве цели.

?- call(employee(john)).
Yes

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

?- functor(G,employee,1),arg(1,G,X),call(G).

G = employee(anthony)
X = anthony ;

G = employee(barbara)
X = barbara

Yes

В SWI-Prolog имеется целое семейство предикатов call/1, call/2, call/3  и т.п. позволяющих одновременно собирать терм, добавляя аргументы и вызывать его.

?- call(boss(isabella,B)).
B = gregory
Yes

?- call(boss(isabella),B).
B = gregory
Yes

?- call(boss,isabella,B).
B = gregory
Yes

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

?- G = (salary(edward,X),X>100),G.

G = salary(edward, 150), 150>100
X = 150
Yes

Предикаты call и метапеременные, подобно функциям eval и apply в Лиспе позволяют в некоторой степени реализовать возможности предикатов высшего порядка. Например, если бы дизъюнкция и "для всех" не были встроены в язык, мы могли бы определить их следующим образом.

A ; B :- A.
A ; B :- B.

forall(A, B) :- \+ (A, \+ B).

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

?- assert(suicide(X) :- retract(suicide(X))).

X = _G157
Yes

?- assert(suicide(1)).
Yes

?- suicide(X).

X = 1
Yes

?- suicide(X).
No

Предикат clause дает возможность выяснить, какие предложения находятся в базе данных.

?- clause(boss(A,B),Body).

A = barbara
B = anthony
Body = true ;

A = charles
B = anthony
Body = true ;

A = diana
B = barbara
Body = true

Yes
Управляющие конструкции

К управляющим конструкциям, в сущности, относятся конъюнкция, дизъюнкция и отрицание.
Выражение (A,B) обозначает "A /\ B" и в то же время указывает что сначала надо выполнить A, а потом B.
Выражение (A;B) обозначает дизъюнкцию целей "A \/ B". С процедурной точки зрения ";" означает точку выбора.
Исполнения (\+ A) начинается с вызова A. Если он завершается неудачей, то \+ A - успешно, и наоборот.

Конструкция (A -> B; C) логически означает то же что (A, B ; \+ A, C), но выполняется более эффективно - цель A вызывается только один раз. Если она завершается успешно, выполняется B, в противном случае C. Другими словами, это хорошо знакомый условный оператор.

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

?- employee(X),!.

X = anthony
Yes

Этот запрос теперь возвращает единственный ответ, потому что точка выбора, созданная подцелью employee(X) устраняется после выполнения '!'. Если отсечение встречается в теле предложения, то его действие распространяется вплоть до вызова этого предложения. То есть, отсекаются все еще не проверенные правила для этого предиката, если они существуют. Схематически это можно представить, соединив выход fail отсечения c выходом fail процедуры, его содержащей.

dp060111.gif (1357 bytes)

Давайте рассмотрим две процедуры.

test1(X) :- atom(X), write(atom(X)),nl.
test1(X) :- integer(X), write(integer(X)),nl.
test1(X) :- float(X), write(float(X)),nl.
test1(X) :- number(X), write(number(X)),nl.
test1(X) :- atomic(X), write(atomic(X)),nl.
test1(X) :- compound(X), write(compound(X)),nl.

test2(X) :- atom(X),!, write(atom(X)),nl.
test2(X) :- integer(X),!, write(integer(X)),nl.
test2(X) :- float(X),!, write(float(X)),nl.
test2(X) :- number(X),!, write(number(X)),nl.
test2(X) :- atomic(X),!, write(atomic(X)),nl.
test2(X) :- compound(X),!, write(compound(X)),nl.

и сравним два запроса

?- test1(1), fail.

integer(1)
number(1)
atomic(1)
No

Вызов test1(1) недерминирован, поскольку сопоставляется с несколькими правилами. Здесь создается точка выбора. Первое правило для test1 завершается неудачей и Пролог переходит ко второму. Это правило успешно выполняется, в результате чего выводится integer(1). Предикат fail, всегда неудачен и Пролог откатывается к точке выбора, где осталось еще четыре непроверенных правила. Затем процесс повторяется, пока все правила не будут исчерпаны.

?- test2(1), fail.

integer(1)
No

Теперь после удачного завершения integer(1) во втором правиле выполняется отсечение. В результате точка выбора, созданная при вызове test2, будет удалена и после fail выполнение запроса прекратится.

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

\+ A :- A,!,fail.
\+ A.

A -> B; C :- A,!,B.
A -> B; C :- C.

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

Предикаты ввода и вывода

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

В библиотеке можно найти массу разнообразных предикатов для ввода и вывода, но самые употребительные read и write. Предикат writeq аналогичен write, но при необходимости берет имена атомов в кавычки, так чтобы термы могли быть считаны посредством read. Предикат nl вызывает переход к следующей строке, а tab(N) выводит N пробелов. Более низкоуровневые предикаты get и put выполняют посимвольный (побайтный) ввод/вывод.

?- get(X),get(Y),put(Y),put(X).
|: ab
ba
X = 97
Y = 98
Yes

Предикат at_end_of_stream успешен когда достигнут конец потока ввода. В этом состоянии read возвращвет атом end_of_file, а get значение -1. Все эти предикаты читают данные со стандартного потока ввода и пишут в стандартный поток вывода. Предикаты see и tell перенаправляют соответственно ввод и вывод на указанные файлы, а seen и told восстанавливают стандартные значения.

Чтобы одновременно работать с несколькими файлами или другими источниками данных существуют аналогичные предикаты, имеющие на один аргумент больше. Например, write(Stream,Term) выведет Term в поток Stream. Предварительно надо открыть поток с помощью предиката open, а потом не забыть закрыть его предикатом close. Для примера две версии процедуры, копирующей файл.

copy_file(FileIn,FileOut):-
  see(FileIn),
  tell(FileOut),
  repeat,
    get(X),
    put(X),
  at_end_of_stream,
  seen,
  told.
copy_file(FileIn,FileOut):-
  open(FileIn,read,StreamIn),
  open(FileOut,write,StreamOut),
  repeat,
    get(StreamIn,X),
    put(StreamOut,X),
  at_end_of_stream(StreamIn),
  close(StreamIn),
  close(StreamOut).

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

Директивы

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

Директива dynamic указывает, что данный предикат динамический, то есть можно добавлять и удалять относящиеся к нему предложения. По умолчанию предикаты считаются статическими и не допускают модификации. Например, было бы вполне естественно объявить

:- dynamic employee/1, salary/2, boss/1.

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

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

Модули, пожалуй, наименее стандартизированная часть Пролога. Традиционно в Прологе используется одно "плоское" пространство имен. Современные реализации позволяют упрятывать локальные предикаты, но делают это всякая на свой лад. В SWI-Prolog исходные тексты могут быть "обычными" программами или модулями. Последние определяются директивой module, которая находится в начале файла. Например

:- module(module1,[p/1,q/2]).

определяет модуль с именем module1, экспортирующий предикаты p/1 и q/2. Команда use_module/2 загружает модуль и импортирует указанные предикаты, а use_module/1 импортирует все общедоступные предикаты. Например

:- use_module(module1).

означает то же, что

:- use_module(module1,[p/1,q/2]).

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

:- use_module(module1,[]).
...
module1:p(X),
module1:q(X,Y)

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

Управление синтаксисом.

Приближенно синтаксис Пролога можно описать следующими правилами

терм      ::= константа 
           | функтор"(" терм {","терм}")"
           | оператор терм 
           | терм оператор 
           | терм оператор терм
           | "(" терм ")".
константа ::= атом | число.
оператор  ::= функтор.
функтор   ::= атом.

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

Приоритет - целое число в диапазоне от 0 до 1200, определяющее старшинство оператора. Чем меньше приоритет, тем большей связывающей силой обладает оператор. Например, по умолчанию определены приоритеты '*', '/' - 400; "+","-" -500; ; "=","<" -700; "," -1000; ":-" - 1200.

Но одного приоритета бывает недостаточно, чтобы однозначно разобрать выражение. Например, "a-b-c" должно читаться как "(a-b)-c", "a,b,c" как  "a,(b,c)", а (a=b=c) - недопустимое выражение. Говорят что оператор "-" левоассоциативный, "," правоассоциативный, а "=" неассоциативный. Ассоциативность оператора задается вместе с его типом, например

op(700,xfx,=).
op(500,yfx,+).
op(1050,xfy,->).
op(500,fx,-).
op(900,fy,\+).

Здесь xfx означает "инфиксный неассоциативный". Буква "f" представляет сам оператор, "y" указывает, что на этом месте может находится терм с таким же или меньшим приоритетом, а "x" разрешает только терм с меньшим приоритетом. В Прологе нет предопределенных постфиксных операторов, но ничто не мешает ввести свои.

?- op(200,yf,!).
Yes

?- X = 5+3!,display(X).
+(5, !(3))
X = 5+3! 
Yes

Для того чтобы объявления операторов оказывали влияние на программу их надо задавать как директивы.

:- op(1070,fx,if).
:- op(1050,xfx,then).
:- op(1060,xfx,else).

if X then Y :- X,!, Y.
if X then Y .

if X then Y else Z :- X,!, Y.
if X then Y else Z :- Z.
Упражнение.
Как будут разобраны выражения (if a then b) и (if a then b else c) ?

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]