miniml

miniml implementation in Rust.

cargo run to run the repl, cargo test to run the tests. You can install Rust and Cargo here

Some tests are here.

Architecture

Miniml is a small statically typed functional language. This implementation uses a virtual machine to execute miniml code. To get to the VM code, the following phases are executed.

Parsing/Lexing

There is no separate lexing phase.

There are two alternative parsers. One is a bottom up LR parser generated by LALRPOP. You can read the grammar. Another one is a hand written top down LL recursive descent/Pratt parser. It lives in syntax_ll crate. You can read about Pratt parsers here. I bet it is more interesting and useful than your usual formal grammars class :)

The AST lives in ast crate.

Type checking

Miniml has a very simple type system (int, bool and arrow types) and no polymorphism. All functions have annotated parameter and return types. There is nothing fancy in typechecking. It is executed on the AST level.

Deshugaring

Miniml VM has a native support for recursive functions. Local variable declarations (let) and mutual recursion (let rec) are lowered to simple recursive functions. This happens in the ir module. Alas, type information is lost on the way: the IR is untyped. Also, string identifiers are converted to numeric ones in the IR. Some new identifiers are synthesised while desugaring.

Compiling

IR is converted to VM instructions in the compile module. Compilation is pretty simple because most of the interesting work happens in the previous phase and also because the VM is pretty high level.

VM

The machine lives in the machine module. It is a stack based SECDish VM. It even has a garbage collector (the collect function)!