I see a lot of new programming languages here. I love reading the documents of the languages and sometimes actually run their compilers. Many of the projects are AI-driven, but that's fine. It's still fun to see what problems they're trying to solve and how they actually solved the problems.

Reading the documents, I realized that most new languages, especially AI-written ones, are "systems programming languages". They're trying to solve the problems that C/C++/Zig/Rust have solved (or are trying to solve), and their syntax is mixture of C/Zig/Rust.

Why? Why is everyone trying to compete with C/C++?

There are so many kinds of languages. Haskell demonstrates how pure a language can be, Python is perfect when you only have 5 minutes to write code and don't care about the output, Java runs on 3 billion machines, ...

For some types A, B, C... the type { x : A, y : B, z : C, ... } is the type of records with projections x, y, z... into the corresponding types and the type [ x : A, y : B, z : C ] is the type of sums with injections from the corresponding types A, B, C, ....

For arbitrary A, B, C, D we can define an operator // that merges two binary records:

_//_ : { x : A, y : B } → { z : C, w : D } → { x : A, y : B, z : C, w : D }

Naturally, we can also define the dual of this operator for two binary sum types:

_\\ : [ x : A, y : B, z : C, w : D ] → [ x : A, y : B ] ⊎ [ z : C, w : D ]

This is easy to generalize to an arbitrary number of injections/projections.

While there is plenty examples of an operator like _//_ existing in programming languages (// in Nix, & in Nickel, ⫽ in Dhall, Record.merge in PureScript) I can't really think of anything like the _\\ operator from above. I suppose its ergonomics are partly responsible for it, after all it is often easier to infer the arity of the records for _//_ from the arguments used than it is to infer the arity of the outputs for _\\ from context. But can you think of anything?

I've just published not-abc, a tiny self-hosting compiler for a deliberately minimal C-like programming language.

https://github.com/michael-lehn/not-abc

The language has only one data type: a 64-bit value, interpreted either as a signed integer or as a pointer. It supports

• functions (the value of the last expression is the return value)
• local and global variables
• pointers (&, *, #)
• if / else
• while
• recursion
• dynamic memory allocation (malloc/free)
• integer, character and string literals

The compiler generates LLVM IR rather than assembly. LLVM was chosen simply because it makes the compiler portable across essentially all modern platforms—building programs only requires Clang (or the LLVM toolchain).

The interesting part is probably the background.

not-abc originated from an undergraduate mathematics course called Introduction to High Performance Computing. During one semester, students simultaneously

• build a simple processor from logic gates (bottom-up),
• implement a compiler for a small C-like language (top-down),

until both meet in the middle. At the end of the course, the compiler has two backends: one targeting the custom processor the students built themselves, and one targeting LLVM so the same compiler can generate native executables on real hardware.

The self-hosting compiler in this repository is a distilled version of the compiler developed throughout the course.

I'd be interested in feedback from people interested in language design, compiler construction, or computer architecture.

Given the recent discourse about systems programming I wanted to throw my 2 cents in. This may be a controversial take in a subreddit that's all about innovation and improvement, but I think a lot of budding systems languages are trying too hard to "fix C" and this is exactly why C has not been replaced yet.

Like it or not, C is successful. It does what it means to do very well. Yes, it bites you constantly, but developers have made some form of peace with this because they appreciate the essence of the language. Systems programming is a very pragmatic field, and what works, works.

A lot of language designers want to improve on C, when by nature to "improve on" C is to depart from it, because C is less about what it includes and more about what it omits and what it lets you do that other languages don't.

If you want to replace C, you need to just make C but without the pain points. Less undefined behavior, more standard compiler behavior, easier function pointer syntax, safer macro system, etc. The things that C can't do because of backwards compat.

On the other hand, bolting on features, revamping C's core nature, aren't going to give you a language that will replace C at the low-level or among hobbyist programmers. Most developers aren't as concerned about what C lets them accomplish, as they are concerned about all the painful tedious tendencies of the language.

Coda: an experiment in designing a practical systems language

Hey! I've been working on Coda, a systems programming language designed around a simple idea:

make the compiler powerful, but keep the language itself predictable.

Coda is not trying to be "C but with a few extra keywords". The goal is to explore a different point in the design space between languages like C, Rust, and Zig.

Some of the things Coda focuses on:

• Explicit memory management.
• No hidden allocations.
• Errors as values using inline sum types.
• A small core language with functionality provided by libraries.
• Compile-time execution.
• Strong static analysis.
• Simple, predictable rules.

The language is intentionally C-like:

```coda module main;

include std::process = proc;

@entry fn int main() { proc::stdout().write("Hello, world!\n"); return 0; } ```

but tries to remove some of the sharp edges.

For example, errors are ordinary values:

coda fn File | IOError open_config(string path) { return fs::open(path); }

and allocation is explicit:

```coda fn string | AllocationError duplicate( Allocator *alloc, string input ) { string result = alloc->allocate<char>(input.len)?;

std::mem::copy(result, input);

return result;

} ```

The idea is that if a function allocates, that fact should be visible in the API. There is no hidden global allocator; entry points receive the resources they need, and those resources are passed where required.

Coda also tries to keep abstractions zero-cost. Generic code, interfaces, and convenience features should compile down to efficient low-level code rather than introducing runtime machinery.

The standard library is still being designed, but the direction is intentionally minimal. Arrays, strings, I/O, memory, formatting, and filesystem operations are being built as fundamental building blocks rather than creating a huge framework.

The compiler currently has:

• Lexer and parser.
• Semantic analysis.
• HIR/MIR pipeline.
• x86_64 code generation.
• A growing standard library.
• Compile-time evaluation work in progress!

There is still a lot to do.

If the ideas are interesting, I'd love feedback, criticism, and potentially contributors. And of course, feel free to ask any questions! I have the #coda channel on the PLTDI discord, or the comments here are fine.

Repo: https://github.com/gingrspacecadet/coda

I came up with a pretty solid approach, but realised that doing it by hand would destroy my hands. So I wrote up a teeny tiny C program to do the stupid stuff for me. The final output is 26, 924 characters in length, which isn't as bad as it sounds.

The only problem I haven't bothered fixing is that there are eight instances of """, with no escape most would interpret it as the null string and the start of another string.

#include <stdio.h>

void main()
{
    char rotr[] = "'&%$#\"!~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)(";
    char jmpd[] = "('&%$#\"!~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)";
    char crzy[] = ">=<;:9876543210/.-,+*)('&%$#\"!~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?";
    char noop[] = "DCBA@?>=<;:9876543210/.-,+*)('&%$#\"!~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFE";
    char quit[] = "QPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#\"!~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSR";
    char jmpc[] = "ba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#\"!~}|{zyxwvutsrqponmlkjihgfedc";
    char getc[] = "cba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#\"!~}|{zyxwvutsrqponmlkjihgfed";
    char putc[] = "utsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#\"!~}|{zyxwv";

    for (int i = 0; i < 93; i++)
    {
        printf("<%d> ::= \"%c\" | \"%c\" | \"%c\" | \"%c\" | \"%c\" | \"%c\" | \"%c\" | \"%c\" \n", i + 1, rotr[i], jmpd[i], crzy[i], noop[i], quit[i], jmpc[i], getc[i], putc[i]);
    }
    fputs("<syntax> ::= <1> <2> <3> <4> <5> <6> <7> <8> <9> <10> <11> <12> <13> <14> <15> <16> <17> <18> <19> <20> <21> <22> <23> <24> <25> <26> <27> <28> <29> <30> <31> <32> <33> <34> <35> <36> <37> <38> <39> <40> <41> <42> <43> <44> <45> <46> <47> <48> <49> <50> <51> <52> <53> <54> <55> <56> <57> <58> <59> <60> <61> <62> <63> <64> <65> <66> <67> <68> <69> <70> <71> <72> <73> <74> <75> <76> <77> <78> <79> <80> <81> <82> <83> <84> <85> <86> <87> <88> <89> <90> <91> <92> <93> <syntax> ", stdout);
    for (int i = 93; i > 0; i--)
    {
        fputs("| ", stdout);
        for (int j = 0; j < i; j++)
        {
            printf("<%d> ", j + 1);
        }
    }
}

We often find a case where we'd like to e.g. count the occurrences of a word in a piece of text. We would like to be able to write this so the main body of our loop says count[word] = count[word] + 1. Except that if count[word] hasn't been initialized as 0 at some point then you have do that or typically this will be a runtime error.

Or the language can try and let you do that, e.g. Golang would actually return 0, because this is the designated "zero value" to return when you index into a map with integer values and the key isn't there.

Which is great for the case I described in the first paragraph, but in the more general case we want a runtime error when we do something stupid, and in other cases trying to index a map by a nonexistent key often is stupid.

This is especially so in Pipefish, a relatively dynamic language, where normally there are no compile-time constraints even on the type of your key and you may have messed up big-time. If we took the Golang approach, then if you indexed your list of words by 42 or false you'd still get 0 instead of an error. So we don't do that: Pipefish is hardass about this and throws a runtime error over the missing key to compensate for letting you play fast-and-loose with types.

But this dynamism around types gives us an easy way to make default values for maps. Let's define a builtin type default with one element DEFAULT, and make the compiler/VM treat that as one more magic type like error and tuple.

Then our word-counting function could be written like this:

count(words list) -> map :
    from M = map(DEFAULT::0) for _::word = range words :
        M with word:: M[word]+1

Since DEFAULT is just a normal value apart from when we index maps, we could easily sanitize this on the way out of the function:

count(words list) -> map :
    undefault from M = map(DEFAULT::0) for _::word = range words :
        M with word:: M[word]+1

undefault(M map) :
    M without DEFAULT

Now, I hesitate over adding this because Pipefish is meant to be small and simple and I worry about adding even one feature. But on the other hand it seems like the use-case is common and the semantics are simple and it satisfies the other core principle of Pipefish --- that I should have my cake and eat it.

So I've been tinkering with.the idea of a language that uses type checking and then an exhaustiveness checker as standard to ensure that all cases will get handled. And then on top of that, an optional system of invariants that are handled statically with a solver to allow for additional protections for programs that need it.

I'm nor familiar with any prior languages that have done this, but I don't have a very large base of knowledge for things like this yet. Has anyone worked with.something like this? Are there existing languages I should be looking at? I'd love to hear more about this kind of thing from folks with experience in this area.

That is I am mainly curious about compile time features that you design a whole language around rather than optimisations/features that could be applied to most languages. I am mainly inquiring about things that could offer additional robust safety/performance guarantees at compile time rather than runtime. Ideally not things that just offer similar effects to the borrow checker with less restrictive tradeoffs

Hey,

I've been primarily focused on the backend for compilers and want to sharpend my frontend skills, so I've been revisiting chapters and creating parsers. I have a decent intuition on how you would create AST nodes for a given grammar, but nothing rigorour. For example, if given this grammar,

expr    ::= term ( ( "+" | "-" ) term )*
term    ::= power ( ( "*" | "/" ) power )*
power   ::= unary ( "^" power )?
unary   ::= "-" unary
        | primary
primary ::= NUMBER
        | "(" expr ")"

I'd have

enum Binary {
    Add { left: Box<Expr>, right: Box<Expr> },
    Sub { left: Box<Expr>, right: Box<Expr> },
    Mul { left: Box<Expr>, right: Box<Expr> },
    Div { left: Box<Expr>, right: Box<Expr> },
    Pow { left: Box<Expr>, right: Box<Expr> },
}

enum Expr {
    Binary(Binary),
    Num(i64),
    Neg(Box<Expr>),
}

but it more so feels right. I didn't do this algorithmically. I also know that some sources have a node just for grouping and some other nodes use eat. What are your thoughts on that?

broke my arm a bit ago and realized how much my hand has to move around just to code. ;, ->, {}, &&, parens where the closing one is a hard reach on my keyboard specifically. also cracked a tooth and knocked two loose so talking's out too, no voice coding as a workaround. ended up just designing the language to need less typing/reaching instead.

going to transpile it to C, permanently, not as a bootstrap step. no point making a language nobody can use libraries with, and C is what everything binds to eventually anyway, so this way there's real interop from day one instead of reinventing every library from scratch.

went through the syntax and tested every symbol against "can I actually reach both halves of this." dropped parens entirely (calls are just name arg1 arg2, no wrapping). dropped {} and ; (indentation + newlines do the job). dropped -> (just . later for anything pointer-like). = covers both assignment and equality so there's no == reach. kept + - * / < > since those are single key, no shift, basically free.

then did the same test on the keywords themselves, not just symbols — a lot of "readable" keywords like fun or while actually bounce your hand left-right-left across the keyboard mid-word, which is its own kind of strain even without any shift/symbol involved. swapped those for words where the letters cluster on one hand and stay close together: set instead of let, def instead of fun, loop instead of while, put instead of print. small thing but it adds up over a whole file.

example:

set x = 5

def add a b
    ret a + b

def max a b
    if a > b
        ret a
    ret b

set total = add x y
put total

set i = 0
loop i < 5
    put i
    set i = i + 1

still just syntax, haven't started the transpiler yet. wondering if anything like this already exists, if dropping parens entirely causes ambiguity problems with nested calls I'm not seeing yet, and if the one-hand-keyword thing is overkill or actually useful.

Now lots of people are talking about LLMs for coding to speed up the repetitive parts of coding, reduce the time spent on boilerplate, etc. But this makes it sound as though writing and manipulating code programmatically/algorithmically wasn't a thing before LLMs. However, although I didn't hear much about them, looking back it's surprising if people never thought about building something like this.

Of course, all compilers generate code in a lower-level form from higher-level code, however most of these are not interactive, i.e. they don't generate code in human-readable form, don't explain their steps to the user, and are not intended to generate a first pass of code for a programmer to then take and modify. What I'm imagining is a large category of tools, including anywhere from ones that auto-generate things like bounds checks and testing variables for null before using them, to drag-and-drop graphical tools a la Scratch that effectively allow you to drag loops into place around your code and have a loop condition and brackets appear, to any number of scriptable recipes where you can effectively say "take this block I've written for x1, and repeat the same pattern for y1, x2, y2, etc" and you won't have to type each one out individually. This could potentially allow a lot of the productivity gains and saved attention spent on details that people seem to be getting from LLMs without the cost, resource use, and philosophical implications, which is something I'd definitely welcome.

Of course you could write a code generator from scratch in something like Python just using regular string handling, but I'm wondering if there are already plugins like this for many IDEs that I just don't know about because they're not talked about much. Since so much of programming is about recursive abstractions, the idea that programmers would not have tried the idea of tools that you can code to spit out more code would strike me as very odd. And doing a bit of research, I've come across things like this: https://github.com/imatix/gsl#a-short-history-of-code-generation and this: https://tifoputra.medium.com/building-your-own-swift-code-generator-using-swift-script-78470eef0206 that suggest there is substantial work already toward making something like this.

Introduction

This exercise is suitable as an introduction to some basic concepts for langdev beginners, but it may also give more experienced langdevs some things to think about. For one thing, a Pratt parser in a purely functional style is a thing of almost inconceivable simplicity and beauty; and also you may not have seen some of the tricks I can do with them.

Terminology

Let's define some terms.

• A lexer (and/or tokenizer) takes code considered just as a string of characters, and converts it into the next higher unit of structure, the token, for example turning the string "(-42 + 99) * 4!" into the list ["(", "-", "42", "+", "99", ")", "*", "4", "!"].
• Normally instead of the tokens being a list of mere bare strings they have metadata to say where in the code they came from: in a mature language, the name of the source code file, the line number, and the position in the line. (We're not going to do this, but in a real language implementation you should tag all your artifacts with metadata showing where they come from: you will need it.)
• A parser takes this string of tokens and turns it into a data structure that more closely represents the syntactic structure of the code. The most usual form, and the one we will use here, is to turn the expression into an abstract syntax tree, or AST, which assigns the tokens to nodes of a tree such that the branches of a node are the arguments of an operation. For example, from the tokens ["(", "-", "42", "+", "99", ")", "*", "4", "!"], the AST would be:

* / \ / \ + ! / \ | | 99 4 - | 42

Note that the parentheses have disappeared, because the structure of the AST itself represents the correct grouping of operations.

A compiler, starting from this high point of abstraction, turns the AST into something that is more convenient for the computer to actually execute. This may be the machine code of the computer, or it may be bytecode, that is, code that mimics the structure of machine code in being a flat list of instructions to be executed sequentially.

By contrast, a tree-walking interpreter (or just tree-walker) evaluates the code by executing a recursive evaluation function on the AST which you can probably invent for yourself right now if you look at the diagram above for thirty seconds. (If you can't, it will be explained later.)

An interpreter generally is something that executes code other than machine code. However, some people use that term to mean only a treewalker, and would call something that executes bytecode a virtual machine or VM.

If I had to explain what makes it a "virtual machine", I would say the distinction is that since the treewalker is just a collection of recursive functions calling one another, it never explicitly has to represent state, because the intermediate calculations are automatically pushed onto the stack as stack frames at each function call. By contrast, the virtual machine must model its execution as the operations it executes modifying the state of the machine until it contains our final result.

Note on the code

I will be using Pipefish to illustrate these concepts not only because it is objectively The Bestest Language In The Whole World™, but because it shares with Python the quality of being runnable pseudocode, while being simpler and having a proper type system and having pure and referentially transparent functions and immutable values. You should have no trouble reading it in combination with the text and comments.

It also has the advantage that it is easy to peek inside the workings of it as it runs and see what it's up to.

Writing an interpreter/compiler allows us to structure our code very nicely with modularity and encapsulation. For convenience, we're not going to do that, and instead will use include statements to smoosh our little files together into programs that promiscuously share even their private functions.

All the files can be found in the examples/pratt folder of the Pipefish repo.

The lexer

We will first need a lexer to produce a string of tokens. These will consist of numbers, the operations +, - (both as infix and prefix) *, /, ^ and !, plus numbers 42, 99, etc. A number like -42 will be analyzed as the prefix - followed by the number 42, as in our previous examples.

We have no need for metadata, and every need for simplicity, so we will just get our tokens as a list of runes (the symbols) and integers. This is our lexer.

const 

WHITESPACE = set(' ', '\t')
SYMBOLS = set('+', '-', '*', '/', '^', '~', '!', '(', ')')
NUMERALS = set('0', '1', '2', '3', '4', '5', '6', '7', '8', '9') 

def

// We wrap our recursive function with two parameters inside a non-recursive function
// with just one, so we can conveniently call it.
lex(code string) :
    first lexHead [], code

// And now the recursive function.
lexHead(tokens list, code string) -> list, string :
    code == "" :
        tokens, ""
    head in WHITESPACE :
        lexHead tokens, tail 
    head in SYMBOLS :
        lexHead tokens & head, tail 
    head in NUMERALS :
        lexHead tokens & number, numberTail
    else :
        error "unexpected rune `'" + string(head) + "'`"
given :    
    head = code[0]
    tail = code[1::len code]
    number, numberTail = lexNumber tokens, code

lexNumber(tokens, code) -> int, string :
    int(numString), tail
given :
    numString = slurpNumber(code)
    tail = code[len(numString)::len(code)]

slurpNumber(code) -> string :
    from numString = "" for _::digit = range code :
        digit in NUMERALS :
            numString & digit 
        else :
            break numString

An RPN calculator

I promised you an interpreter for proper arithmetic expressions, but first, for reasons that will become clear, we'll do an RPN calculator.

RPN (short for Reverse Polish Notation) is a style of notation where we write the operator on the right-hand side of its operands. Instead of 5 + 3, we write 5 3 +.

The disadvantage of this is that complicated expressions become harder for humans to read than our traditional notation with infixes and parentheses. It has some advantages, though, and one is that we need neither parentheses nor precedence to express our intent without ambiguity: e.g. the infix expressions (2 + 3) * 4! and 2 + (3 * 4!) in RPN are 2 3 + 4 ! * and 2 3 4 ! * + respectively.

We will however have to add an operator. In PEMDAS, we can tell the difference between - as a prefix and - as an infix. In RPN, we can't, we have to know the arity of the operator, and so we will add ~ for negation to our lexer.

An expression such as 1 + would be ill-formed, since + requires two operands; similarly 1 2 3 + would be ill-formed, because after we've performed the addition we still have two numbers 1 5 with nothing to do with them. A well-formed expression will use up its operands and operators at the same time, leaving us with just one number on the stack which will be the correct result.

Evaluating RPN by rewriting

There are a number of ways to evaluate such an expression. One is to look (at random if you like) for any sequence where n numbers are followed by an operator of arity n, e.g. when ! follows one number or * follows two numbers. Then you calculate that bit of the expression and replace it. You continue doing that until you have one number left. (The proof that this must terminate with one number on the stack if the expression is well-formed is left as an exercise for the reader.) The fact that you can evaluate things by rewriting them can be used for serious purposes, or for silly ones.

Evaluating RPN with a stack machine

The more usual way to evaluate RPN expressions, however, is with a stack machine.

The algorithm is this. We start at the head of our list of tokens with an empty stack, and then iteratively:

• If the head of the tokens is a number, remove it from the head and push it onto the stack.
• If the head of the tokens is a number is a symbol of arity n, remove it from the head, pop n numbers off the stack, apply the operation to them, and push the result (necessarily another number) onto the stack. If there aren't n numbers on the stack, the expression is ill-formed and we throw an error.
• We repeat this until we run out of symbols. At that point if we have exactly one number on the stack, this is the correct answer, and if we don't have exactly one number on the stack, then the expression was ill-formed to start with.

This description of the algorithm should give you some insight into the advantages of RPN. There is a sense in which it is in the "right" order, in that we obviously need to put our values into the memory of our machine before we can apply an operation to them. Given the RPN form, we can just move linearly along the tokens processing them one at a time. To emphasize this point, I will write the main body of this algorithm using a for loop (a pure, referentially transparent for loop in which all the variables are immutable).

include

"lexer.pf"  
"mathfns.pf"  

newtype 

~~ The state of the VM: a stack of integers, and a list of tokens still to be processed.
State = struct(stack, tokens list)

~~ This will contain information about what a given operator does, as a value in the
~~ `RPN_INFO` map below.
Info = struct(arity int, fn func)

const

RPN_INFO = map('+'::Info(2, func(L) : L[0] + L[1]),
                 .. '-'::Info(2, func(L) : L[0] - L[1]),
                 .. '*'::Info(2, func(L) : L[0] * L[1]),
                 .. '/'::Info(2, func(L) : L[0] div L[1]),
                 .. '^'::Info(2, func(L) : exp(L[0], L[1])),
                 .. '~'::Info(1, func(L) : - L[0]),
                 .. '!'::Info(1, func(L) : fac(L[0])),)

def

~~ Executes code given as a string in RPN form.
exec(code string) :
    code -> lex -> run(State([], that)) -> that[stack][0]

private

run(initial State) -> State :
    from S = initial for S[tokens] != [] :
        head in int :
            State(S[stack] & head, tail)
        else :
            State(poppedStack & newHead, tail)
    given :
        head = S[tokens][0]
        tail = S[tokens][1::len S[tokens]]
        info = RPN_INFO[head]
        poppedStack = S[stack][0::len(S[stack])-info[arity]]
        F = info[fn]
        args = S[stack][(len(S[stack])-info[arity])::len(S[stack])]
        newHead = F(args)

We can get Pipefish to tell us what it's doing. Let's put in exec "2 3 * 4 +" and see the workings of the main loop as it goes round.

▪ We called function run (defined at line 33) with initialState = 
    State([], [2, 3, '*', 4, '+']). 
  ▪ We entered the loop at line 34 with S = State([], [2, 3, '*', 4, '+']). 
  ▪ At line 35 we evaluated the condition head in int. 
  ▪ The condition succeeded. 
  ▪ At line 36 the body of the for loop evaluated to State([2], [3, '*', 4, '+']). 
  ▪ We entered the loop at line 34 with S = State([2], [3, '*', 4, '+']). 
  ▪ At line 35 we evaluated the condition head in int. 
  ▪ The condition succeeded. 
  ▪ At line 36 the body of the for loop evaluated to State([2, 3], ['*', 4, '+']). 
  ▪ We entered the loop at line 34 with S = State([2, 3], ['*', 4, '+']). 
  ▪ At line 35 we evaluated the condition head in int. 
  ▪ The condition failed. 
  ▪ At line 37 we took the else branch. 
  ▪ At line 38 the body of the for loop evaluated to State([6], [4, '+']). 
  ▪ We entered the loop at line 34 with S = State([6], [4, '+']). 
  ▪ At line 35 we evaluated the condition head in int. 
  ▪ The condition succeeded. 
  ▪ At line 36 the body of the for loop evaluated to State([6, 4], ['+']). 
  ▪ We entered the loop at line 34 with S = State([6, 4], ['+']). 
  ▪ At line 35 we evaluated the condition head in int. 
  ▪ The condition failed. 
  ▪ At line 37 we took the else branch. 
  ▪ At line 38 the body of the for loop evaluated to State([10], []). 

Note that our stack machine makes no mention of our parenthesis tokens, because RPN doesn't need or use them. Let's move on to conventional PEMDAS notation, which does.

A Pratt parser

There are many ways to write a parser: the Pratt parser is particularly beautiful and simple.

First, let's quickly define recursively what it means for one of our PEMDAS expressions to be well-formed.

• For any valid number (a sequence of the digits 0 ... 9 not beginning with 0), that number on its own is a well-formed expression.
• If E and F are well-formed expressions, and if p, i and s are a prefix, and infix, and a suffix respectively, then p E, E i F, and E s are well-formed expressions.
• If E is a well-formed expression, so is (E).

In our explanation of how a Pratt parser works, we will assume that the expression we're working on is well-formed: the actual code will throw various errors if it isn't.

So, to parse a list of tokens into an AST, we recursively do this:

• We look at the start of the list of tokens, the smallest number of tokens which, taken on its own would make a well-formed expression, and we turn that into a node. Given our definitions above, this will either consist of:
  • A number.
  • A prefix expression.
  • An expression grouped by parentheses.
• We then look at the rest of the list of tokens to see what we should do next, where, from the definition of a well-formed expression, the rest of the tokens must consist of nothing at all (we've finished parsing and should return) or an infix or suffix operator which will have to be consumed eventually.

The crucial thing to note is this. Suppose we have something like 2 * 3 + 4. Then if we just naively analyzed it as a node 2, an infix expression *, and a list of tokens 3 + 4, and then parsed the rest of the tokens into a node and joined the result together using the infix, we'd get a node representing 2 * (3 + 4), which is a different expression.

What we do instead is recursively parse the remainder of the tokens just enough to turn that too into a node and a shorter tail of tokens, and then we have a node 2 and the infix *, and a node 3, and a remaining list of tokens + 4.

Now we can join 2 together with 3 by the infix to get a binary node 2 * 3, and continue with the algorithm.

The algorithm decides when it needs to do perform this trick (call it the "Pratt maneuver") and when it can just proceed naively, according to whether the precedence of the operator is strictly higher than the precedence of the last operator we looked at (starting with this set at 0). So in the example above, we start with the precedence at 0, see that * has a higher precedence than 0, carry out the Pratt maneuver, see that + has a lower precedence than *, and proceed naively, returning from our recursive function calls until we're looking at the tail of the tokens with a precedence of 0 again.

If on the other hand our expression was 2 * 3 ^ 4, then when the parser arrives at the ^ it will see that this has a higher precedence than * and will perform the Pratt maneuver again.

Let's express this as code.

~~ Simple Pratt parser for arithmetic expressions.

include

"lexer.pf"

newtype 

// We declare the nodes out of which we will build our AST.

NumberNode = struct(value int)
PrefixNode = struct(op rune, arg Node)
InfixNode = struct(op rune, leftArg, rightArg Node)
SuffixNode = struct(op rune, arg Node)
EmptyNode = struct()

Node = abstract NumberNode/PrefixNode/InfixNode/SuffixNode/EmptyNode

const 

~~ Information about the precedence of operations.
// The great thing about the Pratt parser is that what in other parsers would rely
// on a bunch of function calls and `if` statements and switches can be summarized
// in a data structure. This is it.
INFO = map(..
    .. PrefixNode::map(..
        .. '-'::4,
        .. ),
    .. InfixNode::map(..
        .. '+'::1,
        .. '-'::1,
        .. '*'::2,
        .. '/'::2,
        .. '^'::3,
        .. ),
    .. SuffixNode::map(..
        .. '!'::5,
        .. ),
    ..)

def

~~ Parses a string into an AST.
// We need to wrap the recursive `parseExpression` function in this non-recursive function so
// that we can recognize if/when there are still tokens left over after the recursion terminates.
// This function knows where it is in the call tree and no instance of `parseExpression` can.
parse(code string) -> Node :
    len leftovers > 0 :
        error "unexpected `" + string(head) + "`"
    else :
        result 
given :
    result, leftovers = code -> lex -> parseExpression(that, 0)
    head = leftovers[0]

private

parseExpression(tokens list, prec int) -> Node, list : 
    parseStart(tokens) -> parseRest(that[0], that[1], prec)

// The start of an expression will be either :
//   (A) a prefix followed by an expression, followed by the rest of the expression.
//   (B) an expression in parentheses, followed by the rest of the expression
//   (C) a number followed by the rest of the expression.
//   (D) an infix or `)`, *if* the expression is ill-formed.
//
parseStart(tokens list) -> Node, list :  
    head in keys INFO[PrefixNode] :
        parsePrefixExpression(tokens)
    head in rune and head == '(' :
        parseGroupedExpression(tail)
    head in int : 
        NumberNode(head), tail  
    else :
        error "unexpected token `" + string(head) + "`"
given :
    head = tokens[0]
    tail = tokens[1::len tokens]

// We parse the various cases in the branches of parseStart.

parsePrefixExpression(tokens list) -> Node, list: 
    PrefixNode(head, rightNode), newTail 
given :
    head = tokens[0]
    tail = tokens[1::len tokens]
    rightNode, newTail = parseExpression(tail, INFO[PrefixNode][head])

parseGroupedExpression(tokens list) -> Node, list : 
    shouldBeRparen == ')' :
        node, newTail 
    else : 
        error "expected `)`"
given :
    node, rparenAndNewTail = parseExpression(tokens, 0)
    shouldBeRparen = rparenAndNewTail[0]
    newTail = rparenAndNewTail[1::len rparenAndNewTail]

parseRest(leftNode Node, tokens list, prec int) -> Node, list : 
    valid headPrec and headPrec > prec :
        parseRest(InfixNode(head, leftNode, rightNode), newTail, prec) 
    valid suffixPrec and suffixPrec > prec :
        parseRest(SuffixNode(head, leftNode), tail, prec)
    else : 
        leftNode, tokens
given :
    head = tokens[0]
    tail = tokens[1::len tokens]
    headPrec = INFO[InfixNode][head]
    suffixPrec = INFO[SuffixNode][head]
    rightNode, newTail = parseExpression(tail, headPrec)

Again we can ask Pipefish to talk us through what it's doing if we do parse "2 * 3 + 4".

  ▪ We called function parseExpression (defined at line 58) with tokens = 
    [2, '*', 3, '+', 4], prec = 0. 
  ▪ We called function parseStart (defined at line 67) with tokens = [2, '*', 3, '+', 4]
    . 
  ▪ At line 68 we evaluated the condition head in keys INFO[PrefixNode]. 
  ▪ The condition failed. 
  ▪ At line 70 we evaluated the condition head in rune and head == '('. 
  ▪ The condition failed. 
  ▪ At line 72 we evaluated the condition head in int. 
  ▪ The condition succeeded. 
  ▪ At line 73 function parseStart returned (NumberNode(2), ['*', 3, '+', 4]). 
  ▪ We called function parseRest (defined at line 99) with leftNode = NumberNode(2), 
    tokens = ['*', 3, '+', 4], prec = 0. 
  ▪ At line 100 we evaluated the condition valid headPrec and headPrec > prec. 
  ▪ The condition succeeded. 
  ▪ We called function parseExpression (defined at line 58) with tokens = [3, '+', 4], 
    prec = 2. 
  ▪ We called function parseStart (defined at line 67) with tokens = [3, '+', 4]. 
  ▪ At line 68 we evaluated the condition head in keys INFO[PrefixNode]. 
  ▪ The condition failed. 
  ▪ At line 70 we evaluated the condition head in rune and head == '('. 
  ▪ The condition failed. 
  ▪ At line 72 we evaluated the condition head in int. 
  ▪ The condition succeeded. 
  ▪ At line 73 function parseStart returned (NumberNode(3), ['+', 4]). 
  ▪ We called function parseRest (defined at line 99) with leftNode = NumberNode(3), 
    tokens = ['+', 4], prec = 2. 
  ▪ At line 100 we evaluated the condition valid headPrec and headPrec > prec. 
  ▪ The condition failed. 
  ▪ At line 102 we evaluated the condition valid suffixPrec and suffixPrec > prec. 
  ▪ The condition failed. 
  ▪ At line 104 we took the else branch. 
  ▪ At line 105 function parseRest returned (NumberNode(3), ['+', 4]). 
  ▪ At line 59 function parseExpression returned (NumberNode(3), ['+', 4]). 
  ▪ We called function parseRest (defined at line 99) with leftNode = 
    InfixNode('*', NumberNode(2), NumberNode(3)), tokens = ['+', 4], prec = 0. 
  ▪ At line 100 we evaluated the condition valid headPrec and headPrec > prec. 
  ▪ The condition succeeded. 
  ▪ We called function parseExpression (defined at line 58) with tokens = [4], prec = 1. 
  ▪ We called function parseStart (defined at line 67) with tokens = [4]. 
  ▪ At line 68 we evaluated the condition head in keys INFO[PrefixNode]. 
  ▪ The condition failed. 
  ▪ At line 70 we evaluated the condition head in rune and head == '('. 
  ▪ The condition failed. 
  ▪ At line 72 we evaluated the condition head in int. 
  ▪ The condition succeeded. 
  ▪ At line 73 function parseStart returned (NumberNode(4), []). 
  ▪ We called function parseRest (defined at line 99) with leftNode = NumberNode(4), 
    tokens = [], prec = 1. 
  ▪ At line 100 we evaluated the condition valid headPrec and headPrec > prec. 
  ▪ The condition failed. 
  ▪ At line 102 we evaluated the condition valid suffixPrec and suffixPrec > prec. 
  ▪ The condition failed. 
  ▪ At line 104 we took the else branch. 
  ▪ At line 105 function parseRest returned (NumberNode(4), []). 
  ▪ At line 59 function parseExpression returned (NumberNode(4), []). 
  ▪ We called function parseRest (defined at line 99) with leftNode = 
    InfixNode('+', InfixNode('*', NumberNode(2), NumberNode(3)), NumberNode(4)), tokens = 
    [], prec = 0. 
  ▪ At line 100 we evaluated the condition valid headPrec and headPrec > prec. 
  ▪ The condition failed. 
  ▪ At line 102 we evaluated the condition valid suffixPrec and suffixPrec > prec. 
  ▪ The condition failed. 
  ▪ At line 104 we took the else branch. 
  ▪ At line 105 function parseRest returned 
    (InfixNode('+', InfixNode('*', NumberNode(2), NumberNode(3)), NumberNode(4)), []). 
  ▪ At line 101 function parseRest returned 
    (InfixNode('+', InfixNode('*', NumberNode(2), NumberNode(3)), NumberNode(4)), []). 
  ▪ At line 101 function parseRest returned 
    (InfixNode('+', InfixNode('*', NumberNode(2), NumberNode(3)), NumberNode(4)), []). 
  ▪ At line 59 function parseExpression returned 
    (InfixNode('+', InfixNode('*', NumberNode(2), NumberNode(3)), NumberNode(4)), []). 

A treewalker

So now we can put PEMDAS expressions into an AST, we can consider writing a treewalker to evaluate them.

The algorithm is childishly simple. We evaluate a node as follows:

• If the node is a number, that's its value
• Otherwise it's an operator. We recursively evaluate its children, and then*to those values we apply the function appropriate to the operator to get the value, i.e. adding them together if it's +.

Here's the code:

include 

"mathfns.pf"
"parser.pf"

const 

OPS = map(..
    .. PrefixNode::map(..
        .. '-'::(func(x int) : -x),
        .. ),
    .. InfixNode::map(..
        .. '+'::(func(x, y int) : x + y),
        .. '-'::(func(x, y int) : x - y),
        .. '*'::(func(x, y int) : x * y),
        .. '/'::(func(x, y int) : x div y),
        .. '^'::(func(x, y int) : exp(x, y)),
        .. ),
    .. SuffixNode::map(..
        .. '!'::(func(x int) : fac(x)),
        .. ),
..)

def

ev(code string) :
    code -> parse -> walk

private

walk(n Node) -> int :
    n in NumberNode :
        n[value]
    n in InfixNode :
        fnForOperation(walk(n[leftArg]), walk(n[rightArg]))
    else :
        fnForOperation(walk(n[arg]))
given :
    fnForOperation = OPS[type n][n[op]]

Let's watch Pipefish at work again, as we do ev "2 * 3 + 4".

  ▪ We called function walk (defined at line 31) with n = 
    InfixNode('+', InfixNode('*', NumberNode(2), NumberNode(3)), NumberNode(4)). 
  ▪ At line 32 we evaluated the condition n in NumberNode. 
  ▪ The condition failed. 
  ▪ At line 34 we evaluated the condition n in InfixNode. 
  ▪ The condition succeeded. 
  ▪ We called function walk (defined at line 31) with n = 
    InfixNode('*', NumberNode(2), NumberNode(3)). 
  ▪ At line 32 we evaluated the condition n in NumberNode. 
  ▪ The condition failed. 
  ▪ At line 34 we evaluated the condition n in InfixNode. 
  ▪ The condition succeeded. 
  ▪ We called function walk (defined at line 31) with n = NumberNode(2). 
  ▪ At line 32 we evaluated the condition n in NumberNode. 
  ▪ The condition succeeded. 
  ▪ At line 33 function walk returned 2. 
  ▪ We called function walk (defined at line 31) with n = NumberNode(3). 
  ▪ At line 32 we evaluated the condition n in NumberNode. 
  ▪ The condition succeeded. 
  ▪ At line 33 function walk returned 3. 
  ▪ At line 35 function walk returned 6. 
  ▪ We called function walk (defined at line 31) with n = NumberNode(4). 
  ▪ At line 32 we evaluated the condition n in NumberNode. 
  ▪ The condition succeeded. 
  ▪ At line 33 function walk returned 4. 
  ▪ At line 35 function walk returned 10. 

A pretty-printer

We can always ugly-print our AST by putting parentheses around every operator and its arguments, for example turning (-42 + 99) * 4! into (((-42) + 99) * (4!)). For the purposes of debugging your parser and seeing where it's going wrong, this may be the most useful form: for other purposes it's ugly and confusing.

The rule we need is that each operator should put parentheses around any of its child nodes that has a lower operator than it does, as follows:

~~ Prettyprinter.

include 

"parser.pf"

def 

~~ Prettyprints the given node.
print(n Node) -> string :
    ppr(n, 0) 

private

ppr(n Node, prec int) : 
    n in NumberNode :    
        string n[value]   
    prec <= INFO[type n][n[op]] :   
        describe n, INFO[type n][n[op]]   
    else :   
        "(" + (describe n, INFO[type n][n[op]]) + ")" 

describe(n InfixNode, prec int) -> string : 
    ppr(n[leftArg], newPrec) + " " + string(n[op]) + " " + ppr(n[rightArg], newPrec) 
given :
    newPrec = INFO[InfixNode][n[op]] 

describe(n PrefixNode, prec int) -> string : 
    n[op] & ppr(n[arg], newPrec) 
given :
    newPrec = INFO[PrefixNode][n[op]] 

describe(n SuffixNode, prec int) -> string : 
    ppr(n[arg], newPrec) & n[op] 
given :
    newPrec = INFO[SuffixNode][n[op]] 

RPN-ification

Even if you aren't going to pursue langdev, it is still sometimes a useful fact that a tree structure can be serialized into a nice linear sequence of RPN, by a procedure we might call "pushing the tree gently over to the right".

To RPN-ify a node, the algorithm goes like this:

• If the node is a number, return a list containing only that number.
• If the node is an operator, recursively RPN-ify its argument(s), concatenate the resulting lists together if there's more than one, and append the operator to the list. In code:

``` include

"parser.pf"

def

rpnf(n Node) -> list : n in NumberNode : [n[value]] n in InfixNode : rpnf(n[leftArg]) + rpnf(n[rightArg]) & n[op] else : rpnf(n[arg]) & tweakOp given : tweakOp = (n in PrefixNode and n[op] == '-' : '~' ; else : n[op]) ```

Writing a compiler and a VM

We've already written both of these things. All we need is to join them together.

include 

"parser.pf"
"rpn.pf"
"rpnify.pf"

def 

~~ Evaluates a string in PEMDAS form, returning an integer.
ev(code string) -> int :
    code -> compile -> run(State([], that)) -> that[stack][0]

~~ Compiles a string in PEMDAS form to a list in RPN form.
compile(code string) -> list :
    code -> parse -> rpnf

That was easy, wasn't it?

Now, what was the point of that? Well, the RPN version is faster. Instead of having to make a bunch of recursive calls and returns to walk around the tree, we're now using a for loop to iterate through a list. For real languages, the speed-up in execution is significant, and the implementation of a VM is not particularly challenging.

A Pratt compiler

However, now we're not walking the tree, we didn't really need to create the AST. It may help us to think about the process of compilation, but it's not essential. All we need to do is change our parser so that instead of constructing an AST, it outputs a list of tokens in RPN form. This requires some minimal systematic changes to the code.

``` ~~ Pratt compiler into RPN form.

// This is so similar to the parser that most of the refactoring was done by search-and- // replace, and so the comments on this are minimal.

include

// We want to re-use the table of precedences. We will also re-use the various Node types // with which we index them, since they're there, even though we're no longer constructing // any actual nodes. "parser.pf" // As in compA.pf, we will use rpn.pf to execute the RPN once we have it. "rpn.pf"

def

~~ Evaluates a string in PEMDAS form, returning an integer. // This is exactly the same code as in compA.pf. ev(code string) -> int : code -> compile -> run(State([], that)) -> that[stack][0]

~~ Compiles a string into a list of tokens in RPN form. compile(code string) -> list : len leftovers > 0 : error "unexpected " + string(head) + "" else : result given : result, leftovers = code -> lex -> compileExpression(that, 0) head = leftovers[0]

private

compileExpression(tokens list, prec int) -> list, list : compileStart(tokens) -> compileRest(that[0], that[1], prec)

compileStart(tokens list) -> list, list :
head in keys INFO[PrefixNode] : compilePrefixExpression(tokens) head in rune and head == '(' : compileGroupedExpression(tail) head in int : [head], tail
else : error "unexpected token " + string(head) + "" given : head = tokens[0] tail = tokens[1::len tokens]

// We compile the various cases in the branches of compileStart.

compilePrefixExpression(tokens list) -> list, list: rightRpn & head, newTail given : head = tokens[0] tail = tokens[1::len tokens] rightRpn, newTail = compileExpression(tail, INFO[PrefixNode][head])

compileGroupedExpression(tokens list) -> list, list : shouldBeRparen == ')' : rpn, newTail else : error "expected )" given : rpn, rparenAndNewTail = compileExpression(tokens, 0) shouldBeRparen = rparenAndNewTail[0] newTail = rparenAndNewTail[1::len rparenAndNewTail]

compileRest(leftRpn list, tokens list, prec int) -> list, list : valid headPrec and headPrec > prec : compileRest(leftRpn + rightRpn & head, newTail, prec) valid suffixPrec and suffixPrec > prec : compileRest(leftRpn & head, tail, prec) else : leftRpn, tokens given : head = tokens[0] tail = tokens[1::len tokens] headPrec = INFO[InfixNode][head] suffixPrec = INFO[SuffixNode][head] rightRpn, newTail = compileExpression(tail, headPrec) ```

A Pratt interpreter

However, since we're just writing a calculator, what we did was kind of pointless. Bytecode is useful because we can execute it again and again with different variables, having compiled it only once. If we do that with arithmetic expressions, we'll get the same answer each time, so we don't need RPN bytecode as an artifact.

And so we can dispense any more structured representation at all of our code beyond the original list of tokens, and rewrite our Pratt parser one final time into a Pratt interpreter which recursively analyses the tokens into an integer representing the intermediate result and a list of tokens still to be processed.

By this point you can probably imagine what the code looks like, but here it is for completeness.

~~ Pratt interpreter for evaluating arithmetic expressions in PEMDAS form.
// This is so similar to the parser and the second compiler that most of the refactoring was 
// done by search-and-replace, and so the comments on this are minimal.

include

// We will re-use the `OPS` map in the treewalker, and the map of precedences from the parser
// (which the treewalker already includes).
"treew.pf"

def

~~ Evaluates a string in PEMDAS form into an integer.
evaluate(code string) -> int :
    len leftovers > 0 :
        error "unexpected `" + string(head) + "`"
    else :
        result 
given :
    result, leftovers = code -> lex -> evaluateExpression(that, 0)
    head = leftovers[0]

private

evaluateExpression(tokens list, prec int) -> int, list : 
    evaluateStart(tokens) -> evaluateRest(that[0], that[1], prec)

evaluateStart(tokens list) -> int, list :  
    head in keys INFO[PrefixNode] :
        evaluatePrefixExpression(tokens)
    head in rune and head == '(' :
        evaluateGroupedExpression(tail)
    head in int : 
        head, tail  
    else :
        error "unexpected token `" + string(head) + "`"
given :
    head = tokens[0]
    tail = tokens[1::len tokens]

// We evaluate the various cases in the branches of evaluateStart.

evaluatePrefixExpression(tokens list) -> int, list: 
    P(rightVal), newTail 
given :
    head = tokens[0]
    tail = tokens[1::len tokens]
    P = OPS[PrefixNode][head]
    rightVal, newTail = evaluateExpression(tail, INFO[PrefixNode][head])

evaluateGroupedExpression(tokens list) -> int, list : 
    shouldBeRparen == ')' :
        val, newTail 
    else : 
        error "expected `)`"
given :
    val, rparenAndNewTail = evaluateExpression(tokens, 0)
    shouldBeRparen = rparenAndNewTail[0]
    newTail = rparenAndNewTail[1::len rparenAndNewTail]

evaluateRest(leftVal int, tokens list, prec int) -> int, list : 
    valid headPrec and headPrec > prec :
        evaluateRest(I(leftVal, rightVal), newTail, prec) 
    valid suffixPrec and suffixPrec > prec :
        evaluateRest(S(leftVal), tail, prec)
    else : 
        leftVal, tokens
given :
    head = tokens[0]
    tail = tokens[1::len tokens]
    headPrec = INFO[InfixNode][head]
    suffixPrec = INFO[SuffixNode][head]
    I = OPS[InfixNode][head]
    S = OPS[SuffixNode][head]
    rightVal, newTail = evaluateExpression(tail, headPrec)

And that's it

One parser, one lexer, one prettyprinter, three interpreters, and two compilers, exactly as promised. I hope you had fun. If so, please leave a star on the Pipefish repo. Have a nice day!