Re: Pure Perl tail call optimization

Another note (hope I haven't bothered you enough yet :-))

Last time I checked with the Parrot docs (the tutorial mainly), there was no mention of jumps to computed values (which is what you said you need for implementing call/cc). So the question is: how can one do proper tail recursion without jumps? (Parrot does have jump LABEL though)

Another question is: if your C compiler doesn't do proper tail recursion (C compilers are not required to), then can you still do proper tail recursion in C?

Just for the record, here is the definition of proper tail recursion according to the Scheme Revised^5 Report:

Implementations of Scheme are required to be properly tail-recursive. ... . A Scheme implementation is properly tail-recursive if it supports an unbounded number of active tail calls. A call is active if the called procedure may still return.

I don't think scheme implementations are required to support call/cc, but they are required to support proper tail recursion.

The reason I'm blabbering about this is that I just finished a course in compilers where we implemented a good subset of scheme. The compiler translates scheme to Sparc assembly code, and at some time we targeted C. So, I know proper tail recursion is possible, even in VB :-).

Aziz,,,

Update: Thanks Elian for the reply. I guess the docs might be out of date since development there is going very fast.

Comment on Re: Pure Perl tail call optimization

Replies are listed 'Best First'.
Re: Re: Pure Perl tail call optimization by Elian (Parson) on Apr 26, 2002 at 15:12 UTC
Last time I checked with the Parrot docs (the tutorial mainly), there was no mention of jumps to computed values (which is what you said you need for implementing call/cc). So the question is: how can one do proper tail recursion without jumps? (Parrot does have jump LABEL though) Parrot supports jumping (and branching) to locations (and offsets, though they're less useful) stored in registers. Only works with the `jump`, `jsr`, `branch`, and `bsr` ops though. (Used to work with the conditionals, but that was silly so we yanked that support)	[reply]
Re: Re: Pure Perl tail call optimization by ambrus (Abbot) on Feb 03, 2004 at 14:36 UTC
I've just read scheme standard. Scheme has to implement both tail-rec and call/cc. As for C, I think it's possible to implement proper tail recursion with setjmp/longjmp, but I'm not sure. Most C compilers have tail call optimizations I think, not because it's so simple but because it's so important. BTW, if perl is implemented like this (in a stackless way) then it may be simple to implement tail-recursion optimization (but the developpers must have some reason why it's not already done). Maybe it's also possible to create true call/cc: reference counting should be enough for most uses of call/cc, like exceptions and multithreading.	[reply]


Clear questions and runnable code get the best and fastest answer
	PerlMonks