Orin Interpreter

Orin is a dynamically-typed, object-oriented programming language interpreter implemented in Java. The project provides a complete execution environment, featuring a custom lexer, a recursive descent parser, a static semantic analysis pass, and a tree-walk interpreter.

While architecturally inspired by the book Crafting Interpreters, Orin implements distinct design choices for static analysis, control flow execution, and AST representation.

High-Level Architecture

The Orin execution pipeline processes source code through distinct, isolated stages:

flowchart LR
    Source([Source Code]) -->|scan| Scanner[Scanner]
    Scanner -->|tokens| Parser[Parser]
    Parser -->|ast| Resolver[Resolver]
    Resolver -.->|resolution map| Interpreter[Interpreter]
    Parser -->|ast| Interpreter
    Interpreter -->|evaluate| Runtime((Execution))

Loading

1. Lexical Analysis (Scanner): Consumes the raw source string and emits a sequence of Token objects. It handles single-character and multi-character operators, keywords, string/number literals, and strips comments/whitespace.
2. Parsing (Parser): A recursive descent parser that consumes the token stream to construct an Abstract Syntax Tree (AST). The grammar supports binary/unary precedence, statements, block scopes, and class definitions.
3. Semantic Analysis (Resolver): A static analysis pass that traverses the AST before execution. It validates lexical scoping rules, computes variable binding distances, and performs compile-time checks.
4. Evaluation (Interpreter): A tree-walk interpreter that executes the AST via post-order traversal using the Visitor pattern. It maintains environment chains, handles runtime type checking, and executes side effects.

Key Implementation Details

AST Representation and the Visitor Pattern

The syntax tree is defined in the grammar package (Stmt.java, Expression.java). Nodes implement an accept method to support the Visitor pattern. Both the Resolver and the Interpreter are implemented as visitors, allowing logic for static analysis and runtime evaluation to be cleanly decoupled from the AST node definitions.

Control Flow via Stack Unwinding

Control flow statements (break, continue, return) are implemented using Java Exceptions (Break, Continue, Return). During AST evaluation, throwing these lightweight exceptions allows the interpreter to instantly unwind the Java call stack out of deeply nested block evaluations and catch the control flow event at the appropriate loop or function boundary.

sequenceDiagram
    participant Interpreter
    participant LoopStmt
    participant NestedBlock
    participant BreakStmt
    
    Interpreter->>LoopStmt: execute()
    LoopStmt->>NestedBlock: execute()
    NestedBlock->>BreakStmt: execute()
    BreakStmt-->>LoopStmt: throw Break()
    Note over LoopStmt: Catches Break exception<br/>and breaks loop
    LoopStmt-->>Interpreter: evaluation continues

Loading

Lexical Scoping and Closures

To prevent dynamic scoping bugs in closures, Orin uses a two-pass resolution system. During the semantic analysis phase, the Resolver simulates block scopes and computes the "distance" (number of environment hops) between a variable's usage and its declaration. This distance is stored in a side-table (Map<Expression, Integer> locals).

Environment Lookup Example:
[Distance 0] Local Scope      (e.g., block variables)
    ↑
[Distance 1] Enclosing Scope  (e.g., function parameters)
    ↑
[Distance 2] Global Scope     (e.g., native functions)

At runtime, the Interpreter uses this exact distance to directly fetch the correct environment, ensuring that closures capture variables based on their lexical position, regardless of where the closure is eventually executed.

Dedicated ForStmt AST Node

A common pattern in simple interpreters is to desugar for loops into while loops during parsing. However, Orin intentionally preserves a distinct ForStmt node in its AST. This design decision correctly supports the continue statement; when a continue exception is caught during a for loop's execution, the interpreter must specifically evaluate the loop's increment expression before proceeding to the next iteration.

Static Analysis Constraints

The Resolver enforces several compile-time rules before the interpreter ever runs:

• Unused Variables: Tracks variable usage within scopes and emits an error if a variable is declared but never referenced before its scope ends.
• Self-Initialization: Prevents a variable from referencing itself in its own initializer.
• Contextual Keywords: Ensures that this and super are only used inside class methods, and return is only used inside functions.

Language Capabilities

Orin supports standard programming constructs:

• Dynamic Typing: Number (backed by Double), String, Boolean, and nil.
• Object-Oriented: class declarations, inheritance (extends), methods, constructor methods (init), this, and super.
• Functions: First-class functions, native functions (e.g., clock()), and closures.
• Control Flow: if/else, while, for, break, continue, return.

Example

class Doughnut {
  cook() {
    print "Fry until golden brown.";
  }
}

class BostonCream extends Doughnut {
  init() {
    this.filling = "custard";
  }

  cook() {
    super.cook();
    print "Pipe full of " + this.filling + " and coat with chocolate.";
  }
}

BostonCream().cook();

Build and Run Instructions

The project uses Gradle and requires Java 21.

Building

./gradlew build

Execution

Run an Orin source file:

./gradlew run --args="path/to/script.orin"

Note: Depending on the configured runner wrapper, you can also use orinc <path>.

Execute a source string directly:

./gradlew run --args="--source 'print \"Hello, World!\";'"

Launch the interactive REPL:

./gradlew run