当将用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))) (
if
(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))) (
if
result result (eval
-
or (cdr exps) env))))))
如果用宏实现就简单了：
(define
-
syntax and (syntax
-
rules () ((_) #t) ((_ e) e) ((_ e1 e2 e3 ) (
if
e1 (and e2 e3 ) #f)))) (define
-
syntax or (syntax
-
rules () ((_) #f) ((_ e) e) ((_ e1 e2 e3 ) (let ((t e1)) (
if
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) (
if
(
null
?
clauses)
'
false
(let ((first (car clauses)) (rest (cdr clauses))) (cond ((cond
-
else
-
clauses
?
first) (
if
(
null
?
rest) (sequence
->
exp (cond
-
actions first)) (error
"
else clause is not LAST
"
clauses))) ((cond
-
extended
-
clauses
?
first) ;判断是否扩展形式 (make
-
if
(extended
-
cond
-
test first) (list (extended
-
cond
-
recipient first) (extended
-
cond
-
test first)) (expand
-
clauses rest))) (
else
(make
-
if
(cond
-
predicate first) (sequence
->
exp (cond
-
actions first)) (expand
-
clauses rest)))))))
习题4.6，let如果用宏定义，类似这样：
(define
-
syntax let (syntax
-
rules () ((_ ((x v) ) e1 e2 ) ((
lambda
(x ) 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) ) e1 )))))
那么，let*->nested-lets可以定义为：
(define (let
*
? exp) (tagged
-
list? exp
'
let*))
(define (let
*->
nested
-
lets exp) (let ((pairs (cadr exp)) (body (caddr exp))) (
if
(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) (
if
(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
相关资源：sicp-py-zh：【译】UCB CS61a SICP Python-源码
