DEV Community: Segni Adeba

Building a Development Environment for Monkey: Part 3 - Solving an Advent of Code problem

Segni Adeba — Sat, 24 Oct 2026 16:33:47 +0000

Intro

We are finally done with building the development environment for Monkey after Part 1 and Part 2 of our series, by adding syntax highlighting with Tree-sitter and building a Language Server for it from scratch in Go respectively. If you haven't already I suggest you check them out.

In the final entry of the series we will put Monkey to "real" work, solving an AoC problem (2024 - Day 1). Attempting to solve this problem will quickly reveal how limited Monkey is, how the Tree-sitter corpus and all the LSP unit tests missed some bugs and how we had to improve upon the language by going back to our previous two projects. Finally, we will also look closely at the solution's performance.

The following are some of the key findings:

The LSP had a typed nil interface bug that broke all language features inside if blocks without an else block.
Monkey's lexer didn't read escape characters correctly while reading/lexing string literals.
Monkey is ~1000x slower than Go (2317 ms vs 2 ms).
Monkey allocates ~2000x more memory than Go (232 MB vs 118 KB per op).
~83% of CPU time is inside the interpreter's Eval loop.
~39% of all allocations come from creating a new Environment per function call.

The AoC problem and solution

For brevity, I won't dump the interesting story behind the problem itself here since AoC problems tend to have rather long mythical stories.

The problem has two parts and they both have a similar input file: 1000 lines of two columns of numbers separated by three white-space characters. An example input:

Part one

The problem is stated as follows:

Pair up the smallest number in the left list with the smallest number in the right list, then the second-smallest left number with the second-smallest right number, and so on.

Within each pair, figure out how far apart the two numbers are; you'll need to add up all of those distances.

The naive algorithm of my solution is as follows:

Sort both columns in a non-decreasing order.
Iterate over the two columns simultaneously, and in the iteration we sum up the absolute difference between each column for each line.

Part two

The problem is stated as follows:

This time, you'll need to figure out exactly how often each number from the left list appears in the right list. Calculate a total similarity score by adding up each number in the left list after multiplying it by the number of times that number appears in the right list.

The algorithm to my naive solution: To find the similarity score, for each number in the first column, we count it in the second column and multiply that count with the number. The sum of all of these products will be the solution.

The efficient solution would be to build a frequency map the numbers in the right column first and then using it to find the counts of the numbers in the first column with a cheap hash map lookup.

We will stick to the naive O(n^2) solution to put Monkey to more work, which will help us observe its flaws far better than if we went with the efficient solution.

Monkey's limitations

First and foremost we need to read the input file and Monkey does not have a way to do that. We also need to do some string manipulations on the input text like splitting and trimming. Since the input is read as a string, we need a way to convert the string numbers into integers. As we saw in our solution for part one, we also need a way to sort an array of numbers. Other major issues include:

no for loops - we have no keywords to iteratively run a code snippet or loop over iterable objects.
no variable re-assignment (only declaration) - which makes Monkey a "type-safe" language (when it comes to variables). But funnily enough not just limited to types, it's also "value-safe" because you cannot assign another value to an already declared variable.

Solutions to language limitations

Some limitations can be worked around while some require changes to the interpreter itself. For example we can solve the following without any changes:

Loops: We can use recursion to loop however we like. It only comes at the disadvantage of having O(n) space complexity. The bigger the loop, the deeper the recursion, the more stack memory used.
Variable assignment: This can be solved by simply declaring new variables or, in our solutions, just passing them into functions as arguments to be updated through calls.

But when it comes to other limitations such as reading a file, string manipulations, ASCII to integer conversion or sorting, I resorted to just adding more built-in Monkey functions. In other words, doing them in Go, which may seem like cheating but implementing some of these things in Monkey is way more than what I'm currently willing to do!

Monkey updates: built-in functions and more

The following are the new Monkey built-in functions I had to add in order solve this AoC problem.

readFile

This function accepts the path to the file as a string and returns the full string content of the file. It uses Go's os.ReadFile function under the hood.

The main take away from implementing this and struggling with why it was reporting "file doesn't exist" is that a process's CWD is wherever the shell was when the program is launched. Running ./bin/monkey from the project root and relative paths resolve against the root; cd bin && ./run and they resolve against bin. The binary's location is irrelevant.

splitString

This function accepts a string as its first argument and the separator string as the second and it returns an array of strings. It uses Go's strings.Split function under the hood.

Unfortunately this wasn't the end of it, check out the following code: input.txt

1
2

main.monkey

let input = readFile("input.txt");
let lines = splitString(input, "\n");

puts(lines)
// Expected: ["1", "2"]
// Actual  : ["1/n2"]

When I tried to split a file into lines using splitString, the result was a single-element array containing the entire file.

Updating Monkey's Lexer to read escape sequences properly

The culprit turned out to be Monkey's Lexer, can you figure out what the issue is? lexer.go


// readChar() reads one character at a time from the input source code
func (l *Lexer) readString() string {
    position := l.position + 1 // advances the reader's position by one from the initial opening " of a string

    for {
        l.readChar()

        if l.ch == '"' || l.ch == 0 { // reached end of string or file
            break
        }
    }

    return l.input[position:l.position]
}

Our lexer did not handle escape sequences correctly, our second argument "\n" was lexed as two literal characters/bytes (\ and n) rather than the newline byte 0x0A (\n). This meant that splitString was searching for a two-character sequence that never appeared in the actual file content.

The fix was to rewrite readString in the lexer to decode escape sequences on the fly:

\n becomes a real newline
\t a tab
\\ a backslash, and
\" a quote
Unknown escapes are kept literally so that no data is silently lost.

lexer.go (see source)

func (l *Lexer) readString() string {
    var sb strings.Builder

    for {
        l.readChar()

        // end of string or file
        if l.ch == '"' || l.ch == 0 {
            break
        }

        // normal case
        if l.ch != '\\' {
            sb.WriteByte(l.ch)
            continue
        }

        // different paths depending on the next char
        switch l.peekChar() {
        case 'n':
            l.readChar()
            sb.WriteByte('\n')
        case 't':
            l.readChar()
            sb.WriteByte('\t')
        case 'r':
            l.readChar()
            sb.WriteByte('\r')
        case '"':
            l.readChar()
            sb.WriteByte('"')
        case '\\':
            l.readChar()
            sb.WriteByte('\\')
        default:
            sb.WriteByte('\\') // just writes \ by default
        }
    }

    return sb.String()
}

NOTE: Not only did we fix readString, but we also added escaping quotes to Monkey's strings, which was not possible before.

Updating Monkey's Tree-sitter to handle escape sequences properly

Monkey strings can properly use escape sequences after updating our Lexer but our Tree-sitter grammar does not.

This is what a Monkey string with escaped quotes looked like before the fix, not so great:

Let's look at how our grammar describes strings: grammar.js

string: _ => token(seq('"', /[^"]*/, '"')), // no escapes

It handles any character except for quotes. Lets fix this by adding a new rule escape_sequence: grammar.js

string: $ => seq('"', repeat(choice(
    $.escape_sequence, // \n, \t, \\, \"
)), '"'),
escape_sequence: _ => /\\[ntr"\\]/,

That's it.

It also turns out that there's a specific Neovim capture @string.escape (check Neovim docs) to handle escaped characters specifically, lets use that in highlights.scm:

(escape_sequence) @string.escape

The result:

Bellissima!

atoi

atoi accepts a string as an argument and returns a number, it uses Go's strconv.Atoi function under the cover.

sortInts

sortInts accepts an array of integers and returns it sorted in a non-decreasing order, it uses Go's slices.Sort function.

trimSpace

trimSpace accepts a string and trims leading and trailing white space, returning the resulting string. It uses Go's strings.TrimSpace internally.

trimSuffix

trimSuffix accepts a string and returns it without the provided trailing suffix string. It uses Go's strings.TrimSuffix internally.

Updating Tree-sitter to include our new built-in functions

We should update highlights.scm to highlight our new functions as built-ins with the @function.builtin capture.

((call_expression
  function: (identifier) @function.builtin
  (#any-of? @function.builtin "len" "first" "last" "rest" "push" "puts"
    "readFile" "splitString" "atoi" "sortInts" "trimSpace" "trimSuffix"))
  (#set! priority 130))

Yet another typed nil interface bug

As I was implementing the solution, I encountered the most elusive bug I have faced in the series so far. Consider the following monkey code:

if(true){
    puts("hello")
}

All three language features stopped working inside and also after the if block, all triggering these features caused the server to panic.

After inspecting the stack trace, the cause turned out to be the function FindASTNode(state.go) in the Monkey Language Server. FindASTNode received an interface value whose data word was 0x0 yet somehow survived my if node == nil guard at the very start of the function.

IfExpression.Alternative is declared as *ast.BlockStatement, and an if expression without an else leaves it as a nil pointer.

Boxing a (*ast.BlockStatement)(nil) into the ast.Node interface produces a non-nil interface wrapping a nil pointer. node == nil is false because the type word is set, the type switch still matches *ast.BlockStatement, and the walker happily de-references the empty struct causing a panic.

This exact mistake is mentioned in the Go Mistakes and How to Avoid Them book under mistake #45, Returning a nil receiver. state.go

func FindASTNode(node ast.Node, line, character uint) ast.Node {
    // This fails
    if node == nil {
        return nil
    }

    switch node := node.(type) {
    case *ast.BlockStatement:
        // Panic happens in this function, dereferencing the nil node
        if !positionIsInRange(node, line, character) {
            return nil
        }
        for _, stmt := range node.Statements {
            if n := FindASTNode(stmt, line, character); n != nil {
                return n
            }
        }

    case *ast.IfExpression:
        if n := FindASTNode(node.Condition, line, character); n != nil {
            return n
        }
        if n := FindASTNode(node.Consequence, line, character); n != nil {
            return n
        }

        // The issue, node.Alternative is nil
        return FindASTNode(node.Alternative, line, character)
    }

    return nil
}

The following fix of changing the if expression case suffices (see source):

case *ast.IfExpression:
        if n := FindASTNode(node.Condition, line, character); n != nil {
            return n
        }
        if n := FindASTNode(node.Consequence, line, character); n != nil {
            return n
        }

        if node.Alternative != nil {
            return FindASTNode(node.Alternative, line, character)
        }

        return nil
    }

We can also update our guard to be more capable using reflection as follows:

func FindASTNode(node ast.Node, line, character uint) ast.Node {
    if isNilNode(node) {
        return nil
    }
    // ...
}

func isNilNode(node ast.Node) bool {
    if node == nil {
        return true
    }

    v := reflect.ValueOf(node)
    switch v.Kind() {
    case reflect.Pointer, reflect.Interface, reflect.Slice, reflect.Map:
        return v.IsNil()
    }
    return false
}

The Monkey solution

All issues are now fixed, let's finally solve the AoC problem.

reading the input

We read the input similarly for both problems.

let content = trimSuffix(readFile("input.txt"), "\n")
let lines = splitString(content, "\n")

let prep = fn(i) {
    if (i==len(lines)){
        return {
            "colOne": [],
            "colTwo": [],
        };
    }

    let res = prep(i+1);

    let splitLine = splitString(lines[i], "   ");
    return {
        "colOne": push(res["colOne"], atoi(splitLine[0])),
        "colTwo":push(res["colTwo"], atoi(splitLine[1])),
    };
}

let res = prep(0)

trimSuffix applied on the input because editors sometimes add \n to the input text. prep accepts an iteration index to recursively prepare two integer arrays from lines, an array of strings where each string is a line from the input. The base case is the end of the input, when the iterator is equal to the number of lines.

The result is a hash-map with two keys, they should be self-descriptive enough.

part one

part1.monkey

// read input

let colOne = sortInts(res["colOne"]);
let colTwo = sortInts(res["colTwo"]);

let dayOne = fn(i, j){
    if (i==len(lines)) {
        return 0
    }

    let sum = dayOne(i+1, j+1);

    let diff = colOne[i] - colTwo[j];
    return sum + if(diff<0){ -1*diff }else{ diff };
}

puts(dayOne(0, 0))

We start by sorting both columns (integer arrays) with sortInts. dayOne accepts two iteration indexes and recursively sums up the absolute differences of numbers on each line. The base case is the end of the input; we return 0. Then the recursion stack unwinds calculating and returning the new sum starting from the end of the arrays.

Running this on the main input returns: 2580760, which is the actual solution. It worked first try!

part two

part2.monkey

// read input

let colOne = res["colOne"];
let colTwo = sortInts(res["colTwo"]);

let countNumInArray = fn(num, arr, i) {
    if (i == len(arr)){
        return 0;
    }

    if (num < arr[i]){
        return 0;
    }

    let res = countNumInArray(num, arr, i+1);
    return if (num == arr[i]){ res + 1 } else { res };
}

let dayTwo = fn(i){
    if (i == len(colOne)){
        return 0;
    }

    let sol = dayTwo(i+1);

    let num = colOne[i]
    let numCount = countNumInArray(num, colTwo, 0);

    return sol + (num * numCount);
}

puts(dayTwo(0))

The solution to the second part is a bit more involved compared to the first as it is for most AoC problems.

We start by grabbing the two columns from the input and sorting the second one, this will help us prune our search by stopping the count when a candidate number in the second column becomes bigger than the number we are counting from the first.

countNumInArray accepts a number, an array and an iteration index and recursively counts the number in the given array. The base case is the end of the input and it also has an early return to stop the count to continue past bigger numbers than the one we are counting.

dayTwo accepts an iteration index as input and recursively iterates over the first column of integers and each time, it counts the number at that index in the second column and returns the product of the number and its count in the second column.

Running this on the main input again returns: 25358365, which is the correct answer!

Performance

Even though our solutions to each problem produced correct answers, their performances leave much to be desired. The poor performance is especially noticeable when testing the solutions with the main 1000-line input.

In the following sections we will do some benchmarking to compare our Monkey solutions to their equivalent Go solutions. Afterwards, we will explore and try to diagnose where all the CPU time is spent by performing CPU profiling.

The Go solution is as follows:

func Parse(path string) (col1, col2 []int) {
    fileBytes, err := os.ReadFile(path)
    if err != nil { panic(err) }

    fileBytes = bytes.TrimSuffix(fileBytes, []byte{'\n'})

    for line := range bytes.SplitSeq(fileBytes, []byte{'\n'}) {
        splitLine := bytes.Split(line, bytes.Repeat([]byte{' '}, 3))

        num1, _ := strconv.Atoi(string(splitLine[0]))
        num2, _ := strconv.Atoi(string(splitLine[1]))

        col1 = append(col1, num1)
        col2 = append(col2, num2)
    }

    return col1, col2
}

func Abs(num int) int {
    if num < 0 { return num * -1 }
    return num
}

func Part1(col1, col2 []int) int {
    slices.Sort(col1)
    slices.Sort(col2)
    soln := 0
    for i := range len(col1) { soln += Abs(col1[i] - col2[i]) }
    return soln
}

func Part2(col1, col2 []int) int {
    // Could've done this with a frequency map, again, but let's keep the solution as close as possible to the Monkey version.
    slices.Sort(col2)

    soln := 0
    for _, num1 := range col1 {
        count := 0
        for _, num2 := range col2 {
            if num1 < num2 { break }
            if num1 != num2 { continue }
            count++
        }
        soln += num1 * count
    }

    return soln
}

Notice that the Go solution doesn't compromise by avoiding for loops in favor of recursion to try and close the gap to the Monkey solution. The one adjustment I made is in Part2, where I sort col2 and do a linear scan instead of using a hash map - this keeps the algorithm closer to Monkey's approach.

Raw time comparison: Monkey vs Go solutions

You can check out the benchmark test file at bench_test.go.

Using the 1000-line input file, we use the following command to run our benchmark:

$ go test -bench=. -benchtime=10s

The -benchtime flag allows us to set the duration of the benchmark, how long each benchmark should run.

Output:

goos: linux
goarch: amd64
pkg: github.com/SegniAT/monkey-language-interpreter/examples/AoC_2024/benchmark
cpu: Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
BenchmarkGoDay1Part1-8     12189     1032764 ns/op     121160 B/op     2029 allocs/op
BenchmarkGoDay1Part2-8      6582     1965238 ns/op     121160 B/op     2029 allocs/op
BenchmarkMonkeyDay1Part1-8   273     46781362 ns/op    19007745 B/op   55037 allocs/op
BenchmarkMonkeyDay1Part2-8     5     2317095265 ns/op  243211913 B/op  4325964 allocs/op
PASS
ok      github.com/SegniAT/monkey-language-interpreter/examples/AoC_2024/benchmark  49.902s

Reading the Benchmark Output

Before diving into the profiling data, let's establish a baseline. Below is the raw output from running the benchmarks. Each row represents one benchmark, and the columns break down the performance per operation:

Benchmark Name & GOMAXPROCS: The name of the benchmark, followed by the number of CPUs available to the Go runtime (e.g., -8 means 8 logical CPUs).
Iterations: The number of times the benchmark loop ran during the test duration.
ns/op: The average execution time per operation in nanoseconds. This is the primary measure of speed.
B/op: The average number of bytes allocated per operation. This measures memory pressure.
allocs/op: The average number of distinct memory allocations per operation. This is the key metric for understanding GC pressure.

A quick look at the numbers and code complexity

The following is the comparison for bench time of 10 seconds. Part One:

Stat	Go	Monkey	Diff
ops	12,189	273	x44
duration/op	1 ms	46 ms	x46
allocation size/op	118 KB	18,562 KB	x157
allocation count/op	2,029	55,037	x27
Part Two:

Stat	Go	Monkey	Diff
ops	6,582	5	x1,316
duration/op	1.9 ms	2,317 ms	x1,219
allocation size/op	118 KB	237,512 KB	x2,013
allocation count/op	2,029	4,325,964	x2,132

What could be causing such a stark difference, especially in memory usage and allocations? Let's take a closer look at the Monkey solution and look for hints.

Let's start with prep function since it's common to both part one and two.

let content = trimSuffix(readFile("input.txt"), "\n");
let lines = splitString(content, "\n"); // array of strings

let prep = fn(i) {
    if (i==len(lines)){
        return {
            "colOne": [],
            "colTwo": [],
        };
    }

    let res = prep(i+1);

    let splitLine = splitString(lines[i], "   ");
    return {
        "colOne": push(res["colOne"], atoi(splitLine[0])),
        "colTwo":push(res["colTwo"], atoi(splitLine[1])),
    };
}

let res = prep(0);

The function is called with an argument of 0 and recursively calls itself until the base case is hit. At the base case we return a new hash literal and then the call stack unwinds, this is where all the work is done.

splitString creates a new array for each line, in our case 1000 times. The function then returns a new hash literal with two keys where for each key a push function is called, which is not cheap since it copies the array, time complexity of O(n). The push function makes our prep function have a time and space complexity of O(n^2), compared to O(n) time complexity of the Go version. This is also the main suspect for the high memory allocation because of the n (count of lines) number of new hash literal creations.

After getting the two columns we do sorting in both cases, which has the time complexity of O(nlog(n)) leaving prep with O(n^2) to still be our bottleneck.

Coming to the actual solutions, part one is a linear recursive function that only does math. The space complexity would also be linear because of the call stack. Part two on the other hand has O(n^2) time and space complexity.

We can get an idea of what the performance bottlenecks are from looking at the code alone and doing time and space complexity analysis. But we must do profiling to really know where all the CPU time is spent and what causes the massive memory allocations. Is our algorithm too slow and inefficient or is the Monkey interpreter itself too much of an overhead?

We do CPU and Memory profiling in the following section. Our goal is to only investigate, not optimize the solutions or the Interpreter.

CPU Profiling to know where Monkey is CHOKING

The benchmark function we use to profile our solution lives in at bench_test.go. We'll only benchmark the Monkey solution to part two since it's the most glaring when it comes to raw execution time and memory allocation numbers.

We will use the following command to produce a CPU profile file:

$ go test -bench=BenchmarkMonkeyDay1Part2 -benchtime=10s -cpuprofile /tmp/cpu.out

Outputs the following and creates a CPU profile file at /tmp/cpu.out:

goos: linux
goarch: amd64
pkg: github.com/SegniAT/monkey-language-interpreter/examples/AoC_2024/benchmark
cpu: Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
BenchmarkMonkeyDay1Part2-8   5   2548156523 ns/op   243326184 B/op   4325995 allocs/op
PASS
ok      github.com/SegniAT/monkey-language-interpreter/examples/AoC_2024/benchmark      13.110s

We can use the following command to see the results in our browser:

$ go tool pprof -http=:8080 /tmp/cpu.out

This is what the Flame Graph looks like:

X-axis: the total sample count (which represents CPU time). The width of a block is proportional to how much CPU time it consumed.
Y-axis: the call stack (depth).

As expected most of our time is spent evaluating the source code:

evaluator.Eval: 7.33 s, 51.4%
evaluator.applyFunction: 2.54 s, 17.8%
evaluator.evalBlockStatement: 2.03 s, 14.2%

But these only account for 83.4% of the time spent, where is the rest?

The rest of the time is when the GC runs in a separate goroutine, functions such as runtime.gcBgMarkWorker, runtime.bgsweep etc. We're using up so much memory that 20% of our program's run time is the GC doing work.

Note: The CPU profiler is a sampling tool that runs for the duration of the benchmark and captures all code that executes during that window, including setup. Our b.ResetTimer() only affects the ns/op and allocs/op numbers (as we'll see in the Heap Profiling), not the profile's sampling window.

Now let's take a look at the Flat views of the functions/nodes called.

1. The Flat View ("Where is the CPU?")

Flat% is the percentage of total CPU time spent directly inside the function itself.

Command:

# Show only the top 20 functions sorted by flat time
$ go tool pprof -top -flat -nodecount=20 /tmp/cpu.out

Output:

File: benchmark.test
Build ID: f8e079acc9de3bb17d615a24edff6fbc81f4736f
Type: cpu
Time: 2026-10-08 11:19:36 EAT
Duration: 12.75s, Total samples = 14270ms (111.93%)
Showing nodes accounting for 8460ms, 59.29% of 14270ms total
Dropped 201 nodes (cum <= 71.35ms)
Showing top 20 nodes out of 129
      flat  flat%   sum%        cum   cum%
    2090ms 14.65% 14.65%    11910ms 83.46%  github.com/SegniAT/monkey-language-interpreter/evaluator.Eval
     870ms  6.10% 20.74%      870ms  6.10%  aeshashbody
     740ms  5.19% 25.93%     1810ms 12.68%  internal/runtime/maps.(*Map).getWithoutKeySmallFastStr
     450ms  3.15% 29.08%     2850ms 19.97%  github.com/SegniAT/monkey-language-interpreter/object.(*Environment).Get
     450ms  3.15% 32.24%     2370ms 16.61%  runtime.mapaccess2_faststr
     360ms  2.52% 34.76%      360ms  2.52%  runtime.nextFreeFast (inline)
     330ms  2.31% 37.07%      360ms  2.52%  runtime.tryDeferToSpanScan
     310ms  2.17% 39.24%     1810ms 12.68%  runtime.mallocgcSmallScanNoHeader
     300ms  2.10% 41.35%    11900ms 83.39%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalBlockStatement
     290ms  2.03% 43.38%     2920ms 20.46%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalExpressions
     290ms  2.03% 45.41%     3310ms 23.20%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIdentifier
     280ms  1.96% 47.37%      280ms  1.96%  runtime.memclrNoHeapPointers
     230ms  1.61% 48.98%      550ms  3.85%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalInfixExpression
     230ms  1.61% 50.60%      230ms  1.61%  runtime.memmove
     220ms  1.54% 52.14%      220ms  1.54%  runtime.procyieldAsm
     210ms  1.47% 53.61%      390ms  2.73%  github.com/SegniAT/monkey-language-interpreter/evaluator.isError (inline)
     210ms  1.47% 55.08%      210ms  1.47%  memeqbody
     210ms  1.47% 56.55%      270ms  1.89%  runtime.(*mspan).writeHeapBitsSmall
     210ms  1.47% 58.02%     2850ms 19.97%  runtime.mallocgc
     180ms  1.26% 59.29%      290ms  2.03%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIntegerInfixExpression

Look at the top of the Flat output:

14.65% : github.com/SegniAT/monkey-language-interpreter/evaluator.Eval
6.10% : aeshashbody
5.19% : internal/runtime/maps.(*Map).getWithoutKeySmallFastStr
3.15% : github.com/SegniAT/monkey-language-interpreter/object.(*Environment).Get
3.15% : runtime.mapaccess2_faststr

The single biggest cost is the evaluator.Eval function itself, this is expected since we are bound to have a very high count of recursive calls to it and we spend considerable time inside that function even though it involves just a big switch statement.

But if we look closely at the next four entries, they are all related to map look-ups.

aeshashbody is the CPU instruction Go uses to hash strings for map keys. It is eating 6.1% of our entire CPU time. The reason is the Monkey interpreter resolves variables by looking up strings (like i, lines, colOne) in a map[string]object.Object.
Then, look at the memory functions: nextFreeFast, mallocgcSmallScanNoHeader, memclrNoHeapPointers, memmove. They collectively account for another ~7% of flat CPU time.

The CPU is spending a lot of time hashing strings for variable look-ups and frantically moving memory around for allocations.

2. The Cumulative View ("Why is it slow?")

Cum% is the percentage of total CPU time spent in the function plus all functions it called.

Command:

# Show only the top 20 functions sorted by cumulative time
$ go tool pprof -top -cum -nodecount=20 /tmp/cpu.out

Output:

File: benchmark.test
Build ID: f8e079acc9de3bb17d615a24edff6fbc81f4736f
Type: cpu
Time: 2026-10-08 11:19:36 EAT
Duration: 12.75s, Total samples = 14.27s (111.93%)
Showing nodes accounting for 5.84s, 40.93% of 14.27s total
Dropped 201 nodes (cum <= 0.07s)
Showing top 20 nodes out of 129
      flat  flat%   sum%        cum   cum%
     2.09s 14.65% 14.65%     11.91s 83.46%  github.com/SegniAT/monkey-language-interpreter/evaluator.Eval
     0.09s  0.63% 15.28%     11.91
s 83.46%  github.com/SegniAT/monkey-language-interpreter/evaluator.applyFunction
     0.30s  2.10% 17.38%     11.90s 83.39%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalBlockStatement
     0.14s  0.98% 18.36%      6.02s 42.19%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIfExpression
     0.29s  2.03% 20.39%      3.31s 23.20%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIdentifier
     0.29s  2.03% 22.42%      2.92s 20.46%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalExpressions
     0.45s  3.15% 25.58%      2.85s 19.97%  github.com/SegniAT/monkey-language-interpreter/object.(*Environment).Get
     0.21s  1.47% 27.05%      2.85s 19.97%  runtime.mallocgc
         0     0% 27.05%      2.79s 19.55%  runtime.systemstack
     0.45s  3.15% 30.20%      2.37s 16.61%  runtime.mapaccess2_faststr
     0.11s  0.77% 30.97%      2.07s 14.51%  github.com/SegniAT/monkey-language-interpreter/evaluator.extendFunctionEnv (inline)
     0.74s  5.19% 36.16%      1.81s 12.68%  internal/runtime/maps.(*Map).getWithoutKeySmallFastStr
     0.31s  2.17% 38.33%      1.81s 12.68%  runtime.mallocgcSmallScanNoHeader
         0     0% 38.33%      1.75s 12.26%  runtime.gcBgMarkWorker
         0     0% 38.33%      1.67s 11.70%  runtime.gcBgMarkWorker.func2
     0.03s  0.21% 38.54%      1.67s 11.70%  runtime.gcDrain
     0.09s  0.63% 39.17%      1.49s 10.44%  runtime.newobject
     0.09s  0.63% 39.80%      1.47s 10.30%  github.com/SegniAT/monkey-language-interpreter/object.(*Environment).Set (inline)
     0.16s  1.12% 40.93%      1.37s  9.60%  runtime.mapassign_faststr
         0     0% 40.93%      0.93s  6.52%  runtime.gcDrainMarkWorkerDedicated (inline)

Look at these three numbers:

83.46% - evaluator.Eval: This is expected since the entire program runs inside this recursive function.
42.19% - evaluator.evalIfExpression: This is pretty huge. Nearly half of your interpreter's total execution time is spent evaluating if expressions. In Monkey, if is used for base cases and control flow. Every recursive call (prep(i+1), partTwo(i+1), countNumInArray(...)) hits an if check. Millions of conditional jumps are being evaluated as AST nodes rather than machine instructions like in compiled languages such as Go.
23.20% - evaluator.evalIdentifier: Almost a quarter of all time is spent just finding variables. This calls Environment.Get 19.97%), which does a map lookup.

Look at runtime.mallocgc 19.97%) and runtime.gcBgMarkWorker 12.26%). GC background workers alone account for ~20%; adding the allocator brings total memory-management CPU to ~32%.

Where are all the allocations and garbage coming from?

extendFunctionEnv 14.51%): Every function call creates a new enclosed environment.
object.(*Environment).Set 10.30%): Every variable declaration or assignment updates a map.
NewEnclosedEnvironment: Creating a map for every single recursive call.

The interpreter is spending 32% of its time cleaning up the memory it allocated. This is because every recursive call creates a brand new environment map.

Heap Profiling for confirmation

Just from CPU Profiling above we were able to figure out that the GC is doing a lot of work and we were able to deduce the exact reason there's so much garbage for the GC to collect: mainly creating a new environment on each function call. Now let's confirm this with Heap Profiling.

We use the -memprofile flag to create the Heap Profile file.

Command:

$ go test -bench=BenchmarkMonkeyDay1Part2 -benchtime=10s -memprofile /tmp/mem.out

Output:

goos: linux
goarch: amd64
pkg: github.com/SegniAT/monkey-language-interpreter/examples/AoC_2024/benchmark
cpu: Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
BenchmarkMonkeyDay1Part2-8  4  2540705147 ns/op  243217254 B/op   4325988 allocs/op
PASS
ok      github.com/SegniAT/monkey-language-interpreter/examples/AoC_2024/benchmark      10.508s

We can use the following command to see the results in our browser:

$ go tool pprof -http=:8080 /tmp/mem.out

We can take a look at the Flame Graph with sampling set to alloc_objects under SAMPLE since the GC deals with objects.

X-axis: the total allocated objects. The width of a block is proportional to how many objects are allocated.
Y-axis: the call stack (depth).

The following are the functions that account for ~99% of the object allocations:

84.4% - evaluator.Eval
7.7% - evaluator.evalBlockStatement
6.5% - evaluator.applyFunction

These are expected, let's scroll down and take a look at the rest of the graph:

The suspects from the CPU profile - NewEnclosedEnvironment and Environment.Set - are back at the top of the alloc list. Let's see their numbers more closely below.

1. The Flat View (The Smoking Guns)

Flat% tells us who is doing the allocating directly. This points the finger at the exact function and line of code. This is our "smoking gun."

Command:

$ go tool pprof -top -flat -sample_index=alloc_objects -nodecount=20 /tmp/mem.out

Output:

File: benchmark.test
Build ID: f8e079acc9de3bb17d615a24edff6fbc81f4736f
Type: alloc_objects
Time: 2026-10-08 14:27:14 EAT
Showing nodes accounting for 15357595, 99.41% of 15448453 total
Dropped 29 nodes (cum <= 77242)
      flat  flat%   sum%        cum   cum%
   4150735 26.87% 26.87%    4150735 26.87%  github.com/SegniAT/monkey-language-interpreter/object.NewEnvironment (inline)
   4104337 26.57% 53.44%    6267057 40.57%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalExpressions
   2981932 19.30% 72.74%   15443004   100%  github.com/SegniAT/monkey-language-interpreter/evaluator.Eval
   1922917 12.45% 85.19%    1922917 12.45%  github.com/SegniAT/monkey-language-interpreter/object.(*Environment).Set (inline)
   1114129  7.21% 92.40%    1114129  7.21%  github.com/SegniAT/monkey-language-interpreter/evaluator.init.func1
   1081360  7.00% 99.40%    1081360  7.00%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIntegerInfixExpression
      2185 0.014% 99.41%     136747  0.89%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalHashLiteral
         0     0% 99.41%   15443004   100%  github.com/SegniAT/monkey-language-interpreter/evaluator.applyFunction
         0     0% 99.41%   15443004   100%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalBlockStatement
         0     0% 99.41%    3309618 21.42%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIfExpression
         0     0% 99.41%    1081360  7.00%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalInfixExpression
         0     0% 99.41%    6073652 39.32%  github.com/SegniAT/monkey-language-interpreter/evaluator.extendFunctionEnv (inline)
         0     0% 99.41%    4150735 26.87%  github.com/SegniAT/monkey-language-interpreter/object.NewEnclosedEnvironment (inline)

Sorting by flat% shows the top functions physically calling mallocgc:

26.87% - object.NewEnvironment: 4.15 million objects!
26.57% - evalExpressions: 4.10 million objects!
12.45% - Environment.Set: 1.92 million objects!
7.21% - init.func1: 1.11 million objects!
7.00% - evalIntegerInfixExpression: 1.08 million objects!

NewEnvironment is creating a new map for every single recursive function call. Because Part 2 has an O(n^2) algorithm, it calls functions millions of times creating millions of maps.
evalExpressions is allocating a slice every time it evaluates a list of arguments (like function arguments or array literal elements).
Environment.Set is allocating an object every time a variable is declared (like let res = ...).
init.func1 is a builtin function - almost certainly Monkey's push function allocating a new array on every single call. It's named func1 since it's an anonymous closure. It's under init since we defined builtins map globally.

2. The Cumulative View (The General Trend)

Cum% tells us the total cost of a subsystem. It shows you how individual allocations roll up into a massive total. This is the "macro trend."

Command:

$ go tool pprof -top -cum -sample_index=alloc_objects -nodecount=20 /tmp/mem.out

Output:

File: benchmark.test
Build ID: f8e079acc9de3bb17d615a24edff6fbc81f4736f
Type: alloc_objects
Time: 2026-10-08 14:27:14 EAT
Showing nodes accounting for 15357595, 99.41% of 15448453 total
Dropped 29 nodes (cum <= 77242)
      flat  flat%   sum%        cum   cum%
   2981932 19.30% 19.30%   15443004   100%  github.com/SegniAT/monkey-language-interpreter/evaluator.Eval
         0     0% 19.30%   15443004   100%  github.com/SegniAT/monkey-language-interpreter/evaluator.applyFunction
         0     0% 19.30%   15443004   100%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalBlockStatement
   4104337 26.57% 45.87%    6267057 40.57%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalExpressions
         0     0% 45.87%    6073652 39.32%  github.com/SegniAT/monkey-language-interpreter/evaluator.extendFunctionEnv (inline)
         0     0% 45.87%    4150735 26.87%  github.com/SegniAT/monkey-language-interpreter/object.NewEnclosedEnvironment (inline)
   4150735 26.87% 72.74%    4150735 26.87%  github.com/SegniAT/monkey-language-interpreter/object.NewEnvironment (inline)
         0     0% 72.74%    3309618 21.42%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIfExpression
   1922917 12.45% 85.19%    1922917 12.45%  github.com/SegniAT/monkey-language-interpreter/object.(*Environment).Set (inline)
   1114129  7.21% 92.40%    1114129  7.21%  github.com/SegniAT/monkey-language-interpreter/evaluator.init.func1
         0     0% 92.40%    1081360  7.00%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalInfixExpression
   1081360  7.00% 99.40%    1081360  7.00%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalIntegerInfixExpression
      2185 0.014% 99.41%     136747  0.89%  github.com/SegniAT/monkey-language-interpreter/evaluator.evalHashLiteral

Sorting by cum% shows the subsystems responsible:

40.57% - evalExpressions: 6.26 million objects!
39.32% - extendFunctionEnv: 6.07 million objects!
26.87% - NewEnclosedEnvironment: 4.15 million objects!
21.42% - evalIfExpression: 3.30 million objects!

Nearly 40% of all object allocations in the entire program come from one place: extendFunctionEnv. This is the function that sets up the environment for a new function call. Because our Part 2 algorithm is heavily recursive, this function is called millions of times and every call creates a new environment map.

Diagnosis: Interpreter Overhead vs. Language Design

Interpreter overhead: ~83% of time is spent in Eval + applyFunction + evalBlockStatement. That's the cost of the AST tree-walking nature of the interpreter itself.

Environment churn: ~39% of all allocations come from extendFunctionEnv. That's a design choice of the interpreter: creating a fresh Environment per call.

Language design: The lack of loops forces O(n) recursion depth, which means O(n) environments. The lack of mutable arrays turns push into O(n) copying.

Verdict: It's both. The CPU profile shows the interpreter's tree-walking overhead dominates execution time (~83% in Eval). But the memory gap is a different story - the 2000x difference is driven by the language's design (no loops, immutable arrays) being amplified by the O(n^2) algorithm. The interpreter overhead is the cost of running any Monkey program; the language design is what makes this specific program catastrophic.

Conclusion

Even though we had to make a few improvements to the interpreter, like adding builtin functions which could be considered cheating, and fixing tricky bugs we were able to achieve our goal of solving an AoC problem with Monkey. We were able to navigate Monkey's limitations such as missing loop primitives and variable re-assignments to solve the two-part problem.

We were able to accomplish our initial goal but there's a noticable performance problem we had discovered. Our Monkey solutions were 46x and 1,219x slower compared to their Go counterpart for part one and two of the AoC problem respectively.

To know the exact reason why there's such big contrast between the two languages, we had to do CPU and Heap profiling. The story these profiling results told were that there's a huge memory/heap overhead (lots of allocations) and the CPU spends a lot of time allocating and cleaning up all the garbage. Due to the nature of our interpreter (AST tree-walker) and lack of loop primitives forcing us to resort to recursive Monkey function calls, it led to deep call stacks and millions of new environment creations per function call.

Adding native builtins is how every production interpreter handles I/O and performance-critical paths - it's not cheating, it's the standard extension mechanism. But it does mean part of the answer comes from Go, not from Monkey.

Monkey is barely capable on its own even for simple AoC problems let alone real problems. Yet it was more capable than I thought when I began this series creating a Tree-sitter highlighting and a Language Server after that. Capability is one thing but programs running at a reasonable efficiency is another, and Monkey is far from efficient.

This shouldn't stop us from sitting back and appreciating what we have built. To conclude this 3-part series, I'll leave you with a quote from a wise king:

The end of a thing is better than its beginning; The patient in spirit is better than the proud in spirit. Ecclesiastes 7:8

Building a Development Environment for Monkey: Part 2 - An LSP for Hover, Definition, Completion and Diagnostics

Segni Adeba — Sat, 03 Oct 2026 18:04:58 +0000

Intro

In the previous blog, the first entry of the series, we taught editors what Monkey looks like by adding syntax highlighting to Neovim using Tree-sitter. Syntax highlighting makes our source-code pretty but it only goes so far.

The next planned step in building the development environment is teaching editors what Monkey means, by introducing diagnostics, hover, go-to-definition and completion. That layer is the LSP.

This blog covers the actual steps I took to build an extremely basic but extremely helpful version. It includes the walls I hit and how I had to go and extend the already existing interpreter to help me implement LSP features.

You can find the full docs for Monkey and full LSP implementation in the Monkey repository.

What the LSP actually is (and what we're building)

Language Server is a server that provides language-specific functions that can communicate with development tooling, for example editors, over a protocol that enables inter-process communication. LSP (Language Server Protocol) on the other hand standardizes the way editors communicate with Language Servers.

Thanks to this protocol, we know exactly what editors send to Language Servers and the responses they expect to receive back.

The messages the editor and server exchange looks like the following.

Content-Length: ...\r\n
\r\n
{
    "jsonrpc": "2.0",
    "id": 1,
    "method": "textDocument/completion",
    "params": {
        ...
    }
}

All messages have two parts, separated by the \r\n separator:

Headers: consists header fields separated by \r\n. Currently Content-Length and Content-Type headers are supported.
Content: is the main body of the message which is just json, specifically JSON-RPC 2.0.

The messages that the Language Server receives from the editors can be of two types: request and notification. We can pick and choose what to handle and what to ignore. Some of them are absolutely necessary to handle.

But before we talk about the specifics of the messages, let's actually read them first. That is handled by the rpc package.

Step 1 - The RPC layer

The RPC layer deals with reading and writing LSP messages from and to the LS clients, often editors. The LSP communication mostly happens using the stdin and stdout files, but not limited to it.

Because of this, we will abstract functions using io.Reader and io.Writer interfaces from the standard lib. This will be very handy when it comes to unit testing as well. This practice is mentioned in 100 Go Mistakes and How to Avoid Them book under mistake #46, "Using a filename as a function input".

The writer half of it is pretty simple:

accept an argument of content which is a byte array (presumably JSON)
frame it with the header section of the message that includes Content-Length (the length of the byte array argument)
write the whole message to our writer interface

When it comes to reading, we can't just do json.Decode(io.Reader), an LSP message is not just JSON. It's framed as follows:

Content-Length: 42\r\n
\r\n
<42 bytes of JSON>

First attempt: `bufio.Scanner` with a custom `SplitFunc`

Following Learn By Building: Language Server Protocol, the first attempt uses bufio.Scanner and SplitFunc to neatly read each of our messages from the input as tokens.

scanner := bufio.NewScanner(os.Stdin)
scanner.Split(Split)

// type SplitFunc func(data []byte, atEOF bool) (advance int, token []byte, err error)
func Split(data []byte, _ bool) (advance int, token []byte, err error) {
    header, content, found := bytes.Cut(data, []byte{'\r', '\n', '\r', '\n'})
    if !found { return 0, nil, nil }

    // Content-Length: <number>
    contentLengthBytes := header[len("Content-Length: "):]
    contentLength, err := strconv.Atoi(string(contentLengthBytes))
    if err != nil { return 0, nil, err }

    if len(content) < contentLength {
        return 0, nil, nil
    }

    totalLength := len(header) + 4 + contentLength
    return totalLength, data[:totalLength], nil
}

This implementation reads the input until a full message has arrived, which is decided by the Split function, which advances depending on if the full message has been received.

This worked fine - until it didn't.

The problem

bufio.Scanner has a default token size limit of 64 KiB. Since an entire LSP message is one "token" under our SplitFunc, a large message (say, a big didOpen with a huge file) would blow up with:

bufio.Scanner: token too long

This shortcoming is mentioned in go doc bufio.scanner as follows, it even suggests a solution.

Scanning stops unrecoverably at EOF, the first I/O error, or a token too large to fit in the Scanner.Buffer. When a scan stops, the reader may have advanced arbitrarily far past the last token. Programs that need more control over error handling or large tokens, or must run sequential scans on a reader, should use bufio.Reader instead.

It is possible to change the token size limit and the initial buffer size that are set by default.

scanner := bufio.NewScanner(io.Reader)
scanner.Buffer(
    make([]byte, 64*1024), // initial buffer
    1024*1024,             // maximum token size: 1 MiB
)

The problem with this approach is that we're just pulling those numbers out of nowhere. Let's move on to the solution suggested in the Go docs.

The solution: `bufio.Reader` + `io.ReadFull`

This solution allows us to first read the headers line by line using bufio.Reader, which in-turn allows us to handle errors at a more granular level. After reading all the headers, we parse out our Content-Length, then allocate a buffer with size that number and use io.ReadFull to read the content part of the message until the buffer is full or an error occurs, then we return the content that we just read.

The following is the implementation.
rpc/reader.go

type Reader struct {
    rd *bufio.Reader
}

func NewReader(reader io.Reader) *Reader {
    return &Reader{
        rd: bufio.NewReader(reader),
    }
}

func (r *Reader) ReadMessage() ([]byte, error) {
    contentLength, err := r.readHeaders()
    if err != nil {
        return nil, err
    }

    content := make([]byte, contentLength)
    _, err = io.ReadFull(r.rd, content)
    if err != nil {
        if errors.Is(err, io.EOF) || errors.Is(err, io.ErrUnexpectedEOF) {
            return nil, ErrIncompleteMessage
        }
        return nil, err
    }
    return content, nil
}

func (r *Reader) readHeaders() (int, error) {
    // Omitted for brevity, this function reads from the input line-by-line with '\n' as the delimiter, handling reading all the headers and handling errors in a more granular way, check source.
}

The folks at Microsoft implemented their own version in typescript-go in a very similar way to this.

We now have a way of reading and writing LSP messages, but we don't exactly know what they look like, when we receive them, when or what we should respond with.

Step 2 - Protocol types (the boring part) and handlers

The next work is basically converting Typescript types specified in the LSP spec into Go structs in the protocol package. LSP is a big spec, so we will only include the minimum required types to achieve our goals.

Go's type system

One of the more frustrating parts of implementing LSP in Go is that the language's type system doesn't always map neatly onto the shape of the specification. LSP makes extensive use of inheritance-like relationships, optional fields, and union types using TypeScript, while Go has no direct equivalent of TypeScript's extends or tagged unions. Embedding and interfaces can approximate some of these relationships, but they don't always express the same structure.

For example, my base request type contains only the fields common to every request:

type Request struct {
    Message
    ID     int64  `json:"id"`
    Method string `json:"method"`
}

type HoverRequest struct {
    Request
    Params HoverParams `json:"params"`
}

The problem is that Request isn't really a complete LSP request on its own; its params depend on which concrete request it represents. It doesn't even signal that there should be one more field named params. In TypeScript, this relationship can be modeled more naturally through interfaces and extension. In Go, it becomes a collection of concrete types built around an incomplete base type, with the connection between them handled by the implementation.

Lifecycle message Initialize and server capabilities

We start by defining Request Message, Response Message and Notification Message types as structs. These comprise all types of messages exchanged between the client and the server, every other types extend these.

The lifecycle messages, as mentioned in the spec, begin with a request of method Initialize sent from the client to the server.

This is the very first message that we expect to receive and it includes a capabilities field which includes details of if and how the client supports features such as hover, completion etc. We are expected to return a response including the server information and also the InitializeResult type, which includes its very own capabilities, i.e capabilities the server supports or implements. In our case we return the following:

{
    "result": {
        "capabilities": {
            "textDocumentSync": 1,
            "hoverProvider": true,
            "definitionProvider": true,
            "completionProvider": {}
        },
        "serverInfo": {
            "name": "monkey-lsp",
            "version": "0.0.1"
        }
    }
}

With our response, we tell our client that we support the following:

Document sync of type 1 (full document sync). This means that the client will send the full text document each time there's a change. Type 1 may seem inefficient compared to type 2 (incremental document sync) but let's save that more complicated task for future me.
Hover provider: true, this tells the client that we can handle a hover request.
Definition provider: true, to tell the client that we can handle a definition request.
Completion provider is set to an empty object because it has some optional configurations that we could set inside, which we won't bother with for now.
Server info includes the name and the version of our Language Server.

Note: The client doesn't ask the server for something that the server has not specified in its capabilities. So, the client won't bombard our server with all types of requests.

The rest is mechanical translation. We now know the requests that we can expect from the client thanks to the server capabilities so we can define the request and response Go types for them by referring to the LSP spec. All the types are specified in the protocol package.

Handling Requests and Notifications

Our server uses the rpc package to first read the received message. It then figures out if the message is of a request or notification type depending if the message includes an ID, only requests include IDs. Then call their respective handlers depending on the method by passing content (and the ID in case of requests) to them. These handlers use the Go structs we defined above to read the incoming content of the message, do some work and then return a response using the proper LSP types.

We can now make sense of the shapes of the data we receive and send. We are now done with the building blocks and we can move on to what to do with those nicely structured messages we receive in the following steps.

Step 3 - State, Documents, and Diagnostics

Before we can do anything with the document open in the editor, we need to know about its current state on the server. We do this in the analysis package.

Document sync

Our server needs a way of knowing about the state of the current text document content in the editor. For this very reason, we have 3 helpful notifications for document synchronization in the spec.

DidOpen is sent from client to server to signal a newly opened text document. It includes the following relevant fields to us: uri, version and text.
DidChange is sent from the client to the server to signal changes to a text document. It includes the following fields: textDocument (identifier) and contentChanges.
DidClose is sent from the client to the server when the document gets closed in the client. It will only include textDocument (identifier).

We will store the state of the opened text document in our editor buffers using the following structures.

package analysis

type Document struct {
    Version int
    URI     string
    Content string

    AST     *ast.Program
    parser  *parser.Parser
}

type State struct {
    // key is URI of the text document
    Documents map[string]*Document
}

Document represents an opened text document with the information we receive in the DidOpen notification. It also includes AST and parser field imported from our interpreter used to parse the Content. The server will have a single State object and is able store and process multiple open documents.

The server updates it's state whenever it receives the three document sync notifications listed above.

DidOpen and DidChange either create a new document or update an existing one identified by its uri.
DidClose deletes a document from the server state using the given uri.

Diagnostics

The DidOpen and DidChange notifications are good set of events on when to send some diagnostics back to the client, they could be errors, warnings, information etc. The server can publish a diagnostics notification to the client (see spec).

Diagnostics notification the client expects has the following shape:

type PublishDiagnosticsParams struct {
    URI         string       `json:"uri"`
    Version     int          `json:"version"`
    Diagnostics []Diagnostic `json:"diagnostics"`
}

type Diagnostic struct {
    Range    Range  `json:"range"`    // has `start` & `end` Position: {Line, Character} fields
    Severity int    `json:"severity"` // 0-4 (Error, Warning, Information, Hint)
    Source   string `json:"source"`
    Message  string `json:"message"`
}

Our original interpreter's parser is already capable of reporting syntax errors as strings as it parses our source-code. But as we have seen above, diagnostics are more encompassing than errors with more information than just a message.

There's another problem though, diagnostics requires Range which is used by the editor to show exactly where in the source code a specific diagnostic message applies by usually underlining the specified range with different colors depending on the severity, red for errors and yellow for warnings, for example.

The Monkey parser reports errors faced in the parsing process as it's dealing with tokens, if the token is unexpected or incorrect, it adds an error to a list. It would be helpful to know the range of this problematic token for our LSP diagnostics implementation, but we have no way of knowing in our current implementation.

Extending Monkey tokens

As the original interpreter is limited, we need to add starting and ending positions to all Monkey tokens. We also need a way to store diagnostics that includes the message, range and severity.

The idea is to track and update where the current position of the lexer is on every byte read. Line number always increases when \n is met, while character number increases on each byte read then resets when we hit \n.

token/token.go

package token

type Token struct {
    Type    TokenType
    Literal string
    Range   Range // New - includes Start & End, both include Line and Character number
}

lexer/lexer.go

type Lexer struct {
    input        string
    position     int  // current position in input (points to current char)
    readPosition int  // current reading position in input (after current char)
    ch           byte // current char under examination

    line      uint // New - current line
    character uint // New - current column
}

func New(input string) *Lexer {
    l := &Lexer{
        input:     input,
        line:      1,
        character: 0, // we begin at 0 since we call readChar below, which advances our cursor and sets this to 1
    }
    l.readChar()
    return l
}

func (l *Lexer) readChar() {
    if l.ch == '\n' {
        l.line++
        l.character = 1
    } else {
        l.character++
    }

    if l.readPosition >= len(l.input) {
        l.ch = 0 // ASCII code for the "NUL" character
    } else {
        l.ch = l.input[l.readPosition]
    }
    l.position = l.readPosition
    l.readPosition++
}

Now that our tokens each have their positions known, we can collect the diagnostics as follows during parsing:
token.go

// New type
type Diagnostic struct {
    Range    Range
    Message  string
    Severity DiagnosticSeverity
}

parser.go

type Parser struct {
    l           *lexer.Lexer
    diagnostics []token.Diagnostic // updated field

    // ...
}

// ...

// An example of how we collect diagnostics
func (p *Parser) parseIntegerLiteral() ast.Expression {
    literal := &ast.IntegerLiteral{Token: p.curToken}

    value, err := strconv.ParseInt(p.curToken.Literal, 0, 64)
    if err != nil {
        msg := fmt.Sprintf("could not parse %q as integer", p.curToken.Literal)
        p.diagnostics = append(p.diagnostics, token.Diagnostic{
            Message:  msg,
            Range:    p.curToken.Range,
            Severity: token.Error,
        })
        return nil
    }

    literal.Value = value
    return literal
}

Lines and Characters: 0 vs 1-based numbering

There was a decision we needed to make above: LSP positions are 0-based. But editors usually show lines and characters as 1-based numbers. I opted to use 1-based numbering for the Lexer and the Language Server's state analyzer.
We convert from 0 to 1-based numbers at the protocol boundary in translate.go and convert from 1 to 0-based when it's the other way around. Every diagnostic, hover, and definition range passes through that same conversion.

Syntax diagnostics are fairly easy. But hover, go-to-definition, and completion need to know what an identifier means - which let it refers to, whether it's a parameter or builtin.

There is no way to answer that without building a small semantic model of the program.

Step 4 - Static analysis: symbols, scopes, and the features built on them (the fun part)

Now that we have diagnostics, specifically errors, correctly being reported back to our editor and we can move on to implementing our three language features: hover, definition and completion.

This step is without a doubt the most interesting and challenging part of the entire project for me, but at the end, also very rewarding.

Let us look at what the shapes of requests and expected responses for each look like below.

Hover (see spec):

// REQUEST
{
    // ...
    "method": "textDocument/hover",
    "params": {
        "textDocument": { "uri": "file:///tmp/main.monkey" },
        "position": { "line": 2, "character": 5 }
    }
}

// RESPONSE
{
    // ...
    "result": { // optional
        "contents": {
            "kind": "markdown",
            "value": "```

monkey\nlet x = 42;\n

```"
        }
    }
}

In Neovim it is triggered with K and it shows an information on whatever is being hovered over.
We receive the document URI and exact position where the hover happens. We are expected to return a response with an optional content (markdown in our case) that has some information on the token under the cursor.

Definition (see spec):

// REQUEST
{
    // ...
    "method": "textDocument/definition",
    "params": {
        "textDocument": { "uri": "file:///tmp/main.monkey" },
        "position": { "line": 2, "character": 5 }
    }
}

// RESPONSE
{
    // ...
    "result": { // optional
        "uri": "file:///tmp/main.monkey",
        "range": {
            "start": { "line": 1, "character": 4 },
            "end": { "line": 1, "character": 5 }
        }
    }
}

In Neovim this is commonly triggered with g + d and it moves the cursor to the position in the code-base where the identifier under the cursor is defined.
We receive similar request params as Hover and we are expected to return an optional result including a file URI and a range (start and end position).

Completion (see spec):

// REQUEST
{
    // ...
    "method": "textDocument/completion",
    "params": {
        "textDocument": { "uri": "file:///tmp/main.monkey" },
        "position": { "line": 2, "character": 5 }
    }
}

// RESPONSE
{
    // ...
    "result": { // optional
        "items": [ { "label": "foobar", "kind": 6 } ]
    }
}

This request is triggered by typing in our editor. The request's content is similar to the above two, except here the position we receive is of the cursor's so it's one character off to the right of the text we are typing. The response includes an optional return field which includes a list of candidates to apply completion.

Our server as a response to these requests has to answer: what identifier is under the cursor?
If your intuition is to first find the AST nodes at the positions we get from the requests, then you're spot on!

But we immediately hit the wall here since our original interpreter's AST nodes do not have ranges defined to help us search the AST for what node exists at a specific position. We go back to our interpreter to extend it for the second time.

Adding `Start()` and `End()` on every AST node

Same trick as tokens, applied one level up. Every node already wraps a token or more so adding Start() and End() that return the token's range makes it trivial to walk the AST tree and find the smallest node containing a given position. The changes are as follows:
ast/ast.go

type Node interface {
    TokenLiteral() string
    String()       string
    Start()        token.Position // New
    End()          token.Position // New
}

Adding ranges to Monkey tokens earlier makes implementing these methods rather trivial. For example, If Expression AST nodes implement these as follows:

type IfExpression struct {
    Token       token.Token
    Condition   Expression
    Consequence *BlockStatement // BlockStatement implements Start() & End() itself
    Alternative *BlockStatement
}

func (ie *IfExpression) Start() token.Position { return ie.Token.Range.Start }  // New
func (ie *IfExpression) End() token.Position { // New
    if ie.Alternative != nil {
        return ie.Alternative.EndToken.Range.End
    }
    return ie.Consequence.EndToken.Range.End
}

Now we have a way of grabbing AST nodes from a parsed source code given a position in it using Depth First Search and the Start() and End() methods we just introduced.

Let's move on with our implementations for the three language features.

Implementing our language features and the problems we face

Hover

We can handle this request depending on the node under the cursor as follows:

String Literal: Show the length and size of the string in bytes.
Integer Literal: Show the hexadecimal, octal and binary representation of the number.
Boolean Literal: Show just the value.
Identifier: Show the type (variable, parameter or built-in function), name, and the position where it is defined.

We can implement the first three fairly simply, but the fourth one needs significantly more brain power to come up with a good enough solution for it. Consider the following scenario.

let num = 1;
puts(num);

Problem: If we hover over num on the second line, it should report back the position where the original is defined at, which we have no way of knowing currently.
The obvious and naive solution would be to traverse the AST again and to find the closest definition of this identifier to the position where the hover happened, in order to respect Monkey scopes. But this is inefficient to do on every hover request, we can do better.

Definition

We basically need to first find the node in the AST and if it's an Identifier node, we return the range where this identifier is defined.

Problem: We face the same exact problem as we mentioned above, we have no immediate way of knowing where this identifier is originally defined at in our source-code.

Completion

Completion needs more work to implement, we do the following in order:

get the full identifier that is in the process of being typed
know the deepest scope or function enclosing this identifier
build a list of candidate identifiers (identifiers that have current identifier as prefix) for the completion that are defined in the deepest scope enclosing the identifier and then unwind to go up the scopes up until the root scope where built-in functions and keywords are defined.

Problem: The two problems above were only about finding and searching for the closest definition of an identifier, but here we have a problem an order of magnitude bigger: we need to find multiple identifiers, but also that are in scope of the identifier before the cursor.

Before solving the problems listed above, we must do static analysis to help us solve these issues more efficiently.

Static analysis, symbols, symbol tables and diagnostics

Static analysis deals with inspecting the source code for semantic errors, style violations etc. In our case, we analyze our AST to collect our identifiers and all function scopes for quick access.

This will help us solve the problems mentioned in the previous section efficiently, since the analysis just happens once on text document open or update it allows every hover, definition or completion use the results of the latest static analysis.

We introduce a few more types in the analysis package.

analysis/scope.go

package analysis

// ...

type symbolType string

const (
    variable  symbolType = "variable"
    parameter symbolType = "parameter"
    builtin   symbolType = "builtin"
)

type symbol struct {
    Name       string
    Type       symbolType
    Range      Range
    Identifier *ast.Identifier
    Used       bool
}

type symbolTable struct {
    Outer   *symbolTable
    Symbols map[string]*symbol
}

symbol represents all identifier definitions including variables, parameters and names of built-in functions.
symbolTable stores symbols, the keys are their names and the values are the symbols themselves. It also has symbolTable.Outer field which will allow us to store symbols defined in the outer scope of the current symbol table.

We use the above to add some very important fields to Document struct.
analysis/state.go

type Document struct {
    // Version, URI, Content, AST, parser ... old fields

    rootScope      *symbolTable                          // New
    identifierUses map[*ast.Identifier]*symbol           // New 
    functionScopes map[*ast.FunctionLiteral]*symbolTable // New
}

rootScope stores our initial/root symbol table initialized with symbols of built-in functions.
identifierUses stores a map of pointers of all identifier nodes to their respective symbols.
functionScopes stores a map of pointers of all function literal nodes to their respective symbol tables.

Now for the main player that makes sense of all the types we have mentioned above.
analysis/analyzer.go (some sections are removed for brevity)

package analysis

import (
    "fmt"

    "github.com/SegniAT/monkey-language-interpreter/ast"
    "github.com/SegniAT/monkey-language-interpreter/token"
)

// analyze builds the document's symbol table, resolves every identifier into
// the Uses map, records every function scope in the Scopes map and returns
// semantic diagnostics for undefined, redeclared and unused names.
func (d *Document) analyze() []token.Diagnostic {
    d.rootScope = newRootScope()
    d.identifierUses = make(map[*ast.Identifier]*symbol)
    d.functionScopes = make(map[*ast.FunctionLiteral]*symbolTable)

    var diags []token.Diagnostic
    d.visit(d.AST, d.rootScope, &diags)
    diags = append(diags, d.unusedDiagnostics()...)

    return diags
}

func (d *Document) visit(node ast.Node, scope *symbolTable, diags *[]token.Diagnostic) {
    if node == nil { return }

    switch node := node.(type) {
    // cases *ast.Program and *ast.BlockStatement:

    case *ast.LetStatement:
        if scope.define(node.Name.Value, variable, node.Name) {
            *diags = append(*diags, token.Diagnostic{
                Message:  fmt.Sprintf("redeclaration of %s", node.Name.Value),
                Range:    node.Name.Token.Range,
                Severity: token.Error,
            })
        }
        d.visit(node.Value, scope, diags)

    case *ast.FunctionLiteral:
        child := newChildScope(scope)
        d.functionScopes[node] = child
        for _, param := range node.Parameters {
            if child.define(param.Value, parameter, param) {
                *diags = append(*diags, token.Diagnostic{
                    Message:  fmt.Sprintf("redeclaration of %s", param.Value),
                    Range:    param.Token.Range,
                    Severity: token.Error,
                })
            }
        }
        d.visit(node.Body, child, diags)

    // multipe cases removed for brevity

    case *ast.Identifier:
        if sym, ok := scope.lookup(node.Value); ok {
            sym.Used = true
            d.identifierUses[node] = sym
        } else {
            *diags = append(*diags, token.Diagnostic{
                Message:  fmt.Sprintf("undefined variable: %s", node.Value),
                Range:    node.Token.Range,
                Severity: token.Error,
            })
        }

        // *ast.IntegerLiteral, *ast.Boolean and *ast.StringLiteral are leaves.
    }
}

*Document.analyze gets called on events textDocument/didOpen and textDocument/didChange in order to analyze the latest source-code and return it's diagnostics.
*symbolTable.define adds a new symbol to the symbol table and returns true if it is re-declared in the same scope.
*symbolTable.lookup searches for a symbol by name in the proper scopes, starting from the current symbol table (scope) up to the root symbol table.
*Document.analyze initializes some fields and starts the tree walker that populates the newly added Document fields and returns diagnostics.

*Document.visit is the main function that walks our AST and does several distinct actions depending on the type of the node it encounters:

*ast.LetStatement: we define a new symbol using the node's name. If it is a re-declaration we add a new error diagnostic to our global diagnostics list.
*ast.FunctionLiteral:
1. We first create a new child symbol table using the current as parent.
2. We save this child scope's pointer into *Document.functionScopes using the function literal AST node's pointer as key.
3. We loop over the parameters and define symbols for each, if there's a re-declaration we add a new error diagnostic.
4. We visit the function's body with our newly defined scope as input.
*ast.Identifier: We lookup if a symbol exists with similar name, if so, we store the identifier to *Document.identifierUses using the node pointer as key and the found symbol pointer as a value. We also set *symbol.Used to true, we will find this useful later. If no symbol is found, we add an error "undefined variable" diagnostic to our global diagnostics list.

One last extra but useful thing is the method *Document.unusedDiagnosticscalled in *Document.analyze, its purpose is straight-forward: it collects warning diagnostics by going through every single symbol defined in all scopes of the source-code for unused symbols.

Note: Remember that we set a symbol's Used field to true when we come across an identifier in *Document.visit and if an identifier with the same name is found in the relevant scope/s.

We now have done all the work to finally implement our language features.

Hover, definition and completion implementation

Let's get straight to implementing our solutions now that we have overcome the latest blockers.

Hover

Source: analysis/state.go *State.Hover()

We first find the node at the specified position and then handle the request depending on the type of the node. The problem was that in case of hovering over identifiers, we did not have a good way to know the position where it is defined at.

We can now figure this out easily thanks to *Document.identifierUses. We use it to look-up the node's symbol and get the range off of it.

Definition

Source: analysis/state.go *State.Definition()

For Definition, we first find the AST node at the given position and we make sure that it's of an identifier type or we return early. We then look-up it's symbol in *Document.identifierUses and if we find a symbol we return it's range.

Completion

Source: analysis/state.go *State.Completion()

Completion does more work than the other two. After finding the exact identifier node, the next step is finding the deepest function node that encloses this identifier. From *document.functionScopes, we can get that function's symbol table, which also includes a pointer to its outer scope's symbol table. For each level of eligible scope, we go through the unique names of identifiers registered and check if the identifier being typed is a prefix to them, if it is we add it as one option for completion.

LSP has an option to differentiate what type of completion an item is, in our case we have three: Variable, Function and Keyword.
Most of our completion items will be of type Variable, even functions are defined using a let statement by assigning them to variables. Only built-in functions will have completion type Function and Keyword is for Monkey keywords such as if, let etc.

A design trade-off I hit while writing the analyzer

Our static analyzer has one flaw right now. For a let statement, it registers a symbol with the variable's name before visiting the right-hand side. This leads to failing to report "undefined variable" in the following case:

let a = a;

Suppose we fixed that by defining the symbol after visiting the right-hand side. Now consider:

let fib = fn(x) {
    if (x < 2) { return x; }
    return fib(x - 1) + fib(x - 2);  // fib not yet defined → error
};

Reporting an "undefined variable 'fib'" error here will hinder us from ever using recursion. Our interpreter can technically run the code without any problems but our Language Server will always report this as an error to our editor.

I chose to go with the current approach, i.e defining before visiting the right-hand side, because recursion is a first-class Monkey feature and self-reference is a footgun the programmer will notice immediately. Worth calling out as an explicit trade-off.

We are finally done with all the language features!

The `let` crash (a Go interface gotcha)

Excited, after implementing all the cool features of our Language Server I went right to testing. But I soon found out a bug that made my server crash.

Opening a file containing or typing the following:

let

If there ever is a let keyword alone without an identifier in the source-code, it crashes the server. I went digging through the stack-traces and finally figured out the problem! It was the following function in Monkey's parser.
parser/parser.go

func (p *Parser) parseStatement() ast.Statement {
    switch p.curToken.Type {
    case token.LET:
        return p.parseLetStatement()
    case token.RETURN:
        return p.parseReturnStatement()
    default:
        return p.parseExpressionStatement()
    }
}

When parseLetStatement returns (*ast.LetStatement)(nil), that pointer is wrapped in the ast.Statement interface, and an interface holding a typed nil pointer is not nil. Every downstream if stmt != nil check succeeds, and the first field access panics.

This exact mistake is mentioned in the Go Mistakes and How to Avoid Them book under mistake #45, Returning a nil receiver.

The solution is to return nil explicitly at the call site. We return a nil interface, not a nil receiver converted into a non-nil interface.
parser/parser.go

func (p *Parser) parseStatement() ast.Statement {
    switch p.curToken.Type {
    case token.LET:
        if stmt := p.parseLetStatement(); stmt != nil {
            return stmt
        }
        return nil // Explicitly returns untyped nil
    case token.RETURN:
        if stmt := p.parseReturnStatement(); stmt != nil {
            return stmt
        }
        return nil
    default:
        if stmt := p.parseExpressionStatement(); stmt != nil {
            return stmt
        }
        return nil
    }
}

Step 5 - Concurrency

The main loop of our server currently is single-threaded. While a hover request is being served, no notifications are being read. A slow request made the editor feel laggy, even worse, a long completion while the user typed meant didChange was queued behind it.

The solution to this is to dispatch request handlers in goroutines:
server/server.go

// ...
if isRequest {
    // Spin up a goroutine for read-only requests
    go func(reqID int64, reqMethod string, reqContent []byte) {
        defer func() {
            if r := recover(); r != nil {
                // ... logs error
            }
        }()

        s.HandleRequest(reqID, reqMethod, reqContent)
    }(*msg.ID, msg.Method, content)
} else {
    // Run notifications synchronously to guarantee state mutation order
    s.HandleNotification(msg.Method, content)
}
// ...

This solution however introduces a problem of its own. Now didChange notification (which mutates AST, identifierUses, functionScopes fields on Document) races against hover request (which reads identifierUses). Go's runtime map access detector could catch it, and could cause the server to fatally crash with a concurrent map read and map write message.

We must add a locking mechanism to our server's state to access and update these fields safely. We add a global sync.RWMutex to analysis.State.

analysis/state.go State

// ...
type State struct {
    mu        sync.RWMutex         // New
    Documents map[string]*Document
}
// ...

Write-lock on DidOpen, DidChange, DidClose.
Sources: analysis/state.go *State.DidOpen,
analysis/state.go *State.DidChange,
analysis/state.go *State.Close

func (s *State) DidOpen(...) []token.Diagnostic {
    s.mu.Lock()
    defer s.mu.Unlock()
    // ...
}

// DidChange and Close are similar to the above.

Read-lock on Hover, Definition, Completion.
Sources: analysis/state.go *State.Hover,
analysis/state.go *State.Definition,
analysis/state.go *State.Completion

func (s *State) Hover(...) *Hover {
    s.mu.RLock()
    defer s.mu.RUnlock()
    // ...
}

// Definition and Completion are similar to the above.

These additions solve the data race mentioned above.

Step 6 - Hooking up our server to Neovim

We should first add the monkey file type to Neovim, we have done the same in part 1 when adding our Tree-sitter to Neovim.

vim.filetype.add({ extension = { monkey = "monkey" } })

The final step is to configure and enable our LSP.

vim.lsp.config("monkey", {
    name="monkey-lsp",
    cmd= { "/path-to-LSP-binary/monkey" },
    filetypes = { "monkey" }
})

vim.lsp.enable("monkey")

Testing

All packages are extensively unit tested to ensure reliability.

Unit tests for the RPC reader
Analyzer tests: scopes, undefined vars, re-declaration, unused variables, closure capture.
Manual testing in Neovim:
- K for hover
- gd for go-to-definition.
- <CTRL + x><CTRL + o> for completion.
- Typing let alone to confirm the nil-interface crash is fixed.

Showcase

Let's now look at the final result of our hard work!

Diagnostics on text document open and change

Re-declaration of variables

Notice how variables are function scoped by the way the second sum variable is not being reported as a re-declaration. Also note that this diagnosis also catches parameter re-declarations as well.

Undefined variables

result is undefined in the above code snippet.

Unused variables

We can use an underscore (_) to ignore unused variables so that the LSP won't complain about them, inspired by Go.

Hover

Hovering over a builtin function puts, a string, a parameter, a variable, a number and a boolean shows different types of information.

Definition

This request is triggered with <g><r><d> key combination in my current Neovim setup.

Completion

The completion request is triggered automatically in my Neovim, but it can also be triggered manually with <C-x><C-o>.

Conclusion

Part 1 taught editors what Monkey looks like. This post taught them what Monkey means. Between the two, we went from syntax highlighting to hover, go-to-definition, completion, and diagnostics - all from scratch, in a language that had none of them two posts ago.

The timeline this post actually followed: RPC framing, protocol types and handlers, document state and diagnostics, extending the interpreter with token ranges, adding AST node ranges, static analysis, the three language features, concurrency and locking, and finally wiring it all into Neovim.

Two lessons that stuck with me:

Editor features aren't a single feature. Diagnostics looked trivial until I realized the parser had no way to point at a range in the file. Hover looked trivial until I realized the AST had no node positions. Everything looked fine until I made the server concurrent and noticed a possible data race. Each feature I added exposed a missing layer in the layer below it. None of those trips back to the interpreter were in the original plan. All of them were necessary.
The protocol boundary is where conventions get translated. LSP is 0-indexed; editors are 1-indexed. The protocol deals in wire types; the analyzer deals in analysis.Hover and analysis.Location. Every one of those conversions lives in exactly one place - translate.go. It keeps the analyzer free of protocol concerns and the protocol layer free of analysis concerns, and it's the architectural decision I'd keep if I had to rewrite this from scratch.

What's next: Once Monkey has enough of a dev environment to be pleasant to write in, I want to see what it actually feels like to solve a real Advent of Code problem with it. That's Part 3.

References

LSP specification (3.18)
Part 1: Tree-sitter grammar for Monkey
monkey-language-interpreter repository (includes LSP implementation in /lsp)
Go docs: bufio.Reader, io.ReadFull, sync.RWMutex
Go Mistakes and How to Avoid Them : the nil-interface gotcha, io.Reader/io.Writer abstraction

Building a development environment for Monkey: Part 1 - Syntax highlighting with Tree-sitter

Segni Adeba — Sun, 20 Sep 2026 14:54:48 +0000

Intro

A few years ago on a quest of learning Go, I followed Writing An Interpreter In Go and built Monkey, a small interpreted programming language. Recently, I came back to it with a different goal: I wanted to see how far I could take the language as an actual development environment.

My plan is to build the tooling around Monkey step by step: first syntax highlighting, then LSP support, and eventually use the language to solve an Advent of Code problem.

As we begin writing code in Monkey, we immediately notice that it lacks the editor features we have come to take for granted: syntax highlighting, diagnostics, navigation, completion, and more.
There is a lot of machinery behind features we take for granted, and I wanted to understand it by building it. This post is the first step: teaching editors how to understand Monkey's syntax using Tree-sitter, primarily for highlighting purposes.

Before building the tooling, we should first understand the language we are building it for. Monkey is small, but it has enough language features to build simple tooling around it that would teach us all the basics of parsing. The core functionalities and features in Monkey are the following:

Data Types: integers, booleans, strings, arrays, and hash maps.
Variables: created using let statements (e.g., let foo = 1;).
Operators: prefix (e.g., -, !) and infix operators (e.g., +, -, *, /, ==, !=, <, >) to evaluate arithmetic and boolean expressions.
Functions as First-Class Citizens: Functions can be bound to names, passed as arguments, and returned from other functions, allowing for higher-order functions.
Closures: fully supports lexical closures, meaning functions can capture and retain access to the variables in which they were defined.
Built-in Functions: includes pre-defined utility functions, such as len() (to get the length of strings or arrays), puts() (for printing to standard output), first(), rest(), last(), and push().

You can find the full docs of Monkey and full Tree-sitter implementation in the Monkey repository.

By the end of this post we'll have a Tree-sitter grammar that parses every construct in Monkey, tested against a corpus, and wired into Neovim.

Why Tree-sitter?

I decided on using it instead of the approaches most editors used for syntax highlighting before Tree-sitter, such as regular expressions, custom parsers, and lexer-based systems, because Tree-sitter has become widely adopted for editor tooling and syntax-aware features.

There are a few other reasons:

Error recovery: Tree-sitter can parse incomplete or syntactically invalid code while still producing a useful syntax tree. This is important for editors because code is often temporarily broken while we are in the process of writing it.
A real syntax tree: Instead of treating source code as a collection of patterns to match, Tree-sitter produces a syntax tree, which the CLI displays as S-expressions. Editors can use this structural information to provide more accurate, context-aware highlighting. For example, an identifier can be distinguished based on whether it represents a type, variable, function, or something else.

And syntax highlighting is only one of the things we can build on top of a syntax tree. Once we have one, we can also implement features such as:

Incremental parsing
Code folding
Structural selection
Code navigation
Semantic highlighting
LSP integration and more

Project setup

Before we start writing the grammar, let's get a minimal Tree-sitter project running. Since the goal of this post isn't to explain the installation process, I'll keep this section short and link to the official setup guide.

Dependencies:

A JavaScript runtime
A C compiler
Tree-sitter CLI (0.26.9)

Follow the getting started documentation to set up a similar project.

Building the grammar

With the Tree-sitter project set up, the next step is to teach it what Monkey looks like. We already have a parser and AST that define the language's structure in the interpreter, so rather than designing the grammar from scratch, we'll translate those existing concepts into Tree-sitter rules.

1. Starting with a basic grammar

The grammar skeleton

The following is the minimal skeleton of our grammar.
grammar.js

/**
 * @file Monkey grammar for tree-sitter
 * @author SegniAT <se.segni.adeba@gmail.com>
 * @license MIT
 */

/// <reference types="tree-sitter-cli/dsl" />
// @ts-check

export default grammar({
  name: "monkey",

  rules: {
    source_file: $ => repeat($._statement),

    _statement: $ => choice(
      $.expression_statement
    ),

    expression_statement: $ => seq(
      $.expression,
      optional(';')
    ),

    expression: $ => choice(
      $.identifier,
      $.integer,
    ),

    identifier: _ => /[a-zA-Z_]+/,
    integer: _ => /\d+/,
  }
});

The grammar function is the most important part of this file. It contains the declarative schema for our language. The name property is the name of the language we're writing the grammar for and the rules property allows us to define rules using built-in functions listed in the documentation.

We build the grammar top-down, mirroring how the interpreter's AST (Abstract Syntax Tree) is organized. One important fact to know up front is that the start rule for the grammar is the first property in the rules object. In the example above, that would correspond to source_file, but it can be named anything.

Every grammar rule is written as a JavaScript function that takes a parameter $. The syntax $.identifier is how you refer to another grammar symbol within a rule.

In the monkey parser, a program is a struct that has a slice of statements:

// ast/ast.go
type Program struct {
    Statements []Statement
}

We replicated this in our grammar as follows:

source_file: $ => repeat($._statement), // 'repeat(rule)' creates a rule that matches zero-or-more occurrences of a given rule.

Now we have to define _statement. In our Monkey parser, there are 3 types of Statements:

// ast/ast.go
type Statement interface {
    Node
    statementNode()
}

// 1. The LET statement 
type LetStatement struct {
    Token token.Token // the token.LET token
    Name  *Identifier
    Value Expression
}

// 2. The RETURN statement
type ReturnStatement struct {
    Token       token.Token // the 'return' token
    ReturnValue Expression
}

// 3. The ExpressionStatement statement
type ExpressionStatement struct {
    Token      token.Token // the first token of the expression
    Expression Expression
}

In our skeleton grammar we only define the Expression Statement for now:

// Starting a rule's name with an underscore causes the rule to be hidden in the syntax tree. This avoids depth and noise to the syntax tree.
// 'choice(rule1, rule2, ...)' function creates a rule that matches one of a set of possible rules.
_statement: $ => choice(
      $.expression_statement
      // We later add the LET and RETURN statements here.
),

Expression Statement is defined as the following in our grammar:

// `seq(rule1, rule2, ...)` function creates a rule that matches any number of other rules, in order.
expression_statement: $ => seq(
    $.expression,
    optional(';') // `optional(rule)` function creates a rule that matches zero or one occurrence of a given rule.
)

An Expression Statement is just an Expression followed by an optional semicolon (semicolons are optional in Monkey).
Let's look at Expression now:

expression: $ => choice(
      $.identifier,
      $.integer,
),

identifier: _ => /[a-zA-Z_]+/,
integer: _ => /\d+/,

An expression can be an identifier or an integer here, we will add much more to our final version. We describe identifier and integer as regular expressions, an identifier can only include letters and underscores, while an integer only includes numbers.

At this point we have enough grammar to parse something simple, so let's verify that Tree-sitter produces the tree we expect before adding more rules.

Testing the grammar

Create test/corpus/basics.txt with these two tests:

=================================
Expression statement (identifier)
=================================

foo

---

(source_file
  (expression_statement
    (identifier)))

==============================
Expression statement (integer)
==============================

42

---

(source_file
  (expression_statement
    (integer)))

Let's now generate a parser from the grammar and test it against the test.

tree-sitter generate
tree-sitter test

Output:

basics:
    1. ✓ Expression statement (identifier)
    2. ✓ Expression statement (integer)

Total parses: 2; successful parses: 2; failed parses: 0; success percentage: 100.00%; average speed: 593 bytes/ms

Our generated parser based on the grammar outputs an S-expression when parsing our target language source code, so we use that fact to write our tests. Let's look at the first tests.

The name of each test is written between two lines containing only = (equal sign) characters.
Then the input source code is written, followed by a line containing three or more - (dash) characters.
Then, the expected output syntax tree is written as an S-expression. The exact whitespace in the S-expression doesn't matter.

As shown in the expected output, the root of our syntax tree is a named node called source_file, which directly corresponds to our root rule defined in grammar.js.

The next node we might expect would be _statement, but the underscore makes it hidden. So we move on to its children, for now we just have expression_statement which has either identifier or integer as its children. In our first test case, foo will be identified as identifier, but in the second 42 is an integer node.

2. Building out the grammar

The basic grammar works, so now we can start filling in the pieces we left out of the skeleton.

Statements: `let` and `return`

Our interpreter has two more Statement types in addition to the already defined Expression Statement. We add them as the other two alternatives of _statement rule:

// `field(name, rule)` function assigns a field name to the child node(s) matched by the given rule. We can use it to access specific children in the resulting syntax tree.
let_statement: $ => seq(
  'let',
  field('name', $.identifier),
  '=',
  field('value', $.expression),
  optional(';')
),

return_statement: $ => seq(
  'return',
  field('value', $.expression), 
  optional(';')
),

This mirrors the interpreter's AST: the LetStatement struct has a Name and a Value field.

With the remaining Statements in place, we can move on to the remaining Literals and Expressions. This is where the grammar starts getting more interesting. Monkey has several kinds of Literals and Expressions, and some Tree-sitter features become necessary to keep the resulting tree useful and less noisy.

Literals and Expressions

Some of the remaining Literals are as follows:

// `token(rule)` function marks the given rule as producing only a single token. Tree-sitter's default is to treat each `String` or `RegExp` literal in the grammar as a separate token. We don't want 3 separate tokens here, just one.
string: _ => token(seq('"', /[^"]*/, '"')), // We don't allow '"' in strings since we cannot escape characters in Monkey at the time of writing this.
boolean: _ => choice("true", "false"),

// ... function, hash, array literals

In the Monkey grammar, the expression rule is defined as a choice between many different kinds of Expressions:

    expression: $ => choice(
      $.identifier,
      $.integer,
      $.string,
      $.boolean,

      $.unary_expression,
      $.binary_expression,
      $.paren_expression,

      $.call_expression,
      $.index_expression,

      $.if_expression,
      $.function_literal,
      $.array_literal,
      $.hash_literal,
),

Keyword extraction using `word`

Consider the following snippet:

iffoo

Tree-sitter would lex this source code as follows:

an if keyword
an identifier foo

But if should only be matched if it appears as a whole word, on its own.

The word property solves this problem. It tells Tree-sitter which rule represents the language's "word" (its identifier). This is what drives keyword extraction: Tree-sitter scans the grammar for string literals that could collide with identifiers (let, fn, true, false, if, else, return) and turns them into keywords that only match as whole words.
Add word property as a grammar-level setting:

word: $ => $.identifier,

Abstract categories using `supertypes`

Some rules in your grammar will represent abstract categories of syntax nodes, such as "expression", "type", or "declaration". These rules are often defined as simple choices between several other rules. As shown above, in our grammar, the expression rule is a choice between 13 different rules.

By default Tree-sitter will generate a visible node type for each of these abstract category rules, which can lead to unnecessarily deep and complex syntax trees. To avoid this you can add these abstract category rules to the grammar's supertypes definition. Tree-sitter will then treat these rules as supertypes and will not generate visible node types for them in the syntax tree.

supertypes is a cleanup setting, we add it as a grammar-level setting:

supertypes: $ => [
  $.expression,
],

What's the difference between supertypes and hidden rules (using _ prefix)?
Both supertypes and hidden rules are used to keep the final syntax tree cleaner, they are both hidden. However, they serve different purposes and are used in distinct ways.

supertypes mark abstract categories as conceptual groups, so they don't appear as concrete nodes while hidden rules hide intermediate helper rules that exist only to structure the grammar, not to represent a meaningful language construct.

A query can target a supertype, and it will automatically match all of its sub-types. When it comes to hidden rules, since the node doesn't exist in the tree, you can't query for it.

Expression precedence (Pratt precedence)

This is the most interesting part of our parser, because the interpreter's Pratt parser and Tree-sitter's GLR parser solve the same problem in completely different ways.

Let's look at why we need to explicitly define precedence for rules that may cause conflict. Let's say our grammar has the following snippet:

{
  // ...
  expression: $ => choice(
    $.identifier,
    $.unary_expression,
    $.binary_expression,
    // ...
  ),

  unary_expression: $ => choice(
    seq('-', $.expression),
    seq('!', $.expression)
  ),

  binary_expression: $ => choice(
    seq($.expression, '*', $.expression),
    seq($.expression, '+', $.expression),
    // ...
  ),
}

This flat structure is highly ambiguous. If we try to generate a parser with the tree-sitter generate command Tree-sitter gives us an error message:

Error: Unresolved conflict for symbol sequence:

  '-'  _expression  •  '*'  …

Possible interpretations:

  1:  '-'  (binary_expression  _expression  •  '*'  _expression)
  2:  (unary_expression  '-'  _expression)  •  '*'  …

Possible resolutions:

  1:  Specify a higher precedence in `binary_expression` than in the other rules.
  2:  Specify a higher precedence in `unary_expression` than in the other rules.
  3:  Specify a left or right associativity in `unary_expression`
  4:  Add a conflict for these rules: `binary_expression` `unary_expression`

• in the error message indicates where exactly during parsing the conflict occurs. For an expression like -a * b, it's not clear whether the - operator applies to the a * b or just to the a.

This is where the prec function comes into play. By wrapping a rule with prec, we can indicate that certain sequence of symbols should bind to each other more tightly than others. For example, the -, $.expression sequence in unary_expression should bind more tightly than the $.expression, +, $.expression sequence in binary_expression.

Our interpreter resolves operator precedence in code at runtime, with a table of constants. They are numbered starting from 1 (LOWEST) to 8 (INDEX):
parser/parser.go

const (
    _ int = iota
    LOWEST
    EQUALS      // ==
    LESSGREATER // > or <
    SUM         // +                
    PRODUCT     // *
    PREFIX      // -X or !X
    CALL        // myFunction(X)
    INDEX       // array[index]
)

Tree-sitter handles precedence in the grammar, by attaching prec and prec.left to the rules themselves. The mapping is almost one-to-one:

Operator	Interpreter constant	Tree-sitter
`==`, `!=`	`EQUALS`	`prec.left(1)`
`<`, `>`	`LESSGREATER`	`prec.left(2)`
`+`, `-`	`SUM`	`prec.left(3)`
`*`, `/`	`PRODUCT`	`prec.left(4)`
`-x`, `!x` (prefix)	`PREFIX`	`prec(5)`
`f(x)` (call)	`CALL`	`prec.left(7)`
`a[i]` (index)	`INDEX`	`prec.left(8)`

{
  // ...

// `prec(number, rule)` function marks the given rule with a numerical precedence, which will be used to resolve LR(1) Conflicts (https://en.wikipedia.org/wiki/LR_parser#Conflicts_in_the_constructed_tables) at parser-generation time.
  unary_expression: $ =>
    prec(
      5,
      choice(
        seq("-", $.expression),
        seq("!", $.expression),
        // ...
      ),
    );

    // `prec.left([number], rule)` function marks the given rule as left-associative (and optionally applies a numerical precedence).
    binary_expression: $ => choice(
      prec.left(1, seq(field('left',$.expression), '==', field('right',$.expression))),
      prec.left(1, seq(field('left',$.expression), '!=', field('right',$.expression))),
      prec.left(2, seq(field('left',$.expression), '<', field('right',$.expression))),
      prec.left(2, seq(field('left',$.expression), '>', field('right',$.expression))),
      prec.left(3, seq(field('left',$.expression), '+', field('right',$.expression))),
      prec.left(3, seq(field('left',$.expression), '-', field('right',$.expression))),
      prec.left(4, seq(field('left',$.expression), '*', field('right',$.expression))),
      prec.left(4, seq(field('left',$.expression), '/', field('right',$.expression))),
    ),
}

prec.left(n) means: this operator binds with precedence n and is left-associative, so a - b - c parses as (a - b) - c, exactly like the interpreter's loop, which keeps parsing while the next token's precedence is higher. Prefix operators use plain prec(n), because associativity doesn't apply to them.

In the Pratt parser the constants only need to be relatively ordered. Tree-sitter's numbers do the same job, so the two tables line up almost exactly.

There is one main difference between the two styles worth knowing: the Pratt parser decides how to continue looking forward from an expression, but the GLR parser explores all parse branches in parallel and only uses precedence to resolve conflicts when they actually arise. That's why for example choice order doesn't matter in Tree-sitter.

Calls, indexing, and the remaining constructs

With operator precedence sorted out, we can finish the remaining Expressions. Calls and indexing are Infix Expressions with the highest binding as seen in the previous section.

call_expression: $ => prec.left(7, seq(
  field('function', $.expression),
  field('arguments', $.argument_list)
)),

index_expression: $ => prec.left(8, seq(
  field('object', $.expression),
  '[',
  field('index', $.expression),
  ']',
)),

The remaining constructs need no new concepts, they are combinations of the primitives we have already seen.

block: $ => seq('{', repeat($._statement), '}'),

if_expression: $ => seq(
  'if',
  '(',
  field('condition', $.expression),
  ')',
  field('consequence', $.block),
  optional(seq('else', field('alternative', $.block))),
),

function_literal: $ => seq(
  'fn',
  field('parameters', $.parameter_list),
  field('body', $.block)
),

hash_pair: $ => seq(
  field('key', $.expression),
  ':',
  field('value', $.expression),
)

3. The complete grammar

At this point we've covered all the Tree-sitter concepts that required explanation. The remaining rules are mostly combinations of the same primitives, so we can jump directly to the complete grammar. The final grammar.js is only ~145 lines.

Feeding it a complete program shows what we built. Create a file with the following content:

let x = 5;
let add = fn(a, b) { return a + b; };
let result = add(3, 4);
let arr = [1, 2, 3, 4];
let person = {"name": "Alice", "age": 30};
let age = person["age"];
if (age > 21) { let status = "adult"; } else { let status = "minor"; }
let makeAdder = fn(x) { return fn(y) { return x + y; }; };
let addFive = makeAdder(5);
addFive(10);

Running the command tree-sitter parse [your file name] should output the following:

(source_file
  (let_statement name: (identifier) value: (integer))
  (let_statement
    name: (identifier)
    value: (function_literal
      parameters: (parameter_list
        name: (identifier)
        name: (identifier))
      body: (block
        (return_statement
          value: (binary_expression
            left: (identifier)
            right: (identifier))))))
  (let_statement
    name: (identifier)
    value: (call_expression
      function: (identifier)
      arguments: (argument_list
        (integer)
        (integer))))
  (let_statement
    name: (identifier)
    value: (array_literal
      (integer) (integer) (integer) (integer)))
  (let_statement
    name: (identifier)
    value: (hash_literal
      (hash_pair
        key: (string)
        value: (string))
      (hash_pair
        key: (string)
        value: (integer))))
  (let_statement
    name: (identifier)
    value: (index_expression
      object: (identifier)
      index: (string)))
  (expression_statement
    (if_expression
      condition: (binary_expression
        left: (identifier)
        right: (integer))
      consequence: (block
        (let_statement
          name: (identifier)
          value: (string)))
      alternative: (block
        (let_statement
          name: (identifier)
          value: (string)))))
  (let_statement
    name: (identifier)
    value: (call_expression
      function: (identifier)
      arguments: (argument_list
        (integer))))
  (expression_statement
    (call_expression
      function: (identifier)
      arguments: (argument_list
        (integer)))))

Every construct shows up as a named node, with fields (name:, value:, left:, right:, condition:, consequence:, ...) carrying the same information the interpreter's AST carries in Go.

The grammar is now complete, but that does not mean that the generated parser outputs the correct syntax tree. Validation is our next undertaking.

The corpus as executable specification

tree-sitter generate compiles the grammar into a C parser, and tree-sitter test runs the corpus (test cases). There are 70 test cases in the project written alongside the grammar:

Total parses: 70; successful parses: 70; failed parses: 0; success percentage: 100.00%

The corpus is the spec. Because each test includes an input source code and the expected output tree, it also serves as documentation of the language.

Error recovery: Tree-sitter's superpower for editors is its behavior on broken code. Instead of stopping the parsing task, the parser emits an ERROR node and continues its parsing. The tree stays mostly correct while you type. We test these cases in the corpus with the :error directive:

===========================
Integer as let name
:error
===========================

let 5 = x;

---

============================
Missing value
:error
============================

let x = ;

---

============================
Unterminated list
:error
============================

[1, 2

These tests assert that the input contains a syntax error while still allowing Tree-sitter to produce a useful tree around it. This is why highlighting stays useful in an editor. Code is broken most of the time while we're writing it, and the parser still produces a useful tree around the errors.

At this point we have a parser that can turn Monkey source code into a syntax tree, and we can test that parser against a corpus to verify its validity. But our original goal wasn't just to parse Monkey, we wanted an editor to understand it well enough to highlight it.

Turning the parsed tree into highlighting

To achieve our main goal of syntax highlighting, we need to write queries that match nodes in the syntax tree and assign them captures, those are names that Neovim understands and maps to highlight groups it has already defined.

You can find the list of standard captures supported by Neovim in their Tree-sitter docs. These include captures such as @function, @variable, @keyword, and @string, which are highlighted according to the current colorscheme.

The queries assigned to captures live at queries/highlights.scm. The ordering inside it matters, more specific patterns need to come before generic ones. But we will set priorities using #set! priority N to be more explicit. Higher numbers win, which lets us keep related patterns grouped together instead of carefully ordering every rule.

In our case, we have different types of functions and identifiers:

; User-defined function calls
((call_expression
  function: (identifier) @function.call)
  (#set! priority 120))

; Built-in function calls
((call_expression
  function: (identifier) @function.builtin
  (#any-of? @function.builtin "len" "first" "last" "rest" "push" "puts"))
  (#set! priority 130))

; Function parameters
((function_literal
  parameters: (parameter_list
    (identifier) @variable.parameter))
  (#set! priority 120))

; Hash keys are properties (strings and bare identifiers)
((hash_pair
  key: (string) @property)
  (#set! priority 120))

((hash_pair
  key: (identifier) @property)
  (#set! priority 120))

; All-caps identifiers are constants by convention, which is a convention from other languages - Monkey has no reassignment, so every variable is effectively constant.
((identifier) @constant
  (#match? @constant "^[A-Z][A-Z_]*$")
  (#set! priority 120))

; more captures ...

; Catch-all: every other identifier is a variable
(identifier) @variable

Two predicates do the heavy lifting here:

#any-of? checks the node's text against a list, that's how len and other builtin functions become @function.builtin while every other callee is @function.call. Monkey has no named function definitions (functions assigned to a variable with let), so @function itself stays unused.
#match? applies a regex, all-caps identifiers become @constant by convention, before the catch-all below turns everything else into @variable. The Monkey language does not have the concept of constant variables, this is just for convention.

The rest is a straightforward mapping of literals and keywords:

; Keywords
"let" @keyword

[
  "if"
  "else"
] @keyword.conditional

"return" @keyword.return

"fn" @keyword.function

; Literals
[
  "true"
  "false"
] @boolean

(integer) @number

(string) @string

; ... more

Keywords and literals map directly, and the rest of queries/highlights.scm covers operators, brackets, and delimiters (,, ;, :). Check out the file to explore all the captures. The full list is 18 captures which is tiny compared to languages like TypeScript or Rust for example.

We now have both pieces we need to finalize our project: a parser that produces the tree and highlight queries that turn nodes into captures. The final step is connecting that grammar to Neovim so it knows when to use the parser for .monkey files.

Neovim integration and showcase

Now comes our final task, i.e. editor integration. We will follow the nvim-treesitter README.md, "Adding custom languages" section.

First, we need to let Neovim know that .monkey files are a thing, in our configuration file we add the following:

vim.filetype.add({ extension = { monkey = "monkey" } })

Then we need to register the parser with nvim-treesitter:

vim.api.nvim_create_autocmd('User', {
  pattern = 'TSUpdate',
  callback = function()
    require('nvim-treesitter.parsers').monkey = {
      install_info = {
        url = 'https://github.com/SegniAT/monkey-language-interpreter',
        location = 'tree-sitter-monkey',
        queries = 'tree-sitter-monkey/queries',
      },
    }
  end,
})

The interesting part is the monorepo layout: our grammar lives inside the interpreter's repository. nvim-treesitter downloads the repo tarball from url, builds the grammar found at location, and installs the queries found at queries.

This works, but it isn't really ideal since the grammar is only one directory inside a much larger repository of the Monkey interpreter (and soon, the LSP as well)! So installing the parser means downloading the entire interpreter repository.

After this, the update loop is:

tree-sitter generate && tree-sitter test   # locally
git commit && git push                     # to the repo
:TSUpdate monkey                           # in Neovim

That's enough to get the whole pipeline working. We can now open a .monkey file in Neovim, have Tree-sitter parse it, apply our queries, and get syntax highlighting.

Before:

After: (tokyonight-night theme)

Beautiful!

A look at the generated tree by the parser using :InspectTree in Neovim:

A few queries on the generated tree using :EditQuery in Neovim:

Conclusion

To add syntax highlighting and make our custom language prettier to look at and more convenient to work with, we had to go through a whole bunch of fun challenges: a hand-written grammar, a corpus that also serves as a spec, queries that map the tree to editor semantics, and finally editor integration.

The biggest lesson: the grammar is an executable spec and the corpus is its test suite. Together they make the language's actual behavior much harder to misunderstand than documentation alone.

A second lesson: a toy language is still a precise language. Monkey's grammar fits in ~145 lines, yet every rule had to be right: precedence levels, hidden rules, keyword extraction, fields, this is the same machinery that parses Go or Zig, just much smaller.

But syntax highlighting is only the beginning. We can now tell the editor what a piece of code looks like, but not much about what it means. The next step is to teach the editor about Monkey itself: diagnostics, definitions, completion, and eventually the other features we expect from a modern development environment. That's where the LSP comes in, in our second entry the series.

DEV Community: Segni Adeba

Building a Development Environment for Monkey: Part 3 - Solving an Advent of Code problem

Intro

The AoC problem and solution

Part one

Part two

Monkey's limitations

Solutions to language limitations

Monkey updates: built-in functions and more

readFile

splitString

Updating Monkey's Lexer to read escape sequences properly

Updating Monkey's Tree-sitter to handle escape sequences properly

atoi

sortInts

trimSpace

trimSuffix

Updating Tree-sitter to include our new built-in functions

Yet another typed nil interface bug

The Monkey solution

reading the input

part one

part two

Performance

Raw time comparison: Monkey vs Go solutions

Reading the Benchmark Output

A quick look at the numbers and code complexity

CPU Profiling to know where Monkey is CHOKING

1. The Flat View ("Where is the CPU?")

2. The Cumulative View ("Why is it slow?")

Heap Profiling for confirmation

1. The Flat View (The Smoking Guns)

2. The Cumulative View (The General Trend)

Diagnosis: Interpreter Overhead vs. Language Design

Conclusion

Building a Development Environment for Monkey: Part 2 - An LSP for Hover, Definition, Completion and Diagnostics

Intro

What the LSP actually is (and what we're building)

Step 1 - The RPC layer

First attempt: bufio.Scanner with a custom SplitFunc

The problem

The solution: bufio.Reader + io.ReadFull

Step 2 - Protocol types (the boring part) and handlers

Go's type system

Lifecycle message Initialize and server capabilities

Handling Requests and Notifications

Step 3 - State, Documents, and Diagnostics

Document sync

Diagnostics

Extending Monkey tokens

Lines and Characters: 0 vs 1-based numbering

Step 4 - Static analysis: symbols, scopes, and the features built on them (the fun part)

Adding Start() and End() on every AST node

Implementing our language features and the problems we face

Hover

Definition

Completion

Static analysis, symbols, symbol tables and diagnostics

Hover, definition and completion implementation

Hover

Definition

Completion

A design trade-off I hit while writing the analyzer

The let crash (a Go interface gotcha)

Step 5 - Concurrency

Step 6 - Hooking up our server to Neovim

Testing

Showcase

Diagnostics on text document open and change

Re-declaration of variables

Undefined variables

Unused variables

Hover

Definition

Completion

Conclusion

References

Building a development environment for Monkey: Part 1 - Syntax highlighting with Tree-sitter

Intro

Why Tree-sitter?

First attempt: `bufio.Scanner` with a custom `SplitFunc`

The solution: `bufio.Reader` + `io.ReadFull`

Adding `Start()` and `End()` on every AST node

The `let` crash (a Go interface gotcha)

Statements: `let` and `return`

Keyword extraction using `word`

Abstract categories using `supertypes`