是“几乎纯"的Prolog 富有表现力? [英] 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中使用，会不会还有差距?表现力，ie 定义微不足道的事物，例如，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 是否允许像 Scheme 允许操作 Scheme 列表一样方便地操作 Prolog 列表?

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

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

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 等.除了 pure (Horn) 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).

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