惰性求值

Published on 6月 19, 2012

惰性求值

啥叫惰性求值

具体的含义可以参看这里 惰性求值 。我的看法就是一种延迟计算方法,好像一个懒汉,只计算需要计算的东西。

为什么要惰性求值

因为惰性求值能极大优化程序的性能,想想那个Dice of Doom的游戏,如果不需要每次都生成不需要的游戏树,将会节省多少时间和电力。同时,惰性求值能做到一些几乎不可能的事,构造无穷的东西。

在common lisp中实现一整套惰性求值函数库

据作者说,像Haskell和Clojure这样的预言直接把惰性求值作为语言默认的一部分,common lisp则没有这样,不过实现一整套惰性求值库也没有什么难度

延迟求值我们想要得到这样的东西:lazy和force.lazy只返回函数。

    (lazy (+ 1 2))
    #<FUNCTION...>
    (force (lazy (+ 1 2)))
    3

lazy可以用宏这么实现

    (defmacro lazy (&body body)
      (let ((forced (gensym))
            (value (gensym)))
        `(let ((,forced nil)
               (,value nil))
           (lambda ()
             (unless ,forced;unless,when后是并行结构
               (setf ,value (progn ,@body))
               (setf ,forced t))
             ,value))))

force可以直接用简单的函数实现

    (defun force (lazy-value)
      (funcall lazy-value))

但我们需要的不只这些,要完成惰性求值需要一整套相应的函数比如延迟的cons、cdr、car、nth、mapcar等等等等。建立延迟的cons和相应的cdr和car

    (defmacro lazy-cons (a d)
      `(lazy (cons ,a ,d)))
    (defun lazy-car (x)
      (car (force x)))
    (defun lazy-cdr (x)
      (cdr (force x)))

猜猜这是在干什么

    (defparameter *integers*
      (labels ((f (n)
                 (lazy-cons n (f (1+ n)))))
        (f 1)))
    (lazy-car (lazy-cdr *integers*)) 
    (lazy-car (lazy-cdr (lazy-cdr *integers*)))

我们还需要延迟生成lazy-nil和判断空延迟求值的列表的lazy-null

    (defun lazy-nil ()
      (lazy nil))
    ;(force (lazy-nil)) 
    (defun lazy-null (x)
      (not (force x)))

然后是将常规列表和惰性列表相互转换的函数make-lazy、take、take-all.注意take-all只能返回有限列表。

    (defun make-lazy (lst)
      (lazy (when lst
              (cons (car lst) (make-lazy (cdr lst))))))
    (defun take (n lst)
      (unless (or (zerop n) (lazy-null lst))
        (cons (lazy-car lst) (take (1- n) (lazy-cdr lst)))))
    (defun take-all (lst)
      (unless (lazy-null lst)
        (cons (lazy-car lst) (take-all (lazy-cdr lst)))))
    (take 10 *integers*)
    (take 10 (make-lazy '(a s d f g h j k l q w e r t y u i)))
    (take-all (make-lazy '(a s d f g h j k l q w e r t y u i)))

是不是看不懂?作者说它深邃如禅宗公案,需要凝神细视许久才能了悟。

然后是遍历和搜索整个惰性列表的mapcar、mapcan、find-if和nth函数。mapcar和mapcan返回的也是惰性列表,find-if和nth则返回原子。

    (defun lazy-mapcar (fun lst)
      (lazy (unless (lazy-null lst)
              (cons (funcall fun (lazy-car lst))
                    (lazy-mapcar fun (lazy-cdr lst))))))
    ;现在我还是得看着Hyperspec来分辨这一堆map
    (defun lazy-mapcan (fun lst)
      (labels ((f (lst-cur)
                 (if (lazy-null lst-cur)
                   (force (lazy-mapcan fun (lazy-cdr lst)))
                   (cons (lazy-car lst-cur) (lazy (f (lazy-cdr lst-cur)))))))
        (lazy (unless (lazy-null lst)
                (f (funcall fun (lazy-car lst)))))))
    (defun lazy-find-if (fun lst)
      (unless (lazy-null lst)
        (let ((x (lazy-car lst)))
          (if (funcall fun x)
            x
            (lazy-find-if fun (lazy-cdr lst))))))
    (defun lazy-nth (n lst)
      (if (zerop n)
        (lazy-car lst)
        (lazy-nth (1- n) (lazy-cdr lst))))

使用也很直观

    (take 10 (lazy-mapcar #'sqrt *integers*))
    (take 10 (lazy-mapcan (lambda (x)
                            (if (evenp x)
                              (make-lazy (list x))
                              (lazy-nil)))
                          *integers*))
    (lazy-find-if #'oddp (make-lazy '(2 4 6 7 8 10)))
    (lazy-nth 4 (make-lazy '(a b c d e f g)))

最后的废话

不爽的事很多,人与人之间的差别太大,根本不能相互理解。上无聊的课,听老师扯淡,做无聊的事,这就是世界,这就是生活?

老师说你该下定决心了,可我带着多少不舍与怀疑,甚至畏惧。

室友dota视频依然放的很欢,还有想一暑假打dota的人。然而无关对错,谁也无法预言未来。

然而我想珍惜我的生命,珍惜令我着迷的事物。不想在这里那里被各种无聊的人和事磨灭激情,唉……

别人都在想些什么呢?别人想得差别怎么这么大?

走下去,哪怕是条孤苦的路,此生不后悔。