If you don't evaluate the function's body when it's declared, and your language is lexical, than your function should always be evaluated in a context where its

If you don't evaluate the function's body when it's declared, and your language is lexical, than your function should always be evaluated in a context where its own name is bound. If your language has dynamic scope, than the above still basically works until somebody defines a local var to the name of your function. The only situation where recursion wouldn't work is where all of your vars are static. As for compiling Lexical scoping, I can't help you there, although I've heard it's not too hard, if you don't care about optimization. Dynamic scoping is dead simple to compile, though. As for tail call optimization, if your target is an assembler with a goto instruction that in any way resembles a real instruction set, the only slightly tricky bit is figuring out what function is in the tail position. Once you've done that, it shouldn't be too hard. Lambda, The Ultimate Declaritive has details, IIRC.