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


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.


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:

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.


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!

Excellent solution.

I can get the main point of the solution, but just be confused about the notation. Would you mind giving a brief pointer about the notation "[f().i/fi]" please? I can see the notation \x1.e1 means (lambda (x1) e1). Thank you very much.
Finally, I think I understand the notation, it means replace "fi" with "f().i" in the previous expression.

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.


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.

Not the same thing

let* and letrec* are sequential binding constructs. They de-sugar to a series of nested let/letrecs, each of which binds exactly one identifier. Letrec for a single identifier is pretty straightforward.

For let, something like what you propose can be made to work. You first evaluate all of the right-hand (initializing) expressions, binding the result to temporary (free) identifiers. You then initialize the let-bound identifiers from the temporaries. This avoids the problem that the let-bound identifiers are not supposed to be bound in the environment where the right-hand expressions are evaluated.

For letrec, this doesn't work, because the letrec-bound identifiers are supposed to be bound in the environment where the right-hand expressions are evaluated.

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


that discussion makes my brain hurt... :)


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) ...)


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

For instance:

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

 (let ((ev?
        (lambda (ev? od?)
          (lambda (k)
            (or (zero? k)
                (od? (- (abs k) 1))))))
        (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.


Clean implementation of letrec is one of the things that's easy to do in Kernel (pdf). For whatever odd insight that might offer, or not, to what you're doing. I do note vau-caluclus, the theory underlying kernel-style operatives, extends lambda calculus.

($define! $letrec
   ($vau (bindings . body) env
      (eval (list* $let ()
                   (list $define!
                         (map car bindings)
                         (list* list (map cadr bindings)))


The Kernel programming language seems to be *the language* I am looking for, especially its simplicity and expressiveness. Thank you very much.

Polyvariadic fixpoint combinator

The general solution is the polyvariadic fixpoint combinator. It is
expressible in the simply-typed lambda-calculus. Please see the
following article for the derivation of both call-by-value and
call-by-name combinators, and further references.

Relevant paper

Ther paper Fixing LetRec addresses this question in the context of Scheme, but the approach only works if the language is not let-polymorphic.