Perl 6 already supports those semantics for things like hyperoperators and junctions, and pugs already implements it if you have multiple CPUs.

There will also be an is cached trait to tell Perl that a routine may be treated as effectively pure. There is no commitment here to the level of caching, however. The optimizer could, for instance, trade an LRU cache for a complete cache to trade memory for time if the potential parameter space is large.

Or you can write your own caching, of course. Here's the current self-caching version of fibonacci. It works in pugs:

sub fib (UInt $n) {
    (state @seen = 0,1,1)[$n] //= fib($n-1) + fib($n-2);
}
[download]

This is likely to be more efficient than automatic caching because we know that the arguments are not going to be sparse integers. Also, the explicit "state" declaration tells the optimizer in no uncertain terms that this is not pure code.

Another Perl 6 solution down in the pugs examples directories looks like this:

sub fib (UInt $n, UInt $curr = 0, UInt $next = 1) {
    return $curr unless $n;
    return fib($n-1, $next, $curr + $next);
}
[download]

That's essentially just using tail recursion to implement the standard loop algorithm. The optimizer could probably deduce that it's pure code and maybe memoize it. As you point out, whether that's a win or not really depends on context.

Anyway, the point is that Perl 6 will certainly support TMTOWTDI when it comes to the amount of control you desire, and over how functionally you want to think. As specced (but not yet implemented), you can even do the really pretty version in Perl 6:

multi fib (0)       { 0 }
multi fib (1)       { 1 }
multi fib (UInt $n) { fib($n-1) + fib($n-2); }
[download]

Admittedly, that's not quite as spare as the Haskell version, mostly because I hate dangling syntax, which Haskell is full of. I like things to have a beginning, a middle, and an end. "Once upon a time, Perl 6 happened, and they all lived happily ever after." :)