Interpreting Programs
Learning Objectives
- You understand what interpretation means and how it differs from parsing.
- You can evaluate expressions recursively using pattern matching.
- You know how to use HashMap to store program state (variables and lines).
- You can implement a program counter for sequential and jumping execution.
- You can execute all BASIC statements.
- You can test the interpreter with complete programs.
Creating an Interpreter
At this point, we have a lexer and a parser that can turn text-based BASIC programs into statements. We are, however, missing the possibility to execute the statements.
For this, we need an interpreter. An interpreter is a program that reads and executes code, without compiling it to machine code first.
Managing State and Execution
To create a BASIC interpreter, we need the functionality for managing program state and for executing statements. The program state includes variables and their values, as well as the program lines themselves.
Start by adding the following to the interpreter.rs:
use std::collections::HashMap;
use crate::ast::*;
use crate::lexer::Lexer;
use crate::parser::Parser;
use crate::token::Token;
pub struct Interpreter {
program: HashMap<usize, Statement>,
variables: HashMap<String, i32>,
}
impl Interpreter {
pub fn new() -> Self {
Interpreter {
program: HashMap::new(),
variables: HashMap::new(),
}
}
}In our BASIC interpreter, the variables will be global and accessible from any line. This is typical for BASIC interpreters. Storing the lines in a HashMap allows us to have sparse line numbers (e.g., 10, 20, 100) without wasting memory.
Loading Program Lines
To load program lines into the interpreter, we need a method that takes a line of BASIC code, tokenizes it, parses it into a statement, and stores it in the program HashMap. We already have the lexer and parser, so we can use them here. The line number will be the key in the HashMap, and the parsed statement will be the value.
Add the following function to the Interpreter impl:
pub fn load_line(&mut self, line: &str) -> Result<(), String> {
if line.trim().is_empty() {
return Ok(());
}
let mut lexer = Lexer::new(line);
let tokens = lexer.tokenize()?;
if tokens.is_empty() {
return Ok(());
}
match &tokens[0] {
Token::Number(line_num) => {
let line_num = *line_num as usize;
let stmt_tokens = tokens[1..].to_vec();
if stmt_tokens.is_empty() {
self.program.remove(&line_num);
} else {
let mut parser = Parser::new(stmt_tokens);
let statement = parser.parse_statement()?;
self.program.insert(line_num, statement);
}
Ok(())
}
_ => Err("Line must start with a line number".to_string()),
}
}The function load_line handles takes a line, tokenizes it, parses it, and stores it in the program HashMap.
Listing the Program
Let’s also add a helper function for listing the current program:
pub fn list(&self) {
let mut lines: Vec<&usize> = self.program.keys().collect();
lines.sort();
for line_num in lines {
if let Some(statement) = self.program.get(line_num) {
println!("{} {:?}", line_num, statement);
}
}
}Now, we can load and list program lines in our interpreter.
use basic_interpreter::interpreter::Interpreter;
fn main() {
let mut interpreter = Interpreter::new();
interpreter.load_line(r#"10 PRINT "HELLO!""#).unwrap();
interpreter.load_line(r#"20 PRINT "WORLD!""#).unwrap();
interpreter.list();
}Running the above program would output something like:
10 Print(String("HELLO!"))
20 Print(String("WORLD!"))Evaluating Expressions
A key part of an interpreter is the ability to evaluate expressions. Expressions can be numbers, variables, or binary operations (like addition or multiplication). We will implement a method eval_expr that takes an expression and returns its evaluated value. For now, our evaluation focuses just on arithmetic operations and variables; the evaluation outcome is always a number or an error.
Starting Simple
First, we evaluate numbers, strings and variables. Numbers are returned as-is, strings evaluate to 0 (since BASIC treats strings as 0 in numeric context), and variables are looked up in the variables HashMap.
fn eval_expr(&self, expr: &Expr) -> Result<i32, String> {
match expr {
Expr::Number(n) => Ok(*n),
Expr::String(_) => Ok(0),
Expr::Variable(v) => Ok(*self.variables.get(v).unwrap_or(&0)),
Expr::BinOp(left, op, right) => ???
}
}Evaluating Binary Operations
For binary operations, as they consist of a left-hand side and a right-hand side expression along with an operator, we need to recursively evaluate both sides and then apply the operator. Pattern matching is, again, our friend here.
Expr::BinOp(left, op, right) => {
let l = self.eval_expr(left)?;
let r = self.eval_expr(right)?;
match op {
ArithOp::Add => Ok(l + r),
ArithOp::Sub => Ok(l - r),
ArithOp::Mul => Ok(l * r),
ArithOp::Div => {
if r == 0 {
Err("Division by zero".to_string())
} else {
Ok(l / r)
}
}
}
}Expression Evaluation Complete
As a whole, the eval_expr function looks like this:
fn eval_expr(&self, expr: &Expr) -> Result<i32, String> {
match expr {
Expr::Number(n) => Ok(*n),
Expr::String(_) => Ok(0),
Expr::Variable(v) => Ok(*self.variables.get(v).unwrap_or(&0)),
Expr::BinOp(left, op, right) => {
let l = self.eval_expr(left)?;
let r = self.eval_expr(right)?;
match op {
ArithOp::Add => Ok(l + r),
ArithOp::Sub => Ok(l - r),
ArithOp::Mul => Ok(l * r),
ArithOp::Div => {
if r == 0 {
Err("Division by zero".to_string())
} else {
Ok(l / r)
}
}
}
}
}
}String Trickery
As our interpreter supports PRINT, we need to also be able to convert expressions to strings for display. Let’s create a separate function expr_to_string for this purpose. Rust’s to_string method is handy here.
fn expr_to_string(&self, expr: &Expr) -> Result<String, String> {
match expr {
Expr::String(s) => Ok(s.clone()),
Expr::Number(n) => Ok(n.to_string()),
Expr::Variable(v) => Ok(self.variables.get(v).unwrap_or(&0).to_string()),
Expr::BinOp(_, _, _) => Ok(self.eval_expr(expr)?.to_string()),
}
}Running Programs
Now, we have the functionality for loading program lines and evaluating expressions. The next step is to implement the main execution loop that runs the loaded program line by line.
For this, we need to extract the line numbers from the program HashMap, sort them, and then execute each line in order. In addition, as our interpreter supports control flow statements like GOTO and IF, we need to implement a program counter that can jump to different lines based on the execution flow.
Starting Point
The starting point for running programs looks as follows. The function run takes the lines, sorts them, initiates a program counter, and enters a loop to execute each line, one by one. Add the following function run to the Interpreter impl:
pub fn run(&mut self) -> Result<(), String> {
let mut lines: Vec<usize> = self.program.keys().copied().collect();
lines.sort();
let mut pc = 0;
while pc < lines.len() {
let line_num = lines[pc];
let statement = self
.program
.get(&line_num)
.ok_or(format!("Line {} not found", line_num))?
.clone();
// TODO: handle statements
}
Ok(())
}Handling Statements
Next, let’s start handling the statements.
PRINT Statement
We’ll begin with the PRINT statement, which uses the expr_to_string method we created earlier. In addition, we’ll add a default case to handle unimplemented statements.
pub fn run(&mut self) -> Result<(), String> {
let mut lines: Vec<usize> = self.program.keys().copied().collect();
lines.sort();
let mut pc = 0;
while pc < lines.len() {
let line_num = lines[pc];
let statement = self
.program
.get(&line_num)
.ok_or(format!("Line {} not found", line_num))?
.clone();
match statement {
Statement::Print(expr) => {
println!("{}", self.expr_to_string(&expr)?);
pc += 1;
}
_ => {
return Err(format!("Unimplemented statement at line {}", line_num));
}
}
}
Ok(())
}Now, we can already test the interpreter by running a simple program with PRINT statements.
fn main() {
let mut interpreter = Interpreter::new();
interpreter.load_line(r#"10 PRINT "HELLO!""#);
interpreter.load_line(r#"20 PRINT "WORLD!""#);
interpreter.run();
}The above program should output:
HELLO!
WORLD!LET Statement
Next, let’s implement the LET statement, which assigns values to variables. We’ll use the eval_expr method to evaluate the expression on the right-hand side of the assignment, and then store the result in the variables HashMap.
match statement {
Statement::Print(exprs) => {
self.execute_print(&exprs)?;
pc += 1;
}
Statement::Let(var, expr) => {
let value = self.eval_expr(&expr)?;
self.variables.insert(var, value);
pc += 1;
}
_ => {
return Err(format!("Unimplemented statement at line {}", line_num));
}
}Now, our interpreter can handle both PRINT and LET statements.
fn main() {
let mut interpreter = Interpreter::new();
interpreter.load_line(r#"10 LET X = 10"#);
interpreter.load_line(r#"20 PRINT X"#);
interpreter.run();
}The above program should output:
10Handling GOTO
Next, let’s implement the GOTO statement, which allows jumping to a specific line number. We’ll modify the program counter (pc) to point to the target line when a GOTO statement is encountered. As the pc is an index, we need to find the index of the target line in the sorted lines vector.
match statement {
Statement::Print(exprs) => {
self.execute_print(&exprs)?;
pc += 1;
}
Statement::Let(var, expr) => {
let value = self.eval_expr(&expr)?;
self.variables.insert(var, value);
pc += 1;
}
Statement::Goto(target) => {
pc = lines
.iter()
.position(|&x| x == target)
.ok_or(format!("Line {} not found", target))?;
}
_ => {
return Err(format!("Unimplemented statement at line {}", line_num));
}
}Now, the output of the following program should be:
fn main() {
let mut interpreter = Interpreter::new();
interpreter.load_line(r#"10 GOTO 40"#);
interpreter.load_line(r#"20 LET X = 10"#);
interpreter.load_line(r#"30 PRINT X"#);
interpreter.load_line(r#"40 PRINT "HELLO!""#);
interpreter.run();
}HELLO!Handling IF Statement
Finally, let’s add the functionality for handling the IF statement. The IF statement consists of a comparison between two expressions and a target line number to jump to if the condition is true. We’ll evaluate both expressions, perform the comparison, and update the program counter accordingly.
// ...
Statement::If {
left,
op,
right,
target,
} => {
let l = self.eval_expr(&left)?;
let r = self.eval_expr(&right)?;
let condition = match op {
ComparisonOp::Equal => l == r,
ComparisonOp::Greater => l > r,
ComparisonOp::Less => l < r,
};
if condition {
pc = lines
.iter()
.position(|&x| x == target)
.ok_or(format!("Line {} not found", target))?;
} else {
pc += 1;
}
}
// ...Now, our program should also handle IF statements correctly.
fn main() {
let mut interpreter = Interpreter::new();
interpreter.load_line(r#"10 LET X = 5"#);
interpreter.load_line(r#"20 IF X > 3 THEN 40"#);
interpreter.load_line(r#"30 PRINT "X <= 3""#);
interpreter.load_line(r#"40 PRINT "X > 3""#);
interpreter.run();
}The output of the above program should be:
X > 3END Statement and Whole Run Loop
Finally, let’s implement the END statement, which terminates the program execution. When an END statement is encountered, we simply break out of the execution loop.
Statement::End => {
break;
}Together, the whole run function is as follows:
pub fn run(&mut self) -> Result<(), String> {
let mut lines: Vec<usize> = self.program.keys().copied().collect();
lines.sort();
let mut pc = 0; // Program counter
while pc < lines.len() {
let line_num = lines[pc];
let statement = self
.program
.get(&line_num)
.ok_or(format!("Line {} not found", line_num))?
.clone();
match statement {
Statement::Print(expr) => {
println!("{}", self.expr_to_string(&expr)?);
pc += 1;
}
Statement::Let(var, expr) => {
let value = self.eval_expr(&expr)?;
self.variables.insert(var, value);
pc += 1;
}
Statement::If {
left,
op,
right,
target,
} => {
let l = self.eval_expr(&left)?;
let r = self.eval_expr(&right)?;
let condition = match op {
ComparisonOp::Equal => l == r,
ComparisonOp::Greater => l > r,
ComparisonOp::Less => l < r,
};
if condition {
pc = lines
.iter()
.position(|&x| x == target)
.ok_or(format!("Line {} not found", target))?;
} else {
pc += 1;
}
}
Statement::Goto(target) => {
pc = lines
.iter()
.position(|&x| x == target)
.ok_or(format!("Line {} not found", target))?;
}
Statement::End => break,
}
}
Ok(())
}Complete Interpreter
Here’s the complete interpreter in one place:
use std::collections::HashMap;
use crate::ast::*;
use crate::lexer::Lexer;
use crate::parser::Parser;
use crate::token::Token;
pub struct Interpreter {
program: HashMap<usize, Statement>,
variables: HashMap<String, i32>,
}
impl Interpreter {
pub fn new() -> Self {
Interpreter {
program: HashMap::new(),
variables: HashMap::new(),
}
}
pub fn load_line(&mut self, line: &str) -> Result<(), String> {
if line.trim().is_empty() {
return Ok(());
}
let mut lexer = Lexer::new(line);
let tokens = lexer.tokenize()?;
if tokens.is_empty() {
return Ok(());
}
match &tokens[0] {
Token::Number(line_num) => {
let line_num = *line_num as usize;
let stmt_tokens = tokens[1..].to_vec();
if stmt_tokens.is_empty() {
self.program.remove(&line_num);
} else {
let mut parser = Parser::new(stmt_tokens);
let statement = parser.parse_statement()?;
self.program.insert(line_num, statement);
}
Ok(())
}
_ => Err("Line must start with a line number".to_string()),
}
}
pub fn list(&self) {
let mut lines: Vec<&usize> = self.program.keys().collect();
lines.sort();
for line_num in lines {
if let Some(statement) = self.program.get(line_num) {
println!("{} {:?}", line_num, statement);
}
}
}
pub fn run(&mut self) -> Result<(), String> {
let mut lines: Vec<usize> = self.program.keys().copied().collect();
lines.sort();
let mut pc = 0;
while pc < lines.len() {
let line_num = lines[pc];
let statement = self
.program
.get(&line_num)
.ok_or(format!("Line {} not found", line_num))?
.clone();
match statement {
Statement::Print(expr) => {
println!("{}", self.expr_to_string(&expr)?);
pc += 1;
}
Statement::Let(var, expr) => {
let value = self.eval_expr(&expr)?;
self.variables.insert(var, value);
pc += 1;
}
Statement::If {
left,
op,
right,
target,
} => {
let l = self.eval_expr(&left)?;
let r = self.eval_expr(&right)?;
let condition = match op {
ComparisonOp::Equal => l == r,
ComparisonOp::Greater => l > r,
ComparisonOp::Less => l < r,
};
if condition {
pc = lines
.iter()
.position(|&x| x == target)
.ok_or(format!("Line {} not found", target))?;
} else {
pc += 1;
}
}
Statement::Goto(target) => {
pc = lines
.iter()
.position(|&x| x == target)
.ok_or(format!("Line {} not found", target))?;
}
Statement::End => break,
}
}
Ok(())
}
fn eval_expr(&self, expr: &Expr) -> Result<i32, String> {
match expr {
Expr::Number(n) => Ok(*n),
Expr::String(_) => Ok(0),
Expr::Variable(v) => Ok(*self.variables.get(v).unwrap_or(&0)),
Expr::BinOp(left, op, right) => {
let l = self.eval_expr(left)?;
let r = self.eval_expr(right)?;
match op {
ArithOp::Add => Ok(l + r),
ArithOp::Sub => Ok(l - r),
ArithOp::Mul => Ok(l * r),
ArithOp::Div => {
if r == 0 {
Err("Division by zero".to_string())
} else {
Ok(l / r)
}
}
}
}
}
}
fn expr_to_string(&self, expr: &Expr) -> Result<String, String> {
match expr {
Expr::String(s) => Ok(s.clone()),
Expr::Number(n) => Ok(n.to_string()),
Expr::Variable(v) => Ok(self.variables.get(v).unwrap_or(&0).to_string()),
Expr::BinOp(_, _, _) => Ok(self.eval_expr(expr)?.to_string()),
}
}
}Testing the Interpreter
Finally, append the following tests to the interpreter.rs file.
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_eval_number() {
let interp = Interpreter::new();
let expr = Expr::Number(42);
assert_eq!(interp.eval_expr(&expr).unwrap(), 42);
}
#[test]
fn test_eval_addition() {
let interp = Interpreter::new();
let expr = Expr::BinOp(
Box::new(Expr::Number(5)),
ArithOp::Add,
Box::new(Expr::Number(3)),
);
assert_eq!(interp.eval_expr(&expr).unwrap(), 8);
}
#[test]
fn test_eval_subtraction() {
let interp = Interpreter::new();
let expr = Expr::BinOp(
Box::new(Expr::Number(10)),
ArithOp::Sub,
Box::new(Expr::Number(3)),
);
assert_eq!(interp.eval_expr(&expr).unwrap(), 7);
}
#[test]
fn test_eval_multiplication() {
let interp = Interpreter::new();
let expr = Expr::BinOp(
Box::new(Expr::Number(6)),
ArithOp::Mul,
Box::new(Expr::Number(7)),
);
assert_eq!(interp.eval_expr(&expr).unwrap(), 42);
}
#[test]
fn test_eval_division() {
let interp = Interpreter::new();
let expr = Expr::BinOp(
Box::new(Expr::Number(20)),
ArithOp::Div,
Box::new(Expr::Number(4)),
);
assert_eq!(interp.eval_expr(&expr).unwrap(), 5);
}
#[test]
fn test_division_by_zero() {
let interp = Interpreter::new();
let expr = Expr::BinOp(
Box::new(Expr::Number(5)),
ArithOp::Div,
Box::new(Expr::Number(0)),
);
assert!(interp.eval_expr(&expr).is_err());
}
#[test]
fn test_eval_variable_undefined() {
let interp = Interpreter::new();
let expr = Expr::Variable("X".to_string());
assert_eq!(interp.eval_expr(&expr).unwrap(), 0);
}
#[test]
fn test_eval_variable_defined() {
let mut interp = Interpreter::new();
interp.variables.insert("X".to_string(), 42);
let expr = Expr::Variable("X".to_string());
assert_eq!(interp.eval_expr(&expr).unwrap(), 42);
}
#[test]
fn test_eval_nested_expression() {
let interp = Interpreter::new();
let expr = Expr::BinOp(
Box::new(Expr::BinOp(
Box::new(Expr::Number(2)),
ArithOp::Add,
Box::new(Expr::Number(3)),
)),
ArithOp::Mul,
Box::new(Expr::Number(4)),
);
assert_eq!(interp.eval_expr(&expr).unwrap(), 20);
}
#[test]
fn test_load_line() {
let mut interp = Interpreter::new();
interp.load_line("10 PRINT \"Hello\"").unwrap();
assert_eq!(interp.program.len(), 1);
assert!(interp.program.contains_key(&10));
}
#[test]
fn test_load_multiple_lines() {
let mut interp = Interpreter::new();
interp.load_line("10 LET X = 5").unwrap();
interp.load_line("20 PRINT X").unwrap();
interp.load_line("30 END").unwrap();
assert_eq!(interp.program.len(), 3);
}
#[test]
fn test_delete_line() {
let mut interp = Interpreter::new();
interp.load_line("10 PRINT \"Hello\"").unwrap();
assert_eq!(interp.program.len(), 1);
interp.load_line("10").unwrap();
assert_eq!(interp.program.len(), 0);
}
#[test]
fn test_simple_program() {
let mut interp = Interpreter::new();
interp.load_line("10 LET X = 5").unwrap();
interp.load_line("20 LET Y = 10").unwrap();
interp.load_line("30 LET Z = X + Y").unwrap();
interp.load_line("40 END").unwrap();
interp.run().unwrap();
assert_eq!(interp.variables.get("X"), Some(&5));
assert_eq!(interp.variables.get("Y"), Some(&10));
assert_eq!(interp.variables.get("Z"), Some(&15));
}
#[test]
fn test_goto_loop() {
let mut interp = Interpreter::new();
interp.load_line("10 LET X = 0").unwrap();
interp.load_line("20 LET X = X + 1").unwrap();
interp.load_line("30 IF X < 5 THEN 20").unwrap();
interp.load_line("40 END").unwrap();
interp.run().unwrap();
assert_eq!(interp.variables.get("X"), Some(&5));
}
#[test]
fn test_conditional_skip() {
let mut interp = Interpreter::new();
interp.load_line("10 LET X = 10").unwrap();
interp.load_line("20 IF X < 5 THEN 40").unwrap();
interp.load_line("30 LET Y = 1").unwrap();
interp.load_line("40 END").unwrap();
interp.run().unwrap();
assert_eq!(interp.variables.get("Y"), Some(&1));
}
#[test]
fn test_conditional_jump() {
let mut interp = Interpreter::new();
interp.load_line("10 LET X = 3").unwrap();
interp.load_line("20 IF X < 5 THEN 40").unwrap();
interp.load_line("30 LET Y = 1").unwrap();
interp.load_line("40 END").unwrap();
interp.run().unwrap();
assert_eq!(interp.variables.get("Y"), None);
}
#[test]
fn test_invalid_goto() {
let mut interp = Interpreter::new();
interp.load_line("10 GOTO 999").unwrap();
interp.load_line("20 END").unwrap();
let result = interp.run();
assert!(result.is_err());
}
#[test]
fn test_comparison_equal() {
let mut interp = Interpreter::new();
interp.load_line("10 LET X = 5").unwrap();
interp.load_line("20 IF X = 5 THEN 40").unwrap();
interp.load_line("30 LET Y = 1").unwrap();
interp.load_line("40 END").unwrap();
interp.run().unwrap();
assert_eq!(interp.variables.get("Y"), None);
}
#[test]
fn test_comparison_greater() {
let mut interp = Interpreter::new();
interp.load_line("10 LET X = 10").unwrap();
interp.load_line("20 IF X > 5 THEN 40").unwrap();
interp.load_line("30 LET Y = 1").unwrap();
interp.load_line("40 END").unwrap();
interp.run().unwrap();
assert_eq!(interp.variables.get("Y"), None);
}
#[test]
fn test_comparison_less() {
let mut interp = Interpreter::new();
interp.load_line("10 LET X = 3").unwrap();
interp.load_line("20 IF X < 5 THEN 40").unwrap();
interp.load_line("30 LET Y = 1").unwrap();
interp.load_line("40 END").unwrap();
interp.run().unwrap();
assert_eq!(interp.variables.get("Y"), None);
}
}When you run the tests with cargo test interpreter, they should all pass.
Summary
In this chapter, we built an interpreter that allows us to execute BASIC programs. In summary:
- Evaluation recursively computes expression values
- HashMap stores variables and program lines
- A program counter keeps track of execution flow when the program runs
In the next chapter, we’ll add user interaction to our interpreter by implementing a Read-Eval-Print Loop (REPL).