Adapton: Programming Language Abstractions for Incremental Computation

Anyone know how incremental-computation related to partial-evaluation or staged-computation?

I haven’t dug into the IC papers yet, but from my understanding.

Partial-Evaluation is specialization of function over arguments. Say f(x,y,z) => v, a partially computed function f’(x,y) can be computed by binding ‘z’. Thus, applying f’ to (x,y) will yield the same value ‘v’ as f(x,y,z).

Staged-Computation is a generalization (restriction?) of partial-evaluation, but for meta-programs that generate other programs. That’s to say, the result value v of a staged meta-program M is itself a computable function. M(f(x,y,z)) the meta-program that generates previous function f can itself be decomposed to multiple steps M’’(M’(f(x,y,z))) => M(f,x,z), but having those intervening steps of computation openly accessible allows for interesting program manipulation possibilities. Which is why staged-computation subsumes everything from compiler generation, to macros, to runtime optimization.

So, Incremental-Computation (is?) looks to me like partial-evaluation + reactive programming? That is, a PE’ed function will get recomputed if any of its arguments change value? This doesn’t make in a formal model like the lambda calculus, which captures values and renames variables. So perhaps there is something other than call-by-value at work here?

  (define add-two
    (let ((two 2))
      (lambda (x)
        (+ x two))))

If I were then to say

  (incremental-computation:change-value 'two 3)

And I'm assuming ADD-TWO will get recomputed, how would this work? Which "two" will be changed? Will it replace the captured value in the body of the lambda, or does it reify captured variables of each function into a global symbol-table, a la the Mozart/Oz constraint store?

Can someone explain how this works actually?

Exciting stuff. I'm hoping for an implementation that targets Javascript, and which will be a fundamentally more powerful and more efficient alternative to libraries like React.

On a _very_ high-level it is like a spreadsheet model of computation: build the dependencies between calculations, propagate value changes to the dependent calculations, but with two important improvements: per-node memoization of the previous calculations and ignoring updates that will not lead to the change of something visible to the user in the UI.

My compiler compiles 100,000 lines of code a second.

50,000 lines are compiled during boot (half a second).

50,000 lines are compiled during MakeAll (half a second).

If you echo to screen, compiles slowly.