17 releases (5 breaking)

Uses old Rust 2015

0.6.0 Jan 26, 2018
0.5.6 Jan 18, 2018
0.4.5 May 31, 2017
0.3.1 May 1, 2017
0.1.3 Apr 9, 2017

#1940 in Encoding

41 downloads per month

CC0 license

25KB
395 lines

blc

blc is an implementation of the binary lambda calculus.

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:

term lambda BLC
abstraction λM 00M
application MN 01MN
variable i 1i0

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:

bit lambda BLC
0 λλ2 (true) 0000110
1 λλ1 (false) 000010

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

encoding representation
decimal 96
binary 01100001
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

Documentation

Status

The library is already usable, but it is still a work in progress.

TODO

  • better documentation
  • more blc examples

Dependencies

~180KB