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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk