Author: ctian Date: Thu Aug 30 09:34:36 2007 New Revision: 30
Added: books/onlisp/7-macros.tex Modified: books/onlisp/2-functions.tex books/onlisp/3-functional_programming.tex books/onlisp/onlisp.tex Log: finish chap 2, start chap 3
Modified: books/onlisp/2-functions.tex ============================================================================== --- books/onlisp/2-functions.tex (original) +++ books/onlisp/2-functions.tex Thu Aug 30 09:34:36 2007 @@ -352,7 +352,7 @@ (defun make-adder (n) #'(lambda (x) (+ x n))) \end{verbatim} -接受一个数值参数, 然后返回一个闭包, 当后者被调用时, 能够把之前那个数加到它的参数上. +\label{fun:make-adder} 接受一个数值参数, 然后返回一个闭包, 当后者被调用时, 能够把之前那个数加到它的参数上. 我们可以根据需要生成任意数量的这种加法器: \begin{verbatim}
(setq add2 (make-adder 2)
@@ -514,6 +514,168 @@ \section{尾递归} \label{sec:tail-recursion}
+递归函数调用它们自身. 如果调用以后没其他事可做, 这种调用就称为\textsl{尾递归 (tail-recursive)}. +下面这个函数不是尾递归的 +\begin{verbatim} +(defun our-length (lst) + (if (null lst) + 0 + (1+ (out-length (cdr lst))))) +\end{verbatim} +因为在从递归调用返回之后我们又把结果传给了 \texttt{1+}. 而下面这个函数就是尾递归的 +\begin{verbatim} +(defun out-find-if (fn lst) + (if (funcall fn (car lst)) + (car lst) + (our-find-if fn (cdr lst)))) +\end{verbatim} +因为通过递归调用得到的值被立即返回了. + +尾递归是非常理想的, 因为许多 Common Lisp 编译器都可以把尾递归转化成循环. 在这种编译器下, +你可以在源代码里书写优雅的递归而不必担心它们在运行期导致函数调用过载. + +一个不是尾递归的函数经常可以通过嵌入一个称为 \textsl{聚集器} 的本地函数, 来转换成尾递归的形式. +在当前上下文里, 聚集器仅指一个代表当前已完成计算量的值. 例如 \texttt{our-length} 可以转换成 +\begin{verbatim} +(defun our-length (lst) + (labels ((rec (lst acc) + (if (null lst) + acc + (rec (cdr lst) (1+ acc))))) + (rec lst 0))) +\end{verbatim} +在这里, 当前所见的列表元素的数量包含在另一个参数 \texttt{acc} 里面了. 当递归到达列表的结尾, \texttt{acc} +的值就是总的长度, 只要直接返回就好. 通过在向下调用树的过程中聚集一个值, 而不是在返回的时候构造它, 我们就可以将 +\texttt{rec} 尾递归化. + +许多 Common Lisp 编译器可以做尾递归优化, 但并非所有都是默认行为. 所以在你编写尾递归函数时, 你也许需要将 +\begin{verbatim} +(proclaim '(optimize speed)) +\end{verbatim} +写在文件的最前面, 确保编译器可以利用你的优化努力. + +提供尾递归和类型声明, 现存的 Common Lisp 编译器都可以生成运行起来快得多的代码, 甚至快过 C. Richard Gabriel +给出下列函数作为示例, 它可以从 1 加到 \texttt{n}: +\begin{verbatim} +(defun triangle (n) + (labels ((tri (c n) + (declare (type fixnum n c)) + (if (zerop n) + c + (tri (the fixnum (+ n c)) + (the fixnum (- n 1)))))) + (tri 0 n))) +\end{verbatim} +这就是快速的 Common Lisp 代码看起来的样子. 一开始以这种方式写程序可能不太自然. +通常的方式是首先以尽可能自然的方式来写一个函数, 然后如果必要的话, 把它转化成等价的尾递归形式. + +\section{编译} +\label{sec:compilation} + +Lisp 函数可以单独编译或者按文件编译. 如果你只是在 toplevel 下输入一个 \texttt{defun} 表达式. +\begin{verbatim} +> (defun foo (x) (1+ x)) +FOO +\end{verbatim} +多数实现会创建一个解释函数. 你可以使用 \texttt{compiled-function-p} 来检查一个函数是否已被编译: +\begin{verbatim} +> (compiled-function-p #'foo) +NIL +\end{verbatim} +我们可以通过把通过把名字送给 \texttt{compile} 来编译 \texttt{foo} +\begin{verbatim} +> (compile 'foo) +FOO +\end{verbatim} +这就可以编译 \texttt{foo} 的定义并且把之前的解释版本替换成编译版本. +\begin{verbatim} +> (compiled-function-p #'foo) +T +\end{verbatim} +编译和解释函数都是 Lisp 对象, 它们的对外表现相同, 除了 \texttt{compiled-function-p} 这部分. +直接给出的函数也可以编译: \texttt{compile} 希望它的第一个参数是一个名字, 但如果你给它一个 \texttt{nil}, +它就会编译第二个参数给出的 \lexpr. +\begin{verbatim} +> (compile nil '(lambda (x) (+ x 2))) +#<Function "LAMBDA (X)" {58128F31}> +\end{verbatim} +如果你同时给出名字和函数参数, \texttt{compile} 就相当于编译一个 \texttt{defun} 了: +\begin{verbatim} +> (progn (compile 'bar '(lambda (x) (* x 3))) + (compiled-function-p #'bar)) +T +\end{verbatim} + +把 \texttt{compile} 集成进语言里意味着一个程序可以随时构造和编译新函数. 尽管如此, 显式调用 \texttt{compile} +仍属于过激手段, 和调用 \texttt{eval} 相比同样值得怀疑.\footnote{某页有关于为何说显式调用 \texttt{eval} +不好的一个解释.} 当第 \ref{sec:functions_as_data} 章里说在运行时创建新函数属常用编程技术时, 它指的是从类似 +\texttt{make-adder} 那样的函数中生成的闭包, 并非指从原始列表里调用 \texttt{compile} 得到的新函数. 调用 +\texttt{compile} 并非常用编程技术---相反是极其罕见的. 所以除非必要就别那样做. 就算你在实现 Lisp +之上实现另一种语言 (并且甚至已经花费大量时间), 你需要的可能也只是宏. + +有两类函数你不能作为参数送给 \texttt{compile}. 根据 \textsc{CLTL2} (第 667 页), 你不能编译一个 +``解释性地定义在一个非空词法环境中的'' 函数. 那就是说, 在 toplevel 下你定义一个带有 \texttt{let} 的 +\texttt{foo} +\begin{verbatim} +> (let ((y 2)) + (defun foo (x) (+ x y))) +\end{verbatim} +然后 \texttt{(compile 'foo)} 并不一定能正常工作.\footnote{把这段代码写在文件里然后再编译是好的. +这一限制是由于具体实现的原因强加在解释型函数上的, 绝不是因为在如此清晰的词法环境中定义函数有什么错误.} +你也不能在一个已经编译了的函数上调用 \texttt{compile}, \textsc{CLTL2} 隐晦地暗示 ``结果是不确定的''. + +通常编译 Lisp 代码的方式是并非使用 \texttt{compile} 逐个函数地编译, 而是使用 \texttt{compile-file} +编译整个文件. 该函数接受一个文件名然后创建源代码的一个编译版本---典型的是带有相同基本文件名但有不同扩展名. +当被编译过的文件加载时, 文件里定义的所有函数对于 \texttt{compiled-function-p} 来说都是真. + +以后的章节还依赖于编译带来的另一种效果: 当一个函数产生于另一个函数里, 并且外网函数已经编译, +那么里面的函数将也会被编译. \textsc{CLTL2} 里并没有明确这一行为, 但所有正规的实现都支持. + +对于那些返回函数的函数来说, 内层函数的编译行为是很清楚的. 当 \texttt{make-adder} +(第 \pageref{fun:make-adder} 页) 被编译时, 它将返回一个编译了的函数: +\begin{verbatim} +> (compile 'make-adder) +MAKE-ADDER +> (compiled-function-p (make-adder 2)) +T +\end{verbatim} +后面的章节里将说明, 这一事实对于实现嵌入式语言来说尤为重要. 如果一种新语言是通过转换来实现的, +并且转换出来的代码是编译了的, 那它也会产生编译了的输出---也就变成了新语言的高效的编译器. +(一个简单的例子描述在某页上) + +如果我们有一个特别小的函数, 我们可能要求它被编译成内联的. 否则调用这个函数的开销可能比这个函数本身的开销都大. +如果我们定义了一个函数: +\begin{verbatim} +(defun 50th (lst) (nth 49 lst)) +\end{verbatim} +并且做了声明: +\begin{verbatim} +(proclaim '(inline 50th)) +\end{verbatim} +然后一个编译的函数里针对 \texttt{50th} 的引用就不需要一个实际的函数调用了. 如果我们定义并且编译一个调用了 +\texttt{50th} 的函数, +\begin{verbatim} +(defun foo (lst) + (+ (50th lst) 1)) +\end{verbatim} +那么当 \texttt{foo} 被编译时, \texttt{50th} 的代码应该被编译进它里面. 就好像我们一开始写的就是 +\begin{verbatim} +(defun foo (lst) + (+ (nth 49 lst) 1)) +\end{verbatim} +那样. 唯一的缺点是当我们重新定义 \texttt{50th} 以后, 也必须重新编译 \texttt{foo}, 否则它用的还是旧定义. +内联函数的限制基本上和宏差不多 (见第 \ref{sec:dependence_on_macros} 章). + +\section{作为列表的函数} +\label{functions_from_lists} + +在一些早期的 Lisp 方言中, 函数被表达成一个列表. 这给了程序员们不同寻常的编写和执行他们自己的 Lisp 程序的能力. +在 Common Lisp 中, 函数不再由列表组成---好的实现把它们编译成本机代码. 但你仍然可以写出那种写程序的程序, +因为列表是编译器的输入. + +难以形容 Lisp 程序可以写 Lisp 程序这件事有多么重要, 尤其是当这一事实经常被忽视时. 即使有经验的 Lisp +程序员也很少认识到他们从这种语言风格里享受到的好处. 例如 \texttt{这} 就是为何 Lisp 宏如此有力. +本书里描述的大部分技术都依赖于编写管理 Lisp 表达式的程序的能力.
%%% Local Variables: %%% coding: utf-8
Modified: books/onlisp/3-functional_programming.tex ============================================================================== --- books/onlisp/3-functional_programming.tex (original) +++ books/onlisp/3-functional_programming.tex Thu Aug 30 09:34:36 2007 @@ -1,6 +1,18 @@ \chapter{函数型编程} \label{chap:functional_programming}
+前一章解释了 Lisp 和 Lisp 程序是怎样构建自单一的基本材料: 函数. 与任何建筑材料一样, +它的品质既影响我们所建造的东西的种类, 也影响我们建造它的方式. + +本章描述了 Lisp 界流行的那类构造方法. 这些方法的高度精巧允许我们去尝试更加雄心勃勃的那类程序. +下一章将描述一类特别重要的程序, 现在对 Lisp 来说成为可能了: +程序逐渐进化而不是以老式的先计划再实现的方法开发. + +\section{函数型设计} +\label{sec:functional_design} + + + %%% Local Variables: %%% coding: utf-8 %%% mode: latex
Added: books/onlisp/7-macros.tex ============================================================================== --- (empty file) +++ books/onlisp/7-macros.tex Thu Aug 30 09:34:36 2007 @@ -0,0 +1,11 @@ +\chapter{Macros} +\label{chap:macros} + +\section{宏的依赖关系} +\label{sec:dependence_on_macros} + +%%% Local Variables: +%%% coding: utf-8 +%%% mode: latex +%%% TeX-master: nil +%%% End:
Modified: books/onlisp/onlisp.tex ============================================================================== --- books/onlisp/onlisp.tex (original) +++ books/onlisp/onlisp.tex Thu Aug 30 09:34:36 2007 @@ -12,12 +12,12 @@
\begin{titlepage} \title{On Lisp\thanks{原书网站: \texttt{http://www.paulgraham.com/onlisp.html%7D%7D%7D -\author{Paul Graham [著] - \and Chun Tian (binghe) [译] +\author{Paul Graham [原著] + \and Chun Tian (binghe) [翻译] \thanks{E-mail: \texttt{binghe.lisp@gmail.com}}\ NetEase.com, Inc.\ 杭州研究院 - \and Jianshi Huang [校] + \and Jianshi Huang [校对] \thanks{E-mail: \texttt{jianshi.huang@gmail.com}}\ 電気通信大学 システム工学\ 本多研究室} @@ -30,6 +30,7 @@ \include{1-the_extensible_language} \include{2-functions} \include{3-functional_programming} +\include{7-macros} \include{24-prolog}
\include{packages}