『惰性求值』初探

Posted by David Gu on April 5, 2015

首先,以一个经典的问题来引入惰性求值1的概念:能否用定义函数的方式定义出if2控制构造?例如,对于某个语言的 if 语句,有如下简单的语法:if test then-clause else-clauseif true (1+1) (1-1)将返回2 );那么,我们能否用定义函数的方式定义出这个if操作符?不妨先试试吧:

def new_if(test, then_clause, else_clause):
    tmp = test and then_clause
    return (tmp or else_clause)

new_if(True, 1+1, 1-1) # -> 2
new_if(False, 1+1, 1-1) # -> 0

如此看上去似乎效果不错。现在我们用这个新的 if 来写一个简单的阶乘函数:

def factorial(n):
    return new_if(n<=2, n, n*factorial(n-1))

factorial(4)
# -> should be 24, but instead, we get
# RuntimeError: maximum recursion depth exceeded

糟糕!Python解释器告诉我们由于递归深度超过了限制,计算被中断了。这说明,这个所谓new_if是行不通的,为什么呢?

事实上,包括Python在内的众多语言都是使用『严格求值序』3的。这意味着,当作为实参的表达式被送入函数体时,总是会被先求值。例如,在刚刚的例子里,由于在执行new_if之前第三个实参总是要被求值,于是整个计算过程就变成『死循环』了。

这看上去似乎是很无奈的事情。但另一方面,一门叫「Haskell」4的语言采用了『正则求值序』——即我们今天要讨论的所谓『惰性求值』。在这样的求值序下,当且仅当表达式需要被求值时才会被求值。例如,如果 Python 采用的是『正则求值序』,那么在刚刚的new_if函数体里,只有当tmpFalse的时候else-clause才会被求值,否则是不会被求值的。

所以,从这个角度看,『惰性求值』是个很有趣的概念。例如,它可以实现『惰性表』这样的东西。总的来说,利用『惰性求值』,可以避免掉不必要的计算。下面,我们先用 Python5 实现两个函数,它们可被视为实现『惰性表』的原语:

def lazy_first(Cons): return Cons[0]

def lazy_rest(Cons): return (Cons[1])()

熟悉Lisp的朋友应该都知道Cons,但是这里的ConsLispCons关系并不大,姑且只是将其看成一个二元组好了。可以看到,lazy_first直接利用索引取出了第一个元素;lazy_rest则首先取出第二个元素,并执行了一次函数调用;而从他们的名字可以看出,lazy_first被用来取出『惰性表』的第一个元素,lazy_rest则被用来取出剩余的元素并以列表的形式返回。

接下来,我们再实现两个函数6

  1. from_n接受一个整数n,返回一个从该整数起始的『惰性表』;例如,如果n为0,则我们得到一个自然数序列;
  2. take_n接受一个整数n和一个『惰性表』,返回该表的前n项。
def from_n(n):
    return [n, lambda : from_n(n+1)]

def take_n(n, lazy_list):
    if n==0: return []
    else: return [lazy_first(lazy_list)] + take_n(n-1, lazy_rest(lazy_list))

number = from_n(0) # -> [0, <function <lambda> at 0x1078d3578>]

take_n(10, number) # -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

take_n(20, number) # -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

from_n中,我们可以看到我们是怎么实现『惰性表』的:『惰性表』是一个二元组,第一个元素为表的内容,第二个元素为一个所谓「thunk」的东西——一个无参函数,此处用lambda表达式构造。这样一来,在take_n中的递归过程便不难理解了。

事实上,理解这里的『惰性表』的关键即在于理解thunk的作用:延迟计算。例如给定一个表达式 expr,经过thunk后,expr 的求值就被延迟了:expr -> lambda : expr;直到thunk被执行后,expr 才会被求值。这个概念用 Common Lisp7能很好的表达出来:

(defmacro delay (expr) `(lambda () ,expr)) ;; thunk it!

(defun force (thunk) (funcall thunk)) ;; force it to be evaluated.

这篇博文只是对『惰性求值』的一个简单介绍;我们看到,利用「thunk」,我们可以延迟计算从而实现『惰性表』这样的东西。下面是『惰性表』在 OCamlCommon Lisp 中的示例代码,以及一些引用。

OCaml8

type 'a seq = Nil
            | Cons of 'a * (unit -> 'a seq)

let first = function
  | Cons(x, _) -> x
  | Nil -> None

let rest = function
  | Cons(_, thunk) -> Some(thunk())
  | Nil -> None

let rec from_n k = Cons(k, fun() -> from_n(k+1))

let rec take_n = function
  | 0, lst -> []
  | n, Nil -> []
  | n, Cons(x, thunk) -> x :: take_n(n-1,thunk())

Common Lisp

(defmacro make-lazy-list (first rest)
  `(cons ,first #'(lambda () ,rest)))

(defun llst-first (llst) (car llst))

(defun llst-rest (llst) (funcall (cdr llst)))

(defun from-n (n)
  (make-lazy-list n (from-n (1+ n))))

(defun take-n (n llst)
  (cond ((zerop n) nil)
	((not (llst-first llst)) nil)
	(t (cons (llst-first llst)
		 (take-n (1- n) (llst-rest llst))))))

;;;; Since Common Lisp is my first language, I write two more example functions here.
;;;; 'map-llst' is just like Scheme's 'map', but not that powerful, of course.
;;;; It takes a function and a lazy list, then return another lazy list;
;;;; 'filter-llst' takes a predicate and a lazy list, then
;;;; return another lazy list which has been filtered out those 'incorrect' elements.

(defun map-llst (fn llst)
  (if (null llst)
      nil
      (make-lazy-list (funcall fn (llst-first llst))
		      (map-llst fn (llst-rest llst)))))

(defun filter-llst (pred llst)
  (cond ((null llst) nil)
	((funcall pred (llst-first llst))
	 (make-lazy-list (llst-first llst)
			 (filter-llst pred (llst-rest llst))))
	(t (filter-llst pred (llst-rest llst)))))

;;;; (setf numbers (from-n 0)) -> (0 . #<Closure (:INTERNAL FROM-N 0) @ #x20839d12>)
;;;; (setf squares (map-llst #'(lambda (x) (* x x)) numbers))
;;;; (setf even-numbers (filter-llst #'evenp numbers))
;;;; (take-n 10 numbers) -> (0 1 2 3 4 5 6 7 8 9)
;;;; (take-n 10 squares) -> (0 1 4 9 15 25 36 49 64 81)
;;;; (take-n 10 even-numbers) -> (0 2 4 6 8 10 12 14 16 18)
  1. Wikipedia, Lazy Evaluation 

  2. 这个例子事实上来自于《计算机程序构造与解释》(SICP)一书的练习1.6 

  3. Wikipedia, Strict Evaluation 

  4. Haskell Language,一门号称最『纯粹』的函数式编程语言。 

  5. 本人并没有写过多少Python代码,如果这里的代码还有其它问题,请指正,谢谢 :-) 

  6. 这段实现并不完美,例如,当惰性表的长度不足「n」时,「take_n」函数将会有些难堪;这个问题在下面的另外两个实现中解决掉了。 

  7. 「宏」在Lisp中是一种强大的机制。简单的说,「宏」是一个函数,它接收一组「S-expression」并将其映射为另一组「S-expression」。想了解一些关于「宏」的知识可参见Wikipedia以及Paul Graham所著的《On Lisp》。 

  8. 这段实现多多少少参考了《ML for the Working Programmer》一书中的相关内容。