blc/encoding/
binary.rs

1//! Binary encoding for lambda `Term`s
2
3use lambda_calculus::term::*;
4use self::Error::*;
5
6/// An error that can occur if the input stream of "bits" is not valid binary lambda calculus.
7#[derive(Debug, PartialEq)]
8pub enum Error {
9    /// not a valid term
10    NotATerm
11}
12
13/// Parse a blc-encoded lambda `Term`.
14///
15/// # Example
16/// ```
17/// use blc::encoding::binary::{from_bits, to_bits};
18///
19/// let k = from_bits(b"0000110");
20///
21/// assert!(k.is_ok());
22/// assert_eq!(to_bits(&k.unwrap()), Vec::from(&b"0000110"[..]));
23/// ```
24pub fn from_bits(input: &[u8]) -> Result<Term, Error> {
25    if let Some((result, _)) = _from_bits(input) {
26        Ok(result)
27    } else {
28        Err(NotATerm)
29    }
30}
31
32fn _from_bits(input: &[u8]) -> Option<(Term, &[u8])> {
33    if input.is_empty() { return None }
34
35    if [9, 10, 13, 32].contains(&input[0]) {
36        _from_bits(&input[1..]) // skip whitespaces
37    } else {
38        match &input[0..2] {
39            b"00" => {
40                if let Some((term, rest)) = _from_bits(&input[2..]) {
41                    Some((abs(term), rest))
42                } else {
43                    None
44                }
45            },
46            b"01" => {
47                if let Some((term1, rest1)) = _from_bits(&input[2..]) {
48                    if let Some((term2, rest2)) = _from_bits(rest1) {
49                        Some((app(term1, term2), rest2))
50                    } else {
51                        None
52                    }
53                } else {
54                    None
55                }
56            },
57            b"10" | b"11" => {
58                let i = input.iter().take_while(|&b| *b == b'1').count();
59                if input[2..].is_empty() {
60                    Some((Var(i), &*b""))
61                } else {
62                    Some((Var(i), &input[i+1..]))
63                }
64            },
65            _ => None
66        }
67    }
68}
69
70/// Represent a lambda `Term` in blc.
71///
72/// # Example
73/// ```
74/// use blc::encoding::binary::{from_bits, to_bits};
75///
76/// let k = from_bits(b"0000110");
77///
78/// assert!(k.is_ok());
79/// assert_eq!(to_bits(&k.unwrap()), Vec::from(&b"0000110"[..]));
80/// ```
81pub fn to_bits(term: &Term) -> Vec<u8> {
82    let mut output = Vec::new();
83    _to_bits(term, &mut output);
84
85    output
86}
87
88fn _to_bits(term: &Term, output: &mut Vec<u8>) {
89    match *term {
90        Var(i) => {
91            for _ in 0..i { output.push(b'1') }
92            output.push(b'0');
93        }
94        Abs(ref t) => {
95            output.extend_from_slice(b"00");
96            output.append(&mut to_bits(t));
97        }
98        App(ref t1, ref t2) => {
99            output.extend_from_slice(b"01");
100            output.append(&mut to_bits(t1));
101            output.append(&mut to_bits(t2));
102        }
103    }
104}
105
106/// Convert a stream of "bits" into bytes. It is not always reversible with `decompress`, because
107/// it produces full bytes, while the length of its input can be indivisible by 8.
108///
109/// # Example
110/// ```
111/// use blc::encoding::binary::{compress};
112///
113/// let succ_compressed = compress(&*b"000000011100101111011010");
114/// assert_eq!(succ_compressed, vec![0x1, 0xCB, 0xDA]);
115/// ```
116pub fn compress(bits: &[u8]) -> Vec<u8> {
117    let length = bits.len();
118    let mut output = Vec::with_capacity(length / 8 + 1);
119    let mut pos = 0;
120
121    while pos <= length - 8 {
122        output.push(bits_to_byte(&bits[pos..(pos + 8)]));
123        pos += 8;
124    }
125
126    if pos != length {
127        let mut last_byte = Vec::with_capacity(8);
128        last_byte.extend_from_slice(&bits[pos..]);
129        for _ in 0..(8 - (length - pos)) { last_byte.push(b'0') }
130        output.push(bits_to_byte(&last_byte));
131    }
132
133    output
134}
135
136fn bits_to_byte(bits: &[u8]) -> u8 {
137    bits.iter().fold(0, |acc, &b| acc * 2 + (b - 48))
138}
139
140/// Convert bytes into "bits" suitable for binary lambda calculus purposes.
141///
142/// # Example
143/// ```
144/// use blc::encoding::binary::decompress;
145///
146/// let succ_compressed = vec![0x1, 0xCB, 0xDA];
147///
148/// assert_eq!(decompress(&succ_compressed), b"000000011100101111011010");
149/// ```
150pub fn decompress(bytes: &[u8]) -> Vec<u8> {
151    let mut output = Vec::with_capacity(bytes.len() * 8);
152
153    for byte in bytes {
154        output.extend_from_slice(format!("{:08b}", byte).as_bytes());
155    }
156
157    output
158}
159
160#[cfg(test)]
161mod test {
162    use super::*;
163
164    const QUINE: &'static [u8; 66] =
165        b"000101100100011010000000000001011011110010111100111111011111011010";
166
167    const PRIMES: &'static [u8; 167] =
168        b"00010001100110010100011010000000010110000010010001010111110111101001000110100001\
169          11001101000000000010110111001110011111110111100000000111110011011100000010110000\
170          0110110";
171
172    const BLC: &'static [u8; 232] =
173        b"01010001101000000001010110000000000111100001011111100111100001011100111100000011\
174          11000010110110111001111100001111100001011110100111010010110011100001101100001011\
175          111000011111000011100110111101111100111101110110000110010001101000011010";
176
177    #[test]
178    fn variables() {
179        assert_eq!(from_bits(b"10"),   Ok(Var(1)));
180        assert_eq!(from_bits(b"110"),  Ok(Var(2)));
181        assert_eq!(from_bits(b"1110"), Ok(Var(3)));
182    }
183
184    #[test]
185    fn abstractions() {
186        assert_eq!(from_bits(b"0010"),     Ok(abs(Var(1))));
187        assert_eq!(from_bits(b"000010"),   Ok(abs!(2, Var(1))));
188        assert_eq!(from_bits(b"00000010"), Ok(abs!(3, Var(1))));
189    }
190
191    #[test]
192    fn applications() {
193        assert_eq!(from_bits(b"011010"),  Ok(app(Var(1), Var(1))));
194        assert_eq!(from_bits(b"0110110"), Ok(app(Var(1), Var(2))));
195        assert_eq!(from_bits(b"0111010"), Ok(app(Var(2), Var(1))));
196    }
197
198    #[test]
199    fn ignoring_whitespaces() {
200        assert_eq!(from_bits(b"00 00\t00\n10\r\n"), Ok(abs!(3, Var(1))));
201    }
202
203    #[test]
204    fn from_bits_and_back() {
205        let k =    b"0000110";
206        let v15 =  b"1111111111111110";
207        let s =    b"00000001011110100111010";
208        let succ = b"000000011100101111011010";
209
210        assert_eq!(to_bits(&from_bits(&*k).unwrap()),      k);
211        assert_eq!(to_bits(&from_bits(&*v15).unwrap()),    v15);
212        assert_eq!(to_bits(&from_bits(&*s).unwrap()),      s);
213        assert_eq!(to_bits(&from_bits(&*succ).unwrap()),   succ);
214        assert_eq!(to_bits(&from_bits(&*QUINE).unwrap()),  &QUINE[..]);
215        assert_eq!(to_bits(&from_bits(&*PRIMES).unwrap()), Vec::from(&PRIMES[..]));
216        assert_eq!(to_bits(&from_bits(&*BLC).unwrap()),    Vec::from(&BLC[..]));
217    }
218
219    #[test]
220    fn compression() {
221        let primes_c = compress(&PRIMES[..]);
222        assert_eq!(primes_c.first().unwrap(), &0x11);
223        assert_eq!(primes_c.last().unwrap(),  &0x6c);
224
225        let blc_c = compress(&BLC[..]);
226        assert_eq!(blc_c.first().unwrap(), &0x51);
227        assert_eq!(blc_c.last().unwrap(),  &0x1a);
228    }
229
230    #[test]
231    fn decompression() {
232        let s_c = vec![0x1, 0x7a, 0x74];
233        assert_eq!(compress(&decompress(&s_c)), s_c);
234    }
235
236    #[test]
237    fn compress_decompress() {
238        assert_eq!(decompress(&compress(&BLC[..])), Vec::from(&BLC[..]));
239    }
240}
blc/encoding/binary.rs

blc/encoding/
binary.rs
