Lambda Calculus Interpreter

This is a Haskell implementation of a Lambda Calculus interpreter, developed as part of the "Paradigms of Programming" course (Tema 3). It supports evaluation strategies, macro definitions, and includes a standard library of Church encodings.

Project Structure

• Lambda.hs: Core logic for the lambda calculus, including:
  • Lambda data type definition.
  • Functions for handling variables (vars, freeVars, newVar).
  • Substitution and Beta-reduction logic (reduce).
  • Evaluation strategies: Normal (normalStep) and Applicative (applicativeStep) order.
• Parser.hs: A monadic parser for parsing lambda expressions and line definitions from strings.
• Binding.hs: Manages the evaluation context and macro expansion (expandMacros, simplifyCtx).
• Default.hs: Contains a "standard library" of pre-defined macros (Church booleans, numerals, and pairs) and the default context.
• main.hs: The main entry point, implementing a Read-Eval-Print Loop (REPL) for interactive use.
• test.hs: A comprehensive test suite to verify the correctness of the implementation.

Features

• Evaluation Strategies: Supports both Normal and Applicative order reduction to normal form.
• Parsing: Parses standard lambda calculus syntax (e.g., \x.x, \x y.x, lambda x.x).
• Macros & Context: Allows defining and using macros (e.g., TRUE, ADD).
• Standard Library: Includes Church encodings for:
  • Booleans: TRUE, FALSE, AND, OR, NOT, XOR.
  • Pairs: PAIR, FST, SND.
  • Numerals: N0, N1... N2, SUCC, PRED, ADD, SUB, MULT.
• Interactive REPL: rigorous testing environment.

Usage

Running the REPL

To start the interactive interpreter, run:

runhaskell main.hs

REPL Commands

• <expression>: Evaluates a lambda expression.
• <NAME> = <expression>: Defines a new macro in the current context.
• :ctx: Displays the current context (defined macros).
• :r: Resets the context to the default state (reloads Default.hs).
• :q: Quits the REPL.

Example Session

λ> \x.x
λx.x

λ> (\x.x) y
y

λ> ADD N1 N1
λf.λx.f (f x)

λ> MYID = \x.x
λx.x

λ> MYID a
a

Testing

To run the full test suite:

runhaskell test.hs

To run tests for specific components:

runhaskell test.hs lambda    # Test evaluation logic
runhaskell test.hs parser    # Test parser
runhaskell test.hs binding   # Test context/macros
runhaskell test.hs default   # Test standard library