### 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 |

#**978** in Encoding

**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 | 1^{i}0 |

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