196
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))
实现谓词和各自的过程：(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
最后更新：2017-05-17 18:01:55