Writing a Programming Language

What I'm intending on writing here is more about what I've implemented within this language, rather than specifically trying to be a tutorial on writing your own programming language. I therefore, assume you have some background information about how programming languages work already. For this post, the main sources I used were Crafting Interpreters, and the lua reference manual.

Architecture

Writing a programming language is a big project, with many different parts to write, therefore having a good interface between each section and being clear as to what is being done is a good place to start in my opinion.

Below is a high-level overview of the stages that I'm planning within the language. Some of these stages may run multiple times, and some are significantly more complex than others, but this is good enough to get started.

As I said previously, the main stage I haven't really experimented with here is the type checker, although there is lots of different ideas I have for pretty much all the stages. I could start this project with pretty much any of the sections, however I have decided that it would be easiest to start from the beginning, so I have an easy way to provide input to the program, without having to write data structures manually to provide type system input.

The majority of information that I have found about writing programming languages focuses on the academic side, with the languages being written being pure functional languages. Most commonly used programming languages are not either pure or functional, lua is neither, I am not planning on changing that. Therefore, we will be working on dealing with the complexity of a real programming language, how it isn't perfect for type systems and how most academic literature doesn't directly apply to what I'm doing here.

Lets start then, with a parser. There has been a lot written about different ways to parse source code, there are endless different ways to write a parser. I have decided to go with a hand written recursive decent parser, due to how easy they are to write, so I can move on to more interesting parts of the language.

Lexing

Before the parser, we have a lexer, which converts the raw character stream of a source file into a stream of tokens which will be consumed by the parser. For each token we recode a little bit of information:

struct Token<'a> {
    kind: TokenKind,
    value: &'a str,
    line: usize,
}
 
enum TokenKind {
    Number, Name, And, Function, // ...
}

Each token contains a reference into the original source file that it was created from, this makes it easier to read the text later on in the parser, although it does mean that it is harder to store the individual tokens. We store the line number for providing diagnostics for the file, although it isn't particularly accurate, especially if you have a long line of code.

The TokenKind enum identifies what is within the token. The lexer tries to identify keywords such as function and if so they can be distinguished from other identifiers (or Names to use lua's terminology). This makes it easy for the parser to match directly on any keywords, without having to repeatedly check for string equality.

Number tokens in source code are writen using characters, where as in the program, they will be represented by the actual number, as floats or integers. The work to convert a number token to is actual value is pretty similar to the work to identify the bounds of the number within the source code. I could convert numbers to their value within the lexer and store that result within the token, however that would increase the size of all tokens. I therefore, will do the conversion later on, once parsing has finished, even though this feels slightly like duplication of work. The same also applies to string values and parsing of any possible escape sequences.

I have chosen to make the lexer run at the same time as the parser. Instead of running the lexer to completion and storing the tokens in a list, I have structured the lexer to work as an iterator. This avoids creating a list of tokens that will then immediately be consumed by the parser.

AST

Before writing the parser, we need to work out what data it will produce. An Abstract Syntax Tree (AST) contains a portion of the information from the source code, skipping over a lot of the details which are not needed later on in the program. The type system doesn't care about individual brackets being represented in the same way as the user typed.

Modern compilers typically have been moving away from the parser output being an AST. Instead, some compilers output a Concrete Syntax Tree (CST) (Examples include C#'s Roslyn and Rust Analyser). This would include all characters from the source file within the tree, even the whitespace and comments. This tree would typically be un-typed, and the AST would be a typed view over the tree. Using a CST is useful if you are writing an language server, an auto formatter, or want to know whether a change was just to the whitespace, but generally can be avoided for the case of a traditional batch compiler. Avoiding a CST is therefore what we will be doing here to simplify things.

For function names, the lua reference manual describes them using the following syntax description:

funcname ::= Name {‘.’ Name} [‘:’ Name]

I have translated this into a rust structure to be produced by the parser:

struct FunctionName<'a> {
    names: Vec<Token<'a>>,
    method: Option<Token<'a>>,
}

This struct includes all the useful information from the original description, while not including the . and : tokens.

This AST contains the tokens directly, which means it has to contain the lifetime parameter from the tokens. This is a pain to store and manipulate further through the program, so future stages of the compiler will remove this reference to the initial source code.

An improvement to the AST could be to reduce all the allocations within it. This structure has a bad cache locality as different parts of the AST could be spread anywhere throughout memory. Additionally, the destruction and creation is slow due to having to recursively call malloc and free to create and destroy the structure. A flattened AST would solve both these issues, so could be an improvement to be implemented in the future.

Parsing

The parser is a recursive descent parser that pretty much follows the design of the lua grammar, with functions for each line of the grammar. For expression parsing, I use a Pratt parser, which can handle precedence, associativity, and some operators being both prefix and infix (unary minus vs subtract). The grammar of lua does not include anything about this precedence, with it being represented in text. The Pratt parser pretty much follows the design set out in Crafting Interpreters, just ported to rust, with the main difference being the language itself.

While writing the parser, there was one main difference between the C version in Crafting Interpreters and the Rust I've written. The table that drives the Pratt parser is defined in C as:

ParseRule rules[] = {
    [TOKEN_LEFT_PAREN]    = {grouping, NULL,   PREC_NONE},
    [TOKEN_RIGHT_PAREN]   = {NULL,     NULL,   PREC_NONE},
    ...
}

This exact structure cannot be represented in rust as is. The ParseRule struct contains 2 function pointers, which can be set to NULL, which isn't allowed in Rust. Additionally the table is indexed by an Enum, there aren't any easy ways to write an array constructed in the same way as in C (The table constructor in lua does allow pretty much the same syntax as c though!).

Working around the enum indexing is relatively easy as the table isn't modified at all. This means that I can translate it into a match expression:

match token.kind {
    LeftParen => (),
    RightParen => (),
    // ...
}

The harder part, to me, is what should be put in each match arm and the types involved. In order to have a nullable function pointer, the translation to rust is Option<fn()>. Each of the parse functions to be put in the table will require access to the parser and will need to output the AST for the expression it has parsed. The return type, therefore, should be ast::Expression<'a> and the functions need to take an argument of &mut Parser<'a>, making the function type fn(&mut Parser<'a>) -> ast::Expression<'a>. In this signature, the lifetimes need to come from somewhere. This requires introducing a 'Higher Ranked Trait Bound' (hrtb), which makes the final type^[1]:

Option<for<'a> fn(&mut Parser<'a>) -> ast::Expression<'a>>

Now we have the type signature, we have to consider how to construct values of this type. The easiest options is to use the rust syntax for constructing structs:

ParseRule { prefix: Some(grouping), infix: None, precedence: None }

This, while clear, is really verbose, especially once we've repeated it for all 50 odd token kinds. (Actually, I just went and counted them, I think its 60, not 50).

An alternative would be to use a constructor function:

ParseRule::new(Some(grouping), None, None)

This is still repetitive, and yet less clear than the built in syntax, in my opinion. I have tried a few ways of fixing this, however none of them ended up working. Both of the attempts failed due to an issue I was only vaguely aware of: all rust function types are unique, even when they aren't closures. This means that the type of an individual function might be fn() {myFn}. Typically this would not have any effect on normal code, you can pass the function into another function without thinking about it at all. One place where it does matter is within trait resolution.

If you have the function:

fn example(f: impl Into<fn()>) { todo!() }

then when rust is checking example(myFn) it will complain that fn() {myFn} doesn't impl Into<fn()>. If you ignore the uniqueness of the function type, then it does (due to the impl Into<T> for T blanket impl) work. You can either provide an explicit type for the example function so trait resolution isn't required, or use an as cast example(myFn as fn()), which will work, but this is one area where the obvious path with trait resolution doesn't work as I expect.

In the end, what I have gone with is a series of methods to create rules:

match token.kind {
    LeftParen => None.prefix(grouping),
    RightParen => None.into(),
    Add => AddPrec.prefix(unary).infix(binary),
    // ...
}

In my opinion this is both clearer and less repetitive than any of the other options I tried.

Handling Errors

There are multiple different ways of handling syntax errors within a parser that we could choose.

In Compiling Interpreters, the parsers introduced use error tokens and a synchronise function, which lets the parser recover from some errors which it encounters. This means that multiple syntax errors can be reported within one file, without having to run the compiler repeatedly to find all the errors, fixing them one at a time. This, in my opinion doesn't work very well for lua. There are no specific statement terminators which can easily be used for synchronising, semi colons are only used where it is ambiguous to the parser, rather than at every expression (This is pretty much only when an expression starts with ().

An alternative error recovery system is used by Rust Analyser, which instead keeps parsing as if an error did not even occur, instead recording the wrong tokens in the tree output by the parser. This requires the parser to output a CST, which can support trees that contains errors, unlike the AST presented above. I learnt about this from "Resilient LL Parsing Tutorial", which shows how it works for a small language. This makes the parser much clearer for an end user, however isn't easy to write.

The error handling strategy I have chosen is neither of the previous. Instead we don't handle errors at all. If the parser encounters an error, it crashes, with a hopefully vaguely relevant message. This is pretty much the opposite of what is wanted for a language server, IDE, or any other long running process. However, it is the easiest to implement, to allow us to get on with the rest of the language.

I would like to come back to the decisions made in this post, so I can improve the parser in the future, but that is very much a "future work" problem, rather than something that needs a solution now. The code shown in this post is viewable in the source tree in the repository.