[ericbb]

I definitely struggled to find a satisfying approach to recursion in my own current language project. What I'm doing right now is passing the closure value of the callee as a hidden first argument to every call. Nonrecursive functions just ignore that argument but recursive functions can always call themselves via that hidden argument.

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.

[chrisseaton]

Do you not have any kind of registry of functions in your language where you can look up a function from a name and then call it? Then you don't need to pass in the current function to itself as it can look itself up in the registry, like any other function could (again, no special cases needed).

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.

[ericbb]

That's an excellent question! :)

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"!

[ww520]

What about using scope environments and variable binding? For lambda calculus, variable binding (of the single variable x) in an environment (the current application of lambda) is a fundamental part of it anyway.

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.

[chrisseaton]

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

[ericbb]

Yes, I think I see your point. If I may put it in my own words, I think you are talking about "dynamic recursive activation" throughout this thread.

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!

[_RPM]

My language has first class functions, as names are tied to values, and a value can be a function. With the opcode CALL_FUNCTION (in my VM), it does a searching of the hash table for the value.