Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Re: Pure Perl tail call optimization

by abstracts (Hermit)
on Apr 26, 2002 at 06:54 UTC ( #162200=note: print w/ replies, xml ) Need Help??


in reply to 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
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)
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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://162200]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (10)
As of 2014-09-17 18:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (94 votes), past polls