Writing My Own Language - Conclusion

I decided to write my own programming language to solve 2024 Advent of Code. This includes an interpreter, syntax highlighting, and a language server. In the first part, we looked at how the interpreter works. In the second part, we looked at how syntax highlighting is implemented.

In this part we’ll take a look at the basic idea behind the LSP implementation and how the language performed for solving 2024 Advent of Code.

Language Server Implementation §

My language server implements the following features:

• Go to Definition
• Find References
• Document Highlight
• Hover
• List Document Symbols
• Completion Recommendations

When I started this project, I thought I would be able to reuse much of the compiler logic to analyze the AST for the above queries. However, it turned out that the compiler logic had nothing to do with the AST analysis required for these queries.

I came up with two data structures to resolve these queries: ¹

• Document Symbol Tree - A tree of symbols used to provide completion recommendations.
• Location Data - An array of data connected to document locations, used for all other queries.

Document Symbol Tree §

This is a simple data structure - a tree of document symbols. Each document has an array of symbols. A symbol contains location data, a name, a kind (function/variable), and an array of children. The children are document symbols within the scope of the parent symbol.

Let’s look at an example:

foo = 420

bar = fn() {
    baz = 42
}

In this example, document has two symbols:

• foo
• bar

The symbol foo has no children, whereas bar has baz as a child.

Getting Completion Recommendations §

To get completion recommendations, the text editor sends the language server the cursor location. With the document symbol tree constructed, we can easily retrieve all symbols that are reachable from the cursor’s location. We then rely on the text editor to filter and sort the recommendations ².

Constructing an array of available document symbols is easy. We just iterate through all symbols and, depending on their location, either:

• Include the symbol (if it appears before the cursor).
• Retrieve the symbol’s children (if the cursor is inside a function’s scope).
• Exclude the symbol (if it appears after the cursor).

Location Data §

This is an even simpler data structure - just an array of data connected to document locations, sorted by location. Because it’s sorted, we can query it using binary search.

As an example, let’s take a look how “go to definition” is implemented. All other queries follow a similar pattern.

During document analysis, we check whether an identifier has already been defined. If it has, we add its definition’s location to the location data array. If not, we mark it as defined and store the definition’s location.

The result is an array of all symbols and their definition locations, sorted by their position in the document. To find where a symbol is defined, we simply locate the identifier at the cursor position using binary search and return its definition’s location.

Using the Language §

I tested the language’s usability by solving Advent of Code 2024 with it. I knew I wouldn’t have time to complete the entire Advent of Code, especially since I was also busy with a new side project. That’s why I decided to solve only the first 10 days. If you’re interested, the solutions are available on my GitHub.

After solving the first 10 days with the language, I would say it definitely passed the usability test. It isn’t anywhere near a production-ready language, but it was a very fun side project where I learned a lot. It’s also a side project I can comfortably mark as finished and move on to the next one :)