Computational DAGs

  • Makefile triggers only updates to what changed (how?)
    main: main.o module1.o module2.o
        g++ main.o module1.o module2.o -o main

    To build the file main, I need to first make sure that targets main.o, module1.o and module2.o are up to date; then I need to call the following command...

    To be "up to date" means that the last-modified time of [output file] is newer than any of its prerequisites' last-modified times

  • React redraws UI based on state change, ideally recalculating only what changed
    • there's a tension between this approach, and imgui one, where UI is drawn every frame, and there's no need to calculate diffs
  • is this related to signal-collect graphs or VPLs?
  • this is also somewhat related to structural sharing in Clojure

Are there any incremental computation systems that treat inputs not as mutable cells, but model the whole system as a persistent data structure, and updates create a new, structure-sharing instance?

  • this idea is also related to computational DAGs - building a graph of computation, instead of organising everything into a tree of objects
  • representing as a DAG (nodes and edges):
    • this is a DAG:
      |       |
      A       +->F->G
      |       |
      represented as a tree:
      + B
      | + E
      |   + F
      |     + G
      + C
        + D
          + F
            + G
    • DAGs can make describing relations simpler: F depends on E and D - this is used in Makefiles for example
    • node-and-edge languages (VPLs) are DAGs describing computations - they are best modeled with streams, event emitters, etc.

Nodes on the board can hold internal state, which other nodes can react to, forming a computational DAG:

Szymon Kaliski © 2022