From 4d6897509d4f34fd6d2af56e289a32cf70009fb9 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Thu, 25 May 2017 16:41:36 -0600 Subject: [PATCH] evacuate arguments on overwrite. --- src/main.rs | 6 +++++- src/prolog/ast.rs | 30 +++++++++++++++++++----------- src/prolog/codegen.rs | 8 ++------ src/prolog/debray_allocator.rs | 24 ++++++++++++++++++++---- src/prolog/io.rs | 2 +- src/prolog/iterators.rs | 29 ++++++++++------------------- src/prolog/machine.rs | 12 ++++++------ src/prolog/prolog_parser.lalrpop | 13 +++++++++---- src/prolog/prolog_parser.rs | 10 ++++++++-- 9 files changed, 80 insertions(+), 54 deletions(-) diff --git a/src/main.rs b/src/main.rs index 5bfac5db..70d9d605 100644 --- a/src/main.rs +++ b/src/main.rs @@ -611,7 +611,11 @@ mod tests { assert_eq!(submit(&mut wam, "?- f(p(three), X, X)."), false); assert_eq!(submit(&mut wam, "?- f(p(three), one, Y)."), false); assert_eq!(submit(&mut wam, "?- f(p(three), one, two)."), false); - assert_eq!(submit(&mut wam, "?- f(p(three), one, three)."), false); + assert_eq!(submit(&mut wam, "?- f(p(three), one, three)."), false); + + submit(&mut wam, "f(P, X) :- call(P, X)."); + + assert_eq!(submit(&mut wam, "?- f(p(one), one)."), true); } } diff --git a/src/prolog/ast.rs b/src/prolog/ast.rs index 6b35c1a9..56083c2e 100644 --- a/src/prolog/ast.rs +++ b/src/prolog/ast.rs @@ -13,6 +13,15 @@ pub enum GenContext { Head, Mid(usize), Last(usize) // Mid & Last: chunk_num } +impl GenContext { + pub fn chunk_num(self) -> usize { + match self { + GenContext::Head => 0, + GenContext::Mid(cn) | GenContext::Last(cn) => cn + } + } +} + pub enum PredicateClause { Fact(Term), Rule(Rule) @@ -115,7 +124,7 @@ pub enum Term { } pub enum QueryTerm { - CallN(Cell, Var, Vec>), + CallN(Vec>), Cut, Term(Term) } @@ -124,15 +133,15 @@ impl QueryTerm { pub fn arity(&self) -> usize { match self { &QueryTerm::Term(ref term) => term.arity(), - &QueryTerm::CallN(_, _, ref terms) => terms.len() + 1, + &QueryTerm::CallN(ref terms) => terms.len(), _ => 0 } } pub fn to_ref(&self) -> QueryTermRef { match self { - &QueryTerm::CallN(ref cell, ref var, ref terms) => - QueryTermRef::CallN(cell, var, terms), + &QueryTerm::CallN(ref terms) => + QueryTermRef::CallN(terms), &QueryTerm::Cut => QueryTermRef::Cut, &QueryTerm::Term(ref term) => @@ -148,7 +157,7 @@ pub struct Rule { #[derive(Clone, Copy)] pub enum ClauseType<'a> { - CallN(&'a Cell, &'a Var), + CallN, Deep(Level, &'a Cell, &'a Atom), Root } @@ -156,7 +165,7 @@ pub enum ClauseType<'a> { impl<'a> ClauseType<'a> { pub fn level_of_subterms(self) -> Level { match self { - ClauseType::CallN(_, _) => Level::Shallow, + ClauseType::CallN => Level::Shallow, ClauseType::Deep(_, _, _) => Level::Deep, ClauseType::Root => Level::Shallow } @@ -181,14 +190,14 @@ impl<'a> TermRef<'a> { | TermRef::Var(lvl, _, _) => lvl, TermRef::Clause(ClauseType::Root, _) => Level::Shallow, TermRef::Clause(ClauseType::Deep(lvl, _, _), _) => lvl, - TermRef::Clause(ClauseType::CallN(_, _), _) => Level::Shallow + TermRef::Clause(ClauseType::CallN, _) => Level::Shallow } } } #[derive(Clone, Copy)] pub enum QueryTermRef<'a> { - CallN(&'a Cell, &'a Var, &'a Vec>), + CallN(&'a Vec>), Cut, Term(&'a Term) } @@ -197,7 +206,7 @@ impl<'a> QueryTermRef<'a> { pub fn arity(self) -> usize { match self { QueryTermRef::Term(term) => term.arity(), - QueryTermRef::CallN(_, _, terms) => terms.len() + 1, + QueryTermRef::CallN(terms) => terms.len(), _ => 0 } } @@ -206,8 +215,7 @@ impl<'a> QueryTermRef<'a> { match self { QueryTermRef::Term(&Term::Clause(_, _, _)) | QueryTermRef::Term(&Term::Constant(_, Constant::Atom(_))) - | QueryTermRef::CallN(_, _, _) => - true, + | QueryTermRef::CallN(_) => true, _ => false } } diff --git a/src/prolog/codegen.rs b/src/prolog/codegen.rs index e9c87e69..63078650 100644 --- a/src/prolog/codegen.rs +++ b/src/prolog/codegen.rs @@ -97,10 +97,6 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> where Target: CompilationTarget<'a> { match ct { - ClauseType::CallN(_, _) => - for subterm in terms { - self.subterm_to_instr(subterm.as_ref(), term_loc, is_exposed, target); - }, ClauseType::Deep(lvl, cell, atom) => { self.marker.mark_non_var(lvl, term_loc, cell, target); target.push(Target::to_structure(lvl, atom.clone(), terms.len(), cell.get())); @@ -182,7 +178,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> fn add_conditional_call(compiled_query: &mut Code, qt: QueryTermRef, pvs: usize) { match qt { - QueryTermRef::CallN(_, _, terms) => { + QueryTermRef::CallN(terms) => { let call = ControlInstruction::CallN(terms.len()); compiled_query.push(Line::Control(call)); }, @@ -209,7 +205,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> if let &mut Line::Control(ref mut ctrl) = body.last_mut().unwrap() { *ctrl = ControlInstruction::Execute(name.clone(), last_arity); }, - &QueryTerm::CallN(_, _, ref terms) => + &QueryTerm::CallN(ref terms) => if let &mut Line::Control(ref mut ctrl) = body.last_mut().unwrap() { *ctrl = ControlInstruction::ExecuteN(terms.len()); }, diff --git a/src/prolog/debray_allocator.rs b/src/prolog/debray_allocator.rs index b99031d6..0c1f8dcd 100644 --- a/src/prolog/debray_allocator.rs +++ b/src/prolog/debray_allocator.rs @@ -14,7 +14,14 @@ pub struct DebrayAllocator<'a> { in_use: BTreeSet, } -impl<'a> DebrayAllocator<'a> { +impl<'a> DebrayAllocator<'a> { + fn is_curr_arg_distinct_from(&self, var: &'a Var) -> bool { + match self.contents.get(&self.arg_c) { + Some(t_var) if **t_var != *var => true, + _ => false + } + } + fn occurs_shallowly_in_head(&self, var: &'a Var, r: usize) -> bool { match self.bindings.get(var).unwrap() { @@ -142,6 +149,7 @@ impl<'a> DebrayAllocator<'a> { match term_loc { GenContext::Head => if let Level::Shallow = lvl { + self.evacuate_arg(0, target); self.alloc_with_cr(var) } else { self.alloc_with_ca(var) @@ -262,14 +270,22 @@ impl<'a> Allocator<'a> for DebrayAllocator<'a> RegType::Perm(0) => { let pr = cell.get().norm(); self.record_register(var, pr); + (pr, true) }, - r => (r, false) + r => (r, false) }; match lvl { Level::Shallow => { let k = self.arg_c; + + if !r.is_perm() { + if self.is_curr_arg_distinct_from(var) { + self.evacuate_arg(term_loc.chunk_num(), target); + } + } + self.arg_c += 1; cell.set(VarReg::ArgAndNorm(r, k)); @@ -295,14 +311,14 @@ impl<'a> Allocator<'a> for DebrayAllocator<'a> Level::Deep => target.push(Target::subterm_to_value(r)) }; - + if !r.is_perm() { let o = r.reg_num(); self.contents.insert(o, var); self.record_register(var, r); self.in_use.insert(o); - } + } } fn reset(&mut self) { diff --git a/src/prolog/io.rs b/src/prolog/io.rs index f814dc75..97f51633 100644 --- a/src/prolog/io.rs +++ b/src/prolog/io.rs @@ -285,7 +285,7 @@ Each predicate must have the same name and arity."; let compiled_fact = cg.compile_fact(fact); wam.add_fact(fact, compiled_fact); - + EvalSession::EntrySuccess }, &TopLevel::Rule(ref rule) => { diff --git a/src/prolog/iterators.rs b/src/prolog/iterators.rs index 20b9cfe5..2c0bf1a9 100644 --- a/src/prolog/iterators.rs +++ b/src/prolog/iterators.rs @@ -69,9 +69,8 @@ impl<'a> QueryIterator<'a> { fn new(term: QueryTermRef<'a>) -> Self { match term { - QueryTermRef::CallN(cell, var, child_terms) => { - let state = IteratorState::Clause(0, ClauseType::CallN(cell, var), child_terms); - + QueryTermRef::CallN(child_terms) => { + let state = IteratorState::Clause(0, ClauseType::CallN, child_terms); QueryIterator { state_stack: vec![state] } }, QueryTermRef::Term(term) => Self::from_term(term), @@ -97,14 +96,10 @@ impl<'a> Iterator for QueryIterator<'a> { IteratorState::Clause(child_num, ct, child_terms) => { if child_num == child_terms.len() { match ct { - ClauseType::Root => + ClauseType::CallN | ClauseType::Root => return None, ClauseType::Deep(_, _, _) => - return Some(TermRef::Clause(ct, child_terms)), - ClauseType::CallN(cell, var) => { - let state = IteratorState::Var(Level::Shallow, cell, var); - self.state_stack.push(state); - } + return Some(TermRef::Clause(ct, child_terms)) }; } else { self.push_clause(child_num + 1, ct, child_terms); @@ -172,15 +167,11 @@ impl<'a> Iterator for FactIterator<'a> { self.push_subterm(ct.level_of_subterms(), child_term); } - match ct { - ClauseType::Root => - continue, + match ct { ClauseType::Deep(_, _, _) => return Some(TermRef::Clause(ct, child_terms)), - ClauseType::CallN(cell, var) => { - let state = IteratorState::Var(Level::Shallow, cell, var); - self.state_queue.push_back(state); - } + _ => + continue }; }, IteratorState::InitialCons(lvl, cell, head, tail) => { @@ -249,8 +240,8 @@ impl<'a> ChunkedIterator<'a> let iter = once(QueryTermRef::Term(p0)); let inner_iter : Box>> = match p1 { - &QueryTerm::CallN(ref cell, ref var, ref child_terms) => - Box::new(once(QueryTermRef::CallN(cell, var, child_terms))), + &QueryTerm::CallN(ref child_terms) => + Box::new(once(QueryTermRef::CallN(child_terms))), &QueryTerm::Term(ref p1) => Box::new(once(QueryTermRef::Term(p1))), _ => Box::new(empty()) @@ -288,7 +279,7 @@ impl<'a> ChunkedIterator<'a> break; } }, - QueryTermRef::CallN(_, _, child_terms) => { + QueryTermRef::CallN(child_terms) => { result.push(term); arity = child_terms.len() + 1; break; diff --git a/src/prolog/machine.rs b/src/prolog/machine.rs index ae82952d..26c27d88 100644 --- a/src/prolog/machine.rs +++ b/src/prolog/machine.rs @@ -994,7 +994,7 @@ impl MachineState { &ControlInstruction::Call(ref name, arity, _) => self.try_call_predicate(code_dir, name.clone(), arity), &ControlInstruction::CallN(arity) => { - let addr = self.deref(self.registers[arity + 1].clone()); + let addr = self.deref(self.registers[arity].clone()); match self.store(addr) { Addr::Str(a) => { @@ -1006,13 +1006,13 @@ impl MachineState { self.registers[i] = self.heap[a + i].as_addr(a + i); } - self.try_call_predicate(code_dir, name, arity + narity); + self.try_call_predicate(code_dir, name, arity + narity - 1); } else { self.fail = true; } }, Addr::Con(Constant::Atom(name)) => - self.try_call_predicate(code_dir, name, arity), + self.try_call_predicate(code_dir, name, arity - 1), _ => self.fail = true }; }, @@ -1027,7 +1027,7 @@ impl MachineState { &ControlInstruction::Execute(ref name, arity) => self.try_execute_predicate(code_dir, name.clone(), arity), &ControlInstruction::ExecuteN(arity) => { - let addr = self.deref(self.registers[arity + 1].clone()); + let addr = self.deref(self.registers[arity].clone()); match self.store(addr) { Addr::Str(a) => { @@ -1039,13 +1039,13 @@ impl MachineState { self.registers[i] = self.heap[a + i].as_addr(a + i); } - self.try_execute_predicate(code_dir, name, arity + narity); + self.try_execute_predicate(code_dir, name, arity + narity - 1); } else { self.fail = true; } }, Addr::Con(Constant::Atom(name)) => - self.try_execute_predicate(code_dir, name, arity), + self.try_execute_predicate(code_dir, name, arity - 1), _ => self.fail = true }; }, diff --git a/src/prolog/prolog_parser.lalrpop b/src/prolog/prolog_parser.lalrpop index 93a80a04..73c04361 100644 --- a/src/prolog/prolog_parser.lalrpop +++ b/src/prolog/prolog_parser.lalrpop @@ -32,8 +32,13 @@ Call : QueryTerm = { }, "call" "(" )*> ")" => QueryTerm::Term(Term::Clause(Cell::default(), a, ts)), - "call" "(" )*> ")" => - QueryTerm::CallN(Cell::default(), v, ts) + "call" "(" )*> ")" => { + let mut ts = ts; + let bv = Box::new(Term::Var(Cell::default(), v)); + + ts.push(bv); + QueryTerm::CallN(ts) + } }; Clause : Term = { @@ -93,7 +98,7 @@ Rule : Rule = { QueryTerm : QueryTerm = { => <>, "!" => QueryTerm::Cut, - => QueryTerm::CallN(Cell::default(), <>, Vec::new()), + => QueryTerm::CallN(vec![Box::new(Term::Var(Cell::default(), <>))]), => QueryTerm::Term(<>), => QueryTerm::Term(Term::Constant(Cell::default(), Constant::Atom(<>))) }; @@ -108,4 +113,4 @@ Term : Term = { Var : Var = { r"[A-Z][A-Za-z0-9_]*" => <>.trim().to_string() -}; \ No newline at end of file +}; diff --git a/src/prolog/prolog_parser.rs b/src/prolog/prolog_parser.rs index d25a01df..9d3e39d8 100644 --- a/src/prolog/prolog_parser.rs +++ b/src/prolog/prolog_parser.rs @@ -2901,7 +2901,13 @@ pub fn __action9< (_, _, _): (usize, &'input str, usize), ) -> QueryTerm { - QueryTerm::CallN(Cell::default(), v, ts) + { + let mut ts = ts; + let bv = Box::new(Term::Var(Cell::default(), v)); + + ts.push(bv); + QueryTerm::CallN(ts) + } } #[allow(unused_variables)] @@ -3105,7 +3111,7 @@ pub fn __action24< (_, __0, _): (usize, Var, usize), ) -> QueryTerm { - QueryTerm::CallN(Cell::default(), __0, Vec::new()) + QueryTerm::CallN(vec![Box::new(Term::Var(Cell::default(), __0))]) } #[allow(unused_variables)] -- 2.54.0