From 7313472a70ad10bd3bfc718ee6e323824c888626 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Mon, 19 Feb 2018 22:34:56 -0700 Subject: [PATCH] add call_with_inference_limit --- README.md | 1 + src/prolog/ast.rs | 10 +- src/prolog/builtins.rs | 78 +++++- src/prolog/codegen.rs | 2 + src/prolog/io.rs | 14 +- src/prolog/iterators.rs | 12 +- src/prolog/lib/lists.rs | 2 +- src/prolog/machine/machine_state.rs | 297 ++++++++++++++++++++++- src/prolog/machine/machine_state_impl.rs | 257 ++++++++------------ src/prolog/machine/mod.rs | 13 +- src/prolog/macros.rs | 24 ++ src/prolog/parser | 2 +- 12 files changed, 541 insertions(+), 171 deletions(-) diff --git a/README.md b/README.md index e2b959e0..49fd9db9 100644 --- a/README.md +++ b/README.md @@ -96,6 +96,7 @@ The following predicates are built-in to rusty-wam. * `atomic/1` * `between/3` * `call/1..63` +* `call_with_inference_limit/3` * `catch/3` * `compound/1` * `display/1` diff --git a/src/prolog/ast.rs b/src/prolog/ast.rs index 6be24510..6eff00d3 100644 --- a/src/prolog/ast.rs +++ b/src/prolog/ast.rs @@ -419,6 +419,7 @@ pub type JumpStub = Vec; pub enum QueryTerm { Arg(Vec>), CallN(Vec>), + CallWithInferenceLimit(Vec>), Catch(Vec>), CompareTerm(CompareTermQT, Vec>), Cut, @@ -453,6 +454,7 @@ impl QueryTerm { &QueryTerm::Jump(ref vars) => vars.len(), &QueryTerm::NotEq(_) => 2, &QueryTerm::CallN(ref terms) => terms.len(), + &QueryTerm::CallWithInferenceLimit(_) => 3, &QueryTerm::Cut => 0, &QueryTerm::SetupCallCleanup(_) => 3, &QueryTerm::Term(ref term) => term.arity(), @@ -469,6 +471,7 @@ pub struct Rule { pub enum ClauseType<'a> { Arg, CallN, + CallWithInferenceLimit, Catch, CompareNumber(CompareNumberQT), CompareTerm(CompareTermQT), @@ -490,6 +493,7 @@ impl<'a> ClauseType<'a> { match self { &ClauseType::Arg => "arg", &ClauseType::CallN => "call", + &ClauseType::CallWithInferenceLimit => "call_with_inference_limit", &ClauseType::Catch => "catch", &ClauseType::CompareNumber(qt) => qt.name(), &ClauseType::CompareTerm(qt) => qt.name(), @@ -875,6 +879,7 @@ pub enum ArithmeticInstruction { pub enum BuiltInInstruction { CleanUpBlock, CompareNumber(CompareNumberQT, ArithmeticTerm, ArithmeticTerm), + DefaultTrustMe, DynamicCompareNumber(CompareNumberQT), EraseBall, Fail, @@ -883,7 +888,9 @@ pub enum BuiltInInstruction { GetBall, GetCurrentBlock, GetCutPoint(RegType), + InferenceLevel, InstallCleaner, + InstallInferenceCounter(RegType), InstallNewBlock, InternalCallN, IsAtomic(RegType), @@ -894,6 +901,7 @@ pub enum BuiltInInstruction { IsRational(RegType), IsString(RegType), IsVar(RegType), + RemoveInferenceCounter(RegType), ResetBlock, RestoreCutPolicy, SetBall, @@ -938,7 +946,7 @@ pub enum ControlInstruction { IsExecute(RegType, ArithmeticTerm), NotEqCall, NotEqExecute, - Proceed, + Proceed, ThrowCall, ThrowExecute, } diff --git a/src/prolog/builtins.rs b/src/prolog/builtins.rs index b59f0754..97462fbb 100644 --- a/src/prolog/builtins.rs +++ b/src/prolog/builtins.rs @@ -548,6 +548,76 @@ fn get_builtins(atom_tbl: TabledData) -> Code { compare_term_execute!(term_cmp_lt!()), // (@<)/2, 390. compare_term_execute!(term_cmp_eq!()), // (=@=)/2, 391. compare_term_execute!(term_cmp_ne!()), // (\=@=)/2, 392. + allocate!(4), // call_with_inference_limit/3, 393. + fact![get_var_in_fact!(perm_v!(3), 1), + get_var_in_fact!(perm_v!(2), 2), + get_var_in_fact!(perm_v!(1), 3)], + query![put_var!(perm_v!(4), 1)], + get_current_block!(), + query![put_value!(perm_v!(3), 1), + put_value!(perm_v!(2), 2), + put_value!(perm_v!(1), 3), + put_value!(perm_v!(4), 4)], + deallocate!(), + goto_execute!(400, 4), // goto call_with_inference_limit/4, 400. + try_me_else!(16), // call_with_inference_limit/4, 400. + allocate!(7), + fact![get_var_in_fact!(perm_v!(6), 1), + get_var_in_fact!(perm_v!(7), 2), + get_var_in_fact!(perm_v!(4), 3), + get_var_in_fact!(perm_v!(3), 4)], + query![put_var!(perm_v!(1), 1)], + install_new_block!(), + install_inference_counter!(perm_v!(7)), + get_cp!(perm_v!(5)), + query![put_value!(perm_v!(6), 1)], + call_n!(1), + query![put_var!(perm_v!(2), 3)], + remove_inference_counter!(perm_v!(2)), + query![put_value!(perm_v!(4), 1), + put_value!(perm_v!(5), 2)], + inference_level!(), + query![put_value!(perm_v!(3), 1), + put_value!(perm_v!(1), 2), + put_value!(perm_v!(2), 3)], + deallocate!(), + goto_execute!(436, 3), // goto end_block/3, 436. + default_trust_me!(), // 416. + allocate!(2), + fact![get_var_in_fact!(perm_v!(1), 3)], + query![put_value!(temp_v!(4), 1)], + reset_block!(), + query![put_var!(temp_v!(2), 1)], + remove_inference_counter!(temp_v!(1)), + query![put_var!(perm_v!(2), 1)], + get_ball!(), + erase_ball!(), + query![put_unsafe_value!(2, 1), + put_value!(perm_v!(1), 2)], + deallocate!(), + goto_execute!(429, 2), // goto handle_ile/2, 429. + try_me_else!(5), // handle_ile/2, 429. + switch_on_term!(1, 1, 0, 0), + fact![get_constant!(atom!("inference_limit_exceeded", atom_tbl), temp_v!(1)), + get_constant!(atom!("inference_limit_exceeded", atom_tbl), temp_v!(2))], + neck_cut!(), + proceed!(), + default_trust_me!(), + goto_execute!(59, 1), // goto throw/1, 59. + try_me_else!(9), // end_block/3, 436. + allocate!(1), + fact![get_var_in_fact!(perm_v!(1), 1)], + query![put_value!(temp_v!(2), 1)], + clean_up_block!(), + query![put_value!(perm_v!(1), 1)], + deallocate!(), + reset_block!(), + proceed!(), + default_trust_me!(), + install_inference_counter!(temp_v!(3)), + query![put_value!(temp_v!(2), 1)], + reset_block!(), + fail!() ] } @@ -641,7 +711,13 @@ pub fn build_code_dir(atom_tbl: TabledData) -> (Code, CodeDir, OpDir) code_dir.insert((tabled_rc!("=..", atom_tbl), 2), (PredicateKeyType::BuiltIn, 208)); code_dir.insert((tabled_rc!("length", atom_tbl), 2), (PredicateKeyType::BuiltIn, 261)); - code_dir.insert((tabled_rc!("setup_call_cleanup", atom_tbl), 3), (PredicateKeyType::BuiltIn, 294)); + code_dir.insert((tabled_rc!("setup_call_cleanup", atom_tbl), 3), + (PredicateKeyType::BuiltIn, 294)); + code_dir.insert((tabled_rc!("call_with_inference_limit", atom_tbl), 3), + (PredicateKeyType::BuiltIn, 393)); + code_dir.insert((tabled_rc!("_handle_inference_limit_exceeded", atom_tbl), 2), + (PredicateKeyType::BuiltIn, 421)); + code_dir.insert((tabled_rc!("compound", atom_tbl), 1), (PredicateKeyType::BuiltIn, 372)); code_dir.insert((tabled_rc!("rational", atom_tbl), 1), (PredicateKeyType::BuiltIn, 374)); code_dir.insert((tabled_rc!("string", atom_tbl), 1), (PredicateKeyType::BuiltIn, 376)); diff --git a/src/prolog/codegen.rs b/src/prolog/codegen.rs index 26a35458..73c7c97e 100644 --- a/src/prolog/codegen.rs +++ b/src/prolog/codegen.rs @@ -245,6 +245,8 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> fn add_conditional_call(code: &mut Code, qt: &QueryTerm, pvs: usize) { match qt { + &QueryTerm::CallWithInferenceLimit(_) => + code.push(goto_call!(393, 3)), &QueryTerm::SetupCallCleanup(_) => code.push(goto_call!(294, 3)), &QueryTerm::Arg(_) => { diff --git a/src/prolog/io.rs b/src/prolog/io.rs index 741397b2..bb7ccbcc 100644 --- a/src/prolog/io.rs +++ b/src/prolog/io.rs @@ -168,9 +168,9 @@ impl fmt::Display for ControlInstruction { &ControlInstruction::IsCall(r, ref at) => write!(f, "is_call {}, {}", r, at), &ControlInstruction::IsExecute(r, ref at) => - write!(f, "is_execute {}, {}", r, at), + write!(f, "is_execute {}, {}", r, at), &ControlInstruction::DynamicIs => - write!(f, "call_is"), + write!(f, "call_is"), &ControlInstruction::JmpByCall(arity, offset) => write!(f, "jmp_by_call {}/{}", offset, arity), &ControlInstruction::JmpByExecute(arity, offset) => @@ -184,7 +184,7 @@ impl fmt::Display for ControlInstruction { &ControlInstruction::ThrowCall => write!(f, "call_throw"), &ControlInstruction::ThrowExecute => - write!(f, "execute_throw"), + write!(f, "execute_throw"), } } } @@ -207,6 +207,10 @@ impl fmt::Display for BuiltInInstruction { match self { &BuiltInInstruction::CleanUpBlock => write!(f, "clean_up_block"), + &BuiltInInstruction::DefaultTrustMe => + write!(f, "default_trust_me"), + &BuiltInInstruction::InstallInferenceCounter(r) => + write!(f, "install_inference_counter {}", r), &BuiltInInstruction::EraseBall => write!(f, "erase_ball"), &BuiltInInstruction::Fail => @@ -221,6 +225,8 @@ impl fmt::Display for BuiltInInstruction { write!(f, "get_current_block X1"), &BuiltInInstruction::GetCutPoint(r) => write!(f, "get_cp {}", r), + &BuiltInInstruction::InferenceLevel => + write!(f, "inference_level"), &BuiltInInstruction::InstallCleaner => write!(f, "install_cleaner"), &BuiltInInstruction::InstallNewBlock => @@ -261,6 +267,8 @@ impl fmt::Display for BuiltInInstruction { write!(f, "number_test {}, {}, {} ", cmp, at_1, at_2), &BuiltInInstruction::DynamicCompareNumber(cmp) => write!(f, "dynamic_number_test {}", cmp), + &BuiltInInstruction::RemoveInferenceCounter(r) => + write!(f, "remove_inference_counter {}", r) } } } diff --git a/src/prolog/iterators.rs b/src/prolog/iterators.rs index 41ba1206..3bb8fd61 100644 --- a/src/prolog/iterators.rs +++ b/src/prolog/iterators.rs @@ -36,6 +36,12 @@ impl<'a> QueryIterator<'a> { let state = TermIterState::Clause(1, ClauseType::CallN, terms); QueryIterator { state_stack: vec![state] } }, + &QueryTerm::CallWithInferenceLimit(ref terms) => { + let ct = ClauseType::CallWithInferenceLimit; + let state = TermIterState::Clause(0, ct, terms); + + QueryIterator { state_stack: vec![state] } + }, &QueryTerm::Catch(ref terms) => { let state = TermIterState::Clause(0, ClauseType::Catch, terms); QueryIterator { state_stack: vec![state] } @@ -333,7 +339,8 @@ impl<'a> ChunkedIterator<'a> arity = child_terms.len() + 1; break; }, - &QueryTerm::Catch(ref child_terms) | &QueryTerm::Throw(ref child_terms) => { + &QueryTerm::Catch(ref child_terms) + | &QueryTerm::Throw(ref child_terms) => { result.push(term); arity = child_terms.len(); break; @@ -344,7 +351,8 @@ impl<'a> ChunkedIterator<'a> break; }, &QueryTerm::Arg(_) - | &QueryTerm::Functor(_) => { + | &QueryTerm::Functor(_) + | &QueryTerm::CallWithInferenceLimit(_) => { result.push(term); arity = 3; break; diff --git a/src/prolog/lib/lists.rs b/src/prolog/lib/lists.rs index 0e0df5f0..0f503e74 100644 --- a/src/prolog/lib/lists.rs +++ b/src/prolog/lib/lists.rs @@ -10,7 +10,7 @@ pub static LISTS: &str = "member(X, [X|_]). memberchk(X, Xs) :- member(X, Xs), !. reverse(Xs, Ys) :- var(Ys), !, reverse(Xs, [], Ys). - reverse(Ys, Xs) :- var(Ys), reverse(Xs, [], Ys). + reverse(Ys, Xs) :- reverse(Xs, [], Ys). reverse([], Ys, Ys). reverse([H|T], Ps, Rs) :- diff --git a/src/prolog/machine/machine_state.rs b/src/prolog/machine/machine_state.rs index 4189f9c2..eff3a5c4 100644 --- a/src/prolog/machine/machine_state.rs +++ b/src/prolog/machine/machine_state.rs @@ -1,11 +1,18 @@ use prolog::and_stack::*; +use prolog::builtins::CodeDir; use prolog::ast::*; use prolog::copier::*; +use prolog::num::{BigInt, BigUint, Zero, One}; use prolog::or_stack::*; use prolog::tabled_rc::*; use downcast::Any; + +use std::cmp::Ordering; +use std::collections::binary_heap::BinaryHeap; +use std::mem::swap; use std::ops::{Index, IndexMut}; +use std::rc::Rc; pub(super) struct DuplicateTerm<'a> { state: &'a mut MachineState @@ -176,6 +183,288 @@ pub struct MachineState { pub(super) interms: Vec, // intermediate numbers. } +pub(crate) type CallResult = Result<(), Vec>; + +pub(crate) trait CallPolicy: Any { + fn try_call(&mut self, machine_st: &mut MachineState, code_dir: &CodeDir, + name: TabledRc, arity: usize) + -> CallResult + { + let compiled_tl_index = code_dir.get(&(name, arity)).map(|index| index.1); + + match compiled_tl_index { + Some(compiled_tl_index) => { + machine_st.cp = machine_st.p + 1; + machine_st.num_of_args = arity; + machine_st.b0 = machine_st.b; + machine_st.p = CodePtr::DirEntry(compiled_tl_index); + }, + None => machine_st.fail = true + }; + + Ok(()) + } + + fn try_execute(&mut self, machine_st: &mut MachineState, code_dir: &CodeDir, + name: TabledRc, arity: usize) + -> CallResult + { + let compiled_tl_index = code_dir.get(&(name, arity)).map(|index| index.1); + + match compiled_tl_index { + Some(compiled_tl_index) => { + machine_st.num_of_args = arity; + machine_st.b0 = machine_st.b; + machine_st.p = CodePtr::DirEntry(compiled_tl_index); + }, + None => machine_st.fail = true + }; + + Ok(()) + } + + fn retry_me_else(&mut self, machine_st: &mut MachineState, offset: usize) -> CallResult + { + let b = machine_st.b - 1; + let n = machine_st.or_stack[b].num_args(); + + for i in 1 .. n + 1 { + machine_st.registers[i] = machine_st.or_stack[b][i].clone(); + } + + machine_st.e = machine_st.or_stack[b].e; + machine_st.cp = machine_st.or_stack[b].cp; + + machine_st.or_stack[b].bp = machine_st.p + offset; + + let old_tr = machine_st.or_stack[b].tr; + let curr_tr = machine_st.tr; + + machine_st.unwind_trail(old_tr, curr_tr); + machine_st.tr = machine_st.or_stack[b].tr; + + machine_st.trail.truncate(machine_st.tr); + machine_st.heap.truncate(machine_st.or_stack[b].h); + + machine_st.hb = machine_st.heap.h; + + machine_st.p += 1; + + Ok(()) + } + + fn retry(&mut self, machine_st: &mut MachineState, offset: usize) -> CallResult + { + let b = machine_st.b - 1; + let n = machine_st.or_stack[b].num_args(); + + for i in 1 .. n + 1 { + machine_st.registers[i] = machine_st.or_stack[b][i].clone(); + } + + machine_st.e = machine_st.or_stack[b].e; + machine_st.cp = machine_st.or_stack[b].cp; + + machine_st.or_stack[b].bp = machine_st.p + 1; + + let old_tr = machine_st.or_stack[b].tr; + let curr_tr = machine_st.tr; + + machine_st.unwind_trail(old_tr, curr_tr); + machine_st.tr = machine_st.or_stack[b].tr; + + machine_st.trail.truncate(machine_st.tr); + machine_st.heap.truncate(machine_st.or_stack[b].h); + + machine_st.hb = machine_st.heap.h; + + machine_st.p += offset; + + Ok(()) + } + + fn trust(&mut self, machine_st: &mut MachineState, offset: usize) -> CallResult + { + let b = machine_st.b - 1; + let n = machine_st.or_stack[b].num_args(); + + for i in 1 .. n + 1 { + machine_st.registers[i] = machine_st.or_stack[b][i].clone(); + } + + machine_st.e = machine_st.or_stack[b].e; + machine_st.cp = machine_st.or_stack[b].cp; + + let old_tr = machine_st.or_stack[b].tr; + let curr_tr = machine_st.tr; + + machine_st.unwind_trail(old_tr, curr_tr); + + machine_st.tr = machine_st.or_stack[b].tr; + machine_st.trail.truncate(machine_st.tr); + + machine_st.heap.truncate(machine_st.or_stack[b].h); + machine_st.b = machine_st.or_stack[b].b; + + machine_st.or_stack.truncate(machine_st.b); + + machine_st.hb = machine_st.heap.h; + machine_st.p += offset; + + Ok(()) + } + + fn trust_me(&mut self, machine_st: &mut MachineState) -> CallResult + { + let b = machine_st.b - 1; + let n = machine_st.or_stack[b].num_args(); + + for i in 1 .. n + 1 { + machine_st.registers[i] = machine_st.or_stack[b][i].clone(); + } + + machine_st.e = machine_st.or_stack[b].e; + machine_st.cp = machine_st.or_stack[b].cp; + + let old_tr = machine_st.or_stack[b].tr; + let curr_tr = machine_st.tr; + + machine_st.unwind_trail(old_tr, curr_tr); + + machine_st.tr = machine_st.or_stack[b].tr; + machine_st.trail.truncate(machine_st.tr); + + machine_st.heap.truncate(machine_st.or_stack[b].h); + + machine_st.b = machine_st.or_stack[b].b; + + machine_st.or_stack.truncate(machine_st.b); + + machine_st.hb = machine_st.heap.h; + machine_st.p += 1; + + Ok(()) + } +} + +downcast!(CallPolicy); + +pub(crate) struct DefaultCallPolicy {} + +impl CallPolicy for DefaultCallPolicy {} + +#[derive(Clone, Eq, PartialEq)] +struct InferenceLimit(BigUint); + +// ensure the heap behaves as a min-heap. +impl Ord for InferenceLimit { + fn cmp(&self, other: &InferenceLimit) -> Ordering { + other.0.cmp(&self.0) + } +} + +impl PartialOrd for InferenceLimit { + fn partial_cmp(&self, other: &InferenceLimit) -> Option { + Some(self.cmp(other)) + } +} + +pub(crate) struct CallWithInferenceLimitCallPolicy { + atom_tbl: TabledData, + pub(crate) prev_policy: Box, + count: BigUint, + limits: BinaryHeap +} + +impl CallWithInferenceLimitCallPolicy { + pub(crate) fn new_in_place(atom_tbl: TabledData, policy: &mut Box) + { + let mut prev_policy: Box = Box::new(DefaultCallPolicy {}); + swap(&mut prev_policy, policy); + + let new_policy = CallWithInferenceLimitCallPolicy { atom_tbl, prev_policy, + count: BigUint::zero(), + limits: BinaryHeap::new() }; + + *policy = Box::new(new_policy); + } + + fn increment(&mut self) -> CallResult { + if let Some(ref limit) = self.limits.peek() { + if self.count == limit.0 { + return Err(vec![heap_atom!("inference_limit_exceeded", self.atom_tbl)]) + } else { + self.count = BigUint::one() + &self.count; + } + } + + Ok(()) + } + + pub(crate) fn add_limit(&mut self, limit: Rc) { + match limit.to_biguint() { + Some(limit) => self.limits.push(InferenceLimit(limit + &self.count)), + _ => panic!("add_limit: expected unsigned integer.") + }; + } + + pub(crate) fn remove_limit(&mut self) -> Option { + self.limits.pop().map(|i| i.0 - &self.count) + } + + pub(crate) fn is_empty(&self) -> bool { + self.limits.is_empty() + } + + pub(crate) fn into_inner(&mut self) -> Box { + let mut new_inner: Box = Box::new(DefaultCallPolicy {}); + swap(&mut self.prev_policy, &mut new_inner); + new_inner + } +} + +impl CallPolicy for CallWithInferenceLimitCallPolicy { + fn try_call(&mut self, machine_st: &mut MachineState, code_dir: &CodeDir, + name: TabledRc, arity: usize) + -> CallResult + { + self.prev_policy.try_call(machine_st, code_dir, name, arity)?; + self.increment() + } + + fn try_execute(&mut self, machine_st: &mut MachineState, code_dir: &CodeDir, + name: TabledRc, arity: usize) + -> CallResult + { + self.prev_policy.try_execute(machine_st, code_dir, name, arity)?; + self.increment() + } + + fn retry_me_else(&mut self, machine_st: &mut MachineState, offset: usize) -> CallResult + { + self.prev_policy.retry_me_else(machine_st, offset)?; + self.increment() + } + + fn retry(&mut self, machine_st: &mut MachineState, offset: usize) -> CallResult + { + self.prev_policy.retry(machine_st, offset)?; + self.increment() + } + + fn trust_me(&mut self, machine_st: &mut MachineState) -> CallResult + { + self.prev_policy.trust_me(machine_st)?; + self.increment() + } + + fn trust(&mut self, machine_st: &mut MachineState, offset: usize) -> CallResult + { + self.prev_policy.trust(machine_st, offset)?; + self.increment() + } +} + pub(crate) trait CutPolicy: Any { fn cut(&mut self, &mut MachineState, RegType); } @@ -200,20 +489,20 @@ impl CutPolicy for DefaultCutPolicy { return; } - machine_st.p += 1; + machine_st.p += 1; } } pub(crate) struct SetupCallCleanupCutPolicy { // locations of cleaners, cut points, the previous block - cont_pts: Vec<(Addr, usize, usize)> + cont_pts: Vec<(Addr, usize, usize)> } impl SetupCallCleanupCutPolicy { pub(crate) fn new() -> Self { SetupCallCleanupCutPolicy { cont_pts: vec![] } } - + pub(crate) fn out_of_cont_pts(&self) -> bool { self.cont_pts.is_empty() } @@ -243,7 +532,7 @@ impl CutPolicy for SetupCallCleanupCutPolicy { } machine_st.p += 1; - + if !self.out_of_cont_pts() { machine_st.cp = machine_st.p; machine_st.num_of_args = 0; diff --git a/src/prolog/machine/machine_state_impl.rs b/src/prolog/machine/machine_state_impl.rs index 1e601f43..3288f361 100644 --- a/src/prolog/machine/machine_state_impl.rs +++ b/src/prolog/machine/machine_state_impl.rs @@ -185,7 +185,7 @@ impl MachineState { } } - fn unwind_trail(&mut self, a1: usize, a2: usize) { + pub(super) fn unwind_trail(&mut self, a1: usize, a2: usize) { for i in a1 .. a2 { match self.trail[i] { Ref::HeapCell(r) => @@ -932,36 +932,7 @@ impl MachineState { } } - fn try_call_predicate(&mut self, code_dir: &CodeDir, name: TabledRc, arity: usize) - { - let compiled_tl_index = code_dir.get(&(name, arity)).map(|index| index.1); - - match compiled_tl_index { - Some(compiled_tl_index) => { - self.cp = self.p + 1; - self.num_of_args = arity; - self.b0 = self.b; - self.p = CodePtr::DirEntry(compiled_tl_index); - }, - None => self.fail = true - }; - } - - fn try_execute_predicate(&mut self, code_dir: &CodeDir, name: TabledRc, arity: usize) - { - let compiled_tl_index = code_dir.get(&(name, arity)).map(|index| index.1); - - match compiled_tl_index { - Some(compiled_tl_index) => { - self.num_of_args = arity; - self.b0 = self.b; - self.p = CodePtr::DirEntry(compiled_tl_index); - }, - None => self.fail = true - }; - } - - fn handle_internal_call_n(&mut self, code_dir: &CodeDir) + fn handle_internal_call_n(&mut self, call_policy: &mut Box, code_dir: &CodeDir) { let arity = self.num_of_args + 1; let pred = self.registers[1].clone(); @@ -974,7 +945,7 @@ impl MachineState { self.registers[arity - 1] = pred; if let Some((name, arity)) = self.setup_call_n(arity - 1) { - self.try_execute_predicate(code_dir, name, arity); + try_or_fail!(self, call_policy.try_execute(self, code_dir, name, arity)); } } else { self.fail = true; @@ -1266,7 +1237,8 @@ impl MachineState { } pub(super) fn execute_built_in_instr(&mut self, code_dir: &CodeDir, - cut_policy: &mut Box, + call_policy: &mut Box, + cut_policy: &mut Box, instr: &BuiltInInstruction) { match instr { @@ -1276,12 +1248,21 @@ impl MachineState { self.compare_numbers(cmp, n1, n2); }, + &BuiltInInstruction::DefaultTrustMe => { + let mut call_policy = DefaultCallPolicy {}; + try_or_fail!(self, call_policy.trust_me(self)); + }, &BuiltInInstruction::DynamicCompareNumber(cmp) => { let n1 = try_or_fail!(self, self.arith_eval_by_metacall(temp_v!(1))); let n2 = try_or_fail!(self, self.arith_eval_by_metacall(temp_v!(2))); self.compare_numbers(cmp, n1, n2); }, + &BuiltInInstruction::EraseBall => { + self.ball.0 = 0; + self.ball.1.truncate(0); + self.p += 1; + }, &BuiltInInstruction::GetArgCall => try_or_fail!(self, { let val = self.try_get_arg(); @@ -1301,11 +1282,6 @@ impl MachineState { self.write_constant_to_var(addr, c); self.p += 1; }, - &BuiltInInstruction::EraseBall => { - self.ball.0 = 0; - self.ball.1.truncate(0); - self.p += 1; - }, &BuiltInInstruction::GetBall => { let addr = self.store(self.deref(self[temp_v!(1)].clone())); let h = self.heap.h; @@ -1333,6 +1309,24 @@ impl MachineState { self.p += 1; }, + &BuiltInInstruction::InferenceLevel => { // X1 = R, X2 = B. + let a1 = self[temp_v!(1)].clone(); + let a2 = self.store(self.deref(self[temp_v!(2)].clone())); + + match a2 { + Addr::Con(Constant::Usize(bp)) => + if self.b <= bp { + let a2 = Addr::Con(atom!("!", self.atom_tbl)); + self.unify(a1, a2); + } else { + let a2 = Addr::Con(atom!("true", self.atom_tbl)); + self.unify(a1, a2); + }, + _ => self.fail = true + }; + + self.p += 1; + }, &BuiltInInstruction::InstallCleaner => { let addr = self[temp_v!(1)].clone(); let b = self.b; @@ -1351,6 +1345,31 @@ SetupCallCleanupCutPolicy.") self.p += 1; }, + &BuiltInInstruction::InstallInferenceCounter(r) => { + let addr = self.store(self.deref(self[r].clone())); + + if call_policy.downcast_ref::().is_err() { + CallWithInferenceLimitCallPolicy::new_in_place(self.atom_tbl.clone(), call_policy); + } + + self.p += 1; + + match addr { + Addr::Con(Constant::Number(Number::Integer(n))) => + match call_policy.downcast_mut::().ok() { + Some(call_policy) => call_policy.add_limit(n), + None => panic!("install_inference_counter: should have installed \\ + CallWithInferenceLimitCallPolicy.") + }, + _ => { + let atom_tbl = self.atom_tbl.clone(); + self.throw_exception(functor!(atom_tbl, + "type_error", + 1, + [heap_atom!("integer_expected", atom_tbl)])) + } + }; + }, &BuiltInInstruction::IsAtomic(r) => { let d = self.store(self.deref(self[r].clone())); @@ -1415,6 +1434,33 @@ SetupCallCleanupCutPolicy.") _ => self.fail = true }; }, + &BuiltInInstruction::RemoveInferenceCounter(r) => { + let restore_default = + match call_policy.downcast_mut::().ok() { + Some(call_policy) => { + if let Some(diff) = call_policy.remove_limit() { + let addr = self[r].clone(); + self.unify(addr, Addr::Con(integer!(diff))); + } else { + panic!("remove_inference_counters: no limit found."); + } + + if call_policy.is_empty() { + Some(call_policy.into_inner()) + } else { + None + } + }, + None => panic!("remove_inference_counters: requires \\ + CallWithInferenceLimitCallPolicy.") + }; + + if let Some(new_policy) = restore_default { + *call_policy = new_policy; + } + + self.p += 1; + }, &BuiltInInstruction::RestoreCutPolicy => { let restore_default = if let Ok(cut_policy) = cut_policy.downcast_ref::() { @@ -1492,7 +1538,7 @@ SetupCallCleanupCutPolicy.") self.fail = true; }, &BuiltInInstruction::InternalCallN => - self.handle_internal_call_n(code_dir), + self.handle_internal_call_n(call_policy, code_dir), &BuiltInInstruction::Fail => { self.fail = true; self.p += 1; @@ -1683,7 +1729,9 @@ SetupCallCleanupCutPolicy.") false } - pub(super) fn execute_ctrl_instr(&mut self, code_dir: &CodeDir, cut_policy: &mut Box, + pub(super) fn execute_ctrl_instr(&mut self, code_dir: &CodeDir, + call_policy: &mut Box, + cut_policy: &mut Box, instr: &ControlInstruction) { match instr { @@ -1728,7 +1776,7 @@ SetupCallCleanupCutPolicy.") self.p = CodePtr::DirEntry(150); }, &ControlInstruction::Call(ref name, arity, _) => - self.try_call_predicate(code_dir, name.clone(), arity), + try_or_fail!(self, call_policy.try_call(self, code_dir, name.clone(), arity)), &ControlInstruction::CatchCall => { self.cp = self.p + 1; self.num_of_args = 3; @@ -1742,7 +1790,7 @@ SetupCallCleanupCutPolicy.") }, &ControlInstruction::CallN(arity) => if let Some((name, arity)) = self.setup_call_n(arity) { - self.try_call_predicate(code_dir, name, arity); + try_or_fail!(self, call_policy.try_call(self, code_dir, name, arity)) }, &ControlInstruction::CheckCpExecute => { let a = self.store(self.deref(self[temp_v!(2)].clone())); @@ -1838,10 +1886,10 @@ SetupCallCleanupCutPolicy.") self.p = self.cp; }, &ControlInstruction::Execute(ref name, arity) => - self.try_execute_predicate(code_dir, name.clone(), arity), + try_or_fail!(self, call_policy.try_execute(self, code_dir, name.clone(), arity)), &ControlInstruction::ExecuteN(arity) => if let Some((name, arity)) = self.setup_call_n(arity) { - self.try_execute_predicate(code_dir, name, arity); + try_or_fail!(self, call_policy.try_execute(self, code_dir, name, arity)) }, &ControlInstruction::FunctorCall => try_or_fail!(self, { @@ -1936,7 +1984,8 @@ SetupCallCleanupCutPolicy.") }; } - pub(super) fn execute_indexed_choice_instr(&mut self, instr: &IndexedChoiceInstruction) + pub(super) fn execute_indexed_choice_instr(&mut self, instr: &IndexedChoiceInstruction, + call_policy: &mut Box) { match instr { &IndexedChoiceInstruction::Try(l) => { @@ -1963,63 +2012,15 @@ SetupCallCleanupCutPolicy.") self.hb = self.heap.h; self.p += l; }, - &IndexedChoiceInstruction::Retry(l) => { - let b = self.b - 1; - let n = self.or_stack[b].num_args(); - - for i in 1 .. n + 1 { - self.registers[i] = self.or_stack[b][i].clone(); - } - - self.e = self.or_stack[b].e; - self.cp = self.or_stack[b].cp; - - self.or_stack[b].bp = self.p + 1; - - let old_tr = self.or_stack[b].tr; - let curr_tr = self.tr; - - self.unwind_trail(old_tr, curr_tr); - self.tr = self.or_stack[b].tr; - - self.trail.truncate(self.tr); - self.heap.truncate(self.or_stack[b].h); - - self.hb = self.heap.h; - - self.p += l; - }, - &IndexedChoiceInstruction::Trust(l) => { - let b = self.b - 1; - let n = self.or_stack[b].num_args(); - - for i in 1 .. n + 1 { - self.registers[i] = self.or_stack[b][i].clone(); - } - - self.e = self.or_stack[b].e; - self.cp = self.or_stack[b].cp; - - let old_tr = self.or_stack[b].tr; - let curr_tr = self.tr; - - self.unwind_trail(old_tr, curr_tr); - - self.tr = self.or_stack[b].tr; - self.trail.truncate(self.tr); - - self.heap.truncate(self.or_stack[b].h); - self.b = self.or_stack[b].b; - - self.or_stack.truncate(self.b); - - self.hb = self.heap.h; - self.p += l; - }, + &IndexedChoiceInstruction::Retry(l) => + try_or_fail!(self, call_policy.retry(self, l)), + &IndexedChoiceInstruction::Trust(l) => + try_or_fail!(self, call_policy.trust(self, l)) }; } - pub(super) fn execute_choice_instr(&mut self, instr: &ChoiceInstruction) + pub(super) fn execute_choice_instr(&mut self, instr: &ChoiceInstruction, + call_policy: &mut Box) { match instr { &ChoiceInstruction::TryMeElse(offset) => { @@ -2046,60 +2047,10 @@ SetupCallCleanupCutPolicy.") self.hb = self.heap.h; self.p += 1; }, - &ChoiceInstruction::RetryMeElse(offset) => { - let b = self.b - 1; - let n = self.or_stack[b].num_args(); - - for i in 1 .. n + 1 { - self.registers[i] = self.or_stack[b][i].clone(); - } - - self.e = self.or_stack[b].e; - self.cp = self.or_stack[b].cp; - - self.or_stack[b].bp = self.p + offset; - - let old_tr = self.or_stack[b].tr; - let curr_tr = self.tr; - - self.unwind_trail(old_tr, curr_tr); - self.tr = self.or_stack[b].tr; - - self.trail.truncate(self.tr); - self.heap.truncate(self.or_stack[b].h); - - self.hb = self.heap.h; - - self.p += 1; - }, - &ChoiceInstruction::TrustMe => { - let b = self.b - 1; - let n = self.or_stack[b].num_args(); - - for i in 1 .. n + 1 { - self.registers[i] = self.or_stack[b][i].clone(); - } - - self.e = self.or_stack[b].e; - self.cp = self.or_stack[b].cp; - - let old_tr = self.or_stack[b].tr; - let curr_tr = self.tr; - - self.unwind_trail(old_tr, curr_tr); - - self.tr = self.or_stack[b].tr; - self.trail.truncate(self.tr); - - self.heap.truncate(self.or_stack[b].h); - - self.b = self.or_stack[b].b; - - self.or_stack.truncate(self.b); - - self.hb = self.heap.h; - self.p += 1; - } + &ChoiceInstruction::RetryMeElse(offset) => + try_or_fail!(self, call_policy.retry_me_else(self, offset)), + &ChoiceInstruction::TrustMe => + try_or_fail!(self, call_policy.trust_me(self)) } } diff --git a/src/prolog/machine/mod.rs b/src/prolog/machine/mod.rs index 9ac9d915..e6b9da46 100644 --- a/src/prolog/machine/mod.rs +++ b/src/prolog/machine/mod.rs @@ -19,6 +19,7 @@ use std::rc::Rc; pub struct Machine { ms: MachineState, + call_policy: Box, cut_policy: Box, code: Code, code_dir: CodeDir, @@ -47,9 +48,9 @@ impl Machine { let atom_tbl = Rc::new(RefCell::new(HashSet::new())); let (code, code_dir, op_dir) = build_code_dir(atom_tbl.clone()); - Machine { ms: MachineState::new(atom_tbl), + call_policy: Box::new(DefaultCallPolicy {}), cut_policy: Box::new(DefaultCutPolicy {}), code, code_dir, @@ -106,13 +107,15 @@ impl Machine { &Line::Arithmetic(ref arith_instr) => self.ms.execute_arith_instr(arith_instr), &Line::BuiltIn(ref built_in_instr) => - self.ms.execute_built_in_instr(&self.code_dir, &mut self.cut_policy, built_in_instr), + self.ms.execute_built_in_instr(&self.code_dir, &mut self.call_policy, + &mut self.cut_policy, built_in_instr), &Line::Choice(ref choice_instr) => - self.ms.execute_choice_instr(choice_instr), + self.ms.execute_choice_instr(choice_instr, &mut self.call_policy), &Line::Cut(ref cut_instr) => self.ms.execute_cut_instr(cut_instr, &mut self.cut_policy), &Line::Control(ref control_instr) => - self.ms.execute_ctrl_instr(&self.code_dir, &mut self.cut_policy, control_instr), + self.ms.execute_ctrl_instr(&self.code_dir, &mut self.call_policy, + &mut self.cut_policy, control_instr), &Line::Fact(ref fact) => { for fact_instr in fact { if self.failed() { @@ -127,7 +130,7 @@ impl Machine { &Line::Indexing(ref indexing_instr) => self.ms.execute_indexing_instr(&indexing_instr), &Line::IndexedChoice(ref choice_instr) => - self.ms.execute_indexed_choice_instr(choice_instr), + self.ms.execute_indexed_choice_instr(choice_instr, &mut self.call_policy), &Line::Query(ref query) => { for query_instr in query { if self.failed() { diff --git a/src/prolog/macros.rs b/src/prolog/macros.rs index d4291667..c1c495ec 100644 --- a/src/prolog/macros.rs +++ b/src/prolog/macros.rs @@ -622,3 +622,27 @@ macro_rules! term_cmp_eq { CompareTermQT::Equal ) } + +macro_rules! install_inference_counter { + ($r:expr) => ( + Line::BuiltIn(BuiltInInstruction::InstallInferenceCounter($r)) + ) +} + +macro_rules! remove_inference_counter { + ($r:expr) => ( + Line::BuiltIn(BuiltInInstruction::RemoveInferenceCounter($r)) + ) +} + +macro_rules! inference_level { + () => ( + Line::BuiltIn(BuiltInInstruction::InferenceLevel) + ) +} + +macro_rules! default_trust_me { + () => ( + Line::BuiltIn(BuiltInInstruction::DefaultTrustMe) + ) +} diff --git a/src/prolog/parser b/src/prolog/parser index 5cd21c56..74bb1031 160000 --- a/src/prolog/parser +++ b/src/prolog/parser @@ -1 +1 @@ -Subproject commit 5cd21c56d516f934d89b40935487cfda8ad903b4 +Subproject commit 74bb1031f54631bae14aee7d8814c33573e7171d -- 2.54.0