I wrote a VM, I still can't get recursion to work. It's hard.
If I tell you that a function may call any function, then you already know everything you need to know for recursion. If we didn't have recursion, only then would I need to qualify what I just told you with the restriction that a function can only be active once.
When I show students recursion I can't understand their confusion. I think to myself 'but I already showed you functions can call any other function, why do you see this case differently?'
(Obviously I try to be more patient, understanding and anticipatory in person.)
Also, just to be clear, I understand how recursion works as a user of a programming language, though implementing it is different than using it.
It doesn't allow you to support syntactic mutual recursion but it's easy to do and can be implemented without data modification at any level.
There shouldn't be any need for recursive calls to be a special kind of call. They caller shouldn't need to know that it is calling itself (again, lack of special casing).
This is how recursion works in languages like Java, Python, Ruby, C.
In my language, there is no special global scope for variables; every program is basically one giant (extended and sugared) lambda calculus expression.
I do use lambda-lifting so that in the C code I generate, there is a C function in the global C namespace that is called to execute an object-language function but object-language functions also have closure environments so any kind of self-reference needs to include both the global C function and the closure environment for that particular closure.
Note that my language does support modularity (breaking programs into multiple files, basically). However, the mechanism for referring to "packages" (stuff in other files) uses a separate name system.
I agree that languages that bind all functions in a global scope can easily use that global scope to resolve recursive references. It's also easier when your language supports variable assignment and destructive updates of data structures. But my language doesn't support those things either. :)
Addendum: By the way, you mentioned Java, Python, and Ruby, which are all object-oriented. Of course, the recursion among methods in those languages arises in a way that's very similar to passing a callee as a hidden argument. In OO languages, the hidden argument is "self" or "this"!
Self or this allows you to refer to the same object. You don't need to refer to the same object to wind up calling the same method. You could have two different objects that just have the same method. Maybe they share a class, or a mixin, or whatever. So I'm not sure self is relevant here.
I don't mean to disagree with the point you are making! It's a valid point.
However, I would like to emphasize that some languages have syntactic properties that complicate things a bit and I feel that a comment about how things "should" be really ought to be qualified by something like, "in a mainstream Java-like language".
Consider the simply-typed lambda calculus, or Martin-Löf type theory. These languages don't allow general recursion but it's not because they are always poorly implemented!
A scope environment gives you a place to name "things". "Things" can be functions. It's just a name-value map. You create a local scope environment for every function invocation. You can bind things (value or functions) to names in the local environment. Then you can refer to "things" by their names, like calling a function using its name.
Parent scope environments can be nested in the local scope when the function is called. A search on a name not found on the current scope can be delegated to the parent scope, so that functions defined and named in outer scope can be referenced in inner scope.
Recursive call is not a problem for named function since you can look up the function by name. It becomes a problem for anonymous function (lambda) since it can't be looked by name. For that you can introduce a special name like "_lamb" for it. Upon entry of a function, you bind the current function to the name in the current environment. A reference to it would call the current function again. e.g. _lamb(). You can even have a special name "_parent" to bind to the parent environment. In that case you can call the anonymous parent function. E.g. _parent._lamb()
Function calling and recursive function have nothing to do with OO or Java/Python/Ruby. It has everything to do with name, binding, scope, and environment.
Assume the following AST.
FN_DEF: { NAME: foo, PARAMS: [int4 param1, int4 param2] }
LOCAL_VARS: [int4 var1, int4 var2, int4 var3]
...
ASSIGN: { var1, CONST: 0x1 }
ASSIGN: { var2, ADD:{ 0x2, param1 } }
...
var3 = FN_CALL: { foo, ARGS: [var1, var2] }
...
RETURN: { var3 }
fn_foo:
push ebp ; save the caller's old frame pointer
mov ebp, esp ; the new frame pointer to current stack ptr
sub esp, 20 ; make new space in stack for params and locals
; EBP points to the base of the current frame
; the frame has 20 bytes in the stack
; var1 at [ebp-4]
; var2 at [ebp-8]
; var3 at [ebp-12]
; param1 at [ebp-16]
; param2 at [ebp-20]
...
mov [ebp-4], 1 ; assign 0x1 to var1
mov [ebp-8], 2 ; assign 0x2 to var2
add [ebp-8], [ebp-16] ; add param1 to var2
...
push [ebp-4] ; push var1 for the function call
push [ebp-8] ; push var2 for the function call
call fn_foo ; call function foo at address fn_foo
; the current EIP is saved in stack
; the return value will be in EAX
mov [ebp-12], eax ; save function return value to var3
...
mov eax, [ebp-12] ; set function return value from var3
mov esp, ebp ; pop frame
pop ebp ; restore old EBP to previous frame
ret ; return to the caller by popping the
; caller's address from stack into EIP.
; Execution will continue at the restored EIP address.Most programming I learned was imperative. As I wrote the code, I imagined the execution in my head. This led to a problem where when I was halfway through a function, and it referred to itself, my brain would segfault. How could something I was not yet done writing refer to itself? I hadn't finished yet, so my brain could not comprehend what such a reference would mean.
It was also difficult because I wanted to think of functions as nice neat pieces of code that would take some data, do it's thing, and return a value. I could mentally inline a function call without much effort.
But when recursion is introduced, the floor drops out of my mental inlining. Suddenly my mental effort for such things becomes huge. For me anyway. My brain doesn't like to float around in abstraction land for long, it needs to periodically be anchored in the concrete. Otherwise I quickly lose my sense of direction and orientation... I lose my context.
Declarative languages actually make these easier, for me, because I'm not mentally executing a recipe as I write. I am giving a piece-wise description of what something is. So there is no mental tracing.
I expect the a-ha moment for recursion is different for everyone. But just showing recursion in many different forms would probably help. For example, show fib sequence generation where instead of the function calling itself, each function calls a uniquely named function... such that you concretely demonstrate building the first 5 or so numbers in the sequence...
Then show the similarity of the functions, show what the computer has to keep track of with the nested function calls, and step by step work your way to straight recursion.
Show it in BASIC with GOTO statements.
Finding as many different ways to concretely demonstrate an abstract concept will help reach more people.
1. I do still inline recursive functions, but I've learned to selectively inline just the base case when I first implement recursion. Paradoxically, experience with lisp helped me with recursion in C, particularly Common Lisp's trace facility which taught me to visualize stacks of multiple function calls (whether recursive or not) rather than a single one at a time.
2. I've learned to think declaratively even when I program in C. When writing a C function I might start out with a crisp definition in my head ("this function saves the reverse of the list seen so far in its second argument") so that I can rely on that definition even when the implementation isn't yet complete.
[1] http://akkartik.name/post/mu
[2] https://news.ycombinator.com/favorites?id=akkartik&comments=...
That should happen naturally, if you implement a compiler to native code. A "call" instruction is just a "goto/branch/jump" with some extra stack fiddling.
Also, I don't think pure functions are so easy mentally either. Try to understand "call with current continuation". ;)
Recursion is likely to expose bugs in the calling convention if you're writing your first compiler.
If I give you a list of requirements for a programming language that I want you to implement and it includes 'a function must be able to call any function' then you have recursion. You don't need additional separate requirement for 'and that function may be itself', as long as you've fully implemented the first requirement. In fact you'd need an extra requirement to prevent recursion, not to allow it.
That's what I mean by you shouldn't need to consider recursion as a special case.
The fact it is not an additional requirement to allow recursion is irrealevent, what matter is that its extra complexity to handle that case correctly.
Not that I think that is the OP's problem - just a bit of interesting history. Support for recursion may seem obvious in hindsight, but there was a time where that wasn't the case.
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.