repos / machines.rs.git

commit

1ef4e59

parent

50cdfb8

author

Evgenii Akentev

date

2024-09-24 15:46:35 +0400 +04

Add Krivine

 1@@ -0,0 +1,81 @@
 2+#[derive(Clone, Debug, PartialEq)]
 3+enum V {
 4+    Free(String),
 5+    Bound(usize),
 6+}
 7+
 8+#[derive(Clone, Debug)]
 9+enum Term {
10+    Appl(Box<(Term, Term)>),
11+    Var(V),
12+    Abst(Box<Term>),
13+}
14+
15+#[derive(Clone, Debug)]
16+enum Value {
17+    Closure(Term, Vec<(V, Value)>),
18+}
19+
20+#[derive(Clone, Debug)]
21+struct State(Term, Vec<Value>, Vec<(V, Value)>);
22+
23+impl State {
24+    fn eval(&self) -> Self {
25+        match self {
26+            State(Term::Abst(_), s, _) if s.len() == 0 => self.clone(),
27+            s => {
28+                let new_s = s.step();
29+                new_s.eval()
30+            }
31+        }
32+    }
33+
34+    fn step(&self) -> Self {
35+        match self {
36+            State(Term::Abst(m), s, e) => {
37+                match s.split_first() {
38+                    Some((head, tail)) => {
39+                        let mut new_e = vec![(V::Bound(0), head.clone())];
40+                        new_e.append(&mut e.clone());
41+                        State(*m.clone(), tail.to_vec(), new_e)
42+                    },
43+                    None => { todo!() }
44+                }
45+            },
46+            State(Term::Appl(tuple), s, e) => {
47+                let (m, n) = *tuple.clone();
48+                let mut new_s = vec![Value::Closure(n.clone(), e.clone())];
49+                new_s.append(&mut s.clone());
50+                State(m.clone(), new_s, e.clone())
51+            },
52+            State(Term::Var(x), s, e) => {
53+                let m = e.iter().find(|item| {
54+                    let (var, _) = *item;
55+                    *var == *x
56+                });
57+                match m {
58+                    Some(item) => {
59+                        let (_, Value::Closure(m, new_e)) = item;
60+                        State(m.clone(), s.clone(), new_e.clone())
61+                    },
62+                    None => panic!()
63+                        
64+                }
65+            }
66+        }
67+    }
68+}
69+
70+pub fn main() {
71+    use Term::*;
72+    use V::*;
73+    println!("Krivine:");
74+
75+    let t1: Term = Appl(Box::new((Abst(Box::new(Appl(Box::new((Var(Bound(0)), Var(Bound(0))))))), (Abst(Box::new(Var(Bound(0))))))));
76+    let result = State(t1, vec![], vec![]).eval();
77+    println!("T1 eval: {:?}", result);
78+
79+    let t2: Term = Appl(Box::new((Appl(Box::new((Abst(Box::new(Var(Bound(0)))), Abst(Box::new(Var(Bound(0))))))), Abst(Box::new(Var(Bound(0)))))));
80+    let result2 = State(t2, vec![], vec![]).eval();                                                                     
81+    println!("T2 eval: {:?}", result2);
82+}

1@@ -1 +1,2 @@
2 pub mod cek;
3+pub mod krivine;

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