1

@false之前评论过：

是的，您可以在没有dif/2. 但是你甚至不能实现交集或类似的谓词。

假设我们用 , , 和 扩展纯 Prolog ( Horn FOL + CWA + UNA ) ,用于, 它的表达能力是否仍然存在差距,即在Scheme中定义微不足道的东西, 但要困难得多在这样扩展的（几乎是纯粹的）Prolog 中陈述？call/Ndif/2(=)/3if_/3

特别是，这样的 Prolog 是否允许像 Scheme 允许操作 Scheme 列表一样方便地操作 Prolog 列表？

编辑： 假设方案没有突变、宏、延续、惰性、流、数字、字符串、向量或字符。只是符号、布尔值和列表（树）。

4

3 回答 3

4

只是符号和列表（树）。

您还需要 Scheme 布尔值#t，#f如果您不想在纯 lambda 演算中编码所有内容。您还排除了函数值，谢天谢地，这使这个答案更简单。尽管您必须允许顶级(define name (lambda ...))表单的特殊情况。（其他任何东西，包括扩展let表达式，都可以去功能化。）

所以，我的主张是：不，这个模糊的 Scheme 子集和你定义的纯 Prolog 在表达能力上没有差距。我的论点（这不是证明）是建设性的，通过将列表交集的方案代码从这个答案翻译到 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 真值而不是trueor false。随意将其按摩成“标准”形式。编辑：有几种“足够好”的方法来定义(=)/3在这个答案的上下文中起作用的 a，但为了避免进一步的自行车脱落，只需使用来自https://stackoverflow.com/a/27358600/4391743的定义。

测试：

?- 'member?'(a, [x, y, a, c], Result).
Result = '#t' ;
false.

?- intersect([a, b, c, d], [c, d, e, f], Result).
Result = [c, d] ;
false.
于 2020-12-27T17:49:00.843 回答
2

只是symbol/1并且dif/2是逻辑纯 Prolog 的充分扩展。

证明：

这个答案包含一个 Scheme 表达式的求值器，evil/2。它理解lambdaand quote，并且可以很容易地扩展来处理内置的列表过程，如list, car,cdr等。除了纯（喇叭）Prolog，它只使用symbol/1and dif/2。虽然它是一个解释器并且运行缓慢，但它的存在表明 Scheme 所做的相同列表操作可以在这种几乎纯 Prolog 中完成。（我认为symbol/1也不需要，如果将 Scheme 符号转换为symb(prolog_atom)而不是直接转换为prolog_symbol）

编辑

这扩展evil/2到句柄if,#t和#f（由trueand表示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).
于 2020-12-31T08:14:50.887 回答
1

如果您采用纯方案。可能纯 Prolog 就足够了。Pure Scheme 将是具有某种严格的按值调用评估策略的 lambda 表达式。所以我们可以在 Prolog 中实现纯 Scheme，利用deBruijn 索引：

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).

如果你稍微改变一下表示，我想你可以摆脱削减。也许通过皮亚诺公理做必要的算术。嗯，你在纯 Prolog 中得到了纯 Scheme。

这是一个示例查询，SUCC 和 ZERO 来自这里：

?- 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)
于 2020-12-23T15:35:00.663 回答