lunes, 2 de noviembre de 2009

Eficient implementation of Tail recursion in Perl 5



I'm getting more and more interested in fringe programming languages (some of them are use the functional paradigm).

I'm no pro by any means, but little by little, I think I'm starting to grasp what's all that about, and I understand small new tricks every now and then.

In the YAPC::EU::2009, there was a loooooong discussion while we were having dinner about tail recursion, the minimizing of stack space and so.

Until this week, in perl 5, you could emulate tail recursion optimization by implementing it manually in the place where you want the optimisation. An explanation of "HOW" can be found in chapter 13 of "Exploring Programming Language Architecture in Perl" (EPLAiP from now on) , when the author explains how you could implement a sort of CPS in perl.

Well, last week,
Yuval Kogman (a great perl hacker with *LOTS* of useful modules) released Sub::Call::Tail , a Perl 5 module that allows you to call a function and make perl optimize the stack usage. For a brief usage howto, you can visit Yuval's post.

Today, I see in another of his blog posts he just created Sub::Call::Recur , a kind of curried version of Sub::Call::Tail, that just loops over the current sub. As he sais, it's a kind of redo but for functions instead of blocks. The resulting code is quite optimized (nearly as fast as plain iteration), so we can say perl5 has now tail recursion optimization. nothingmuch++;

Byez!

UPDATE:
Seeing http://ezrakilty.net/research/2009/11/function_calls_are_not_stack_frames.html I think I might review the post.... sorry for my ignorance :(