The Artima Developer Community
Sponsored Link

Heron-Centric: Ruminations of a Language Designer
Recursion in a Stack Based Language
by Christopher Diggins
July 8, 2006
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?

Talk Back!

Have an opinion? Readers have already posted 7 comments about this weblog entry. Why not add yours?

RSS Feed

If you'd like to be notified whenever Christopher Diggins adds a new entry to his weblog, subscribe to his RSS feed.

About the Blogger

Christopher Diggins is a software developer and freelance writer. Christopher loves programming, but is eternally frustrated by the shortcomings of modern programming languages. As would any reasonable person in his shoes, he decided to quit his day job to write his own ( ). Christopher is the co-author of the C++ Cookbook from O'Reilly. Christopher can be reached through his home page at

This weblog entry is Copyright © 2006 Christopher Diggins. All rights reserved.

Sponsored Links


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