Haskell Lambda & Arithmetic REPL

A lightweight interpreter for Lambda Calculus extended with basic arithmetic, built from scratch in Haskell.

This project implements a monadic parser combinator library (without using external tools like Parsec) and a small-step operational semantics evaluator with capture-avoiding substitution.

Features

• Custom Parser Combinators: Full implementation of Functor, Applicative, Monad, and Alternative for parsing.
• Lambda Calculus: Supports abstraction (\x. body), application, and variable binding.
• Arithmetic: Standard order of operations for +, -, *, /.
• REPL: Interactive Read-Eval-Print Loop for testing expressions.
• Evaluation: Call-by-Name reduction strategy.

Getting Started

Prerequisites

You need GHC and Cabal installed.

Running the REPL

This project is configured as a Cabal executable. You can run it easily with:

cabal run

Alternatively, to build the executable specifically:

cabal build

Usage Examples

Once inside the REPL (λ>), you can try the following:

Arithmetic:

λ> 10 + 5 * 2
Result: 20

Identity Function:

λ> (\x. x) 100
Result: 100

Function Application:

λ> (\x. x + 1) 5
Result: 6

Higher Order Functions:

λ> (\f. \x. f (f x)) (\y. y * 2) 3
Result: 12

Implementation Details

• Parser: Recursive descent parser handling left-associativity and precedence levels.
• Reduction: Small-step semantics that reduces the leftmost outermost redex first (Call-by-Name), but evaluates arithmetic operators strictly.
• Substitution: Handles variable capture by renaming bound variables when necessary.