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