From 50cdfb8a64e76fa6ef3d2713d27cad3c6a29dc25 Mon Sep 17 00:00:00 2001 From: Evgenii Akentev Date: Tue, 24 Sep 2024 11:48:20 +0400 Subject: [PATCH 1/1] Add CEK --- .gitignore | 1 + Cargo.lock | 7 ++++ Cargo.toml | 6 ++++ src/abstract_machines/cek.rs | 67 ++++++++++++++++++++++++++++++++++++ src/abstract_machines/mod.rs | 1 + src/lib.rs | 1 + src/main.rs | 5 +++ 7 files changed, 88 insertions(+) create mode 100644 .gitignore create mode 100644 Cargo.lock create mode 100644 Cargo.toml create mode 100644 src/abstract_machines/cek.rs create mode 100644 src/abstract_machines/mod.rs create mode 100644 src/lib.rs create mode 100644 src/main.rs diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..ea8c4bf --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +/target diff --git a/Cargo.lock b/Cargo.lock new file mode 100644 index 0000000..ed62551 --- /dev/null +++ b/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "machines" +version = "0.1.0" diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 0000000..b7deaec --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "machines" +version = "0.1.0" +edition = "2021" + +[dependencies] diff --git a/src/abstract_machines/cek.rs b/src/abstract_machines/cek.rs new file mode 100644 index 0000000..21a2ada --- /dev/null +++ b/src/abstract_machines/cek.rs @@ -0,0 +1,67 @@ +#[derive(Clone, Debug)] +enum Term { + Appl(Box<(Term, Term)>), + Var(usize), + Abst(Box), +} + +impl Term { + fn eval(&self, e: Vec, k: Cont) -> Value { + match self { + Term::Var(v) => k.cont(e[*v].clone()), + Term::Abst(t) => k.cont(Value::Closure(*t.clone(), e)), + Term::Appl(tuple) => { + let (t0, t1) = *tuple.clone(); + t0.eval(e.clone(), Cont::C2(t1, e.clone(), Box::new(k))) + } + } + } +} + +#[derive(Clone, Debug)] +enum Value { + Closure(Term, Vec), +} + +impl Value { + fn apply(&self, v1: Value, k: Cont) -> Value { + match self { + Value::Closure(t, e) => { + let mut new_e = vec![v1]; + new_e.append(e.clone().as_mut()); + t.eval(new_e.clone(), k) + }, + } + } +} + +#[derive(Clone)] +enum Cont { + C0, + C1(Value, Box), + C2(Term, Vec, Box) +} + +impl Cont { + fn cont(&self, v: Value) -> Value { + match self { + Cont::C0 => v, + Cont::C1(v0, k) => { v0.apply(v, *k.clone()) }, + Cont::C2(t1, e, k) => { t1.eval(e.to_vec(), Cont::C1(v, k.clone())) } + } + } +} + + +pub fn main() { + use Term::*; + println!("CEK:"); + + let t1: Term = Appl(Box::new((Abst(Box::new(Appl(Box::new((Var(0), Var(0)))))), (Abst(Box::new(Var(0))))))); + let result = t1.eval(vec![], Cont::C0); + println!("T1 eval: {:?}", result); + + let t2: Term = Appl(Box::new((Appl(Box::new((Abst(Box::new(Var(0))), Abst(Box::new(Var(0)))))), Abst(Box::new(Var(0)))))); + let result2 = t2.eval(vec![], Cont::C0); + println!("T2 eval: {:?}", result2); +} diff --git a/src/abstract_machines/mod.rs b/src/abstract_machines/mod.rs new file mode 100644 index 0000000..59f7641 --- /dev/null +++ b/src/abstract_machines/mod.rs @@ -0,0 +1 @@ +pub mod cek; diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..0af09f2 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1 @@ +pub mod abstract_machines; diff --git a/src/main.rs b/src/main.rs new file mode 100644 index 0000000..1b4716d --- /dev/null +++ b/src/main.rs @@ -0,0 +1,5 @@ +use machines::abstract_machines::cek; + +fn main() { + cek::main(); +} -- 2.34.1