北京大学 -- 程序设计技术和方法 notes(1)
Table of Contents

北京大学 裘宗燕 老师的课程

http://www.math.pku.edu.cn/teachers/qiuzy/progtech/

序

命令式和函数式计算

程序设计的主流是命令式 (imperative) 程序设计，计算基于一组基本操 作，在一个环境里进行。操作效果是改变环境的状态，体现在所创建和 修改的状态中:

初始状态 -> ... -> 中间状态 -> ... -> 结束状态

函数式 (functional) 程序设计中计算过程被看成是数据的变换，程序的 行为就是对数据的一系列变换:

数据 -> ... -> 数据 -> ... -> 数据

(常规)程序以命令方式描述计算：

函数式程序设计层次较高：

在编程中命令式思维和函数式思维都有价值：

程序的工作常可分解为一些阶段：

Lisp 是函数式语言之祖

LISP语言(LISP，List Processing的缩写)是一种早期开发的、具有重大意义的表处理语言。它适用于符号处理、自动推理、硬件描述和超大规模集成电路设计等。特点是，使用表结构来表达非数值计算问题，实现技术简单。LISP语言已成为最有影响，使用十分广泛的人工智能语言。

关于 Scheme

学习函数式程序设计(包括 Lisp 类语言程序设计)，有助于掌握如何在较高抽象层次上思考计算问题和程序问题

构造过程抽象 (1)

Scheme 语言介绍

Scheme 是交互式语言，其解释器运行时反复执行一个“读入-求值-打印 循环”(Read-Evaluate-Print Loop，REPL)。每次循环:

Scheme 编程就是构造各种表达式(是一种“表达式语言”)

Scheme 语言由三类(三个层次的)编程机制组成:

区分“过程”(操作)和“数据”，本章主要研究过程的构造。

和 C 语言的对比：

scheme 中的表达式

一些简单的 Scheme 表达式举例

数字是基本表达式：

> 235
235

简单的算术表达式：

> (+ 123 456)
579
> (+ 1.2 3)
4.2

表达式的形式：带括号的前缀形式。

有些运算符允许多个参数，如连加：

> (+ 1 2 3 4)
10

表达式可以任意嵌套：

> (+ 1 (* 2 3))
7

可以写任意复杂的表达式(组合式)，如：

> (+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))

复杂表达式难写难读。采用适当格式有利于正确书写和阅读:

(+
  (* 3
     (+ (* 2 4) (+ 3 5)))
  (+ (- 10 7)
     6))

scheme 中命名和环境

编程语言必须提供为对象命名的机制，这是最基本的抽象机制。

用 define 为对象值命名(给名字关联一个值)：

> (define size 10)
> size
10
> (* size 3)
30

可以用任意复杂的表达式描述要求关联于变量的值：

> (define num (* size 30))
> num
300

计算对象的结构可能很复杂，需要通过复杂费时的计算才能得到，给计算得到的结果命名，可以很方便地多次使用。

复杂程序通常就是为了计算(构造)出很不容易得到的对象：

构造的值可以存入变量供以后使用，说明 Scheme 解释器有存储能力。 这种存储称为“环境”：

组合表达式求值：

求值规则有例外。如 (define x 1) 里的 x 不应该求值，是要求为名字 x 关联一个新值。说明 define 有特殊求值规则：

scheme 中的过程定义

表达式可能变得很长，编程中经常出现重复或类似的表达式：

求平方过程的定义:

(define (square x) (* x x))

包括：过程名，形式参数，做什么(如何求值) 求值这种定义表达式，将相应计算过程关联于名字(这里的square)

定义好的过程就像基本操作，可以通过名字使用：

> (square 2)
4
> (square (* (+ 1 1) 4))
64

可以用过程名来定义新的过程（复合过程）：

(define (sum_of_squares x y)
    (+ (square x) (square y)))
> (sum_of_squares 3 4)
25

预定义基本过程(操作)和特殊形式是构造程序的基本构件：

过程应用的代换模型（简化模型）

组合式和复合过程确定的计算过程是(代换模型):

  1. 求出各参数表达式(子表达式)的值
  2. 找到要调用的过程的定义(根据第一个子表达式的求值结果)
  3. 用求出的实际参数代换过程体里的形式参数
  4. 求值过程体

代换模型给出了过程定义和过程应用的一种语义：

代换模型只是为了帮助直观理解过程应用的行为：

应用序和正则序求值

解释器先求值子表达式(运算符和各运算对象)，而后把得到的运算应 用于运算对象(实际参数)。这种“先求值参数后应用运算符”的顺序称为应用序：

另一方式是先不求值运算对象，推迟到需要时再求值。这种“完全展开之后归约”的顺序称为正则序。

scheme 使用应用序求值

条件表达式和谓词

复杂计算的描述中总需要描述条件和选择。

求绝对值的过程：

(define (abs x)
    (cond ((> x 0) x)
          ((= x 0) 0)
          ((< x 0) (- x))))

scheme 中条件表达式的一般形式：

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

依次求值各个 p(条件)，遇到第一个非false的条件后求值对应的 e，以其值作为整个cond 表达式的值

简化上面的 abs 过程：

(define (abs x)
    (cond ((< x 0) (- x))
          (else x)))

else 表示永远成立的条件，只应该放在最后。

使用 if 的条件表达式形式：

(if <predicate> <consequent> <alternative>)

cond 和 if 都是特殊形式，有特殊的求值规则

逻辑组合运算符 and 和 or 也是特殊形式，采用特殊求值方式：

(and <e1> <e2> ... <en>)

and求值规则：逐个求值 e，直到某个 e 求出假，或最后一个 e 求值完成。以最后求值的那个子表达式的值作为值。

(or <e1> <e2> ... <en>)

or： 逐个求值 e，直到某个 e 求出真，或最后一个 e 求值完成。以最后求值的那个子表达式的值作为值

(not <e>)

not：如果 e 的值不是真，就得真，否则得假。

求出真假值的过程称为谓词。各种关系运算符是基本谓词，可以用 and、or、not 组合出各种复杂逻辑条件，可以用过程定义谓词。

过程必须是有效的计算

过程很像数学函数，但它必须要描述一种有效的计算方法。

什么是有效的计算？

看一个例子：

如果按照平方根的数学定义

sqrt(x) is the y that y >= 0 and y*y = x

(define (sqrt x)
    (the y (and (>= y 0)
                (= x (* y y)))))

这个过程定义是没有意义的。

我们可以用牛顿法来求平方根：

; 注意括号不能乱加，比如下面返回 guess 不能写成 (guess)，加括号的要是 applicable 的才行
(define (sqrt_iter guess x)
    (if (good_enough guess x)
        guess
        (sqrt_iter (improve guess x) x)))

(define (good_enough guess x)
    (< (abs (- (* guess guess) x)) 0.001))

(define (improve guess x)
    (average guess (/ x guess)))

(define (sqrt x) (sqrt_iter 1.0 x))

Scheme 过程构造同 C 语言的对比

scheme 基于表达式，其中的每种结构都是表达式：

C 语言(和其他常规语言)的基本结构单元是 语句 ，表达式只是语句的组成部分，不能独立存在