From 315c748c31c36f8c19036e11d9b58d0eb7b0f40a Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Wed, 2 Aug 2017 17:38:12 -0600 Subject: [PATCH] clean up support for recursive calls, add support for (and protection of) built-in predicates. --- Cargo.lock | 2 +- Cargo.toml | 2 +- src/prolog/ast.rs | 5 ++ src/prolog/codegen.rs | 2 +- src/prolog/io.rs | 20 ++--- src/prolog/machine.rs | 202 +++++++++++++++++++++++------------------- 6 files changed, 127 insertions(+), 106 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 4724aa07..49a55684 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -1,6 +1,6 @@ [root] name = "rusty-wam" -version = "0.6.5" +version = "0.6.6" dependencies = [ "lalrpop 0.13.1 (registry+https://github.com/rust-lang/crates.io-index)", "lalrpop-util 0.13.1 (registry+https://github.com/rust-lang/crates.io-index)", diff --git a/Cargo.toml b/Cargo.toml index f7a338a9..3f24d610 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -1,6 +1,6 @@ [package] name = "rusty-wam" -version = "0.6.5" +version = "0.6.6" authors = ["Mark Thom"] build = "build.rs" diff --git a/src/prolog/ast.rs b/src/prolog/ast.rs index 5a84b8c8..72b0c2fa 100644 --- a/src/prolog/ast.rs +++ b/src/prolog/ast.rs @@ -292,6 +292,10 @@ impl IndexedChoiceInstruction { } } +pub enum BuiltInInstruction { + InternalCallN +} + pub enum ControlInstruction { Allocate(usize), Call(Atom, usize, usize), @@ -359,6 +363,7 @@ pub type CompiledFact = Vec; pub type CompiledQuery = Vec; pub enum Line { + BuiltIn(BuiltInInstruction), Choice(ChoiceInstruction), Control(ControlInstruction), Cut(CutInstruction), diff --git a/src/prolog/codegen.rs b/src/prolog/codegen.rs index 15fb9432..acd9407e 100644 --- a/src/prolog/codegen.rs +++ b/src/prolog/codegen.rs @@ -14,7 +14,7 @@ pub struct CodeGenerator<'a, TermMarker> { } pub enum EvalSession<'a> { - EntryFailure, + EntryFailure(String), EntrySuccess, InitialQuerySuccess(AllocVarDict<'a>, HeapVarDict<'a>), QueryFailure, diff --git a/src/prolog/io.rs b/src/prolog/io.rs index 4ace7e9b..ef844cd7 100644 --- a/src/prolog/io.rs +++ b/src/prolog/io.rs @@ -244,6 +244,7 @@ fn is_consistent(predicate: &Vec) -> bool { pub fn print_code(code: &Code) { for clause in code { match clause { + &Line::BuiltIn(_) => {}, &Line::Fact(ref fact) => for fact_instr in fact { println!("{}", fact_instr); @@ -300,38 +301,30 @@ pub fn eval<'a, 'b: 'a>(wam: &'a mut Machine, tl: &'b TopLevel) -> EvalSession<' if is_consistent(clauses) { let compiled_pred = cg.compile_predicate(clauses); - wam.add_predicate(clauses, compiled_pred); - - EvalSession::EntrySuccess + wam.add_predicate(clauses, compiled_pred) } else { let msg = r"Error: predicate is inconsistent. Each predicate must have the same name and arity."; - - println!("{}", msg); - EvalSession::EntryFailure + + EvalSession::EntryFailure(String::from(msg)) } }, &TopLevel::Fact(ref fact) => { let mut cg = CodeGenerator::::new(); let compiled_fact = cg.compile_fact(fact); - wam.add_fact(fact, compiled_fact); - - EvalSession::EntrySuccess + wam.add_fact(fact, compiled_fact) }, &TopLevel::Rule(ref rule) => { let mut cg = CodeGenerator::::new(); let compiled_rule = cg.compile_rule(rule); - wam.add_rule(rule, compiled_rule); - - EvalSession::EntrySuccess + wam.add_rule(rule, compiled_rule) }, &TopLevel::Query(ref query) => { let mut cg = CodeGenerator::::new(); let compiled_query = cg.compile_query(query); - print_code(&compiled_query); wam.submit_query(compiled_query, cg.take_vars()) } } @@ -393,6 +386,7 @@ pub fn print(wam: &mut Machine, result: EvalSession) { write!(stdout(), ".\n").unwrap(); }, EvalSession::QueryFailure => println!("false."), + EvalSession::EntryFailure(msg) => println!("{}", msg), _ => {} }; } diff --git a/src/prolog/machine.rs b/src/prolog/machine.rs index bb114e00..4c39a26e 100644 --- a/src/prolog/machine.rs +++ b/src/prolog/machine.rs @@ -15,17 +15,13 @@ enum MachineMode { Write } -//TODO: probably.. the wrong solution. should integrate deeply with the WAM. -//type SpecialHandler<'a> = fn(&'a mut MachineState, bool, usize); - -struct MachineState { //<'a> { +struct MachineState { h: usize, s: usize, p: CodePtr, b: usize, b0: usize, e: usize, - //special_handlers: HashMap<&'a Atom, SpecialHandler<'a>>, num_of_args: usize, cp: CodePtr, fail: bool, @@ -37,9 +33,18 @@ struct MachineState { //<'a> { trail: Vec, tr: usize, hb: usize, + lco: bool +} + +#[derive(Clone, Copy, PartialEq, Eq, Hash)] +enum PredicateKeyType { + BuiltIn, + User } -type CodeDir = HashMap<(Atom, usize), usize>; +type PredicateKey = (Atom, usize); // name, arity, type. + +type CodeDir = HashMap; pub struct Machine { ms: MachineState, @@ -92,10 +97,19 @@ impl Index for Machine { impl Machine { pub fn new() -> Self { + let mut code_dir = HashMap::new(); + let code = vec![Line::BuiltIn(BuiltInInstruction::InternalCallN)]; + + // there are 64 registers in the VM, so call/N is defined for all 0 <= N <= 63 + // (an extra register is needed for the predicate name) + for arity in 0 .. 64 { + code_dir.insert((String::from("call"), arity), (PredicateKeyType::BuiltIn, 0)); + } + Machine { ms: MachineState::new(), - code: Vec::new(), - code_dir: HashMap::new(), + code: code, + code_dir: code_dir, cached_query: None } } @@ -103,8 +117,23 @@ impl Machine { pub fn failed(&self) -> bool { self.ms.fail } - - pub fn add_fact(&mut self, fact: &Term, mut code: Code) { + + fn add_user_code<'a>(&mut self, name: Atom, arity: usize, offset: usize) -> EvalSession<'a> + { + match self.code_dir.get(&(name.clone(), arity)) { + Some(&(PredicateKeyType::BuiltIn, _)) => + return EvalSession::EntryFailure(format!("error: cannot replace built-in predicate {}/{}", + name, + arity)), + _ => {} + }; + + self.code_dir.insert((name, arity), (PredicateKeyType::User, offset)); + EvalSession::EntrySuccess + } + + pub fn add_fact<'a>(&mut self, fact: &Term, mut code: Code) -> EvalSession<'a> + { if let Some(name) = fact.name() { let p = self.code.len(); @@ -112,11 +141,14 @@ impl Machine { let arity = fact.arity(); self.code.append(&mut code); - self.code_dir.insert((name, arity), p); + self.add_user_code(name, arity, p) + } else { + EvalSession::EntryFailure(format!("error: the fact has no name.")) } } - pub fn add_rule(&mut self, rule: &Rule, mut code: Code) { + pub fn add_rule<'a>(&mut self, rule: &Rule, mut code: Code) -> EvalSession<'a> + { if let Some(name) = rule.head.0.name() { let p = self.code.len(); @@ -124,11 +156,14 @@ impl Machine { let arity = rule.head.0.arity(); self.code.append(&mut code); - self.code_dir.insert((name, arity), p); + self.add_user_code(name, arity, p) + } else { + EvalSession::EntryFailure(format!("error: the rule has no name.")) } } - pub fn add_predicate(&mut self, clauses: &Vec, mut code: Code) + pub fn add_predicate<'a>(&mut self, clauses: &Vec, mut code: Code) + -> EvalSession<'a> { let p = self.code.len(); @@ -136,7 +171,7 @@ impl Machine { let name = clauses.first().unwrap().name().clone(); self.code.append(&mut code); - self.code_dir.insert((name, arity), p); + self.add_user_code(name, arity, p) } fn cached_query_size(&self) -> usize { @@ -162,6 +197,8 @@ impl Machine { }; match instr { + &Line::BuiltIn(ref builtin_instr) => + self.ms.execute_builtin_instr(&self.code_dir, builtin_instr), &Line::Choice(ref choice_instr) => self.ms.execute_choice_instr(choice_instr), &Line::Cut(ref cut_instr) => @@ -412,7 +449,8 @@ impl MachineState { registers: vec![Addr::HeapCell(0); 64], trail: Vec::new(), tr: 0, - hb: 0 + hb: 0, + lco: false } } @@ -955,27 +993,22 @@ impl MachineState { } } - fn try_call_predicate(&mut self, code_dir: &CodeDir, name: Atom, arity: usize) + fn try_call_predicate(&mut self, code_dir: &CodeDir, name: Atom, arity: usize, lco: bool) { - let compiled_tl_index = code_dir.get(&(name, arity)).map(|index| *index); - + 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; + Some(compiled_tl_index) if lco => { + self.lco = true; + 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: Atom, arity: usize) - { - let compiled_tl_index = code_dir.get(&(name, arity)).map(|index| *index); - - match compiled_tl_index { Some(compiled_tl_index) => { + self.lco = false; + + self.cp = self.p + 1; self.num_of_args = arity; self.b0 = self.b; self.p = CodePtr::DirEntry(compiled_tl_index); @@ -984,75 +1017,57 @@ impl MachineState { }; } - fn dispatch_call_n(&mut self, - code_dir: &CodeDir, - name: Atom, - is_call: bool, - arity: &mut usize, - narity: usize) - -> bool + fn handle_internal_call_n(&mut self, code_dir: &CodeDir) { - if name == "call" { - let new_pred = self.registers[1].clone(); - - for i in 2 .. *arity + narity { - self.registers[i-1] = self.registers[i].clone(); - } - - self.registers[*arity + narity - 1] = new_pred; + let arity = self.num_of_args + 1; + let lco = self.lco; + let pred = self.registers[1].clone(); - if *arity + narity - 1 > 0 { - *arity = *arity + narity - 1; - return true; - } else { - self.fail = true; - return false; - } + for i in 2 .. arity { + self.registers[i-1] = self.registers[i].clone(); } - if is_call { - self.try_call_predicate(code_dir, name, *arity + narity - 1); + if arity > 1 { + self.registers[arity - 1] = pred; + self.execute_call_n(code_dir, arity - 1, lco); } else { - self.try_execute_predicate(code_dir, name, *arity + narity - 1); + self.fail = true; } - - false } - fn execute_call_n(&mut self, code_dir: &CodeDir, is_call: bool, mut arity: usize) + fn execute_call_n(&mut self, code_dir: &CodeDir, arity: usize, lco: bool) { - loop { - let addr = self.deref(self.registers[arity].clone()); + let addr = self.deref(self.registers[arity].clone()); - match self.store(addr) { - Addr::Str(a) => { - let result = self.heap[a].clone(); + let (name, narity) = match self.store(addr) { + Addr::Str(a) => { + let result = self.heap[a].clone(); - if let HeapCellValue::NamedStr(narity, name) = result { - for i in (1 .. arity).rev() { - self.registers[i + narity] = self.registers[i].clone(); - } - - for i in 1 .. narity + 1 { - self.registers[i] = self.heap[a + i].as_addr(a + i); - } + if let HeapCellValue::NamedStr(narity, name) = result { + for i in (1 .. arity).rev() { + self.registers[i + narity] = self.registers[i].clone(); + } - if self.dispatch_call_n(code_dir, name, is_call, &mut arity, narity) { - continue; - } + for i in 1 .. narity + 1 { + self.registers[i] = self.heap[a + i].as_addr(a + i); } - }, - Addr::Con(Constant::Atom(name)) => - if self.dispatch_call_n(code_dir, name, is_call, &mut arity, 0) { - continue; - }, - _ => self.fail = true - }; - - break; - } + + (name, narity) + } else { + self.fail = true; + return; + } + }, + Addr::Con(Constant::Atom(name)) => (name, 0), + _ => { + self.fail = true; + return; + } + }; + + self.try_call_predicate(code_dir, name, arity + narity - 1, lco); } - + fn execute_ctrl_instr(&mut self, code_dir: &CodeDir, instr: &ControlInstruction) { match instr { @@ -1065,9 +1080,9 @@ impl MachineState { self.p += 1; }, &ControlInstruction::Call(ref name, arity, _) => - self.try_call_predicate(code_dir, name.clone(), arity), + self.try_call_predicate(code_dir, name.clone(), arity, false), &ControlInstruction::CallN(arity) => - self.execute_call_n(code_dir, true, arity), + self.execute_call_n(code_dir, arity, false), &ControlInstruction::Deallocate => { let e = self.e; @@ -1076,10 +1091,10 @@ impl MachineState { self.p += 1; }, - &ControlInstruction::Execute(ref name, arity) => - self.try_execute_predicate(code_dir, name.clone(), arity), + &ControlInstruction::Execute(ref name, arity) => + self.try_call_predicate(code_dir, name.clone(), arity, true), &ControlInstruction::ExecuteN(arity) => - self.execute_call_n(code_dir, false, arity), + self.execute_call_n(code_dir, arity, true), &ControlInstruction::Proceed => self.p = self.cp, }; @@ -1171,6 +1186,13 @@ impl MachineState { }; } + fn execute_builtin_instr(&mut self, code_dir: &CodeDir, instr: &BuiltInInstruction) + { + match instr { + &BuiltInInstruction::InternalCallN => self.handle_internal_call_n(code_dir) + } + } + fn execute_choice_instr(&mut self, instr: &ChoiceInstruction) { match instr { -- 2.54.0