sicp-4-1-6-4-1-7
Posted on 2015-03-09 23:37:54 +0900 in SICP
4.16
a:
(define (lookup-variable-value var env)
(define (env-loop env)
(define (scan vars vals)
(cond ((null? vars)
(env-loop (enclosing-environment env)))
((eq? var (car vars))
(if (equal? (car vals) '*unassigned*)
(error "Unassigned variable" var)
(car vals)))
(else (scan (cdr vars) (cdr vals)))))
(if (eq? env the-empty-environment)
(error "Unbound variable" var)
(let ((frame (first-frame env)))
(scan (frame-variables frame)
(frame-values frame)))))
(env-loop env))b:
(define (scan-out-defines body)
(let* ((definitions (filter definition? body))
(rest-of-lambda (filter (lambda (x)
(not (definition? x)))
body))
(symbols (map cadr definitions))
(let-body (map (lambda (s) (list s ''*unassigned*))
symbols))
(set-body (map (lambda (s) (list 'set! (cadr s) (caddr s)))
definitions)))
(if (null? let-body)
body
(list (append (list 'let let-body) set-body rest-of-lambda)))))This part is tricky, which took me several hours to make it.
''*unassigned*needs two single quotes. Because'*unassigned*is the value of a variable.- The returned value should be in a list.
- The
(null? let-body)should be used, otherwise it would loop forever.
4.17
There is an extra frame in the transformed program because let is transformed to a lambda call.
To make the scope role “simultaneous” without creating a new frame, the internal definations could be extract to the top before being runned.
(define (rearrange body)
(let* ((definitions (filter definition? body))
(rest-of-lambda (filter (lambda (x)
(not (definition? x)))
body)))
(append definitions rest-of-lambda)))4.18
Both this version and the original version would not work, as the values of u and v are
evaluated directly without through other proxy values.
4.19
The footnote gives the opinion of the author.
It is complicated implement the simutaneous, even though Topological sort could be used to deal with
simple defination order problem.
But when the mutual_recursion happens, it would not be possible to get the actual defination order at all.
For racket:
(let ((a 1))
(define (f x)
(define b (+ a x))
(define a 5)
(+ a b))
(f 10))
a: undefined;
cannot use before initialization4.20
(define (letrec? exp) (tagged-list? exp 'letrec))
(define (letrec->let exp)
(let* ((assi (let-associations exp))
(rest-of-lambda (let-body exp))
(symbols (map car assi))
(let-body (map (lambda (s) (list s ''*unassigned*))
symbols))
(set-body (map (lambda (s) (list 'set! (car s) (cadr s)))
assi)))
(if (null? let-body)
exp
(append (list 'let let-body) set-body rest-of-lambda))))letrecis evaluated includes all the letrec bindings, while let is not.
4.21
((lambda (n)
((lambda (fact)
(fact fact n))
(lambda (ft k)
(if (= k 1)
1
(* k (ft ft (- k 1)))))))
10)
;-->
((lambda (ft k)
(if (= k 1)
1
(* k (ft ft (- k 1)))))
(lambda (ft k)
(if (= k 1)
1
(* k (ft ft (- k 1)))))
10)
;-->
(if (= 10 1)
1
(* 10
((lambda (ft k)
(if (= k 1)
1
(* k (ft ft (- k 1)))))
(lambda (ft k)
(if (= k 1)
1
(* k (ft ft (- k 1)))))
9)))
;-->
(* 10
((lambda (ft k)
(if (= k 1)
1
(* k (ft ft (- k 1)))))
(lambda (ft k)
(if (= k 1)
1
(* k (ft ft (- k 1)))))
9)))(define (f x)
((lambda (even? odd?)
(even? even? odd? x))
(lambda (ev? od? n)
(if (= n 0) true (od? ev? od? (- n 1))))
(lambda (ev? od? n)
(if (= n 0) false (ev? ev? od? (- n 1))))))$\lambda$ makes functional programming possible.
4.22
((let? exp) (analyze (let->combination exp)))Analyze is able to handle it.
4.23
execute-sequence has cond and other extra commands, while the text version
is just some runnable procedure.
(lambda (env)
((lambda (env)
(proc1 env)
(proc2 env))
env)
(proc3 env))4.24
(eval '(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n))) the-global-environment)
(let ((t0 0) (t1 0))
(define (loop i n)
(eval '(factorial 1234) the-global-environment)
(if (< i n)
(loop (+ i 1) n)))
(set! t0 (runtime))
(loop 0 200)
(set! t1 (runtime))
(- t1 t0))For original version: $3.302853$ second, while for optimized version $2.106789$ second.