Lambda the Ultimate

For good or for ill, the computer algebra (and programming) language Maple has a very sophisticated caching strategy that users can choose to associate to any function/procedure. For those functions where caching is enabled, then computational cost can indeed become impossible to calculate, the best you can do is measure it empirically [since it depends on external factors!].

In practice, it seems to help for medium-sized problems, and can be a hindrance for very large problems [mostly because Maple's usage of memory tends to be distributed uniformly over all allocated memory, which really messes up with the processor cache].

Thanks, this is just the sort of thing I'm looking for..

By the way, out of curiosity, do you know why Maple distributes its allocations in that way?

At the low-level, the most fundamental data-structure (after arrays) in Maple are hash tables. These are absolutely pervasive in the low-level implementation. In particular, all objects are made "unique"; in other words, all objects (implemented as DAGs, Directed Acyclic Graphs, via C pointers) only exist in one copy in memory. This is done by using a global hash table with keys based on object's memory addresses. Memory allocation happens, like in most systems, based on various free-lists. Since a lot of computations are ``almost functional'', this means creating a lot of temporary objects which quickly get collected. The main effect of this is that long-lived objects tend to get spread throughout memory pretty uniformly.

I do believe that some of these ideas were already present in Macsyma. However the Maple implementation was at least an order of magnitude more efficient, so that in the mid-80s, Maple completely took over from Macsyma as the ``main'' computer algebra system.

I use the term "decayed memoization" to emphasize its use as a (transparent) language level feature.

For one thing, it would make it even harder to calculate computational cost for the program.

Indeed it would.. But perhaps not any more than choice of GC scheme/execution strategy/optimization technique.

chances are you would get worse performance in general from this language than without this "feature".

This is a valid concern. I picture the runtime only inserting "memoization points" at places where the computation time is significant. Memoized data is considered second class, and in tight memory situations the allocation of "real data" causes a cull of the memoization pool based on the metrics mentioned above.

I can imagine various scenarios where this scheme would produce good speed-ups, and others where it wouldn't help at all. I guess the tricky part would be to get the runtime smart enough to distinguish between the two.

I'm toying with the idea of adding this feature to a dataflow style language I'm currently working on, as it appears be a natural fit. I guess the proof is in the eating..

But perhaps not any more than choice of GC scheme/execution strategy/optimization technique.

I'm talking about algorithmic complexity cost, not runtime cost per se.

Algorithmic costs are in general WAY more significant than operational runtime costs, such as GC, on any vaguely decent platform.

Furthermore, I tend to believe that operational concerns without algorithmic impact don't really belong in a language design.

I picture the runtime only inserting "memoization points" at places where the computation time is significant.

I would think that in general, you would be better off building a simple purpose-built cache using your specific knowledge of your data structures and their required characteristics.

May be worth a try though. Good luck with it.

of Hughes' paper: here, thanks to google books.

[on edit:] alas, they only show the first 2/16 pages, plus citations.