"almost pure" Prolog 有表达力吗？
Is "almost pure" Prolog expressive?
@false commented :
Yes, you can implement a Turing machine without dif/2. But you cannot even implement intersection or similar predicates.
假设我们确实扩展了纯 Prolog（Horn FOL + CWA + UNA) with call/N, dif/2, and (=)/3, to be used in if_/3, would there still be gaps in its expressiveness, i.e. things that are trivial to define in, say, Scheme，但是在这种扩展的（几乎是纯的）Prolog 中更难说明？
特别是，这样的 Prolog 是否允许像 Scheme 允许操作 Scheme 列表一样方便地操作 Prolog 列表？
编辑： 假设方案没有突变、宏、延续、惰性、流、数字、字符串、向量或字符。只是符号、布尔值和列表（树）。
如果你走的是纯Scheme。可能纯 Prolog 就足够了。 Pure Scheme 是具有某种严格的按值调用评估策略的 lambda 表达式。所以我们可以在 Prolog 中实现如下纯 Scheme，利用 deBruijn indexes:
eval(P*Q, H) :- !,
eval(P, R),
eval(Q, S),
reduce(R, S, H).
eval(X, X).
reduce(b(R), S, J) :- !,
subst(R, 0, S, H),
eval(H, J).
reduce(R, S, R*S).
如果你稍微改变一下表示，我想你可以摆脱削减。也许通过 Peano 公理进行必要的算术运算。嗯瞧，你在纯 Prolog 中得到了纯 Scheme。
这是一个示例查询，SUCC 和 ZERO 来自 here:
?- ZERO = b(b(0)), SUCC = b(b(b(1*(2*1*0)))),
eval(SUCC*(SUCC*ZERO)*f*a, X).
ZERO = b(b(0)),
SUCC = b(b(b(1*(2*1*0)))),
X = f*(f*a)
Just symbols and lists (trees).
如果您不想在纯 lambda 演算中对所有内容进行编码，您还需要 Scheme 布尔值 #t 和 #f。您还排除了函数值，谢天谢地，这使这个答案更简单。尽管您必须允许顶级 (define name (lambda ...)) 表单的特殊情况。 （任何其他内容，包括展开的 let 表达式，都可以是 defunctionalized。）
所以，我的主张是：没有，这个模糊的Scheme子集和你定义的纯Prolog在表达能力上没有差距。我的论点（不是证明）是有建设性的，通过将列表交集的 Scheme 代码从 this answer 翻译成 Prolog.
具体来说，这个：
(define intersect
(lambda (set1 set2)
(cond
((null? set1)(quote ()))
((member? (car set1) set2)
(cons (car set1)
(intersect (cdr set1) set2)))
(else (intersect (cdr set1) set2)))))
变成：
intersect(Set1, Set2, Result) :-
cond([
['null?'(Set1), result([])],
[cond_1(Set1, Set2), body_1(Set1, Set2)],
[else, body_2(Set1, Set2)]], Result).
cond_1(Set1, Set2, Result) :-
car(Set1, Car),
'member?'(Car, Set2, Result).
body_1(Set1, Set2, Result) :-
car(Set1, Car),
cdr(Set1, Cdr),
intersect(Cdr, Set2, PartialIntersection),
cons(Car, PartialIntersection, Result).
body_2(Set1, Set2, Result) :-
cdr(Set1, Cdr),
intersect(Cdr, Set2, Result).
还有这个：
(define member?
(lambda (a lat)
(cond
((null? lat) #f)
(else (or (equal? (car lat) a)
(member? a (cdr lat)))))))
变成：
'member?'(A, Lat, Result) :-
cond([
['null?'(Lat), result('#f')],
[else, or([or_case_1(Lat, A),
or_case_2(Lat, A)])]], Result).
or_case_1(Lat, A, Result) :-
car(Lat, Car),
'equal?'(Car, A, Result).
or_case_2(Lat, A, Result) :-
cdr(Lat, Cdr),
'member?'(A, Cdr, Result).
请注意，嵌套的表达式需要取消嵌套，并且在除了最微不足道的情况之外的所有情况下，通过定义辅助 Prolog 谓词，这是最简单的。这不会非线性地增加代码大小。
这些定义使用标准 Scheme 结构的以下翻译：
'equal?'(X, Y, '#t') :-
=(X, Y, true).
'equal?'(X, Y, '#f') :-
=(X, Y, false).
'null?'(Value, Result) :-
'equal?'(Value, [], Result).
car([Car | _Cdr], Car).
cdr([_Car | Cdr], Cdr).
cons(Car, Cdr, [Car | Cdr]).
or([], '#f').
or([Goal | Goals], Result) :-
if(Goal,
Result = '#t',
or(Goals, Result)).
cond([], _Result) :-
throw(error(cond_without_else, _)).
cond([[Condition, Body] | OtherCases], Result) :-
if(Condition,
call(Body, Result),
cond(OtherCases, Result)).
一些支持从 cond 案例主体和 else 案例中获取简单值的内容：
result(Result, Result).
else('#t').
这就是您需要的所有内部不纯、外部纯的 Prolog 支持：
if(Goal, True, False) :-
call(Goal, Truth),
( Truth == '#t' -> call(True)
; Truth == '#f' -> call(False)
; throw(error(type_or_instantiation_error(Truth), _)) ).
我称其为 if/3 而不是 if_/3 因为它不完全是“标准” if_/3：它期望条件求值为 Scheme 真值而不是 true 或 false。随意将其按摩成“标准”形式。 编辑： 有几种“足够好”的方法来定义一个 (=)/3 将在这个答案的上下文中工作，但为了避免进一步的 bikeshedding，只需使用 (=)/3 中的定义=33=].
测试：
?- 'member?'(a, [x, y, a, c], Result).
Result = '#t' ;
false.
?- intersect([a, b, c, d], [c, d, e, f], Result).
Result = [c, d] ;
false.
只是 symbol/1 和 dif/2 是逻辑上纯 Prolog 的足够扩展。
证明：
This answer 包含 Scheme 表达式的计算器 evil/2。它理解 lambda 和 quote，并且可以轻松扩展以处理内置列表过程，如 list、car、cdr 等。除了 pure (Horn) Prolog，它仅使用 symbol/1 和 dif/2。虽然它是一个解释器并且会 运行 缓慢，但它的存在表明 Scheme 完成的相同列表操作可以在这种几乎纯 Prolog 中完成。 （我认为 symbol/1 也不需要，如果 Scheme 符号被翻译成 symb(prolog_atom) 而不是直接翻译成 prolog_symbol）
编辑
这扩展了 evil/2 以处理 if、#t 和 #f（由 true 和 false 表示）：
evil(true, _, true).
evil(false, _, false).
evil([if, E1, E2, E3], Env, Val) :-
evil(E1, Env, false),
symbols(E2),
evil(E3, Env, Val).
evil([if, E1, E2, E3], Env, Val) :-
evil(E1, Env, V),
dif(V, false),
symbols(E3),
evil(E2, Env, Val).
这扩展了 evil/2 以处理 equalp。它甚至比 Scheme 的 eq* 更强大，因为它也等同于一些闭包：
evil([equalp, E1, E2], Env, true) :-
evil(E1, Env, V),
evil(E2, Env, V).
evil([equalp, E1, E2], Env, false) :-
evil(E1, Env, V1),
evil(E2, Env, V2),
dif(V1, V2).
@false commented
Yes, you can implement a Turing machine without
dif/2. But you cannot even implement intersection or similar predicates.
假设我们确实扩展了纯 Prolog（Horn FOL + CWA + UNA) with call/N, dif/2, and (=)/3, to be used in if_/3, would there still be gaps in its expressiveness, i.e. things that are trivial to define in, say, Scheme，但是在这种扩展的（几乎是纯的）Prolog 中更难说明？
特别是，这样的 Prolog 是否允许像 Scheme 允许操作 Scheme 列表一样方便地操作 Prolog 列表？
编辑： 假设方案没有突变、宏、延续、惰性、流、数字、字符串、向量或字符。只是符号、布尔值和列表（树）。
如果你走的是纯Scheme。可能纯 Prolog 就足够了。 Pure Scheme 是具有某种严格的按值调用评估策略的 lambda 表达式。所以我们可以在 Prolog 中实现如下纯 Scheme，利用 deBruijn indexes:
eval(P*Q, H) :- !,
eval(P, R),
eval(Q, S),
reduce(R, S, H).
eval(X, X).
reduce(b(R), S, J) :- !,
subst(R, 0, S, H),
eval(H, J).
reduce(R, S, R*S).
如果你稍微改变一下表示，我想你可以摆脱削减。也许通过 Peano 公理进行必要的算术运算。嗯瞧，你在纯 Prolog 中得到了纯 Scheme。
这是一个示例查询，SUCC 和 ZERO 来自 here:
?- ZERO = b(b(0)), SUCC = b(b(b(1*(2*1*0)))),
eval(SUCC*(SUCC*ZERO)*f*a, X).
ZERO = b(b(0)),
SUCC = b(b(b(1*(2*1*0)))),
X = f*(f*a)
Just symbols and lists (trees).
如果您不想在纯 lambda 演算中对所有内容进行编码，您还需要 Scheme 布尔值 #t 和 #f。您还排除了函数值，谢天谢地，这使这个答案更简单。尽管您必须允许顶级 (define name (lambda ...)) 表单的特殊情况。 （任何其他内容，包括展开的 let 表达式，都可以是 defunctionalized。）
所以，我的主张是：没有，这个模糊的Scheme子集和你定义的纯Prolog在表达能力上没有差距。我的论点（不是证明）是有建设性的，通过将列表交集的 Scheme 代码从 this answer 翻译成 Prolog.
具体来说，这个：
(define intersect
(lambda (set1 set2)
(cond
((null? set1)(quote ()))
((member? (car set1) set2)
(cons (car set1)
(intersect (cdr set1) set2)))
(else (intersect (cdr set1) set2)))))
变成：
intersect(Set1, Set2, Result) :-
cond([
['null?'(Set1), result([])],
[cond_1(Set1, Set2), body_1(Set1, Set2)],
[else, body_2(Set1, Set2)]], Result).
cond_1(Set1, Set2, Result) :-
car(Set1, Car),
'member?'(Car, Set2, Result).
body_1(Set1, Set2, Result) :-
car(Set1, Car),
cdr(Set1, Cdr),
intersect(Cdr, Set2, PartialIntersection),
cons(Car, PartialIntersection, Result).
body_2(Set1, Set2, Result) :-
cdr(Set1, Cdr),
intersect(Cdr, Set2, Result).
还有这个：
(define member?
(lambda (a lat)
(cond
((null? lat) #f)
(else (or (equal? (car lat) a)
(member? a (cdr lat)))))))
变成：
'member?'(A, Lat, Result) :-
cond([
['null?'(Lat), result('#f')],
[else, or([or_case_1(Lat, A),
or_case_2(Lat, A)])]], Result).
or_case_1(Lat, A, Result) :-
car(Lat, Car),
'equal?'(Car, A, Result).
or_case_2(Lat, A, Result) :-
cdr(Lat, Cdr),
'member?'(A, Cdr, Result).
请注意，嵌套的表达式需要取消嵌套，并且在除了最微不足道的情况之外的所有情况下，通过定义辅助 Prolog 谓词，这是最简单的。这不会非线性地增加代码大小。
这些定义使用标准 Scheme 结构的以下翻译：
'equal?'(X, Y, '#t') :-
=(X, Y, true).
'equal?'(X, Y, '#f') :-
=(X, Y, false).
'null?'(Value, Result) :-
'equal?'(Value, [], Result).
car([Car | _Cdr], Car).
cdr([_Car | Cdr], Cdr).
cons(Car, Cdr, [Car | Cdr]).
or([], '#f').
or([Goal | Goals], Result) :-
if(Goal,
Result = '#t',
or(Goals, Result)).
cond([], _Result) :-
throw(error(cond_without_else, _)).
cond([[Condition, Body] | OtherCases], Result) :-
if(Condition,
call(Body, Result),
cond(OtherCases, Result)).
一些支持从 cond 案例主体和 else 案例中获取简单值的内容：
result(Result, Result).
else('#t').
这就是您需要的所有内部不纯、外部纯的 Prolog 支持：
if(Goal, True, False) :-
call(Goal, Truth),
( Truth == '#t' -> call(True)
; Truth == '#f' -> call(False)
; throw(error(type_or_instantiation_error(Truth), _)) ).
我称其为 if/3 而不是 if_/3 因为它不完全是“标准” if_/3：它期望条件求值为 Scheme 真值而不是 true 或 false。随意将其按摩成“标准”形式。 编辑： 有几种“足够好”的方法来定义一个 (=)/3 将在这个答案的上下文中工作，但为了避免进一步的 bikeshedding，只需使用 (=)/3 中的定义=33=].
测试：
?- 'member?'(a, [x, y, a, c], Result).
Result = '#t' ;
false.
?- intersect([a, b, c, d], [c, d, e, f], Result).
Result = [c, d] ;
false.
只是 symbol/1 和 dif/2 是逻辑上纯 Prolog 的足够扩展。
证明：
This answer 包含 Scheme 表达式的计算器 evil/2。它理解 lambda 和 quote，并且可以轻松扩展以处理内置列表过程，如 list、car、cdr 等。除了 pure (Horn) Prolog，它仅使用 symbol/1 和 dif/2。虽然它是一个解释器并且会 运行 缓慢，但它的存在表明 Scheme 完成的相同列表操作可以在这种几乎纯 Prolog 中完成。 （我认为 symbol/1 也不需要，如果 Scheme 符号被翻译成 symb(prolog_atom) 而不是直接翻译成 prolog_symbol）
编辑
这扩展了 evil/2 以处理 if、#t 和 #f（由 true 和 false 表示）：
evil(true, _, true).
evil(false, _, false).
evil([if, E1, E2, E3], Env, Val) :-
evil(E1, Env, false),
symbols(E2),
evil(E3, Env, Val).
evil([if, E1, E2, E3], Env, Val) :-
evil(E1, Env, V),
dif(V, false),
symbols(E3),
evil(E2, Env, Val).
这扩展了 evil/2 以处理 equalp。它甚至比 Scheme 的 eq* 更强大，因为它也等同于一些闭包：
evil([equalp, E1, E2], Env, true) :-
evil(E1, Env, V),
evil(E2, Env, V).
evil([equalp, E1, E2], Env, false) :-
evil(E1, Env, V1),
evil(E2, Env, V2),
dif(V1, V2).