Вот решение, в котором используется небольшой стиль программирования с блокировкой. Он не использует when / 2, а только замораживает / 2. Есть один предикат expr / 2, который проверяет, является ли что-то правильным выражением без какого-либо замыкания в нем:
expr(X) :- freeze(X, expr2(X)).
expr2([X|Y]) :-
expr(X),
expr(Y).
expr2(quote).
expr2([]).
expr2(cons).
expr2(lambda).
expr2(symbol(_)).
Затем снова используется предикат поиска с использованием freeze / 2,
для ожидания списка окружения.
lookup(S, E, R) :- freeze(E, lookup2(S, E, R)).
lookup2(S, [S-T|_], R) :-
unify_with_occurs_check(T, R).
lookup2(S, [T-_|E], R) :-
dif(S, T),
lookup(S, E, R).
И, наконец, оценщик, который закодирован с использованием DCG,
для ограничения общего количества минусов и применения вызовов:
eval([quote,X], _, X) --> [].
eval([], _, []) --> [].
eval([cons,X,Y], E, [A|B]) -->
step,
eval(X, E, A),
eval(Y, E, B).
eval([lambda,symbol(X),B], E, closure(X,B,E)) --> [].
eval([X,Y], E, R) -->
step,
eval(X, E, closure(Z,B,F)),
eval(Y, E, A),
eval(B, [Z-A|F], R).
eval(symbol(S), E, R) -->
{lookup(S, E, R)}.
step, [C] --> [D], {D > 0, C is D-1}.
Главный предикат постепенно увеличивает количество разрешенных
минусов и применяет вызовы:
quine(Q, M, N) :-
expr(Q),
between(0, M, N),
eval(Q, [], P, [N], _),
unify_with_occurs_check(Q, P).
Этот запрос показывает, что 5 минусов и вызовов применения достаточно для создания Quine. Работает в SICStus Prolog и Jekejeke Prolog. Для SWI-Prolog необходимо использовать, например, этот обходной путь unify / 2:
?- dif(Q, []), quine(Q, 6, N).
Q = [[lambda, symbol(_Q), [cons, symbol(_Q), [cons, [cons,
[quote, quote], [cons, symbol(_Q), [quote, []]]], [quote,
[]]]]], [quote, [lambda, symbol(_Q), [cons, symbol(_Q), [cons,
[cons, [quote, quote], [cons, symbol(_Q), [quote, []]]],
[quote, []]]]]]],
N = 5
Мы можем вручную убедиться, что это действительно нетривиальный Куайн:
?- Q = [[lambda, symbol(_Q), [cons, symbol(_Q), [cons, [cons,
[quote, quote], [cons, symbol(_Q), [quote, []]]], [quote,
[]]]]], [quote, [lambda, symbol(_Q), [cons, symbol(_Q), [cons,
[cons, [quote, quote], [cons, symbol(_Q), [quote, []]]],
[quote, []]]]]]], eval(Q, [], P, [5], _).
Q = [[lambda, symbol(_Q), [cons, symbol(_Q), [cons, [cons,
[quote, quote], [cons, symbol(_Q), [quote, []]]], [quote,
[]]]]], [quote, [lambda, symbol(_Q), [cons, symbol(_Q), [cons,
[cons, [quote, quote], [cons, symbol(_Q), [quote, []]]],
[quote, []]]]]]],
P = [[lambda, symbol(_Q), [cons, symbol(_Q), [cons, [cons,
[quote, quote], [cons, symbol(_Q), [quote, []]]], [quote,
[]]]]], [quote, [lambda, symbol(_Q), [cons, symbol(_Q), [cons,
[cons, [quote, quote], [cons, symbol(_Q), [quote, []]]],
[quote, []]]]]]]
person
Mostowski Collapse
schedule
30.12.2020
