有段时间没看这本书了.

而且在做笔记的时候产生了一些疑问,觉得这样照着书做笔记没什么意义.于是乎,改变了一下做法.改成先提出疑问,记下重点,然后结合实际案例学习相关东西,最后附上题解,

ok,下面就是第一次的笔记.(依旧是旧套路的)

本节内容

• l  讨论基本的Scheme语法规则
• l  过程的定义
• l  代换模型
• l  条件表达式和谓词
• l  过程抽象
• l  与C语言比较

程序设计的基本元素

所有的高级的语言都会在把简单的认知组合起来形成复杂认识的方法上有独到之处.而且每个强有力的语言都为此提供了三种机制:

• l  基本表达形式:用于表示语言所关心的最简单的个体
• l  组合的方法:从简单的东西出发构造出复杂的元素
• l  抽象的方法:为复合对象命名,并将它们当做单元操作

而在程序设计中我们需要处理的两类要素:数据和过程.

Scheme基本语法规则

是一个交互式语言,类似于Python的解释器运行方式,其解释器运行时反复执行一个”读入---求值---打印”的循环过程,即是递归调用在Scheme中非常常见.每次循环:

• Ø 读入一个完整地表达式
• Ø 对表示求值
• Ø 返回求出的值

与C语言相比,C语言是一个编译型语言,他要求程序要有完整的结构,表达式和语句不是程序,不能够被编译运行,而且编写好的程序需经过编译后运行;从结构上看,,C语言也有描述基本运算的表达式,有描述基本动作的语句,语句上有各种组合(控制流),而它的函数式语言的抽象机制.

C语言还严格的区分了数据和操作数据的过程(代码),而在Scheme里面,数据和过程可以自然的转化:数据可以作为被执行的代码,代码可以被当做被处理的数据.

演示Scheme的基本语法:

1.表达式

2.复合表达式的求值:

要求求值的通常是组合式，解释器的工作方式是：

1. 求值该组合式的各个子表达式
2. 将最左子表达式的值（运算符的值，应该是一个过程）作用于相应的实际参数（由其他子表达式求出的值）

例：(* (+ 2 (* 4 6)) (+ 3 5 7))

组合式求值要求先求值子表达式。因此求值过程是递归的求值过程可以用树表示，先取得终端（叶）结点的值后向上累积,最终在树根得到整个表达式的值树具有递归结构，递归处理很自然

3.变量

4.复合过程

过程定义的基本形式是:

求平方过程的定义：

(define (<name>
 <formalparameters> )  (body) )

过程名     形式参数        做什么（如何求值）

代换模型

预定义基本过程（操作）和特殊形式是构造程序的基本构件,即是可以根据需要，通过定义过程扩大了这一构件集,我们通过定义一个过程将该过程的计算细节抽象起来,使用时只需要像使用运算符一样使用该过程即可,上例而言,从使用上完全看不出 square 是基本操作还是用户定义过程.

复合过程的使用方式和威力与基本操作一样，是很好的语言特征,而过程定义是分解和控制程序复杂性的最重要技术之一

求值这种定义表达式，将相应计算过程关联于名字,组合式和复合过程确定的计算过程是（代换模型）：

a)       求出各参数表达式（子表达式）的值

b)       找到要调用的过程的定义（根据第一个子表达式的求值结果）

c)       用求出的实际参数代换过程体里的形式参数

d)       求值过程体

代换模型给出了过程定义和过程应用的一种语义,很多 Scheme 过程的行为可以用这个模型描述,后面会看到，更复杂的过程需要用扩充的语义模型.

注意：

• Ø  代换模型只是为了帮助直观理解过程应用的行为
• Ø  它并没有反映解释器的实际工作过程
• Ø  实际解释器的情况后面讨论，基于环境实现
• Ø  代换模型最简单，容易理解，但不足以解释所有的实际程序
• Ø  其局限性是不能解释带有可变数据的程序
• Ø  后面将介绍更精细的模型

关于应用序求值和正则序求值

对于复合过程运算,解释器先求值子表达式（运算符和各运算对象），而后把得到的运算应用于运算对象（实际参数）.这一做法合理，但合理的做法不唯一.另一方式是先不求值运算对象，推迟到需要时再求值。

前一方式（先求值参数后应用运算符）称为应用序求值，后一方式（完全展开之后归约）称为正则序求值。Scheme 采用应用序求值.可以避免一些重复计, 其他的作用后面讨论.

Scheme的条件表达式和谓词

Scheme 有条件表达式。绝对值函数可定义为：

条件表达式的一般形式：

 

绝对值函数还可定义为：

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

简化的条件表达式形式：

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

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

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

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

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

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

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

(not<e>) 如果 e的值不是真，就得真，否则得假

谓词是指返回真或假的过程,也指那些能够求出真或假的表达式.各种关系运算符是基本谓词，可以用 and、or、not 组合出各种复杂逻辑条件，可以用过程定义谓词.

题解

练习1.1

直接把表达式敲进编译器就会得出结果.

练习1.2

将中缀表达式改为前缀表达式:

练习1.3

这道题我采用的解决方法是:找出三个数中最小的,然后用三个数的和减去之即可.

首先是找出三个数中最大的代码:

(define (biggest x y z)
    (define (bigger m n)
      (if (< n m)
          m
          n))
    ( bigger x (bigger y z)))

然后是题目answer:

(define (sum-of-bigger x y z)
    (define (smallest x y z)
    (define (smaller m n)
      (if (< n m)
          n
          m))
      (smaller x (smaller y z)))
    (- (+ x y z) (smallest x y z)))

结果如下:

练习1.4

这个无解.

练习1.5

解答这道题的关键在于了解到应用序和正则序之间的区别(书本的 1.1.5 小节有详细的说明)。

首先，可以确定的是，无论解释器使用的是什么求值方式，调用 (p) 总是进入一个无限循环(infinite loop)，因为函数 p 会不断调用自身：

(define (p) (p))

具体到解释器中，执行 (p) 调用会让解释器陷入停滞，最后只能强制将解释器进程杀掉：

1 ]=> (p)
^Z
[1]+  已停止               mit-scheme
$ killall mit-scheme

在应用序中，所有被传入的实际参数都会立即被求值，因此，在使用应用序的解释器里执行 (test 0 (p)) 时，实际参数 0 和(p) 都会被求值，而对
(p) 的求值将使解释器进入无限循环，因此，如果一个解释器在运行 Ben 的测试时陷入停滞，那么这个解释器使用的是应用序求值模式。

另一方面，在正则序中，传入的实际参数只有在有需要时才会被求值，因此，在使用正则序的解释器里运行 (test 0 (p)) 时， 0 和(p) 都不会立即被求值，当解释进行到
if 语句时，形式参数 x 的实际参数(也即是 0)会被求值(求值结果也是为0 )，然后和另一个
0 进行对比((= x 0))，因为对比的值为真(#t),所以 if 返回 0 作为值表达式的值，而这个值又作为
test 函数的值被返回。

因为在正则序求值中，调用 (p) 从始到终都没有被执行，所以也就不会产生无限循环，因此，如果一个解释器在运行 Ben 的测试时顺利返回
0 ，那么这个解释器使用的是正则序求值模式。