How to Design Programs -- I.Fixed-Size Data

程序即数据、数据即程序

How to Design Programs
一书聚焦于 GUI 与 批处理 程序

I.Fixed-Size Data

1
2
3
4
5
6
7
8
9
10
11
12
13
lang racket

; factorial function
(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))
)
)

; output 5!
(displayln (factorial 5))

原始表达式( Lisp 中使用 前缀表达式 定义运算规则 )

1
(+ 1 1)

即,自然语言中的 1 + 1 计算


Arithmetic 算术

numbers 数字

以下列出常用的运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(add1 9) ; 9 + 1
(expt 2 10) ; 2^10
(ceiling 1.2) ; [1.2] = 2.0
(exact->inexact 1.999) ; 转换为精确数
(floor 1.9) ; floor(1.9) = 1.0
(gcd 2 4 8) ; 最大公约数
(log x a) ; log_a(x)
(numerator 3/13) ; 提取分子
(quotient 7 3) ; 7 / 2 得出商
(random-seed 69) ; 设置随机种子
(random 10) ; 范围随机 [0, 10)
(remainder 7 2) ; 取余
(sqr 3) ; 平方 x^2
(sqrt 9) ; 平方根 x^(1/2)

pi ; 即圆周率pi
(exp x) ; 自然对数 x * e

使用以下方法进行 数据定义

1
(define x 1)

使用以下方法进行 函数定义

  • 以 距离公式 为例
1
2
3
4
(define (length x y)
(sqrt
(+ (sqr x) (sqr y)))
)

string 字符串

racket中提供了标准函数

1
2
3
4
5
6
7
8
9
10
11
(+ (string-length "Hello World!") 10)
==
(+ 12 10)
==

(+ (string-length (number->string 42)) 10)
==
(+ (string-length "42") 10)
==
(+ 2 10)
==

用字符串原语创建一个表达式,在位置 i 加 “_”。这里期望的结果是 “hello_world”。

我们设计了一个函数,传入原字符串,插入索引,插入字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define str "helloworld")
(define i 5)

; 定义
(define (insert_c_into_str_at_idx str idx c)
(string-append
(substring str 0 idx)
c
(substring str idx (string-length str))
)
)

; 调用
(insert_c_into_str_at_idx str i "_")

images 图像

使用以下方法导入包

1
(require 2htdp/image)

图像操作有三种原语:

  1. 创建基本图像

    • ellipse 椭圆
    • line 直线
    • reactangle 矩形
    • text 文本
    • triangle 三角形
  2. 图像的属性

    image-

    • image-width 提取图像宽度
    • image-height 提取图像高度
  3. 锚点 anchor point

    图像的其中一个像素作为隐式锚点,在使用图像原语合成两张图片时,合成是针对锚点进行的
    overlay/

    • overlay 叠加 将所有被应用的图像进行叠加,中心作为锚点
    • overlay/xy 叠加/xy 将第二个传入的图形移动(+x, +y)
    • overlay/align 叠加/对齐 通过传入对齐位置(两个字符串标识),控制一长串图形的对齐生成

Boolean 布尔值

racket提供的布尔值,以及布尔运算规则

1
2
3
4
5
6
7
8
9
10
11
12
; 布尔值
true
false

; 布尔运算规则
not
or nor
and nand
xor

(define (xnor b1 b2)
((not (xor b1 b2))))
  • 非
  • 或 或非
  • 与 与非
  • 异或
  • 同或(xnor 需要用户实现)

数字电路模拟

由此可以实现 半加器、全加器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
; 半加器
(define (bit-half-adder a b)
(values (and a b) (xor a b))
)

; 全加器
(define (bit-full-adder c0 a b)
(values
(or (and a b) (and (xor a b) c0))
(xor (xor a b) c0)))
|
(let-values ([
(c s)
(bit-half-adder true #true)])
(list c s))

(let-values
([(c1 s) (bit-full-adder t #t #t)])
(list c1 s))
|

逻辑演算

如果今天小明去了学校,那么我也在学校

1
2
3
4
5
6
7
(define P f) ; 小明没去学校
(define Q t) ; 假设 我去了学校

; 计算蕴涵式
(define implication (or (not P) Q))

(printf "P: ~a, Q: ~a, P->Q: ~a~n" P Q implication)

Mixing It Up with Boolean 混合布尔值

racket提供了包含以下比较原语

  • =
  • >
  • <
  • =>
  • <=
  • string=?
  • string>?
  • string<?
  • string>=?
  • string<=?

条件表达式

if语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
; 数值
(if (> 1 2)
(printf "Hello World~n")
(printf "Good Bye World~n")
)

(define catch
(if (< 1 2)
t
f
)
)
(printf "~a~n" catch)

; 字符串
(define cur-color "green")
(define truth
(if (string=? cur-color "red")
t
f
)
)
(printf "~a~n" truth)

when

当 表达式 时
执行所有内部语句(隐含 begin)

1
2
3
4
(when (> 1 0)
(display "Hello World!\n")
(display "Line 1\n")
(display "line 2\n"))

unless

除 表达式 之外
执行所有内部语句(隐含 begin)

1
2
3
4
(unless (< 1 0)
(display "unless line\n")
(display "line 3\n")
(display "line 4\n"))

条件分支语句

case

使用 eqv? 进行匹配
基于 符号 常量 进行匹配
无穿透,不支持范围判断,但允许多个标签并列(多点)

1
2
3
4
(case 2
[(0) (printf "zero\n")]
[(1 2) (printf "one two\n")]
[(3) (printf "three\n")])

cond

自上而下进行判断,无穿透
支持表达式,更像是 if 链
使用 else 作为可选的默认表达

1
2
3
4
5
6
7
8
(define (grade score)
(cond
[(>= score 90) (printf "case A\n")]
[(>= score 80) (printf "case B\n")]
[(>= score 70) (printf "case C\n")]
[else (printf "case else\n")]))

(grade 60)

match

更强大的匹配工具
可以解构数据、匹配字符串、复合结构等

1
2
3
4
5
6
7
(define (describe x)
(match x
[0 (printf "zero\n")]
[(? string? s) (string-append "string: " s)]
[(list a b) (printf "list, [0]: ~a, [1]: ~a\n" a b)]
[_ (printf "other")]))
(describe 0)

Predicates 谓词

谓词是一个函数,用于消耗一个值并判断该值是否属于某类数据
通过返回的Boolean值,控制程序流向,对控制流进行抽象

在 Lisp 家族中,一个谓词就是任何返回 t 或 #f 的函数。
按惯例,谓词名通常以 ? 结尾(如 null?、even?),或者就是逻辑运算符本身(=, >, and, or)。

如:

1
2
3
4
5
(number? 1)
(number? t)
(boolean? f)
(number? "Hello")
(string? "World")

以上调用的返回值是 Boolean 类型

可以使用于以下情况

1
2
3
4
(define input 42)
(if (string? input)
(* (+ (string-length input) 1) pi)
(printf "ERROR: INVALID INPUT TYPE~n"))

在通过 struct 自定义一个结构体时,自动产生 (<struct-name>?) 谓词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(struct Person
(
name
age
print-info
)
)
(define (Person::print-info p)
(printf
"Person:
name:~a
age:~a~n"
(Person-name p) (Person-age p)))

(define (make-Person name age)
(Person
name age
Person::print-info))

(define p (make-Person "Volador" 99))

(if (Person? p)
((Person-print-info p) p)
(printf "ERROR: INPUT IS NOT PERSON~n"))

注意 (rational? pi) 的结果是 t


Functions and Programs 函数与程序

Functions 函数

函数定义与调用

1
2
3
4
5
6
; 定义函数
(define (func <args>)
(printf "call a func~n"))

; 调用函数
(func <args>)

可变参数函数

1
2
3
4
5
6
7
8
9
10
11
; 定义可变参数函数

; 有固定参数时
(define (func a b c . args)
(apply + a b c args))

; 无固定参数时
(define (func . args)
(<func-body>))

(func <args>)

注意, apply 函数是处理可变参数的函数,其最后一个参数一定是 可变参数
或者是列表类型 (list args)
apply 针对可变参数进行原位展开
(apply + `(1 2 3 4)) => (+ 1 2 3 4)

lambda函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
; 定义lambda函数
(define func
(lambda (<args>)
(func-body)))

(func <args>)

; 匿名定义与调用
(define func
(lambda (<args>)
(func-body))
<args>)

; 匿名函数的可变参数
; 有固定参数
(define func
(lambda (a . args)
(func-body))
<args>)

; 无固定参数
(define func
(lambda parameter
(apply + parameter))
<args>)

case-lambda 按参数个数分派

在racket中 [] 与 () 同级,可以进行视觉上的区分,增加程序的可读性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(define flexible
(case-lambda
([x] (<single-arg-func-body>))
([x y] (<double-arg-func-body>))
([x y . z] (<parameter-func-body>))
))

(flexible 1)
(flexible 1 2)
(flexible 1 2 3 4 5)

((case-lambda
[(x) (printf "~a\n" x)]
[(x y) (printf "~a ~a\n" x y)]
[(x y . z) (printf "~a ~a ~a\n" x y z)])
1 2 3 4 5)
  • 每个 (参数) (函数体) 对,使用 [] 包裹
  • 本质上仍是使用 lambda函数

关键字参数

1
2
3
4
5
6
7
8
9
10
11
(define (person-greet-act #:name [n "default"] #:greeting [g "Hello"] #:endl [e "\n"])
(printf"~a: ~a~a" n g e))

(person-greet-act #:name "volador")
(person-greet-act #:greeting "Hello World!" #:name "programmer")

; 可变参数模板混合
(define (para-sp x #:y [yy "y"] . sp)
(list x yy sp))

(para-sp 1 #:y 2 3 4)

使用 #:<key-arg> 定义关键字

关键字参数可以在调用时乱序指定

也可以与可变参数结合使用


Composing Functions 合成函数

一个完整的程序,一般都是由许多函数组合而成的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
(define (letter first-name last-name signature-name)
(string-append
(opening first-name)
"\n\n"
(body first-name last-name)
"\n\n"
(closing signature-name)))

(define (opening first-name)
(string-append "Dear " first-name ","))

(define (body first-name last-name)
(string-append
"We have discovered that all people with the" "\n"
"last name " last-name " have won our lottery. So" "\n"
first-name ", " "hurry and pick up your prize."))

(define (closing signature-name)
(string-append
"Sincerely,"
"\n\n"
signature-name
"\n"))

(letter "A" "B" "C")

为每一个任务定义一个函数
使每个函数都相对较小,易于理解


Global Constants 全局常量

常使用大写字母标识常量

1
(define CONST-INT 5)

对于问题陈述中提到的每个常数,引入一个常数定义


Programs 程序

  • 批处理程序

    • 批处理程序 一次性消耗所有输入 并计算结果。
    • 其主要功能是辅助功能的合成,辅助功能可能指代额外的辅助功能,依此类推。
    • 当我们启动批处理程序时,操作系统会调用其输入的主函数,并等待程序的输出。
  • 交互式程序

    • 交互程序 消耗部分输入 ,计算,产生部分输出,消耗更多输入,依此类推。
    • 当输入出现时,我们会谈论 事件 ,并创建交互式程序作为事件驱动程序。
    • 此类事件驱动程序的主要功能使用表达式来描述应调用哪些函数以应对哪些类型的事件。
      • 这些应对特定事件的函数称为事件处理程序。

Batch Programs 批处理程序

  • read-file 函数 将整个文件读取为字符串
  • write-file 函数 从给定字符串创建文件

与 C 语言中的 stdout stdin 相联系的是:

1
2
read-file('stdin) ; 从标准输入中读取内容 在读取时,使用 ctrl+D 传入完成信号
write-file('stdout <string>) ; 将字符串写入标准输出

Interactive Programs 交互式程序

2htdp/universe
设计遵循了 事件驱动编程 与 函数式编程

设计交互式程序需要指定某个函数处理键盘事件,另一个处理时钟函数,第三个函数以图像形式呈现数据

1
2
3
4
5
6
(define (number->square s)
(square s "solid" "red"))
(big-bang 100
[to-draw number->square]
[on-tick sub1]
[stop-when zero?])

以上程序建立一个 100*100 窗口,内部的正方形虽时间刻度 -1 ,当减为0后停止

1
2
3
4
5
6
(big-bang <初始世界>
[to-draw <渲染函数>] ; 世界 -> Image
[on-tick <时钟处理函数>] ; 世界 -> 新世界
[on-key <键盘处理函数>] ; 世界 按键 -> 新世界
[on-mouse <鼠标处理函数>] ; 世界 坐标 事件 -> 新世界
[stop-when <停止条件>]) ; 世界 -> Boolean
  • 世界最初是什么样子(初始状态,可以是一个数、字符串、结构体等)
  • 世界如何随时间变化(on-tick,每秒调用若干次)
  • 世界如何响应用户输入(on-key, on-mouse)
  • 世界如何显示在屏幕上(to-draw,把状态变成图像)
  • 何时停止(stop-when,返回 #t 时结束)

参考以下例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(define (number->square size)
(square size "solid" "red"))

(define SQUARE-SIZE 720)

(define (reset s key)
(match key
["escape" 0]
["/" (/ s 2)]
["*" (* s 2)]
["shift" s]
[_ SQUARE-SIZE]))

(big-bang SQUARE-SIZE
[to-draw number->square]
[on-tick sub1]
[on-key reset]
[stop-when zero?])
  • big-bang 会每tick进行状态更新
  • on-key 在每次big-bang时进行键盘事件的接收
  • on-mouse big-bang状态,接收mouse的(x,y)
  • 多事件同时发生,按排序处理

cw: current world
e: event

current state cw_0 cw_1 …
event e_0 e_1 e_{…}
on clock tick (tock cw_0) (tock cw_1) …
on keystroke (ke-h cw_0 e_0) (ke-h cw_1 e_1) …
on mouse (me-h cw_0 e_0) (me-h cw_1 e_1) …
event …) …) …)
its image (render cw_0) (render cw_1) …
  • 所有的操作都是围绕着 当前状态 进行的,他们接收旧状态并返回新状态, 绝不修改旧状态
  • 事件驱动:世界产生变换(cw_{n} -> cw_{n+1})的 唯一原因 是某个事件处理函数被调用并返回了一个不同值
  • 快照排序:若将以上表格横向展开,可以得到在时间尺度上,由于事件的产生,而激发的各个世界状态,并且,每个状态都是由前一个状态在事件发生后变化而来的
    • 各个注册事件自上而下激发,程序运行时间自左到右更新为新世界
    • 最后渲染当前状态为图像

How To Design Programs 如何设计程序

Designing Functions 设计函数

信息与数据 程序的目的是描述一个计算过程,消耗部分信息并产生新信息。
为处理现实问题,程序需要将其转化为某种形式的编程语言中的数据;处理数据;将数据转化为信息。
模型-视图-控制器 (MVC) 描述 (设计信息-数据转换-) 数据处理-解析信息-数据转化为信息 的逻辑过程

设计流程

  1. 如何将信息表示数据
1
; 使用 *类型 描述 *信息
  1. 写下相关函数的头部、签名与目的陈述
    • 让调用者只需要理解该函数如何运算,而非阅读实现细节
1
2
3
4
; Number -> String
(define (temp-to-string num) string)
; Number String Image -> Image
(define (make-image num str img) img)
  1. 用实用例子说明签名和目的陈述。给出 输入->期望的输出 对。
1
2
3
4
5
; 通过正方形变长计算正方形面积
; Number -> Number
; given: 2 -> expect: 4
; given: 3 -> expect: 9
(define (area-of-square alen) number)
  1. 盘点,了解这些问题的既有条件,包括需要计算的内容
  2. 编程实现
  3. 测试程序

Domain Knowledge 领域知识

在编写程序时(功能函数)需要对待解决问题的相关领域有一定认识
领域知识来自以下两方面

  1. 外部领域: 数学、音乐、生物学、艺术,等。需要理解多个领域的知识,并与相关领域的专家讨论,常常需要学习相应领域的语言。
  2. 所选的编程语言: 理解该编程语言本身,如何使用该语言的生态对各个外部领域的信息进行翻译,模拟。

From Function To Program 从函数到程序

在编写较大规模的程序时,尽量明确一份功能清单,以规划开发任务
包括 设计函数、函数间的关系,等描述性、定义性设计信息。
并在开发中不断完善。


On Testing 关于测试

弄清所用语言的单元测试框架

  • 编写自动化的测试任务
  • 检查测试中的预期值,并根据错误信息修正函数实现

Intervals, Enumerations, and Itemization 区间、枚举与列举

Finite State Worlds 有限状态世界

有限状态机(FSM)/有限状态自动机(FSA)
为可能的世界状态设计状态转移过程


Adding Structure 添加结构

Defining Structure Types 结构类型的定义

使用 `(define-struct [ …])

1
(define-struct 3d-pos [x y z])

在结构定义的同时,定义了以下三种类型的函数(可将以下函数视作为内置原语使用):

  • 构造函数
    • make-<struct-name>
  • 字段选择器
    • <struct-name>-<field-name>
    • …
  • 结构谓词
    • <struct-name>?