Quite different. To achieve the effects of "Incremental" you would need lazy evaluation coupled with a caching layer, so that successive calls to pure functions with same arguments are not re-computed. This optimization technique is in a sense similar to Common Subexpression Elimination.

But this is possible to do trivially using a hash keyed by the input variables. It seems to me that SAC offers an interest only in the case where:

- the input variables of the DAG are updated at a different rate

- and the result of complex subgraphs depend on only a few of these variables (and thus avoiding to recompute their result is a win)

I don't know if it's enough to get excited about.

Doesn't Haskell already do this? What is the advantage of OCaml + Incremental over Haskell?

Haskell does not do this. Haskell is lazy (computed results are shared), but Haskell does not memoize by default. To illustrate:

    func y = let z = y + y
             in (add 1 z) * (add 1 z)

in `func` the result of computing `y + y` is shared because it has been given a name: `z`. However, the result of `add 1 z` is _not_ given a name and therefore has to be computed twice. Because Haskell is pure, they will result return the same result, however the result is not saved.

This avoids needing to save the results of _all_ function calls.

That's a bad example, since GHC will perform common expressions elimination, which effectively give the same name to the two `add 1 z` (unless you specifically ask it not to, with `-O0`.)

Furthermore, Incremental isn't memoizing every function calls. It just keeps the intermediate results of the latest computation in memory, so that when the inputs change, it can determine exactly which subresults need a recomputation, and which can be reused. It's like Excel, but with dynamic dependencies.

(But yes, Haskell definitively does not do this. You could say that Haskell is about doing the least amount of work to compute something fresh, while Incremental is about working the least to recompute something we (almost) already computed just before.)

A better example might have been

    func (f (add 1 z), f (add z 1))

Since f is not memoized it will be evaluated once for each component of the tuple.

Actually, that's an interesting question. Having built similar systems before, the main reason why you would not simply run a function every time your input is updated is that you often need for your computations to keep a certain amount of state, which may depend on the input. However, as Incremental does not seem to support much in the way of stateful computations, I'm a bit puzzled wrt to what problem it addresses.