A garden of small programming language implementations šŖ“
Some toy programming language implementations, mostly implemented in OCaml.
These projects are mostly my attempt to understand different techniques and approaches to implementing programming languages. Perhaps from these seedlings something new and interesting might germinate?
Elaboration is an approach to implementing language front-ends where a complicated, user friendly surface language is type checked and lowered to a simpler, typed core language. This approach to type checking is particularly popular and useful for implementing dependently typed programming languages, but is more widely applicable as well.
Simply typed:
Polymorphically typed:
Dependently typed:
These are related to compilation. Mainly to stack-machines, but Iām interested in exploring more approaches in the future, and other compilation passes related to compiling functional programming languages.
Miscellaneous programming language experiments.
While most of the above projects need more work put into them, the following projects need more work put into them and a more incomplete in comparison.
As Iāve been working in the area of programming languages Iāve often found myself in the position of:
My hope is that by collecting some of these projects and experiments together into a single repository they might be useful to others and my future self.
The metaphor of a āgardenā as related to knowledge work was inspired by the rising popularity of ādigital gardeningā (which apparently originates from Hypertext Gardens). While this project is less directly interconnected than other digital gardens, I still like the idea of each project being a āseedlingā that can be nurtured and tended to over an extended period of time, with the learning from one project being transferred to the others. Perhaps a ālanguage nurseryā would have been a more fitting name.
Iāve also been particularly inspired by Mark Barboneās small, self-contained gists implementing small type systems and solvers, and Andras Kovacsā excellent elaboration-zoo (which was instrumental in helping me get my head around how to implement elaborators).
If you like this repository, you might find these interesting as well:
The predominant style in OCaml of leaving off type annotations makes understanding and porting code far more difficult. Instead I try to add type annotations to most top-level type signatures.
When open
is used I find it hard to figure out where identifiers are coming from without an editor.
Instead I prefer using an explicitly qualified path where possible.
In the past Iāve often found it hard to find related nodes in an AST when trying to understand other peopleās code. For example, the following variants might all refer to different parts of a dependent pair type:
type tm =
...
| Sig of string * tm * tm
| Pair of tm * tm
| Fst of tm
| Snd of tm
Instead I prefer to use the following constructors:
type tm =
...
| PairType of string * tm * tm
| PairLit of tm * tm
| PairFst of tm
| PairSnd of tm
OCamlās variant constructors arenāt namespaced under the type like in Rust or Lean, so reusing the same variant name will result in ambiguities if you are relying on global type inference. Generally OCaml programmers will either:
I find the former convention often results in duplicated datatype definitions (mutually dependent modules require explicit module signatures), and the latter is a little arbitrary and ugly.
Instead Iāve decided to just disambiguate variants using the type. I realise this might make the code a more difficult to understand and if I come up with a better compromise I might revisit this in the future.
Using Nix is not required, but can be useful for setting up a development shell with the packages and tools used in this project. With Nix flakes enabled:
nix run .#arith -- compile --target=anf <<< "1 + 2 * 27"
nix-direnv can be used to load development tools into your shell automatically. Once itās installed, run the following commands to enable it in the project directory:
echo "use flake" > .envrc
direnv allow
Youāll want to locally exclude the .envrc
, or add it to your global gitignore.
After that, dune can be used to build, test, and run the projects:
dune build
dune test
dune exec arith -- compile --target=anf <<< "1 + 2 * 27"
Alternatively, opam package definitions are provided in the ./opam
directory. They drive the Nix flake, so should be up to date. I donāt use opam
however, so Iām not sure what the workflow is.