[plt-scheme] Behind the scenes of letrec

From: Marco Morazan (morazanm at gmail.com)
Date: Wed Feb 27 21:00:00 EST 2008

Dear All,

I am considering different alternatives for implementing letrec. As an
example consider the following:

 (letrec ((a (lambda (b) (* 2 b)))
          (b (lambda (c) (a c)))
          (c (lambda (q) (b q))))
   (c 5))

We can implement it by transforming letrec into let and use assignment:

(let ((a '())
       (b '())
       (c '()))
   (let ((x (lambda (b) (* 2 b)))
         (y (lambda (c) (a c)))
         (z (lambda (q) (b q))))
     (set! a x)
     (set! b y)
     (set! c z))
   (c 5))

I am aware that Dybvig et. al. proposed a more sophisticated
transformation to let with assignments.

Alternatively, we could transform the letrec into an application
expression and create a new local function (i.e. within the same scope
of the letrec expression) such as:

new local function:

(define (new)
   (define a (lambda (b) (* 2 b)))
   (define b (lambda (c) (a c)))
   (define c (lambda (q) (b q)))
   (c 5))

new application expression:

 (new)

>From a purist's perspective, the latter is attractive given the lack
of assignment. What are the reasons for preferring the former
transformation?

Cheers,

Marco


Posted on the users mailing list.