repos / machines.rs.git

cam.rs

  1#[derive(Clone, Debug)]
  2enum Term {
  3    Var(usize),
  4    Lam(Box<Term>),
  5    App(Box<(Term, Term)>),
  6    Nil,
  7    MkPair(Box<(Term, Term)>),
  8    Car(Box<Term>),
  9    Cdr(Box<Term>),
 10    Lit(usize),
 11}
 12
 13impl Term {
 14    fn eval(&self) -> Value {
 15        run(self.compile(), Value::Null, vec![])
 16    }
 17
 18    fn compile(&self) -> Vec<Instruction> {
 19        match self {
 20            Term::Var(0) => vec![Instruction::Snd],
 21            Term::Var(n) => {
 22                let mut res = vec![Instruction::Fst];
 23                res.append(&mut Term::Var(n - 1).compile());
 24                res
 25            },
 26            Term::Lam(t) => vec![Instruction::Cur(t.compile())],
 27            Term::App(tuple) => {
 28                let (t0, t1) = *tuple.clone();
 29                let mut result = vec![Instruction::Push];
 30
 31                result.append(&mut t0.compile());
 32                result.push(Instruction::Swap);
 33                result.append(&mut t1.compile());
 34                result.push(Instruction::Cons);
 35                result.push(Instruction::Call);
 36
 37                result
 38            },
 39            Term::Nil => vec![Instruction::Quote(Value::Null)],
 40            Term::MkPair(tuple) => {
 41                let (t0, t1) = *tuple.clone();
 42                let mut result = vec![Instruction::Push];
 43
 44                result.append(&mut t0.compile());
 45                result.push(Instruction::Swap);
 46                result.append(&mut t1.compile());
 47                result.push(Instruction::Cons);
 48
 49                result
 50            },
 51            Term::Car(t) => {
 52                let mut result = t.compile();
 53                result.push(Instruction::Fst);
 54                result
 55            },
 56            Term::Cdr(t) => {
 57                let mut result = t.compile();
 58                result.push(Instruction::Snd);
 59                result
 60            },
 61            Term::Lit(n) => vec![Instruction::Quote(Value::Num(*n))],
 62            _ => todo!(),
 63        }
 64    }
 65}
 66
 67#[derive(Clone, Debug)]
 68enum Instruction {
 69    Fst,
 70    Snd,
 71    Push,
 72    Swap,
 73    Cons,
 74    Call,
 75    Cur(Vec<Instruction>),
 76    Quote(Value),
 77}
 78
 79#[derive(Clone, Debug)]
 80enum Value {
 81    Null,
 82    Pair(Box<(Value, Value)>),
 83    Closure(Box<Value>, Vec<Instruction>),
 84    Num(usize),
 85}
 86
 87type Stack = Vec<Value>;
 88
 89fn run(instrs: Vec<Instruction>, v: Value, s: Stack) -> Value {
 90
 91    match (instrs.split_first(), v.clone(), s.split_first()) {
 92        (Some((Instruction::Fst, tail)), Value::Pair(tuple), _) => {
 93            let (v1, _) = *tuple.clone();
 94            run(tail.to_vec(), v1, s)
 95        },
 96        (Some((Instruction::Snd, tail)), Value::Pair(tuple), _) => {
 97            let (_, v2) = *tuple.clone();
 98            run(tail.to_vec(), v2, s)
 99        },
100        (Some((Instruction::Quote(val), tail)), _, _) => {
101            run(tail.to_vec(), val.clone(), s)
102        },
103        (Some((Instruction::Cur(steps), tail)), _, _) => {
104            run(tail.to_vec(), Value::Closure(Box::new(v), steps.to_vec()), s)
105        },
106        (Some((Instruction::Push, tail)), _, _) => {
107            let mut new_stack = vec![v.clone()];
108            new_stack.append(&mut s.clone());
109            run(tail.to_vec(), v, new_stack)
110        },
111        (Some((Instruction::Swap, tail)), _, Some((val, s_tail))) => {
112            let mut new_stack = vec![v.clone()];
113            new_stack.append(&mut s_tail.to_vec());
114            run(tail.to_vec(), val.clone(), new_stack)
115        },
116        (Some((Instruction::Cons, tail)), _, Some((val, s_tail))) => {
117            run(tail.to_vec(), Value::Pair(Box::new((val.clone(), v))), s_tail.to_vec())
118        },
119        (Some((Instruction::Call, tail)), Value::Pair(tuple), _) => {
120            let (Value::Closure(v0, steps), v1) = *tuple.clone() else { panic!("Impossible") };
121            let mut new_steps = steps.to_vec();
122            new_steps.append(&mut tail.to_vec());
123            run(new_steps.to_vec(), Value::Pair(Box::new((*v0, v1))), s)
124        },
125        (None, v, None) => v,
126        _ => panic!("Impossible"),
127    }
128}
129
130
131pub fn main() {
132    use Term::*;
133    println!("CAM:");
134
135    let t1 = Car(Box::new(MkPair(Box::new((Lit(1), Lit(2))))));
136    println!("t1: {:?}", t1.eval());
137
138    let t2 = App(Box::new((App(Box::new((Lam(Box::new(Var(0))), Lam(Box::new(Var(0)))))), Lam(Box::new(Var(0))))));
139    println!("t2: {:?}", t2.eval());
140}