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 и адаптирована под мир капусты, козла и волка.