From 3ecde4e791d3bd6812d4421326d6d1cc4a03d106 Mon Sep 17 00:00:00 2001 From: Evgenii Akentev 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), + App(Box<(Term, Term)>), + Nil, + MkPair(Box<(Term, Term)>), + Car(Box), + Cdr(Box), + Lit(usize), +} + +impl Term { + fn eval(&self) -> Value { + run(self.compile(), Value::Null, vec![]) + } + + fn compile(&self) -> Vec { + 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), + Quote(Value), +} + +#[derive(Clone, Debug)] +enum Value { + Null, + Pair(Box<(Value, Value)>), + Closure(Box, Vec), + Num(usize), +} + +type Stack = Vec; + +fn run(instrs: Vec, 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