doing letrec with lambdas

Hi there,

I promise this isn't a homework assignment of some sort, but it sure feels like it should be....

I'm working on a pet language of mine, which I'm building up from a hopefully minimal intermediate language very similar to lambda-calculus. In order to map proper (potentially mutual) tail-recursion onto the lower-level implementation mechanics, I realized that I need to be able to do the moral equivalent of a letrec, but, since this's just a kernel-intermediate language, I want to avoid syntactic sugaring until higher-level intermediate forms instead, and would strongly prefer to not introduce a one-off level of complexity to hack this up. Doing "let" with lambdas is trivial enough that even I understand it, but I've gone 'round the proverbial mulberry bush with letrec, and to no avail.

Would someone either have a quick answer as to how this's done, or else know of a link to a site/paper/discussion where folks do this? This really can't be as hard as it seems....

Thanks!

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

easy in simple interpreters with frame based bindings

If you're doing it yourself and you can do a 'let' or a 'let*', then letrec is only barely different: the frame with bindings declared by the letrec must be visible in the letrec as well. That's all you need. It's a visibility thing. If the bindings produced by letrec can also be seen by the code inside the letrec definitions, then you're done.

If you need a reference, you can find a copy of any ancient XLisp implementation and look at the difference between letrec and let.

but it could be even harder,

Infact it could be impossible to implement it only using lambda, since it's mutable references can be implemented using letrec (combined with call-with-current-continuation).
Of course that doesn't mean you can't define a special form which takes the fixpoint of a procedure (or procedures), this is possible with a small generalization of the Y combinator.

exactly

At this point I'm trying to avoid any special forms I possibly can; right now I have forms for application, lambda-abstraction and typecases -- if I absolutely have to I'll add one for letrec (all my lets will be letrecs), but that seems to imply much more "environment" than I want to keep around at this level in the interpreter stack.

Perhaps I'm trying to square a circle and just need to bite the proverbial bullet....

Fixpoint combinator

If your IL is untyped, you can simply code up a fixpoint combinator such as Y:

http://en.wikipedia.org/wiki/Y_combinator

If your IL is typed, you need recursive types to be able to express such a combinator.

Edit: Note that you can easily code up mutually recursive functions with a single recursive higher-order function that returns a tuple of functions.

letrec f1 x1 = e1 ... fN xN = eN in e
:=
letrec f x = (\x1.e1,...,\xN.eN)[f().i/fi] in let f1 = f().1 ... fN = f().N in e
:=
let f = Y (\f.\x.(\x1.e1,...,\xN.eN)[f().i/fi]) in let f1 = f().1 ... fN = f().N in e
:=
(\f. (\f1....\fN.e) (f().1) ... (f().N)) (Y (\f.\x.(\x1.e1,...,\xN.eN)[f().i/fi]))

Edit 2: Fixed error in expansion.

hmm

Creating a tuple-type for passing the mutually-recursive functions hadn't occurred to me -- I'll mull that one over.

The next stage up will be typed, but at the level I'm currently working on, that might work out ok. Thanks!

You know, if you realy want

You know, if you realy want to you can implement tuples with nothing but closures.

as product types?

You mean by implementing them as categorical product types and projection functions? Yeah, I'm familiar with that from the wizard book, but at this point I don't have true closures yet -- at this point in my interpreter stack I have formal parameters only.

EDIT: actually, a very restrictive curry-closure might be appropriate where I am in the stack, which might make this really the correct answer. Thanks!

Transform to let + set

If you have mutable bindings, you can use this transformation:

(letrec ((x 1) (y 2)) ...)
==>
(let ((x nil) (y nil)) (set x 1) (set y 2) ...)

I think this binding construct is called letrec* in R6RS Scheme.

yeah...

That's the scheme (pardon the pun) that I'm familiar with -- I'm planning on doing just that later on up the interpreter stack, but am trying to avoid putting that functionality this far down if I can help it.

See Fixing letrec

See Fixing letrec: A faithful yet efficient implementation of Scheme’s recursive binding construct. This might not be a solution to your problem, but maybe it will give you some ideas.

a recent discussion of

a recent discussion of letrec in Scheme about letrec and continuation

ouch

that discussion makes my brain hurt... :)

Let-polymorphism

Depending on your intended language design, you may want to be a little bit careful about combinator tricks. If you intend a let-polymorphic language, then the LET construct becomes first class, and has subtly different behavior from LAMBDA application.

This only works in a call by name model though

I came on this page to find some answers for a similar problem of my own, I'm implementing some toy pure lisp interpreter which hasn't any mutations, so I would have to find a way to make letrec sensibly. I have introduced a combinator fixp such that:


(fixp f) >> f
(fixp f x ...) >> (f (fixp x x ...) ...)

edit: the bottom pattern may look wierd, but it means that:

(fixp f a b c) >> (f (fixp a a b c) (fixp b a b c) (fixp c a b c))

For instance

Which allows me to rewrite


(letrec ((name value) ...)
  body)

to:


(let ((name (lambda (name ...))
              value)) ...)
   (let ((name (fixp name name ...)) ...)
      body)

For instance:

(define (fixp f . xs)
  (apply f
         (let loop ((q xs))
             (if (null? q) '()
                 (cons (apply fixp (car q) xs) 
                       (loop (cdr q)))))))

(display
 (let ((ev?
        
        (lambda (ev? od?)
          (lambda (k)
            (or (zero? k)
                (od? (- (abs k) 1))))))
       (od?
        
        (lambda (ev? od?)
          (lambda (k)
            (and (not (zero? k))
                 (ev? (- k 1)))))))
   
   (let ((ev? (fixp ev? ev? od?))
         (od? (fixp od? ev? od?)))
     
     (ev? 16))))

Which works, mutual recursion without the use of set! or define, but only if you use a call by need/name model. I'm sure the combinator can be adjusted towards an applicative model but at the moment it diverges in an applicative model.

Of course, the relative speed of the letrec greatly depends on the efficiency by which fixp can be implemented.