Create Your Own Programming Language with Rust

Firstlang is a dynamically typed, interpreted programming language featuring Python-like syntax. It is designed as a pure interpreter with no external dependencies, making it suitable for learning language implementation via a tree-walking interpreter.

Key Features:

• Variables and assignments
• Functions with parameters
• Control flow (if/else, while)
• Recursion
• Boolean and integer types
• Comparison and arithmetic operators
• REPL for interactive exploration

The Calculator is a simple arithmetic expression language designed to introduce fundamental compiler concepts. It supports integer arithmetic, unary operators, and parentheses for grouping.

It features three distinct execution backends:

1. Interpreter: Direct AST evaluation (Fast compilation, slower execution, uses stable Rust).
2. VM: Bytecode compilation and stack-based execution (Compact bytecode, faster than interpreter, uses stable Rust).
3. JIT: LLVM-based just-in-time compilation to native machine code (Slowest compilation, fastest execution, requires nightly Rust and LLVM).

Supported syntax includes:

• Basic arithmetic: 1 + 2, 10 - 5
• Unary operators: -1, +5, -2 + 5
• Parentheses: (1 + 2), -(5 - 2)
• Multiple operations: 1 + 2 + 3

Firstlang is a complete interpreted programming language built as a step up from a simple calculator. Unlike a calculator that only evaluates arithmetic expressions, Firstlang supports full programming constructs including variables, functions, and control flow.

Key Features

• Variables and assignment: e.g., x = 42
• Functions with parameters: e.g., def add(a, b) { return a + b }
• Conditionals: if (condition) { ... } else { ... }
• Loops: while (condition) { ... }
• Recursion: Functions can call themselves.

Example: Recursive Fibonacci

def fib(n) {
    if (n < 2) {
        return n
    } else {
        return fib(n - 1) + fib(n - 2)
    }
}

fib(10)  # Returns 55

The project builds four increasingly complex languages to teach compiler construction concepts:

1. Calculator: Focuses on PEG basics, ASTs, and operators. Supports Interpreter, VM, and JIT execution.
2. Firstlang: Introduces variables, functions, control flow, and recursion using a tree-walking interpreter.
3. Secondlang: Adds static types, type inference, and optimization passes, compiling to native code via LLVM JIT.
4. Thirdlang: Adds Object-Oriented Programming (classes, methods, constructors) and manual memory management (heap allocation) using LLVM JIT.

LLVM IR (Intermediate Representation) is a low-level, typed, platform-independent representation that sits between your language's AST and machine assembly.

By compiling your language to LLVM IR instead of direct machine code, you leverage the LLVM compiler infrastructure to handle:

• Optimizations: World-class optimizations (like dead code elimination and constant propagation) are provided for free.
• Code Generation: LLVM translates the IR into optimized machine code for various architectures (x86, ARM, WebAssembly, etc.).

Think of it as a universal assembly language that allows you to write your compiler once and support many platforms automatically.

Secondlang follows a multi-stage pipeline to transform source code into executable native code:

1. Parser: Uses PEG grammar (pest) to convert source code into an Abstract Syntax Tree (AST).
2. Type System: Performs type checking and inference to catch errors at compile time.
3. Optimization: Uses the visitor pattern to perform passes that simplify the AST.
4. Code Generation: Uses inkwell to generate LLVM IR from the typed AST.
5. JIT Compilation: Compiles the LLVM IR into native machine code and executes it.

An Abstract Syntax Tree (AST) is a data structure that captures the structure and meaning of source code, rather than just its text. While a parser (like pest) provides a generic tree of syntax pairs, the AST translates those pairs into domain-specific nodes that represent actual operations and values.

In a calculator language:

• Operators (e.g., +, -) are nodes that dictate actions.
• Values (e.g., 1, 2) are nodes that provide data.

This separation allows the program to move from a raw string like "1 + 2" to a manageable tree structure where nesting (like "-1 + (2 + 3)") is represented naturally.

The project implements local type inference (also known as "flow-based" inference). Unlike Hindley-Milner, which can infer polymorphic types without annotations, local type inference requires explicit type annotations at function boundaries (parameters and return types) but infers types for all variables and expressions within function bodies.

Types "flow" forward from known sources (literals, parameters) through operations into variables. For example, in x = 1 + 2, the Int type of the literals flows through the + operator to the expression, and finally to the variable x.

The type environment (also called a symbol table or context) is a mapping of names to types. In this implementation, it is represented as:

type TypeEnv = HashMap<String, Type>;

Key characteristics:

• Extension: New bindings are added when variables are declared or when entering a function scope.
• Querying: Used to look up the type of a variable during expression typechecking.
• Scoping: The environment is scoped; inner scopes can shadow outer bindings.