# How do I solve this graphing dependency cycle in an AST?

I'm playing around with AST generation and exploring how it relates to a directed acyclic graph. I hit a logical snag that I don't understand.

``````var literal = 3; // expression 1

literal = literal+1; // expression 2

``````

Clearly the value of literal is 4; that is, once expression 2 has been parsed. Logically, though, the actual result of expression 1 is dependent on expression 2, and expression 2 is dependent on expression 1.

Can an acyclic graph represent the above?

Obviously since ASTs are graphs, and an AST can parse the above without overflowing (i.e. cyclic) there must be some sort of temporal parameter that is part of the DAG that I'm missing.

In sketching the dependencies of the graph, I can see a valid graph being created when a third node is introduced, representing the register location of the variable. But this is only valid if the DAG is recursed in the correct order.

Can you give some guidance or help in understanding the logic of how AST parsing obtains acyclic conditions?

• Where is the cycle in your graph? i.e. how can you start from one node, move to another node, and then later return to the original node. Commented Mar 23 at 20:00
• I didn't illustrate the cyclic condition, but logically `literal = expression(literal)` is a self-referential statement, i.e. `literal = expression(literal = expression(literal = expression(literal = ...` Commented Mar 23 at 20:14
• An AST just describes syntactic structure, not data flows. Typical ASTs just carry the information that a variable called `literal` exists, but not yet resolve it. That typically happens in later phases, after parsing. Sometimes the AST is enriched with such info, sometimes there is a separate Intermediate Representation (IR). You may find the LLVM IR to be particularly interesting because all its virtual registers are assign-once, making data flow analysis straightforward. There might be different registers for each "version" of the variable. Can still be cyclic though, if you have loops.
– amon
Commented Mar 23 at 20:39

## 2 Answers

I'm playing around with AST generation and exploring how it relates to a directed acyclic graph. I hit a logical snag that I don't understand.

``````var literal = 3; // expression 1

literal = literal+1; // expression 2
``````

Clearly the value of literal is 4; that is, once expression 2 has been parsed.

No, it is not. It has the value `4` once the code is executed, but there is no such thing as a "value" during parsing. "Value" is a semantic thing, not a syntactic thing.

Logically, though, the actual result of expression 1 is dependent on expression 2, and expression 2 is dependent on expression 1.

That is true when evaluating, but not when parsing.

Can an acyclic graph represent the above?

Sure. Here is an example of what a hypothetical AST for a hypothetical language in which your code is valid might look like:

And, since your code happens to be valid ECMAScript source code, here are two not hypothetical examples of how a real ECMAScript parser would parse your code.

This first one was generated with JointJS:

And this one was generated with AST Explorer, which is based on the Acorn ECMAScript parser:

``````---
type: Program
body:
- type: VariableDeclaration
declarations:
- type: VariableDeclarator
id:
type: Identifier
name: literal
init:
type: Literal
value: 3
kind: var
- type: ExpressionStatement
expression:
type: AssignmentExpression
operator: "="
left:
type: Identifier
name: literal
right:
type: BinaryExpression
left:
type: Identifier
name: literal
operator: "+"
right:
type: Literal
value: 1
``````

As you can see, none of these three require any cycles.

Obviously since ASTs are graphs, and an AST can parse the above without overflowing (i.e. cyclic) there must be some sort of temporal parameter that is part of the DAG that I'm missing.

There is nothing "temporal" in parsing. Syntax and grammar are completely static properties of a programming language. (Well, there are a very small number of mostly very obscure programming languages where the programmer can modify the syntax at runtime. Let's ignore these for now.)

• Thank you for the post! In the first graph image you provided, there is an implicit "left to right" order. Reversing the descendants of the first `Statement Sequence` node would dereference `id:literal` before it is declared. Therefore the graph has an "already performed" topological sort. In reality, I wrote the order of the code because I knew the reverse order is a compiler error. The compiler however had to perform some task to give me the error to teach me the order to write the code...loosely called "the step after parsing"??? What is this next step called in the process? Commented Mar 23 at 21:54
• The first `Statement Seqence` has two descendants 1. left branch described as "the branch that assigns the variable" and 2. "the branch that performs the expression." Logically the second branch is dependent on the first. Of the three illustrations you gave, none have directed edges pointing from 2. to 1. expressing that the entirety of branch 2 cannot exist with branch 1. What am I missing here? What type of illustration would validly express this? Is it some future stage in compiling? Commented Mar 23 at 22:04
• The notable case of a language that did not keep this barrier sufficiently distinct is perl. Perl allows runtime state to leaking into lexing decisions leading to perlmonks.org/?node_id=663393 Commented Mar 25 at 19:54
``````literal = literal + 1;
``````

This doesn't quite mean what you think it means. It's more like this:

``````literal' = literal + 1;
``````

Or invent a new name like `literal4` if you're not fond of the prime.

The point is, your LHS `literal` is different from your RHS `literal`, and there's no going back to the original one, which is lost and GC'd. We're tracing the temporal evolution of a system. There is no cycle.

Some production systems prohibit recycling an identifier like `literal`, to prevent such confusion. Under revised rules, we would be forced to introduce a new identifier like `literal4`.

• I do know that C# allows this, whereas Rust has more explicit annotations required "hey do you really want to do that assignment" via `let mut` declaration. The question, though, is can a stable DAG be illustrated accounting for the temporal aspect. This seems like a classic topological sort of the graph, such that the logical result of a successful run of the program must have an equivalent topologically sorted graph where the value of variables have been accessed in the correct order... Commented Mar 23 at 20:34
• In other words, where the language allows the "shadowing" of the variable, the programmer has additional overhead designing the system to access a variable in the correct order...this is the source of my question and would love any resources that explores this temporal aspect Commented Mar 23 at 20:37
• Suppose we initialize three variables to zero and then we have `a = 1; b = 2; c = 3;` and later `a = b + c;`. Those three assignments are causally independent and may be arbitrarily re-ordered or executed in parallel. In contrast, the final assignment induces a happens-before relationship, such that we must first associate 2 and 3 with `b` and `c`. Your example features a similar relationship. // Modern compilers and Intel processors re-order statements all the time. So the literature you're looking for might feature concepts like "memory fence", associated with implementing a mutex.
– J_H
Commented Mar 23 at 20:38
• Yes, your example would have multiple valid topological sorts, i.e. a,b,c could be assigned in any order, or all 3 in parallel as you say, but any sort in this example would definitively require the a,b,c assignments to appear before the expression execution. I'd like to validate my hypothesis that "any validly executable code has an equivalent directed acyclic graph that at runtime is equivalent to the topological sort." I'm sure most language primitives are designed around graph nodes, just looking for some prior art. Commented Mar 23 at 21:07