Writing my own interpreter for Lox, Part 3 - Evaluating Expressions
Last time, we parsed expressions in Lox and this time we are going to evaluate those expressions.
Evaluating expressions means producing some kind of value. Values are created by literals in Lox (Booleans, Numbers, Strings) and they are combined with expressions. Since, we are implementing Lox in Python, we need to map values in Lox to values in Python. Co-incidentally, both Python and Lox support dynamic typing so the type of a value in Lox and their runtime representation in Python admits a natural mapping.
| Lox type | Python representation |
|---|---|
| Any Lox value | Object |
| nil | None |
| Boolean | bool |
| number | float |
| string | str |
We are going to reuse the Visitor pattern to implement interpreter functionality for our Abstract Syntax Trees.
Evaluating Literals
Literals are the atomic things that other expressions are composed of. Literals are themselves not values but they are syntax that produce a value. Values are from the runtime's world while Literals are from the parser's.
So, we define an Interpreter that extends the ExprVisitor abstract class to convert the literal AST node into a runtime value.
class Interpreter(ExprVisitor):
def __init__(self):
self.had_runtime_error = False
def visit_literal(self, expr):
return expr.value
And we want to define some helper functions to stringify these values -
def min_decimal(num: float):
s = f"{num:.15g}"
if '.' in s:
# Strip trailing zeros and dot if needed
s = s.rstrip('0').rstrip('.')
return s
def get_str_for_lox_value(value):
if isinstance(value, bool):
return 'true' if value else 'false'
elif isinstance(value, float):
return min_decimal(value)
elif value == None:
return 'nil'
elif isinstance(value, str):
return value
return f"{value}"
We also refactor our entrypoint into the interpreter (main.py):
class Command(Enum):
tokenize="tokenize"
parse="parse"
evaluate="evaluate"
def main():
if len(sys.argv) < 3:
print("Usage: ./run.sh tokenize <filename>", file=sys.stderr)
exit(1)
command = sys.argv[1]
filename = sys.argv[2]
if command not in Command.__members__:
print(f"Unknown command: {command}", file=sys.stderr)
exit(1)
command = Command.__members__[command]
# Scanning
with open(filename) as file:
file_contents = file.read()
scanner = Scanner(file_contents)
scanner.scan()
if command == Command.tokenize:
for token in scanner.tokens:
print(token)
if not scanner.had_error:
exit(0)
if scanner.had_error:
exit(65)
# Parsing
parser = Parser(scanner.tokens)
try:
expr = parser.expression()
if command == Command.parse and expr:
print(AstPrinter().print(expr))
exit(0)
except Exception:
exit(65)
# Evaluating
interpreter = Interpreter()
value = interpreter.interpret(expr)
if not interpreter.had_runtime_error:
print(get_str_for_lox_value(value))
else:
exit(70)
if __name__ == "__main__":
main()
Evaluating Parentheses
The Grouping expression simply wraps another expression and when evaluated, it just evaluates the inner expression:
def visit_grouping(self, expr: Grouping):
return self.evaluate(expr.expression)
The parentheses themselves don't affect the value - they just control the order of evaluation by creating a grouping in the AST during parsing.
Evaluating Unary and Binary Operators
Unary Operators
Unary operators take a single operand. In Lox, we have two unary operators:
!(bang) - logical NOT-(minus) - arithmetic negation
def visit_unary(self, expr: Unary):
operator = expr.operator
operand = self.evaluate(expr.right)
match operator.token_type:
case TokenType.MINUS:
Interpreter.check_number_operand(operator, operand)
return -(float)(operand)
case TokenType.BANG:
return not Interpreter.is_truthy(operand)
For the minus operator, we need to ensure the operand is a number. For the bang operator, we use Lox's truthiness rules where nil and false are falsy, everything else is truthy:
@staticmethod
def is_truthy(val):
if (val == None):
return False
if isinstance(val, bool):
return val
return True
Binary Operators
Binary operators take two operands. Lox supports arithmetic (+, -, *, /), comparison (<, <=, >, >=), and equality (==, !=) operators:
def visit_binary(self, expr: Binary):
op = expr.operator
left_val = self.evaluate(expr.left)
right_val = self.evaluate(expr.right)
match op.token_type:
case TokenType.STAR:
Interpreter.check_number_operands(op, left_val, right_val)
return (float)(left_val) * (float)(right_val)
case TokenType.SLASH:
Interpreter.check_number_operands(op, left_val, right_val)
return (float)(left_val) / (float)(right_val)
case TokenType.MINUS:
Interpreter.check_number_operands(op, left_val, right_val)
return (float)(left_val) - (float)(right_val)
case TokenType.PLUS:
if isinstance(left_val, float) and isinstance(right_val, float):
return (float)(left_val) + (float)(right_val)
if isinstance(left_val, str) and isinstance(right_val, str):
return (str)(left_val) + (str(right_val))
raise LoxRuntimeError(op, "Operands must be two numbers or two strings.")
case TokenType.LESS:
Interpreter.check_number_operands(op, left_val, right_val)
return (float)(left_val) < (float)(right_val)
case TokenType.LESS_EQUAL:
Interpreter.check_number_operands(op, left_val, right_val)
return (float)(left_val) <= (float)(right_val)
case TokenType.GREATER:
Interpreter.check_number_operands(op, left_val, right_val)
return (float)(left_val) > (float)(right_val)
case TokenType.GREATER_EQUAL:
Interpreter.check_number_operands(op, left_val, right_val)
return (float)(left_val) >= (float)(right_val)
case TokenType.EQUAL_EQUAL:
return Interpreter.is_equal(left_val, right_val)
case TokenType.BANG_EQUAL:
return not Interpreter.is_equal(left_val, right_val)
The + operator is overloaded - it performs arithmetic addition for numbers and string concatenation for strings. Equality uses Lox's notion of equality which is similar to Python's:
def is_equal(a, b):
if a == None and b == None:
return True
if a == None:
return False
return a == b # Lox uses Pythonic notion of equality
Runtime Errors
When evaluating expressions, we need to handle runtime errors that occur when operations are performed on incompatible types. We define a custom LoxRuntimeError exception:
class LoxRuntimeError(RuntimeError):
def __init__(self, token, message):
self.message = message
self.token = token
This error carries the token where the error occurred and stores the message as an attribute, which helps with error reporting. We also have a dedicated error reporting function in errors.py:
def runtime_error(error: LoxRuntimeError):
print(f"{error.message}\n[line {error.token.line}]", file=sys.stderr)
We have helper functions to check operand types:
@staticmethod
def check_number_operand(operator: Token, operand):
if not isinstance(operand, float):
raise LoxRuntimeError(operator, "Operand must be a number.");
@staticmethod
def check_number_operands(operator: Token, left, right):
if not isinstance(left, float) or not isinstance(right, float):
raise LoxRuntimeError(operator, "Operands must be numbers.")
The interpreter catches these runtime errors and handles them gracefully using the dedicated error reporting function:
def interpret(self, expression: Expr):
try:
value = self.evaluate(expression)
return value
except LoxRuntimeError as err:
self.had_runtime_error = True
runtime_error(err)
We've also updated the main function to use the interpreter's interpret method and handle runtime errors properly:
# Evaluating
interpreter = Interpreter()
value = interpreter.interpret(expr)
if not interpreter.had_runtime_error:
print(get_str_for_lox_value(value))
else:
exit(70)
The interpreter tracks whether a runtime error occurred and exits with code 70 (following standard conventions for runtime errors) if one did occur. This completes our basic expression evaluator that can handle literals, grouping, unary operations, binary operations, and runtime error handling.