commit 72b3c7a9d43eadedbaf1fa0dddfc784feb034487
parent bb44d5a8955a79096b6944d6acd7f6c6644c148d
Author: Demonstrandum <moi@knutsen.co>
Date: Mon, 22 Jul 2019 01:16:41 +0100
Function Currying & partial application for infix. Yay!
Diffstat:
9 files changed, 125 insertions(+), 47 deletions(-)
diff --git a/README.md b/README.md
@@ -4,6 +4,24 @@
# Valhalla Language
+## IN DEVELOPMENT
+
+What's been done so far on the front end:
+- [ ] Parser
+ - [x] Lexical analysis, full UTF-8 support, handling: identifiers, symbols, numbers, strings (utf-8 with good number of escapes), all sorts of braces for vectors, sets, grouping, etc.
+ - [x] Infix, prefix and suffix notation.
+ - [x] Correct parsing of precedence, arity and associativity.
+ - [x] The base operators for the language.
+ - [x] Proper function calls, Currying is properly implemented for functions (Haskell-like syntax).
+ - [x] (Cool) error messages, with line and column number and read-out of the line.
+ - [ ] Macros (incl. macro definitions and macro application).
+- [ ] Compiler (generating bytecode to assemble an executable file).
+
+The VM, i.e. the backend for the language, is being developed independently
+and will have its own progress and check-list updates.
+
+### Description
+
This repository contains the front-end (parser and
bytecode compilation) which understands the syntax and
semantics, as well as doing static type analysis and code
diff --git a/samples/currying_infix.vh b/samples/currying_infix.vh
@@ -1,3 +1,13 @@
(2 + 3) -- Eq. of: ((2 +) 3), can write: ((+ 3) 2)
(2 +)
-(+ 3) -- Partial application-
\ No newline at end of file
+(+ 3) -- Partial application
+
+
+----
+2 + 3
+-- same as
+(+) 2 3
+-- same as
+(2 +) 3
+-- same as
+(+ 3) 2+
\ No newline at end of file
diff --git a/samples/func_apl.vh b/samples/func_apl.vh
@@ -0,0 +1,11 @@
+map (1 +) list
+-- The same as
+(map) ((1) +) (list)
+-- which is the same as:
+(((map) ((1) +)) (list))
+-- because of currying, `a b c` <=> `((a b) c)`
+
+-- Function application has highest binding, so:
+a b c + 3
+-- is the same as
+(a b c) + 3+
\ No newline at end of file
diff --git a/samples/functions.vh b/samples/functions.vh
@@ -0,0 +1,6 @@
+plus : Nat -> Nat -> Nat
+
+postulate do:
+ plus n 0 = n
+ plus 0 n = n
+ plus (succ n) m = succ (plus n m)+
\ No newline at end of file
diff --git a/src/syntax/lexer.rs b/src/syntax/lexer.rs
@@ -42,7 +42,7 @@ const IDENT_CHARS : &str = r"\p{L}\?!'\-_";
lazy_static! {
static ref OP : Regex = re!(r"\A([,\+\.\*\|\\/\&%\$\^\~<¬=@>\-]+|:{2,})");
static ref IDENT : Regex = re!(&format!(r"\A([{id}][{id}\p{{N}}]*)", id=IDENT_CHARS));
- static ref SYM : Regex = re!(&format!(r"\A(:[{id}\p{{N}}]+)", id=IDENT_CHARS));
+ static ref SYM : Regex = re!(r"\A(:[^\s]+)");
static ref NUM : Regex = re!(r"\A(\-?(?:(?:0[xX][0-9a-f]+)|(?:0[bB][01]+)|(?:0[Oo][0-7]+)|(?:(?:[0-9]+(?:\.[0-9]+)?(?:e[\+\-]?[0-9]+)?))))");
}
diff --git a/src/syntax/mod.rs b/src/syntax/mod.rs
@@ -30,7 +30,7 @@ use token::ShowStream;
/// Parses a given file, calling various methods from
/// the `syntax` sub-module.
-pub fn parse_file(filename : &'static str) {
+pub fn parse_file(filename : &str) {
let code = fs::read_to_string(filename)
.expect("Could not open file for reading.");
println!("Code:\n{}\n", code);
diff --git a/src/syntax/operators.rs b/src/syntax/operators.rs
@@ -10,16 +10,16 @@ pub enum Side {
/// - Its precedence (as an i32), the higher the int, the higher the precedence.
/// - Associativity, which can either be left, right, or no associativity.
/// - The number of arguments it takes / its arity. Either one, or two.
-#[derive(Copy, Clone)]
-pub struct Operator {
- pub name : &'static str,
+#[derive(Clone, Copy)]
+pub struct Operator<'a> {
+ pub name : &'a str,
pub precedence : i32,
pub associativity : Side,
pub arity : i32,
}
-impl Operator {
- pub fn new(name : &'static str, precedence : i32, associativity : Side, arity : i32) -> Self {
+impl<'a> Operator<'a> {
+ pub fn new(name : &'a str, precedence : i32, associativity : Side, arity : i32) -> Self {
Operator {
name: name.clone(),
precedence,
@@ -46,8 +46,8 @@ impl Operator {
}
/// Wrapper for table of known operators.
-pub struct PrecedenceTable {
- pub table : Vec<Operator>
+pub struct PrecedenceTable<'a> {
+ pub table : Vec<Operator<'a>>
}
#[macro_export]
@@ -57,7 +57,7 @@ macro_rules! push_op {
};
}
-impl PrecedenceTable {
+impl<'a> PrecedenceTable<'a> {
pub fn new() -> Self {
let op = Operator::new;
let table = PrecedenceTable { table: vec![
@@ -107,18 +107,18 @@ impl PrecedenceTable {
table
}
- pub fn new_op(&mut self, name : &'static str, prec : i32, assoc : Side, arity : i32) -> Operator {
+ pub fn new_op(&mut self, name : &'a str, prec : i32, assoc : Side, arity : i32) -> Operator {
let op = Operator::new(name, prec, assoc, arity);
self.table.push(op);
op
}
- pub fn new_fun(&mut self, name : &'static str, max_arity : i32) -> Operator {
+ pub fn new_fun(&mut self, name : &'a str, max_arity : i32) -> Operator {
self.new_op(name, 19, Side::Neither, max_arity)
}
pub fn lookup(&self, name : &str, arity : i32) -> Option<&Operator> {
- self.table.iter().filter(|o| o.name == name && o.arity == arity).next()
+ self.table.iter().filter(|o| o.name == name && o.arity == arity).nth(0)
}
pub fn exists(&self, name : &str) -> bool {
diff --git a/src/syntax/parser.rs b/src/syntax/parser.rs
@@ -6,7 +6,7 @@ use super::err;
use token::{Token, TokenType};
use ast::{Nodes, Numerics};
-pub fn parse(stream : Vec<Token>, file : &'static str) -> ast::Root {
+pub fn parse(stream : Vec<Token>, file : &str) -> ast::Root {
let mut environment = ParseEnvironment::new(stream, file);
environment.optable.new_fun("max", 4);
@@ -15,15 +15,15 @@ pub fn parse(stream : Vec<Token>, file : &'static str) -> ast::Root {
environment.root
}
-struct ParseEnvironment {
+struct ParseEnvironment<'a> {
pub root : ast::Root,
pub stream : Vec<Token>,
- pub optable : operators::PrecedenceTable,
- pub file : &'static str
+ pub optable : operators::PrecedenceTable<'a>,
+ pub file : &'a str
}
-impl ParseEnvironment {
- pub fn new(stream : Vec<Token>, file : &'static str) -> Self {
+impl<'a> ParseEnvironment<'a> {
+ pub fn new(stream : Vec<Token>, file : &'a str) -> Self {
ParseEnvironment {
root: ast::Root::new(),
stream: stream,
@@ -48,23 +48,28 @@ impl ParseEnvironment {
fn null_den(&mut self, token : &Token) -> Nodes {
match token.class {
- TokenType::Ident => ast::IdentNode::new(&token.string),
- TokenType::Op => {
+ TokenType::Op | TokenType::Ident => {
let is_op = self.optable.exists(&token.string);
if is_op {
- return match self.stream[0].class {
- TokenType::RParen => {
- ast::CallNode::new(ast::IdentNode::new(&token.string), vec![])
- },
- _ => ast::CallNode::new(
- ast::CallNode::new(
- ast::IdentNode::new(&token.string),
- vec![]),
- vec![self.expr(500)])
- };
+ let prefix = self.optable.lookup(&token.string, 1);
+ if prefix.is_none() {
+ return match self.stream[0].class {
+ TokenType::RParen => {
+ ast::CallNode::new(ast::IdentNode::new(&token.string), vec![])
+ },
+ _ => ast::CallNode::new(
+ ast::CallNode::new(
+ ast::IdentNode::new(&token.string),
+ vec![ast::EmptyNode::new()]),
+ vec![self.expr(500)])
+ };
+ } else { // It is a prefix unary operator.
+ return ast::CallNode::new(
+ ast::IdentNode::new(&token.string),
+ vec![self.expr(500)]);
+ }
}
- issue!(err::Types::ParseError, self.file, token,
- "`{}` is not an operator.", token.string);
+ ast::IdentNode::new(&token.string)
},
TokenType::Num => ast::NumNode::new(&*token.string),
TokenType::Str => ast::StrNode::new(&token.string),
@@ -95,19 +100,41 @@ impl ParseEnvironment {
|| self.stream[0].class == TokenType::Term
{ return left; }
- if !self.optable.exists(&self.stream[0].string) {
- return issue!(err::Types::ParseError, self.file, &self.stream[0],
- "`{}` is not a binary operator.", &self.stream[0].string);
- }
- while self.optable.precedence(&self.stream[0].string).unwrap_or(0) > right_prec {
- if self.stream[0].class == TokenType::EOF { break; }
- let op = self.optable.lookup(&self.stream.remove(0).string, 2).unwrap();
- left = self.left_den(left, op.clone());
+ while self.optable.precedence(&self.stream[0].string).unwrap_or(190) > right_prec {
+ let next = &(&self.stream[0].string).clone();
+
+ if next == "\0" || next == "\n" || next == ")" { break; }
+
+ let maybe_op = self.optable.lookup(next, 2);
+ if let Some(op) = maybe_op {
+ self.stream.remove(0);
+ let cloned = operators::Operator::new(next, op.precedence, op.associativity, 2);
+ left = self.left_den(left, cloned);
+ } else { // Function call.
+ let mut pushed = false;
+ match left {
+ Nodes::Call(ref mut call) => {
+ if call.operands.is_empty() {
+ call.operands.push(self.expr(190));
+ pushed = true;
+ }
+ }
+ _ => ()
+ };
+ if !pushed {
+ left = self.func_appl(left);
+ }
+ }
}
return left;
}
+ fn func_appl(&mut self, left : Nodes) -> Nodes {
+ println!("Creating function call with:\n --> {}", left);
+ ast::CallNode::new(left, vec![self.expr(190)])
+ }
+
fn left_den(&mut self, left : Nodes, op : operators::Operator) -> Nodes {
let first_appl = ast::CallNode::new(ast::IdentNode::new(op.name), vec![left]);
if self.stream[0].class == TokenType::RParen {
diff --git a/test.vh b/test.vh
@@ -1,3 +1,7 @@
-(2 + 3) -- Eq. of: ((2 +) 3), can write: ((+ 3) 2)
-(2 +)
-(+ 3) -- Partial application-
\ No newline at end of file
+2 + 3
+-- same as
+(+) 2 3
+-- same as
+(2 +) 3
+-- same as
+(+ 3) 2+
\ No newline at end of file
