代码之家 › 专栏 › 技术社区 › MWB

Prolog的“近乎纯粹”表现力强吗?

logical-purity prolog-dif prolog

0

MWB · 技术社区 · 4 年前

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

假设我们确实扩展了纯Prolog( Horn FOL + CWA + UNA )与 call/N , dif/2 ,以及 (=)/3 ,用于 if_/3 ,它的表现力还会有差距吗, 即那些微不足道的事情,比如说, Scheme ,但在这种扩展的(几乎是纯的)Prolog中更难陈述吗?

特别是,这样的Prolog是否允许像Scheme允许操纵Scheme列表那样方便地操纵Prolog列表?

编辑: 假设Scheme没有突变、宏、连续、懒惰、流、数字、字符串、向量或字符。只有符号、布尔值和列表(树)。

0 回复 | 直到 4 年前

1

4

Isabelle Newbie 4 年前

只是符号和列表(树)。

你还需要Scheme布尔值 #t 和 #f 如果你不想用纯lambda演算对所有内容进行编码。您还排除了函数值,谢天谢地,这使得这个答案更简单。虽然你必须允许顶级的特殊情况 (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 这将在这个答案的背景下起作用,但为了避免进一步的自行车避险,只需使用以下定义 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.

2

MWB 4 年前

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

证明:

This answer 包含用于Scheme表达式的计算器, evil/2 它理解 lambda 和 quote ,并且可以很容易地扩展到处理内置的列表过程,如 list , car , cdr 等等。除了 纯(喇叭)Prolog ,它只使用 符号/1 和 dif/2 虽然它是一个解释器,运行速度很慢,但它的存在表明,Scheme完成的相同列表操作也可以在这种几乎纯Prolog中完成。(我想 符号/1 如果Scheme符号被翻译成 symb(prolog_atom) 而不是直接进入 prolog_symbol )

编辑

这延伸了 邪恶/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).

这延伸了 邪恶/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).

3

1

Will Ness Derri Leahy 4 年前

如果你采取一个纯粹的计划。也许纯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).

如果你稍微改变一下表达方式,我想你可以去掉割伤。也许通过皮亚诺公理做必要的算术。瞧,你在纯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)