From 3ecde4e791d3bd6812d4421326d6d1cc4a03d106 Mon Sep 17 00:00:00 2001
From: Evgenii Akentev <hi@ak3n.com>
Date: Thu, 26 Sep 2024 14:06:44 +0400
Subject: [PATCH] Add CAM virtual machine

---
 src/abstract_machines/krivine.rs |   2 +-
 src/lib.rs                       |   1 +
 src/main.rs                      |   2 +
 src/virtual_machines/cam.rs      | 140 +++++++++++++++++++++++++++++++
 src/virtual_machines/mod.rs      |   1 +
 5 files changed, 145 insertions(+), 1 deletion(-)
 create mode 100644 src/virtual_machines/cam.rs
 create mode 100644 src/virtual_machines/mod.rs

diff --git a/src/abstract_machines/krivine.rs b/src/abstract_machines/krivine.rs
index db99686..9561023 100644
--- a/src/abstract_machines/krivine.rs
+++ b/src/abstract_machines/krivine.rs
@@ -1,6 +1,6 @@
 #[derive(Clone, Debug, PartialEq)]
 enum V {
-    Free(String),
+//    Free(String),
     Bound(usize),
 }
 
diff --git a/src/lib.rs b/src/lib.rs
index 0af09f2..baad779 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1 +1,2 @@
 pub mod abstract_machines;
+pub mod virtual_machines;
diff --git a/src/main.rs b/src/main.rs
index d6fa209..f95addf 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,7 +1,9 @@
 use machines::abstract_machines::cek;
 use machines::abstract_machines::krivine;
+use machines::virtual_machines::cam;
 
 fn main() {
     cek::main();
     krivine::main();
+    cam::main();
 }
diff --git a/src/virtual_machines/cam.rs b/src/virtual_machines/cam.rs
new file mode 100644
index 0000000..042562a
--- /dev/null
+++ b/src/virtual_machines/cam.rs
@@ -0,0 +1,140 @@
+#[derive(Clone, Debug)]
+enum Term {
+    Var(usize),
+    Lam(Box<Term>),
+    App(Box<(Term, Term)>),
+    Nil,
+    MkPair(Box<(Term, Term)>),
+    Car(Box<Term>),
+    Cdr(Box<Term>),
+    Lit(usize),
+}
+
+impl Term {
+    fn eval(&self) -> Value {
+        run(self.compile(), Value::Null, vec![])
+    }
+
+    fn compile(&self) -> Vec<Instruction> {
+        match self {
+            Term::Var(0) => vec![Instruction::Snd],
+            Term::Var(n) => {
+                let mut res = vec![Instruction::Fst];
+                res.append(&mut Term::Var(n - 1).compile());
+                res
+            },
+            Term::Lam(t) => vec![Instruction::Cur(t.compile())],
+            Term::App(tuple) => {
+                let (t0, t1) = *tuple.clone();
+                let mut result = vec![Instruction::Push];
+
+                result.append(&mut t0.compile());
+                result.push(Instruction::Swap);
+                result.append(&mut t1.compile());
+                result.push(Instruction::Cons);
+                result.push(Instruction::Call);
+
+                result
+            },
+            Term::Nil => vec![Instruction::Quote(Value::Null)],
+            Term::MkPair(tuple) => {
+                let (t0, t1) = *tuple.clone();
+                let mut result = vec![Instruction::Push];
+
+                result.append(&mut t0.compile());
+                result.push(Instruction::Swap);
+                result.append(&mut t1.compile());
+                result.push(Instruction::Cons);
+
+                result
+            },
+            Term::Car(t) => {
+                let mut result = t.compile();
+                result.push(Instruction::Fst);
+                result
+            },
+            Term::Cdr(t) => {
+                let mut result = t.compile();
+                result.push(Instruction::Snd);
+                result
+            },
+            Term::Lit(n) => vec![Instruction::Quote(Value::Num(*n))],
+            _ => todo!(),
+        }
+    }
+}
+
+#[derive(Clone, Debug)]
+enum Instruction {
+    Fst,
+    Snd,
+    Push,
+    Swap,
+    Cons,
+    Call,
+    Cur(Vec<Instruction>),
+    Quote(Value),
+}
+
+#[derive(Clone, Debug)]
+enum Value {
+    Null,
+    Pair(Box<(Value, Value)>),
+    Closure(Box<Value>, Vec<Instruction>),
+    Num(usize),
+}
+
+type Stack = Vec<Value>;
+
+fn run(instrs: Vec<Instruction>, v: Value, s: Stack) -> Value {
+
+    match (instrs.split_first(), v.clone(), s.split_first()) {
+        (Some((Instruction::Fst, tail)), Value::Pair(tuple), _) => {
+            let (v1, _) = *tuple.clone();
+            run(tail.to_vec(), v1, s)
+        },
+        (Some((Instruction::Snd, tail)), Value::Pair(tuple), _) => {
+            let (_, v2) = *tuple.clone();
+            run(tail.to_vec(), v2, s)
+        },
+        (Some((Instruction::Quote(val), tail)), _, _) => {
+            run(tail.to_vec(), val.clone(), s)
+        },
+        (Some((Instruction::Cur(steps), tail)), _, _) => {
+            run(tail.to_vec(), Value::Closure(Box::new(v), steps.to_vec()), s)
+        },
+        (Some((Instruction::Push, tail)), _, _) => {
+            let mut new_stack = vec![v.clone()];
+            new_stack.append(&mut s.clone());
+            run(tail.to_vec(), v, new_stack)
+        },
+        (Some((Instruction::Swap, tail)), _, Some((val, s_tail))) => {
+            let mut new_stack = vec![v.clone()];
+            new_stack.append(&mut s_tail.to_vec());
+            run(tail.to_vec(), val.clone(), new_stack)
+        },
+        (Some((Instruction::Cons, tail)), _, Some((val, s_tail))) => {
+            run(tail.to_vec(), Value::Pair(Box::new((val.clone(), v))), s_tail.to_vec())
+        },
+        (Some((Instruction::Call, tail)), Value::Pair(tuple), _) => {
+            let (Value::Closure(v0, steps), v1) = *tuple.clone() else { panic!("Impossible") };
+            let mut new_steps = steps.to_vec();
+            new_steps.append(&mut tail.to_vec());
+            run(new_steps.to_vec(), Value::Pair(Box::new((*v0, v1))), s)
+        },
+        (None, v, None) => v,
+        _ => panic!("Impossible"),
+    }
+}
+
+
+pub fn main() {
+    use Term::*;
+    println!("CAM:");
+
+    let t1 = Car(Box::new(MkPair(Box::new((Lit(1), Lit(2))))));
+    println!("t1: {:?}", t1.eval());
+
+    let t2 = App(Box::new((App(Box::new((Lam(Box::new(Var(0))), Lam(Box::new(Var(0)))))), Lam(Box::new(Var(0))))));
+    println!("t2: {:?}", t2.eval());
+}
diff --git a/src/virtual_machines/mod.rs b/src/virtual_machines/mod.rs
new file mode 100644
index 0000000..cd0883a
--- /dev/null
+++ b/src/virtual_machines/mod.rs
@@ -0,0 +1 @@
+pub mod cam;
-- 
2.34.1