FASTO: Implementing concurrency in a functional language

For my bachelor thesis I am, as the title suggests, working on implementing concurrency in a functional programming language. The language in question is FASTO, a relatively simple, sequential and functional language from my undergrad course in Implementation of Programming Languages at the University of Copenhagen.

In the course we were tasked with building both an interpreter and a compiler from FASTO to RISC-V32, written in F#. I am now extending them with support for concurrency with communicating threads.

On this page I will document the general process from beginning to end, keep notes on how the language works, and dive into the non-trivial details of the compiler and this task. Hopefully, all this documentation will help me understand the scope of the project — and get a good grade for my final exam. Deadline: June 2026

Some TMI background and disclaimers

When it neared my time to write my bachelor thesis, I honestly had zero ideas for what to write. I have been studying this for over 2 years at this point, and still felt like an imposter. I did okay in my classes, understood things when I really sat down to do so and could read code better than I could write it. I haven't found a niche in the field that I was particularly drawn to compared to others. But I knew I didn't want to do something too out of my scope and something that required tons of interviews with people as I knew I wouldn't have the capacity for either. In other words, I was kind of dreading this.

Throughout my bachelor I found that I was better at understanding the 'hows' and 'whys' of computers more than sitting down and figuring out the 'what' (though they are all related of course). This meant, despite my mediocre grades, I enjoyed courses that focused on low-level stuff and the back-end more, even if I struggled to understand. So I guess I didn't as much find my niche than just choose the thing I believed I was best at to be my 'niche'.

So here I am, pulling my hairs out because of compilers every day. I'm not an expert, I'm just decent at coding, I don't claim to know everything and I am so stressed about this, but I am quite happy and relieved I chose this regardless. In the end, I learn so much the more time I spend on this project. Proceed with this in mind.

Project Background: Fasto and its compiler

Fasto is a simple, strongly-typed, first-order functional language, which supports arrays. Strongly typed meaning, in this context and to my professors liking, that types must be declared and conversion between them are not allowed. First-order meaning that we cannot pass functions as arguments. It does not support modifying variables, meaning that, with exception to its I/O read and write operations, FASTO is purely functional.

The syntax is quite long to include here and trivial for the current task at hand, but it has the basic semantic categories of: Prog, FunDecs, Fun, Params, Type, Exp, Exps, FunArg. And its semantics are similar to that of F#.

Here is an example of how the fibonacci function would be written in fasto:

fun int fib(int n) =
  if n == 0 then 0
  else if n == 1 then 1
  else fib(n - 1) + fib(n - 2)

fun int main() =
  let n = read(int) in
  write(fib(n))

As mentioned we have already built the compiler from FASTO to RISC-V32 written in F#. The compiler is built out of the basic building blocks for any compiler including a lexer, parser, typechecker and finally machine code generation. On top of this we also have an interpreter for FASTO, which is also written in F#. As of project start, the compiler and interpreter work as expected, so there was no need to modify anything about the compiler at project beginning.

If you want to see more of the compiler before added functionality such that it works correctly in terms of specification, here is the public github page: click mee

Project idea: Concurrency

FASTO is as said sequential, meaning only one instruction is executed at a time, operating on a single thread. We want to, of course, add support for concurrency, which means allowing a multi-threaded execution. With how FASTO looks like now and the limit of time we have, we are not aiming for true parallelism, but concurrency by context-switching, meaning control switches between threads so fast that it gives the illusion of simultaneous execution

The model of concurrency we want to implement is message-passing. This means that threads communicate through a channel instead of having shared memory, which also prevents the problem of data races (multiple threads accessing and modifying a shared value in memory simultaneously).

In particular we want to support following functions in FASTO:

spawn : (() -> int) -> pid     // spawn a new process running anonymous function
await : (pid) -> int           // wait for process to terminate, return its result
channel : () -> chan           // create a new channel
send : (chan, int) -> int      // send a value on channel. wait if channel is full.
receive : (chan) -> int        // wait for, and receive, next value from channel

With two new primitive types

pid     //thread id
chan    //channel

This allows fx a thread to send a message to a channel and another to receive it from the same channel. In this way channels acts as communication mechanisms between threads, allowing them to exchange values and synchronize execution without sharing memory.

We would for example be able to write this simple program in FASTO:

fun int main() =
  let c = channel () in
  let p = spawn(fn int () => producer(c)) in
  let x1 = receive(c) in
  let x2 = receive(c) in
  let r = await(p)
  in write(x1+x2+r) // should print 60

fun int producer(chan c) =
  let d = send(c, 10) in
  let d = send(c, 20) in
  30