From 24b60eb2c65449fdbeb225259a814899a2895511 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Thu, 23 Mar 2017 16:55:43 -0600 Subject: [PATCH] optimizations up to section 5.8 --- Cargo.lock | 2 +- Cargo.toml | 2 +- README.md | 7 ++- src/prolog/ast.rs | 2 +- src/prolog/codegen.rs | 134 ++++++++++++++++++++++++------------------ src/prolog/io.rs | 4 +- src/prolog/machine.rs | 2 +- 7 files changed, 90 insertions(+), 63 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 44d3cb16..3d66e845 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -1,6 +1,6 @@ [root] name = "rusty-wam" -version = "0.5.5" +version = "0.5.7" dependencies = [ "lalrpop 0.12.5 (registry+https://github.com/rust-lang/crates.io-index)", "lalrpop-util 0.12.5 (registry+https://github.com/rust-lang/crates.io-index)", diff --git a/Cargo.toml b/Cargo.toml index 180309ee..a231cab1 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -1,6 +1,6 @@ [package] name = "rusty-wam" -version = "0.5.6" +version = "0.5.7" authors = ["Mark Thom"] build = "build.rs" diff --git a/README.md b/README.md index dbedf0d3..4fde54b3 100644 --- a/README.md +++ b/README.md @@ -11,9 +11,14 @@ pure Prolog. Pure Prolog is implemented as a simple REPL. "Pure Prolog" is Prolog without cut, meta- or extra-logical operators, or side effects of any kind. In terms of the tutorial pacing, the work has progressed to the -to the end of section 5.6, skipping past 5.4. Atoms and lists are the +to the end of section 5.7, skipping past 5.4. Atoms and lists are the only two data types currently supported. +While proper environment trimming code is emitted by the code +generator, it has no effect on the bytecode WAM, which lacks +fine-grained control over the alignment and allocation of stack +frames. + ## Tutorial To enter a multi-clause predicate, the brackets ":{" and "}:" are used as delimiters. They must be entirely contained with their own lines. diff --git a/src/prolog/ast.rs b/src/prolog/ast.rs index 27ebae67..c387e759 100644 --- a/src/prolog/ast.rs +++ b/src/prolog/ast.rs @@ -166,7 +166,7 @@ pub enum ChoiceInstruction { pub enum ControlInstruction { Allocate(usize), - Call(Atom, usize), + Call(Atom, usize, usize), Deallocate, Execute(Atom, usize), Proceed diff --git a/src/prolog/codegen.rs b/src/prolog/codegen.rs index c275b9cf..a8e83ad5 100644 --- a/src/prolog/codegen.rs +++ b/src/prolog/codegen.rs @@ -126,7 +126,6 @@ impl<'a> CompilationTarget<'a> for QueryInstruction { struct TermMarker<'a> { bindings: HashMap<&'a Var, VarReg>, arg_c: usize, - perm_c: usize, temp_c: usize } @@ -134,13 +133,11 @@ impl<'a> TermMarker<'a> { fn new() -> TermMarker<'a> { TermMarker { bindings: HashMap::new(), arg_c: 1, - perm_c: 1, temp_c: 1 } } fn reset(&mut self) { self.bindings.clear(); - self.perm_c = 1; } fn contains_var(&self, var: &'a Var) -> bool { @@ -160,26 +157,17 @@ impl<'a> TermMarker<'a> { if reg_type.reg_num() == 0 { match lvl { - Level::Deep if reg_type.is_perm() => { - let perm = self.perm_c; - self.perm_c += 1; - cell.set(RegType::Perm(perm)); - }, - Level::Deep => { + Level::Deep if !reg_type.is_perm() => { let temp = self.temp_c; self.temp_c += 1; cell.set(RegType::Temp(temp)); }, - Level::Shallow if reg_type.is_perm() => { - let arg = self.arg_c; - self.arg_c += 1; - cell.set(RegType::Perm(arg)); - }, - Level::Shallow => { + Level::Shallow if !reg_type.is_perm() => { let arg = self.arg_c; self.arg_c += 1; cell.set(RegType::Temp(arg)); - } + }, + _ => {} }; } } @@ -203,14 +191,12 @@ impl<'a> TermMarker<'a> { fn mark_new_var(&mut self, lvl: Level, var: &'a Var, reg: RegType) -> VarReg { - let inner_reg = if reg.is_perm() { - let perm = self.perm_c; - self.perm_c += 1; - RegType::Perm(perm) - } else { + let inner_reg = if !reg.is_perm() { let temp = self.temp_c; self.temp_c += 1; RegType::Temp(temp) + } else { + reg }; let reg = match lvl { @@ -259,15 +245,15 @@ impl<'a> TermMarker<'a> { } #[derive(Copy, Clone)] -enum TermStatus { - New, Old, Recurrent +enum VarStatus { + New, Old, Permanent(usize) } pub struct CodeGenerator<'a> { marker: TermMarker<'a> } -type VariableFixture<'a> = (TermStatus, Vec<&'a Cell>); +type VariableFixture<'a> = (VarStatus, Vec<&'a Cell>); type VariableFixtures<'a> = HashMap<&'a Var, VariableFixture<'a>>; impl<'a> CodeGenerator<'a> { @@ -472,77 +458,109 @@ impl<'a> CodeGenerator<'a> { target } - fn mark_vars_in_term(iter: Iter, vs: &mut VariableFixtures<'a>) + fn mark_vars_in_term(iter: Iter, vs: &mut VariableFixtures<'a>, i: usize) where Iter : Iterator> { for term in iter { if let TermRef::Var(_, reg_cell, var) = term { let mut status = vs.entry(var) - .or_insert((TermStatus::New, Vec::new())); + .or_insert((VarStatus::New, Vec::new())); status.1.push(reg_cell); match status.0 { - TermStatus::Old => status.0 = TermStatus::Recurrent, + VarStatus::Old => + status.0 = VarStatus::Permanent(i), + VarStatus::Permanent(_) => + status.0 = VarStatus::Permanent(i), _ => {} }; } } - for &mut (ref mut term_status, ref mut cb) in vs.values_mut() { + for &mut (ref mut term_status, _) in vs.values_mut() { match *term_status { - TermStatus::New => *term_status = TermStatus::Old, - TermStatus::Recurrent => { - for cell_reg in cb.drain(0..) { - cell_reg.set(VarReg::Norm(RegType::Perm(0))); - } - }, + VarStatus::New => + *term_status = VarStatus::Old, _ => {} } } } + fn set_perm_vals(vs: &VariableFixtures) { + let mut values_vec : Vec<_> = vs.values() + .map(|ref v| (v.0, &v.1)) + .collect(); + + values_vec.sort_by_key(|ref v| { + match v.0 { + VarStatus::Permanent(i) => i, + _ => usize::min_value() + } + }); + + for (i, v) in values_vec.into_iter().rev().enumerate() { + if let VarStatus::Permanent(_) = v.0 { + for cell in v.1 { + cell.set(VarReg::Norm(RegType::Perm(i + 1))); + } + } else { + break; + } + } + } + fn mark_perm_vars(rule: &'a Rule) -> VariableFixtures { let &Rule { head: (ref p0, ref p1), ref clauses } = rule; - let mut vfs = HashMap::new(); + let mut vs = HashMap::new(); let iter = p0.breadth_first_iter().chain(p1.breadth_first_iter()); - Self::mark_vars_in_term(iter, &mut vfs); + Self::mark_vars_in_term(iter, &mut vs, 0); - for term in clauses { - Self::mark_vars_in_term(term.breadth_first_iter(), &mut vfs); + for (i, term) in clauses.iter().enumerate() { + Self::mark_vars_in_term(term.breadth_first_iter(), &mut vs, i + 1); } - vfs + Self::set_perm_vals(&vs); + + vs } - fn add_conditional_call(compiled_query: &mut Code, term: &Term) + fn add_conditional_call(compiled_query: &mut Code, term: &Term, pvs: usize) { match term { &Term::Constant(_, Constant::Atom(ref atom)) => { - let call = ControlInstruction::Call(atom.clone(), 0); + let call = ControlInstruction::Call(atom.clone(), 0, pvs); compiled_query.push(Line::Control(call)); }, &Term::Clause(_, ref atom, ref terms) => { - let call = ControlInstruction::Call(atom.clone(), terms.len()); + let call = ControlInstruction::Call(atom.clone(), terms.len(), pvs); compiled_query.push(Line::Control(call)); }, _ => {} } } - pub fn compile_rule(&mut self, rule: &'a Rule) -> Code { - let vfs = Self::mark_perm_vars(&rule); - let &Rule { head: (ref p0, ref p1), ref clauses } = rule; - let mut perm_vars = 0; + fn vars_above_threshold(vs: &VariableFixtures, index: usize) -> usize { + let mut var_count = 0; - for &(term_status, _) in vfs.values() { - if let TermStatus::Recurrent = term_status { - perm_vars += 1; + for &(term_status, _) in vs.values() { + if let VarStatus::Permanent(i) = term_status { + if i >= index { + var_count += 1; + } } } + var_count + } + + pub fn compile_rule(&mut self, rule: &'a Rule) -> Code { + let vs = Self::mark_perm_vars(&rule); + let &Rule { head: (ref p0, ref p1), ref clauses } = rule; + + let perm_vars = Self::vars_above_threshold(&vs, 1); let mut body = Vec::new(); if clauses.len() > 0 { @@ -555,15 +573,19 @@ impl<'a> CodeGenerator<'a> { self.marker.advance_at_head(p1); body.push(Line::Query(self.compile_target(p1, false))); - Self::add_conditional_call(&mut body, p1); + Self::add_conditional_call(&mut body, p1, perm_vars); - body = clauses.iter() - .map(|ref term| self.compile_internal_query(term)) + body = clauses.iter().enumerate() + .map(|(i, ref term)| { + let num_vars = Self::vars_above_threshold(&vs, i+2); + self.compile_internal_query(term, num_vars) + }) .fold(body, |mut body, ref mut cqs| { body.append(cqs); body }); + // now perform LCO. let last_arity = rule.last_clause().arity(); let mut dealloc_index = body.len() - 1; @@ -580,7 +602,7 @@ impl<'a> CodeGenerator<'a> { if clauses.len() > 0 { body.insert(dealloc_index, Line::Control(ControlInstruction::Deallocate)); } - + body } @@ -594,11 +616,11 @@ impl<'a> CodeGenerator<'a> { compiled_fact } - fn compile_internal_query(&mut self, term: &'a Term) -> Code { + fn compile_internal_query(&mut self, term: &'a Term, index: usize) -> Code { self.marker.advance(term); let mut compiled_query = vec![Line::Query(self.compile_target(term, false))]; - Self::add_conditional_call(&mut compiled_query, term); + Self::add_conditional_call(&mut compiled_query, term, index); compiled_query } @@ -607,7 +629,7 @@ impl<'a> CodeGenerator<'a> { self.marker.advance(term); let mut compiled_query = vec![Line::Query(self.compile_target(term, true))]; - Self::add_conditional_call(&mut compiled_query, term); + Self::add_conditional_call(&mut compiled_query, term, 1); compiled_query } diff --git a/src/prolog/io.rs b/src/prolog/io.rs index e7823301..58c5d9e7 100644 --- a/src/prolog/io.rs +++ b/src/prolog/io.rs @@ -88,8 +88,8 @@ impl fmt::Display for ControlInstruction { match self { &ControlInstruction::Allocate(num_cells) => write!(f, "allocate {}", num_cells), - &ControlInstruction::Call(ref name, ref arity) => - write!(f, "call {}/{}", name, arity), + &ControlInstruction::Call(ref name, arity, pvs) => + write!(f, "call {}/{}, {}", name, arity, pvs), &ControlInstruction::Deallocate => write!(f, "deallocate"), &ControlInstruction::Execute(ref name, arity) => diff --git a/src/prolog/machine.rs b/src/prolog/machine.rs index 5d328f40..591bec27 100644 --- a/src/prolog/machine.rs +++ b/src/prolog/machine.rs @@ -666,7 +666,7 @@ impl MachineState { self.e = self.and_stack.len() - 1; self.p += 1; }, - &ControlInstruction::Call(ref name, arity) => { + &ControlInstruction::Call(ref name, arity, _) => { let compiled_tl_index = code_dir.get(&(name.clone(), arity)) .map(|index| *index); -- 2.54.0