From 37f4450c34e7f54f5d3af20108ec16d7da62d380 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Sun, 10 Dec 2017 01:24:23 -0700 Subject: [PATCH] bug fixes on LCO, backtracking. --- src/main.rs | 2 +- src/prolog/and_stack.rs | 2 +- src/prolog/ast.rs | 12 +--- src/prolog/codegen.rs | 27 +++++--- src/prolog/fixtures.rs | 2 +- src/prolog/io.rs | 10 +-- src/prolog/machine.rs | 136 +++++++++++++++++++++------------------- src/prolog/macros.rs | 8 --- src/prolog/or_stack.rs | 8 ++- 9 files changed, 104 insertions(+), 103 deletions(-) diff --git a/src/main.rs b/src/main.rs index db52bf6f..70d257ef 100644 --- a/src/main.rs +++ b/src/main.rs @@ -34,7 +34,7 @@ mod tests { submit(&mut wam, "p(Z, Z)."); submit(&mut wam, "clouds(are, nice)."); - // submit returns true on failure, false on success. + // submit returns false on failure, true on success. assert_eq!(submit(&mut wam, "?- p(Z, Z)."), true); assert_eq!(submit(&mut wam, "?- p(Z, z)."), true); assert_eq!(submit(&mut wam, "?- p(Z, w)."), true); diff --git a/src/prolog/and_stack.rs b/src/prolog/and_stack.rs index f4d043da..540ff7c2 100644 --- a/src/prolog/and_stack.rs +++ b/src/prolog/and_stack.rs @@ -48,7 +48,7 @@ impl AndStack { pub fn clear(&mut self) { self.0.clear() } - + pub fn resize(&mut self, fr: usize, n: usize) { let len = self[fr].perms.len(); diff --git a/src/prolog/ast.rs b/src/prolog/ast.rs index cc0dd21f..bf5e467e 100644 --- a/src/prolog/ast.rs +++ b/src/prolog/ast.rs @@ -317,7 +317,7 @@ pub enum Term { pub enum InlinedQueryTerm { CompareNumber(CompareNumberQT, Vec>), IsAtomic(Vec>), - IsVar(Vec>) + IsVar(Vec>), } impl InlinedQueryTerm { @@ -325,7 +325,7 @@ impl InlinedQueryTerm { match self { &InlinedQueryTerm::CompareNumber(_, _) => 2, &InlinedQueryTerm::IsAtomic(_) => 1, - &InlinedQueryTerm::IsVar(_) => 1 + &InlinedQueryTerm::IsVar(_) => 1, } } } @@ -344,8 +344,8 @@ pub enum QueryTerm { CallN(Vec>), Catch(Vec>), Cut, - Is(Vec>), Inlined(InlinedQueryTerm), + Is(Vec>), Term(Term), Throw(Vec>) } @@ -756,8 +756,6 @@ impl ControlInstruction { &ControlInstruction::ThrowExecute => true, &ControlInstruction::Goto(_, _) => true, &ControlInstruction::Proceed => true, - &ControlInstruction::IsCall(_, _) => true, - &ControlInstruction::IsExecute(_, _) => true, _ => false } } @@ -963,10 +961,6 @@ pub struct Heap { } impl Heap { - pub fn new() -> Self { - Heap { heap: vec![], h : 0 } - } - pub fn with_capacity(cap: usize) -> Self { Heap { heap: vec![HeapCellValue::Str(0); cap], h: 0 } } diff --git a/src/prolog/codegen.rs b/src/prolog/codegen.rs index c13ccea1..213141e6 100644 --- a/src/prolog/codegen.rs +++ b/src/prolog/codegen.rs @@ -101,7 +101,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> } } } - + fn add_or_increment_void_instr(target: &mut Vec) where Target: CompilationTarget<'a> { @@ -279,13 +279,13 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> ControlInstruction::Call(name, arity, _) => *ctrl = ControlInstruction::Execute(name, arity), ControlInstruction::CallN(arity) => - *ctrl = ControlInstruction::ExecuteN(arity), - ControlInstruction::IsCall(r, at) => - *ctrl = ControlInstruction::IsExecute(r, at), + *ctrl = ControlInstruction::ExecuteN(arity), ControlInstruction::CatchCall => *ctrl = ControlInstruction::CatchExecute, ControlInstruction::ThrowCall => *ctrl = ControlInstruction::ThrowExecute, + ControlInstruction::IsCall(r, at) => + *ctrl = ControlInstruction::IsExecute(r, at), ControlInstruction::Proceed => {}, _ => dealloc_index += 1 // = code.len() } @@ -334,7 +334,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> let r = self.mark_non_callable(name, 1, term_loc, vr, code); code.push(is_var!(r)); } - } + } } Ok(()) @@ -376,12 +376,10 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> Line::Cut(CutInstruction::Cut(is_terminal)) }); }, - &QueryTerm::Inlined(ref term) => - self.compile_inlined(term, term_loc, code)?, &QueryTerm::Is(ref terms) => { - let (mut acode, at) = try!(self.call_arith_eval(terms[1].as_ref(), 1)); + let (mut acode, at) = self.call_arith_eval(terms[1].as_ref(), 1)?; code.append(&mut acode); - + match terms[0].as_ref() { &Term::Var(ref vr, ref name) => { let r = self.mark_non_callable(name, @@ -389,7 +387,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> term_loc, vr, code); - + code.push(is_call!(r, at.unwrap_or(interm!(1)))); }, &Term::Constant(_, Constant::Float(fl)) => { @@ -405,11 +403,20 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> temp_v!(1))]); code.push(is_call!(temp_v!(1), at.unwrap_or(interm!(1)))); }, + &Term::Constant(_, Constant::Rational(ref r)) => { + let r = r.clone(); + code.push(query![put_constant!(Level::Shallow, + Constant::Rational(r), + temp_v!(1))]); + code.push(is_call!(temp_v!(1), at.unwrap_or(interm!(1)))); + }, _ => { code.push(fail!()); } } }, + &QueryTerm::Inlined(ref term) => + self.compile_inlined(term, term_loc, code)?, _ if chunk_num == 0 => { self.marker.reset_arg(term.arity()); diff --git a/src/prolog/fixtures.rs b/src/prolog/fixtures.rs index 240bf57c..d9404cd0 100644 --- a/src/prolog/fixtures.rs +++ b/src/prolog/fixtures.rs @@ -279,7 +279,7 @@ impl<'a> VariableFixtures<'a> { for term_ref in head.breadth_first_iter() { match term_ref { - TermRef::Var(_, cell, _) => { + TermRef::Var(Level::Shallow, cell, _) => { unsafe_vars.remove(&cell.get().norm()); }, _ => {} diff --git a/src/prolog/io.rs b/src/prolog/io.rs index 298ecb35..4bb6a5a8 100644 --- a/src/prolog/io.rs +++ b/src/prolog/io.rs @@ -114,16 +114,16 @@ impl fmt::Display for ControlInstruction { write!(f, "execute {}/{}", name, arity), &ControlInstruction::Goto(p, arity) => write!(f, "goto {}/{}", p, arity), + &ControlInstruction::IsCall(r, ref at) => + write!(f, "is_call {}, {}", r, at), + &ControlInstruction::IsExecute(r, ref at) => + write!(f, "is_execute {}, {}", r, at), &ControlInstruction::Proceed => write!(f, "proceed"), &ControlInstruction::ThrowCall => write!(f, "call_throw"), &ControlInstruction::ThrowExecute => write!(f, "execute_throw"), - &ControlInstruction::IsCall(r, ref at) => - write!(f, "is_call {}, {}", r, at), - &ControlInstruction::IsExecute(r, ref at) => - write!(f, "is_execute {}, {}", r, at), } } } @@ -166,7 +166,7 @@ impl fmt::Display for BuiltInInstruction { &BuiltInInstruction::IsAtomic(r) => write!(f, "is_atomic {}", r), &BuiltInInstruction::IsVar(r) => - write!(f, "is_var {}", r), + write!(f, "is_var {}", r), &BuiltInInstruction::ResetBlock => write!(f, "reset_block"), &BuiltInInstruction::SetBall => diff --git a/src/prolog/machine.rs b/src/prolog/machine.rs index aea29904..7dcaba6d 100644 --- a/src/prolog/machine.rs +++ b/src/prolog/machine.rs @@ -11,6 +11,7 @@ use prolog::or_stack::*; use prolog::ordered_float::OrderedFloat; use prolog::fixtures::*; +use std::cmp::max; use std::collections::HashMap; use std::ops::{Index, IndexMut}; use std::vec::Vec; @@ -325,6 +326,7 @@ impl Machine { self.ms.execute_fact_instr(&fact_instr); } + self.ms.p += 1; }, &Line::Indexing(ref indexing_instr) => @@ -339,6 +341,7 @@ impl Machine { self.ms.execute_query_instr(&query_instr); } + self.ms.p += 1; } } @@ -398,10 +401,11 @@ impl Machine { match var_data { &VarData::Perm(_) => { let e = self.ms.e; + let r = var_data.as_reg_type().reg_num(); let addr = self.ms.and_stack[e][r].clone(); - heap_locs.insert(var, addr); + heap_locs.insert(var, addr); }, &VarData::Temp(cn, _, _) if cn == chunk_num => { let r = var_data.as_reg_type(); @@ -641,10 +645,11 @@ impl MachineState { } } - fn num_frames(&self) -> usize { - self.and_stack.len() + self.or_stack.len() + fn next_global_index(&self) -> usize { + max(if self.and_stack.len() > 0 { self.and_stack[self.e].global_index } else { 0 }, + if self.b > 0 { self.or_stack[self.b - 1].global_index } else { 0 }) + 1 } - + fn store(&self, a: Addr) -> Addr { match a { Addr::HeapCell(r) => self.heap[r].as_addr(r), @@ -855,12 +860,12 @@ impl MachineState { Ok(Ratio::from_integer(bi)) } } - + fn get_number(&self, at: &ArithmeticTerm) -> Result> { match at { &ArithmeticTerm::Reg(r) => { let addr = self[r].clone(); - let item = self.deref(addr); + let item = self.store(self.deref(addr)); match item { Addr::Con(Constant::Integer(bi)) => @@ -889,10 +894,10 @@ impl MachineState { let u_n2 = BigUint::from_bytes_le(&n2_b); let result = BigInt::from_signed_bytes_le(&f(u_n1, u_n2).to_bytes_le()); - + self.interms[t - 1] = Number::Integer(result); } - + fn execute_arith_instr(&mut self, instr: &ArithmeticInstruction) { match instr { &ArithmeticInstruction::Add(ref a1, ref a2, t) => { @@ -994,7 +999,7 @@ impl MachineState { [atom!("zero_divisor")])); return; } - + self.interms[t - 1] = n1 / n2; self.p += 1; }, @@ -1043,7 +1048,7 @@ impl MachineState { let n2 = try_or_fail!(self, self.get_number(a2)); match (n1, n2) { - (Number::Integer(n1), Number::Integer(n2)) => + (Number::Integer(n1), Number::Integer(n2)) => self.signed_bitwise_op(n1, n2, t, |u_n1, u_n2| u_n1 ^ u_n2), _ => { self.throw_exception(functor!("evaluation_error", @@ -1193,7 +1198,7 @@ impl MachineState { }, Addr::HeapCell(_) | Addr::StackCell(_, _) => { let h = self.heap.h; - + self.heap.push(HeapCellValue::Str(h + 1)); self.heap.push(HeapCellValue::NamedStr(arity, name.clone())); @@ -1254,7 +1259,7 @@ impl MachineState { if let Addr::HeapCell(hc) = addr { if hc < h { let val = self.heap[hc].clone(); - + self.heap.push(val); self.s += 1; @@ -1374,7 +1379,7 @@ impl MachineState { self[reg] = Addr::Lis(self.heap.h), &QueryInstruction::PutStructure(_, ref name, arity, reg) => { let h = self.heap.h; - + self.heap.push(HeapCellValue::NamedStr(arity, name.clone())); self[reg] = Addr::Str(h); }, @@ -1507,7 +1512,7 @@ impl MachineState { let h = self.heap.h; self.registers[1] = Addr::HeapCell(h); - + self.heap.append(hcv); self.goto_throw(); } @@ -1561,7 +1566,7 @@ impl MachineState { fn copy_and_align_ball_to_heap(&mut self) { let diff = self.ball.0 - self.heap.h; - + for heap_value in self.ball.1.iter().cloned() { self.heap.push(match heap_value { HeapCellValue::Con(c) => HeapCellValue::Con(c), @@ -1580,7 +1585,7 @@ impl MachineState { &BuiltInInstruction::CompareNumber(cmp, ref at_1, ref at_2) => { let n1 = try_or_fail!(self, self.get_number(at_1)); let n2 = try_or_fail!(self, self.get_number(at_2)); - + self.fail = match cmp { CompareNumberQT::GreaterThan if !(n1.gt(n2)) => true, CompareNumberQT::GreaterThanOrEqual if !(n1.gte(n2)) => true, @@ -1616,7 +1621,7 @@ impl MachineState { self.write_constant_to_var(addr, &c); self.p += 1; - }, + }, &BuiltInInstruction::EraseBall => { self.ball.0 = 0; self.ball.1.truncate(0); @@ -1663,6 +1668,7 @@ impl MachineState { if nb > 0 && self.or_stack[b].b == nb { self.b = self.or_stack[nb - 1].b; + self.or_stack.truncate(self.b); } self.p += 1; @@ -1691,6 +1697,8 @@ impl MachineState { }, &BuiltInInstruction::UnwindStack => { self.b = self.block; + self.or_stack.truncate(self.b); + self.fail = true; }, &BuiltInInstruction::IsAtomic(r) => { @@ -1727,40 +1735,38 @@ impl MachineState { } }; } - + fn execute_ctrl_instr(&mut self, code_dir: &CodeDir, instr: &ControlInstruction) { match instr { &ControlInstruction::Allocate(num_cells) => { - if let Some(ref or_fr) = self.or_stack.top() { - let and_gi = if self.and_stack.len() > self.e { - self.and_stack[self.e].global_index - } else { - 0 - }; - - if and_gi <= or_fr.global_index { - self.e = or_fr.e; - } - } + let gi = self.next_global_index(); + self.p += 1; + if self.e + 1 < self.and_stack.len() { - let index = self.e + 1; + let and_gi = self.and_stack[self.e].global_index; + let or_gi = self.or_stack.top() + .map(|or_fr| or_fr.global_index) + .unwrap_or(0); - self.and_stack[index].e = self.e; - self.and_stack[index].cp = self.cp; + if and_gi > or_gi { + let index = self.e + 1; - self.and_stack.resize(index, num_cells); - - self.e = index; - } else { - let num_frames = self.num_frames(); - - self.and_stack.push(num_frames + 1, self.e, self.cp, num_cells); - self.e = self.and_stack.len() - 1; - }; + self.and_stack[index].e = self.e; + self.and_stack[index].cp = self.cp; + self.and_stack[index].global_index = gi; + + self.and_stack.resize(index, num_cells); - self.p += 1; + self.e = index; + + return; + } + } + + self.and_stack.push(gi, self.e, self.cp, num_cells); + self.e = self.and_stack.len() - 1; }, &ControlInstruction::Call(ref name, arity, _) => self.try_call_predicate(code_dir, name.clone(), arity), @@ -1781,10 +1787,10 @@ impl MachineState { }, &ControlInstruction::Deallocate => { let e = self.e; - + self.cp = self.and_stack[e].cp; - self.e = self.and_stack[e].e; - + self.e = self.and_stack[e].e; + self.p += 1; }, &ControlInstruction::Execute(ref name, arity) => @@ -1798,15 +1804,6 @@ impl MachineState { self.b0 = self.b; self.p = CodePtr::DirEntry(p); }, - &ControlInstruction::Proceed => - self.p = self.cp, - &ControlInstruction::ThrowCall => { - self.cp = self.p + 1; - self.goto_throw(); - }, - &ControlInstruction::ThrowExecute => { - self.goto_throw(); - }, &ControlInstruction::IsCall(r, ref at) => { let a1 = self[r].clone(); let a2 = try_or_fail!(self, self.get_number(at)); @@ -1818,9 +1815,18 @@ impl MachineState { let a1 = self[r].clone(); let a2 = try_or_fail!(self, self.get_number(at)); - self.unify(a1, Addr::Con(Constant::from(a2))); + self.unify(a1, Addr::Con(Constant::from(a2))); self.p = self.cp; - } + }, + &ControlInstruction::Proceed => + self.p = self.cp, + &ControlInstruction::ThrowCall => { + self.cp = self.p + 1; + self.goto_throw(); + }, + &ControlInstruction::ThrowExecute => { + self.goto_throw(); + }, }; } @@ -1829,9 +1835,9 @@ impl MachineState { match instr { &IndexedChoiceInstruction::Try(l) => { let n = self.num_of_args; - let num_frames = self.num_frames(); - - self.or_stack.push(num_frames + 1, + let gi = self.next_global_index(); + + self.or_stack.push(gi, self.e, self.cp, self.b, @@ -1899,7 +1905,7 @@ impl MachineState { self.heap.truncate(self.or_stack[b].h); self.b = self.or_stack[b].b; - self.or_stack.pop(); + self.or_stack.truncate(self.b); self.hb = self.heap.h; self.p += l; @@ -1912,9 +1918,9 @@ impl MachineState { match instr { &ChoiceInstruction::TryMeElse(offset) => { let n = self.num_of_args; - let num_frames = self.num_frames(); - - self.or_stack.push(num_frames + 1, + let gi = self.next_global_index(); + + self.or_stack.push(gi, self.e, self.cp, self.b, @@ -1983,7 +1989,7 @@ impl MachineState { self.b = self.or_stack[b].b; - self.or_stack.pop(); + self.or_stack.truncate(self.b); self.hb = self.heap.h; self.p += 1; @@ -2012,7 +2018,7 @@ impl MachineState { &CutInstruction::GetLevel => { let b0 = self.b0; let e = self.e; - + self.and_stack[e].b0 = b0; self.p += 1; }, diff --git a/src/prolog/macros.rs b/src/prolog/macros.rs index 3398a36b..130ac3c4 100644 --- a/src/prolog/macros.rs +++ b/src/prolog/macros.rs @@ -135,14 +135,6 @@ macro_rules! is_var { ) } -/* -macro_rules! retry_me_else { - ($o:expr) => ( - Line::Choice(ChoiceInstruction::RetryMeElse($o)) - ) -} - */ - macro_rules! trust_me { () => ( Line::Choice(ChoiceInstruction::TrustMe) diff --git a/src/prolog/or_stack.rs b/src/prolog/or_stack.rs index 2f927b18..07041ed3 100644 --- a/src/prolog/or_stack.rs +++ b/src/prolog/or_stack.rs @@ -78,10 +78,12 @@ impl OrStack { self.0.last() } - pub fn pop(&mut self) { - self.0.pop(); + // truncate expects a 1-indexed new_b, ie. + // the value b of MachineState. + pub fn truncate(&mut self, new_b: usize) { + self.0.truncate(new_b); } - + pub fn is_empty(&self) -> bool { self.0.is_empty() } -- 2.54.0