Lambda Calculus Development Toolkit

This repo is a collection of tools for writing programs in lambda calculus and SKI combinator calculus, written by various authors.

This repo is designed and intended to be used as a dependency manager for projects related to lambda calculus programming.

This repo includes tools and interpreters for the following lambda-calculus-based languages:

• Binary Lambda Calculus
• Universal Lambda
• Lazy K

Dependency Graph

Supported Interpreters and Tools

Interpreters

• Blc: Written by Justine Tunney. SectorLambda, a 521-byte lambda calculus interpreter
• tromp: Written by John Tromp. The IOCCC 2012 "Most functional" interpreter (its source is in the shape of a λ)
• uni: Written by John Tromp. An unobfuscated version of tromp
• uni++: Written by Melvin Zhang. A fast binary lambda calculus interpreter written in C++, featuring many speed and memory optimizations.
  • A rewrite of uni. Originally named uni. Named uni++ in this repo to distinguish from uni
• UniObf: Written by John Tromp. A bitwise BLC interpreter written in obfuscated-style Haskell
• lazyk: Written by Kunihiko Sakamoto. A fast Lazy K interpreter
• clamb: Written by Kunihiko Sakamoto. A fast Universal Lambda interpreter

Tools

• asc2bin: Written by Hikaru Ikuta. Packs 0/1 ASCII bit streams to byte streams. Used for BLC interpreters
• lam2bin: Written by Justine Tunney. Parses plaintext lambda terms such as \x.x to BLC notation
• blc-ait: Written by John Tromp. A multi-functional tool for binary lambda calculus, binary combinator calculus, etc. Includes a head normal form optimizer for lambda terms and many more features.
  • Originally named blc. Named blc-ait in this repo to distinguish between Blc

Other Tools

Not included in this repo, but related to lambda calculus programming:

• LambdaCraft: Written by Written by Hikaru Ikuta. A Common Lisp DSL for building untyped lambda calculus terms. Compilable with BLC notation and SKI combinator calculus notation, for programming in BLC, UL, and Lazy K.

Lambda Calculus Interpreter Details

Below is a summary of the supported lambda calculus interpreters. Each interpreter uses a slightly different I/O encoding, classified below as languages.

Language	Extension	Engine	Program Format
Binary Lambda Calculus	*.blc	Untyped Lambda Calculus	Binary (asc2bin can be used)
Bitwise Binary Lambda Calculus	*.blc, *.bitblc	Untyped Lambda Calculus	ASCII
Universal Lambda	*.ulamb	Untyped Lambda Calculus	Binary (asc2bin can be used)
Lazy K	*.lazy	SKI Combinator Calculus	ASCII

Interpreter	Language	Platforms	Build Command	Author	Notes
Blc	Binary Lambda Calculus	x86-64-Linux	make blc	@jart	521-byte interpreter
tromp	Binary Lambda Calculus	Any	make tromp	@tromp	IOCCC 2012 "Most functional" - the source is in the shape of a λ
uni	Binary Lambda Calculus	Any	make uni	@tromp	Unobfuscated version of tromp
uni++	Binary Lambda Calculus	Any	make uni++	@melvinzhang	Fast binary lambda calculus interpreter written in C++, featuring many speed and memory optimizations. A rewrite of uni. Originally named uni
UniObf	Bitwise Binary Lambda Calculus	Any	make UniObf	@tromp	Features optimizations included in uni++. Written in obfuscated-style Haskell
clamb	Universal Lambda	Any	make clamb	@irori	Fast UL interpreter
lazyk	Lazy K	Any	make lazyk	@irori	Fast Lazy K interpreter

Building the Interpreters and Tools

To build all interpreters:

make blc tromp uni uni++ UniObf clamb lazyk

Several notes about the interpreters:

• The BLC intepreter Blc runs only on x86-64-Linux systems.
• The BLC interpreter tromp may not compile on a Mac with the defualt gcc (which is actually an alias of clang). Details are provided below.

To build all tools:

make asc2bin lam2bin blc-ait

Building tromp on a Mac

Mac has gcc installed by default or via Xcode Command Line Tools. However, gcc is actually installed as an alias to clang, which is a different compiler that doesn't compile tromp. This is confirmable by running gcc --version. On my Mac, running it shows:

$ gcc --version
Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/Library/Developer/CommandLineTools/SDKs/MacOSX10.15.sdk/usr/include/c++/4.2.1
Apple clang version 12.0.0 (clang-1200.0.32.29)
Target: x86_64-apple-darwin19.6.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin

A workaround for this is to use uni instead, which is an unobfuscated version of tromp compilable with clang. To build tromp, first install gcc via Homebrew:

brew install gcc

Currently, this should install the command gcc-11. After installing gcc, check the command it has installed.

Then, edit the Makefile's CC configuration:

- CC=cc
+ CC=gcc-11

Then, running

make tromp

will compile tromp.

Usage

Please see the "Running LambdaLisp" section in my other project LambdaLisp for details.