Causal networks have another name in computer science, in the context of compilers. They’re the dataflow diagrams of loop-free array-free non-recursive functions represented in SSA form. (Functions that contain loops, arrays and recursion can still be reasoned about with causal networks, but only locally—you have to unroll everything, and that blows up quickly if you try to do it globally.)
A dataflow diagram is when you give each variable in a function a node, and draw an edge from the variable to each of the other variables that was used in its definition. SSA form is when you write a function in such a way that every variable is assigned to exactly once—ie, you can’t give a var a value, use it, then give it a new value. Compilers automatically translate functions to SSA form by giving unique names to all the assignments, and defining a new variable (conventionally marked with a combination function phi) at each point where one of several of those names would be chosen based on branch conditions. Compilers use this form because it makes it easier to check which optimizations and transforms are valid before applying them.
Is this comparable to causal networks in some sense, other than being represented as a directed graph? Digraphs are ubiquitous in applications of math, they’re used for all sorts of things.
I’m not sure if this is what jimrandomh was getting at, but there does seem to be a connection to me deeper than merely both being DAGs: optimizations are often limited by how much inference can be made about the causal relations of variables and functions.
One of Haskell’s purposes is to see what happens when you make dependencies explicit, removing most global state, and what optimizations are enabled. For example, consider constant propagation: a constant is a node unconnected to any other node, and therefore cannot change, and being unchanging can be inlined everywhere and assumed to be whatever its value is. If the constant were not constant but had a causal connection to, say, a node which is an IO String that the user types in, then all these inlinings are forbidden and must remain indirections to the user input.
Or consider profile-guided optimization: we relocate branches based on which one is usually taken (probability!), but what about branches not specifically in our profiling sample? Seems to me like causal inference on the program DAG might let you infer which branch is most likely.
Causal networks have another name in computer science, in the context of compilers. They’re the dataflow diagrams of loop-free array-free non-recursive functions represented in SSA form. (Functions that contain loops, arrays and recursion can still be reasoned about with causal networks, but only locally—you have to unroll everything, and that blows up quickly if you try to do it globally.)
A dataflow diagram is when you give each variable in a function a node, and draw an edge from the variable to each of the other variables that was used in its definition. SSA form is when you write a function in such a way that every variable is assigned to exactly once—ie, you can’t give a var a value, use it, then give it a new value. Compilers automatically translate functions to SSA form by giving unique names to all the assignments, and defining a new variable (conventionally marked with a combination function phi) at each point where one of several of those names would be chosen based on branch conditions. Compilers use this form because it makes it easier to check which optimizations and transforms are valid before applying them.
Is this comparable to causal networks in some sense, other than being represented as a directed graph? Digraphs are ubiquitous in applications of math, they’re used for all sorts of things.
I’m not sure if this is what jimrandomh was getting at, but there does seem to be a connection to me deeper than merely both being DAGs: optimizations are often limited by how much inference can be made about the causal relations of variables and functions.
One of Haskell’s purposes is to see what happens when you make dependencies explicit, removing most global state, and what optimizations are enabled. For example, consider constant propagation: a constant is a node unconnected to any other node, and therefore cannot change, and being unchanging can be inlined everywhere and assumed to be whatever its value is. If the constant were not constant but had a causal connection to, say, a node which is an
IO String
that the user types in, then all these inlinings are forbidden and must remain indirections to the user input.Or consider profile-guided optimization: we relocate branches based on which one is usually taken (probability!), but what about branches not specifically in our profiling sample? Seems to me like causal inference on the program DAG might let you infer which branch is most likely.