Abstract Syntax Trees: They're Actually Used Everywhere -- But What Are They?

Isn't it wonderful how VS Code grays out obsolete lines of code? Oops, my return statement is on line 3. Line 4 won't run... But I haven't called the function yet. So how in the world does VS Code know which lines of code won't be used in the future, when the code finally does run?

If we have a conditional statement, VS Code accurately evaluates the potential for us to hit the code outside of it:

bool could turn out to be false after all. But if we change the condition to true VS Code knows we will always run that block and (if there is an inevitable return inside) never reach the final line:

It's almost as if VS Code has the ability to understand the semantics of code. But under the hood VS Code uses code to do this! How?

Enter: Abstract Syntax Trees (ASTs)

An AST is a data structure that encodes abstract information about a piece of code.

This one is specifically for the above sample code declaring function foo(bool).

An AST is a "tree", which is a kind of graph. And a graph is a very useful type of data structure, ubiquitous in software engineering. In order to understand ASTs we have to understand graphs. (You can also skip ahead to learn more about ASTs or look at these tools to make and use an AST yourself.)

How Do Graphs Work?

Graphs consist of "nodes" and "edges", and can be represented by (often nested) objects or arrays. A graph can mix objects and arrays as well, nesting one kind within the other to whatever degree of complexity.

Each node and edge can contain information. You can travel from one node to another via the edge between them. Edges have direction as well. Here's a simple graph connecting node A to node B:

At a very basic level, if you were to write this in Javascript, it could look like this:

[ ["A", ["B"] ], [ "B", [] ] ]

or

{ 
   A: { value: data_set1, children: ["B"] }, 
   B: { value: data_set2, children: [] }
}

You can flip the direction

Resulting in code like this:

[ ["A", [] ], [ "B", ["A"] ] ]

or this

{ 
   A: { value: data_set1, children: [] }, 
   B: { value: data_set2, children: ["A"] }
}

And you can make the edge bidirectional, usually represented with a plain line with no arrows.

With code that does something like this

[ ["A", ["B"] ], [ "B", ["A"] ] ]

or this

{ 
   A: { value: data_set1, children: ["B"] }, 
   B: { value: data_set2, children: ["A"] }
}

These are simple examples, and in practice graphs can encode large amounts of data. Google displays search results with the help of a page rank graph, for example. This is a simplified representation of one:

Graphs can also have certain constraints. We can say: "The graph will start with exactly one node and every node except the first will have exactly one parent. Nodes can have multiple children though."

This is an example of one kind of tree. In general, a tree branches out. Every node after the first (root node) has exactly one parent. Trees are hierarchical and do not contain loops. (Graphs can have loops, and do not necessarily have a root node.)

But for now we'll focus on trees. Because when we build an AST, we take abstract syntactical data from code and encode it into a tree.

AST Design Standards & Traversal Functions

Because ASTs are often used in the process of compiling code (which happens all the time - every time you try to run any code), AST design standards are fairly robust. Compilers (and interpreters) essentially take the code we write (in Javascript, Python, Ruby, or C++) and turn it into machine-language instructions that a computer's CPU can run.

AST design standards include:

• variables (and their declaration locations in the source code) must be preserved
• the order in which statements get executed is well defined and preserved
• in the case of binary operations, left and right positioning is preserved
• identifiers and their values are stored

Ultimately, broken code cannot be turned into an AST. In the process of building the AST, we might come across errors like missing brackets, untyped variables (as in Typescript), or other syntactic mistakes. Instead of proceeding, we can flag these errors and display them to users for correction.

But once we successfully build an AST, it should be possible to unparse an it into something very similar to the original code, using a code generator. And the resulting code should definitely function exactly the same as the original code.

For example, using an AST like this ...

We could rebuild code that would look something like this:

function euclid(a,b) {
   while (b !== 0) {
      if (a > b) { a = a - b; } 
      else { b = b - a; }
   } 
   return a;
}

So we can take a piece of code, turn it into an AST, and eventually turn that back into code. But wait ... there's more: The function we use to step through the AST (called an AST traversal function) is intelligent enough to make sense of the semantic encodings and help us do useful things with that information.

We can use an AST traversal function to walk along the structure to discover "dead branches" (pieces of code that will never run).

Tree Shaking & More

Tree shaking refers to dead-code elimination in Javascript. In order to tree shake, we would combine the use of an AST and an AST traversal function to find which "branches" of code are "dead". This is how VS Code grays out unused lines of code. Tree shaking then eliminates those unused lines of code, for a cleaner, leaner code base.

When a code base is sufficiently large, dead-code elimination is necessary. Dead ends become dead weight, potentially causing worse performance if the product is shipped and bloated code in much need of pruning. (Amusingly, that's not a pun. That's what they call it! I came across many articles on tree pruning in writing this post though.)

There's incentive on both ends, as wet code is more confusing for developers as well.

The same traversal function can, interestingly, help us inject our own code into a given chunk of code according to preset rules if we wanted. (More about this in the follow up below.)

Tools To Make And Use An AST

Create an AST: Esprima

Traverse that AST and replace or inject code: Extraverse

Unparse the modified AST back into Javascript: Escodegen

ASTs vs CPTs

I mentioned earlier that ASTs are used in the process of compiling or interpreting. There is an alternative: Concrete Parse Tree. Unlike ASTs, CPTs include much more granular (potentially unnecessary) information. ASTs can omit some syntactic information like grouping parentheses, because of the way in which the structure of an AST already encodes that information.

CSTs are much bigger than ASTs. But the tradeoff is that they can aid in more efficient compiling. In practice, both are used.

Follow Up

My fascination with ASTs was inspired by an app I'm working on: a Big O (time complexity) calculator.

In my research on Big O approximation, I found that most tools calculate the amount of time a machine takes to run a function on different sized data sets. They use the resulting amounts of time to determine whether the rate of growth of time is sublinear, linear, exponential, etc.

I hope to create a tool that will count the number of actions taken (rather than the amount of time for a specific machine), so that for any snippet of code I can point to the most costly lines and indicate how many times they ran. This can help students learn Big O with a more concrete understanding of what's happening with their code.

The Halting Problem

Slightly outside the scope of this article, but cool enough to include: In 1936, Alan Turing (pictured at age 16, below) proved that it is impossible to write code that can examine another piece of code and its input, and tell whether or not it will ever terminate. This is called the halting problem.

For this reason, code entered into the Big O calculator can run too long in an infinite loop, and lock up a user's computer. I plan to bake in a fail-safe for that.

We'll See What's Possible

I'd eventually like to expand the project into a more comprehensive teaching tool. For now, I've scoped the project to the calculator to see if it's viable.