3

我有一个问题是对上一个主题的跟进， 我应该避免在 Prolog 中和一般情况下使用尾递归吗？

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

早在 1970 年代，主要的 AI 语言是 LISP。相应的定义将是......

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

...不是直接尾递归的：原因是cons：在那个时候的实现中，它的参数首先被评估，然后才cons可以执行。因此，按照您的指示重写（并反转结果列表）是一种可能的优化技术。

然而，在 Prolog 中，您可以cons在知道实际值之前创建先验，这要归功于逻辑变量。这么多在 LISP 中不是尾递归的程序，在 Prolog 中被翻译成尾递归程序。

在许多 Prolog 教科书中仍然可以找到这种影响。

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

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

插件实例

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 功能的文档

缺点对象 1 对象 2 => 缺点

创建一个新的 cons ，其 car 为 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 是一个 cons ， car 返回那个 cons 的 car。如果 x 为 nil ，则 car 返回 nil 。

(cdr x) => 对象

如果 x 是 cons ，则 cdr 返回该 cons 的 cdr。如果 x 为 nil ，则 cdr 返回 nil 。

cond {条款}* => 结果*

子句::= (测试形式*)

测试表单按照它们在参数列表中给出的顺序一次评估一个，直到找到一个评估为 true 的测试表单。

如果该子句中没有表单，则 cond 表单返回 test-form 的主值 [ed: test-form 的第一个值，如果没有值，则返回 nil]。否则，与此测试表单关联的表单将按从左到右的顺序作为隐式 progn 进行评估，最后一个表单返回的值由 cond 表单返回。

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

有关详细信息，请参阅 http://www.lispworks.com/documentation/HyperSpec/Body/m_cond.htm#cond 。

defun 函数名 lambda-list 形式* => 函数名

有关详细信息，请参阅 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
4

2 回答 2

4

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

一个不相关的直接实现将是：

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

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

这也可以使用 来完成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).
于 2017-05-11T03:14:56.813 回答
3

直接翻译：

(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 的要小得多和容易得多的原因。所需要的只是将一行代码提升一两个档次（而且它可能是一样的）。

于 2018-12-10T23:20:49.243 回答