Goal

The goal of this project is to prototype extensible languages in OCaml to find a good way to represent extensible ASTs which can form the base of a type safe and convenient macro system.

Step one is to experiment with OCamls variant and GADT types and module system to find the things which do not work well. Step two will be to design a language for extensible ASTs.

Languages

The following small languages will be implemented and combined:

calc-int

Arithmetic expressions with integers

calc-float

Arithmetic expressions with floats

calc

calc-int + calc-float and conversions

algo-int

Extending calc-int with conditional evaluation

algo

Extending calc with conditional evaluation, loops, and booleans

algo-generic

Extending a given language with conditional evaluation and loops

General language combination

A system to combine fragments of languages to form new ones

binding

Define values and use them, for dynamic variables and compiled w/o runtime

More complex compiler analysis

Constant folding, transformations

Parser

Parsers which can be combined easily

Source Location handling

Track source locations and use them for error reporting

Optimization framework

Should be able to combine contexts of Eval_compiled and Parser, combine several bottom/up or top/down passes into a single one

Approaches

There are two different approaches so far:

1. Extensible ASTs using extensible tagged unions in source/ast

   This works well to make languages which can be extended. But it does not scale well to multiple levels of language layers, compare Algo with the implementation for tagless unions

2. Functors and tagless staged interpreters in source/tagless

   This works well for multiple layers of languages which can extend each other multiple times. Also reusable language layers are very simple to do.

Building

Initial one time setup

opam switch create . ocaml-base-compiler.4.10.0 --deps-only

Build the project

dune build

Running demo app

dune exec calc-demo
dune exec algo-demo
dune exec tagless-demo

Build in Emacs

• Open any .ml file
• Call ‘(tuareg-opam-update-env)’
• Run above build commands

Using Nix

This will install all dependencies into the Nix store and compile the project

nix-build

Run it by calling ./result/bin/tagless-demo