From 657e4f12bbeaf3af40959cae3b88af60f59d3c7c Mon Sep 17 00:00:00 2001 From: notoria Date: Sat, 19 Dec 2020 14:52:38 +0100 Subject: [PATCH] Implemented a different way to index clauses --- src/codegen.rs | 96 ++++++++++++++++++++++++------- src/forms.rs | 13 +++++ src/indexing.rs | 31 +++++++--- src/instructions.rs | 22 ++++--- src/machine/machine_state_impl.rs | 12 ++-- src/write.rs | 8 +-- 6 files changed, 136 insertions(+), 46 deletions(-) diff --git a/src/codegen.rs b/src/codegen.rs index a1811985..56128edc 100644 --- a/src/codegen.rs +++ b/src/codegen.rs @@ -857,21 +857,28 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { Ok(code) } - fn split_predicate(clauses: &Vec) -> Vec<(usize, usize)> { + fn split_predicate(clauses: &Vec, optimal_index: Option) -> Vec<(usize, usize)> { let mut subseqs = Vec::new(); let mut left_index = 0; - for (right_index, clause) in clauses.iter().enumerate() { - match clause.first_arg() { - Some(&Term::Var(_, _)) | Some(&Term::AnonVar) => { - if left_index < right_index { - subseqs.push((left_index, right_index)); + if let Some(optimal_i) = optimal_index { + for (right_index, clause) in clauses.iter().enumerate() { + if clause.args().is_none() { + continue; + } + if let Some(arg) = clause.args().unwrap().iter().nth(optimal_i) { + match **arg { + Term::Var(..) | Term::AnonVar => { + if left_index < right_index { + subseqs.push((left_index, right_index)); + } + + subseqs.push((right_index, right_index + 1)); + left_index = right_index + 1; + } + _ => (), } - - subseqs.push((right_index, right_index + 1)); - left_index = right_index + 1; } - _ => {} } } @@ -901,6 +908,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { fn compile_pred_subseq<'b: 'a>( &mut self, clauses: &'b [PredicateClause], + optimal_index: Option, ) -> Result { let mut code_body = Vec::new(); let mut code_offsets = CodeOffsets::new(); @@ -910,9 +918,9 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { for (i, clause) in clauses.iter().enumerate() { self.marker.reset(); - let mut clause_code = match clause { - &PredicateClause::Fact(ref fact, ..) => self.compile_fact(fact), - &PredicateClause::Rule(ref rule, ..) => self.compile_rule(rule)?, + let mut clause_code = match *clause { + PredicateClause::Fact(ref fact, ..) => self.compile_fact(fact), + PredicateClause::Rule(ref rule, ..) => self.compile_rule(rule)?, }; if num_clauses > 1 { @@ -925,17 +933,28 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { code_body.push(Line::Choice(choice)); } - clause.first_arg().map(|arg| { - let index = code_body.len(); - code_offsets.index_term(arg, index); - }); + if let Some(optimal_i) = optimal_index { + let arg = match clause.args() { + Some(args) => match args.iter().nth(optimal_i) { + Some(term) => Some(term), + None => None, + }, + None => None, + }; + if let Some(arg) = arg { + let index = code_body.len(); + code_offsets.index_term(arg, index); + } + } code_body.append(&mut clause_code); } let mut code = Vec::new(); - code_offsets.add_indices(&mut code, code_body); + if let Some(optimal_i) = optimal_index { + code_offsets.add_indices(&mut code, code_body, optimal_i + 1); + } Ok(code) } @@ -944,11 +963,48 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { clauses: &'b Vec, ) -> Result { let mut code = Vec::new(); - let split_pred = Self::split_predicate(&clauses); + let mut optimal_index = None; + let has_args = match clauses.first() { + Some(clause) => match clause.args() { + Some(args) => !args.is_empty(), + None => false, + }, + None => false, + }; + if has_args { + for clause in clauses.iter() { + let args = clause.args().unwrap(); + for (i, arg) in args.iter().enumerate() { + if let Some(optimal_index) = optimal_index { + if i >= optimal_index { + break; + } + } + match **arg { + Term::AnonVar | Term::Var(..) => (), + _ => { + match optimal_index { + Some(ref mut optimal_i) => *optimal_i = i, + None => optimal_index = Some(i), + } + break; + } + } + } + } + } + match optimal_index { + // No good index or no argument, default to 0. + // TODO: Why? + None => optimal_index = Some(0), + Some(_) => (), + } + let split_pred = Self::split_predicate(&clauses, optimal_index); let multi_seq = split_pred.len() > 1; for (l, r) in split_pred { - let mut code_segment = self.compile_pred_subseq(&clauses[l..r])?; + let mut code_segment = + self.compile_pred_subseq(&clauses[l..r], optimal_index)?; if multi_seq { let choice = match l { diff --git a/src/forms.rs b/src/forms.rs index 499ee875..5a7fcd2b 100644 --- a/src/forms.rs +++ b/src/forms.rs @@ -339,6 +339,19 @@ impl PredicateClause { } } + // TODO: add this to `Term` in `prolog_parser` like `first_arg`. + pub fn args(&self) -> Option<&[Box]> { + match *self { + PredicateClause::Fact(ref term, ..) => { + match term { + Term::Clause(_, _, args, _) => Some(&args), + _ => None, + } + }, + PredicateClause::Rule(ref rule, ..) => Some(&rule.head.1), + } + } + pub fn arity(&self) -> usize { match self { &PredicateClause::Fact(ref term, ..) => { diff --git a/src/indexing.rs b/src/indexing.rs index b93b3c93..ccd63717 100644 --- a/src/indexing.rs +++ b/src/indexing.rs @@ -237,12 +237,17 @@ impl CodeOffsets { fn switch_on_constant( con_ind: IndexMap, prelude: &mut CodeDeque, + optimal_index: usize, ) -> IntIndex { let con_ind = Self::second_level_index(con_ind, prelude); if con_ind.len() > 1 { let index = Self::flatten_index(con_ind, prelude.len()); - let instr = IndexingInstruction::SwitchOnConstant(index.len(), index); + let instr = IndexingInstruction::SwitchOnConstant( + optimal_index, + index.len(), + index + ); prelude.push_front(Line::from(instr)); @@ -259,12 +264,17 @@ impl CodeOffsets { fn switch_on_structure( str_ind: IndexMap<(ClauseName, usize), ThirdLevelIndex>, prelude: &mut CodeDeque, + optimal_index: usize, ) -> IntIndex { let str_ind = Self::second_level_index(str_ind, prelude); if str_ind.len() > 1 { let index = Self::flatten_index(str_ind, prelude.len()); - let instr = IndexingInstruction::SwitchOnStructure(index.len(), index); + let instr = IndexingInstruction::SwitchOnStructure( + optimal_index, + index.len(), + index + ); prelude.push_front(Line::from(instr)); @@ -325,7 +335,7 @@ impl CodeOffsets { } } - pub fn add_indices(self, code: &mut Code, mut code_body: Code) { + pub fn add_indices(self, code: &mut Code, mut code_body: Code, optimal_index: usize) { if self.no_indices() { *code = code_body; return; @@ -334,8 +344,10 @@ impl CodeOffsets { let mut prelude = VecDeque::new(); let lst_loc = Self::switch_on_list(self.lists, &mut prelude); - let str_loc = Self::switch_on_structure(self.structures, &mut prelude); - let con_loc = Self::switch_on_constant(self.constants, &mut prelude); + let str_loc = + Self::switch_on_structure(self.structures, &mut prelude, optimal_index); + let con_loc = + Self::switch_on_constant(self.constants, &mut prelude, optimal_index); let prelude_length = prelude.len(); @@ -355,8 +367,13 @@ impl CodeOffsets { let con_loc = Self::switch_on_con_offset_from(con_loc, prelude.len()); let lst_loc = Self::switch_on_lst_offset_from(lst_loc, prelude.len()); - let switch_instr = - IndexingInstruction::SwitchOnTerm(prelude.len() + 1, con_loc, lst_loc, str_loc); + let switch_instr = IndexingInstruction::SwitchOnTerm( + optimal_index, + prelude.len() + 1, + con_loc, + lst_loc, + str_loc + ); prelude.push_front(Line::from(switch_instr)); diff --git a/src/instructions.rs b/src/instructions.rs index 33997018..c3de3469 100644 --- a/src/instructions.rs +++ b/src/instructions.rs @@ -143,6 +143,7 @@ impl IndexedChoiceInstruction { } } +/// A `Line` is an instruction (cf. page 98 of wambook). #[derive(Debug)] pub enum Line { Arithmetic(ArithmeticInstruction), @@ -424,11 +425,13 @@ impl ControlInstruction { } } +/// `IndexingInstruction` cf. page 110 of wambook. #[derive(Debug)] pub enum IndexingInstruction { - SwitchOnTerm(usize, usize, usize, usize), - SwitchOnConstant(usize, IndexMap), - SwitchOnStructure(usize, IndexMap<(ClauseName, usize), usize>), + // The first index is the optimal argument being indexed. + SwitchOnTerm(usize, usize, usize, usize, usize), + SwitchOnConstant(usize, usize, IndexMap), + SwitchOnStructure(usize, usize, IndexMap<(ClauseName, usize), usize>), } impl From for Line { @@ -440,25 +443,26 @@ impl From for Line { impl IndexingInstruction { pub fn to_functor(&self) -> MachineStub { match self { - &IndexingInstruction::SwitchOnTerm(vars, constants, lists, structures) => { + &IndexingInstruction::SwitchOnTerm(arg, vars, constants, lists, structures) => { functor!( "switch_on_term", - [integer(vars), + [integer(arg), + integer(vars), integer(constants), integer(lists), integer(structures)] ) } - &IndexingInstruction::SwitchOnConstant(constants, _) => { + &IndexingInstruction::SwitchOnConstant(arg, constants, _) => { functor!( "switch_on_constant", - [integer(constants)] + [integer(arg), integer(constants)] ) } - &IndexingInstruction::SwitchOnStructure(structures, _) => { + &IndexingInstruction::SwitchOnStructure(arg, structures, _) => { functor!( "switch_on_structure", - [integer(structures)] + [integer(arg), integer(structures)] ) } } diff --git a/src/machine/machine_state_impl.rs b/src/machine/machine_state_impl.rs index 849e18f5..0e4a4e1c 100644 --- a/src/machine/machine_state_impl.rs +++ b/src/machine/machine_state_impl.rs @@ -1392,8 +1392,8 @@ impl MachineState { pub(super) fn execute_indexing_instr(&mut self, instr: &IndexingInstruction) { match instr { - &IndexingInstruction::SwitchOnTerm(v, c, l, s) => { - let addr = self[temp_v!(1)]; + &IndexingInstruction::SwitchOnTerm(arg, v, c, l, s) => { + let addr = self[temp_v!(arg)]; let addr = self.store(self.deref(addr)); let offset = match addr { @@ -1423,8 +1423,8 @@ impl MachineState { o => self.p += o, }; } - &IndexingInstruction::SwitchOnConstant(_, ref hm) => { - let addr = self[temp_v!(1)]; + &IndexingInstruction::SwitchOnConstant(arg, _, ref hm) => { + let addr = self[temp_v!(arg)]; let addr = self.store(self.deref(addr)); let offset = @@ -1445,8 +1445,8 @@ impl MachineState { o => self.p += o, }; } - &IndexingInstruction::SwitchOnStructure(_, ref hm) => { - let a1 = self.registers[1]; + &IndexingInstruction::SwitchOnStructure(arg, _, ref hm) => { + let a1 = self.registers[arg]; let addr = self.store(self.deref(a1)); let offset = match addr { diff --git a/src/write.rs b/src/write.rs index 71289d56..cf40509d 100644 --- a/src/write.rs +++ b/src/write.rs @@ -276,13 +276,13 @@ impl fmt::Display for ChoiceInstruction { impl fmt::Display for IndexingInstruction { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { match self { - &IndexingInstruction::SwitchOnTerm(v, c, l, s) => { - write!(f, "switch_on_term {}, {}, {}, {}", v, c, l, s) + &IndexingInstruction::SwitchOnTerm(a, v, c, l, s) => { + write!(f, "switch_on_term {}, {}, {}, {}, {}", a, v, c, l, s) } - &IndexingInstruction::SwitchOnConstant(num_cs, _) => { + &IndexingInstruction::SwitchOnConstant(_, num_cs, _) => { write!(f, "switch_on_constant {}", num_cs) } - &IndexingInstruction::SwitchOnStructure(num_ss, _) => { + &IndexingInstruction::SwitchOnStructure(_, num_ss, _) => { write!(f, "switch_on_structure {}", num_ss) } } -- 2.54.0