sicp4.1.1-4.1.5节部分习题尝试解答(update)-白红宇

当将用scheme写的scheme求值器跑起来的时候，你不觉的兴奋是不可能的，真的太酷了，太magic了。

习题4.2，如果将application？判断放在define?判断之前，那么求值(define x 3)将把define当作一般的procedure应用于参数x和3，可是define是特殊的语法形式，而非一般过程，导致出错。

习题4.4，我的解答，eval增加两个判断：

((and

exp)

(eval

and (and

exps exp) env))

((or

exp)

(eval

or (or

exps exp) env))

实现谓词和各自的过程：

(define (and

exp)

(tagged

list

exp

and))

(define (and

exps exp)

(cdr exp))

(define (eval

and exps env)

(cond ((

null

exps)

true)

(

else

(let ((result (eval (car exps) env)))

(

(not result)

result

(eval

and (cdr exps) env))))))

(define (or

exp)

(tagged

list

exp

or))

(define (or

exps exp) (cdr exp))

(define (eval

or exps env)

(cond ((

null

exps)

false)

(

else

(let ((result (eval (car exps) env)))

(

result

(eval

or (cdr exps) env))))))

如果用宏实现就简单了：

(define

syntax and

(syntax

rules ()

((_) #t)

((_ e) e)

((_ e1 e2 e3

)

(

e1 (and e2 e3

) #f))))

(define

syntax or

(syntax

rules ()

((_) #f)

((_ e) e)

((_ e1 e2 e3

)

(let ((t e1))

(

t t (or e2 e3

))))))

习题4.5，cond的扩展形式，也不难，在else子句之外增加个判断，是否带有=>符号，修改expand-clauses过程：

(define (cond-extended-clauses? clause)

(and (> (length clause) 2) (eq? (cadr clause) '=>)))

(define (extended-cond-test clause)

(car clause))

(define (extended-cond-recipient clause)

(caddr clause)

(define (expand

clauses clauses)

(

null

clauses)

false

(let ((first (car clauses))

(rest (cdr clauses)))

(cond ((cond

else

clauses

first)

(

null

rest)

(sequence

exp (cond

actions first))

(error

else clause is not LAST

clauses)))

((cond

extended

clauses

first) ;判断是否扩展形式

(make

(extended

cond

test first)

(list

(extended

cond

recipient first)

(extended

cond

test first))

(expand

clauses rest)))

(

else

(make

(cond

predicate first)

(sequence

exp (cond

actions first))

(expand

clauses rest)))))))

习题4.6，let如果用宏定义，类似这样：

(define

syntax let

(syntax

rules ()

((_ ((x v)

) e1 e2

)

((

lambda

) e1 e2

) v

))))

求值器扩展，实现let->combination过程：

(define (let? exp)

(tagged

list? exp

let))

(define (let

combination exp)

(let ((vars (map car (cadr exp)))

(vals (map cadr (cadr exp)))

(body (caddr exp)))

(cons (make

lambda

vars (list body)) vals)))

我们做的仅仅是syntax transform，将let转成对应的lambda形式。

习题4.7，这里的关键在于let*->netsted-lets要递归调用，从let*的宏定义可以看出：

(define

syntax let

(syntax

rules()

((_ ((var1 val1)) e1

)

(let ((var1 val1)) e1

))

((_ ((var1 val1) (var2 val2)

) e1

)

(let ((var1 val1))

(let

((var2 val2)

)

)))))

那么，let*->nested-lets可以定义为：

(define (let

? exp)

(tagged

list? exp

let*))

(define (let

*->

nested

lets exp)

(let ((pairs (cadr exp))

(body (caddr exp)))

(

(null? (cdr pairs))

(list

let pairs body)

(list

let (list (car pairs)) (let*->nested-lets (list

let

(cdr pairs) body))))))

测试一下：

(let* ((x 1) (y (+ x 3))) (+ x y)) =》5

习题4.8，命名let，修改let->combination过程，判断cadr是pair还是symbol，如果是前者，那就是一般的let，如果是symbol就是命名let语句，那么需要定义一个名为(cadr exp)的过程放在body里，注意，我们是在做语法转换，因此，这个定义也应该描述成符号，定义一个make-define过程来生成define语句：

(define (make

define var parameters body)

(list

define (cons var parameters) body))

然后修改let->combination过程，如上所述：

(define (let

combination exp)

(

(symbol? (cadr exp))

(let ((var (cadr exp))

(vars (map car (caddr exp)))

(vals (map cadr (caddr exp)))

(pairs (caddr exp))

(body (cadddr exp)))

(cons (make

lambda

vars (list (make

define var vars body) body)) vals))

(let ((vars (map car (cadr exp)))

(vals (map cadr (cadr exp)))

(body (caddr exp)))

(cons (make

lambda

vars (list body)) vals))))

习题4.1.4，原生的map过程接受的procedure，是以scheme内在数据结构表示的procedure，而在我们的求值器中，procedure的内在数据结构取决于我们，与原生的结构不同，导致原生的map无法接受自制求值器的procedure，如果map也以求值器中的结构定义，那么就没有这个问题。因此，本质上的困难就在于两个求值器对procedure的数据结构表示的不同。

习题4.1.5，著名的图灵停机问题，先是假设存在halts?过程可以正确地判断任何过程p和对象a是否p对a终止，定义了try过程：

(define (try p)

(if (halts? p p)

(run-forever)

'halted))

当执行(try try),如果这个过程可终止，那么(halts? try try)应该返回false，也就是try过程对try不会终止，这与一开始的假设矛盾；如果这个过程将无穷运行下去，那么(halts? try try)应该返回true，也就是try对try终止，这也与(try try)将无穷运行的假设矛盾。因此，可以推论出，我们不可能写出一个过程halts?，使它能正确地判断任何过程p和对象a是否p对a终止。

文章转自庄周梦蝶，原文发布时间 2008-06-01