Common Lisp中的持续传递风格？

Question

为了找到一个不让我头疼的CPS的简单例子,我遇到了这个Scheme代码(Hand typed,所以parens可能不匹配):

(define fact-cps
    (lambda(n k)
        (cond
            ((zero? n) (k 1))
            (else
                (fact-cps (- n 1)
                          (lambda(v)
                             (k (* v n))))))))
(define fact
    (lambda(n)
        (fact-cps n (lambda(v)v))))  ;; (for giggles try (lambda(v)(* v 2)))

(fact 5) => 120

很棒,但Scheme 并不是 Common Lisp,所以我对它进行了一次尝试:

(defun not-factorial-cps(n k v)
    (declare (notinline not-factorial-cps)) ;; needed in clisp to show the trace
    (cond
        ((zerop n) (k v))
        ((not-factorial-cps (1- n) ((lambda()(setq v (k (* v n))))) v))))
       ;; so not that simple...
(defun factorial(n)
    (not-factorial-cps n (lambda(v)v) 1))

(setf (symbol-function 'k) (lambda(v)v))

(factorial 5) => 120

正如你所看到的,我遇到了一些问题,所以虽然这有效,但这一定是错的.我认为我所取得的成就是一种令人费解的方式来做累积器传递方式.除了回到绘图板之外,我还有一些问题:在Scheme示例中,v的初始值是从哪里来的？难道需要的是lambda表达式只能用？会不会名为功能完成更多,因为你可以保持在一个数据结构中的每个的延续,它可以根据需要被操纵的状态？在Common Lisp中是否有特定的样式/延续传递方式,有或没有所有的宏？谢谢.

Answer 1

您的代码的问题是您在重复时调用匿名函数,而不是像在Scheme示例中那样传递延续.Scheme代码可以很容易地变成Common Lisp:

(defun fact-cps (n &optional (k #'values))
  (if (zerop n) 
      (funcall k 1)
      (fact-cps (- n 1)
                (lambda (v)
                  (funcall k (* v n))))))

(fact-cps 10) ; ==> 3628800

由于代码没有使用几个术语或我改变的隐式预测,if因为我认为它稍微更具可读性.除此之外,funcall由于Common Lisp的LISP-2性质的使用,它与您的Scheme版本的代码相同.

这里有一个例子,你不能在没有变异或CPS的情况下递归递归:

(defun fmapcar (fun lst &optional (k #'values))
  (if (not lst)
      (funcall k lst)
      (let ((r (funcall fun (car lst))))
        (fmapcar fun
                 (cdr lst)
                 (lambda (x)
                   (funcall k (cons r x)))))))

(fmapcar #'fact-cps '(0 1 2 3 4 5)) ; ==>  (1 1 2 6 24 120)

编辑

在Scheme示例中,v的初始值是从哪里来的？

对于每次递归,函数都会创建一个函数,该函数使用来自此迭代的值调用前一个continuation,并使用下一次迭代中的值作为参数v.在我,fmapcar如果你这样做(fmapcar #'list '(1 2 3))变成

;; base case calls the stacked lambdas with NIL as argument
((lambda (x) ; third iteration
   ((lambda (x) ; second iteration 
      ((lambda (x) ; first iteration
         (values (cons (list 1) x)))
       (cons (list 2) x)))
    (cons (list 3) x))
   NIL)

现在,在第一次迭代中,延续是值,我们将其包含在lambda中,同时使用尚未计算的尾部来构造第一个元素.下一次迭代我们创建了另一个lambda,我们用这个迭代调用前一个continuation来处理尚未计算的尾部.最后我们用空列表调用这个函数,它调用从结尾到开头的所有嵌套函数即使迭代按照你如何组合列表的相反顺序,也能以正确的顺序生成结果列表.

是否只需要使用lambda表达式？会不会名为功能完成更多,因为你可以保持在一个数据结构中的每个的延续,它可以根据需要被操纵的状态？

我使用一个命名函数(值)来启动它,但是事实cps的每次迭代都有它自己的自由变量n和k,这对于该迭代是唯一的.这是使用的数据结构,并且它是您需要使用的命名函数,flet或者labels与匿名lambda函数在同一范围内.由于您在新的闭包中应用了先前的延续,因此每次都需要构建一个新的闭包.

在Common Lisp中是否有特定的样式/延续传递方式,有或没有所有的宏？

除了双命名空间之外,它是相同的.你需要funcall或者apply.除此之外,你可以像任何其他语言一样.