From e7560150b06687c24725fccf84aa0f1f3e981ac3 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Sat, 10 Feb 2018 23:34:30 -0700 Subject: [PATCH] add eq, neq predicates. --- README.md | 12 +++--- src/prolog/ast.rs | 24 ++++++++++-- src/prolog/builtins.rs | 5 +++ src/prolog/codegen.rs | 45 ++++++++++----------- src/prolog/heap_iter.rs | 50 +++++++++++++++++++++++- src/prolog/io.rs | 8 ++++ src/prolog/iterators.rs | 19 ++++++--- src/prolog/machine/machine_state_impl.rs | 29 +++++++++----- src/prolog/macros.rs | 12 ++++++ src/prolog/parser | 2 +- src/tests.rs | 14 ++++++- 11 files changed, 172 insertions(+), 48 deletions(-) diff --git a/README.md b/README.md index 17499cce..e2f97699 100644 --- a/README.md +++ b/README.md @@ -18,23 +18,23 @@ Extend rusty-wam to include the following, among other features: * call/N as a built-in meta-predicate (_done_). * ISO Prolog compliant throw/catch (_done_). * Built-in and user-defined operators of all fixities, with custom - associativity and precedence (_done_). + associativity and precedence (_done_). * Bignum, rational number and floating point arithmetic (_done_). * Built-in control operators (`,`, `;`, `->`, etc.) (_done_). * Built-in predicates for list processing and top-level declarative control (`setup_call_control/3`, `call_with_inference_limit/3`, etc.) (_in progress_). -* Add a rudimentary module system. +* Add a rudimentary module system. * Attributed variables using the SICStus Prolog interface and semantics. Adding coroutines like `dif/2`, `freeze/2`, etc. - is straightforward with attributed variables. + is straightforward with attributed variables. * An occurs check. * Mode declarations. * Extensions for clp(FD). * `if_` and related predicates, following the developments of the paper "Indexing `dif/2`". * Strings, blobs, and other data types. - + ## Phase 3 Use the WAM code produced by the completed code generator to target LLVM @@ -78,6 +78,8 @@ The following predicates are built-in to rusty-wam. `(xor)/2`, `(rem)/2`, `(mod)/2`, `(/\)/2`, `(\/)/2`, `(>>)/2`, `(<<)/2`. * Comparison operators: `>`, `<`, `=<`, `>=`, `=:=`, `=\=`. * `(\+)/1` +* `(==)/2` +* `(\==)/2` * `(=)/2` * `(=..)/2` * `(->)/2` @@ -159,7 +161,7 @@ prolog> :{ member(X, [X|_]). member(X, [_|Xs]) :- member(X, Xs). }: -prolog> ?- member(X, [a, b, c]). +prolog> ?- member(X, [a, b, c]). true . X = a ; X = b ; diff --git a/src/prolog/ast.rs b/src/prolog/ast.rs index 4d82a194..79f72642 100644 --- a/src/prolog/ast.rs +++ b/src/prolog/ast.rs @@ -399,12 +399,14 @@ pub enum QueryTerm { Catch(Vec>), Cut, Display(Vec>), - DuplicateTerm(Vec>), + DuplicateTerm(Vec>), + Eq(Vec>), Functor(Vec>), Ground(Vec>), Inlined(InlinedQueryTerm), Is(Vec>), Jump(JumpStub), + NotEq(Vec>), SetupCallCleanup(Vec>), Term(Term), Throw(Vec>) @@ -417,12 +419,14 @@ impl QueryTerm { &QueryTerm::Catch(_) => 3, &QueryTerm::Display(_) => 1, &QueryTerm::Throw(_) => 1, - &QueryTerm::DuplicateTerm(_) => 2, + &QueryTerm::DuplicateTerm(_) => 2, + &QueryTerm::Eq(_) => 2, &QueryTerm::Functor(_) => 3, &QueryTerm::Ground(_) => 1, &QueryTerm::Inlined(ref term) => term.arity(), &QueryTerm::Is(_) => 2, &QueryTerm::Jump(ref vars) => vars.len(), + &QueryTerm::NotEq(_) => 2, &QueryTerm::CallN(ref terms) => terms.len(), &QueryTerm::Cut => 0, &QueryTerm::SetupCallCleanup(_) => 3, @@ -445,9 +449,11 @@ pub enum ClauseType<'a> { Deep(Level, &'a Cell, &'a TabledRc, Option), Display, DuplicateTerm, + Eq, Functor, Ground, Is, + NotEq, Root(&'a TabledRc), SetupCallCleanup, Throw, @@ -463,9 +469,11 @@ impl<'a> ClauseType<'a> { &ClauseType::Display => "display", &ClauseType::Deep(_, _, name, _) => name.as_str(), &ClauseType::DuplicateTerm => "duplicate_term", + &ClauseType::Eq => "==", &ClauseType::Functor => "functor", &ClauseType::Ground => "ground", &ClauseType::Is => "is", + &ClauseType::NotEq => "\\==", &ClauseType::Root(name) => name.as_str(), &ClauseType::SetupCallCleanup => "setup_call_cleanup", &ClauseType::Throw => "throw" @@ -857,7 +865,9 @@ pub enum ControlInstruction { DisplayExecute, Deallocate, DuplicateTermCall, - DuplicateTermExecute, + DuplicateTermExecute, + EqCall, + EqExecute, Execute(TabledRc, usize), ExecuteN(usize), FunctorCall, @@ -871,6 +881,8 @@ pub enum ControlInstruction { JmpByExecute(usize, usize), IsCall(RegType, ArithmeticTerm), IsExecute(RegType, ArithmeticTerm), + NotEqCall, + NotEqExecute, Proceed, ThrowCall, ThrowExecute, @@ -888,11 +900,15 @@ impl ControlInstruction { &ControlInstruction::DisplayExecute => true, &ControlInstruction::DuplicateTermCall => true, &ControlInstruction::DuplicateTermExecute => true, + &ControlInstruction::EqCall => true, + &ControlInstruction::EqExecute => true, &ControlInstruction::Execute(_, _) => true, &ControlInstruction::CallN(_) => true, &ControlInstruction::ExecuteN(_) => true, &ControlInstruction::FunctorCall => true, &ControlInstruction::FunctorExecute => true, + &ControlInstruction::NotEqCall => true, + &ControlInstruction::NotEqExecute => true, &ControlInstruction::ThrowCall => true, &ControlInstruction::ThrowExecute => true, &ControlInstruction::GetCleanerCall => true, @@ -903,7 +919,7 @@ impl ControlInstruction { &ControlInstruction::IsCall(..) => true, &ControlInstruction::IsExecute(..) => true, &ControlInstruction::JmpByCall(..) => true, - &ControlInstruction::JmpByExecute(..) => true, + &ControlInstruction::JmpByExecute(..) => true, _ => false } } diff --git a/src/prolog/builtins.rs b/src/prolog/builtins.rs index a0889d58..dc05b568 100644 --- a/src/prolog/builtins.rs +++ b/src/prolog/builtins.rs @@ -540,6 +540,8 @@ fn get_builtins(atom_tbl: TabledData) -> Code { restore_cut_policy!(), // restore_cut_policy/0, 382. proceed!(), ground_execute!(), // ground/1, 384. + eq_execute!(), // (==)/2, 385. + not_eq_execute!(), // (\==)/2, 386. ] } @@ -590,6 +592,7 @@ pub fn build_code_dir(atom_tbl: TabledData) -> (Code, CodeDir, OpDir) op_dir.insert((tabled_rc!("=..", atom_tbl), Fixity::In), (XFX, 700)); op_dir.insert((tabled_rc!("==", atom_tbl), Fixity::In), (XFX, 700)); + op_dir.insert((tabled_rc!("\\==", atom_tbl), Fixity::In), (XFX, 700)); // there are 63 registers in the VM, so call/N is defined for all 0 <= N <= 62 // (an extra register is needed for the predicate name) @@ -634,6 +637,8 @@ pub fn build_code_dir(atom_tbl: TabledData) -> (Code, CodeDir, OpDir) code_dir.insert((tabled_rc!("nonvar", atom_tbl), 1), (PredicateKeyType::BuiltIn, 380)); code_dir.insert((tabled_rc!("ground", atom_tbl), 1), (PredicateKeyType::BuiltIn, 384)); + code_dir.insert((tabled_rc!("==", atom_tbl), 2), (PredicateKeyType::BuiltIn, 385)); + code_dir.insert((tabled_rc!("\\==", atom_tbl), 2), (PredicateKeyType::BuiltIn, 386)); (builtin_code, code_dir, op_dir) } diff --git a/src/prolog/codegen.rs b/src/prolog/codegen.rs index a386e611..6e16dcc9 100644 --- a/src/prolog/codegen.rs +++ b/src/prolog/codegen.rs @@ -259,10 +259,12 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> code.push(Line::Control(ControlInstruction::CatchCall)), &QueryTerm::Display(_) => code.push(Line::Control(ControlInstruction::DisplayCall)), - &QueryTerm::DuplicateTerm(_) => + &QueryTerm::DuplicateTerm(_) => code.push(Line::Control(ControlInstruction::DuplicateTermCall)), + &QueryTerm::Eq(_) => + code.push(Line::Control(ControlInstruction::EqCall)), &QueryTerm::Ground(_) => - code.push(Line::Control(ControlInstruction::GroundCall)), + code.push(Line::Control(ControlInstruction::GroundCall)), &QueryTerm::Functor(_) => code.push(Line::Control(ControlInstruction::FunctorCall)), &QueryTerm::Inlined(_) => @@ -270,6 +272,8 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> &QueryTerm::Jump(ref vars) => { code.push(jmp_call!(vars.len(), 0)); }, + &QueryTerm::NotEq(_) => + code.push(Line::Control(ControlInstruction::NotEqCall)), &QueryTerm::Term(Term::Constant(_, Constant::Atom(ref atom))) => { let call = ControlInstruction::Call(atom.clone(), 0, pvs); code.push(Line::Control(call)); @@ -303,12 +307,16 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> *ctrl = ControlInstruction::DisplayExecute, ControlInstruction::DuplicateTermCall => *ctrl = ControlInstruction::DuplicateTermExecute, + ControlInstruction::EqCall => + *ctrl = ControlInstruction::EqExecute, ControlInstruction::GroundCall => *ctrl = ControlInstruction::GroundExecute, ControlInstruction::FunctorCall => *ctrl = ControlInstruction::FunctorExecute, ControlInstruction::JmpByCall(arity, offset) => *ctrl = ControlInstruction::JmpByExecute(arity, offset), + ControlInstruction::NotEqCall => + *ctrl = ControlInstruction::NotEqExecute, ControlInstruction::CatchCall => *ctrl = ControlInstruction::CatchExecute, ControlInstruction::ThrowCall => @@ -509,21 +517,14 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> }, &QueryTerm::Inlined(ref term) => self.compile_inlined(term, term_loc, code)?, - _ if chunk_num == 0 => { - self.marker.reset_arg(term.arity()); - - let iter = term.post_order_iter(); - let query = self.compile_target(iter, term_loc, is_exposed); - - if !query.is_empty() { - code.push(Line::Query(query)); - } - - Self::add_conditional_call(code, term, conjunct_info.perm_vars()); - }, _ => { - let num_vars = conjunct_info.perm_vs.vars_above_threshold(i + 1); - self.compile_query_line(term, term_loc, code, num_vars, is_exposed); + let num_perm_vars = if chunk_num == 0 { + conjunct_info.perm_vars() + } else { + conjunct_info.perm_vs.vars_above_threshold(i + 1) + }; + + self.compile_query_line(term, term_loc, code, num_perm_vars, is_exposed); }, }; @@ -666,18 +667,18 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> } fn compile_query_line(&mut self, term: &'a QueryTerm, term_loc: GenContext, - code: &mut Code, index: usize, is_exposed: bool) + code: &mut Code, num_perm_vars_left: usize, is_exposed: bool) { self.marker.reset_arg(term.arity()); - let iter = term.post_order_iter(); - let compiled_query = self.compile_target(iter, term_loc, is_exposed); + let iter = term.post_order_iter(); + let query = self.compile_target(iter, term_loc, is_exposed); - if !compiled_query.is_empty() { - code.push(Line::Query(compiled_query)); + if !query.is_empty() { + code.push(Line::Query(query)); } - Self::add_conditional_call(code, term, index); + Self::add_conditional_call(code, term, num_perm_vars_left); } pub fn compile_query(&mut self, query: &'a Vec) -> Result diff --git a/src/prolog/heap_iter.rs b/src/prolog/heap_iter.rs index 608d5d13..a61f4a0e 100644 --- a/src/prolog/heap_iter.rs +++ b/src/prolog/heap_iter.rs @@ -123,10 +123,18 @@ impl MachineState { HeapCellPostOrderIterator::new(HeapCellPreOrderIterator::new(self, a)) } - pub fn acyclic_pre_order_iter<'a>(&'a self, a: Addr) -> HeapCellAcyclicIterator> + pub fn acyclic_pre_order_iter<'a>(&'a self, a: Addr) + -> HeapCellAcyclicIterator> { HeapCellAcyclicIterator::new(HeapCellPreOrderIterator::new(self, a)) } + + pub fn zipped_acyclic_pre_order_iter<'a>(&'a self, a1: Addr, a2: Addr) + -> HeapCellZippedAcyclicIterator> + { + HeapCellZippedAcyclicIterator::new(HeapCellPreOrderIterator::new(self, a1), + HeapCellPreOrderIterator::new(self, a2)) + } } pub trait MutStackHeapCellIterator { @@ -171,3 +179,43 @@ impl Iterator for HeapCellAcyclicIterator self.iter.next() } } + +pub struct HeapCellZippedAcyclicIterator { + i1: HeapCellIter, + i2: HeapCellIter, + seen: HashSet<(Addr, Addr)> +} + +impl HeapCellZippedAcyclicIterator +{ + pub fn new(i1: HeapCellIter, i2: HeapCellIter) -> Self { + HeapCellZippedAcyclicIterator { i1, i2, seen: HashSet::new() } + } +} + +impl Iterator for HeapCellZippedAcyclicIterator + where HeapCellIter: Iterator + + MutStackHeapCellIterator +{ + type Item = (HeapCellValue, HeapCellValue); + + fn next(&mut self) -> Option { + while let (Some(a1), Some(a2)) = (self.i1.stack().pop(), self.i2.stack().pop()) { + if self.seen.contains(&(a1.clone(), a2.clone())) { + continue; + } else { + self.i1.stack().push(a1.clone()); + self.i2.stack().push(a2.clone()); + self.seen.insert((a1, a2)); + + break; + } + } + + if let (Some(v1), Some(v2)) = (self.i1.next(), self.i2.next()) { + Some((v1, v2)) + } else { + None + } + } +} diff --git a/src/prolog/io.rs b/src/prolog/io.rs index dc23a742..55d0d9ee 100644 --- a/src/prolog/io.rs +++ b/src/prolog/io.rs @@ -123,6 +123,10 @@ impl fmt::Display for ControlInstruction { write!(f, "call_duplicate_term"), &ControlInstruction::DuplicateTermExecute => write!(f, "execute_duplicate_term"), + &ControlInstruction::EqCall => + write!(f, "eq_call"), + &ControlInstruction::EqExecute => + write!(f, "eq_execute"), &ControlInstruction::ExecuteN(arity) => write!(f, "execute_N {}", arity), &ControlInstruction::FunctorCall => @@ -151,6 +155,10 @@ impl fmt::Display for ControlInstruction { write!(f, "jmp_by_call {}/{}", offset, arity), &ControlInstruction::JmpByExecute(arity, offset) => write!(f, "jmp_by_execute {}/{}", offset, arity), + &ControlInstruction::NotEqCall => + write!(f, "neq_call"), + &ControlInstruction::NotEqExecute => + write!(f, "neq_execute"), &ControlInstruction::Proceed => write!(f, "proceed"), &ControlInstruction::ThrowCall => diff --git a/src/prolog/iterators.rs b/src/prolog/iterators.rs index 0a5b08c1..4b0f7f63 100644 --- a/src/prolog/iterators.rs +++ b/src/prolog/iterators.rs @@ -52,6 +52,10 @@ impl<'a> QueryIterator<'a> { let state = TermIterState::Clause(0, ClauseType::SetupCallCleanup, terms); QueryIterator { state_stack: vec![state] } }, + &QueryTerm::Eq(ref terms) => { + let state = TermIterState::Clause(0, ClauseType::Eq, terms); + QueryIterator { state_stack: vec![state] } + }, &QueryTerm::Functor(ref terms) => { let state = TermIterState::Clause(0, ClauseType::Functor, terms); QueryIterator { state_stack: vec![state] } @@ -64,9 +68,9 @@ impl<'a> QueryIterator<'a> { let state = TermIterState::Clause(0, ClauseType::Ground, terms); QueryIterator { state_stack: vec![state] } }, - &QueryTerm::Inlined(InlinedQueryTerm::CompareNumber(qt, ref terms)) => { + &QueryTerm::Inlined(InlinedQueryTerm::CompareNumber(qt, ref terms)) => { let state = TermIterState::Clause(0, ClauseType::CompareNumber(qt), terms); - QueryIterator { state_stack: vec![state] } + QueryIterator { state_stack: vec![state] } }, &QueryTerm::Is(ref terms) => { let state = TermIterState::Clause(0, ClauseType::Is, terms); @@ -79,8 +83,12 @@ impl<'a> QueryIterator<'a> { | &QueryTerm::Inlined(InlinedQueryTerm::IsFloat(ref terms)) | &QueryTerm::Inlined(InlinedQueryTerm::IsRational(ref terms)) | &QueryTerm::Inlined(InlinedQueryTerm::IsCompound(ref terms)) - | &QueryTerm::Inlined(InlinedQueryTerm::IsString(ref terms)) => + | &QueryTerm::Inlined(InlinedQueryTerm::IsString(ref terms)) => Self::from_term(terms[0].as_ref()), + &QueryTerm::NotEq(ref terms) => { + let state = TermIterState::Clause(0, ClauseType::NotEq, terms); + QueryIterator { state_stack: vec![state] } + }, &QueryTerm::Term(ref term) => Self::from_term(term), &QueryTerm::Throw(ref term) => { @@ -332,7 +340,8 @@ impl<'a> ChunkedIterator<'a> arity = 3; break; }, - &QueryTerm::Is(_) | &QueryTerm::DuplicateTerm(_) => { + &QueryTerm::Eq(_) | &QueryTerm::NotEq(_) + | &QueryTerm::Is(_) | &QueryTerm::DuplicateTerm(_) => { result.push(term); arity = 2; break; @@ -345,7 +354,7 @@ impl<'a> ChunkedIterator<'a> if self.term_loc.chunk_num() > 0 { self.deep_cut_encountered = true; } - }, + }, }; item = self.iter.next(); diff --git a/src/prolog/machine/machine_state_impl.rs b/src/prolog/machine/machine_state_impl.rs index 08872cf2..a9c594b8 100644 --- a/src/prolog/machine/machine_state_impl.rs +++ b/src/prolog/machine/machine_state_impl.rs @@ -1461,17 +1461,15 @@ SetupCallCleanupCutPolicy.") self.unify(Addr::HeapCell(old_h), a2); } - /* TODO: needs careful consideration of cyclic terms. // returns true on failure. fn eq_test(&self) -> bool { let a1 = self.store(self.deref(self[temp_v!(1)].clone())); let a2 = self.store(self.deref(self[temp_v!(2)].clone())); - let iter1 = self.acyclic_pre_order_iter(a1); - let iter2 = self.acyclic_pre_order_iter(a2); + let iter = self.zipped_acyclic_pre_order_iter(a1, a2); - for (v1, v2) in iter1.zip(iter2) { + for (v1, v2) in iter { match (v1, v2) { (HeapCellValue::NamedStr(ar1, n1, _), HeapCellValue::NamedStr(ar2, n2, _)) => if ar1 != ar2 || *n1 != *n2 { @@ -1482,16 +1480,13 @@ SetupCallCleanupCutPolicy.") (HeapCellValue::Addr(a1), HeapCellValue::Addr(a2)) => if a1 != a2 { return true; - }, - _ => { - return true; - } + }, + _ => return true } } false } - */ // returns true on failure. fn ground_test(&self) -> bool @@ -1620,6 +1615,14 @@ SetupCallCleanupCutPolicy.") self.duplicate_term(); self.p = self.cp; }, + &ControlInstruction::EqCall => { + self.fail = self.eq_test(); + self.p += 1; + }, + &ControlInstruction::EqExecute => { + self.fail = self.eq_test(); + self.p = self.cp; + }, &ControlInstruction::GroundCall => { self.fail = self.ground_test(); self.p += 1; @@ -1707,6 +1710,14 @@ SetupCallCleanupCutPolicy.") self.b0 = self.b; self.p += offset; }, + &ControlInstruction::NotEqCall => { + self.fail = !self.eq_test(); + self.p += 1; + }, + &ControlInstruction::NotEqExecute => { + self.fail = !self.eq_test(); + self.p = self.cp; + }, &ControlInstruction::Proceed => self.p = self.cp, &ControlInstruction::ThrowCall => { diff --git a/src/prolog/macros.rs b/src/prolog/macros.rs index a201d353..281129a8 100644 --- a/src/prolog/macros.rs +++ b/src/prolog/macros.rs @@ -568,3 +568,15 @@ macro_rules! ground_execute { Line::Control(ControlInstruction::GroundExecute) ) } + +macro_rules! eq_execute { + () => ( + Line::Control(ControlInstruction::EqExecute) + ) +} + +macro_rules! not_eq_execute { + () => ( + Line::Control(ControlInstruction::NotEqExecute) + ) +} diff --git a/src/prolog/parser b/src/prolog/parser index 5de18ac4..b50ed579 160000 --- a/src/prolog/parser +++ b/src/prolog/parser @@ -1 +1 @@ -Subproject commit 5de18ac4728701492cc19fd08d32b40f4d5918a3 +Subproject commit b50ed579fdb245f2d42fcd05b546c23f077b0991 diff --git a/src/tests.rs b/src/tests.rs index c4382421..dd2019b5 100644 --- a/src/tests.rs +++ b/src/tests.rs @@ -1339,6 +1339,18 @@ fn test_queries_on_builtins() assert_prolog_failure!(&mut wam, "?- B = f(A), ground(A)."); assert_prolog_success!(&mut wam, "?- ground(x), ground(f(x)), X = f(x), ground(g(f(X), [a,b]))."); + + assert_prolog_success!(&mut wam, "?- A = f(A), g(A, B) == g(f(A), B)."); + assert_prolog_failure!(&mut wam, "?- A = f(A), g(A, B) == g(f(A), b)."); + assert_prolog_failure!(&mut wam, "?- A == B."); + assert_prolog_failure!(&mut wam, "?- A == 12.1."); + assert_prolog_success!(&mut wam, "?- X = x, f(X, x) == f(x, X)."); + + assert_prolog_failure!(&mut wam, "?- A = f(A), g(A, B) \\== g(f(A), B)."); + assert_prolog_success!(&mut wam, "?- A = f(A), g(A, B) \\== g(f(A), b)."); + assert_prolog_success!(&mut wam, "?- A \\== B."); + assert_prolog_success!(&mut wam, "?- A \\== 12.1."); + assert_prolog_failure!(&mut wam, "?- X = x, f(X, x) \\== f(x, X)."); } #[test] @@ -1393,5 +1405,5 @@ fn test_queries_on_setup_call_cleanup() assert_prolog_success!(&mut wam, "?- catch(setup_call_cleanup(true,throw(goal),throw(cl)), Pat, true).", [["Pat = goal"]]); assert_prolog_success!(&mut wam, "?- catch(( setup_call_cleanup(true,(G=1;G=2),throw(cl)), throw(cont)), Pat, true).", - [["Pat = cont", "G = _1"]]); + [["Pat = cont", "G = _1"]]); } -- 2.54.0