17 January 2009

Prolog, введение

Prolog
Довольно оживленное обсуждение предыдущей стати (http://habrahabr.ru/blogs/programming/47416/) показало, что тема пролога оказалась интересна сообществу.
Чтобы заинтересовать еще более читателя и вместе с тем облегчить ему начало работы с этим языком, я решил написать немного начальных данных о прологе.

Кратко основные особенности.


Типы данных

Числа

?- A = 12, B = -0.5e4.<br>
A = 12,<br>
B = -5000.0.<br>
<br>
?- number($A), number($B).<br>
true. % показываем, что тип переменных - числа<br>

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

Атомы

?- A = abc, B = 'Hello World'.<br>
A = abc,<br>
B = 'Hello World'.<br>
<br>
?- atom($A), atom($B).<br>
true. % показываем, что тип переменных - атомы<br>

Строки

?- S = "Привет мир".<br>
S = [1055, 1088, 1080, 1074, 1077, 1090, 32, 1084, 1080|...].<br>

Видно, что строки являются списками кодов символов, т.е. к ним применимы все те же операции что и к спискам, но об этом позже.

Списки

?- A=[], B=[a, foo, 123, [[[[[1,2,42]],bar]]], "Привет", A], C=[A,B].<br>
A = [], % пустой список<br>
B = [a, foo, 123, [[[[[1|...]], bar]]], [1055, 1088, 1080, 1074|...], []],<br>
C = [[], [a, foo, 123, [[[[...]|...]]], [1055, 1088|...], []]]<br>

Видим, что списки
1) могут быть разнородными (содержать любые комбинации выше- (и ниже-) перечисленных типов)
2) могут быть вложенными

Структуры

?- A = aaa(bb), B = aaa(bbbbbb, 123, [456, c]), C = ccc(ddd(eee), fff, g(h(i(j(kkkkk))))).<br>
A = aaa(bb),<br>
B = aaa(bbbbbb, 123, [456, c]),<br>
C = ccc(ddd(eee), fff, g(h(i(j(kkkkk)))))<br>

Пример осмысленнее:

?- Family = family(father(bill, age(37)), mother(ann, age(34)), children([son(john, age(10)), daughter(jill, age(8))])).<br>
Family = family(father(bill, age(37)), mother(ann, age(34)), children([son(john, age(10)), daughter(jill, age(8))]))<br>
<br>

Примеры посложнее:

?- A = aaa(foo, bar, "абв", [12, 13], 123.4e34), B = bbb(cc, A, [A, fff(A)]), C=foo(foo(foo(foo(bar)))), D=(+(2, *(3, -(7, 2)))).<br>
A = aaa(foo, bar, [1072, 1073, 1074], [12, 13], 1.234e+036),<br>
B = bbb(cc, aaa(foo, bar, [1072, 1073, 1074], [12, 13], 1.234e+036), [aaa(foo, bar, [1072, 1073, 1074], [12, 13], 1.234e+036), fff(aaa(foo, bar, [1072, 1073, 1074], [12, 13], 1.234e+036))]),<br>
C = foo(foo(foo(foo(bar)))),<br>
D = 2+3* (7-2)<br>
<br>
?- C=cc(1, C), cc(1, cc(1, B))=C, C=B. % B и С совпадают<br>
C = cc(1, **), % рекурсивная структура, с бесконечной вложенностью<br>
B = cc(1, **).<br>

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

Заметим, что между этими типами существует глубокая связь, например, списки есть ни что иное, как более красивое (синтаксический сахар) применение функтора "."

?- A = (.(1,.(2, .(aa, .(bbb, []))))).<br>
A = [1, 2, aa, bbb].<br>

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

?- [a,b,c,d] = (.(H, T)).<br>
H = a,<br>
T = [b, c, d].<br>

Хотя так никто не делает, в виду того, что для конструирования списков из головы и хвоста (а также обратное преобразование, т.е. разделение списка на голову и хвост) есть более удобный синтаксис вида [H | T].

?- [a,b,c,d] = [H | T].<br>
H = a,<br>
T = [b, c, d].<br>
<br>
?- Head = голова, Tail = [о, с, т, а, л, ь, н, о, е], List = [Head | Tail].<br>
Head = голова,<br>
Tail = [о, с, т, а, л, ь, н, о, е],<br>
List = [голова, о, с, т, а, л, ь, н, о|...].<br>
<br>
?- A = [a | [ b | [ c | [d | [] ] ] ] ]. % напоминает haskell, не так ли? )<br>
A = [a, b, c, d].<br>
<br>
?- [A,B,C | Tail] = [1,2,3,4,5,6].<br>
A = 1,<br>
B = 2,<br>
C = 3,<br>
Tail = [4, 5, 6].<br>

В равнозначности синтаксисов можно убедиться запросом

?- [H | T] = (.(H, T)).<br>
true. % т.е. справедливо при любых значениях неизвестных H и T.<br>

Как видим, тут проявляется на первый взгляд не совсем привычное поведение знака "=", а именно то, что он работает «в обе стороны». И это очень важный момент. Дело в том, что в прологе знак "=" обозначает не обычное (императивное) равенство (присвоение), а унификацию (что в других языках называется сопоставление с образцом), а именно сопоставление левой и правой части и в случае удачного сопоставления конкретизация неизвестных значений.
Фраза может выглядеть немного заумно, легче пояснить на примере.

?- aaa = bb. <br>
false. % сопоставление неудачно (атомы не совпадают)<br>
<br>
?- aaa = aaa.<br>
true. % удачно<br>
<br>
?- aaa(bbb) = aaa(bbb).<br>
true. % удачно (функторы и аргументы совпадают)<br>
<br>
?- aaa(bbb) = aaa(B).<br>
B = bbb. % удачно + выполнена конкретизация<br>
<br>
?- aaa(bbb) = aaa(B, C).<br>
false. % не удачно, арность функторов не совпадает, неизвестные B и С определены быть не могут<br>
<br>
?- aaa(bbb, C) = aaa(B, ccc(1)).<br>
C = ccc(1),<br>
B = bbb.<br>
% удачно + конкретизация<br>
<br>
?- [1,2] = [1,2,3,4].<br>
false. % списки не совпадают<br>
<br>
?- [1,2 | T] = [1,B,3,4].<br>
T = [3, 4],<br>
B = 2.<br>
% удачно + конкретизация<br>

Разобравшись немного с понятием унификации, становится понятно, почему

?- A = 2, A = 5.<br>
false.<br>


Выполнив первую унификацию, пролог система сопоставляет неизвестную A c числом 2. Таким образом вторая унификация будет ни что иное как 2 = 5, т.е. сопоставление чисел 2 и 5 которое конечно же окончится неудачей в виду того что числа не равны. Таким образом, в прологе переменные могут быть конкретизированы только один раз (по этому, например, попытки императивного программирования вида N = N + 1 в прологе не имеют смысла, подобное обычно делается через рекурсию).
Чтобы точно уяснить смысл последнего запроса, нужно еще пояснить смысл функтора ",". Да, не удивляйтесь, "," это действительно функтор (а именно, инфиксный оператор с арностью 2). В этом можно убедиться, выполнив запросы

?- call((,),A=2,A=5).<br>
false.<br>


а вот

?- call((,),A=2,A=B).<br>
A = 2,<br>
B = 2<br>

что эквивалентно

?- A = 2, A = B.<br>
A = 2,<br>
B = 2.<br>

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

Однако, мы отвлеклись. Оператор "," обозначает ни что иное, как логическое «И». Понятно что если мы говорим системе что некоторое число равно 2 и (при этом) оно же равно 5 то мы, очевидно, врем, о чем система нам и сообщает. Для логического «ИЛИ» предусмотрен оператор ";".

?- A = 2; A = 5.<br>
A = 2 ;<br>
A = 5.<br>

Собственно, ответ системы не представляет ничего удивительного. Она ответила ровно то, что мы ей сообщили, а именно, что неизвестное число это либо 2 либо 5.

Впрочем если мы конкретизируем наш запрос (неизвестное число это либо 2 либо 5 и при этом оно четное), то и ответ системы обретет однозначность

?- (A = 2; A = 5), A mod 2 =:= 0.<br>
A = 2 ;<br>
false.<br>

Наблюдательные могут спросить, что же тогда есть false в конце — неужели унификация не удалась? Тут мы подошли ко второй особенности языка пролог, не свойственной больше почти никакому другому языку программирования (кроме Mercury =) ), а именно backtracking или если сказать по-русски — перебор с возвратом. Конкретно для последнего примера система рассуждает следующим образом — допустим A=2, проведем проверку на A mod 2 =:= 0 — это выполняется -> сопоставление удачно — выполняется конкретизация (A=2), далее происходит откат (возврат) к первой части утверждения и проверяется гипотеза A = 5, она терпит крах и потому система показывает false.
Забегая на перед, замечу, что можно отменить возврат (после первого удачного сопоставления) с помощью оператора отсечения "!"

?- (A = 2; A = 5), A mod 2 =:= 0, !.<br>
A = 2.<br>
% ответ системы однозначен<br>

Попробуем выполнить арифметическое вычисление.
?- A = 2 + 3 * 5.<br>
A = 2+3*5.<br>

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

?- A + B * C = (+(A, *(B, C))).<br>
true.<br>

показывает что так и есть. Что же тогда делать? Однако, оказывается, есть специальный предикат is/2 (через "/" обычно обозначается арность предиката), который выполняет арифметическое действие.

?- A = 2 + 3 * 5, B is A.<br>
A = 2+3*5,<br>
B = 17.<br>

или просто

?- B is 2 + 3 * 5.<br>
B = 17.<br>

Пока что мы работали в интерактивном режиме, чтобы «пощупать» пролог на вкус. Обычно же, пролог-программы, как и программы на любом другом языке представляют собой файл с текстом программы. Обычной практикой является загрузка этого файла в интерактивную среду с помощью команды consult('file'). (или ее синтаксическим сахаром — [file].) и последующими запросами к программе, т.е. к фактам и предикатам в ней определенным.
Пролог машина, используя описанные выше 2 основных механизма (унификация с конкретизацией + backtracking) вычисляет необходимый результат.

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

% собаки<br>
dog(sharik). % дословно означает, что Шарик - собака<br>
dog(tuzik). % --//--<br>
<br>
% кошки<br>
cat(pushok).<br>
cat(druzgok).<br>
<br>
% хомячки<br>
hamster(pit).<br>
<br>
% мужчины<br>
man(bill).<br>
man(george).<br>
man(barak).<br>
man(platon).<br>
man(sokrat).<br>
<br>
% женщины<br>
woman(ann).<br>
woman(kate).<br>
woman(pam).<br>
<br>
% ныне покойные<br>
dead(sharik).<br>
dead(platon).<br>
dead(sokrat).<br>
<br>
% возраст<br>
age(sharik, 18). % возраст Шарика - 18 лет<br>
age(tuzik, 10). % --//--<br>
age(pushok, 5).<br>
age(druzhok, 2).<br>
age(bill, 62).<br>
age(george, 62).<br>
age(barak, 47).<br>
age(sokrat, 70).<br>
age(platon, 80).<br>
age(ann, 20).<br>
age(kate, 25).<br>
age(pam, 30).<br>

Предикаты же, это отношения, которые сопровождаются некоторыми дополнительными условиями (что-то вроде: «отношение справедливо, если выполнены след. условия ...»). Эти самые условия записываются через оператор ":-". Напишем несколько предикатов для нашей базы фактов.
% животные<br>
animal(X) :-<br>
dog(X); % это либо собака<br>
cat(X); % либо кошка<br>
hamster(X). % либо хомячок<br>
<br>
% Читается как: X - животное, если X - собака, либо Х - кошка, либо Х - хомяк.<br>
<br>
% люди<br>
human(X) :-<br>
man(X); % либо мужчина<br>
woman(X). % либо женщина<br>
<br>
% живые (или жившие) существа<br>
living(X) :-<br>
animal(X);<br>
human(X).<br>
<br>
% живые (в данный момент) существа<br>
alive(X) :-<br>
living(X),<br>
\+ dead(X).<br>
<br>
% старый<br>
old(X) :-<br>
( animal(X)<br>
-> age(X, Age),<br>
Age >= 10 % считаем, что животные старше 10 лет - старые<br>
; human(X),<br>
age(X, Age),<br>
Age >= 60 % считаем, что люди старше 60 лет - старые<br>
), <br>
\+ dead(X). % старые, но при этом - живые<br>
<br>
% молодой - значит - живой и не старый<br>
young(X) :-<br>
alive(X),<br>
\+ old(X).<br>


Полезно заметить, что факт — это фактически тоже разновидность предиката, более того вышеприведенные 3 факта woman(...) могут быть записаны одним предикатом

woman(X) :- X = ann; X = kate; X = pam.<br>


или даже

woman(X) :- member(X, [ann, kate, pam]).<br>


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

Запросы к системе, ознакомленной с приведенной программой:

1 ?- human(ann).<br>
true.<br>
<br>
?- human(tuzik).<br>
false.<br>
<br>
?- human(Who).<br>
Who = bill ;<br>
Who = george ;<br>
Who = barak ;<br>
Who = platon ;<br>
Who = sokrat ;<br>
Who = ann ;<br>
Who = kate ;<br>
Who = pam.<br>

Или так (получить сразу список):

?- bagof(H, human(H), Humans).<br>
Humans = [bill, george, barak, platon, sokrat, ann, kate, pam].<br>
<br>
?- alive(sokrat).<br>
false.<br>
<br>
?- alive(pit).<br>
true.<br>
<br>
% перечислить молодых<br>
?- young(Y).<br>
Y = pushok ;<br>
Y = druzgok ;<br>
Y = pit ;<br>
Y = barak ;<br>
Y = ann ;<br>
Y = kate ;<br>
Y = pam.<br>
<br>
% перечислить молодых мужчин<br>
?- young(H), man(H).<br>
H = barak ;<br>
false.<br>

И даже

% показать все пары живых существ, где одно старше другого в 2 раза<br>
?- living(X), living(Y), age(X, AgeX), age(Y, AgeY), AgeX =:= 2 * AgeY.<br>
X = tuzik,<br>
Y = pushok,<br>
AgeX = 10,<br>
AgeY = 5 ;<br>
X = ann,<br>
Y = tuzik,<br>
AgeX = 20,<br>
AgeY = 10 ;<br>
false.<br>


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

same(A, B) :-<br>
A = B.<br>

этот предикат допускает фактически 3 способа применения:

% вперед<br>
?- same(A, abc).<br>
A = abc.<br>
<br>
% назад<br>
?- same(abc, A).<br>
A = abc.<br>
<br>
% проверка на равенство<br>
?- same(abc, abc).<br>
true.<br>
<br>
?- same(abc, aaa).<br>
false.<br>


заметим еще, что этот предикат может быть записан в виде факта:

same(A, A).<br>


Более показательный в этом плане пример с предикатом append (сложение списков).
% сложение списков<br>
8 ?- append([a, b], [c, d, e], L).<br>
L = [a, b, c, d, e].<br>
<br>
% вычитание списков<br>
?- append(L1, [c, d, e], [a, b, c, d, e]).<br>
L1 = [a, b] ;<br>
false.<br>
<br>
?- append([a, b], L2, [a, b, c, d, e]).<br>
L2 = [c, d, e].<br>
<br>
% не возможно, поскольку массив [a, b, c, d, e] не начинается с [a, c]<br>
?- append([a, c], L2, [a, b, c, d, e]).<br>
false.<br>
<br>
% проверка на правильность сложения<br>
?- append("Привет ", "Мир", "Привет Мир").<br>
true.<br>
<br>
?- append("Привет ", "Мир", "Привет Habrahabr").<br>
false.<br>
<br>
% даже перебор всех возможных вариантов сложения, дающих данный список<br>
?- append(L1, L2, [a,b,c]).<br>
L1 = [],<br>
L2 = [a, b, c] ;<br>
L1 = [a],<br>
L2 = [b, c] ;<br>
L1 = [a, b],<br>
L2 = [c] ;<br>
L1 = [a, b, c],<br>
L2 = [] ;<br>
false.<br>
<br>
% и даже все возможные разбиения списка по некоторому элементу<br>
?- B = [c,c,c,separator,d,d,separator,e,e,e,e], append(L1, [separator | L2], B).<br>
B = [c, c, c, separator, d, d, separator, e, e|...],<br>
L1 = [c, c, c],<br>
L2 = [d, d, separator, e, e, e, e] ;<br>
B = [c, c, c, separator, d, d, separator, e, e|...],<br>
L1 = [c, c, c, separator, d, d],<br>
L2 = [e, e, e, e] ;<br>
false.<br>


И все это используя только один предикат!

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

Как-то гуляя по просторам сайта рефал-сообщества (еще один интересный язык программирования, местами идейно перекликающийся с прологом), наткнулся на сравнение Refal'а с Java'ой на примере решения конкретной задачи http://wiki.botik.ru/Refaldevel/ForJavaProgrammer (собственно первоисточник — тут http://nuclight.livejournal.com/111696.html ). Для интереса написал решение на прологе (написание заняло ~10 мин).


ischar(H, [H]).<br>
<br>
% пустые строка соответстует пустому паттерну.<br>
matches([], []) :-!.<br>
<br>
% если равны первый знак патерна и строки, или первый знак паттерна "?"<br>
% то для соответствия должны соответствовать "хвосты" строки и паттерна<br>
matches([H | T], [H1 | T1]) :-<br>
( <br>
H = H1;<br>
ischar(H, "?")<br>
),<br>
matches(T, T1), !.<br>
<br>
matches([H | T], T1) :-<br>
ischar(H, "*"), % иначе, если первая буква паттерна * то<br>
append(_, T2, T1), % некая подстрока T2 хвоста строки T1 <br>
matches(T, T2), !. % должна соответствовать хвосту паттерна<br>


и проверка (остальные тест-кейсы опустил из-за того, что очень длинные строки распирают страницу сайта)

check:-<br>
matches("ASDFAASDASDAAASDASDASD", "ASDFAASDASDAAASDASDASD"),<br>
matches("*", "ASDFAASDASDAAASDASDASD"),<br>
matches("A?DF?A*ASD*ASDA?DASD", "ASDFAASDASDAAASDASDASD"),<br>
\+ matches("ASDFAASDADAAASDASDASD", "ASDFAASASDAAASDASDASD").<br>


Запускаем проверку:

?- check.<br>
true. % алгоритм работает верно на тестовых данных<br>

Полный текст программ доступен здесь.

И последнее, рекомендации и подсказки.

1) Все примеры приведены для диалеката SWI-Prolog (по моему скромному мнению — самый вменяемый и близкий к классическому прологу). Правда, рекомендую использовать версию 5.7.3 (бета) доступную здесь http://prolog.cs.vu.nl/download/devel/bin/ (файл w32pl573.exe для win) или 5.6.X. В версии 5.7.4 присутствует небольшая ошибка при работе в пролог-консоли (https://mailbox.iai.uni-bonn.de/mailman/public/swi-prolog/2009/000904.html).
2) Загрузка файла:
?- [file].<br>

нескольких файлов:
?- [file1, file2, file3].<br>

3) Хелп по предикату:
?- help(is).<br>

или
?- apropos(test).<br>

4) редактирование текущего загруженного файла (удобный редактор с подсветкой, к слову, написанный на прологе).
?- edit.<br>

редактировать другой файл
?- edit(file).<br>

5) Пошаговая отладка (консольная):
?- trace, do_smth_with(arg).<br>

графическая:
?- gtrace, do_smth_with(arg).<br>


На сегодня все. Спасибо, что дочитали =).
Tags:prologintrorefalprogramminglogiclogic programmingdeclarative
Hubs: Prolog
+50
88.4k 118
Comments 41