repos / machines.rs.git

commit

3ecde4e

parent

1ef4e59

author

Evgenii Akentev

date

2024-09-26 14:06:44 +0400 +04

Add CAM virtual machine

1@@ -1,6 +1,6 @@
2 #[derive(Clone, Debug, PartialEq)]
3 enum V {
4-    Free(String),
5+//    Free(String),
6     Bound(usize),
7 }
8 

1@@ -1 +1,2 @@
2 pub mod abstract_machines;
3+pub mod virtual_machines;

 1@@ -1,7 +1,9 @@
 2 use machines::abstract_machines::cek;
 3 use machines::abstract_machines::krivine;
 4+use machines::virtual_machines::cam;
 5 
 6 fn main() {
 7     cek::main();
 8     krivine::main();
 9+    cam::main();
10 }

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

1@@ -0,0 +1 @@
2+pub mod cam;