Prolog in Prolog: зачем и как
Язык Prolog создавался для задач искусственного интеллекта, который сейчас обычно называют "классическим", чтобы не путать с машинным обучением путем подбора большого количества числовых параметров. Важным классом таких задач является моделирование "мира", в котором можно совершать какие-либо действия. Игрушечным примером такого мира является Nani Search. И решают их часто в таком стиле: состояние мира помещается в прологовскую базу данных и все изменения производятся путем удаления и добавления фактов в это хранилище. Но это получается уже не логическое программирование, а самое настоящее императивное! При этом используются худшие практики программирования - глобальное состояние! Мимо этого я пройти не могу!
Но самое плохое в таком подходе не стиль, в конце концов большая часть современного кода императивна, и даже частенько использует, явно или неявно, глобальные переменные. Важно что состояние мира перестает быть first-order value и пропадает возможность решать задачи в моделируемом мире, для чего и создавался язык Prolog.
Такие решения сравнительно удобно программируются на Prolog, и естественное желание это удобство сохранить. Напрашивается написать интерпретатор Prolog, такой, что его состояние хранится в переменной, чем мы сейчас и займемся.
Prolog - язык, претендующий на гомоиконичность, и мы этим воспользуется. Синтаксически предикаты пролога совпадают с термами, а база данных является по сути списком термов, в которой при выполнении программы ищутся термы, соответствующие проверяемым предикатам.
К сожалению, прологовская база данных устроена не слишком логично. Простому предикату p(x) может соответствовать просто запись p(x), а может и вычислимое правило p(X) :- X = Y, Y = x.. Такое правило также представлено термом: ':-'(p(X), ','('='(X,Y), '='(Y,x))), То есть терм ':-' является особенным - все термы равноправны, но некоторые равноправнее. Я решил не копировать эту особенноcть, и хранить все определения в виде списка, голова которого будет определяемый предикат, а хвост - список предикатов, обединяемых через AND. Приведенные выше определения p будут записаны как [p(x)] и [p(X), '='(X, Y), '='(Y,x)]. В родном прологовском ':-' тело предиката может хранится в виде одного терма-предиката или тупла (',') термов-предикатов. Но в Prolog нет пустого тупла и туплов из одного элемента. Поэтому я отказался от использования туплов во внутреннем представлении в пользу более универсальных списков.
Важной концепцией пролога являются неопределенные переменные. В частности, связывание этих переменных со значениями или другими переменными используется для протаскивания агрументов предиката в его тело. Заманчиво было бы использовать такие переменные в представлении программы и в базе данных интерпретатора, но это приведет к неожиданным последствиям. Допустим, в базе данных есть определения f(X) :- g(X). g(a). g(b)., и проверяется пара предикатов f(a), f(b).. В Prolog эта проверка пройдет, но что будет с интерпретатором, использующим наивное внутреннее представление? При проверке f(a) переменная X будет связана с атомом 'a', проверка g(a) пройдет успешно, но в базе данных запись об f превратится в f(a) :- g(a). и пропытка проверить f(b) провалится. По этому в нашей базе данных придется хранить шаблоны определений, в которые подставлять при проверке новые неопределенные переменные. Имена переменных можно задавать уникальными в пределах определения атомами, список которых будет храниться рядом с определением.
mkfree([], []).
mkfree([V|T], [(V,_)|TF]) :- mkfree(T, TF).
subst(F, V, O) :- atom(V) ->
( member((V, R), F) -> O=R ; O=V ) ;
( V =.. [P | A], maplist(subst(F), A, N), O =.. [P | N] ) .
setfree((N, V), O) :-
mkfree(N, F),
maplist(subst(F), V, O).Предикат mkfree первым параметром получает список "имен" новых переменных, а во втором возвращает список пар - имя, новая переменная.
subst подставляет в терм вместо атомов-имен что-то другое, в данном случае новосозданные переменные. В нем используется предикат '=..' который превращает терм в список (и обратно, как и положено "хорошим" прологовским предикатам). Например a(x,y) =.. [a, x, y]. Интересен предикат "высшего порядка" maplist, получающий первым параметром терм, конвертируемый в вызов предиката добавлением двух параметров. Пока такие предикаты в этом интерпретаторе не поддержаны. Возможно, с целью самоприменимости я избавлюсь от него в следующих версиях.
setfree собственно объединяет mkfree и subst, применяя последний к представлению определения в виде списка (возможность использовать готовый maplist - еще один аргумент в пользу использования списка, а не тупла).
Сам интепретатор разобьем на два предиката: check - для проверки/выполнения списка предикатов, связанных общими переменными, и doio, реализующий встроенные предикаты, в том числе ввод/вывод. Предикаты также получают два дополнительных параметра - исходное и конечное состояние базы данных.
doio(DB, writeln(X), DB) :- writeln(X).
check([], DB, DB).
check([P|R], DB, DBO) :-
(doio(DB, P, DBN) ->
true ;
(member(D, DB),
setfree(D, [P | B]),
check(B, DB, DBN))),
check(R, DBN, DBO).
check пытается выполнить сначала встроеный предикат, а если это не получилось, то ищет его в базе данных. Это можно было бы реализовать с использованием "отсечения", но я не люблю этот прием (как слишком императивный) и реализовать его в интерпретаторе нетривиально (а я все еще думаю о самоприменимости). Вместо отсечения я использую конструкцию P -> T ; E, которая реализуется сравнительно просто.
doio(DB, (P -> T ; F), NDB) :-
check(P, DB, TDB) -> check(T, TDB, NDB) ; check(F, DB, NDB).
Здесь стоит обратить внимание, что в этой конструкции в Prolog каждый предикат может быть туплом предикатов. Так как я отказался от туплов в пользу списков, у меня даже единственный предикат должен быть завернут в список.
?- check([[a(x)] -> [writeln(a)] ; [writeln(b)]], [([], [a(x)])], _).
a
true.
Для работы игровых миров требуются предикаты, модифицирующие базу данных. Элементарный вариант предиката asserta почти тривиален.
doio(DB, asserta(P), [([],[P])|DB]).Он позволяет добавлять в базу только простые факты. В приведенных выше примерах моделируемых миров этого достаточно. Если требуется полноценная реализация, придется повозиться.
atoms(T, A) :-
atom(T) -> A=[T] ;
var(T) -> A=[] ;
T =.. [_ | L], maplist(atoms, L, LL), append(LL, A).
nextatom(D, A, N) :-
name(A, M),
append(M, [97], NM),
name(NP, NM),
(member(NP, D) -> nextatom(D, NP, N) ;
N = NP).
fillfree(D, V, (A, L), (AN, LN)) :-
(var(V) -> (nextatom(D, A, AN), V = A, LN = [A | L]) ;
atom(V) -> AN=A, LN=L ;
V =.. [_ | F],
foldl(fillfree(D), F, (A, L), (AN, LN))).
fillfree(V, VO, L) :-
atoms(V, A),
nextatom(A, w, I),
findall((V, L1), fillfree(A, V, (I,[]), (_,L1)), [(VO, L)]).
compile(P, I) :-
(P = (H, T)) -> compile(H, I1), compile(T, I2), append(I1, I2, I) ;
(P = (C -> T ; E)) -> compile(C, IC), compile(T, IT), compile(E, IE), I = [IC -> IT ; IE];
I = [P].
compileDef(P, I) :-
(P = (D :- C)) -> compile(C, IC), I = [D | IC];
I = [P].
doio(DB, asserta(P), [(V,DO)|DB]) :- def2list(P, D), fillfree(D, DO, V).Здесь нетривиальны предикаты fillfree/4 и fillfree/3.
fillfree/4 ищет несвязанные переменные (для них выполняется предикат var) и связывет их с уникальными атомами. Если в иходном терме переменная встречается более одного раза, то она будет установлена только первый раз, а при последующих проверках var сочтет ее связянной. На выходе будет получен исходный терм, в котором все переменные связяны с атомами-именами, и список этих имен, для последующей передачи в setfree. Но остается небольшая проблема - если переменная в терме используется еще где-то в интерпретируемой программе, она там тоже будет связяна с сгенерированным атомом. Что бы их развязать fillfree/3 вызывает fillfree/4 из findall, который агреггирует все возможные решения fillfree/4 забывая при этом произошедшие связывания.
Использование findall - еще одино препятствие к самоприметимости интерпретатора. Вызов findall можно было бы заменить на вызов setfree, который заменит атомы на новосозданные переменные и еще один вызов fillfree/4, который создаст терм не зависящий от внешних переменных.
Для реализации retract тоже приходится повозиться с несвязанными переменными.
deleteall(_, [], []).
deleteall(P, [E | L], O) :-
(P = E -> fail ;
deleteall(P, L, O1), O = [E | O1]) ->
true ;
deleteall(P, L, O).
doio(DB, retract(P), DBO) :- def2list(P, D), deleteall((_,D), DB, DBO).Здесь используются две вложенные конструкции P -> T ; E. Внутренняя проверяет что запись в базе данных соотвествует шаблону и фейлится, чтобы забыть результаты унификации, внешняя обрабатывает эту ситуацию и удаляет найденый предикат.
У этих реализаций assert и retract появляется интересное отличие от стандартной реализации - "транзакционность". Если какой-либо предикат модифицирует базу данных, а потом фейлится, то в обычном Prolog изменения сохраняются, а в этом интерпретаторе - откатываются. Хотя это и может оказаться удобным в задачах моделирования миров, теряется возможность отладки таких моделей в стандартной реализации Prolog с последующим переносом в интерпретатор.
Nani search - сравнительно сложный мир. Попробуем смоделировать мир попроще, с козлом/carba, волком/lobo и капустой/repollo, которых надо переправить на лодке/barco через реку. (Для большей абстрактости названия взяты из испанского).
:- dynamic(barco/1).
:- dynamic(esta/2).
barco(izquierda).
esta(carba, izquierda).
esta(lobo, izquierda).
esta(repollo, izquierda).
costados(izquierda, derecha).
costados(derecha, izquierda).
comer(lobo, repollo).
comer(repollo, lobo).
movimiento(X) :-
barco(L),
esta(X, L),
costados(L, N),
retract(esta(X, L)),
asserta(esta(X, N)),
retract(barco(L)),
asserta(barco(N)).
paso(carba) :-
movimiento(carba).
paso(X) :-
comer(X, Y),
esta(carba, L),
costados(L, O),
esta(Y, O),
movimiento(X).
paso(none) :-
esta(carba, L),
costados(L, O),
esta(lobo, O),
esta(repollo, O),
barco(X),
costados(X, N),
retract(barco(X)),
asserta(barco(N)).Перемещения делаются командами paso(X), где X это carba, lobo, repollo или none.
Перепишим этот код один к одному в представление интепрететора и попытаемся решить задачу автоматически.
solve(X, R) :-
X = [paso(_), paso(_), paso(_), paso(_), paso(_), paso(_), paso(_), esta(repollo, derecha), esta(lobo, derecha), esta(carba, derecha)],
PROG = [([], [barco(izquierda)]),
([], [esta(carba, izquierda)]), ([], [esta(lobo, izquierda)]), ([], [esta(repollo, izquierda)]),
([], [costados(izquierda, derecha)]), ([], [costados(derecha, izquierda)]),
([], [comer(lobo, repollo)]), ([], [comer(repollo, lobo)]),
([x, l, n], [movimiento(x),
barco(l),
esta(x, l),
costados(l, n),
retract(esta(x, l)),
retract(barco(l)),
asserta(esta(x, n)),
asserta(barco(n))]),
([], [paso(carba), movimiento(carba)]),
([a, b, l, o], [paso(a),
comer(a, b),
esta(carba, l),
costados(l, o),
esta(b, o),
movimiento(a)]),
([l, o, x, n], [paso(none),
esta(carba, l),
costados(l, o),
esta(lobo, o),
esta(repollo, o),
barco(x),
costados(x, n),
retract(barco(x)),
asserta(barco(n))])],
check(X, PROG, R).Prolog реализует алгоритм поиска "вглубь", который может зациклиться на бесконечных структурах. Поэтому мы делаем небольшую подсказку, что ищется решение ровно из семи шагов. В моих планах переделать интерпретатор на поиск "вширь", но это не слишком просто.
?- solve(P, D).
P = [paso(carba), paso(none), paso(lobo), paso(carba), paso(repollo), paso(none), paso(carba), esta(repollo, derecha), esta(..., ...)|...],
D = [([], [barco(derecha)]), ([], [esta(carba, derecha)]), ([], [esta(repollo, derecha)]), ([], [esta(lobo, derecha)]), ([], [costados(izquierda, derecha)]), ([], [costados(derecha, izquierda)]), ([], [comer(..., ...)]), ([], [...]), (..., ...)|...] ;
P = [paso(carba), paso(none), paso(repollo), paso(carba), paso(lobo), paso(none), paso(carba), esta(repollo, derecha), esta(..., ...)|...],
D = [([], [barco(derecha)]), ([], [esta(carba, derecha)]), ([], [esta(lobo, derecha)]), ([], [esta(repollo, derecha)]), ([], [costados(izquierda, derecha)]), ([], [costados(derecha, izquierda)]), ([], [comer(..., ...)]), ([], [...]), (..., ...)|...] ;
false.
Как видно, нашлось два решения, подходящие под это условие.
Если воспользоваться "транзакционностью" нашей базы данных, то код упрощается - теперь не нужно проверять громоздкие предусловия возможности хода, а можно сделать ход и проверить сравнительно простое постусловие.
solve(X, R) :-
X = [paso(_), paso(_), paso(_), paso(_), paso(_), paso(_), paso(_), esta(repollo, derecha), esta(lobo, derecha), esta(carba, derecha)],
PROG = [([], [barco(izquierda)]),
([], [esta(carba, izquierda)]), ([], [esta(lobo, izquierda)]), ([], [esta(repollo, izquierda)]),
([], [costados(izquierda, derecha)]), ([], [costados(derecha, izquierda)]),
([x, l], [seguro(x), esta(carba, l), esta(x, l), barco(l)]),
([x, l, o], [seguro(x), esta(carba, l), esta(x, o), costados(l, o)]),
([], [seguro, seguro(lobo), seguro(repollo)]),
([x, l, n], [paso(x),
barco(l),
esta(x, l),
costados(l, n),
retract(esta(x, l)),
retract(barco(l)),
asserta(esta(x, n)),
asserta(barco(n)),
seguro]),
([l, n], [paso(none),
barco(l),
costados(l, n),
retract(barco(l)),
asserta(barco(n)),
seguro])],
check(X, PROG, R).Где все это можно примерить? Один из вариантов - прототипирование новых прологоподобных языков. С помощью этого можно моделировать модальности (если не хочется осваивать что-нибудь сложное и экзотическое, типа Modal Prolog). Свой интерпретатор также понадибится при реализации методов генерации программ с помощью машинного обучения, таких как Индуктивное логическое программирование (спасибо @robofreakза статью в Википедии).
В заключение выражаю благодорность @usr345за подброшенный мне Nani Search.
Полные исходники можно взять на github - там можно посмотреть код в боевой расскраске, которую для Prolog здешний редактор не поддерживает.
Картинка для привлечения внимания была взята из мира Nani Search и адаптирована под мир капусты, козла и волка.