I'm looking for some pointers/articles/papers on abstractions for incremental computations. Something that describes a Computation that can compute a value on demand and has Dependencies and the value is invalidated when one of the Dependencies change... and a Computation can also be a Dependency of another computation. But more detailed and more rigorous. Has anybody ever seen such a thing?

Would dataflow fit your requirement list? https://en.wikipedia.org/wiki/Dataflow

Timely Dataflow: https://dl.acm.org/doi/abs/10.1145/2517349.2522738

Things to look up: Adapton, Self adjusting computation, dataflow, Salsa (rust), Reactive programming/systems

Jane street has a library called incremental based on works by Umut Acar. https://blog.janestreet.com/introducing-incremental/ https://www.ccs.neu.edu/home/amal/papers/impselfadj.pdf I've found dissertations to be the best place to learn hard technical things. They are long. But almost always assume less prior knowledge and give you lots of references.

Thank you all for all the pointers so far. I have a lot to look through 🙂

https://dagger.io can do this, built on BuildKit and CUE (cue/flow) auto dependency detection and knows when inputs have changed and something needs to be rerun / recalced

FRP: http://conal.net/papers/frp.html

Branching off FRP, i would recommend a javascript libray like

@vue/reactivity

, solidjs, ect.

import {ref, computed} from ‘@vue/reactivity’

const count = ref(0)
const doubleCount = computed(() => count.value * 2)

console.log(count.value, doubleCount.value) // 0, 1

count.value++

console.log(count.value, doubleCount.value) // 1, 2

observablehq.com notebooks are functional reactive graphs that do the correct thing when code changes (like spreadhseets). The runtime is open source: https://github.com/observablehq/runtime. An explanation of the execution is here: https://observablehq.com/@observablehq/how-observable-runs

Partial evaluation may also be relevant.

Maya uses a Directed Acyclic Graph, I guess this is one implementation of DataFlow. In Maya’s system, nodes are invalidated when data is pushed onto connections on the node, and the dirty state is propagated to all dependent nodes. When connections are read, nodes are computed up the chain until the connection can be validated. Maya has an interesting design where nodes can also be part of a hierarchy (used to evaluate a scene graph for geometry transforms, etc.). Since I read about this ‘first’, a lot of my graph designs use a similar approach; it’s the first thing that made sense to me.

Thank you all! I'm going to study Jane Street’s Incremental next, and I also found the “map” by @jamii very helpful. My context is I want to prototype a system for storing DSL models in the form of ASTs and doing transformations on them (type checking, interpretation, etc.). I don’t think I will find an existing implementation I could directly reuse, but I hope to borrow ideas.

I love this post: https://lord.io/spreadsheets/ The "further reading" section at the bottom also has great pointers.