valhallac

Compiler for set-theoretic programming language.
git clone git://git.knutsen.co/valhallac
Log | Files | Refs | README | LICENSE

commit 4d5959d62ea46789cffe2099f3c57c5422ccebc5
parent 59e198024a6f1eb1001bcd79e71276580298e223
Author: Demonstrandum <moi@knutsen.co>
Date:   Fri,  9 Aug 2019 19:18:38 +0100

Basic static typing for functions.

Diffstat:
MREADME.md | 1+
Agraph.png | 0
Asamples/call_tree.vh | 12++++++++++++
Msrc/syntax/analyser.rs | 123+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------------
Msrc/syntax/ast.rs | 51+++++++++++++++++++++++++++++++--------------------
Mtest.vh | 9++++-----
6 files changed, 149 insertions(+), 47 deletions(-)

diff --git a/README.md b/README.md @@ -20,6 +20,7 @@ What's been done so far on the front-end: - [x] Error messages, with fancy line and column number and read-out of the source line. - [x] Constant folding optimisations on trivially deducible numeric computations at compile time. + - [x] Implicit compile-time type-casting in specific situations. - [ ] Macros (including macro definitions and macro application). - [ ] User-defined binary operators as aliases to functions. - [ ] Compiler (generating bytecode to assemble an executable file). diff --git a/graph.png b/graph.png Binary files differ. diff --git a/samples/call_tree.vh b/samples/call_tree.vh @@ -0,0 +1,11 @@ +A <> B +(<>) A B +((<>) A) B + +-- CALL +-- / \ +-- / \ +-- CALL B +-- / \ +-- / \ +-- <> A+ \ No newline at end of file diff --git a/src/syntax/analyser.rs b/src/syntax/analyser.rs @@ -1,4 +1,5 @@ use std::collections::{HashMap, VecDeque}; +use std::cell::RefCell; use crate::err; @@ -18,11 +19,15 @@ fn const_fold(node : &Nodes) -> Nodes { let left = const_fold(&call.callee.call().unwrap().operands[0]); let right = const_fold(&call.operands[0]); - let default = ast::CallNode::new( - ast::CallNode::new( - const_fold(&*call.callee.call().unwrap().callee), - vec![left.clone()]), - vec![right.clone()]); + let default = Nodes::Call(ast::CallNode { + callee: Box::new(Nodes::Call(ast::CallNode { + callee: Box::new(const_fold(&*call.callee.call().unwrap().callee)), + operands: vec![left.clone()], + return_type: call.callee.yield_type() + })), + operands: vec![right.clone()], + return_type: call.return_type.clone() + }); let is_num_left = left.num().is_some(); let is_num_right = right.num().is_some(); @@ -49,9 +54,11 @@ fn const_fold(node : &Nodes) -> Nodes { return default; } } - return ast::CallNode::new( - const_fold(&*call.callee), - vec![const_fold(&call.operands[0])]); + return Nodes::Call(ast::CallNode { + callee: Box::new(const_fold(&*call.callee)), + operands: vec![const_fold(&call.operands[0])], + return_type: call.return_type.clone() + }); } return node.to_owned(); } @@ -149,7 +156,7 @@ fn balance_types(node : &Nodes) -> Nodes { balance_types(&*call.callee), vec![balance_types(&call.operands[0])]); if let Nodes::Call(ref mut c) = non_bi { - c.set_return_type(node.yield_type()); + c.set_return_type(call.return_type.clone()); } return non_bi; } @@ -158,11 +165,11 @@ fn balance_types(node : &Nodes) -> Nodes { type VarType = (String, ast::StaticTypes); +#[derive(Clone)] struct TypeChecker { - source_line : usize, - source_file : String, - annotations : VecDeque<VarType>, - last_annotated : Option<VarType>, + pub source_line : usize, + pub source_file : String, + ident_map : HashMap<String, ast::StaticTypes>, } impl TypeChecker { @@ -170,8 +177,7 @@ impl TypeChecker { Self { source_line: 0, source_file: String::from("UNANNOUNCED_FILE"), - annotations: VecDeque::new(), - last_annotated: None, + ident_map: HashMap::new(), } } @@ -181,11 +187,11 @@ impl TypeChecker { Nodes::Line(l) => self.source_line = l.line, Nodes::File(f) => self.source_file = f.filename.to_owned(), Nodes::Ident(ref mut i) => { - for pairs in &self.annotations { - if pairs.0 == i.value { - if let ast::StaticTypes::TSet(class) = pairs.1.to_owned() { - i.static_type = *class; - } + if let Some(annotation) = self.ident_map.get(&i.value) { + if let ast::StaticTypes::TSet(class) = annotation.clone() { + i.static_type = *class; + } else { + i.static_type = annotation.clone(); } } return Nodes::Ident(i.to_owned()); @@ -200,12 +206,15 @@ impl TypeChecker { annotatee.value.to_owned(), self.type_branch(&call.operands[0]).yield_type() ); - self.last_annotated = Some(annotation.clone()); - self.annotations.push_back(annotation.clone()); + + self.ident_map.insert(annotation.0.clone(), annotation.1.clone()); if let ast::StaticTypes::TSet(class) = annotation.1 { annotatee.static_type = *class; + } else { + // Error, can only be element of set. } + return clone; } else { // Error: We need the left to be an ident. @@ -216,12 +225,82 @@ impl TypeChecker { Only variable names can be declared as being members of sets."); } }, + "=" => { + // This is useful for checking variables in functions. + if let Nodes::Call(ref assignee) = callee.operands[0] { + // Check all the types in the annotation (A -> B -> C) + // and match them to the arguments found on the left side + // of the assignment (=). Compile these matches into a list + // and pass that list into a new TypeChecker object which checks + // the right hand side of the assignment, matching up the sub-scoped + // variables. + + // A -> B -> C -> D + // f a b c = d + // <=> + // (A -> (B -> (C -> D))) + // ( ((=) ( (((f a) b) c) )) d) + fn collect_args(s : &TypeChecker, call_node : &Nodes, operands : Vec<Nodes>) -> Vec<Nodes> { + let mut pushed = operands.clone(); + + if let Nodes::Call(call) = call_node { + pushed.insert(0, call.operands[0].clone()); + return collect_args(s, &*call.callee, pushed); + } + + if let Nodes::Ident(ident) = call_node { + pushed.insert(0, call_node.clone()); + return pushed; + } + issue!(err::Types::ParseError, + s.source_file.as_str(), + err::NO_TOKEN, s.source_line, + "Function definition must have base caller be an identifier."); + } + + let mut operands = collect_args(&self, &callee.operands[0], vec![]); + let mut func_checker = self.clone(); + + let maybe_type = self.ident_map.get(&operands.remove(0).ident().unwrap().value); + if maybe_type.is_none() { + issue!(err::Types::TypeError, + self.source_file.as_str(), + err::NO_TOKEN, self.source_line, + "Cannot find type annotation for this function."); + } + let mut t = maybe_type.unwrap().clone(); + + for operand in operands { + if let Nodes::Ident(ident) = operand { + if let ast::StaticTypes::TSet(f) = &t { + if let ast::StaticTypes::TFunction(i, o) = *f.clone() { + func_checker.ident_map.insert(ident.value, *i.clone()); + t = *o.clone(); + } + } + } + } + + call.operands[0] = func_checker.type_branch(&call.operands[0]); + return clone; + } + } _ => () } } } + call.callee = Box::new(self.type_branch(&*call.callee)); call.operands = vec![self.type_branch(&call.operands[0])]; + + if let ast::StaticTypes::TFunction(_, o) = call.callee.yield_type() { + if let ast::StaticTypes::TSet(t) = *o { + call.return_type = *t.clone(); + } else { + call.return_type = *o.clone(); + } + } + return Nodes::Call(call.to_owned()); }, _ => () diff --git a/src/syntax/ast.rs b/src/syntax/ast.rs @@ -242,7 +242,7 @@ pub struct FileNode { pub struct EmptyNode; /// All base types, determined at compile time. -#[derive(Clone, PartialEq)] +#[derive(Debug, Clone, PartialEq)] pub enum StaticTypes { TNatural, TInteger, TReal, TString, TSymbol, @@ -267,15 +267,15 @@ impl StaticTypes { impl fmt::Display for StaticTypes { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { let s = match self { - StaticTypes::TNatural => "Natural".to_string(), - StaticTypes::TInteger => "Integer".to_string(), + StaticTypes::TNatural => "Nat".to_string(), + StaticTypes::TInteger => "Int".to_string(), StaticTypes::TReal => "Real".to_string(), - StaticTypes::TString => "String".to_string(), - StaticTypes::TSymbol => "Symbol".to_string(), - StaticTypes::TSet(st) => format!("Set({})", st), - StaticTypes::TFunction(o, r) => format!("Function({}, {})", o, r), + StaticTypes::TString => "Str".to_string(), + StaticTypes::TSymbol => "Sym".to_string(), + StaticTypes::TSet(st) => format!("Set {}", st), + StaticTypes::TFunction(o, r) => format!("({} -> {})", o, r), StaticTypes::TNil => "Nil".to_string(), - StaticTypes::TUnknown => "Dynamic".to_string(), + StaticTypes::TUnknown => "Universal".to_string(), }; write!(f, "{}", s) } @@ -300,12 +300,12 @@ impl fmt::Display for Nodes { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { let yt = self.yield_type(); let printable = match self { - Nodes::Ident(node) => format!("%ident{{ :value \"{}\"; :yield :{} }}", node.value, yt), - Nodes::Num(node) => format!("%num{{ :value {}; :yield :{} }}", node.value, yt), - Nodes::Str(node) => format!("%str{{ :value \"{}\"; :yield :{} }}", node.value, yt), - Nodes::Sym(node) => format!("%sym{{ :value \":{}\"; :yield :{} }}", node.value, yt), + Nodes::Ident(node) => format!("%ident{{ :value \"{}\"; :yield {} }}", node.value, yt), + Nodes::Num(node) => format!("%num{{ :value {}; :yield {} }}", node.value, yt), + Nodes::Str(node) => format!("%str{{ :value \"{}\"; :yield {} }}", node.value, yt), + Nodes::Sym(node) => format!("%sym{{ :value \":{}\"; :yield {} }}", node.value, yt), Nodes::Call(node) => format!( - "%call{{\n :yield :{}\n :callee ({})\n :operands [|\n {}\n |]\n}}", yt, node.callee, + "%call{{\n :yield {}\n :callee ({})\n :operands [|\n {}\n |]\n}}", yt, node.callee, node.operands.iter().map(Nodes::to_string).collect::<Vec<String>>().join("\n ")), Nodes::Block(_) => format!("%block{{ ... }}"), Nodes::Line(node) => format!("%newline{{ :line {} }}", node.line), @@ -361,10 +361,10 @@ impl Nodes { if let Nodes::Ident(ident) = &*sub_call.callee { match ident.value.as_str() { "->" => { - return StaticTypes::TFunction( - Box::new(sub_call.operands[0].yield_type()), - Box::new(call.operands[0].yield_type()) - ); + return StaticTypes::TSet( + Box::new(StaticTypes::TFunction( + Box::new(sub_call.operands[0].yield_type()), + Box::new(call.operands[0].yield_type())))); }, _ => () } @@ -374,7 +374,18 @@ impl Nodes { }; call.return_type.to_owned() }, - _ => StaticTypes::TUnknown + Nodes::Block(_) + | Nodes::Line(_) + | Nodes::File(_) => StaticTypes::TUnknown, + Nodes::Empty(_) => StaticTypes::TNil, + } + } + + pub fn change_yield(&mut self, new_yield : StaticTypes) { + match self { + Nodes::Ident(i) => i.static_type = new_yield, + Nodes::Call(c) => c.return_type = new_yield, + _ => panic!("Cannot change static yield type of node with inherent type.") } } @@ -492,9 +503,9 @@ pub fn pretty_print(node : &Nodes, depth : usize) -> String { let tab = TAB.repeat(depth); let printable = match node { Nodes::Call(n) => format!( - "{tab}%call{{\n{tab}{T}:yield :{yt}\n{tab}{T}:callee (\n{calling}\n{tab}{T})\n{tab}{T}:operand [|{op}|]\n{tab}}}", + "{tab}%call{{\n{tab}{T}:yield {yt}\n{tab}{T}:callee (\n{calling}\n{tab}{T})\n{tab}{T}:operand [|{op}|]\n{tab}}}", tab=tab, T=TAB, - yt=node.yield_type(), + yt=n.return_type, calling=pretty_print(&*n.callee, depth + 2), op=(if n.operands.is_empty() { String::from(" ") } else { format!( "\n{ops}\n{tab}{T}", diff --git a/test.vh b/test.vh @@ -1,5 +1,4 @@ -a : Set Nat -a = Nat +a : Nat -> Nat -> Int +a n m = n + 2*m -b : a -b = 6 * 7- \ No newline at end of file +a 1 2+ \ No newline at end of file