microFP

A Haskell implementation of parser combinators, an EDSL for a small functional language called microFP, and an interpreter for it. Built as part of a university compiler engineering course.

What's in here

The project has three modules:

PComb.hs contains a small parser combinator library built from scratch. It defines a Parser a type, along with Functor, Applicative, and Alternative instances. No external parser library (Parsec, Megaparsec, etc.) is used.

BasicParsers.hs builds token-level parsers on top of PComb: letters, digits, integers, identifiers, whitespace handling, and combinators like between, sep, sep1, option, parens, braces, and symbol. Higher-level parsers compose exclusively from these primitives without touching the input stream directly.

MicroFP.hs contains four things:

1. An abstract syntax tree for microFP programs (deep embedding), covering function definitions with pattern-matched parameters, arithmetic, comparisons, if-then-else, and function calls.
2. A pretty printer that generates source code from an AST.
3. An evaluator that walks the AST, using substitution-based binding of parameters and recursive reduction of expressions. Supports pattern matching on integer literal parameters, so multi-clause definitions work properly.
4. A parser for microFP source code, plus compile and runFile for turning textual programs into evaluatable ASTs.

The microFP language

microFP is a small pure functional language. Programs consist of one or more function definitions, each of the form:

name param1 param2 ... := expression;

Parameters can be variable names or integer literal patterns. The language supports arithmetic (+, -, *), comparisons (<, ==, >), if-then-else with braces, and function calls with parenthesized comma-separated arguments. Identifiers are lowercase letters followed by lowercase letters or digits.

Example: computing Fibonacci numbers two different ways.

fibonacci 0 := 0;
fibonacci 1 := 1;
fibonacci n := fibonacci(n-1) + fibonacci(n-2);

fib n := if (n < 3) then { 1 } else { fib(n-1) + fib(n-2) };

The first uses pattern matching on integer literals, the second uses if-then-else for the base case. Both are supported by the evaluator.

Running it

Load MicroFP.hs in GHCi:

ghci MicroFP.hs

Evaluate example programs directly:

ghci> eval fib "fib" [10]
55

ghci> eval functionFibonacci "fibonacci" [10]
55

Parse and evaluate a source file:

ghci> runFile "functions.txt" []
499

functions.txt contains sample microFP definitions; runFile reads it, parses it, and evaluates the last function (main := div(999, 2)).

Features implemented

From the assignment's feature list:

• Parser combinator foundations (Functor, Applicative, Alternative, char, failure)
• Basic parsers and combinators
• EDSL, example programs, pretty printer, evaluator
• microFP parser, compile, runFile
• Pattern matching for the evaluator using substitution

Partial application, higher-order functions, error handling, and QuickCheck property testing were not included due to tight time constraints.