是“几乎纯的"序言表达? [英] Is "almost pure" Prolog expressive?

问题描述

@false 评论 之前:

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

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

假设我们确实扩展了纯 Prolog (Horn FOL + CWA + UNA) 和 call/N、dif/2 和(=)/3，在if_/3中使用，会不会还有差距?表现力，即在Scheme中定义的东西是微不足道的，但是在这种扩展的(几乎是纯的)Prolog 中很难表述吗?

Suppose we do extend pure 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, but are much harder to state in such extended (almost pure) Prolog?

特别是，这样的 Prolog 是否允许操作 Prolog 列表与 Scheme 允许操作 Scheme 列表一样方便?

In particular, does such a Prolog allow manipulating Prolog lists about as conveniently as Scheme allows manipulating Scheme lists?

假设 Scheme 没有突变、宏、延续、懒惰、流、数字、字符串、向量或字符.只是符号、布尔值和列表(树).

Assume Scheme without mutation, macros, continuations, laziness, streams, numbers, strings, vectors or characters. Just symbols, booleans and lists (trees).

推荐答案

只要 symbol/1 和 dif/2 是逻辑纯 Prolog 的足够扩展.

Just symbol/1 and dif/2 are sufficient extensions of logically pure Prolog.

证明:

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

This answer contains an evaluator for Scheme expressions, evil/2. It understands lambda and quote, and can be easily extended to handle built-in list procedures like list, car, cdr, etc. Aside from pure (Horn) Prolog, it uses only symbol/1 and dif/2. While it is an interpreter and will run slowly, its existence shows that the same list operations done by Scheme can be done in such almost pure Prolog. (I think symbol/1 wouldn't be needed either, if Scheme symbols were translated into symb(prolog_atom) instead of directly into prolog_symbol)

编辑

这扩展了evil/2来处理if、#t和#f(由true 和 false):

This extends evil/2 to handle if, #t and #f (represented by true and 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* 更强大，因为它也将等同于一些闭包:

This extends evil/2 to handle equalp. It's even more powerful than Scheme's eq* in that it will equate some closures too:

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

这篇关于是“几乎纯的"序言表达?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！