The Artima Developer Community
Sponsored Link

Weblogs Forum
Recursion in a Stack Based Language

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

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
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 10:06 AM
Reply to this message Reply
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.
Advertisement

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 8, 2006 10:59 PM
Reply to this message Reply
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 7:48 AM
Reply to this message Reply
> 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 4:19 PM
Reply to this message Reply
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 4:51 AM
Reply to this message Reply
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 12:11 PM
Reply to this message Reply
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 1:52 PM
Reply to this message Reply
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 2:01 PM
Reply to this message Reply
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
Topic: Recursion in a Stack Based Language Previous Topic   Next Topic Topic: Version 0.3 of the Cat Programming Language

Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use