[cl-net-snmp-cvs] r28 - books/onlisp
ctian at common-lisp.net
ctian at common-lisp.net
Wed Aug 29 10:57:10 UTC 2007
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
More information about the Cl-net-snmp-cvs
mailing list