Writing my own interpreter for Lox, Part 6 - Functions

03 Sep, 2025

This is the next part in writing my own interpreter for Lox in Python. Previously, we implemented control flow constructs, making our interpreter Turing complete. In this post, we add functions - the feature that transforms our language from a series of sequential statements into a tool for building reusable, modular programs. Here is the corresponding chapter from Crafting Interpreters.

Functions are first-class values in Lox, meaning they can be:

Stored in variables and data structures
Passed as arguments to other functions
Returned as values from other functions

This functionality (pun intended), combined with lexical scoping and closures, makes functions incredibly powerful building blocks for organizing code.

Updated Grammar

The grammar now includes function declarations, function calls and return statements. Here's the updated grammar we're working with:

program        → declaration* EOF ;

declaration    → funDecl
               | varDecl
               | statement ;

funDecl        → "fun" function ;
function       → IDENTIFIER "(" parameters? ")" block ;
parameters     → IDENTIFIER ( "," IDENTIFIER )* ;

varDecl        → "var" IDENTIFIER ( "=" expression )? ";" ;

statement      → exprStmt
               | ifStmt
               | printStmt
               | returnStmt
               | whileStmt
               | forStmt
               | block ;

returnStmt     → "return" expression? ";" ;

exprStmt       → expression ";" ;
printStmt      → "print" expression ";" ;
block          → "{" declaration* "}" ;

expression     → assignment ;
assignment     → IDENTIFIER "=" assignment
               | logic_or ;

logic_or       → logic_and ( "or" logic_and )* ;
logic_and      → equality ( "and" equality )* ;

equality       → comparison ( ( "!=" | "==" ) comparison )* ;
comparison     → term ( ( ">" | ">=" | "<" | "<=" ) term )* ;
term           → factor ( ( "-" | "+" ) factor )* ;
factor         → unary ( ( "/" | "*" ) unary )* ;
unary          → ( "!" | "-" ) unary | call ;

call           → primary ( "(" arguments? ")" )* ;
arguments      → expression ( "," expression )* ;

primary        → "true" | "false" | "nil"
               | NUMBER | STRING | IDENTIFIER
               | "(" expression ")" ;

The key additions from our previous grammar are:

Function declarations: fun keyword with parameters and body
Function calls: Parentheses with optional comma-separated arguments
Return statements: Optional return values

Function Calls as Expressions

Function calls in Lox are expressions, not statements. This means they produce values and can appear anywhere an expression is valid:

var result = fibonacci(10);
print max(a, b) + min(c, d);
if (is_valid(input)) { /* ... */ }

Call Expression Syntax Tree

I added a Call expression class to app/expr.py:

class Call(Expr):
    def __init__(self, callee: Expr, closing_paren: Token, arguments: list[Expr]):
        self.callee = callee
        self.closing_paren = closing_paren
        self.arguments = arguments
    
    def accept(self, visitor: ExprVisitor):
        return visitor.visit_call(self)

The call expression holds:

callee: The expression that evaluates to the function (often just an identifier, but could be another expression that produces a function)
closing_paren: The closing parenthesis token (for error reporting)
arguments: List of argument expressions

Parsing Function Calls

Function calls have high precedence in the expression hierarchy. In app/parser.py, I modified the unary method to call a new call() method:

def unary(self):
    if self.match(TokenType.BANG, TokenType.MINUS):
        op = self.previous()
        right = self.unary()
        return Unary(op, right)
    
    return self.call()

def call(self):
    expr = self.primary()
    
    while (True):
        if self.match(TokenType.LEFT_PAREN):
            expr = self.finish_call(expr)
        else:
            break
    return expr

def finish_call(self, callee: Expr):
    arguments = []
    if not self.check(TokenType.RIGHT_PAREN):
        arguments.append(self.expression())
        while self.match(TokenType.COMMA):
            if len(arguments) >= 255:
                ParseError.error(self, self.peek(), "Can't have more than 255 arguments.")
            arguments.append(self.expression())
    closing_paren = self.consume(TokenType.RIGHT_PAREN, "Expect ')' after arguments.")
    return Call(callee, closing_paren, arguments)

The parser supports chained calls like getCallback()()() by looping and building nested Call expressions. The 255 argument limit isn't necessary but is present for simplicity purposes.

Native Functions

Before implementing user-defined functions, I added support for native functions - functions implemented in the host language (Python) that can be called from Lox code.

The Callable Interface

I created an abstract base class LoxCallable in app/lox_callable.py:

from abc import ABC, abstractmethod

class LoxCallable(ABC):
    @abstractmethod
    def arity(self):
        raise NotImplementedError()
    
    @abstractmethod
    def call(self, interpreter, arguments):
        raise NotImplementedError()

This interface defines the contract that all callable objects must implement:

arity(): Returns the number of arguments the function expects
call(interpreter, arguments): Executes the function with the given arguments

Clock Native Function

I implemented a clock native function in app/native_fns.py:

from app.lox_callable import LoxCallable
import time

class Clock(LoxCallable):
    def arity(self):
        return 0
    
    def call(self, interpreter, arguments):
        return (float)(round(time.time()))
    
    def __str__(self):
        return "<native_fn>"

The clock() function returns the current Unix timestamp and demonstrates how to integrate host language functionality into Lox.

Global Environment Setup

In app/interpreter.py, I modified the interpreter to have both global and local environments:

class Interpreter(ExprVisitor, StmtVisitor):
    def __init__(self):
        self.had_runtime_error = False
        self.globals = Environment()
        self.environment = self.globals
        self.globals.define("clock", Clock())

The interpreter now maintains a reference to the global environment and initializes it with native functions. This separation becomes important for closures later.

Function Declarations

User-defined functions are created through function declarations using the fun keyword:

fun greet(name) {
    print "Hello, " + name + "!";
}

fun fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 2) + fibonacci(n - 1);
}

Function Statement Syntax Tree

I added a FunctionStmt class to app/stmt.py:

class FunctionStmt(Stmt):
    def __init__(self, name: Token, params: list[Token], body: list[Stmt]):
        self.name = name
        self.params = params
        self.body = body
    
    def accept(self, visitor: StmtVisitor):
        return visitor.visit_function_stmt(self)

The function statement stores:

name: The function's identifier token
params: List of parameter name tokens
body: List of statements that make up the function body

Parsing Function Declarations

In app/parser.py, I added parsing logic for function declarations:

def declaration(self):
    try:
        if (self.match(TokenType.FUN)):
            return self.function_declaration("function")
        if (self.match(TokenType.VAR)):
            return self.variable_declaration_statement()
        return self.statement()
    except ParseError as err:
        self.synchronize()
        return None
        
def function_declaration(self, kind):
    name = self.consume(TokenType.IDENTIFIER, f"Expect {kind} name.")
    self.consume(TokenType.LEFT_PAREN, f"Expect '(' after {kind} name.")
    parameters = []
    if not self.check(TokenType.RIGHT_PAREN):
        parameters.append(self.consume(TokenType.IDENTIFIER, "Expect parameter name."))
        while self.match(TokenType.COMMA):
            if len(parameters) >= 255:
                ParseError.error(self.peek(), "Can't have more than 255 parameters.")
            parameters.append(self.consume(TokenType.IDENTIFIER, "Expect parameter name."))
    self.consume(TokenType.RIGHT_PAREN, "Expect ')' after parameters.")
    
    self.consume(TokenType.LEFT_BRACE, f"Expect '{{' before {kind} body.")
    body = self.block_statement()
    return FunctionStmt(name, parameters, body)

The parser enforces the function syntax and collects the parameter names. Like arguments, there's a 255 parameter limit.

Function Objects and the Callable Interface

User-defined functions are represented as objects that implement the LoxCallable interface. I created a LoxFunction class in app/lox_function.py:

from app.lox_callable import LoxCallable
from app.environment import Environment
from app.return_error import Return

class LoxFunction(LoxCallable):
    def __init__(self, declaration, closure):
        self.declaration = declaration
        self.closure = closure
    
    def arity(self):
        return len(self.declaration.params)
    
    def call(self, interpreter, arguments: list[any]):
        environment = Environment(self.closure)
        for param, argument in zip(self.declaration.params, arguments):
            environment.define(param.lexeme, argument)
        try:
            interpreter.execute_block(self.declaration.body, environment)
        except Return as err:
            return err.value
        return None
        
    def __str__(self):
        return f"<fn {self.declaration.name.lexeme}>"

Key aspects of function execution:

Parameter Binding: Creates a new environment with the closure as its enclosing environment
Argument Assignment: Binds each argument to its corresponding parameter
Body Execution: Executes the function body in the new environment
Return Handling: Catches Return exceptions and returns their value (we go deeper into this in the next section)
Implicit Return: Returns None (Lox's nil) if no explicit return

Function Declaration Execution

In app/interpreter.py, function declarations create and bind function objects:

def visit_function_stmt(self, stmt: FunctionStmt):
    function = LoxFunction(stmt, self.environment)
    self.environment.define(stmt.name.lexeme, function)
    return None

The function captures the current environment as its closure - this is crucial for lexical scoping.

Function Call Execution

Function calls are executed in the visit_call method:

def visit_call(self, expr: Call):
    function = self.evaluate(expr.callee)
    args = [self.evaluate(arg) for arg in expr.arguments]
    if not isinstance(function, LoxCallable):
        raise LoxRuntimeError(expr.closing_paren, "Can only call functions and classes.")
    if len(args) != function.arity():
        raise LoxRuntimeError(expr.closing_paren, f"Expected {function.arity()} arguments but got {len(args)}.")
    return function.call(self, args)

The interpreter:

Evaluates the callee expression to get the function object
Evaluates all argument expressions
Validates that the result is callable
Checks that the argument count matches the function's arity
Calls the function with the interpreter and arguments

Return Statements

Return statements allow functions to produce values and exit early. They can appear anywhere within a function body:

fun max(a, b) {
    if (a > b) {
        return a;
    }
    return b;
}

fun findFirst(list, predicate) {
    for (var i = 0; i < list.length; i = i + 1) {
        if (predicate(list[i])) {
            return list[i];
        }
    }
    return nil;  // Not found
}

Return Statement Syntax Tree

I added a ReturnStmt class to app/stmt.py:

class ReturnStmt(Stmt):
    def __init__(self, keyword: Token, value: Expr):
        self.keyword = keyword
        self.value = value
    
    def accept(self, visitor: StmtVisitor):
        return visitor.visit_return_stmt(self)

The return statement holds:

keyword: The return token (for error reporting)
value: Optional expression to return (can be None)

Parsing Return Statements

In app/parser.py, I added parsing for return statements:

def statement(self):
    if (self.match(TokenType.FOR)):
        return self.for_statement()
    if (self.match(TokenType.IF)):
        return self.if_statement()
    if (self.match(TokenType.PRINT)):
        return self.print_statement()
    if (self.match(TokenType.RETURN)):
        return self.return_statement()
    # ... rest of statement types

def return_statement(self):
    keyword = self.previous()
    value = None
    if (not self.check(TokenType.SEMICOLON)):
        value = self.expression()
    self.consume(TokenType.SEMICOLON, "Expect ';' after return value.")
    return ReturnStmt(keyword, value)

If no expression follows return, the value defaults to None.

Return Implementation with Exceptions

Return statements are implemented using control flow exceptions - a technique where exceptions are used for non-error control flow. I created a Return class in app/return_error.py:

class Return(RuntimeError):
    def __init__(self, value):
        self.value = value

In app/interpreter.py, return statements throw this exception:

def visit_return_stmt(self, stmt: ReturnStmt):
    value = None
    if (stmt.value is not None):
        value = self.evaluate(stmt.value)
    raise Return(value)

This approach elegantly handles the complexity of unwinding the call stack from deeply nested statements back to the function call boundary.

Closures and Lexical Scoping

Closures are functions that capture and "close over" variables from their enclosing scope. This enables powerful programming patterns and is essential for functional programming.

Consider this example:

fun makeAccumulator() {
    var sum = 0;
    var count = 0;

    fun accumulate(value) {
        sum = sum + value;
        count = count + 1;
        return sum;
    }

    return accumulate;
}

var acc1 = makeAccumulator();
var acc2 = makeAccumulator();

print acc1(5);  // 5
print acc1(3);  // 8
print acc2(10); // 10
print acc2(2);  // 12

Each call to makeAccumulator creates a new closure that captures its own copy of sum and count. The inner accumulate function can access and modify these variables even after makeAccumulator has returned.

Closure Implementation

Closures work because LoxFunction captures the environment where the function was declared (not where it's called):

def visit_function_stmt(self, stmt: FunctionStmt):
    function = LoxFunction(stmt, self.environment)  # Captures current environment
    self.environment.define(stmt.name.lexeme, function)
    return None

When the function is called, it creates a new environment with the closure as its parent:

def call(self, interpreter, arguments: list[any]):
    environment = Environment(self.closure)  # New environment with closure as parent
    for param, argument in zip(self.declaration.params, arguments):
        environment.define(param.lexeme, argument)
    try:
        interpreter.execute_block(self.declaration.body, environment)
    except Return as err:
        return err.value
    return None

This creates a proper lexical scoping chain where:

Local variables and parameters are in the innermost environment
Closed-over variables are accessible through the environment chain
Each function call gets its own parameter bindings but shares closed-over variables

Practical Examples

Let's see functions in action with some practical examples:

Recursive Functions

fun fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 2) + fibonacci(n - 1);
}

print fibonacci(10); // 55

Higher-Order Functions

fun applyTwice(func, value) {
    return func(func(value));
}

fun double(x) {
    return x * 2;
}

print applyTwice(double, 5); // 20

Factory Functions

fun makeMultiplier(factor) {
    fun multiply(x) {
        return x * factor;
    }
    return multiply;
}

var double = makeMultiplier(2);
var triple = makeMultiplier(3);

print double(5); // 10
print triple(4); // 12

Conclusion

With the addition of functions, our Lox interpreter has gained tremendous expressive power. Functions enable:

Code Reuse: Write once, call many times
Abstraction: Hide implementation details behind clean interfaces
Modularity: Break complex problems into smaller, manageable pieces
Functional Programming: First-class functions enable elegant solutions to many problems

The implementation demonstrates several important concepts:

First-class functions: Functions as values that can be stored, passed, and returned
Lexical scoping: Variables are resolved based on where they were defined, not called
Closures: Functions that capture their lexical environment
Control flow exceptions: Using exceptions for non-error control flow

Our language now supports the fundamental building blocks of most programming paradigms. While we're still missing classes and inheritance, functions alone enable writing sophisticated programs with clear separation of concerns and reusable components. The foundation is solid for the advanced features we'll add next!

#compilers #lox-interpreter #programming-languages #software-engineering