# Rewriting recursion in a stack based language

## Christopher Diggins — 2006-07-08 17:13:36

    I believe that in a stack based language like Cat or Joy, the compiler can

    use macros instead of functions. Whenever a recursive definition is arrived

    upon though, it is replaced simply with a goto. I believe this to be more

    powerful than a tail-call recursive optimization, since it works whether or

    not the recursive call is at the end of the function. I have written more

    about it at http://www.artima.com/weblogs/viewpost.jsp?thread=167848 and I

    would appreciate hearing your comments. Hopefully I am not stating the

    obvious :-)

    Christopher Diggins

    http://www.cdiggins.com/cat/

    [Non-text portions of this message have been removed]

## Joe Bowbeer — 2006-07-08 22:34:52

    Using "goto" reminds me of continuation passing style, which was

    exploited by one of the first Scheme compilers (Rabbit) such that

    every call was compiled as a tail call (read "goto").  The Chicken

    Scheme compiler exploits continuation passing style, too.

    Is this an accurate and/or useful comparison?

    Btw, wikipedia goes on to say "As continuation passing style and tail

    call optimization eliminate the concept of an implicit function

    return, their combined use can eliminate the need for a runtime

    stack".

    http://en.wikipedia.org/wiki/Continuation_passing_style

     On 7/8/06, Christopher Diggins <cdiggins@...> wrote:

    > I believe that in a stack based language like Cat or Joy, the compiler can

    > use macros instead of functions. Whenever a recursive definition is arrived

    > upon though, it is replaced simply with a goto. I believe this to be more

    > powerful than a tail-call recursive optimization, since it works whether or

    > not the recursive call is at the end of the function. I have written more

    > about it at http://www.artima.com/weblogs/viewpost.jsp?thread=167848 and I

    > would appreciate hearing your comments. Hopefully I am not stating the

    > obvious :-)

    >

    > Christopher Diggins

    > http://www.cdiggins.com/cat/

    >

## stevan apter — 2006-07-09 00:47:37

    F (and an earlier language of mine, XY) evaluate a quotation

    by pushing its contents onto the input queue.  for example,

    here's a trace of the program 'foo' which executes itself:

    F>[foo!] foo

    F>1"t

    F>foo!

                                             ♦ foo !

                                     [foo !] ♦ !

                                             ♦ foo !

                                     [foo !] ♦ !

                                             ♦ foo !

                                     [foo !] ♦ !

                                             ♦ foo !

                                     [foo !] ♦ !

                                             ♦ foo !

                                     [foo !] ♦ !

                                             ♦ foo !

                                     [foo !] ♦ !

                                             ♦ foo !

                                     [foo !] ♦ !

                                             ♦ foo !

                                     [foo !] ♦ !

                                             ♦ foo !

                                     [foo !] ♦ !

     ----- Original Message -----

    From: "Joe Bowbeer" <joe.bowbeer@...>

    To: <concatenative@yahoogroups.com>

    Sent: Saturday, July 08, 2006 6:34 PM

    Subject: Re: [stack] Rewriting recursion in a stack based language

    > Using "goto" reminds me of continuation passing style, which was

    > exploited by one of the first Scheme compilers (Rabbit) such that

    > every call was compiled as a tail call (read "goto").  The Chicken

    > Scheme compiler exploits continuation passing style, too.

    >

    > Is this an accurate and/or useful comparison?

    >

    > Btw, wikipedia goes on to say "As continuation passing style and tail

    > call optimization eliminate the concept of an implicit function

    > return, their combined use can eliminate the need for a runtime

    > stack".

    >

    > http://en.wikipedia.org/wiki/Continuation_passing_style

    >

    >

    > On 7/8/06, Christopher Diggins <cdiggins@...> wrote:

    > > I believe that in a stack based language like Cat or Joy, the compiler can

    > > use macros instead of functions. Whenever a recursive definition is arrived

    > > upon though, it is replaced simply with a goto. I believe this to be more

    > > powerful than a tail-call recursive optimization, since it works whether or

    > > not the recursive call is at the end of the function. I have written more

    > > about it at http://www.artima.com/weblogs/viewpost.jsp?thread=167848 and I

    > > would appreciate hearing your comments. Hopefully I am not stating the

    > > obvious :-)

    > >

    > > Christopher Diggins

    > > http://www.cdiggins.com/cat/

    > >

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

## William Tanksley, Jr — 2006-07-09 16:28:21

    Christopher Diggins <cdiggins@...> wrote:

     > I believe that [...] Whenever a recursive definition is arrived

    > upon though, it is replaced simply with a goto. I believe this to be more

    > powerful than a tail-call recursive optimization, since it works whether or

    > not the recursive call is at the end of the function.

     I'm not sure if that's right. There are classes of recursion that

    actually do need to return to the caller. In fact, in general

    recursion does by definition need to return to the caller.

    In general, though, full power tail-call optimization is easy to do in

    Forth -- colorForth uses it very heavily, and in fact because of it

    discourages the use of 'else'.

     > Christopher Diggins

     -Billy