PoC: Cached function calls

[Chris Nicholson-Sauls]

A discussion on this group caused me to add a new feature to a hypothetical scripting 
language I've been toying around with for a couple months or so.  It looks, basically, 
like this:

# cache Int fibidx (Int n) {
#   if (n < 2) return n;
#   else       return fibidx(n - 1) + fibidx(n - 2);
# }

The nifty feature is the keyword 'cache' up there, which causes the function 'fibidx' to 
be evaluated /exactly once/ for a given parameter list.  (Granted in the case of Fibonacci 
one can easily accomplish what I'm talking about with a class, but I thought it'd make a 
simple demonstration case.)

So I got to thinking... wouldn't it be nifty to have this, or something like it, in D! 
With that in mind, I tried to think up a way it might be accomplished -- I hadn't yet 
actually tried to do anything with any of D's nifty new templating features, namely 
tuples.  Well, I've learned a few things anyhow.  :)  The following actually works!

# import std .traits ;
#
# struct TCachedFunc (alias Func) { static:
#
#   alias ReturnType         !(Func) Ret    ;
#   alias ParameterTypeTuple !(Func) Params ;
#
#   static if (is(typeof(Params[1]))) {
#     // multiple parameters
#
#     private struct Node {
#       Params params ;
#     }
#
#     private Ret[Node] p_cache ;
#
#     Ret opCall (Params args) {
#       Node node   ;
#       Ret* result ;
#
#       foreach (i, x; args) {
#         node.params[i] = x;
#       }
#       result = node in p_cache;
#
#       if (!result) {
#         p_cache[node] = Func(args);
#         result = node in p_cache;
#       }
#       return *result;
#     }
#   }
#   else {
#     // single parameter
#
#     alias Params[0] Param ;
#
#     private Ret[Param] p_cache ;
#
#     Ret opCall (Param arg) {
#       Ret* result = arg in p_cache;
#
#       if (!result) {
#         p_cache[arg] = Func(arg);
#         result = arg in p_cache;
#       }
#       return *result;
#     }
#   }
# }

Given a 'fibidx' D function like the one above, one may use this template to create a 
cached version by simply aliasing the template.  For example:
# alias TCachedFunc!(fibidx) fibidx_cached;

Then just call it like normal.  I timed such a function as a means of testing the 
template.  The results follow (in order: normal function call, initial use of cache, a 
second use of the cache):
<Benchmark TCachedFunc> Baseline 17.520000
<Benchmark TCachedFunc> Time 16.810000 & 1.042237 versus baseline
<Benchmark TCachedFunc> Time 0.000000 & inf versus baseline

Just, wow.  That said, it really only exhibits any benefits for functions of some 
reasonable complexity, or with deep recursion that eats up cycles (like a fib function 
;)).  Anything that would normally be inlined by the compiler will definitely perform 
better with a normal call.

Anyhow, I just thought someone might find it interesting.  Maybe even useful.  I'm 
considering it for inclusion in Cashew, once I figure out how to properly do this with a 
delegate as well.

-- Chris Nicholson-Sauls