Re: [boost] Re: Memoization library

From: Jeremy Maitin-Shepard (jbms_at_[hidden])
Date: 2003-12-14 16:03:04

David Abrahams <dave_at_[hidden]> writes:

> Jim Apple <japple_at_[hidden]> writes:
>> David Abrahams wrote:
>>>> I don't think I understand your problem. Is the graph a function
>>>> parameter, or a global? 
>>> I don't see why that matters.
>> 
>> Persistent memoization (see below) depends on always returning the
>> same result for the same arguments.

> Between or within calls? (turnabout's fair play)

> And, I still don't see how the global vs. parameter thing changes
> anything.  We don't have a functional programming language; even
> parameters can be mutated.

In practice, I think it would be rather difficult for a general library
such as this to support some sort of partial cache invalidation, simply
because such support must inevitably be very problem-specific.  I am
guessing, however, that with most graph-related algorithms, the entire
cache would need to be invalidated, and thus this is less of an issue
for those problems.  As far as practical issues, I am guessing that the
memorization library works by using the function arguments as a key to
an associative container, and so the library would not normally work
with global state; in the case of graph problems though, if the graph
were specified as a function argument, any change to the graph would
mean that the memorization library would not associate existing cache
data with the new graph.

-- 
Jeremy Maitin-Shepard