项目作者: ljedrz

项目描述 :
Binary lambda calculus
高级语言: Rust
项目地址: git://github.com/ljedrz/blc.git
创建时间: 2017-04-07T11:48:33Z
项目社区:https://github.com/ljedrz/blc

开源协议:Creative Commons Zero v1.0 Universal

下载


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 for them to be applicable to binary (but not BLC-encoded) input, it has to be lambda-encoded
first. Bytestrings are lambda-encoded as
single-pair lists of bytes
and bytes are lambda-encoded as single-pair 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 0c 2c 10 b0 42 c1 85 83 0b 06 16 0c 2c 10 41 00

Documentation

Example BLC program

  1. extern crate blc;
  2. extern crate lambda_calculus;
  3. use blc::*;
  4. use blc::encoding::binary::to_bits;
  5. use blc::execution::Input;
  6. use lambda_calculus::{parse, DeBruijn};
  7. fn repeat(input: &[u8]) -> String {
  8. let code_lambda = "λ1((λ11)(λλλλλ14(3(55)2)))1"; // the program (a lambda expression)
  9. let code_term = parse(code_lambda, DeBruijn).unwrap();
  10. let code_blc = to_bits(&code_term); // the program in binary lambda calculus
  11. run(&*code_blc, Input::Bytes(input)).unwrap()
  12. }
  13. fn main() {
  14. assert_eq!(
  15. repeat(&*b"hurr"),
  16. "hurrhurr"
  17. );
  18. }