prolog - "almost pure"Prolog 有表达力吗？

Question

@ false评论 earlier :

Yes, you can implement a Turing machine without dif/2. But you cannot even implement intersection or similar predicates.

假设我们用 call/N、dif/2 和 (=)/3，将在 if_/3 中使用，它的表达力是否仍然存在差距，即定义起来微不足道的事情在，比方说，Horn , 但在这种扩展的(几乎是纯的)Prolog 中更难表述？

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

---

编辑:假设方案没有突变、宏、延续、惰性、流、数字、字符串、向量或字符。只是符号、 bool 值和列表(树)。

Answer 1

Just symbols and lists (trees).

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

所以，我的主张是:不，这个模糊的 Scheme 子集和您定义的纯 Prolog 之间在表达能力上没有差距。我的论点(不是证明)是有建设性的，通过翻译来自 this answer 的列表交集的 Scheme 代码序言。

具体来说，这个:

(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，只需使用来自 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.