Crate blc

Source
Expand description

blc is an implementation of the binary lambda calculus in Rust.

§Binary lambda calculus basics

Binary lambda calculus (BLC) is a minimal, purely functional programming language based on a binary encoding of the untyped lambda calculus with De Bruijn indices.

Lambda terms have the following representation in BLC:

termlambdaBLC
abstractionλM00M
applicationMN01MN
variablei1i0

Since BLC programs are basically lambda calculus terms, they can be applied to other terms. In order to be applicable to binary (but not BLC-encoded) input, it has to be lambda-encoded first. Bytestrings are lambda-encoded as Church lists of bytes and bytes are lambda-encoded as Church lists of lambda-encoded bits.

Bits 0 and 1 are lambda-encoded as Church booleans:

bitlambdaBLC
0λλ2 (true)0000110
1λλ1 (false)000010

Example: BLC-encoding steps for a byte representing the ASCII/UTF-8 encoded letter ‘a’:

encodingrepresentation
decimal96
binary01100001
lambdaλ1(λλ2)(λ1(λλ1)(λ1(λλ1)(λ1(λλ2)(λ1(λλ2)(λ1(λλ2)(λ1(λλ2)(λ1(λλ1)(λλ1))))))))
BLC (hex)16 16 c 2c 10 b0 42 c1 85 83 b 6 16 c 2c 10 41 0

Re-exports§

pub use self::execution::run;
pub use self::encoding::binary::to_bits;
pub use self::encoding::binary::from_bits;

Modules§

encoding
BLC-relevant encodings
execution
Binary lambda calculus execution