[Back]

Chapter 1

1.1 基本元素

心智的认识,主要体现在组合、联系和抽象三个方面,这是洛克在500年前就已经提出的认知论,我们学习程序设计,也不外乎如此。

程序构建了计算过程的规则,而计算过程负责操作数据,这就像利用咒语控制精灵似的。 Lisp最初的目的,是为了对递归方程的使用作推理。它和当时的语言革命性一点的不同,是引入了原子和表的概念。 Lisp极为强大的一点是,它将计算的过程,也当作了一种数据来对待。

DEF.1 程序设计的基本元素

  • 基本表达形式
  • 组合方法
  • 抽象方法
  • DEF.2 组合式 将多个表达式作用于过程的表达形式,叫做组合式(表),这被称为过程应用。

    DEF.3 运算对象和运算符、实际参数 一个组合式最左的称为运算符,其余的为运算对象,要获得组合式的值,就需要应用过程到实际参数,也就是运算对象的值。

    DEF.4 变量 绑定名字和计算对象的行为,是最简单的抽象方式,其中,名字标识符被称为变量,而计算对象则是变量的值。 例如:(define x 3)

    DEF.5 环境 维持名字-值的对偶关系的存储被称为环境(全局环境)。

    DEF.6 一般性求值规则 1. 求值该组合式的各个子表达式 2. 将最左子表达式的值的过程应用于实际参数,即其他子表达式的值。

    DEF.6.1 树形积累 在树状结构中,应用递归方法进行“值向上穿行”的求值计算过程被称为树形积累。

    DEF.7 过程定义 一般形式: (define (<name> <formal parameters>) <body>) 一般地说,我们将实际参数在作用时按照语法顺序绑定给形式参数,并对之后的表达式求值,将这一个过程绑定给一个变量(符号),存储在环境中调用。其中,形式参数起到了自然语言中代词的作用。 过程体可以是多个表达式,并返回最后一个表达式的值。

    DEF.8 代换模型 将复合过程应用于实际参数,就是将过程体中的每个形参用相应的实参取代之后,对这一过程体求值。

    DEF.8.1 正则序与应用序 “完全展开后规约”的求值模型被称为正则序求值,而“先求值参数而后应用”的方式称为应用序求值。

    DEF.9 谓词和条件表达式 形式:

    (cond (<p1> <e1>)
              (<p2> <e2>)
                   …
              (<pn> <en>))
    

    cond之后跟随众多子句,子句以谓词开头,cond的值是第一个真子句。

    else是一个永远为真的谓词

    形式: (if <predicate> <consequent> <alternative>)

    DEF.10 过程抽象 在一个过程抽象中,每一个子过程都是一件清楚表明的工作,这被称为工程黑盒,代表了原问题向子问题的分解。

    DEF.11 局部名称 过程的形式参数只是一个局部名称,我们说,一个过程约束了它的形式参数。

    DEF.11.1 自由变量与作用域 我们将不被约束的变量称为自由变量。 我们将一个变量的符号被约束的最大范围称为变量的作用域。

    DEF.12 块结构 我们可以在过程中嵌套定义过程作为局部过程来使用,这种局部过程被称为块结构。

    DEF.12.1 词法作用域 在某一过程中的自由变量,实际上是在引用外围定义过程中的约束,这种方式被称为词法作用域,来源于Algol 60。

     

    1.2 过程与产生它们的计算

    Think:过程究竟是什么?是一种描述,还是一种数据,还是一种抽象。或者说,其实这些要素在过程之上是不冲突的? 在这一章所要学习的,是如何在全局的角度判断一个过程的演化方式。

    DEF.13 线性递归与线性迭代 计算时需要保存运算轨迹,呈现出一条推迟进行的轨迹时,被称为递归计算过程。 需要保存的信息量与n呈线性的时候,被称为线性递归。 对立的,我们以步骤执行直接达到计算结果的过程,被称为迭代计算过程。 迭代过程一般是可以用具体数量的状态变量来描述计算过程,同时又有一套更新规则和结束条件,线性增长的计算步骤时,被称为线性迭代过程。

    迭代在每一个状态,都保留了该计算的完整信息,而递归则不是这样。

    DEF.14 过程与计算过程 实际上我们知道在Lisp中,任何的过程都是递归的,这是个语法上的概念,意指一个过程直接或间接的引用了过程本身。而计算过程,则是在分析后实际的进展方式。

    DEF.15 尾递归 一切循环结构,不过是迭代的语法糖衣,尾递归的本质是计算的”消息传递“模型,这是Scheme能够将递归过程解释成迭代计算过程的坚实基础。

    DEF.16 树形递归 在递归中多次调用自身,导致递归过程呈现一棵树的形状,这样的过程往往是冗余的,但是容易理解。

    有一种理想的灵巧编译器,能够使机器自动将一个树形递归的过程变为迭代的过程。 一种解决冗余计算的方法是使得计算过程能自动构造出一个已经计算出的表格,这种技术被称为表格技术或记忆技术。

    DEF.17 增长阶 我们称R(n)为一个计算过程中在处理规模为n的问题时的资源量。 当满足

    我们称 拥有 的增长阶,即为 这是一个十分粗略的估计,但他给了我们一个分析所需的计算资源的一个初步的工具。

    在设计迭代算法的时候,定义一个不变量,依据这个不变量来设计状态转移,是一个强有力的方法。

    DEF.18 Lame定理 设欧几里得算法需要k步,则数对中任一数必不小于Fibonacci(k)。

    DEF.19 Fermat小定理 如果p是素数,则对于任意a不是p的倍数,都有:

    DEF.20 Fermat检查 选取足够多的数a来运算待检测数p是否满足Fermat小定理,这样可以将这个数p的素数概率逐步加大,这样的检测素数方法叫做Fermat检查。

     

    1.3 用高阶函数做抽象

    DEF.21 高阶过程 只需将过程翻译成形式参数,我们就能够利用过程来计算过程,这样的过程被称为高阶过程

    DEF.22 匿名函数 使用(lambda (parameter) (body))来定义匿名函数,它和define一样制造过程,但是区别是匿名函数并不指定过程名称。

    DEF.23 匿名变量 应用匿名函数来约束局部变量是一个很有效的方法。因此,我们产生了一种简化语法为let

    (let ((<name> <exp>)
            (<name> <exp>)
            ……)
           <body>)
    

    注意:变量的值是在变量外部求值的。

    DEF.24 不动点和映射 我们将满足 的点x称为函数f的不动点,本质上讲,求解平方根也是一个寻找不动点的过程。 我们将x↦f(x)称为x到f(x)的一个映射,这是一种记述lambda函数的方法。

    DEF.25 第一级 在一门程序设计语言中,带有最少使用限制的元素被称为第一级元素。它们拥有以下特征: • 可以用变量命名 • 可以作为参数传递 • 可以被当作返回值 • 可以包括在数据结构中 Lisp中,函数,也就是过程是第一级元素。