4 ms·

Not sure I follow. 0001 GOTO 0002 0002 GOTO 0001 How would that be a DAG?

Zambyte 3y ago
I think they meant more the syntactic representation, rather than the control flow. If you rewrite the program using s-expressions, the DAG becomes a little more clear (begin (0001 GOTO 0002) (0002 GOTO 0001)) The DAG has two branches, each with three leaves. There are no cycles in the syntax, even if there is in the execution.
- kdmccormick 3y ago
  Sure, but I would imagine that GGP would have said been more specific and said "tree" instead of "DAG" if they were talking about the AST.
duped 3y ago
More of just a graph like: V: (0001, 0002) E: ([0001, 0002], [0002, 0001]) But really I was just being sarcastic. Builds are "just" DAGs with syntactic sugar just like programs are "just" DAGs with syntactic sugar. That's one possible abstraction and one that is inherently lossy, because what "sugar" is available is the actual meat that makes one build system useful and another terrible. And one actually awful limitation is acylicity, since any build system will eventually deal with it (and outright forbidding of it makes your build system incapable of representing certain builds, just like acyclicity fundamentally limits a program's execution) You can represent pretty much any data model as a graph, that doesn't really address the problem.
- kdmccormick 3y ago
  Right, I understand the graph metaphor, my objection is that programs in a turing complete language do not seem like they can exhaustively modeled as DAGs. Graphs, sure; but AFAICT DAGs fail due to the halting problem (in some abstract sense). A build system modelling itself as a DAG, on the other hand, is very consciously taking on acyclicity as a feature. I am curious what builds would need to be cyclic. Artifact A is built from B and C, where C is built from D and A? Does that happen in any well-designed build?
  - duped 3y ago
    A syntax tree is also a DAG. > I am curious what builds would need to be cyclic. Compilers, interpreters, kernels, and the things that depend on them. So lots. > Does that happen in any well-designed build? Whether or not it's 'well designed' is irrelevant, the question is 'does it need to be possible' because even if it's rare it's still present in a lot of foundational software, notably GCC.

I think they meant more the syntactic representation, rather than the control flow. If you rewrite the program using s-expressions, the DAG becomes a little more clear (begin (0001 GOTO 0002) (0002 GOTO 0001)) The DAG has two branches, each with three leaves. There are no cycles in the syntax, even if there is in the execution.

kdmccormick 3y ago
Sure, but I would imagine that GGP would have said been more specific and said "tree" instead of "DAG" if they were talking about the AST.

duped 3y ago

More of just a graph like: V: (0001, 0002) E: ([0001, 0002], [0002, 0001]) But really I was just being sarcastic. Builds are "just" DAGs with syntactic sugar just like programs are "just" DAGs with syntactic sugar. That's one possible abstraction and one that is inherently lossy, because what "sugar" is available is the actual meat that makes one build system useful and another terrible. And one actually awful limitation is acylicity, since any build system will eventually deal with it (and outright forbidding of it makes your build system incapable of representing certain builds, just like acyclicity fundamentally limits a program's execution) You can represent pretty much any data model as a graph, that doesn't really address the problem.

kdmccormick 3y ago
Right, I understand the graph metaphor, my objection is that programs in a turing complete language do not seem like they can exhaustively modeled as DAGs. Graphs, sure; but AFAICT DAGs fail due to the halting problem (in some abstract sense). A build system modelling itself as a DAG, on the other hand, is very consciously taking on acyclicity as a feature. I am curious what builds would need to be cyclic. Artifact A is built from B and C, where C is built from D and A? Does that happen in any well-designed build?
- duped 3y ago
  A syntax tree is also a DAG. > I am curious what builds would need to be cyclic. Compilers, interpreters, kernels, and the things that depend on them. So lots. > Does that happen in any well-designed build? Whether or not it's 'well designed' is irrelevant, the question is 'does it need to be possible' because even if it's rare it's still present in a lot of foundational software, notably GCC.