开发者

Looking for references describing tail recursion optimization through exceptions

开发者 https://www.devze.com 2023-04-08 16:36 出处:网络
I have implemented a small lisp interpretor (sapid lisp at google code) in python and sapid lisp itself. Perhaps its main characteristic is to implement tail and mutual recursion optimization through

I have implemented a small lisp interpretor (sapid lisp at google code) in python and sapid lisp itself. Perhaps its main characteristic is to implement tail and mutual recursion optimization through exceptions. Implementation details here https://sites.google.com/site/sapidlisp/recursion-optimization.

The advantage over standard techniques is the limited changes to apply to a recursive interpretor to get tail recursion optimization. Disad开发者_开发问答vantage could be timing.

I have found a similar technique used in a python decorator ( http://code.activestate.com/recipes/474088/ ). Now to put the technique in its context I am looking for references describing such a technique for lisp or other interpreted languages. Any information?


See Eli's answer. But to add a little more context, Baker's Cheney on the M.T.A. technique was a well-known trick for implementing proper tail recursion that used the C stack as a nursery (as in generational GC) for continuation frames and other objects. Rather than keeping the stack small (as most implementations of tail recursion do), this technique allows the stack to grow for a while, then clears it with a big jump (longjmp, execption, whatever) every once in a while. And before you clear the stack, you copy all of the live stuff out of it onto the heap.

That works fine as long as you're able and willing to trace the stack and copy objects out of the stack onto the heap. The paper Eli cited (Continuations from Generalized Stack Inspection) is about adapting the trick to "managed" platforms, where you can't inspect the stack directly.


See Continuations from Generalized Stack Inspection by Pettyjohn et al, and a related addendum by Joe Marshall.

("interpreted", whatever that means these days, has nothing to do with the subject.)

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号