惰性求值

在common lisp完成一套惰性求值函数库。

惰性求值

啥叫惰性求值

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

为什么要惰性求值

因为惰性求值能极大优化程序的性能,想想那个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的人。然而无关对错,谁也无法预言未来。

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

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

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