Beatle - functional language interpreter

Beatle is a functional language with syntax and semantics inspired mostly by OCaml, but by Haskell as well. Its interpreter is written in Haskell.

Acknowledgements

The interpreter was written as a assignment on "Programming Languages and Paradigms" course on MIMUW (University of Warsaw - Faculty of Mathematics, Informatics and Mechanics).

Stephen Diehl blog was a tremendous help when working on this task. I also read first chapters of Simon Peyton Jones book called "The Implementation of Functional Programming Languages" to understand ideas standing behind implementations.

When working on type inference I used Martin Grabmüller paper on W algorithm implementation and So You Still Don't Understand Hindley-Milner blog series to understand HM type system.

Getting started

Usage

The project uses Stack build tool to compile and manage dependencies.

Running the interpreter:

stack build
stack run

If no command line arguments are provided, interpreter runs as REPL (using Haskeline). In this mode, you cannot write multi-line commands.

Command line arguments are considered as names of files to interpret -- for example, calling stack run file.bt loads content of file.bt, interprets it and write results to standard output.

Example code

λ 1 + 1;;
- : Int = 2
λ let x = 4 * 4;;
x : Int = 16
λ x + 4;;
- : Int = 20
20
λ letrec map f l = match l with { case h::t -> (f h) :: (map f t); case [] -> [] };;
map : ('m -> 'n) -> (['m] -> ['n]) = <fun>
λ let compose f g = \x -> f (g x);;
compose : ('e -> 'd) -> (('c -> 'e) -> ('c -> 'd)) = <fun>
λ let fs = [\x -> x + 1, \x -> x - 1];;
fs : [Int -> Int] = [<fun>, <fun>]
λ let nfs = map (compose (\x -> x == 0)) fs;;
nfs : [Int -> Bool] = [<fun>, <fun>]
λ map (\f -> f 1) nfs;;
- : [Bool] = [False, True]

More code examples can be found in good folder.

Project structure

Main.hs in app folder is an appropriate entrypoint of the interpreter program.

In the src folder you may find code of the interpreter, split into files:

• AbsBeatle.hs, ErrM.hs, LayoutBeatle.hs, LexBeatle.hs, ParBeatle.hs and PrintBeatle.hs have been automatically generated by BNFC. Grammar used by it is in Beatle.cf file,
• Expr.hs contains definitions of algebraic data types zawiera definicje typów algebraicznych denoting expressions Expr and types Type,
• Values.hs contains the definition of ADT Value, enclosing result of evaluation,
• Errors.hs contains definitions of various errors,
• TypeInference.hs contains code of type inference algorithm,
• Lambda.hs is responsible for evaluation of AST made from Expr,
• Interpreter.hs transforms AST processed by parser into smaller Expr tree, which is then used by both TypeInference.hs and Lambda.hs.

Type inference

Type inference is based on M. Grabmüller implementation of the famous W algorithm.

For now, inference of mutually recursive functions is possible only if those functions have the same types (so, for example, classic even and odd functions). Recursion inference uses the trick of typing the Y combinator (forall x. (x -> x) -> x) and then expand it to type "bigger" combinator (forall x. ([x] -> x) -> x).

Used monads

Interpreter uses State, Except, Input and IO monads, together creating stack of monad transformers -- ExceptT InterpreterError (StateT Env (InputT IO)). State and Except are responsible for keeping map of names and values connected with them (including closures) and error handling.

ExceptT is the most external transformer, because I wanted to keep continuity of the state of REPL in case of any evaluation or typing errors.

InputT is used by Haskeline.

Evaluator (Lambda.hs) uses Except enclosed by ReaderT -- ReaderT Env (Except InterpreterError) Value.

Type inference uses State and Except monads -- StateT TcState (Except InterpreterError). TcState is a container for current type variable.