北京大学 -- 程序设计技术和方法 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 语言(和其他常规语言)的基本结构单元是 语句 ,表达式只是语句的组成部分,不能独立存在