《ANSI Common Lisp》- 第六章:函数【笔记】

理解函数是理解 Lisp 的关键之一。概念上来说,函数是 Lisp 的核心所在。实际上呢,函数是你手边最有用的工具之一。

6.1 全局函数 (Global Functions)

谓词 fboundp 告诉我们,是否有个函数的名字与给定的符号绑定。如果一个符号是函数的名字,则 symbol-function 会返回它:

[1]> (fboundp '+)

T

[2]> (symbol-function '+)

#<SYSTEM-FUNCTION +>

可通过 symbol-function 给函数配置某个名字

[3]> (setf (symbol-function 'add2)

  #'(lambda (x) (+ x 2)))

#<FUNCTION :LAMBDA (X) (+ X 2)>

新的全局函数可以这样定义,用起来和 defun 所定义的函数一样:

[4]> (add2 1)

3

实际上 defun 做了稍微多的工作,将某些像是

(defun add2 (x) (+ x 2))

翻译成上述的 setf 表达式。使用 defun 让程序看起来更美观,并或多或少帮助了编译器,但严格来说,没有 defun 也能写程序。

通过把 defun 的第一个实参变成这种形式的列表 (setf f) ,你定义了当 setf 第一个实参是 f 的函数调用时,所会发生的事情。下面这对函数把 primo 定义成car 的同义词:

[8]> (defun primo (lst) (car lst))

PRIMO

[9]>

(defun (setf primo) (val lst)

  (setf (car lst) val))

(SETF PRIMO)

在函数名是这种形式 (setf f) 的函数定义中,第一个实参代表新的数值,而剩余的实参代表了传给 f 的参数。

现在任何 primo 的 setf ,会是上面后者的函数调用:

[10]> (let ((x (list 'a 'b 'c)))

    (setf (primo x) 480)

    x)

(480 B C)

不需要为了定义 (setf primo) 而定义 primo ,但这样的定义通常是成对的。

由于字符串是 Lisp 表达式,没有理由它们不能出现在代码的主体。字符串本身是没有副作用的,除非它是最后一个表达式,否则不会造成任何差别。如果让字符串成为 defun 定义的函数主体的第一个表达式,

[11]> (defun foo (x)

  "Implements an enhanced paradigm of diversity"

  x)

FOO

那么这个字符串会变成函数的文档字符串(documentation string)。要取得函数的文档字符串,可以通过调用 documentation 来取得:

[12]> (documentation 'foo 'function)

"Implements an enhanced paradigm of diversity"

6.2 局部函数 (Local Functions)

通过 defun 或 symbol-function 搭配 setf 定义的函数是全局函数。你可以像存取全局变量那样,在任何地方存取它们。定义局部函数也是有可能的,局部函数和局部变量一样,只在某些上下文内可以访问。

局部函数可以使用 labels 来定义,它是一种像是给函数使用的 let 。它的第一个实参是一个新局部函数的定义列表,而不是一个变量规格说明的列表。列表中的元素为如下形式:

(name parameters . body)

而 labels 表达式剩余的部份,调用 name 就等于调用 (lambda parameters . body) 。

[13]> (labels ((add10 (x) (+ x 10))

          (consa  (x) (cons 'a x)))

    (consa (add10 3)))

(A . 13)

labels 与 let 的类比在一个方面上被打破了。由 labels 表达式所定义的局部函数,可以被其他任何在此定义的函数引用,包括自己。所以这样定义一个递归的局部函数是可能的:

[14]> (labels ((len (lst)

            (if (null lst)

                0

                (+ (len (cdr lst)) 1))))

    (len '(a b c)))

3

5.2 节展示了 let 表达式如何被理解成函数调用。 do 表达式同样可以被解释成调用递归函数。这样形式的 do :

(do ((x a (b x))

    (y c (d y)))

    ((test x y) (z x y))

  (f x y))

等同于

(labels ((rec (x y)

          (cond ((test x y)

                  (z x y))

                (t

                  (f x y)

                  (rec (b x) (d y))))))

  (rec a c))

这个模型可以用来解决,任何你对于 do 行为仍有疑惑的问题。

6.3 参数列表 (Parameter Lists)

2.1 节我们演示过,有了前序表达式, + 可以接受任何数量的参数。从那时开始,我们看过许多接受不定数量参数的函数。要写出这样的函数,我们需要使用一个叫做剩余( rest )参数的东西。

如果我们在函数的形参列表里的最后一个变量前,插入 &rest 符号,那么当这个函数被调用时,这个变量会被设成一个带有剩余参数的列表。现在我们可以明白funcall 是如何根据 apply 写成的。它或许可以定义成:

[21]> (defun our-funcall (fn &rest args)

  (apply fn args))

我们也看过操作符中,有的参数可以被忽略,并可以缺省设成特定的值。这样的参数称为选择性参数(optional parameters)。(相比之下,普通的参数有时称为必要参数「required parameters」) 如果符号 &optional 出现在一个函数的形参列表时,

[22]> (defun philosoph (thing &optional property)

  (list thing 'is property))

那么在 &optional 之后的参数都是选择性的,缺省为 nil :

[25]> (philosoph 'death)

(DEATH IS NIL)

我们可以明确指定缺省值,通过将缺省值附在列表里给入。这版的 philosoph

[26]> (defun philosoph (thing &optional (property 'fun))

  (list thing 'is property))

有着更鼓舞人心的缺省值:

[27]> (philosoph 'death)

(DEATH IS FUN)

选择性参数的缺省值可以不是常量。可以是任何的 Lisp 表达式。若这个表达式不是常量,它会在每次需要用到缺省值时被重新求值。

一个关键字参数(keyword parameter)是一种更灵活的选择性参数。如果你把符号 &key 放在一个形参列表,那在 &key 之后的形参都是选择性的。此外,当函数被调用时,这些参数会被识别出来,参数的位置在哪不重要,而是用符号标签(译注: : )识别出来:

[28]> (defun keylist (a &key x y z)

    (list a x y z))

KEYLIST

[29]> (keylist 1 :y 2)

(1 NIL 2 NIL)

[30]>  (keylist 1 :y 3 :x 2)

(1 2 3 NIL)

和普通的选择性参数一样,关键字参数缺省值为 nil ,但可以在形参列表中明确地指定缺省值。

关键字与其相关的参数可以被剩余参数收集起来,并传递给其他期望收到这些参数的函数。举例来说,我们可以这样定义 adjoin :

(defun our-adjoin (obj lst &rest args)

  (if (apply #'member obj lst args)

      lst

      (cons obj lst)))

由于 adjoin 与 member 接受一样的关键字,我们可以用剩余参数收集它们,再传给 member 函数。

5.2 节介绍过 destructuring-bind 宏。在通常情况下,每个模式(pattern)中作为第一个参数的子树,可以与函数的参数列表一样复杂:

[32]> (destructuring-bind ((&key w x) &rest y) '((:w 3) a)

  (list w x y))

(3 NIL (A))

6.4 示例:实用函数 (Example: Utilities)

2.6 节提到过,Lisp 大部分是由 Lisp 函数组成,这些函数与你可以自己定义的函数一样。这是程序语言中一个有用的特色:你不需要改变你的想法来配合语言,因为你可以改变语言来配合你的想法。如果你想要 Common Lisp 有某个特定的函数,自己写一个,而这个函数会成为语言的一部分,就跟内置的 + 或 eql 一样。

有经验的 Lisp 程序员,由上而下(top-down)也由下而上 (bottom-up)地工作。当他们朝着语言撰写程序的同时,也打造了一个更适合他们程序的语言。通过这种方式,语言与程序结合的更好,也更好用。

写来扩展 Lisp 的操作符称为实用函数(utilities)。当你写了更多 Lisp 程序时,会发现你开发了一系列的程序,而在一个项目写过许多的实用函数,下个项目里也会派上用场。

专业的程序员常发现,手边正在写的程序,与过去所写的程序有很大的关联。这就是软件重用让人听起来很吸引人的原因。但重用已经被联想成面向对象程序设计。但软件不需要是面向对象的才能重用 ── 这是很明显的,我们看看程序语言(换言之,编译器),是重用性最高的软件。

要获得可重用软件的方法是,由下而上地写程序,而程序不需要是面向对象的才能够由下而上地写出。实际上,函数式风格相比之下,更适合写出重用软件。想想看 sort 。在 Common Lisp 你几乎不需要自己写排序程序; sort 是如此的快与普遍,以致于它不值得我们烦恼。这才是可重用软件。

图 6.1 实用函数

你可以通过撰写实用函数,在程序里做到同样的事情。图 6.1 挑选了一组实用的函数。前两个 single? 与 append1 函数,放在这的原因是要演示,即便是小程序也很有用。前一个函数 single? ,当实参是只有一个元素的列表时,返回真。

[38]>(single? '(a))

T

而后一个函数 append1 和 cons 很像,但在列表后面新增一个元素,而不是在前面:

[39]> (append1 '(a b c) 'd)

(A B C D)

下个实用函数是 map-int ,接受一个函数与整数 n ,并返回将函数应用至整数 0 到 n-1 的结果的列表。

这在测试的时候非常好用(一个 Lisp 的优点之一是,互动环境让你可以轻松地写出测试)。如果我们只想要一个 0 到 9 的列表,我们可以:

[40]> (map-int #'identity 10)

(0 1 2 3 4 5 6 7 8 9)

然而要是我们想要一个具有 10 个随机数的列表,每个数介于 0 至 99 之间(包含 99),我们可以忽略参数并只要:

[41]> (map-int #'(lambda (x) (random 100))

          10)

(84 93 50 46 36 67 42 91 97 28)

map-int 的定义说明了 Lisp 构造列表的标准做法(idiom)之一。我们创建一个累积器 acc ,初始化是 nil ,并将之后的对象累积起来。当累积完毕时,反转累积器。 [1]

我们在 filter 中看到同样的做法。 filter 接受一个函数与一个列表,将函数应用至列表元素上时,返回所有非 nil 元素:

[42]> (filter #'(lambda (x)

              (and (evenp x) (+ x 10)))

          '(1 2 3 4 5 6 7))

(12 14 16)

另一种思考 filter 的方式是用通用版本的 remove-if 。

图 6.1 的最后一个函数, most ,根据某个评分函数(scoring function),返回列表中最高分的元素。它返回两个值,获胜的元素以及它的分数:

[43]> (most #'length '((a b) (a b c) (a)))

(A B C) ;

3

如果平手的话,返回先驰得点的元素。

注意图 6.1 的最后三个函数,它们全接受函数作为参数。 Lisp 使得将函数作为参数传递变得便捷,而这也是为什么,Lisp 适合由下而上程序设计的原因之一。成功的实用函数必须是通用的,当你可以将细节作为函数参数传递时,要将通用的部份抽象起来就变得容易许多。

本节给出的函数是通用的实用函数。可以用在任何种类的程序。但也可以替特定种类的程序撰写实用函数。确实,当我们谈到宏时,你可以凌驾于 Lisp 之上,写出自己的特定语言,如果你想这么做的话。如果你想要写可重用软件,看起来这是最靠谱的方式。

6.5 闭包 (Closures)

函数可以如表达式的值,或是其它对象那样被返回。以下是接受一个实参,并依其类型返回特定的结合函数:

(defun combiner (x)

  (typecase x

    (number #'+)

    (list #'append)

    (t #'list)))

在这之上,我们可以创建一个通用的结合函数:

(defun combine (&rest args)

  (apply (combiner (car args))

        args))

它接受任何类型的参数,并以适合它们类型的方式结合。(为了简化这个例子,我们假定所有的实参,都有着一样的类型。)

[46]> (combine 2 3)

5

[47]> (combine '(a b) '(c d))

(A B C D)

2.10 小节提过词法变量(lexical variables)只在被定义的上下文内有效。伴随这个限制而来的是,只要那个上下文还有在使用,它们就保证会是有效的。

如果函数在词法变量的作用域里被定义时,函数仍可引用到那个变量,即便函数被作为一个值返回了,返回至词法变量被创建的上下文之外。下面我们创建了一个把实参加上 3 的函数:

[48]> (setf fn (let ((i 3))

            #'(lambda (x) (+ x i))))

#<FUNCTION :LAMBDA (X) (+ X I)>

[49]> (funcall fn 2)

5

当函数引用到外部定义的变量时,这外部定义的变量称为自由变量(free variable)。函数引用到自由的词法变量时,称之为闭包(closure)。 [2] 只要函数还存在,变量就必须一起存在。

闭包结合了函数与环境(environment);无论何时,当一个函数引用到周围词法环境的某个东西时,闭包就被隐式地创建出来了。这悄悄地发生在像是下面这个函数,是一样的概念:

(defun add-to-list (num lst)

  (mapcar #'(lambda (x)

              (+ x num))

          lst))

这函数接受一个数字及列表,并返回一个列表,列表元素是元素与传入数字的和。在 lambda 表达式里的变量 num 是自由的,所以像是这样的情况,我们传递了一个闭包给 mapcar 。

一个更显着的例子会是函数在被调用时,每次都返回不同的闭包。下面这个函数返回一个加法器(adder):

(defun make-adder (n)

  #'(lambda (x)

      (+ x n)))

它接受一个数字,并返回一个将该数字与其参数相加的闭包(函数)。

[59]> (setf add3 (make-adder 3))

#<FUNCTION :LAMBDA (X) (+ X N)>

[60]> (funcall add3 2)

5

[61]> (setf add27 (make-adder 27))

#<FUNCTION :LAMBDA (X) (+ X N)>

[62]> (funcall add27 2)

29

我们可以产生共享变量的数个闭包。下面我们定义共享一个计数器的两个函数:

[65]> (let ((counter 0))

  (defun reset ()

    (setf counter 0))

  (defun stamp ()

    (setf counter (+ counter 1))))

STAMP

这样的一对函数或许可以用来创建时间戳章(time-stamps)。每次我们调用 stamp 时,我们获得一个比之前高的数字,而调用 reset 我们可以将计数器归零:

[66]> (list (stamp) (stamp) (reset) (stamp))

(1 2 0 1)

你可以使用全局计数器来做到同样的事情,但这样子使用计数器,可以保护计数器被非预期的引用。

Common Lisp 有一个内置的函数 complement 函数,接受一个谓词,并返回谓词的补数(complement)。比如:

[67]> (mapcar (complement #'oddp)

          '(1 2 3 4 5 6))

(NIL T NIL T NIL T)

有了闭包以后,很容易就可以写出这样的函数:

(defun our-complement (f)

  #'(lambda (&rest args)

      (not (apply f args))))

如果你停下来好好想想,会发现这是个非凡的小例子;而这仅是冰山一角。闭包是 Lisp 特有的美妙事物之一。闭包开创了一种在别的语言当中,像是不可思议的程序设计方法。

6.6 示例:函数构造器 (Example: Function Builders)

Dylan 是 Common Lisp 与 Scheme 的混合物,有着 Pascal 一般的语法。它有着大量返回函数的函数:除了上一节我们所看过的 complement ,Dylan 包含:compose 、 disjoin 、 conjoin 、 curry 、 rcurry 以及 always 。图 6.2 有这些函数的 Common Lisp 实现,而图 6.3 演示了一些从定义延伸出的等价函数。

图 6.2 Dylan 函数建构器

首先, compose 接受一个或多个函数,并返回一个依序将其参数应用的新函数,即,

(compose #'a #'b #'c)

返回一个函数等同于

#'(lambda (&rest args) (a (b (apply #'c args))))

这代表着 compose 的最后一个实参,可以是任意长度,但其它函数只能接受一个实参。

下面我们建构了一个函数,先给取参数的平方根,取整后再放回列表里,接着返回:

[80]> (mapcar (compose #'list #'round #'sqrt)

          '(4 9 16 25))

((2) (3) (4) (5))

下来的两个函数, disjoin 及 conjoin 同接受一个或多个谓词作为参数: disjoin 当任一谓词返回真时,返回真,而 conjoin 当所有谓词返回真时,返回真。

[81]> (mapcar (disjoin #'integerp #'symbolp)

          '(a "a" 2 3))

(T NIL T T)

[82]> (mapcar (conjoin #'integerp #'symbolp)

          '(a "a" 2 3))

(NIL NIL NIL NIL)

若考虑将谓词定义成集合, disjoin 返回传入参数的联集(union),而 conjoin 则是返回传入参数的交集(intersection)。

图 6.3 某些等价函数

函数 curry 与 rcurry (“right curry”)精神上与前一小节的 make-adder 相同。两者皆接受一个函数及某些参数,并返回一个期望剩余参数的新函数。下列任一个函数等同于 (make-adder 3) :

(curry #'+ 3)

(rcurry #'+ 3)

当函数的参数顺序重要时,很明显可以看出 curry 与 rcurry 的差别。如果我们 curry #'- ,我们得到一个用其参数减去某特定数的函数,

[87]> (funcall (curry #'- 3) 2)

1

而当我们 rcurry #'- 时,我们得到一个用某特定数减去其参数的函数:

[88]> (funcall (rcurry #'- 3) 2)

-1

最后, always 函数是 Common Lisp 函数 constantly 。接受一个参数并原封不动返回此参数的函数。和 identity 一样,在很多需要传入函数参数的情况下很有用。

6.7 动态作用域 (Dynamic Sc​​ope)

2.11 小节解释过局部与全局变量的差别。实际的差别是词法作用域(lexical scope)的词法变量(lexical variable),与动态作用域(dynamic scope)的特别变量(special variable)的区别。但这俩几乎是没有区别,因为局部变量几乎总是是词法变量,而全局变量总是是特别变量。

在词法作用域下,一个符号引用到上下文中符号名字出现的地方。局部变量缺省有着词法作用域。所以如果我们在一个环境里定义一个函数,其中有一个变量叫做x ,

(let ((x 10))

  (defun foo ()

    x))

则无论 foo 被调用时有存在其它的 x ,主体内的 x 都会引用到那个变量:

[90]> (let ((x 20)) (foo))

10

而动态作用域,我们在环境中函数被调用的地方寻找变量。要使一个变量是动态作用域的,我们需要在任何它出现的上下文中声明它是 special 。如果我们这样定义 foo :

(let ((x 10))

  (defun foo ()

    (declare (special x))

    x))

则函数内的 x 就不再引用到函数定义里的那个词法变量,但会引用到函数被调用时,当下所存在的任何特别变量 x :

[93]> (let ((x 20))

    (declare (special x))

    (foo))

20

新的变量被创建出来之后, 一个 declare 调用可以在代码的任何地方出现。 special 声明是独一无二的,因为它可以改变程序的行为。 13 章将讨论其它种类的声明。所有其它的声明,只是给编译器的建议;或许可以使程序运行的更快,但不会改变程序的行为。

通过在顶层调用 setf 来配置全局变量,是隐式地将变量声明为特殊变量:

[94]> (setf x 30)

30

[95]> (setf x 30)

30

在一个文件里的代码,如果你不想依赖隐式的特殊声明,可以使用 defparameter 取代,让程序看起来更简洁。

动态作用域什么时候会派上用场呢?通常用来暂时给某个全局变量赋新值。举例来说,有 11 个变量来控制对象印出的方式,包括了 *print-base* ,缺省是 10 。如果你想要用 16 进制显示数字,你可以重新绑定 *print-base* :

[99]> (let ((*print-base* 16))

    (princ 32))

20

32

这里显示了两件事情,由 princ 产生的输出,以及它所返回的值。他们代表着同样的数字,第一次在被印出时,用 16 进制显示,而第二次,因为在 let 表达式外部,所以是用十进制显示,因为 *print-base* 回到之前的数值, 10 。

6.8 编译 (Compilation)

Common Lisp 函数可以独立被编译或挨个文件编译。如果你只是在顶层输入一个 defun 表达式:

[100]> (defun foo (x) (+ x 1))

FOO

许多实现会创建一个直译的函数(interpreted function)。你可以将函数传给 compiled-function-p 来检查一个函数是否有被编译:

[101]> (compiled-function-p #'foo)

NIL

若你将 foo 函数名传给 compile :

[102]> (compile 'foo)

FOO 

则这个函数会被编译,而直译的定义会被编译出来的取代。编译与直译函数的行为一样,只不过对 compiled-function-p 来说不一样。

你可以把列表作为参数传给 compile 。这种 compile 的用法在 161 页 (译注: 10.1 小节)。

有一种函数你不能作为参数传给 compile :一个像是 stamp 或是 reset 这种,在顶层明确使用词法上下文输入的函数 (即 let ) [3] 在一个文件里面定义这些函数,接着编译然后载入文件是可以的。这么限制直译的代码的是实作的原因,而不是因为在词法上下文里明确定义函数有什么问题。

通常要编译 Lisp 代码不是挨个函数编译,而是使用 compile-file 编译整个文件。这个函数接受一个文件名,并创建一个原始码的编译版本 ── 通常会有同样的名称,但不同的扩展名。当编译过的文件被载入时, compiled-function-p 应给所有定义在文件内的函数返回真。

当一个函数包含在另一个函数内时,包含它的函数会被编译,而且内部的函数也会被编译。所以 make-adder (108 页)被编译时,它会返回编译的函数:

[104]> (compile 'make-adder)

MAKE-ADDER

[105]> (compiled-function-p (make-adder 2))

T

6.9 使用递归 (Using Recursion)

比起多数别的语言,递归在 Lisp 中扮演了一个重要的角色。这主要有三个原因:

1)函数式程序设计。递归演算法有副作用的可能性较低。

2)递归数据结构。 Lisp 隐式地使用了指标,使得递归地定义数据结构变简单了。最常见的是用在列表:一个列表的递归定义,列表为空表,或是一个 cons ,其中 cdr 也是个列表。

3)优雅性。Lisp 程序员非常关心它们的程序是否美丽,而递归演算法通常比迭代演算法来得优雅。

学生们起初会觉得递归很难理解。但 3.9 节指出了,如果你想要知道是否正确,不需要去想递归函数所有的调用过程。

同样的如果你想写一个递归函数。如果你可以描述问题是怎么递归解决的,通常很容易将解法转成代码。要使用递归来解决一个问题,你需要做两件事:

1)你必须要示范如何解决问题的一般情况,通过将问题切分成有限小并更小的子问题。

2)你必须要示范如何通过 ── 有限的步骤,来解决最小的问题 ── 基本用例。

如果这两件事完成了,那问题就解决了。因为递归每次都将问题变得更小,而一个有限的问题终究会被解决的,而最小的问题仅需几个有限的步骤就能解决。

举例来说,下面这个找到一个正规列表(proper list)长度的递归算法,我们每次递归时,都可以找到更小列表的长度:

1)在一般情况下,一个正规列表的长度是它的 cdr 加一。

2)基本用例,空列表长度为 0 。

当这个描述翻译成代码时,先处理基本用例;但公式化递归演算法时,我们通常从一般情况下手。

前述的演算法,明确地描述了一种找到正规列表长度的方法。当你定义一个递归函数时,你必须要确定你在分解问题时,问题实际上越变越小。取得一个正规列表的 cdr 会给出 length 更小的子问题,但取得环状列表(circular list)的 cdr 不会。

这里有两个递归算法的示例。假定参数是有限的。注意第二个示例,我们每次递归时,将问题分成两个更小的问题:

第一个例子, member 函数,我们说某物是列表的成员,需满足:如果它是第一个元素的成员或是 member 的 cdr 的成员。但空列表没有任何成员。

第二个例子, copy-tree 一个 cons 的 copy-tree ,是一个由 cons 的 car 的 copy-tree 与 cdr 的 copy-tree 所组成的。一个原子的 copy-tree 是它自己。

一旦你可以这样描述算法,要写出递归函数只差一步之遥。

某些算法通常是这样表达最自然,而某些算法不是。你可能需要翻回前面,试试不使用递归来定义 our-copy-tree (41 页,译注: 3.8 小节)。另一方面来说,23 页 (译注: 2.13 节) 迭代版本的 show-squares 可能更容易比 24 页的递归版本要容易理解。某些时候是很难看出哪个形式比较自然,直到你试着去写出程序来。

如果你关心效率,有两个你需要考虑的议题。第一,尾递归(tail-recursive),会在 13.2 节讨论。一个好的编译器,使用循环或是尾递归的速度,应该是没有或是区别很小的。然而如果你需要使函数变成尾递归的形式时,或许直接用迭代会更好。

另一个需要铭记在心的议题是,最显而易见的递归算法,不一定是最有效的。经典的例子是费氏函数。它是这样递归地被定义的,

Fib(0) = Fib(1) = 1

Fib(n) = Fib(n-1)+Fib(n-2)

直接翻译这个定义,

(defun fib (n)

  (if (<= n 1)

      1

      (+ (fib (- n 1))

        (fib (- n 2)))))

这样是效率极差的。一次又一次的重复计算。如果你要找 (fib 10) ,这个函数计算 (fib 9) 与 (fib 8) 。但要计算出 (fib 9) ,它需要再次计算 (fib 8),等等。

下面是一个算出同样结果的迭代版本:

(defun fib (n)

  (do ((i n (- i 1))

      (f1 1 (+ f1 f2))

      (f2 1 f1))

      ((<= i 1) f1)))

迭代的版本不如递归版本来得直观,但是效率远远高出许多。这样的事情在实践中常发生吗?非常少 ── 这也是为什么所有的教科书都使用一样的例子 ── 但这是需要注意的事

Chapter 6 总结 (Summary)

1)命名函数是一个存在符号的 symbol-function 部分的函数。 defun 宏隐藏了这样的细节。它也允许你定义文档字符串(documentation string),并指定setf 要怎么处理函数调用。

2)定义局部函数是有可能的,与定义局部变量有相似的精神。

3)函数可以有选择性参数(optional)、剩余(rest)以及关键字(keyword)参数。

4)实用函数是 Lisp 的扩展。他们是由下而上编程的小规模示例。

5)只要有某物引用到词法变量时,它们会一直存在。闭包是引用到自由变量的函数。你可以写出返回闭包的函数。

6)Dylan 提供了构造函数的函数。很简单就可以使用闭包,然后在 Common Lisp 中实现它们。

7)特别变量(special variable)有动态作用域 (dynamic scope)。

8)Lisp 函数可以单独编译,或(更常见)编译整个文件。

9)一个递归演算法通过将问题细分成更小丶更小的子问题来解决问题。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 205,132评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,802评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,566评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,858评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,867评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,695评论 1 282
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,064评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,705评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 42,915评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,677评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,796评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,432评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,041评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,992评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,223评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,185评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,535评论 2 343

推荐阅读更多精彩内容