Minimal toolkit that parses untyped Lambda Calculus expressions and compiles them into executable Python code.
Project description
Miterand
Authors:
- Haydon Behl
- Neal Chandra
Overview
Miterand is a minimal toolkit that parses untyped Lambda Calculus expressions and compiles them into executable Python code. It serves both as an educational demonstration of functional programming concepts (α, β, η conversions, currying) and as a lightweight interpreter that can be embedded in Python projects.
Features & Results
- Lambda Calculus Support: Definitions of anonymous functions (
Lx.x) and multi-argument currying (Lx.Ly.(x+y)). - Boolean Logic: Encodes
TRUE,FALSE, and anIFcombinator purely with functions. - Arithmetic Operations: Supports numeric expressions and nested function calls, e.g.,
add(1)(add(2)(3))evaluates to6. - Correctness: Verified through a suite of basic tests (see
basic_tests.ipynb) showing:- Increment and compose:
f := Lx.(x+1),g := Lx.(x+2),g(f(1)) → 4 - Arithmetic currying:
add := Lx.Ly.(x+y),add(1)(add(2)(3)) → 6 - Boolean logic:
IF TRUE 1 2 → 1,IF FALSE 1 2 → 2.
- Increment and compose:
Creation Process
-
Tokenizer (
tokenizer.py)- Transforms source code into a token sequence: numbers, identifiers, lambda markers (
L), operators, parentheses.
- Transforms source code into a token sequence: numbers, identifiers, lambda markers (
-
Parser (
parser.py)- Implements a recursive-descent parser that builds an AST with nodes:
Assignment,Lambda,BinaryOp,Variable,Number,Call.
- Supports chained lambdas and left-associative application.
- Implements a recursive-descent parser that builds an AST with nodes:
-
Generator (
generator.py)- Converts AST nodes into valid Python expressions:
Lambda(param, body) → lambda param: <body>Call(func, arg) → <func>(<arg>)- Arithmetic and variable references maintain Python syntax.
- Converts AST nodes into valid Python expressions:
-
Interpreter (
interpreter.py)- Splits source into assignments and expressions.
- Uses
Tokenize+Parser+Generateto get Python code. - Executes code in a persistent Python REPL subprocess (
python_repl.py), capturing output after each prompt.
Quickstart
- Install requirements (none beyond standard library).
- Run basic tests:
pip install -r requirements.txt # if any jupyter notebook basic_tests.ipynb
- Use
interpretin your code:from interpreter import interpret code = ''' add := Lx.Ly.(x + y) result := add(2)(3) result ''' print(interpret(code)) # >>> 5
Application & Extensions
- Educational Tool: Visualize the correspondence between Lambda Calculus and Python lambdas.
- Prototype Compiler: Foundation for more advanced functional-to-imperative language compilers.
- Extensible: Easily add features—such as multi-argument built-ins, let-bindings, or type-checking—by extending the parser and generator.
Future Work
- η‑conversion simplification: Automatically remove redundant λ-abstractions.
- Support for recursion: Add fixed-point combinators (e.g.,
Ycombinator). - Error Handling: Better syntax error messages with line/column annotations.
- Optimizations: Inline small lambdas and apply α-renaming to avoid variable capture.
Miterand bridges the gap between theoretical functional programming and practical Python execution.
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Filter files by name, interpreter, ABI, and platform.
If you're not sure about the file name format, learn more about wheel file names.
Copy a direct link to the current filters
File details
Details for the file miterand-0.1.0.tar.gz.
File metadata
- Download URL: miterand-0.1.0.tar.gz
- Upload date:
- Size: 6.7 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/6.1.0 CPython/3.13.2
File hashes
| Algorithm | Hash digest | |
|---|---|---|
| SHA256 |
d9e76714624e3d1d97fc9539d0fe2df7649aceea75b6c0c54cf4a3aa8f35ee3c
|
|
| MD5 |
73749c08dc78b05717c3b975900f2781
|
|
| BLAKE2b-256 |
82b5a949cc213d7b56c8c110b4b04ff0fbf6d6f2918c23a8309bd6dc86b4db71
|
File details
Details for the file miterand-0.1.0-py3-none-any.whl.
File metadata
- Download URL: miterand-0.1.0-py3-none-any.whl
- Upload date:
- Size: 6.3 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/6.1.0 CPython/3.13.2
File hashes
| Algorithm | Hash digest | |
|---|---|---|
| SHA256 |
e57c934aaa21b8670ff5cee9e1f7451f12cc12bd7b99470f29574952d6f5c84b
|
|
| MD5 |
e7f7e2887e09b270c30f5a244a24fe5c
|
|
| BLAKE2b-256 |
d7f5ead08b320dc13088cb58c851d6389329894735d32dd97a4cea979977eaeb
|
