Abstract Syntax Trees: They're Actually Used Everywhere -- But What Are They?
source link: https://dev.to/aruna/abstract-syntax-trees-theyre-used-everywhere-but-what-are-they-jh6
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Posted on Nov 17
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", [] ] ]
{
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
It should be possible to unparse an AST object into something very similar to its 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), syntax errors (e.g. missing curly braces), or untyped variables (as in TypeScript).
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 find and flag errors (e.g. missing close bracket, or missing function name) in code editors. It can also, 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.
Recommend
-
32
A ST is an acronym for Abstract Syntax Tree. It is a representation of tokens generated from statements and expressions in a programming language. With the AST, the interpreter or the compiler can generate...
-
15
Abstract Syntax Forestry An EmberConf 2020 workshop from simplabs to teach you the basics about Abstract Syntax Trees. Before we begin, there are three things you'...
-
6
Pretty-print syntax trees with this one simple trick prettyprintI want to share a simple trick for pretty-printing syntax trees with the correct precedence that I’ve been using in my own interpreter projects. I believe this...
-
9
Abstract Syntax Tree 抽象语法树简介在使用前端许多工具插件的时候,我们大多知道每个工具库、每个插件能做什么,不过很多同学其实并不清楚背后用到的技术,如webpack、rollup、UglifyJS、Lint等很多的工具和库的核心都是通过Abstract Syntax Tree 抽...
-
12
Anonymous types can actually be used as targets for deserialization. · GitHub Instantly share code, notes, and snippets. Anonymous types can actually...
-
2
Programmer and Software Interview Questions and AnswersWould you like to thank ProgrammerInterview.com for being a helpful free resource? Then why not tell a friend about us, or simply add a link to t...
-
3
Erlang & ASN.1(Abstract Syntax Notation One)"Many programs don't have a well-defined interface. They should have." — Joe Armstrong.Hi folks! Ukrainian Erlanger is here 🤘!...
-
3
12 tool gifts that will actually get usedJean LevasseurTue, April 19, 2022, 1:15 AM·9 min read
-
0
June 27, 2022 ...
-
3
36 countries now have more trees t...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK