“I must create a system, or be enslaved by another man’s. I will not reason and compare: my business is to create.”
William Blake
Why Create a Language?
Why not? Creating is fun. But there are other benefits. A programming language encodes instructions for how to do something; the steps to perform, and the constraints that must be adhered to. Just like there are many different writing styles in the world of fiction, which yield different reading experiences, there are many different styles of specifying instructions. Language ties in to thought and emotions and the human experience. If you write your own programming language, you get to use the syntax and semantics that best align with your way of thinking. You make deliberate choices about how your language is constructed, which gives you a deeper understanding of the choices and trade-offs that other language designers have made in their languages.
Why TypeScript?
At the moment, TypeScript is a great option for building a language. It is one of the most used languages, so that’s naturally a plus. More importantly, VS Code, one of the most widely used code editors, has great support for plugins written in TypeScript. VS Code allows you to provide language intelligence for your language by creating a language extension. The Language Server Protocol Specification (LSP for short) is written in TypeScript, and there is a corresponding node module to ease implementation. There are many extension samples written in TypeScript, including an LSP sample, which means you can get started seeing your language in action in VS Code quickly.
System Design
There are two main activities a language user performs.
- Editing – Writing valid statements in the language
- Executing – running the statements
With a text based language, we need to convert a raw stream of characters into something more meaningful for both of those activities. (That’s right, there are languages not based on text, a fun topic for another time).
To support an editing experience in VS Code, with features like autocomplete, find references, go to definition, and so forth, we need rich data structures that store the structure of the program defined by the text, with all its interconnections. This set of features
To support execution, we need data structures that support control flow, debugging, and remembering values to be used later.
The two activities of editing and execution have different needs, but there are common procedures and structures that can support both. The basic architecture might look something like this:
A Parser transforms the raw text, which is a stream of characters, into a Parse Tree. A Parse Tree is a data structure which stores information about each syntactic structure from the source text, including what kind of thing it is, and its location. For example, if you have an expression on line 3 of the text like let x = 5;, a parse tree might look like…
Assignment
Keyword "let" at 3,0
Variable "x" at 3,4
Operator "=" at 3,6
Integer "5" at 3,8
Semicolon ";" at 3,9This structure helps you answer common language questions more efficiently. A stream of 10,000 characters might be reduced to 1000 nodes, which is an order of magnitude reduction for the input space to algorithms that will operate against it. It also stores ‘what things are’, so you don’t need to apply syntax rules again to decide. If you want to know where the variable x is defined, you can search through the tree for Assignment nodes, which have a child Variable node with value x. If you want to implement Code Folding, where you collapse structures like functions and conditional blocks in your editor, the parse tree tells you where those blocks are in the document. For further performance gains for these operations, you might feed the parse tree into an indexer for even faster lookup.
The parse tree is focused on syntax, and preserves information about every element from the source text, with detailed location data. We don’t need all that information for execution, and we may not need all that information for many editing features. We can transform the Parse Tree into an Abstract Syntax Tree. An Abstract Syntax Tree (or AST for short) is more about the semantic structure; the statements and the data we need to execute those statements. Continuing our example with an expression on line 3 of the text like let x = 5; , the AST might be…
Assignment at line 3
Target "x"
Value "5"We no longer have the assignment keyword, the equals operator, or the statement terminating semicolon. We have also lost the character locations. We keep the line number, because when if the statement fails during execution, we need to direct the user to the failing line in the source text so they can fix the error. Again, we have reduced the size of our data structure, so memory storage requirements are lower, and the input space for algorithms operating against it is smaller. We have also removed the dependency on specific syntactical elements, which means we can freely change syntax without needing to modify the AST. All of the following syntax variations could produce the exact same AST node:
- x = 5
- int x = 5;
- var x = 5;
- Henceforth, the esteemed variable x shall hold as its value, the number five.
The AST can be directly executed by a Tree Walking Interpreter, or it can be further transformed for use in more efficient execution techniques, like a Bytecode Interpreter.
The Parse Tree is typically only needed for the Editing Experience, because it focuses on syntax. The AST may be used for both. The Parser, the Editing Experience, and the Execution Experience are each complicated systems that we will break down and explore further as we go along.
Next Time…
We’ll continue the system design by looking at the Editing Experience in more depth so we can understand how the Parse Tree feeds in.
