wam/
lib.rs

1use std::collections::HashMap;
2
3#[derive(Clone, PartialEq)]
4enum Cell {
5    Variable(Address),          // points to bounded term (or itself if unbound)
6    Structure(Address),         // usize points to functor
7    Functor(String, usize),     // String refers to the name, usize is the arity
8}
9
10impl std::fmt::Debug for Cell {
11    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
12        match self {
13            &Cell::Variable(bind) => write!(f, "REF {:?}", bind),
14            &Cell::Structure(ptr) => write!(f, "STR {:?}", ptr),
15            &Cell::Functor(ref name, arity) => write!(f, "{}/{}", name, arity),
16        }
17    }
18}
19
20#[derive(Clone, Debug)]
21pub enum Instruction {
22    // query term instructions
23    PutStructure(String, usize, Address),   // name, arity, register
24    SetVariable(Address),                   // register
25    SetValue(Address),                      // register
26    
27    // program instructions
28    GetStructure(String, usize, Address),   // name, arity, register
29    UnifyVariable(Address),                 // register
30    UnifyValue(Address),                    // register
31
32    // varaible argument instructions
33    PutVariable(Address, Address),          // register, register
34    PutValue(Address, Address),             // register, register
35    GetVariable(Address, Address),          // register, register
36    GetValue(Address, Address),             // register, register
37
38    // controll instructions
39    Call(String),                           // label
40    Proceed,
41}
42
43enum Mode {
44    Read,
45    Write,
46}
47
48#[derive(Clone, PartialEq, Debug, Copy)]
49pub enum Address {
50    Heap(usize),
51    Register(usize),
52}
53
54impl std::ops::Add<usize> for Address {
55    type Output = Address;
56
57    fn add(self, rhs: usize) -> Address {
58        match self {
59            Address::Heap(a) => Address::Heap(a + rhs),
60            Address::Register(a) => Address::Register(a + rhs),
61        }
62    }
63}
64
65pub struct Instance {
66    heap: Vec<Cell>,
67    registers: Vec<Option<Cell>>,
68    mode: Mode,
69    s_ptr: Address,
70    instructions: Vec<Instruction>,
71    pc: usize,
72    labels: HashMap<String, usize>,
73}
74
75const REGISTER_COUNT: usize = 100;
76
77impl Instance {
78
79    pub fn new() -> Instance {
80        Instance {
81            heap: Vec::new(),
82            registers: vec![None; REGISTER_COUNT],
83            mode: Mode::Read,
84            s_ptr: Address::Heap(0),
85            instructions: Vec::new(),
86            pc: 0,
87            labels: HashMap::new(),
88        }
89    }
90
91    fn set_cell(&mut self, address: Address, cell: Cell) {
92        match address {
93            Address::Heap(a) => self.heap[a] = cell,
94            Address::Register(a) => self.registers[a] = Some(cell),
95        }
96    }
97
98    fn fetch_cell(&self, address: Address) -> Cell {
99        match address {
100            Address::Heap(a) => self.heap[a].clone(),
101            Address::Register(a) => self.registers[a].clone().unwrap(),
102        }
103    }
104
105    fn deref(&self, address: Address) -> Address {
106        match self.fetch_cell(address) {
107            Cell::Variable(v_address) => {
108                if address == v_address {
109                    address
110                } else {
111                    self.deref(v_address)
112                }
113            },
114            _ => address,
115        }
116    }
117
118    fn bind(&mut self, a1: Address, a2: Address) {
119        let cells = (self.fetch_cell(a1), self.fetch_cell(a2));
120        let (var_address, target_adresss) = match cells {
121            (Cell::Variable(_), _) => (a1, a2),
122            (_, Cell::Variable(_)) => (a2, a1),
123            _ => panic!("neiter {:?} or {:?} points to a variable", a1, a2)
124        };
125
126        // Point the variable to the target cell
127        self.set_cell(var_address, Cell::Variable(target_adresss));    
128    }
129
130    pub fn load(&mut self, instructions: Vec<Instruction>) {
131        self.instructions.extend(instructions);
132    }
133
134    pub fn load_labeled(&mut self, label: String, instructions: Vec<Instruction>) {
135        let index = self.instructions.len();
136        self.load(instructions);
137        self.labels.insert(label, index - 1);
138    }
139
140    fn inst_put_structure(&mut self, name: String, arity: usize, register: Address) {
141        let str_index = self.heap.len();
142        let str_cell = Cell::Structure(Address::Heap(str_index + 1));
143        self.heap.push(str_cell.clone());
144        self.heap.push(Cell::Functor(name.clone(), arity.clone()));               
145        self.set_cell(register, str_cell);
146    }
147
148    fn inst_set_variable(&mut self, register: Address) {
149        let ref_index = self.heap.len();
150        let ref_cell = Cell::Variable(Address::Heap(ref_index));
151        self.heap.push(ref_cell.clone());
152        self.set_cell(register, ref_cell);
153    }
154
155    fn inst_set_value(&mut self, register: Address) {
156        let cell = self.fetch_cell(register);
157        self.heap.push(cell);
158    }
159
160    fn inst_get_structure(&mut self, name: String, arity: usize, register: Address) {
161        let address = self.deref(register);
162        match self.fetch_cell(address) {
163            Cell::Variable(_) => {
164                let str_index = self.heap.len();
165                self.heap.push(Cell::Structure(Address::Heap(str_index + 1)));
166                self.heap.push(Cell::Functor(name, arity));
167                self.bind(address, Address::Heap(str_index));
168                self.mode = Mode::Write;
169            },
170            Cell::Structure(a) => {
171                let cell = self.fetch_cell(a);
172                if cell == Cell::Functor(name, arity) {
173                    self.s_ptr = a + 1;
174                    self.mode = Mode::Read;
175                } else {
176                    panic!("fail");
177                }
178            },
179            _ => panic!("fail"),
180        }
181    }
182
183    fn inst_unify_variable(&mut self, register: Address) {
184        match self.mode {
185            Mode::Read => {
186                let cell = self.fetch_cell(self.s_ptr);
187                self.set_cell(register, cell);
188            },
189            Mode::Write => {
190                let ref_index = self.heap.len();
191                let cell = Cell::Variable(Address::Heap(ref_index));
192                self.heap.push(cell.clone());
193                self.set_cell(register, cell);
194            }
195        }
196        
197        self.s_ptr = self.s_ptr + 1;
198    }
199
200    fn inst_unift_value(&mut self, register: Address) {
201        match self.mode {
202            Mode::Read => {
203                let s = self.s_ptr;
204                self.unify(register, s);
205            },
206            Mode::Write => {
207                let cell = self.fetch_cell(register);
208                self.heap.push(cell);
209            }
210        }
211    }
212
213    fn inst_put_variable(&mut self, register_n: Address, register_i: Address) {
214        let ref_index = self.heap.len();
215        let cell = Cell::Variable(Address::Heap(ref_index));
216        self.heap.push(cell.clone());
217        self.set_cell(register_n, cell.clone());
218        self.set_cell(register_i, cell);
219    }
220
221    fn inst_put_value(&mut self, register_n: Address, register_i: Address) {
222        let cell = self.fetch_cell(register_n);
223        self.set_cell(register_i, cell);
224    }
225
226    fn inst_get_variable(&mut self, register_n: Address, register_i: Address) {
227        let cell = self.fetch_cell(register_i);
228        self.set_cell(register_n, cell);
229    }
230
231    fn inst_get_value(&mut self, register_n: Address, register_i: Address) {
232        self.unify(register_n, register_i);
233    }
234
235    fn inst_call(&mut self, label: String) {
236        if self.labels.contains_key(&label) {
237            self.pc = *self.labels.get(&label).unwrap();
238        } else {
239            panic!("Unification error");
240        }
241    }
242
243    fn fetch_instruction(&self) -> Option<Instruction> {
244        if self.instructions.len() <= self.pc {
245            None
246        } else {
247            Some(self.instructions[self.pc].clone())
248        }
249    }
250
251    pub fn execute(&mut self) {
252        println!("Executing {:?}", self.fetch_instruction());
253
254        match self.fetch_instruction() {
255            Some(instruction) => match instruction {
256                Instruction::PutStructure(name, arity, register) => self.inst_put_structure(name, arity, register),
257                Instruction::SetVariable(register) => self.inst_set_variable(register),
258                Instruction::SetValue(register) => self.inst_set_value(register),
259                Instruction::GetStructure(name, arity, register) => self.inst_get_structure(name, arity, register),
260                Instruction::UnifyVariable(register) => self.inst_unify_variable(register),
261                Instruction::UnifyValue(register) => self.inst_unift_value(register),
262                Instruction::PutVariable(register_n, register_i) => self.inst_put_variable(register_n, register_i),
263                Instruction::PutValue(register_n, register_i) => self.inst_put_value(register_n, register_i),
264                Instruction::GetVariable(register_n, register_i) => self.inst_get_variable(register_n, register_i),
265                Instruction::GetValue(register_n, register_i) => self.inst_get_value(register_n, register_i),
266                Instruction::Call(label) => self.inst_call(label),
267                Instruction::Proceed => return,
268            }
269            None => return
270        }
271
272        self.pc += 1;
273        self.execute();
274    }
275
276    fn unify(&mut self, ad1: Address, ad2: Address) {
277        let mut pdl = Vec::new();
278        pdl.push(ad1);
279        pdl.push(ad2);
280
281        while !pdl.is_empty() {
282            let d1 = self.deref(pdl.pop().unwrap());
283            let d2 = self.deref(pdl.pop().unwrap());
284            println!("{:?} <> {:?}", d1, d2);
285            if d1 != d2 {
286                match (self.fetch_cell(d1), self.fetch_cell(d2)) {
287                    (Cell::Variable(_), _) => self.bind(d1, d2),
288                    (_, Cell::Variable(_)) => self.bind(d1, d2),
289                    (Cell::Structure(str_1), Cell::Structure(str_2)) => {
290                        match (self.fetch_cell(str_1), self.fetch_cell(str_2)) {
291                            (Cell::Functor(f1, n1), Cell::Functor(f2, n2)) => {
292                                if f1 != f2 || n1 != n2 {
293                                    panic!("functors {}/{} and {}/{} do not match", f1, n1, f2, n2);
294                                }
295                                for i in 1..(n1+1) {
296                                    pdl.push(str_1 + i);
297                                    pdl.push(str_2 + i);
298                                }
299                            },
300                            _ => panic!("structure cell addresses unwrapped to {:?} and {:?}", self.fetch_cell(str_1), self.fetch_cell(str_2)),
301                        }
302                    }
303                    _ => {
304                        panic!("cannot unify {:?} and {:?}", self.fetch_cell(d1), self.fetch_cell(d2));
305                    },
306                }
307            }
308        }
309    }
310
311    pub fn dump_heap(&self) {
312        println!("HEAP:");
313        for (index, cell) in self.heap.iter().enumerate() {
314            println!("{:4} | {:?}", index, cell);
315        }
316    }
317
318    pub fn dump_registers(&self) {
319        println!("REGISTERS:");
320        for (index, content) in self.registers.iter().enumerate() {
321            println!("X_{} = {:?}", index, content);
322        }
323    }
324
325}
326
327#[cfg(test)]
328mod tests {
329    use super::*;
330
331    fn instruction_set_1() -> Vec<Instruction> {
332        vec![
333            Instruction::PutStructure(String::from("h"), 2, Address::Register(3)),
334            Instruction::SetVariable(Address::Register(2)),
335            Instruction::SetVariable(Address::Register(5)),
336            Instruction::PutStructure(String::from("f"), 1, Address::Register(4)),
337            Instruction::SetValue(Address::Register(5)),
338            Instruction::PutStructure(String::from("p"), 3, Address::Register(1)),
339            Instruction::SetValue(Address::Register(2)),
340            Instruction::SetValue(Address::Register(3)),
341            Instruction::SetValue(Address::Register(4)),
342        ]
343    }
344
345    fn instruction_set_2() -> Vec<Instruction> {
346        vec![
347            Instruction::GetStructure(String::from("p"), 3, Address::Register(1)),
348            Instruction::UnifyVariable(Address::Register(2)),
349            Instruction::UnifyVariable(Address::Register(3)),
350            Instruction::UnifyVariable(Address::Register(4)),
351            Instruction::GetStructure(String::from("f"), 1, Address::Register(2)),
352            Instruction::UnifyVariable(Address::Register(5)),
353            Instruction::GetStructure(String::from("h"), 2, Address::Register(3)),
354            Instruction::UnifyValue(Address::Register(4)),
355            Instruction::UnifyVariable(Address::Register(6)),
356            Instruction::GetStructure(String::from("f"), 1, Address::Register(6)),
357            Instruction::UnifyVariable(Address::Register(7)),
358            Instruction::GetStructure(String::from("a"), 0, Address::Register(7)),
359        ]
360    }
361
362    fn instruction_set_3() -> Vec<Instruction> {
363        vec![
364            Instruction::PutVariable(Address::Register(4), Address::Register(1)),
365            Instruction::PutStructure(String::from("h"), 2, Address::Register(2)),
366            Instruction::SetValue(Address::Register(4)),
367            Instruction::SetVariable(Address::Register(5)),
368            Instruction::PutStructure(String::from("f"), 1, Address::Register(3)),
369            Instruction::SetValue(Address::Register(5)),
370            Instruction::Call(String::from("p/3")),
371        ]
372    }
373
374    fn instruction_set_4() -> (String, Vec<Instruction>) {
375        (String::from("p/3"), vec![
376            Instruction::GetStructure(String::from("f"), 1, Address::Register(1)),
377            Instruction::Proceed,
378            Instruction::UnifyVariable(Address::Register(1)),
379            Instruction::GetStructure(String::from("h"), 2, Address::Register(2)),
380            Instruction::UnifyVariable(Address::Register(5)),
381            Instruction::UnifyVariable(Address::Register(6)),
382            Instruction::GetValue(Address::Register(5), Address::Register(3)),
383            Instruction::GetStructure(String::from("f"), 1, Address::Register(6)),
384            Instruction::UnifyVariable(Address::Register(7)),
385            Instruction::GetStructure(String::from("a"), 0, Address::Register(7)),
386        ])
387    }
388
389    #[test]
390    fn query_term_instructions() {
391        let mut inst = Instance::new();
392        inst.load(instruction_set_1());
393        inst.execute();
394
395        let expected_heap = vec![
396            Cell::Structure(Address::Heap(1)),
397            Cell::Functor(String::from("h"), 2),
398            Cell::Variable(Address::Heap(2)),
399            Cell::Variable(Address::Heap(3)),
400            Cell::Structure(Address::Heap(5)),
401            Cell::Functor(String::from("f"), 1),
402            Cell::Variable(Address::Heap(3)),
403            Cell::Structure(Address::Heap(8)),
404            Cell::Functor(String::from("p"), 3),
405            Cell::Variable(Address::Heap(2)),
406            Cell::Structure(Address::Heap(1)),
407            Cell::Structure(Address::Heap(5)),
408        ];
409
410        assert_eq!(inst.heap, expected_heap);
411    }
412
413    #[test]
414    fn unify() {
415        let instructions = vec![
416            // f(X, g(X, a))
417            // X1 = f(X2, X3)
418            // X2 = X
419            // X3 = g(X2, X4)
420            // X4 = a
421            Instruction::PutStructure(String::from("a"), 0, Address::Register(4)),
422            Instruction::PutStructure(String::from("g"), 2, Address::Register(3)),
423            Instruction::SetVariable(Address::Register(2)),
424            Instruction::SetValue(Address::Register(4)),
425            Instruction::PutStructure(String::from("f"), 2, Address::Register(1)),
426            Instruction::SetValue(Address::Register(2)),
427            Instruction::SetValue(Address::Register(3)),
428            
429            // f(b, Y)
430            // X5 = f(X7, X8)
431            // X6 = b
432            // X7 = Y
433            Instruction::PutStructure(String::from("b"), 0, Address::Register(6)),
434            Instruction::PutStructure(String::from("f"), 2, Address::Register(5)),
435            Instruction::SetValue(Address::Register(6)),
436            Instruction::SetVariable(Address::Register(7)),
437        ];
438
439        let mut inst = Instance::new();
440        inst.load(instructions);
441        inst.execute();
442        
443        let expected_heap = vec![
444            Cell::Structure(Address::Heap(1)),
445            Cell::Functor(String::from("a"), 0),
446            Cell::Structure(Address::Heap(3)),
447            Cell::Functor(String::from("g"), 2),
448            Cell::Variable(Address::Heap(4)),
449            Cell::Structure(Address::Heap(1)),
450            Cell::Structure(Address::Heap(7)),
451            Cell::Functor(String::from("f"), 2),
452            Cell::Variable(Address::Heap(4)),
453            Cell::Structure(Address::Heap(3)),
454            Cell::Structure(Address::Heap(11)),
455            Cell::Functor(String::from("b"), 0),
456            Cell::Structure(Address::Heap(13)),
457            Cell::Functor(String::from("f"), 2),
458            Cell::Structure(Address::Heap(11)),
459            Cell::Variable(Address::Heap(15)),
460        ];
461        
462        assert_eq!(inst.heap, expected_heap);
463
464        inst.unify(Address::Heap(6), Address::Heap(12));
465        
466        let expected_heap = vec![
467            Cell::Structure(Address::Heap(1)),
468            Cell::Functor(String::from("a"), 0),
469            Cell::Structure(Address::Heap(3)),
470            Cell::Functor(String::from("g"), 2),
471            Cell::Variable(Address::Heap(14)),      // 4 -> 14
472            Cell::Structure(Address::Heap(1)),
473            Cell::Structure(Address::Heap(7)),
474            Cell::Functor(String::from("f"), 2),
475            Cell::Variable(Address::Heap(4)),
476            Cell::Structure(Address::Heap(3)),
477            Cell::Structure(Address::Heap(11)),
478            Cell::Functor(String::from("b"), 0),
479            Cell::Structure(Address::Heap(13)),
480            Cell::Functor(String::from("f"), 2),
481            Cell::Structure(Address::Heap(11)),
482            Cell::Variable(Address::Heap(9)),       // 15 -> 9
483        ];
484
485        assert_eq!(inst.heap, expected_heap);
486
487    }
488
489    #[test]
490    fn program_instructions() {
491        let mut inst = Instance::new();
492        inst.load(instruction_set_1());
493        inst.load(instruction_set_2());
494        inst.execute();
495
496        let expected_heap = vec![
497            Cell::Structure(Address::Heap(1)),
498            Cell::Functor(String::from("h"), 2),
499            Cell::Variable(Address::Heap(12)),
500            Cell::Variable(Address::Heap(14)),
501            Cell::Structure(Address::Heap(5)),
502            Cell::Functor(String::from("f"), 1),
503            Cell::Variable(Address::Heap(3)),
504            Cell::Structure(Address::Heap(8)),
505            Cell::Functor(String::from("p"), 3),
506            Cell::Variable(Address::Heap(2)),
507            Cell::Structure(Address::Heap(1)),
508            Cell::Structure(Address::Heap(5)),
509            Cell::Structure(Address::Heap(13)),
510            Cell::Functor(String::from("f"), 1),
511            Cell::Variable(Address::Heap(15)),
512            Cell::Structure(Address::Heap(16)),
513            Cell::Functor(String::from("a"), 0),
514        ];
515
516        assert_eq!(inst.heap, expected_heap);
517
518    }
519    
520    #[test]
521    fn argument_instructions_1() {
522        let mut inst_1 = Instance::new();
523        inst_1.load(instruction_set_1());
524        inst_1.execute();
525
526        let mut inst_2 = Instance::new();
527        inst_2.load(instruction_set_3());
528        let (label, instructions) = instruction_set_4();
529        inst_2.load_labeled(label, instructions);
530        inst_2.execute();
531
532        assert_eq!(inst_1.heap, inst_2.heap);
533    }
534}
wam/lib.rs

wam/
lib.rs
