BASIC Interpreter with Rust

FUN with Functions

---

Programming Basics

Many programming courses motivate functions as a way to avoid code duplication and to increase code reuse. For example, imagine writing a program that prints a decorative line before and after printing some data:

10 PRINT "=========="
20 PRINT "Data Here"
30 PRINT "=========="
40 PRINT "More Data"
50 PRINT "=========="
60 PRINT "Even More"
70 PRINT "=========="

Above, we repeat PRINT "==========" multiple times. If we would need to change the decoration, we would have to update every line.

A simple solution would be to create a function that takes a string as a parameter and prints it with a decoration. That way, we could call the function whenever we need a decorated print.

fn print_decoration() {
    println!("==========");
}

fn print_decorated(data: &str) {
    print_decoration();
    println!("{}", data);
}

fn main() {
    print_decorated("Data Here");
    print_decorated("More Data");
    print_decorated("Even More");
    print_decoration();
}

BASIC Subroutines

Before modern functions, BASIC had subroutines with GOSUB (Go to Subroutine) and RETURN.

10 PRINT "Starting"
20 GOSUB 100
30 PRINT "After first call"
40 GOSUB 100
50 PRINT "After second call"
60 END
100 PRINT "=========="
110 RETURN

The GOSUB statement jumps to the specified line (100), executes until it hits RETURN, then goes back to the line after the GOSUB. The difference to GOTO is that the return address is saved, allowing the program to continue where it left off.

Fig 2. — GOSUB/RETURN sequence with call stack.

To implement GOSUB, we need a call stack - a list of return addresses.

• When GOSUB executes, we:

  1. Push the current line number (next line after GOSUB) onto the stack.
  2. Jump to the subroutine line.

• When RETURN executes, we:

  1. Pop the line number from the stack.
  2. Jump to that line.

The reason why a stack is used is that subroutines can call other subroutines, leading to nested calls. The last subroutine called must return first (Last In, First Out - LIFO).

Loading Exercise...

Implementing GOSUB/RETURN

Let’s extend our interpreter to support subroutines!

Add Tokens

First, add new tokens Gosub and Return to our token definitions in src/token.rs.

#[derive(Debug, Clone, PartialEq)]
pub enum Token {
    // ... existing tokens ...
    Gosub,
    Return,
}

Update Lexer

Then, update the lexer to recognize GOSUB and RETURN.

fn read_word(&mut self) -> Token {
  // ... existing code ...
  match word.as_str() {
      // ... existing keywords ...
      "GOSUB" => Token::Gosub,
      "RETURN" => Token::Return,
      _ => Token::Variable(word),
  }
}

Add Statements

Update the src/ast.rs file to add new statement variants for GOSUB and RETURN.

#[derive(Debug, Clone)]
pub enum Statement {
    // ... existing variants ...
    Gosub(usize),
    Return,
}

And adjust the display trait to account for the new statements.

impl fmt::Display for Statement {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            // ...
            Statement::Gosub(target) => write!(f, "GOSUB {}", target),
            Statement::Return => write!(f, "RETURN"),
        }
    }
}

Update Parser

Then, update the parser to handle the new statements. First, add a new function for handling GOSUB.

    fn parse_gosub(&mut self) -> Result<Statement, String> {
        match self.advance() {
            Some(Token::Number(line)) => Ok(Statement::Gosub(*line as usize)),
            _ => Err(format!("Expected line number after GOSUB")),
        }
    }

And then, add it to the main statement parsing function.

    pub fn parse_statement(&mut self) -> Result<Statement> {
        match self.advance() {
            // ... existing cases ...
            Some(Token::Gosub) => self.parse_gosub(),
            Some(Token::Return) => Ok(Statement::Return),
            Some(token) => Err(format!(
                "Unexpected token at start of statement: {:?}",
                token
            )),
            None => Err("Empty statement".to_string()),
        }
    }

Add Call Stack to Interpreter

Then, modify the interpreter so that it has a call stack. We’ll use a Vec<usize> to store return addresses.

pub struct Interpreter {
    program: HashMap<usize, Statement>,
    variables: HashMap<String, i32>,
    call_stack: Vec<usize>,
}

impl Interpreter {
    pub fn new() -> Self {
        Interpreter {
            program: HashMap::new(),
            variables: HashMap::new(),
            call_stack: Vec::new(),
        }
    }

    // ...
}

Loading Exercise...

Implement GOSUB/RETURN in Run Loop

Then, add handling for GOSUB and RETURN in the main run loop of the interpreter. When the interpreter encounters a GOSUB, it should push the return address onto the stack and jump to the target line. When it encounters a RETURN, it should pop the return address from the stack and jump back.

   // ... existing code ...
    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() {
            // ... existing code ...
                Statement::Gosub(target) => {
                    if pc + 1 < lines.len() {
                        self.call_stack.push(lines[pc + 1]);
                    } else {
                        self.call_stack.push(usize::MAX);
                    }

                    pc = lines
                        .iter()
                        .position(|&x| x == target)
                        .ok_or(format!("GOSUB target line {} not found", target))?;
                }
                Statement::Return => {
                    let return_line = self
                        .call_stack
                        .pop()
                        .ok_or(format!("RETURN without GOSUB"))?;

                    if return_line == usize::MAX {
                        break;
                    }

                    pc = lines
                        .iter()
                        .position(|&x| x == return_line)
                        .ok_or(format!("GOSUB RETURN line {} not found", return_line))?;
                }
            // ... existing code ...
        }
        Ok(())
    }

Testing GOSUB/RETURN

Then, let’s add a few tests to ensure our GOSUB/RETURN implementation works correctly. Add the following two tests to the tests in src/interpreter.rs:

  // ... existing tests ...
    #[test]
    fn test_simple_gosub() {
        let mut interp = Interpreter::new();

        interp.load_line("10 LET X = 0").unwrap();
        interp.load_line("20 GOSUB 100").unwrap();
        interp.load_line("30 LET Y = 1").unwrap();
        interp.load_line("40 END").unwrap();
        interp.load_line("100 LET X = 5").unwrap();
        interp.load_line("110 RETURN").unwrap();

        interp.run().unwrap();

        assert_eq!(interp.variables.get("X"), Some(&5));
        assert_eq!(interp.variables.get("Y"), Some(&1));
    }

    #[test]
    fn test_multiple_gosub_calls() {
        let mut interp = Interpreter::new();

        interp.load_line("10 LET COUNT = 0").unwrap();
        interp.load_line("20 GOSUB 100").unwrap();
        interp.load_line("30 GOSUB 100").unwrap();
        interp.load_line("40 GOSUB 100").unwrap();
        interp.load_line("50 END").unwrap();
        interp.load_line("100 LET COUNT = COUNT + 1").unwrap();
        interp.load_line("110 RETURN").unwrap();

        interp.run().unwrap();

        assert_eq!(interp.variables.get("COUNT"), Some(&3));
    }

Now, when you run the tests with cargo test interpreter, all the tests should pass.

Loading Exercise...

From Subroutines to Functions

The difference between subroutines and functions is that subroutines (GOSUB/RETURN) do not have parameters or return values, and they operate on global variables. This can lead to code that is hard to understand and maintain, as the state is shared globally.

For example, in the following BASIC code:

10 LET A = 5
20 GOSUB 100
30 PRINT A
100 LET A = 10
110 RETURN

It’s unclear what the value of A will be after the GOSUB call, since the subroutine modifies the global variable A. This can lead to unintended side effects and bugs.

When we say “unclear”, we mean that the reader of the code has to trace through the program to understand what the value of A will be at line 30. This is especially problematic in larger programs where subroutines may be called from multiple places, making it difficult to track variable states.

Functions (or true functions), on the other hand, have explicit parameters and return values, and they operate in their own local scope. This makes it easier to reason about code, as functions do not have side effects on global state.

Local scope means that variables defined within a function are not accessible outside of that function. This encapsulation helps prevent unintended interactions between different parts of the program.

For example, in Rust, a function that sums the value of two numbers would look like this:

fn sum(a: i32, b: i32) -> i32 {
    a + b
}

Loading Exercise...

BASIC Functions

The original BASIC had only a simple function type, where functions were associated with a single expression. The functions had no local variables or complex control flow, they could return a single value, and they could be called with up to one argument.

Functions were declared with the DEF keyword, which was followed by the name of the function, its parameter in parentheses, an equal sign, and then the expression that defines the function’s return value. The name of the function was limited to three letters, with the first two letters always being “FN”.

For example, in the following, we declare a function called FNZ.

10 DEF FNZ(X) = X * 2

The function would then be called like this:

20 PRINT FNZ(5)
30 PRINT FNZ(10)

The above program would print 10 and 20.

Let’s add support for DEF FN functions to our BASIC interpreter. The path is the same as earlier — we start with defining the tokens and then update the lexer. Then, we define the needed statements and expressions, and update the parser. Finally, we’ll modify the interpreter to handle function definitions and calls.

Loading Exercise...

Adding Tokens

First, add the tokens for DEF, (, and ) in src/token.rs:

#[derive(Debug, Clone, PartialEq)]
pub enum Token {
    // ... existing tokens ...
    Def,
    LParen,  // (
    RParen,  // )
}

Update Lexer

Then, update the lexer to recognize these the left and right parentheses:

    pub fn tokenize(&mut self) -> Result<Vec<Token>, String> {
        let mut tokens = Vec::new();

        while let Some(&ch) = self.chars.peek() {
            match ch {
                // ... existing code ...
                '(' => {
                    tokens.push(Token::LParen);
                    self.chars.next();
                }
                ')' => {
                    tokens.push(Token::RParen);
                    self.chars.next();
                }
                _ => {
                    return Err(format!("Unexpected character: '{}'", ch));
                }
            }
        }

        Ok(tokens)
    }

And then, modify the read_word function to recognize the DEF keyword:

    fn read_word(&mut self) -> Token {
        // ... existing code ...

        match word.as_str() {
            // ... existing keywords ...
            "DEF" => Token::Def,
            _ => Token::Variable(word),
        }
    }

Add Function Definitions

Next, modify src/ast.rs to add a new expression variant for function calls and a new statement for function definitions. The function call expression will represent calling a function with an argument, while the function definition statement will represent defining a function with a name, parameter, and body expression.

#[derive(Debug, Clone)]
pub enum Expr {
    // ... existing variants ...
    FnCall(String, Box<Expr>),
}

#[derive(Debug, Clone)]
pub enum Statement {
    // ... existing variants ...
    DefFn(String, String, Expr),
}

Also modify the Display trait implementations accordingly.

Update Parser

Then, update the parser to handle function definitions and calls. First, add a new function to parse function definitions:

    fn parse_def_fn(&mut self) -> Result<Statement, String> {
        let name = match self.advance() {
            Some(Token::Variable(n)) => n.clone(),
            _ => return Err(format!("Expected function name after DEF")),
        };

        if !name.starts_with("FN") || name.len() != 3 {
            return Err(format!(
                "Function name must be of the form 'FNX' where X is a letter"
            ));
        }

        self.expect(&Token::LParen)?;

        let param = match self.advance() {
            Some(Token::Variable(p)) => p.clone(),
            _ => return Err(format!("Expected parameter name in function definition")),
        };

        self.expect(&Token::RParen)?;

        self.expect(&Token::Equal)?;

        let body = self.parse_expr()?;

        Ok(Statement::DefFn(name, param, body))
    }

Then, modify the parse_statement function to call parse_def_fn when it encounters a DEF token:

    pub fn parse_statement(&mut self) -> Result<Statement, String> {
        match self.advance() {
            // ... existing cases ...
            Some(Token::Def) => self.parse_def_fn(),
            Some(token) => Err(format!(
                "Unexpected token at start of statement: {:?}",
                token
            )),
            None => Err("Empty statement".to_string()),
        }
    }

Then, we need to distinguish between variable references and function calls in expressions. Add a new function called parse_function_call:

    fn parse_function_call(&mut self, name: String) -> Result<Expr, String> {
        self.expect(&Token::LParen)?;

        let arg = self.parse_expr()?;

        self.expect(&Token::RParen)?;

        Ok(Expr::FnCall(name, Box::new(arg)))
    }

Finally, update the parse_primary_expr function to adjust how the Variable token is handled. We’ll modify it so that if the variable is three letters starting with “FN”, we treat it as a function call:

    fn parse_primary_expr(&mut self) -> Result<Expr, String> {
        match self.advance() {
            // ... existing cases ...
            Some(Token::Variable(v)) => {
                let v_clone = v.clone();
                if v_clone.len() == 3 && v_clone.starts_with("FN") {
                    self.parse_function_call(v_clone)
                } else {
                    Ok(Expr::Variable(v_clone))
                }
            }
            // ... existing cases ...
        }
    }

This is not ideal, as there in principle could also be variables named FNX. But for simplicity, we’ll assume that function names and variable names do not collide.

Add Function Definitions to Interpreter

Next, let’s add function definitions to the interpreter. We’ll create a hashmap that stores a (string, expression) pair for each function name.

// ...
pub struct Interpreter {
    program: HashMap<usize, Statement>,
    variables: HashMap<String, i32>,
    call_stack: Vec<usize>,
    functions: HashMap<String, (String, Expr)>,
}

impl Interpreter {
    pub fn new() -> Self {
        Interpreter {
            program: HashMap::new(),
            variables: HashMap::new(),
            call_stack: Vec::new(),
            functions: HashMap::new(),
        }
    }
    // ...

Interpreting Function Calls

Finally, we need to modify the interpreter’s run loop to handle function definitions and calls. When we encounter a DefFn statement, we store the function definition in the functions hashmap.

pub fn run(&mut self) -> Result<()> {
    // ... existing setup ...

    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 {
            // ... existing cases ...

            Statement::DefFn(name, param, expr) => {
                self.functions.insert(name, (param, expr));
                pc += 1;
            }

            // ... rest ...
        }
    }

    Ok(())
}

When we encounter a function call expression, we look up the function, evaluate the argument, and then evaluate the function body with the argument bound to the parameter. This might feel a bit overkill, but it works for our simple interpreter.

fn eval_expr(&self, expr: &Expr) -> Result<i32, String> {
    match expr {
        // ... existing cases ...

        Expr::FnCall(name, arg_expr) => {
            let (param, body) = self
                .functions
                .get(name)
                .ok_or(format!("Function {} not defined", name))?
                .clone();

            let arg_value = self.eval_expr(arg_expr)?;

            let mut local_interpreter = Interpreter {
                program: self.program.clone(),
                variables: self.variables.clone(),
                call_stack: Vec::new(),
                functions: self.functions.clone(),
            };

            local_interpreter
                .variables
                .insert(param, arg_value);

            local_interpreter.eval_expr(&body)
        }
        // ... rest ...
    }
}

Note: The above implementation creates a new interpreter instance for each function call, cloning the current state. This is not efficient for large programs, but it simplifies handling variable scope for our simple BASIC interpreter.

Loading Exercise...

Printing

Our PRINT statement is using a separate expr_to_string function to convert expressions to strings. We need to update this function to handle function calls as well.

    fn expr_to_string(&self, expr: &Expr) -> Result<String, String> {
        match expr {
            // ... existing cases ...
            Expr::FnCall(_, _) => Ok(self.eval_expr(expr)?.to_string()),
        }
    }

Testing Functions

Finally, let’s add some tests to ensure our function implementation works correctly. Append the following tests to src/interpreter.rs:

#[test]
fn test_def_function_simple() {
    let mut interp = Interpreter::new();

    interp.load_line("10 DEF FND(X) = X * 2").unwrap();
    interp.load_line("20 LET Y = FND(5)").unwrap();
    interp.load_line("30 END").unwrap();

    interp.run().unwrap();

    assert_eq!(interp.variables.get("Y"), Some(&10));
}

#[test]
fn test_def_function_with_expression() {
    let mut interp = Interpreter::new();

    interp.load_line("10 DEF FNS(X) = X * X").unwrap();
    interp.load_line("20 LET A = 3").unwrap();
    interp.load_line("30 LET B = FNS(A + 1)").unwrap();
    interp.load_line("40 END").unwrap();

    interp.run().unwrap();

    assert_eq!(interp.variables.get("B"), Some(&16));
}

#[test]
fn test_def_function_nested_calls() {
    let mut interp = Interpreter::new();

    interp.load_line("10 DEF FNA(X) = X + 1").unwrap();
    interp.load_line("20 LET Y = FNA(FNA(5))").unwrap();
    interp.load_line("30 END").unwrap();

    interp.run().unwrap();

    // ADD1(ADD1(5)) = ADD1(6) = 7
    assert_eq!(interp.variables.get("Y"), Some(&7));
}

Now, when you run the tests with cargo test interpreter, all the tests should pass.

Loading Exercise...

Summary

In this chapter, we looked a bit into functions. We first implemented GOSUB/RETURN subroutines with a call stack, enabling nested calls. Then, we added simple single-expression functions with DEF FN. To summarize:

• Subroutines are basic building blocks, but have limitations (no parameters, no local scope).
• Call stack keeps track of return addresses for nested calls.
• True functions have parameters, return values, and local scope.