1#![no_std]
2extern crate alloc;
3use alloc::{boxed::Box, vec::Vec};
4use lambda_calculus::Term;
5pub fn le(a: usize) -> Box<dyn Iterator<Item = bool>> {
6 if a == 0 {
7 return Box::new([true, false].into_iter());
8 }
9 let len = usize::BITS - a.leading_zeros();
10 let x = if len == 1 {
11 Vec::default()
12 } else {
13 (0..len - 2)
14 .rev()
15 .map(|a| 1 << a)
16 .map(|v| a & v != 0)
17 .collect()
18 };
19 return Box::new(
20 [true]
21 .into_iter()
22 .chain(le((len - 1) as usize))
23 .chain(x.into_iter()),
24 );
25}
26pub fn encode(t: &Term) -> Box<dyn Iterator<Item = bool> + '_> {
27 match t {
28 Term::Var(v) => le(*v),
29 Term::Abs(term) => Box::new([false, false].into_iter().chain(encode(&*term))),
30 Term::App(t) => {
31 let (a, b) = t.as_ref();
32 Box::new([false, true].into_iter().chain(encode(a)).chain(encode(b)))
33 }
34 }
35}
36pub fn ld(a: &mut (dyn Iterator<Item = bool> + '_)) -> Option<usize> {
37 if !a.next()? {
38 return Some(0);
39 }
40 let mut x = 1;
41 let l = ld(a)?;
42 for _ in (0..l).rev() {
43 x = 2 * x + (if a.next()? { 1 } else { 0 })
44 }
45 return Some(x);
46}
47pub fn decode(a: &mut (dyn Iterator<Item = bool> + '_)) -> Option<Term> {
48 match a.next()? {
49 true => Some(Term::Var(ld(a)?)),
50 false => match a.next()? {
51 false => Some(Term::Abs(Box::new(decode(a)?))),
52 true => Some(Term::App(Box::new((decode(a)?, decode(a)?)))),
53 },
54 }
55}