当将用scheme写的scheme求值器跑起来的时候，你不觉的兴奋是不可能的，真的太酷了，太magic了。
习题4.2，如果将application？判断放在define?判断之前，那么求值(define x 3)将把define当作一般的procedure应用于参数x和3，可是define是特殊的语法形式，而非一般过程，导致出错。
习题4.4，我的解答，eval增加两个判断：
如果用宏实现就简单了：
习题4.5，cond的扩展形式，也不难，在else子句之外增加个判断，是否带有=>符号，修改expand-clauses过程：
习题4.6，let如果用宏定义，类似这样：
习题4.7，这里的关键在于let*->netsted-lets要递归调用，从let*的宏定义可以看出：
(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语句：
习题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))
实现谓词和各自的过程：
(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))))))
(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))))))
(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)))))))
(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过程：
(syntax - rules ()
((_ ((x v)
) e1 e2 )(( lambda (x
) e1 e2 ) v ))))
(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形式。
(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)))
习题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可以定义为：
(syntax - rules()
((_ ((var1 val1)) e1
)(let ((var1 val1)) e1
))((_ ((var1 val1) (var2 val2)
) e1 )(let ((var1 val1))
(let * ((var2 val2)
)e1
)))))
(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))))))
测试一下：
(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过程，如上所述：
(list ' define (cons var parameters) body))
(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))))
( 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
