如何设计程序

Base

基本程序设计步骤

六个基本的程序设计步骤
- 问题分析和数据定义
- 合约,用途说明与结果的描述,函数头部
- 例子
- 函数模板
- 函数定义
- 测试

六个步骤产生定义明确的中间结果
- 问题数据类型描述
- 程序行为的非形式描述
- 说明程序行为的例子
- 开发程序的模板或视图
- 把模板转换成完整的定义
- 通过测试发现错误

要正确的设计程序需要做到
- 分析通常使用文字表述的问题
- 在抽象表达问题实质的同时使用例子进行说明
- 用精确的语言阐明所表述的语句和注释
- 通过检查,测试对上述活动进行评价和修改
- 关注细节

简单数据的处理

学生,教师和计算机

程序只是计算速度非常快的学生,不过程序并不能理解自然语言,所以我们需要学会一门计算机语言将自然语言翻译给计算机.但程序设计需要耐心和专心,保能关注每个微小的细节,并严格规划和对规划忠诚,才能避免错误.

数,表达式和简单程序

数和算术运算

讲述了数和Scheme的一些基本知识

变量和程序

字处理问题

错误

设计程序
- 设计程序至少需要如下4个步骤
  1. 理解程序的目的程序设计的目标是创建一个接收输入并产生结果的机制.因此在开发程序时应该给每一个程序一个有意义的名字,并且说明输入数据和所产生的数据的类型,这称为程序的合约.
  2. 构造并标注例子构造一个例子,并将其写入注释
  3. 程序体写出程序
  4. 测试检查程序计算所得的结果与预期数值是否相符.
  设计诀窍并不能解决程序设计过程中所遇到的所有问题,它提供的是完成程序设计过程中不可避免的步骤的指导.
  - 领域知识
    
    阐明程序体通常需要与问题相关的知识,这种形式的知识称为领域知识.它可能来自简单或复杂的数学,或来自非数学学科.

程序就是函数加上变量定义

函数的复合

辅助函数原则: 对问题表述中所提到的或在进行实例计算中所发现的每种依赖关系都使用一个辅助函数进行明确表达.

变量定义

如果一个数值在程序中多次出现,应该使用变量定义给它一个名字.变量定义将一个名字与一个值相关联.

条件表达式和函数

布尔类型和关系

复合条件: and or not

函数和测试条件

条件和条件函数

cond表达式

条件函数的设计
1. 数据分析和定义了解问题表述所涉及的不同情况
2. 主体-问题主体包含的cond表达式的数目应该与不同情况的数目一样.
3. 主体-答案最后要确定对于每一个cond子句,函数应产生什么结果.
4. 简化检查表达式是否可以被简化.

非数值信息

(symbol=? 'oneSymbol 'anotherSymbol)
;; 这个函数会返回两个参数是否相等.

关于字符串

字符串是第2种形式的符号数据.和符号(symbol)一样,字符串是一个字符序列,但被包含在双引号中. 字符串是复合数据.可以使用"string=?“对两个字符串进行比较.
```
(string=? "oneString" "anotherString")
```

关于图像

图像(image)是第3种形式的符号数据.图像本身并没有固有的含义,但我们往往趋向于将其和相关的信息联系在一起.

复合数据之一,结构体

scheme提供了多种不同的数据组合方法.本节讨论结构体,结构体将固定数目的值组合为单一数据.

结构体定义

drScheme允许程序设计者定义自己的结构体,用以表示属性数目固定的任何类型的对象. 通常结构体包含构造器和选择器.而构造器的前缀通常为"make-",选择器的后缀为字段名.
```
> (define-struct entry (name zip phone))
> (make-entry 'Stone 110101 '13366331320)
(make-entry 'Stone 110101 13366331320)
> (entry-name (make-entry 'Stone 110101 '13366331320))
'Stone
```

数据定义

数据定义是程序设计者和用户间的界面.

设计处理复合数据的函数

数据分析和设计在开始函数设计之前,先必须了解如何在程序设计语言中表示问题的信息. 通常使用Scheme的原子数据(数,符号和图像等)来表示信息,如果发现一个对象有N个属性,可以引入一个有N个字段的结构体,同时给出每个字段的数据定义.
合约为了阐述合约,可以使用诸如数和符号等原子类型的数据.
模板一个读入复合数据的函数在计算中一般会使用到输入数据的组成成分.
例子
主体
测试

阶段	目标	活动
数据分析和设计	阐明数据定义	确定在问题表述中所涉及的对象的数据种类, 对于每类数据增加结构定义和数据定义
合约,用途说明和函数头部	给函数命名,说明输入和输出数据的类型, 描述函数的用途说明,阐明函数头部	给函数命名,说明输入数据的类型,输出数据的类型,指出函数的目的
Examples 例子	使用例子刻划输入和输出间的关系	搜索问题表述中的例子: 计算例子,如果可能的话,验证结果, 构造例子
模板	阐明程序框架	若参数是复合数据,使用选择器表达式填写主体,如果函数是条件式的,写出所有合适的分支
主体	定义函数	使用scheme基本操作,其他函数,选择器表达式和变量设计Scheme表达式
测试	发现错误	应用函数于例子中的输入,检查程序输出是否与预期的值相符

数据的多样性

数据混合与区分
- scheme提供了辨别数据形式的谓词
  1. number? 判断是不是数
  2. boolean? 判断是不是布尔值
  3. symbol? 判断是不是符号
  4. struct? 判断是不是结构体
  5. 对于每种结构体,scheme都将引入一个谓词,如(define-struct posn (x y))结构体会引入(posn? posn-obj)

设计处理混合数据的函数
1. 数据分析和设计分析问题表述的任务之一就是判断该问题有没有涉及不同类型的数据.
2. 模板模板就是把输入数据翻译成Scheme表达式.
3. 主体模板将任务分割成多个子任务,主体就需要单独处理每一个子任务了.

再论函数复合

在分析问题时,比起设计一个大型的数据定义,先设计多个小型数据定义,再把它们组合起来要容易的多.

输入错误

如果要把函数提供给他人使用,为了防止意外输入错误类型,应当定义自带检查的函数.

语法和语义

Scheme的词汇

基本的Scheme词汇有五类.
```
<var> = x | area-of-disk | perimeter | ...
<con> = true | false
        'a | 'doll | ...
             1 | -1 | 3/5 | 1.22 | ...
<prm> = + | - | ...
```
1. 变量,也就是函数和值和名字
2. 常量, 包括布尔值,符号和数值常量.
3. 基本操作, 也是不Scheme提供的基本函数.

Scheme的文法

<def> = (define (<var> <var> ... <var>) <exp>)
<exp> = <var>
        | <con>
             | (<prm> <exp> ... <exp>)
             | (<var> <exp> ... <exp>)
             | (cond (<exp> <exp>) ... (<exp> <exp>))
             | (cond (<exp> <exp>) ... (else <exp>))

上述的两条方法描述了简单句和复合句的结构.所谓复合句,就是由多个语句组成的语句. 表达式的类别有六种: 变量, 常量, 基本操作, 函数调用以及两种cond表达式.

布尔表达式

and表达式和or表达式和not表达式

变量定义
```
(define RAADIUS 5)
```

结构体的定义

define-struct 在定义结构体的时候,实际上定义了几个基本操作: 包括一个构造器,若干个选择器以及一个谓词.
```
(define-struct struct-name (struct-attr struct-attr ...))
```

任意数目数据的处理

复合数据类型之二: 表

使用cons 例如： (cons x (cons y (cons z empty)))

处理任意长的表

表的进一步处理

自然数

三论函数复合

使用list构造表

（define var1 (list var2 var3 … varn)）

再论任意大数据的处理

再论自引用数据定义

抽象设计

定义的相似性

生成递归

知识积累

改变变量的状态

复合值的改变

总结

TIPS

本书的两个创新

本书是给出一系列明确的程序设计指导, 由此引导学生一步一步地从问题的描述出发,通过明确定义的中间过程, 得出程序.在这个过程中,学生将会学会阅读,分析,组织,实验和系统思维能力.
使用了一个全新的程序设计环境. Scheme???