当将用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终止。