It appears that you can automatically identify and rewrite any recursive call in a stack based language like Cat, as a loop using a goto statement.
In Cat I wanted to inline every single function call. Essentially I wanted to replace functions with macros. Ideally the whole language would be based on a series of rules for rewriting the syntax (more on this in a future installment).
The single challenge I faced with this approach was how to deal with recursion. Macros do not allow recursion. I believe I found the answer: goto.
Consider the following psuedo-code in Cat (the code is "psuedo-code" because it uses an old version of Cat syntax, the new form is extremely cryptic and will possibly be revereted to this form again):
define a = b [a] [c] if;
This gets rewritten as:
define a = #a label b [#a goto] [b] if;
This seems to work in all cases, unlike the similar tail-recursion optimization common in functional languages. This whole "label" and "goto" syntax syntax would also be hidden from the programmer.
Am I missing anything here, or is this sufficient?
Mathematically proven things: (1) Any recurssion (even multiple recurssion, like the one in Ackerman function) can be rewritten as an iteration. (at lest by hand). (2) It's CONTINUATIONS in functional languages that make this converssion transparently.
Continuations can be thought as OOP-ish objects organised as a spaghetti-stack of "possible futures".