Computational DAGs

  • Makefile triggers updates only to changed files (by timestamp) 
    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

    — https://stackoverflow.com/a/4349717

  • React redraws UI based on state change, recalculating only what changed
    • there's a tension between this approach, and immediate mode UI, where UI is drawn every frame, and there's no need to calculate diffs

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?

— https://mobile.twitter.com/MarijnJH/status/1191720489523318786

Connections are Usually Better than Taxonomies
  • this idea is also related to computational DAGs - building a graph of computation, instead of organising everything into a tree of objects
DAG and Tree Representations of Code
  • representing as a DAG (nodes and edges):
    • this is a DAG:
      +->B->E-+
|       |
A       +->F->G
|       |
+->C->D-+
      represented as a tree:
      A
+ 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.
VPL
Protoboard

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