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