MemoYzing: memoize using Y Combinator

Lately I've had to speed up an openresty-lua application.  As most of the code is just applications of transformations to data, and it's mainly functional, I thought that memoizing would be the easiest way to go.

After generating a flamegraph for the code, I spotted a couple of functions that could be memoized. Problem solved.

While looking for a nice way to write the memoize function, I remembered the shortest memoizing code ever in lua. Also I googled a bit and found kikito's memoize library. So far so good. But they both share a problem. What about recursive functions? They will get catched only on the top level, because the self referencing calls , after memoizing are not self referencing anymore, and they point to the old function.

Perl memoize module overwrites the symbol table to alias the functions. In ruby 2.0 you can memoize a recursive function using Module#prepend. With the Y combinator

Here's this article from Matt Might about how YCombinator makes it possible to turn a recursive function into a memoized recursive function caching the intermediate results, using the indirect self-reference that it provides.


EDIT: I just published the button and then thought "what if I wanna convert a doubly  recursive function (fib) into a iterative one (tail call) by using accumulators? I can obviously memoize according to the two args, but it gets pretty useless, as the results can be hardly reused. I found this series of articles "from recursion to iteration" that provide some tricks. Haven't fully understood it, but I'm on it.