Weblogs Forum
Recursion in a Stack Based Language

7 replies on 1 page. Most recent reply: Jul 10, 2006 5:01 PM by Emil Cristian Alexandrescu

 Previous Topic Next Topic
 Flat View: This topic has 7 replies on 1 page
 Christopher Diggins Posts: 1215 Nickname: cdiggins Registered: Feb, 2004
Recursion in a Stack Based Language (View in Weblogs)
Posted: Jul 8, 2006 1:06 PM
Summary
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?

 Sean Conner Posts: 19 Nickname: spc476 Registered: Aug, 2005
Re: Recursion in a Stack Based Language Posted: Jul 9, 2006 1:59 AM
Pardon me if I use a Forth-type langauge instead of Cat---I'm sure you can translate it. The point being, turn the following recursive function into an interative one:

`: fib ( n -- n )  dup 0 = if return then  dup 1 = if return then  dup 1- fib swap 2- fib + return;`

You might it to be a tad difficult to inline the recursive calls.

 Christopher Diggins Posts: 1215 Nickname: cdiggins Registered: Feb, 2004
Re: Recursion in a Stack Based Language Posted: Jul 9, 2006 10:48 AM
> Pardon me if I use a Forth-type langauge instead of
> Cat---I'm sure you can translate it. The point being,
> turn the following recursive function into an interative
> one:
>
>
`> : fib ( n -- n )>   dup 0 = if return then>   dup 1 = if return then>   dup 1- fib swap 2- fib + return> ;> `

>
> You might it to be a tad difficult to inline the recursive
> calls.

My gosh, you are completely correct. Thank you for pointing that out!

 Tim LS Posts: 37 Nickname: parchandri Registered: Jul, 2005
Re: Recursion in a Stack Based Language Posted: Jul 9, 2006 7:19 PM
So you can write recursive function definitions in Cat, but you will be trying to automatically optimize them by inlining them?

Does the difficulty with the fibonacci example come from there being 2 possible return addresses?

 Jules Jacobs Posts: 119 Nickname: jules2 Registered: Mar, 2006
Re: Recursion in a Stack Based Language Posted: Jul 10, 2006 7:51 AM
The fibonacci example isn't tail recusive, so you can't optimize tail calls as jumps.

 Emil Cristian Alexandrescu Posts: 13 Nickname: mkcoos Registered: Jul, 2006
Re: Recursion in a Stack Based Language Posted: Jul 10, 2006 3:11 PM
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".

 Jules Jacobs Posts: 119 Nickname: jules2 Registered: Mar, 2006
Re: Recursion in a Stack Based Language Posted: Jul 10, 2006 4:52 PM
Yes, but you'll need a stack or a simulation of one.

 Emil Cristian Alexandrescu Posts: 13 Nickname: mkcoos Registered: Jul, 2006
Re: Recursion in a Stack Based Language Posted: Jul 10, 2006 5:01 PM
Precisely!
However, in the case of Cat, which has a stack-based "core", this is hardly a problem.

And, if continuations are fully supported, a spaghetti-stack structure is needed.
Here, again, Cat has no problems yet - since it is still under construction.

 Flat View: This topic has 7 replies on 1 page
 Previous Topic Next Topic