Author: ctian Date: Wed Aug 29 06:57:08 2007 New Revision: 28

Modified: books/onlisp/2-functions.tex Log: more chap 2

Modified: books/onlisp/2-functions.tex ============================================================================== --- books/onlisp/2-functions.tex (original) +++ books/onlisp/2-functions.tex Wed Aug 29 06:57:08 2007 @@ -274,7 +274,246 @@ \section{作用域} \label{sec:scope}

-Common Lisp 是一种词法作用域 (lexically scope) 的 Lisp. Scheme 是最早的词法作用域方言; 在 Scheme 之前 +Common Lisp 是一种词法作用域 (lexically scope) 的 Lisp. Scheme 是最早的词法作用域方言; 在 Scheme 以前, +动态作用域 (dynamic scope) 被看作 Lisp 的一种明确定义的风格. + +词法和动态作用域的区别取决于一个实现如何处理自由变量. 我们称一个符号在表达式里是约束 (bound) 的, +当且仅当它被作为变量建立起来, 这可以来自参数, 也可以来自像 \texttt{let} 和 \texttt{do} 这样的变量绑定操作符. +不受约束的符号, 就说它是 \textsl{自由} 的. 下面的例子具体说明了作用域: +\begin{verbatim} +(let ((y 7)) + (defun scope-test (x) + (list x y))) +\end{verbatim} +在函数表达式里, x 是受约束的, 而 y 是自由的. 自由变量的有趣之处在于它们应有的值并不是很明显. +一个约束变量的值是毫无疑问的---当 \texttt{scope-test} 被调用时, x 的值就是通过参数传给它的值. +但 y 的值应该是什么呢? 这个问题要看具体方言的作用域规则. + +在动态作用域的 Lisp 里, 要想找出当 \texttt{scope-test} 执行时自由变量的值, 我们要回头检查函数的调用链. +当我们发现一个 y 被约束的环境是, 那个 y 的绑定就将是 \texttt{scope-test} 里使用的那个. 如果我们没有发现, +那我们就取 y 的全局值. 这样, 在一个动态作用域的 Lisp 里, 在调用的时候 y 将会产生这样的值: +\begin{verbatim} +> (let ((y 5)) + (scope-test 3)) +(3 5) +\end{verbatim} +在动态作用域里, 当 \texttt{scope-test} 被定义时 y 被绑定到 7 就没有任何意义了. 当 \texttt{scope-test} +被调用时 y 只有一个值, 就是 5. + +在词法作用域的 Lisp 里, 和回头检查函数的调用链不一样的是, 我们回头检查当这个函数被 \textsl{定义} 时所处的环境. +在一个词法作用域 Lisp 里, 我们的示例将捕捉到当 \texttt{scope-test} 被定义时变量 y 的绑定. +所以下面的事情将会发生在 Common Lisp 里: +\begin{verbatim} +> (let ((y 5)) + (scope-test 3)) +(3 7) +\end{verbatim} +这里将 y 绑定到 5 在调用时对返回值没有任何效果. + +尽管你仍然可以通过将变量声明为 \textsl{special} 来得到动态作用域, 词法作用域是 Common Lisp 的默认行为. +整体来看, Lisp 社区看待动态作用域的过时几乎没什么惋惜之情. 有一点就是它经常会导致痛苦而又难以捉摸的 bug. +但词法作用域不只是一种避免错误的方式而已. 下一章会看到, 它也同时使某种崭新的编程技术成为可能. + +\section{闭包} +\label{sec:closures} + +由于 Common Lisp 是词法作用域的, 当我们定义一个包含自由变量的函数时, 系统必须在函数定义的时候保存那些变量的绑定. +这种函数和一组变量绑定的组合称为\textsl{闭包}. 闭包被用于广泛的应用场合. + +闭包在 Common Lisp 程序中如此无所不在以至于你可能已经用了却不知情. 每当你给 \texttt{mapcar} +一个包含自由变量的前缀 \sq 的 \lexpr 时, 你就在使用闭包. 例如, 假设我们想写一个函数, +它接受一个数列并且给每个数增加确定的数量. 这个 \texttt{list+} 函数 +\begin{verbatim} +(defun list+ (lst n) + (mapcar #'(lambda (x) (+ x n)) + lst)) +\end{verbatim} +将做到我们想要的: +\begin{verbatim} +> (list+ '(1 2 3) 10) +(11 12 13) +\end{verbatim} +如果我们仔细观察 \texttt{list+} 里传给 \texttt{mapcar} 的那个函数, 它实际上是个闭包. 那个 n 是自由的, +它的绑定来自周围的环境. 在词法作用域下, 映射函数的每一次使用都将导致创建一个闭包.\footnote{ +在动态作用域下, 同样的说法却来自不同的原因---由于 \texttt{mapcar} 的任一参数都不叫做 x.} + +闭包在 Abelson 和 Sussman 的经验教材 \textsl{Structure and Interpretation of Computer Programs} +一书中担当了更加重要的角色. 闭包是带有本地状态的函数. 使用这种状态最简单的方式是如下的情况: +\begin{verbatim} +(let ((counter 0)) + (defun new-id () (incf counter)) + (defun reset-id () (setq counter 0))) +\end{verbatim} +这两个函数共享一个计数器变量. 前者返回计数器的下一个值, 后者把计数器重置到 0. +这种方式避免了对计数器变量非预期的引用, 尽管同样的事情也可以用一个全局的计数器变量做到. + +能返回一个带有本地状态的函数也是很有用的. 例如这个 \texttt{make-adder} 函数 +\begin{verbatim} +(defun make-adder (n) + #'(lambda (x) (+ x n))) +\end{verbatim} +接受一个数值参数, 然后返回一个闭包, 当后者被调用时, 能够把之前那个数加到它的参数上. +我们可以根据需要生成任意数量的这种加法器: +\begin{verbatim} +> (setq add2 (make-adder 2) + add10 (make-adder 10)) +#<Interpreted Function "LAMBDA (N)" {58121711}> +> (funcall add2 5) +7 +> (funcall add10 3) +13 +\end{verbatim} +在 \texttt{make-adder} 返回的那些闭包里, 内部状态都是固定的, 但其实也有可能生成那种可以要求改变他们状态的闭包. +\begin{verbatim} +(defun make-adderb (n) + #'(lambda (x &optional change) + (if change + (setq n x) + (+ x n)))) +\end{verbatim} +这个新版本的 \texttt{make-adder} 函数返回一个闭包, 当以一个参数被调用时, 其行为就跟旧版本的一样. +\begin{verbatim} +> (setq addx (make-adderb 1)) +#<Interpreted Function "LAMBDA (N)" {5812A2F9}> +> (funcall addx 3) +4 +\end{verbatim} +尽管如此, 当这个新型的加法器用非空的第二个参数调用时, 它内部的 n 的拷贝将被重置成由第一个参数指定的值: +\begin{verbatim} +> (funcall addx 100 t) +100 +> (funcall addx 3) +103 +\end{verbatim} + +甚至有可能返回共享同一数据对象的一组闭包. 图 \ref{fig:make-dbms} 包含有一个创建原始数据库的函数. +它接受一个关联表 (\texttt{db}), 并且相应地返回一个由查询, 追加和删除这三个闭包所组成的列表. + +\begin{figure} +\begin{verbatim} +(defun make-dbms (db) + (list + #'(lambda (key) + (cdr (assoc key db))) + #'(lambda (key val) + (push (cons key val) db) + key) + #'(lambda (key) + (setf db (delete key db :key #'car)) + key))) +\end{verbatim} +\caption{\label{fig:make-dbms}一个列表里的三个闭包} +\end{figure} + +对 \texttt{make-dbms} 的每次调用创建一个新数据库---封闭在共享的关联表之上的一组新函数. +\begin{verbatim} +> (setq cities (make-dbms '((boston . us) (paris . france)))) +(#<Interpreted Function "LAMBDA (DB)" {581345C9}> + #<Interpreted Function "LAMBDA (DB)" {58134619}> + #<Interpreted Function "LAMBDA (DB)" {58134669}>) +\end{verbatim} +数据库里实际的关联表对外界是不可见的, 我们甚至不知道它是个关联表---但是它可以通过组成 \texttt{cities} +的那些函数访问到: +\begin{verbatim} +> (funcall (car cities) 'boston) +US +> (funcall (second cities) 'london 'england) +LONDON +> (funcall (car cities) 'london) +ENGLAND +\end{verbatim} +调用一个列表的 \texttt{car} 多少有些难看. 实际的程序中, 函数访问的入口可能隐藏在结构体里. +当然也可以设法更清晰地使用它们---数据库可以间接地通过类似这样的函数访问: +\begin{verbatim} +(defun lookup (key db) + (funcall (car db) key)) +\end{verbatim} +尽管如此, 闭包的行为不会受到如此包装的影响. + +实际程序中的闭包和数据结构往往比我们在 \texttt{make-adder} 和 \texttt{make-dbms} 里看到的更为精巧. +这里用到的单个共享变量也可以发展成任意数量的变量，每个都可以约束到任何数据结构上。 + +闭包是 Lisp 的一个明确和独特的优势. 某些 Lisp 程序, 如果努努力的话, 还有可能翻译到不那么强大的语言上, +但只要试着去翻译上面那些使用了闭包的程序, 就会明白这种抽象帮我们省去了多少工作. +后续章节将继续探讨闭包的更多细节. 第 5 章展示了如何用它们构造复合函数, 然后第 6 +章里请看它们如何用来替代传统的数据结构. + +\section{本地函数} +\label{sec:local_functions} + +当我们用 \lexpr 来定义函数时, 我们就会面对一个使用 \texttt{defun} 时所没有的限制: 一个用 \lexpr +定义的函数由于没有名字, 因此也就没有办法引用其自身. 这意味着在 Common Lisp 里我们不能使用 \texttt{lambda} +来定义递归函数. + +如果我们想要应用某些函数到一个列表的所有元素上, 我们可以使用最熟悉的 Lisp 语句: +\begin{verbatim} +> (mapcar #'(lambda (x) (+ 2 x)) + '(2 5 7 3)) +(4 7 9 5) +\end{verbatim} +如果我们想要把一个递归函数作为第一个参数送给 \texttt{mapcar} 呢? 如果函数已经用 \texttt{defun} 定义了, +我们就可以通过名字简单地引用它: +\begin{verbatim} +> (mapcar #'copy-tree '((a b) (c d e))) +((A B) (C D E)) +\end{verbatim} +但现在假设这个函数必须是一个闭包, 带有从 \texttt{mapcar} 发生时所处环境的一些绑定. 在我们的 \texttt{list+} +例子里, +\begin{verbatim} +(defun list+ (lst n) + (mapcar #'(lambda (x) (+ x n)) + lst)) +\end{verbatim} +\texttt{mapcar} 的第一个参数, \texttt{\sq(lambda (x) (+ x n))}, 必须定义在 \texttt{list+} +里因为它需要捕捉 \texttt{n} 的绑定. 到目前为止都还算好, 但如果我们要给 \texttt{mapcar} +传递的函数在需要本地状态 \textsl{同时} 也需要递归呢? 我们不能使用一个在其他地方通过 \texttt{defun} +定义的函数, 因为我们需要本地环境的绑定. 并且我们也不能使用 \texttt{lambda} 来定义一个递归函数, +因为这个函数将没有办法引用其自身. + +Common Lisp 提供了一个 \texttt{labels} 以解决这一两难困境. 作为重要的保留, \texttt{labels} +有点儿像函数的 \texttt{let}. \texttt{labels} 表达式里的每一个绑定规范必须是如下形式: +\begin{verbatim} +(<name> <parameters> . <body>) +\end{verbatim} +在 \texttt{labels} 表达式里, \texttt{<name>} 将指向等价于下面这样的函数: +\begin{verbatim} +#'(lambda <parameters> . <body>) +\end{verbatim} +例如, +\begin{verbatim} +> (labels ((inc (x) (1+ x))) + (inc 3)) +> 4 +\end{verbatim} +尽管如此, 在 \texttt{let} 与 \texttt{labels} 之间有一个重要区别. 在 \texttt{let} 表达式里, +一个变量的值不能依赖于同一个 \texttt{let} 里生成的另一个变量---就是说, 你不能说 +\begin{verbatim} +(let ((x 10) (y x)) + y) +\end{verbatim} +然后期待这个新的 $y$ 能反映出那个新 $x$ 的值来. 相反, 在 \texttt{labels} 里定义的函数 $f$ +的函数体里就可以引用那里定义的其他函数, 包括 $f$ 本身, 这就使定义递归函数成为可能. + +使用 \texttt{labels} 我们就可以写出类似 \texttt{list+} 这样的函数了, 但这里 \texttt{mapcar} +的第一个函数是递归函数: +\begin{verbatim} +(defun count-instances (obj lsts) + (labels ((instances-in (lst) + (if (consp lst) + (+ (if (eq (car lst) obj) 1 0) + (instances-in (cdr lst))) + 0))) + (mapcar #'instances-in lsts))) +\end{verbatim} +该函数接受一个对象和一个列表, 然后返回该对象在列表的每个元素(作为列表)中出现的次数, 所组成的列表: +\begin{verbatim} +> (count-instances 'a '((a b c) (d a r p a) (d a r) (a a))) +(1 2 1 2) +\end{verbatim} + +\section{尾递归} +\label{sec:tail-recursion} +

%%% Local Variables: %%% coding: utf-8