gyehoek-hs/doc/notes.org

assorted notes on compilation

• letrec

letrec

consider:

  (letrec ((even? (lambda (n)
                    (if (zero? n)
                        #t
                        (odd? (- n 1)))))
           (odd? (lambda (n)
                   (if (zero? n)
                       #f
                       (even? (- n 1))))))
    (even? 12))

#t

since letrec is a primitive construct in the CPS language, the translation of mutually recursive functions is straightforward:

  (define (-& x y k) (k (- x y)))
  (define (zero?& x k) (k (zero? x)))
  (define (halt x) x)

  (letrec ((even? (lambda (n ktail)
                    (zero?& n
                            (lambda (x1)
                              (if x1
                                  #t
                                  (-& n 1
                                      (lambda (x2)
                                        (odd? x2 ktail))))))))
           (odd? (lambda (n ktail)
                   (zero?& n
                           (lambda (x1)
                             (if x1
                                 #f
                                 (-& n 1
                                     (lambda (x2)
                                       (even? x2 ktail)))))))))
    (even? 12 halt))

#t

however, Scheme permits letrec-expressions with non-lambda right-hand sides, while the CPS language permits only kappa and lambda forms. thus, the handling of these forms is less trivial.

for now we'll just reject any letrec forms with non-lambda right-hand sides, lol. they aren't very important.