From 50cdfb8a64e76fa6ef3d2713d27cad3c6a29dc25 Mon Sep 17 00:00:00 2001
From: Evgenii Akentev <hi@ak3n.com>
Date: Tue, 24 Sep 2024 11:48:20 +0400
Subject: [PATCH] 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<Term>),
+}
+
+impl Term {
+    fn eval(&self, e: Vec<Value>, 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<Value>),
+}
+
+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<Cont>),
+    C2(Term, Vec<Value>, Box<Cont>)
+}
+
+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