Extensible Dependency Caching

Question

I'm working on developing a system for computing and caching probability models, and am looking for either software that does this (preferably in R or Ruby) or a design pattern to use as I implement my own.

I have a general pattern of the form function C depends on the output of function B, which depends on the output of function A. I have three models, call them 1, 2, and 3. Model 1 implements A, B and C. Model 2 only implements C, and Model 3 implements A and C.

I would like to be able to get the value 'C' from all models with minimal recomputation of the intermediate steps.

To make things less abstract, a simple example:

I have a dependency graph that looks like so: A₁ is Model 1's implementation of A, and A₃ is model 3's implementation of A. C depends on B, and B depends on A in all of the models.

The actual functions are as follows (again, this is a toy example, in reality these functions are much more complex, and can take minutes to hours to compute).

The values should be as follows.

Without caching, this is fine in any framework. I can make a class for model 1, and make model 2 extend that class, and have A,B, and C be functions on that class. Or I can use a dependency injection framework, replacing model 1's A and C with model 2's. And similarly for Model 3.

However I get into problems with caching. I want to compute C on all of the models, in order to compare the results.

So I compute C on model 1, and cache the results, A, B and C. Then I compute C on model 2, and it uses the cached version of B from before, since it is extended from model 2.

However when I compute model 3, I need to not use the cached version of B, since even though the function is the same, the function it depends on, A, is different.

Is there a good way to handle this sort of caching with dependency problem?

Answer 1

Anyway...with this, my first pass at it, is to make sure that functions A, B, and C are all pure functions, aka referentially transparent. That should help, because then you'd know whether to recompute a cached value depending on whether the input has changed or not.

So talking it through, When I'm computing C1, nothing's computed, so compute everything.

When computing C2, check if B1 needs updating. So you ask B1 if it needs updating. B1 checks if its input, A2 has changed from A1. It hasn't, and because all the functionals are referentially transparent, you're guaranteed that if the input hasn't changed, then the output is the same. So therefore, used the cached version of B1 to compute C2

When computing C3, check if B1 needs updating. So we ask B1 if it needs updating. B1 checks to see if its input, A3 has changed from A2, the last time it computed something. It has, so we recompute B1, and then subsequently recompute C3.

As for the dependency injection, I currently see no reason to organize it under the classes, A, B, and C. I'm guessing you want to use the strategy pattern, so that you can use operation overloading in order to keep the algorithm the same, but vary the implementations.

If you guys are using a language that can pass around functions, I would simply chain functions together with a bit of glue code that checks for whether it should call the function or use the cached value. And every time you need a different computation, reassemble all the implementations of the algorithm that you need.