1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
use lambda_calculus::term::*;
use lambda_calculus::church::booleans::{tru, fls};
use std::char;
pub fn decode(term: Term) -> String {
if term == fls() {
"".into()
} else if term.is_list() && term.head_ref().unwrap().is_list() {
let (head, tail) = term.uncons().unwrap();
let byte = decode_byte(head);
let chr = char::from(byte);
chr.to_string() + &decode(tail)
} else if term.head_ref() == Ok(&fls()) {
"1".to_string() + &decode(term.tail().unwrap())
} else if term.head_ref() == Ok(&tru()) {
"0".to_string() + &decode(term.tail().unwrap())
} else {
format!("({:?})", term)
}
}
fn decode_byte(encoded_byte: Term) -> u8 {
let bits = encoded_byte
.into_iter()
.map(|t| (t
.unabs()
.and_then(|t| t.unabs())
.and_then(|t| t.unvar())
.expect("not a lambda-encoded byte!") - 1) as u8
);
!bits.fold(0, |acc, b| acc * 2 + b)
}
fn encode_byte(byte: u8) -> Term {
let bitstr = format!("{:08b}", byte);
let bits = bitstr.as_bytes();
Term::from(bits.into_iter().map(|&bit| encode_bit(bit)).collect::<Vec<Term>>())
}
fn encode_bit(bit: u8) -> Term {
match bit {
b'0' => tru(),
b'1' => fls(),
_ => unreachable!()
}
}
pub fn encode(input: &[u8]) -> Term {
Term::from(input.into_iter().map(|&b| encode_byte(b)).collect::<Vec<Term>>())
}
#[cfg(test)]
mod test {
use super::*;
use binary_encoding::from_binary;
use std::str;
#[test]
fn encoding_lambda() {
assert_eq!(&*format!("{:?}", encode(b"0")),
"λ1(λ1(λλ2)(λ1(λλ2)(λ1(λλ1)(λ1(λλ1)(λ1(λλ2)(λ1(λλ2)(λ1(λλ2)(λ1(λλ2)(λλ1)))))))))(λλ1)");
assert_eq!(&*format!("{:?}", encode(b"1")),
"λ1(λ1(λλ2)(λ1(λλ2)(λ1(λλ1)(λ1(λλ1)(λ1(λλ2)(λ1(λλ2)(λ1(λλ2)(λ1(λλ1)(λλ1)))))))))(λλ1)");
assert_eq!(&*format!("{:?}", encode(b"a")),
"λ1(λ1(λλ2)(λ1(λλ1)(λ1(λλ1)(λ1(λλ2)(λ1(λλ2)(λ1(λλ2)(λ1(λλ2)(λ1(λλ1)(λλ1)))))))))(λλ1)");
}
#[test]
fn decoding_lambda() {
let k = from_binary(b"0000110").unwrap();
let s = from_binary(b"00000001011110100111010").unwrap();
let quine = from_binary(b"000101100100011010000000000001011\
011110010111100111111011111011010").unwrap();
assert_eq!(decode(k), "(λλ2)");
assert_eq!(decode(s), "(λλλ31(21))");
assert_eq!(decode(quine), "(λ1((λ11)(λλλλλ14(3(55)2)))1)");
}
#[test]
fn decode_encode_lambda() {
assert_eq!(decode(encode(b"herp derp")), "herp derp");
assert_eq!(decode(encode(b"0111010101011")), "0111010101011");
assert_eq!(decode(encode(b"01zeros110and1ones101")), "01zeros110and1ones101");
assert_eq!(decode(encode(b"\0(1)")), "\0(1)");
}
}