Awesome

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.

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.