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