Sweet. Tail calls were a bit easier to implement than I had expected. Still not 100%, but getting close.

At first, this was pretty damn difficult since I treat the result of evaluating a lambda as a delegate. E.g. a binding always ends up treating a variable bound to a lambda as a typed delegate (which points to the function that was generated). Unfortunately, delegates can't be tail called in the CLR.

So my first change was to start using the raw method handles instead of delegates where possible. This was an optimization I had to make anyhow, and it's had benefits elsewhere in the compiler that I just got for free. Then I changed my letrec implementation so that it directs the binding information down the lambda's AST before emitting its code. This way the lambda knows what it's being bound to (if anything), and adds it to a psuedo environment when generating its body.

I used to set the environment up for the lambda eagerly, but once I start referring recursively to the lambda being bound, it gets to be quite difficult! I had originally thought I can emit dummie calls to a static void NoOp() function and do some backpatching afterwards, but it turns out Reflection.Emit doesn't allow you to change the IL you've already emitted. So I wound up with the syntax-directed design.

Anyhow, I need to write up some good whitepapers on this stuff. Bottom line, this Scheme program:

(let ((fact2 (lambda (n v)
                  (if (> n 0)
                    (fact2 (- n 1) (* v n))
                    v)))
       (fact (lambda (n) (fact2 n 1))))
  (fact 1000000))

Used to bomb out with a StackOverflowException. Now it runs beautifully... well, except for the fact that I don't have bignum support and hence the result is “Infinity”. Nonetheless, it was a straightforward excercise.