This repository is a small experimental project written while learning lambda calculus.

The idea is simple: first build a tiny lambda interpreter, then use plain lambda terms to construct richer behavior step by step, including arithmetic, booleans, data structures, and recursion. The point of the project is the experiment itself, not production-readiness.

• a lexer built with leex
• a parser built with yecc
• an escript evaluator for beta reduction
• a sample program in foobar.lambda

The sample program starts from raw lambda calculus and builds:

• Church numerals
• arithmetic operators such as succ, plus, mult, pow, pred, and sub
• booleans and branching
• pair/list-like structures
• recursion with the Y combinator

The syntax is intentionally minimal.

Variables:

x
foo
bar_1

Abstractions:

\x.x
\x.\y.x

Applications are left-associative:

f x y

which means:

((f x) y)

Parentheses can be used to control grouping:

(\x.x) y

Top-level definitions use = and end with ;:

id = \x.x;
const = \x.\y.x;
id const

Single-line comments start with //.

Requirements:

• Erlang/OTP

Installation guide: Erlang Installation Guide

Build the generated scanner and parser modules:

git clone https://github.com/rbee3u/lambda-erlang.git
cd lambda-erlang
chmod a+x bootstrap lambda
./bootstrap

Run a lambda source file:

./lambda foobar.lambda

Command line:

usage: lambda [--help] [--full] [--step] <file>

Options:

• --help shows usage
• --full prints the fully parenthesized result
• --step prints each reduction step

foobar.lambda is the main example. It defines arithmetic, booleans, list-like structures, and recursion from pure lambda terms, then evaluates the length of a small encoded list.

A tiny example:

id = \x.x;
id y

This project is mainly useful if you want to experiment with how much can be built from a very small lambda calculus core.