A simple Tree-Walk Interpreter implementation in Go

Based on the book Crafting Interpreters by Robert Nystrom

The goal of this hobby project was to learn how programming languages work by building a simple tree-walk interpreter from scratch in Go.

Features

As a learning project, the language implementation focuses on core concepts:

• Data Types: Support for number (int/float), string, bool, and nil.
• Functions: First-class functions with lexical scoping.
• Structs (Classes): A simple object model using structs. They act like classes, supporting methods and an init constructor, but without inheritance.
• Modules: Basic module system with an import statement to load code from other files.
• Performance: Leverages Go's experimental memory arenas for more efficient Abstract Syntax Tree (AST) node allocation.
• [WIP] Arrays: Initial support for array types and native standard library functions is in progress.

Code examples

To demonstrate the main features of the interpreter here is an example of a program which calculates the constant e to the 5th digit.

fact.code

The famous recursive factorial calculation function (just for the sake of demonstrating recursion).

func fact(x) {
    if x == 1 {
        return x;
    } else {
        return fact(x - 1) * x;
    }
}

main.code

The main program. Imports the definitions from the file above. Defines a struct with a field for the error and a method for calculating the constant e. Uses an instance of this struct to calculate e.

import "fact.code"

struct ConstantsCalculator {
    def init(eps) {
        this.eps = eps; 
    }

    func calculate_e() {
        let prev = 1;
        let curr = 2; 
        for let i = 2; curr - prev > this.eps; i = i + 1 {
            prev = curr;
            curr = curr + 1 / fact(i);
        }
        return curr;
    }
}

let calculator = ConstantsCalculator(0.0001);
let e = calculator.calculate_e();
print("Constant e =", e);

Running the program

foo@bar:[repo-directory]$ ./bin/interpreter run main.code
Constant e = 2.71827876984127

Example 2

Here is an implementation of the Linked List data structure.

linkedlist.code

struct Node {
    func init(data, next) {
        this.data = data;
        this.next = next;
    }
}

struct LinkedList {
    func init() {
        this.head = null;
        this.length = 0;
    }

    func Prepend(data) {
        let newNode = Node(data, this.head);
        this.head = newNode;
        this.length = this.length + 1;
    }

    func Append(data) {
        let newNode = Node(data, null);
        if this.head == null {
            this.head = newNode;
        } else {
            let curr = this.head;
            while curr.next != null {
                curr = curr.next;
            }
            curr.next = newNode;
        }
        this.length = this.length + 1;
    }

    func Print() {
        let curr = this.head;
        while curr != null {
            print("->", curr.data);
            curr = curr.next;
        }
    }

    func Find(data) {
        let curr = this.head;
        while curr != null {
            if curr.data == data {
                return true;
            }
            curr = curr.next;
        }
        return false;
    }

    func InsertAt(index, data) {
        if index < 0 || index > this.length {
            print("error: index out of bounds");
            return false;
        }

        if index == 0 {
            this.Prepend(data);
            return true;
        }

        let newNode = Node(data, null);
        let curr = this.head;
        let prev = null;
        let currentIndex = 0;

        while currentIndex < index {
            prev = curr;
            curr = curr.next;
            currentIndex = currentIndex + 1;
        }

        newNode.next = curr;
        prev.next = newNode;
        this.length = this.length + 1;
        return true;
    }

    func RemoveAt(index) {
        if index < 0 || index > this.length - 1 || this.head == null {
            print("error: index out of bounds or list is empty");
            return null;
        }
        
        let removedData;
        if index == 0 {
            removedData = this.head.data;
            this.head = this.head.next;
            this.length = this.length - 1;
            return removedData;
        }

        let curr = this.head;
        let prev = null;
        let currentIndex = 0;

        while currentIndex < index {
            prev = curr;
            curr = curr.next;
            currentIndex = currentIndex + 1;
        }

        removedData = curr.data;
        prev.next = curr.next;
        this.length = this.length - 1;
        return removedData;
    }
}

let list = LinkedList();
list.Append(1);
list.Append(2);
list.Append(3);
print("LinkedList elements:");
list.Print();

print("LinkedList after removing the element at index 1:");
list.RemoveAt(1);
list.Print();

print("LinkedList after inserting back element 2 at index 1:");
list.InsertAt(1, 2);
list.Print();

Running the program

foo@bar:[repo-directory]$ ./bin/interpreter run linkedlist.code
LinkedList elements: 
-> 1 
-> 2 
-> 3 
LinkedList after removing the element at index 1: 
-> 1 
-> 3 
LinkedList after inserting back element 2 at index 1: 
-> 1 
-> 2 
-> 3 

Getting started

Prerequisites

• Go: Version 1.20 or newer is required for memory arena support.
• Make: A Makefile is used for simple build commands.
• OS: Developed on Linux. Compatibility with macOS or Windows (via WSL) is not guaranteed but may be possible.

Building from source

1. Clone the repo:

   foo@bar:~$ git clone https://github.com/AlexHaborets/interpreter-in-go.git
   foo@bar:~$ cd interpreter-in-go

2. Build using make (this will create the executable in the projects bin directory):

   foo@bar:~/interpreter-in-go$ make build

3. Run the example code in the terminal:

   foo@bar:~/interpreter-in-go$ ./bin/interpreter run main.code

License

This project is licensed under the MIT License - see the LICENSE file for details.