Arc Forumnew | comments | leaders | submitlogin
1 point by evanrmurphy 4861 days ago | link | parent

> implementing a continuation passing style interpreter is the way to go if you want first-class continuations and tail call elimination.

I'm intrigued. Is this how most languages get tail call elimination?



3 points by fallintothis 4861 days ago | link

Is this how most languages get tail call elimination?

Well, more languages do TCO than use CPS -- never mind a CPS interpreter. Though CPS is functionally equivalent to the more popular SSA (Static Single Assignment) form, it remains relatively unused; see http://lambda-the-ultimate.org/node/3467. I imagine the comment about using an interpreter is rooted in http://billhails.net/Book/v10.html, a great chapter from a book that goes through writing a Scheme-like interpreter in Perl, including a CPS transform and TCO using a trampoline. (For quick info about what those mean, there's of course http://en.wikipedia.org/wiki/Continuation-passing_style and http://en.wikipedia.org/wiki/Tail_call)

In fact, CPS benefits from TCO. By converting a program into explicit CPS, every function call becomes a tail call (to the current continuation); without TCO, stack space would run out quickly. Certain TCO implementations can also use CPS; see http://en.wikipedia.org/wiki/Tail_call#Implementation_method....

A great discussion about TCO implementation is http://lambda-the-ultimate.org/classic/message1532.html. To get really into it, the master's thesis at http://users.cecs.anu.edu.au/~baueran/thesis/ talks about tail calls in GCC (I've not read it, but it looks interesting).

-----

1 point by evanrmurphy 4860 days ago | link

Wish I could upvote you more than once. Great reply.

-----