fml

A small ML-family language implemented from scratch in F#. Lexer, parser, type system and evaluator - a complete chain from source to result.

TL;DR

A small ML-family language built from scratch in F#: a lexer, a parser, a type system and an evaluator - the full path from source text to a result. The hardest part is the type system.

Overview

fml is a small ML-family programming language, built from scratch in F#. It has four links that together lead from source text to a result: a lexer, a parser, a type system and an evaluator. Each does one thing, but the most interesting and the hardest is the type system.

Your own language is a project that teaches humility. It is not one problem but a whole sequence where the output of one stage is the input to the next, and a mistake at an early stage comes back with double force three steps later. That is exactly why it is such a good exercise in thinking about systems.

Source text has to be cut into tokens, tokens arranged into a tree, the tree checked for types, and finally executed. It is a chain where you cannot cheat at any stage, because the next one catches it at once - or, worse, does not, and the bug only surfaces at the end as an incomprehensible result.

That dependence between stages is both the difficulty and the beauty of the project. Each link can be understood on its own, but only together do they make something that actually runs a program. Designing the boundaries between them to be clean is half the battle.

Types you do not have to write

In an ML-family language the type system is the most interesting part. You do not write types by hand - the compiler infers them from how you use values. You write an ordinary function, and the language works out its type on its own and makes sure you never use it in a way that contradicts it.

example.fml · fsharp

let rec map f xs =
  match xs with
  | [] -> []
  | x :: rest -> f x :: map f rest

map (fun n -> n + 1) [1; 2; 3]

Note

Nowhere in this code did we write a single type, and yet the language knows that map has the type (a -> b) -> list a -> list b. That is type inference - one of the most beautiful things you can write by hand, and at the same time one of the most demanding.

Four stages from text to result

The whole path breaks into four steps with clearly divided roles. Text becomes tokens, tokens a tree, the tree gets types, and finally it is computed. Type mismatches surface at the third stage, before running, not during execution.

Lexer

source text becomes a stream of tokens.

Parser

tokens arrange into a syntax tree.

Type system

every expression gets a type, and mismatches surface here, not at runtime.

Evaluator

the tree is computed down to a result.

The compiler chain

Stage	Input	Output
Lexer	source text	tokens
Parser	tokens	syntax tree
Type system	tree	typed tree
Evaluator	tree	result

The result: an ML language written in an ML language

What comes out is a small but complete language that genuinely runs a program - from the first character in a file to a computed result. F# was the natural choice here, because it belongs to the ML family itself, and writing an ML language in an ML language has something pleasantly recursive about it. It is a project after which the word "compiler" stops being an abstraction.

More projects

More work from the same category - see how we tackle similar challenges.

Have a similar project?

Get in touch - a quote is free and comes back within an hour.