Abstract Syntax Trees: They're Actually Used Everywhere -- But What Are They?
Tags: javascript, vscode, webdev, beginners
Published: 2021-11-17 21:02:00

Isn't it wonderful how [VS Code](https://code.visualstudio.com/) 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?

![Code snippet of a function in VS Code with line 4 grayed out](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n37rbnd7xpc7iyf3kcxx.png)

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

![Code snippet showing that VS Code knows that an if statement with an unknown conditional might not run](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5nmqkgsugr8stdumtd9v.png)

`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:

![Code snippet showing that VS Code knows that an if statement with a true conditional will always run](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/czrc9sgdf3ibbmgz9pxl.png)

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.

![an AST object of the above code](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/99b0l2z3twokjltcegwa.png)

*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](#ASTs) or look at these tools to [make and use an AST](#tools) 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:

![Simple graph showing A to B](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jmek3jl2ome6q4u6di4w.png)

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

![Simple graph showing B to A](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8h2ybtaok1zyly9arp8g.png)

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.

![Simple graph showing a bidirectional relationship between A and B](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/eyfw9nvrc10ygznonowq.png)

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](https://en.wikipedia.org/wiki/PageRank) graph, for example. This is a simplified representation of one:

![Simplified rank graph example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/d9hqfj7k3f4cw6dt6x3u.png)

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."

![image of a tree data structure](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/d4gzvq8vsglgz9d5yw0q.png)

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.
<span id="ASTs"></span>
## 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 ...

![representation of generalized AST as graph showing the kinds of information each node and edge contain](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uqij99vqzf9ww5193cks.png)

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.)
<span id="tools"></span>
## Tools To Make And Use An AST

Create an AST: [Esprima](https://esprima.org/)

Traverse that AST and replace or inject code: [Extraverse](https://github.com/estools/estraverse)

Unparse the modified AST back into Javascript: [Escodegen](https://github.com/estools/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](https://en.wikipedia.org/wiki/Halting_problem).

![Alan Turing, age 16](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ve3gu6l2mnpib5gsobex.png)

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.