]> git.rkrishnan.org Git - sicp.git/blob - src/sicp/ex4_20.rkt
Solution to 4.44. A bit too verbose. Can be improved by better
[sicp.git] / src / sicp / ex4_20.rkt
1 #lang racket
2
3 #|
4 (define (f x)
5   (letrec ((even? 
6             (lambda (n)
7               (if (= n 0)
8                   #t
9                   (odd? (- n 1)))))
10            (odd?
11             (lambda (n)
12               (if (= n 1)
13                   #t
14                   (even? (- n 1))))))
15     <body>))
16
17
18
19 (letrec ...) is transformed into:
20
21 (let ((even? '*unassigned*)
22       (odd? '*unassigned*))
23   (set! even? (lambda (n)
24                 (if (= n 0)
25                     ...
26                     ...)))
27   (set! odd? (lambda (n)
28                ...))
29   <body>)
30
31 |#
32
33 #|
34
35 letrec is of the form:
36
37 (letrec ((<var1> <exp1>) ... (<varn> <expn>))
38   <body>)
39
40 |#
41 (define (tagged-list? expr tag)
42   (or (pair? expr) (eq? (car expr) tag)))
43
44 (define (letrec? expr)
45   (tagged-list? expr 'letrec))
46
47 (define (letrec-variables expr)
48   (let ((p (car (cdr expr))))
49     (map car p)))
50
51 (define (letrec-values expr)
52   (let ((p (car (cdr expr))))
53     (map cadr p)))
54
55 (define (letrec->let expr)
56   (if (not (letrec? expr))
57       (error "not a letrec expression -- LETREC")
58       (let ((vars (letrec-variables expr))
59             (vals (letrec-values expr))
60             (body (cdr (cdr expr))))
61         (cons 'let
62               (cons (map (lambda (var)
63                            (list var ''*unassigned*))
64                          vars)
65                     (append (map (lambda (var val)
66                                    (list 'set! var val))
67                                  vars
68                                  vals)
69                             body))))))
70
71 #|
72
73 b. In the case where we use lecrec, this gets transformed into let. So, when we call (f 5)
74 a new frame is formed with even? and odd? assigned to '*unassigned. Then these are set to 
75 the lambda expressions belonging to even? and odd?.
76
77 When we use a let in the place of letrec, a frame gets created with even? and odd? assigned
78 to the lambda expressions. Then the body of the let expression (i.e. <rest of body of f>)
79 is wrapped in a lambda which takes as parameters, even? and odd? is called with the lambda
80 expressions corresponding to even? and odd?. 
81
82 i.e. ((lambda (e? o?)
83        <rest of body of f>) 
84       (lambda (n) (...reference to o?..)) 
85       (lambda (n) (.reference to e?... )))
86
87 So, a frame gets created which assigns e? and o? to the corresponding lambdas. The enclosing
88 environment for it, does not have e? or o? defined. So, these definitions
89 When we draw the environment, the two lambdas passed as parameters do not see each other as their
90 environment is the enclosing env of t. so they are undefined. When the body is evaluated, then
91 these will generate error for undefined references.
92
93 |#