feat(tazjin/rlox): Implement tree-walk interpreter of exprs r/2018

This is only a subset of the Lox spec so far. It implements the
language up to the runtime error chapter on
https://craftinginterpreters.com/evaluating-expressions.html

Change-Id: I295dbf4b6544420d6fe80b6aaba661fb21acdea6
Reviewed-on: https://cl.tvl.fyi/c/depot/+/2281
Reviewed-by: tazjin <mail@tazj.in>
Tested-by: BuildkiteCI

2 files changed, 74 insertions, 10 deletions

diff --git a/users/tazjin/rlox/src/interpreter.rs b/users/tazjin/rlox/src/interpreter.rs
index 7c5a18dd9ac9..e7853ada4915 100644
--- a/users/tazjin/rlox/src/interpreter.rs
+++ b/users/tazjin/rlox/src/interpreter.rs
@@ -1,6 +1,6 @@
 use crate::errors::{report, Error};
-use crate::parser;
-use crate::scanner::{self, Token};
+use crate::parser::{self, Expr, Literal};
+use crate::scanner::{self, Token, TokenKind};
 
 // Run some Lox code and print it to stdout
 pub fn run(code: &str) {
@@ -10,7 +10,10 @@ pub fn run(code: &str) {
         Ok(tokens) => {
             print_tokens(&tokens);
             match parser::parse(tokens) {
-                Ok(expr) => println!("Expression:\n{:?}", expr),
+                Ok(expr) => {
+                    println!("Expression:\n{:?}", expr);
+                    println!("Result: {:?}", eval(&expr));
+                }
                 Err(errors) => report_errors(errors),
             }
         }
@@ -30,3 +33,64 @@ fn report_errors(errors: Vec<Error>) {
         report(&error);
     }
 }
+
+// Tree-walk interpreter
+
+fn eval_truthy(lit: &Literal) -> bool {
+    match lit {
+        Literal::Nil => false,
+        Literal::Boolean(b) => *b,
+        _ => true,
+    }
+}
+
+fn eval_unary<'a>(expr: &parser::Unary<'a>) -> Literal {
+    let right = eval(&*expr.right);
+
+    match (&expr.operator.kind, right) {
+        (TokenKind::Minus, Literal::Number(num)) => Literal::Number(-num),
+        (TokenKind::Bang, right) => Literal::Boolean(!eval_truthy(&right)),
+        _ => unimplemented!("no handling of type errors"),
+    }
+}
+
+fn eval_binary<'a>(expr: &parser::Binary<'a>) -> Literal {
+    let left = eval(&*expr.left);
+    let right = eval(&*expr.right);
+
+    match (&expr.operator.kind, left, right) {
+        // Numeric
+        (TokenKind::Minus, Literal::Number(l), Literal::Number(r)) => Literal::Number(l - r),
+        (TokenKind::Slash, Literal::Number(l), Literal::Number(r)) => Literal::Number(l / r),
+        (TokenKind::Star, Literal::Number(l), Literal::Number(r)) => Literal::Number(l * r),
+        (TokenKind::Plus, Literal::Number(l), Literal::Number(r)) => Literal::Number(l + r),
+
+        // Strings
+        (TokenKind::Plus, Literal::String(l), Literal::String(r)) => {
+            Literal::String(format!("{}{}", l, r))
+        }
+
+        // Comparators (on numbers only?)
+        (TokenKind::Greater, Literal::Number(l), Literal::Number(r)) => Literal::Boolean(l > r),
+        (TokenKind::GreaterEqual, Literal::Number(l), Literal::Number(r)) => {
+            Literal::Boolean(l >= r)
+        }
+        (TokenKind::Less, Literal::Number(l), Literal::Number(r)) => Literal::Boolean(l < r),
+        (TokenKind::LessEqual, Literal::Number(l), Literal::Number(r)) => Literal::Boolean(l <= r),
+
+        // Equality
+        (TokenKind::Equal, l, r) => Literal::Boolean(l == r),
+        (TokenKind::BangEqual, l, r) => Literal::Boolean(l != r),
+
+        _ => unimplemented!("type errors unhandled"),
+    }
+}
+
+fn eval<'a>(expr: &Expr<'a>) -> Literal {
+    match expr {
+        Expr::Literal(lit) => lit.clone(),
+        Expr::Grouping(grouping) => eval(&*grouping.0),
+        Expr::Unary(unary) => eval_unary(unary),
+        Expr::Binary(binary) => eval_binary(binary),
+    }
+}
diff --git a/users/tazjin/rlox/src/parser.rs b/users/tazjin/rlox/src/parser.rs
index 0d5f72fe4dc9..611a99f01c22 100644
--- a/users/tazjin/rlox/src/parser.rs
+++ b/users/tazjin/rlox/src/parser.rs
@@ -12,15 +12,15 @@ use crate::scanner::{Token, TokenKind};
 
 #[derive(Debug)]
 pub struct Binary<'a> {
-    left: Box<Expr<'a>>,
-    operator: Token<'a>,
-    right: Box<Expr<'a>>,
+    pub left: Box<Expr<'a>>,
+    pub operator: Token<'a>,
+    pub right: Box<Expr<'a>>,
 }
 
 #[derive(Debug)]
-pub struct Grouping<'a>(Box<Expr<'a>>);
+pub struct Grouping<'a>(pub Box<Expr<'a>>);
 
-#[derive(Debug)]
+#[derive(Debug, Clone, PartialEq)]
 pub enum Literal {
     Boolean(bool),
     Number(f64),
@@ -30,8 +30,8 @@ pub enum Literal {
 
 #[derive(Debug)]
 pub struct Unary<'a> {
-    operator: Token<'a>,
-    right: Box<Expr<'a>>,
+    pub operator: Token<'a>,
+    pub right: Box<Expr<'a>>,
 }
 
 #[derive(Debug)]