Lisp里的延迟执行

Ping Zhou, 2021-07-31

在图计算和协程里经常会用到的“延迟执行”，在Lisp里，只需要十几行代码就能实现！

创建和使用延迟执行对象

首先我们来定义一个宏 defer ，它的作用是把输入的代码块变成一个延迟执行的对象（其实是一个闭包）：

(defmacro defer (&body body)
  (let ((executed (gensym))
        (result (gensym)))
    `(let ((,executed nil)
           (,result nil))
       (lambda ()
         (unless ,executed
           (setf ,result (progn ,@body))
           (setf ,executed t))
         ,result))))

而如果要执行之前被推迟的代码，可以用这个函数：

(defun defer-execute (deferred)
  (funcall deferred))

例如，我们有这样一块代码：

(princ "Hello, world.")
(princ (1+ 2))

用 defer 来包装它：

(defer
  (princ "Hello, world.")
  (princ (1+ 2)))

defer 会把输入的代码块包装成一个闭包返回给我们。所以通常我们要把这个闭包存在一个变量里：

(defvar *deferred-hello*
  (defer
    (princ "Hello, world.")
    (princ (1+ 2))))

等我们想要执行这个代码块的时候，只需要用 defer-execute 来调用这个闭包：

(defer-execute *deferred-hello*)

输出结果：

Hello, world.3
3 (2 bits, #x3, #o3, #b11)

怎么理解这个 defer 宏？我们把它展开一下就明白了：

(macroexpand
 '(defer
   (princ "Hello, World.")
   (princ (1+ 2))))

展开后得到这样的一段代码：

(LET ((#:G659 NIL) (#:G660 NIL))
  (LAMBDA ()
    (UNLESS #:G659
      (SETF #:G660 (PROGN (PRINC "Hello, World.") (PRINC (1+ 2))))
      (SETF #:G659 T))
    #:G660))

defer 首先用 gensym 产生两个临时变量，分别用来记录该代码块是否被执行过，以及运行后的返回值（通常是代码块中最后一个求值表达式的结果）。如果该代码块没有执行过，它就把输入的代码块放到一个 progn 块里顺序执行，然后把返回值记录下来。下次再执行这个闭包的话，就直接返回记录下来的值。

而 defer-execute 就是用 funcall 来执行这个闭包。

一个例子：“延迟”列表

我们可以用 defer 来包装一组列表的API。

(defmacro deferred-cons (a b)
  `(defer (cons ,a ,b)))

(defun deferred-car (x)
  (car (defer-execute x)))

(defun deferred-cdr (x)
  (cdr (defer-execute x)))

(defun deferred-nil ()
  (defer nil))

(defun deferred-null (x)
  (not (defer-execute x)))

这些API就相当于列表API（ car, cdr, cons ）的“延迟执行”版本。

然后呢，我们可以用递归的办法把普通列表转换成一个“延迟执行列表”：

(defun make-deferred-list (lst)
  (defer (when lst
           (cons (car lst) (make-deferred-list (cdr lst))))))

是不是就有点绕了？我们用简单的例子来分析一下。假如我们有个列表 (1 2 3) ，把它转换成延迟执行列表：

(defvar *dlist*
  (make-deferred-list '(1 2 3)))

我们会得到一个闭包：

#<CLOSURE (LAMBDA () :IN MAKE-DEFERRED-LIST) {10036DC8CB}>

这其实是一个构造列表 (1 2 3) 的函数的闭包。如果我们把参数 (1 2 3) 代入 make-deferred-list 的实现，并展开宏：

(macroexpand
 '(defer (when '(1 2 3)
           (cons (car '(1 2 3)) (make-deferred-list (cdr '(1 2 3)))))))

得到展开后的代码：

(LET ((#:G665 NIL) (#:G666 NIL))
  (LAMBDA ()
    (UNLESS #:G665
      (SETF #:G666
              (PROGN
               (WHEN '(1 2 3)
                 (CONS (CAR '(1 2 3)) (MAKE-DEFERRED-LIST (CDR '(1 2 3)))))))
      (SETF #:G665 T))
    #:G666))

这段代码包含的这个lambda函数，返回的是一个cons对（类似于Python里的二元组）：

(CONS (CAR '(1 2 3)) (MAKE-DEFERRED-LIST (CDR '(1 2 3))))

其中第一个元素是 car '(1 2 3) ，也就是1 ，第二个元素调用是 make-deferred-list 形成的另一个闭包，而这个闭包产生的是 (2 3) 的延迟列表。

所以如果我们执行这个闭包：

(defer-execute *dlist*)

得到的是这样一个东西：

(1 . #<CLOSURE (LAMBDA () :IN MAKE-DEFERRED-LIST) {100840F14B}>

我们如果对它作car操作，得到的是列表的第一个元素1，而如果我们想要后续的元素，就需要进一步执行后面那个闭包来得到。

这个过程可以这么理解：我这个闭包假装是一个列表，其实我具体只有第一个元素，后面的元素都在另一个闭包里，你问我要第一个元素，我马上就可以给你，但如果你问我要第2或第3个元素，我就去执行后面的闭包来给你。

类似的，还可以给这个延迟列表API加上 mapcar 的延迟版本，等等。

另一个有趣的例子：“无限”整数列表

接下来看一个有趣的例子：我们可以用前面的“延迟列表”API，创建一个包含1到无穷大的“无限”整数列表！

所需要的代码就这几行：

(defparameter *ints*
  (labels ((f (n)
             (deferred-cons n (f (1+ n)))))
    (f 1)))

这个 *ints* 变量，也是一个闭包，里面是我们定义的这个内部函数f，而这个内部函数f，返回的就是一个生成延迟列表（二元组）的闭包：

(deferred-cons n (f (1+ n)))

这里 deferred-cons 返回的这个闭包，会产生一个与前面类似的二元组，第一个元素是参数n，第二个元素则是递归调用f的闭包。所以如果我们执行这个 *ints* 对象：

(defer-execute *ints*)

得到的是这样一个二元组：

(1 . #<CLOSURE (LAMBDA () :IN F) {100855314B}>)

同样，如果我们用 deferred-cdr 取二元组的后面项，然后执行它：

(defer-execute (deferred-cdr *ints*))

得到的时候以2开头的一个二元组：

(2 . #<CLOSURE (LAMBDA () :IN F) {100899D1EB}>)

以此类推，可以一直这样 car, cdr 下去，看起来就好象得到了一个从1开始到无穷大的“无限”整数列表。

这个无穷列表可以这么想象：表面上看，我这个“列表”从1开始包含了到无穷大的数，你可以不停的 car, cdr 从我这里取数。其实呢，我这里只有第一个数1，后面的是一个闭包，你要第2个数，我就去执行闭包得到2；你要第三个数，我就继续执行2后面的闭包，给你3……

进一步讨论

从这个 defer 宏的实现可以看出，它保证输入的代码块只会被执行一次，如果这个延迟执行闭包被多次调用，后续的调用只会返回相同的返回值，而不会真的执行里面的代码块。所以我前面的例子里用 princ 其实并不是最恰当，因为如果你再次执行闭包的话，会发现它不会再打印“Hello, World”了。

另一个考虑， defer 包装出的闭包如果要用在图计算里，那么势必要有输入输出（例如某个节点从前一节点输入，经过计算输出结果，作为下一节点的输入）。我初步的想法是随着计算图创建各个闭包，并且把图中节点的连接性也打包进闭包，例如在创建某个节点的闭包时，引用它的输入节点闭包，作为代码块的一部分一起打包到闭包里。下次有空试试这个应用。

最后还是感叹一下，Lisp真有意思啊！

注：部分示例参考Land of Lisp（landoflisp.com）