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 |#