From 1a0f50200fa53952c73f3f7b8fc1d61f98ddf7f4 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Mon, 7 May 2018 22:27:58 -0600 Subject: [PATCH] system calls preliminary --- src/prolog/ast.rs | 43 ++++-- src/prolog/builtins.rs | 2 - src/prolog/machine/machine_state.rs | 24 ++-- src/prolog/machine/machine_state_impl.rs | 169 ++--------------------- src/prolog/machine/mod.rs | 1 + 5 files changed, 52 insertions(+), 187 deletions(-) diff --git a/src/prolog/ast.rs b/src/prolog/ast.rs index af5e319b..d3dcfc2c 100644 --- a/src/prolog/ast.rs +++ b/src/prolog/ast.rs @@ -683,6 +683,26 @@ pub struct Rule { pub clauses: Vec } +#[derive(Clone)] +pub enum SystemClauseType { + SkipMaxList +} + +impl SystemClauseType { + pub fn name(&self) -> ClauseName { + match self { + &SystemClauseType::SkipMaxList => clause_name!("$skip_max_list"), + } + } + + pub fn from(name: &str, arity: usize) -> Option { + match (name, arity) { + ("$skip_max_list", 4) => Some(SystemClauseType::SkipMaxList), + _ => None + } + } +} + #[derive(Clone)] pub enum ClauseType { AcyclicTerm, @@ -705,8 +725,8 @@ pub enum ClauseType { Op(ClauseName, Fixity, CodeIndex), Named(ClauseName, CodeIndex), SetupCallCleanup, - SkipMaxList, Sort, + System(SystemClauseType), Throw, } @@ -788,14 +808,14 @@ impl ClauseType { pub fn name(&self) -> ClauseName { match self { - &ClauseType::AcyclicTerm => clause_name!("acyclic_term"), + &ClauseType::AcyclicTerm => clause_name!("$acyclic_term"), &ClauseType::Arg => clause_name!("arg"), &ClauseType::CallN => clause_name!("call"), &ClauseType::CallWithInferenceLimit => clause_name!("call_with_inference_limit"), &ClauseType::Catch => clause_name!("catch"), &ClauseType::Compare => clause_name!("compare"), &ClauseType::CompareTerm(qt) => clause_name!(qt.name()), - &ClauseType::CyclicTerm => clause_name!("cyclic_term"), + &ClauseType::CyclicTerm => clause_name!("$cyclic_term"), &ClauseType::Display => clause_name!("display"), &ClauseType::DuplicateTerm => clause_name!("duplicate_term"), &ClauseType::Eq => clause_name!("=="), @@ -803,26 +823,26 @@ impl ClauseType { &ClauseType::Ground => clause_name!("ground"), &ClauseType::Inlined(inlined) => clause_name!(inlined.name()), &ClauseType::Is => clause_name!("is"), - &ClauseType::KeySort => clause_name!("keysort"), + &ClauseType::KeySort => clause_name!("$keysort"), &ClauseType::NotEq => clause_name!("\\=="), &ClauseType::Op(ref name, ..) => name.clone(), &ClauseType::Named(ref name, ..) => name.clone(), &ClauseType::SetupCallCleanup => clause_name!("setup_call_cleanup"), - &ClauseType::SkipMaxList => clause_name!("$skip_max_list"), - &ClauseType::Sort => clause_name!("sort"), + &ClauseType::System(ref system) => system.name(), + &ClauseType::Sort => clause_name!("$sort"), &ClauseType::Throw => clause_name!("throw") } } pub fn from(name: ClauseName, arity: usize, fixity: Option) -> Self { match (name.as_str(), arity) { - ("acyclic_term", 1) => ClauseType::AcyclicTerm, + ("$acyclic_term", 1) => ClauseType::AcyclicTerm, ("arg", 3) => ClauseType::Arg, ("call", _) => ClauseType::CallN, ("call_with_inference_limit", 3) => ClauseType::CallWithInferenceLimit, ("catch", 3) => ClauseType::Catch, ("compare", 3) => ClauseType::Compare, - ("cyclic_term", 1) => ClauseType::CyclicTerm, + ("$cyclic_term", 1) => ClauseType::CyclicTerm, ("@>", 2) => ClauseType::CompareTerm(CompareTermQT::GreaterThan), ("@<", 2) => ClauseType::CompareTerm(CompareTermQT::LessThan), ("@>=", 2) => ClauseType::CompareTerm(CompareTermQT::GreaterThanOrEqual), @@ -835,11 +855,10 @@ impl ClauseType { ("functor", 3) => ClauseType::Functor, ("ground", 1) => ClauseType::Ground, ("is", 2) => ClauseType::Is, - ("keysort", 2) => ClauseType::KeySort, + ("$keysort", 2) => ClauseType::KeySort, ("\\==", 2) => ClauseType::NotEq, - ("setup_call_cleanup", 3) => ClauseType::SetupCallCleanup, - ("$skip_max_list", 4) => ClauseType::SkipMaxList, - ("sort", 2) => ClauseType::Sort, + ("setup_call_cleanup", 3) => ClauseType::SetupCallCleanup, + ("$sort", 2) => ClauseType::Sort, ("throw", 1) => ClauseType::Throw, _ => if let Some(fixity) = fixity { ClauseType::Op(name, fixity, CodeIndex::default()) diff --git a/src/prolog/builtins.rs b/src/prolog/builtins.rs index f23694f6..6633904c 100644 --- a/src/prolog/builtins.rs +++ b/src/prolog/builtins.rs @@ -736,7 +736,6 @@ fn get_builtins() -> Code { keysort_execute!(), // keysort/2, 484. acyclic_term_execute!(), // acyclic_term/1, 485. cyclic_term_execute!(), // cyclic_term/1, 486. - skip_max_list_execute!() // '$skip_max_list', 487. ] } @@ -856,7 +855,6 @@ pub fn build_code_and_op_dirs() -> (CodeDir, OpDir) code_dir.insert((clause_name!("keysort"), 2), CodeIndex::from((484, builtin.clone()))); code_dir.insert((clause_name!("acyclic_term"), 1), CodeIndex::from((485, builtin.clone()))); code_dir.insert((clause_name!("cyclic_term"), 1), CodeIndex::from((486, builtin.clone()))); - code_dir.insert((clause_name!("$skip_max_list"), 4), CodeIndex::from((487, builtin.clone()))); (code_dir, op_dir) } diff --git a/src/prolog/machine/machine_state.rs b/src/prolog/machine/machine_state.rs index c5f10f98..90b80afc 100644 --- a/src/prolog/machine/machine_state.rs +++ b/src/prolog/machine/machine_state.rs @@ -17,14 +17,14 @@ use std::rc::Rc; pub(super) struct Ball { pub(super) boundary: usize, // ball.0 - pub(super) stub: MachineStub, // ball.1 + pub(super) stub: MachineStub, // ball.1 } impl Ball { pub(super) fn new() -> Self { Ball { boundary: 0, stub: MachineStub::new() } } - + pub(super) fn reset(&mut self) { self.boundary = 0; self.stub.clear(); @@ -502,10 +502,10 @@ pub(crate) trait CallPolicy: Any { }, &ClauseType::Sort => { machine_st.check_sort_errors()?; - + let stub = machine_st.functor_stub(clause_name!("sort"), 2); - let mut list = machine_st.try_from_list(temp_v!(1), stub)?; - + let mut list = machine_st.try_from_list(temp_v!(1), stub)?; + list.sort_unstable_by(|a1, a2| machine_st.compare_term_test(a1, a2)); machine_st.term_dedup(&mut list); @@ -518,11 +518,11 @@ pub(crate) trait CallPolicy: Any { }, &ClauseType::KeySort => { machine_st.check_keysort_errors()?; - + let stub = machine_st.functor_stub(clause_name!("keysort"), 2); let mut list = machine_st.try_from_list(temp_v!(1), stub)?; - let mut key_pairs = Vec::new(); - + let mut key_pairs = Vec::new(); + for val in list { let key = machine_st.project_onto_key(val.clone())?; key_pairs.push((key, val.clone())); @@ -569,11 +569,9 @@ pub(crate) trait CallPolicy: Any { machine_st.execute_inlined(inlined, &vec![temp_v!(1), temp_v!(2)]); Ok(()) }, - &ClauseType::SkipMaxList => { - machine_st.skip_max_list()?; - machine_st.p += 1; - - Ok(()) + &ClauseType::System(ref system) => { + machine_st.execute_system(system)?; + return_from_clause!(lco, machine_st) } } } diff --git a/src/prolog/machine/machine_state_impl.rs b/src/prolog/machine/machine_state_impl.rs index 2392741d..35534955 100644 --- a/src/prolog/machine/machine_state_impl.rs +++ b/src/prolog/machine/machine_state_impl.rs @@ -100,12 +100,12 @@ impl MachineState { where Fmt: HCValueFormatter, Outputter: HCValueOutputter { let orig_len = output.len(); - + output.begin_new_var(); output.append(var.as_str()); output.append(" = "); - + let printer = HCPrinter::from_heap_locs(&self, fmt, output, var_dir); let mut output = printer.print(addr); @@ -125,7 +125,7 @@ impl MachineState { let printer = HCPrinter::from_heap_locs_as_seen(&self, fmt, output, var_dir); printer.print(addr) } - + pub(super) fn print_term(&self, addr: Addr, fmt: Fmt, output: Outputter) -> Outputter where Fmt: HCValueFormatter, Outputter: HCValueOutputter @@ -1106,10 +1106,10 @@ impl MachineState { self.heap.h - self.ball.boundary } } - + pub(super) fn copy_and_align_ball_to_heap(&mut self) -> usize { let diff = self.heap_ball_boundary_diff(); - + for heap_value in self.ball.stub.iter().cloned() { self.heap.push(match heap_value { HeapCellValue::Addr(addr) => HeapCellValue::Addr(addr - diff), @@ -1186,7 +1186,7 @@ impl MachineState { self.p += 1; } - + pub(super) fn compare_term(&mut self, qt: CompareTermQT) { let a1 = self[temp_v!(1)].clone(); let a2 = self[temp_v!(2)].clone(); @@ -1441,7 +1441,7 @@ impl MachineState { try_or_fail!(self, call_policy.trust_me(self)); }, &BuiltInInstruction::EraseBall => { - self.ball.reset(); + self.ball.reset(); self.p += 1; }, &BuiltInInstruction::GetArg(lco) => @@ -1621,7 +1621,7 @@ impl MachineState { let mut duplicator = DuplicateBallTerm::new(self); duplicator.duplicate_term(addr); }; - + self.p += 1; }, &BuiltInInstruction::SetCutPoint(r) => @@ -1841,157 +1841,6 @@ impl MachineState { } } - pub(super) fn detect_cycles_with_max(&self, max_steps: usize, addr: Addr) -> CycleSearchResult - { - let addr = self.store(self.deref(addr)); - - let mut hare = match addr { - Addr::Lis(offset) if max_steps > 0 => offset + 1, - Addr::Lis(offset) => return CycleSearchResult::UntouchedList(offset), - Addr::Con(Constant::EmptyList) => return CycleSearchResult::EmptyList, - _ => return CycleSearchResult::NotList - }; - - // use Brent's algorithm to detect cycles. - let mut tortoise = hare; - let mut power = 2; - let mut steps = 1; - - loop { - if steps == max_steps { - return CycleSearchResult::PartialList(steps, hare); - } - - match self.heap[hare].clone() { - HeapCellValue::Addr(Addr::Lis(l)) => { - hare = l + 1; - steps += 1; - - if tortoise == hare { - return CycleSearchResult::NotList; - } else if steps == power { - tortoise = hare; - power <<= 1; - } - }, - HeapCellValue::NamedStr(..) => - return CycleSearchResult::NotList, - HeapCellValue::Addr(addr) => - match self.store(self.deref(addr)) { - Addr::Con(Constant::EmptyList) => - return CycleSearchResult::ProperList(steps), - Addr::HeapCell(_) | Addr::StackCell(..) => - return CycleSearchResult::PartialList(steps, hare), - _ => - return CycleSearchResult::NotList - } - } - } - } - - pub(super) fn detect_cycles(&self, addr: Addr) -> CycleSearchResult - { - let addr = self.store(self.deref(addr)); - - let mut hare = match addr { - Addr::Lis(offset) => offset + 1, - Addr::Con(Constant::EmptyList) => return CycleSearchResult::EmptyList, - _ => return CycleSearchResult::NotList - }; - - // use Brent's algorithm to detect cycles. - let mut tortoise = hare; - let mut power = 2; - let mut steps = 1; - - loop { - match self.heap[hare].clone() { - HeapCellValue::Addr(Addr::Lis(l)) => { - hare = l + 1; - steps += 1; - - if tortoise == hare { - return CycleSearchResult::NotList; - } else if steps == power { - tortoise = hare; - power <<= 1; - } - }, - HeapCellValue::NamedStr(..) => - return CycleSearchResult::NotList, - HeapCellValue::Addr(addr) => - match self.store(self.deref(addr)) { - Addr::Con(Constant::EmptyList) => - return CycleSearchResult::ProperList(steps), - Addr::HeapCell(_) | Addr::StackCell(..) => - return CycleSearchResult::PartialList(steps, hare), - _ => - return CycleSearchResult::NotList - } - } - } - } - - fn finalize_skip_max_list(&mut self, n: usize, addr: Addr) { - let target_n = self[temp_v!(1)].clone(); - self.unify(Addr::Con(integer!(n)), target_n); - - if !self.fail { - let xs = self[temp_v!(4)].clone(); - self.unify(addr, xs); - } - } - - pub(super) fn skip_max_list(&mut self) -> Result<(), MachineError> { - let max_steps = self.arith_eval_by_metacall(temp_v!(2))?; - - match max_steps { - Number::Integer(ref max_steps) - if max_steps.to_isize().map(|i| i >= -1).unwrap_or(false) => { - let n = self.store(self.deref(self[temp_v!(1)].clone())); - - match n { - Addr::Con(Constant::Number(Number::Integer(ref n))) if n.is_zero() => { - let xs0 = self[temp_v!(3)].clone(); - let xs = self[temp_v!(4)].clone(); - - self.unify(xs0, xs); - }, - _ => { - let search_result = if let Some(max_steps) = max_steps.to_isize() { - if max_steps == -1 { - self.detect_cycles(self[temp_v!(3)].clone()) - } else { - self.detect_cycles_with_max(max_steps as usize, - self[temp_v!(3)].clone()) - } - } else { - self.detect_cycles(self[temp_v!(3)].clone()) - }; - - match search_result { - CycleSearchResult::UntouchedList(l) => - self.finalize_skip_max_list(0, Addr::Lis(l)), - CycleSearchResult::EmptyList => - self.finalize_skip_max_list(0, Addr::Con(Constant::EmptyList)), - CycleSearchResult::PartialList(n, hc) => - self.finalize_skip_max_list(n, Addr::HeapCell(hc)), - CycleSearchResult::ProperList(n) => - self.finalize_skip_max_list(n, Addr::Con(Constant::EmptyList)), - CycleSearchResult::NotList => { - let xs0 = self[temp_v!(3)].clone(); - self.finalize_skip_max_list(0, xs0); - } - } - } - } - }, - _ => self.fail = true - }; - - Ok(()) - } - pub(super) fn duplicate_term(&mut self) { let old_h = self.heap.h; @@ -2330,7 +2179,7 @@ impl MachineState { self.or_stack.clear(); self.registers = vec![Addr::HeapCell(0); 64]; self.block = 0; - + self.ball.reset(); } } diff --git a/src/prolog/machine/mod.rs b/src/prolog/machine/mod.rs index f2a4ad81..5df7085c 100644 --- a/src/prolog/machine/mod.rs +++ b/src/prolog/machine/mod.rs @@ -7,6 +7,7 @@ mod machine_errors; pub(super) mod machine_state; #[macro_use] mod machine_state_impl; +mod system_calls; use prolog::machine::machine_state::*; -- 2.54.0