Making a toy language: a noobie experience

I recently attempted to make a language of my own. It is something I had been meaning to do for a while, and finally got the impetus from a group project in the Club of Programmers in my college, which I ended up doing alone. Here's the repository.

I found it easier to start with an interpreter, and at some later point also make a compiler. I chose Golang to write the interpreter in - a decision I am not particularly fond of in retrospect, with the presence of languages like Rust better suited to this task. It is through this project that I learned a bit of Golang. I found some resources online, chiefly Crafting Interpreters. I will be referring to it as the book. The author uses Java, which obviously is vastly different from Golang in terms of syntax and philosophy, but it only adds to the fun.

When doing something like making an interpreter, there are three main components involved:

The lexer

The first step to interpreting written code is making sense of the individual units of the language grammar. The lexer "lexifies" raw text into lexemes, which are the individual meaningful elements of the language, like literals, operators, keywords, etc. For example, after the lexing phase, we would decipher the letters f-u-n-c-t-i-o-n to represent the beginning of a function block, 420 is a numeric constant, etc. My implementation of the lexer is a chaotic one, with all sorts of checks and conversions happening all over the place. My focus was to get the output first, as the more wonderful aspects of designing an interpreter were yet to come. Later on, I added the line number of each lexeme alongside the actual token it represented, so that I could provide helpful error messages.

The Parser

The next step is to parse the lexemes generated into an Abstract Syntax Tree (AST). The idea is that the entire program can be represented by a tree, whose nodes consist of the individual statements to execute, functions, loops, and other kinds of scopes. This was a phase where I was stuck for a while. This was the first instance where I needed to read the book to get a perspective. The book explained a parsing technique called Recursive Descent, where we recursively parse an expression into a subtree in the AST. There were many other better techniques, but this one seemed simple and sufficient for the time being. (I recently got to know about Pratt Parsing from a senior, which I plan to implement at some point).

In the AST, there are various types of nodes, for various aspects of the language. There would be conditional nodes, loop nodes, function nodes, or just a simple statement node. Each node would then have different kinds of child nodes depending on its types, for example, a conditional node would have a child node containing the expression for the condition for the loop, a function node would have nodes representing arguments, etc. I could have used inheritance etc to model this, but Golang does not provide support for it, so I just had to store the type of node in a string, and the children corresponding to them in a map, because I needed the flexibility which structs could not provide.

Parsing expressions worked quite well until I added function calls and array indexing. Those messed up the structure and order of the code, but hey, it works.

The Interpreter

This is the final piece of the puzzle. Interpreting effectively is just walking the AST created. Seems simple enough, but we need to keep track of the program state (variables) as it progresses, and also devise a scheme for memory management. I was earlier using the map type in Golang to store the variables and functions, and things worked fine until I wrote a program to find the square root of a number using the bisection method, and it would give a different answer each time it ran. I still don't know what caused this, but at that time, I guessed that the management of data had been abstracted away into a black box, and was completely out of my control. Maybe managing the memory myself would solve this (it eventually did).

Virtual Machine

So I set out to make a kind of virtual machine that would run my code, and would have a byte array of 1Kb which it would call "memory". This array would store all the variables. Numbers, arrays, and strings would be decomposed into bytes stored in this array, and retrieved when required. I made a simple malloc function for the allocation too. I figured the simplest way was to just maintain a byte array and a boolean array, to store the data and availability of a particular chunk of memory. It turns out it is a rudimentary way to manage memory. I do plan to employ better methods later on.

Runtime

Whenever we enter a scope, we allocate some space for its variables on the stack, and when we leave it, the now-useless data must somehow be cleaned from the memory, making it available for future use. I have used my implementation of the Stack data structure to mimic a call stack, storing various metadata about the scope.

type scopeContext struct {
    scopeId     string
    scopeTyp    string
    scopeName   string
    variables   map[string]Variable
    functions   map[string]parser.TreeNode
    returnValue *Variable
}

The Culmination

After much effort, I could get the Virtual Machine version of the language working. I had control over almost all aspects of its functionality, which led to various bugs, but I found ways to fix most of them. Most of the project is just my ideation, as I only referred to the book when I was really stuck implementing something. The square root program finally gives correct answers each time, and I keep track of what bytes are written at which part of the virtual memory. The project is far from perfect. It is sloppy, chaotic, and outright disgusting in a few places - but it works. The kind of fulfillment I got from seeing it work without errors was indescribable. This language won't find use in any domain. It is good for nothing. It might just be a waste of time (some people suggested), but it works and I learned a lot from it and will continue to learn as I add new things to it. And I think this is all that matters. There is still a lot I haven't mentioned, like how I managed memory entering and exiting scopes, and how I passed and returned values from functions. But that's for another time.

Bon adieu