MicroCaml Interpreter

An interpreter and interactive REPL for MicroCaml, a small functional programming language based on a subset of OCaml.

This project implements the core components of a small functional language interpreter:

• Lexical analysis (tokenizing source code)
• Parsing into an Abstract Syntax Tree (AST)
• Environment-based evaluation with closures
• Interpreter integrated with an interactive REPL (Mutop)

The interpreter was developed as part of CMSC330: Organization of Programming Languages at the University of Maryland.

Assignment Specification

The project was implemented according to the CMSC330 Project 4 specification:

• Project 4A – Lexer and Parser
• Project 4B – Interpreter and Mutop REPL

Demo

Example interaction with the MicroCaml Mutop REPL demonstrating variable definitions and expression evaluation.

Interpreter Architecture

The project includes an interactive REPL (Mutop) built on top of the MicroCaml interpreter.

The execution flow is:

User Input
   ↓
bin/mutop.ml        (interactive REPL / CLI loop)
   ↓
src/lexer.ml        (tokenization)
   ↓
src/parser.ml       (parsing)
   ↓
src/eval.ml         (evaluation with environment)
   ↓
Result

Core components:

File	Purpose
src/lexer.ml	Converts source text into tokens
src/parser.ml	Parses MicroCaml expressions and Mutop commands
src/eval.ml	Evaluates expressions and Mutop statements
src/microCamlTypes.ml	Defines AST and runtime types
bin/mutop.ml	Provided REPL that interfaces with the interpreter

mutop.ml reads user input until ;;, invokes the lexer/parser/evaluator pipeline, prints results, and preserves the environment across commands such as def x = 5;;.

The evaluator implements environment-based evaluation with closures, supporting higher-order functions and recursion.

The formal operational semantics used to guide the evaluator implementation are included in:

docs/microcaml-opsem.pdf

Mutop REPL

The project includes Mutop, a provided interactive REPL used to execute MicroCaml programs.

Mutop supports two kinds of inputs.

Evaluate an expression

mutop # 3 + 4;;
- : val: Int 7

Define a variable

The def command stores variables in the REPL environment.

mutop # def x = 5;;
val x = Int 5

The variable can then be used in future expressions:

mutop # x + 2;;
- : val: Int 7

Language Features

MicroCaml supports a subset of OCaml-style functional programming.

Primitive values

int
bool

Arithmetic operators

+  -  *  /

Example:

mutop # 1 + 2;;
- : val: Int 3

Boolean operators

&&  ||  not

Comparisons

=  <>  <  <=  >  >=

Conditionals

if <expr> then <expr> else <expr>

Example:

mutop # if true then 1 else 2;;
- : val: Int 1

Let bindings

let x = 6 in x + 4;;

Functions

Anonymous functions:

fun x -> x + 1

Function application:

mutop # (fun x -> x + 1) 5;;
- : val: Int 6

Closures

Functions capture their surrounding environment.

mutop # let x = 5 in
    let f = fun y -> x + y in
    f 3;;
- : val: Int 8

Recursive functions

Recursive functions are supported using let rec.

mutop # let rec fact = fun n ->
    if n = 0 then 1
    else n * fact (n - 1)
  in fact 5;;
- : val: Int 120

Project Structure

MicroCaml
│
├── src/        interpreter implementation
├── bin/        REPL entry point (mutop)
├── test/       unit and property tests
├── docs/       language semantics documentation
│
├── dune-project
├── dune-workspace
├── mutop.sh
└── README.md

Requirements

The project uses the OCaml ecosystem with opam and the Dune build system.

Install dependencies:

opam install dune utop ounit ounit2 qcheck

Build

From the repository root:

dune build

You may see deprecation warnings from the testing libraries (for example QCheck.small_int).
These originate from the provided test suite and do not affect interpreter functionality.

Running the Interpreter

Start the interactive REPL:

dune exec bin/mutop.bc

Alternatively, run the helper script:

./mutop.sh

Running Tests

Run the test suite with:

dune runtest

The tests include both unit tests and property-based tests.

Notes

This project builds on starter infrastructure provided in CMSC330, while the interpreter logic (lexing, parsing, and evaluation) was implemented as part of the assignment.