Lambda the Ultimate

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.

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.

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.

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.

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 letrec in Scheme about letrec and continuation

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.

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.

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)))
                   body)
            env)))

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.

http://okmij.org/ftp/Computation/fixed-point-combinators.html#Poly-variadic

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