Lisp 尾递归的 Prolog 翻译

Question

我有一个问题是上一个主题的后续问题， Should I avoid tail recursion in Prolog and in general?

在上面链接的文章中，用户 false 提供了这个代码示例和这个解释......

Back in the 1970s, the major AI language was LISP. And the corresponding definition would have been ...
  (defun addone (xs)
    (cond ((null xs) nil)
      (t (cons (+ 1 (car xs))
           (addone (cdr xs))))))
... which is not directly tail-recursive: The reason is the cons: In implementations of that time, its arguments were evaluated first, only then, the cons could be executed. So rewriting this as you have indicated (and reversing the resulting list) was a possible optimization technique.

In Prolog, however, you can create the cons prior to knowing the actual values, thanks to logic variables. So many programs that were not tail-recursive in LISP, translated to tail-recursive programs in Prolog.

The repercussions of this can still be found in many Prolog textbooks.

我的问题是：上面的 Prolog 翻译是什么？ LISP 代码 ?

编辑： 添加了 lisp 代码的示例和描述各种 lisp 函数的 lisp 文档。

addone 实例

1 > (addone '(1 2 3))

(2 3 4)

2 > (addone '('()))

> Error: The value 'NIL is not of the expected type NUMBER.
> While executing: CCL::+-2, in process listener(1).
> Type :POP to abort, :R for a list of available restarts.
> Type :? for other options.

3 > (addone '(a b c))

> Error: The value A is not of the expected type NUMBER.
> While executing: CCL::+-2, in process listener(1).
> Type :POP to abort, :R for a list of available restarts.
> Type :? for other options.

3 > ^C

lisp 功能文档

cons object-1 object-2 => 缺点

创造一个新的缺点，汽车是 object-1 ，并且它的 cdr 是 object-2 .

例子

  (cons 1 2) =>  (1 . 2)
  (cons 1 nil) =>  (1)
  (cons nil 2) =>  (NIL . 2)
  (cons nil nil) =>  (NIL)
  (cons 1 (cons 2 (cons 3 (cons 4 nil)))) =>  (1 2 3 4)
  (cons 'a 'b) =>  (A . B)
  (cons 'a (cons 'b (cons 'c '()))) =>  (A B C)
  (cons 'a '(b c d)) =>  (A B C D)

(汽车 x) => 对象

如果 x 是缺点， car returns 那辆缺点的车。如果 x 是 nil ，汽车 returns 无 .

(cdr x) => 对象

如果 x 是缺点， cdr returns cons 的 cdr。如果 x 是 nil ， cdr returns 无 .

条件{子句}* => 结果*

子句::=（测试形式形式*）

测试形式按照它们出现的顺序一次评估一个在参数列表中给出，直到找到测试形式计算结果为真。

如果该子句中没有任何形式，则 test-form [ed: test-form 的第一个值，如果有则为 nil 没有值] 由 cond 形式返回。否则，表格与此测试表单关联的按顺序进行评估，留给对，作为隐式 progn，最后一个返回的值表格由 cond 表格返回。

一旦一个测试表为真，就不会再有其他测试表了评估。如果没有测试表单产生 true，则返回 nil

见 http://www.lispworks.com/documentation/HyperSpec/Body/m_cond.htm#cond 了解更多信息。

defun 函数名 lambda 列表形式* => 函数名

见 http://www.lispworks.com/documentation/HyperSpec/Body/m_defun.htm#defun 了解更多信息。

t => T

t =>  T 
(eq t 't) =>  T
(case 'b (a 1) (t 2)) =>  2

Answer 1

这是给定 Lisp 算法在 Prolog 中的再现。请注意，Lisp 是函数式的，一个 Lisp 函数可以 return 值。 Prolog 中不是这种情况，因此您需要两个参数。

非关系的直接实现是：

addone([], []).
addone([H|T], [H1|T1]) :-
    H1 is H + 1,
    addone(T, T1).

请注意，第二个谓词子句头部的[H1|T1]参数对应于Lisp中的(cons H1 T1)。

这也可以使用 maplist 来完成，它与原始的 Lisp 实现有点不同，但是 Lisp 确实有列表映射函数，可以用来创建一个看起来更像的 Lisp 实现这个：

addone_element(X, X1) :- X1 is X + 1.
addone(List, List1) :- maplist(addone_element, List, List1).

在 Prolog 中，这可以使用 CLP(FD) 变得更相关，这对于整数推理很有用：

:- use_module(library(clpfd)).

addone([], []).
addone([H|T], [H1|T1]) :-
    H1 #= H + 1,
    addone(T, T1).

和 maplist 版本：

addone_element(X, X1) :- X1 #= X + 1.
addone(List, List1) :- maplist(addone_element, List, List1).

Answer 2

一个直接翻译：

(defun addone (xs)
    (cond ((null xs) nil)
          (t (cons (+ 1 (car xs))
                   (addone (cdr xs))))))

是

addone( XS, RESULT) :-
   (   XS = [],              % null XS ? then:
       RESULT = []           % 
   ;
       XS = [CAR | CDR],     % else:
       R is 1 + CAR,         % calculate the two
       addone( CDR, S)       %          fields         % almost TR,
       RESULT = [R | S],     % and cons them up        % save for this cons
   ).

但是，变身了，

(defun addone (xs)
    (let ((result))
      (cond ((null xs) (setf result nil))
            (t         (setf result (cons (+ 1 (car xs))
                                          (addone (cdr xs))))))
      result))
=
(defun addone (xs)
    (let ((result))
      (cond ((null xs) (setf result nil))
            (t         (setf result (list nil))
                       (setf (car result) (+ 1 (car xs)))
                       (setf (cdr result) (addone (cdr xs)))))
      result))
=
(defun addone (xs &optional (result (list nil)))        ; head sentinel
      (cond ((null xs))
            (t         (setf (cdr  result) (list nil))
                       (setf (cadr result) (+ 1 (car xs)))
                       (addone (cdr xs) (cdr result))))    ; almost TR
      (cdr result))                                    ; returned but not used
=
(defun addone (xs &aux (result (list nil)))
    (labels ((addone (xs result)
              (cond ((null xs))
                    (t (setf (cdr  result) (list nil))
                       (setf (cadr result) (+ 1 (car xs)))
                       (addone (cdr xs) (cdr result))))))   ; fully TR
        (addone xs result))
    (cdr result))

是，完全尾递归，

addone( XS, RESULT) :-
   (   XS = [], 
       RESULT = []
   ;
       XS = [CAR | CDR],
       RESULT = [R | S],     % cons two empty places, and
       R is 1 + CAR,         %   fill'em 
       addone( CDR, S)       %   up                          % fully TR
   ).

使用 Boxing / head sentinel 以便我们可以在 Common Lisp 中设置指针，但在 Prolog 中不需要——Prolog 的逻辑变量可直接设置（一次） , 命名指针。

这也是为什么 Prolog 的转换比 Lisp 的更小更容易的原因。所要做的只是将一行代码移动一两行（它本来可以是一样的）。

Lisp 尾递归的 Prolog 翻译

Prolog translation of Lisp's tail-recursion

tail-recursion

common-lisp

prolog

code-translation

tailrecursion-modulo-cons