Compiler Internals

A comprehensive technical deep-dive into the MathViz compiler architecture, implementation details, and optimization strategies. This document is intended for contributors, language implementers, and anyone interested in compiler design.

Overview

The MathViz compiler is a multi-stage source-to-source transpiler that transforms .mviz source files into optimized Python code. It follows a traditional compiler pipeline architecture with additional analysis passes for performance optimization.

Key Design Decisions

• Immutable AST: All AST nodes are frozen dataclasses for thread safety and predictability
• Visitor Pattern: Tree traversal via the visitor pattern enables clean separation of concerns
• Multi-pass Architecture: Separate analysis passes for type checking, purity, complexity, and parallelization
• Optional Strictness: Type errors can be warnings or fatal errors depending on configuration
• Zero Runtime Overhead: No MathViz runtime library required; output is standalone Python

Compilation Pipeline

The compiler executes the following stages in order. Each stage is independent and can be enabled/disabled via the CompilationPipeline configuration.

┌─────────────────────────────────────────────────────────────────────────────┐
│                         MathViz Compilation Pipeline                         │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                             │
│   Source Code (.mviz)                                                       │
│         │                                                                   │
│         ▼                                                                   │
│   ┌─────────────┐                                                           │
│   │   LEXER     │  Tokenization: Unicode math symbols, f-strings, keywords  │
│   │  lexer.py   │  Output: Token stream                                     │
│   └──────┬──────┘                                                           │
│          │                                                                  │
│          ▼                                                                  │
│   ┌─────────────┐                                                           │
│   │   PARSER    │  Recursive descent parser with operator precedence        │
│   │  parser.py  │  Output: Abstract Syntax Tree (AST)                       │
│   └──────┬──────┘                                                           │
│          │                                                                  │
│          ▼                                                                  │
│   ┌─────────────┐                                                           │
│   │   MODULE    │  Resolves `use` statements, loads dependencies            │
│   │   LOADER    │  Detects circular dependencies                            │
│   └──────┬──────┘                                                           │
│          │                                                                  │
│          ▼                                                                  │
│   ┌─────────────┐                                                           │
│   │    TYPE     │  Hindley-Milner style inference with bidirectional hints  │
│   │   CHECKER   │  Output: Type errors, function signatures                 │
│   └──────┬──────┘                                                           │
│          │                                                                  │
│          ├────────────────────┬────────────────────┐                        │
│          ▼                    ▼                    ▼                        │
│   ┌─────────────┐      ┌─────────────┐      ┌─────────────┐                 │
│   │   PURITY    │      │ COMPLEXITY  │      │  PARALLEL   │                 │
│   │  ANALYZER   │      │  ANALYZER   │      │  ANALYZER   │                 │
│   └──────┬──────┘      └──────┬──────┘      └──────┬──────┘                 │
│          │                    │                    │                        │
│          └────────────────────┼────────────────────┘                        │
│                               │                                             │
│                               ▼                                             │
│                        ┌─────────────┐                                      │
│                        │    CODE     │  Emits Python with Numba decorators  │
│                        │  GENERATOR  │  Output: Executable Python code      │
│                        └──────┬──────┘                                      │
│                               │                                             │
│                               ▼                                             │
│                        Generated Python (.py)                               │
│                                                                             │
└─────────────────────────────────────────────────────────────────────────────┘
        

File Structure

Stage 1: Lexical Analysis

The lexer (lexer.py) transforms source code into a stream of tokens. It supports both ASCII and Unicode operators for mathematical notation.

# Input: let x = {1, 2} ∪ {3, 4}
# Output tokens:
Token(LET, "let")
Token(IDENTIFIER, "x")
Token(ASSIGN, "=")
Token(LBRACE, "{")
Token(INTEGER, 1)
Token(COMMA, ",")
Token(INTEGER, 2)
Token(RBRACE, "}")
Token(UNION, "∪")        # Unicode operator!
Token(LBRACE, "{")
Token(INTEGER, 3)
Token(COMMA, ",")
Token(INTEGER, 4)
Token(RBRACE, "}")
Token(EOF, None)

Stage 2: Parsing

The parser (parser.py) is a hand-written recursive descent parser with Pratt parsing for expressions. It produces an immutable Abstract Syntax Tree.

Abstract Syntax Tree

The AST (ast_nodes.py) consists of over 100 node types organized into hierarchies for expressions, statements, patterns, and types.

ASTNode (abstract base)
├── Expression
│   ├── Literal (Integer, Float, String, Boolean, None)
│   ├── Identifier
│   ├── BinaryExpression
│   ├── UnaryExpression
│   ├── CallExpression
│   ├── MemberAccess
│   ├── IndexExpression
│   ├── LambdaExpression (PipeLambda)
│   ├── MatchExpression
│   ├── ConditionalExpression (ternary)
│   ├── RangeExpression
│   ├── CollectionLiteral (List, Set, Dict, Tuple)
│   └── FString
├── Statement
│   ├── LetStatement
│   ├── AssignmentStatement
│   ├── FunctionDef
│   ├── ClassDef / SceneDef
│   ├── StructDef / EnumDef / ImplBlock
│   ├── IfStatement / IfLetStatement
│   ├── ForStatement / WhileStatement / LoopStatement
│   ├── MatchStatement
│   ├── ReturnStatement / BreakStatement / ContinueStatement
│   └── UseStatement / ModuleDecl
├── Pattern (for pattern matching)
│   ├── LiteralPattern
│   ├── IdentifierPattern
│   ├── TuplePattern / ListPattern
│   ├── ConstructorPattern
│   ├── OrPattern / BindingPattern
│   └── WildcardPattern / RestPattern
└── TypeAnnotation
    ├── SimpleType
    ├── GenericType
    └── FunctionType

@dataclass(frozen=True, slots=True)
class BinaryExpression(Expression):
    left: Expression
    operator: BinaryOperator
    right: Expression
    location: Optional[SourceLocation] = None

    def accept(self, visitor: ASTVisitor) -> Any:
        return visitor.visit_binary_expression(self)

Stage 3: Type Checking

The type checker (type_checker.py) implements bidirectional type inference with support for generics, structs, enums, and algebraic data types.

# Primitive types
INT_TYPE = PrimitiveType("Int")
FLOAT_TYPE = PrimitiveType("Float")
BOOL_TYPE = PrimitiveType("Bool")
STRING_TYPE = PrimitiveType("String")
NONE_TYPE = PrimitiveType("None")

# Math types
VEC_TYPE = ArrayType(FLOAT_TYPE, 1)  # Vector
MAT_TYPE = ArrayType(FLOAT_TYPE, 2)  # Matrix

# Special types
ANY_TYPE = AnyType()  # Accepts anything

Analysis Passes

Multiple analysis passes run in parallel to gather information for optimization and code generation.

class Purity(Enum):
    PURE = auto()           # No side effects
    READ_ONLY = auto()      # Reads external state
    IMPURE = auto()         # Has side effects
    UNKNOWN = auto()        # Cannot determine

class Complexity(Enum):
    O_1 = "O(1)"           # Constant
    O_LOG_N = "O(log n)"   # Logarithmic
    O_N = "O(n)"           # Linear
    O_N_LOG_N = "O(n log n)"
    O_N_SQUARED = "O(n²)"  # Quadratic
    O_N_CUBED = "O(n³)"    # Cubic
    O_2_N = "O(2ⁿ)"        # Exponential

Stage 4: Code Generation

The code generator (codegen.py) transforms the AST into executable Python code, handling operator translation, Manim integration, and Numba decorators.

// MathViz
struct Point {
    x: Float
    y: Float
}

impl Point {
    fn new(x: Float, y: Float) -> Point {
        return Point { x: x, y: y }
    }
}

# Generated Python
@dataclass
class Point:
    x: float
    y: float

def Point_new(x: float, y: float) -> Point:
    return Point(x=x, y=y)

// MathViz
scene HelloWorld {
    fn construct(self) {
        let text = Text("Hello")
        play(Write(text))
    }
}

# Generated Python
from manim import *

class HelloWorld(Scene):
    def construct(self):
        text = Text('Hello')
        self.play(Write(text))

Optimization Passes

The compiler includes multiple optimization passes that can be enabled for high-performance numerical code.

Numba JIT Integration

Functions that pass purity analysis are automatically decorated with @njit for Just-In-Time compilation to native code.

# Automatic JIT decoration
@njit(cache=True)
def compute_sum(n: int) -> int:
    total = 0
    for i in range(0, n):
        total = (total + i)
    return total

Constant Folding

The const_fold.py module (99KB) implements multiple optimization passes:

• Constant Folding: Evaluate constant expressions at compile time
• Constant Propagation: Replace variables with known constant values
• Dead Code Elimination: Remove unreachable code
• Algebraic Simplification: Simplify expressions (x * 1 → x, x + 0 → x)
• Strength Reduction: Replace expensive ops (x * 2 → x << 1)
• Common Subexpression Elimination: Reuse repeated computations

Vectorization

The vectorizer.py module detects patterns that can be vectorized to NumPy operations for SIMD acceleration:

• Element-wise array operations
• Reduction operations (sum, product, min, max)
• Stencil computations
• Broadcasting patterns

Memory Optimization

The memory_optimizer.py module optimizes memory access patterns:

• Buffer reuse analysis
• In-place operation detection
• Cache-friendly loop ordering
• Temporary variable elimination
• Memory pool generation

Summary

The MathViz compiler is a production-grade source-to-source transpiler with:

• 31,000+ lines of carefully crafted Python code
• 22 modules covering all aspects of compilation
• 8-stage pipeline with optional analysis passes
• Full type inference with generics and algebraic data types
• Automatic optimization via Numba JIT, vectorization, and constant folding
• Rich diagnostics with source locations and suggestions