Parse abstractions

Got tricked with or()'s function eagerness: Even when the left hand
side succeeds, the argument was evaluated which consumed a token in
the parser which prevented proper parsing.

2 files changed, 58 insertions, 5 deletions

diff --git a/rust/src/ast.rs b/rust/src/ast.rs
index 0493f59..722e9e0 100644
--- a/rust/src/ast.rs
+++ b/rust/src/ast.rs
@@ -1,11 +1,12 @@
 use std::fmt::{self, Display};
 
-#[derive(Debug, PartialEq)]
+#[derive(Debug, PartialEq, Clone)]
 pub enum Value {
     Num(i32),
     Bool(bool),
     Sym(String),
     App(Box<Value>, Box<Value>),
+    Lam(String, Box<Value>),
 }
 
 impl Display for Value {
@@ -15,6 +16,7 @@ impl Display for Value {
             Value::Bool(b) => write!(f, "{}", b),
             Value::Sym(s) => write!(f, "{}", s),
             Value::App(l, r) => write!(f, "({} {})", l, r),
+            Value::Lam(var, body) => write!(f, "(lam {} {})", var, body),
         }
     }
 }
diff --git a/rust/src/parser.rs b/rust/src/parser.rs
index 3ec0ab2..11948c1 100644
--- a/rust/src/parser.rs
+++ b/rust/src/parser.rs
@@ -4,6 +4,7 @@ use crate::ast::*;
 enum Token {
     LParen,
     RParen,
+    Lambda,
     Word(String),
 }
 
@@ -28,6 +29,18 @@ impl Parser {
     fn next(&mut self) {
         self.index += 1;
     }
+
+    fn backtrack(&mut self) {
+        self.index -= 1;
+    }
+
+    fn expect_symbol(&mut self) -> Result<String, String> {
+        if let Token::Word(s) = self.tokens.get(self.index).ok_or("Expected a symbol")? {
+            Ok(s.clone())
+        } else {
+            Err("Expected a symbol".to_string())
+        }
+    }
 }
 
 pub fn parse(arg: &str) -> Value {
@@ -39,7 +52,30 @@ pub fn parse(arg: &str) -> Value {
 }
 
 fn parse_expression(parser: &mut Parser) -> Result<Value, String> {
-    parse_application(parser).or(parse_value(parser))
+    parse_abstraction(parser)
+        .or_else(|_| parse_application(parser))
+        .or_else(|_| parse_value(parser))
+}
+
+fn parse_abstraction(parser: &mut Parser) -> Result<Value, String> {
+    parser.expect(Token::LParen)?;
+    parser.next();
+    parser.expect(Token::Lambda).map_err(|e| {
+        parser.backtrack();
+        e.to_string()
+    })?;
+    parser.next();
+    let var = parse_variable(parser)?;
+    let body = parse_expression(parser)?;
+    parser.expect(Token::RParen)?;
+    parser.next();
+    Ok(Value::Lam(var, Box::new(body)))
+}
+
+fn parse_variable(parser: &mut Parser) -> Result<String, String> {
+    let var = parser.expect_symbol()?;
+    parser.next();
+    Ok(var)
 }
 
 fn parse_application(parser: &mut Parser) -> Result<Value, String> {
@@ -48,14 +84,15 @@ fn parse_application(parser: &mut Parser) -> Result<Value, String> {
     let left = parse_expression(parser)?;
     let right = parse_expression(parser)?;
     parser.expect(Token::RParen)?;
+    parser.next();
     Ok(Value::App(Box::new(left), Box::new(right)))
 }
 
 fn parse_value(parser: &mut Parser) -> Result<Value, String> {
     let token = parser.tokens.get(parser.index).ok_or("Expected a value")?;
     let val = parse_number(token)
-        .or(parse_bool(token))
-        .or(parse_symbol(token))?;
+        .or_else(|_| parse_bool(token))
+        .or_else(|_| parse_symbol(token))?;
     parser.next();
     Ok(val)
 }
@@ -97,7 +134,7 @@ fn terminate(result: &mut Vec<Token>, word: &mut String) {
 fn parse_symbol(token: &Token) -> Result<Value, String> {
     match token {
         Token::Word(s) => Ok(Value::Sym(s.clone())),
-        _ => Err("Expected a symbol".to_string()),
+        _ => Err(format!("Expected a symbol, got {:?}", token)),
     }
 }
 
@@ -193,6 +230,20 @@ mod tests {
         );
     }
 
+    #[test]
+    fn parse_abstraction() {
+        assert_eq!(
+            Lam(
+                "x".to_string(),
+                Box::new(App(
+                    Box::new(Sym("x".to_string())),
+                    Box::new(Sym("x".to_string()))
+                ))
+            ),
+            parse("(lam x (x x))")
+        );
+    }
+
     impl Arbitrary for Value {
         type Parameters = ();
         type Strategy = BoxedStrategy<Self>;