Eucalypt Architecture

This document provides a comprehensive overview of Eucalypt's design and implementation architecture.

Overview

Eucalypt is a functional programming language and tool for generating, templating, rendering, and processing structured data formats like YAML, JSON, and TOML. Written in Rust (~44,000 lines), it features a classic multi-phase compiler design with an STG (Spineless Tagless G-machine) runtime for lazy evaluation.

System Architecture

High-Level Pipeline

Source Code (*.eu files)
        │
        ▼
┌───────────────────────┐
│    Parsing Phase      │  src/syntax/
│  Lexer → Parser → AST │
└───────────────────────┘
        │
        ▼
┌───────────────────────┐
│     Core Phase        │  src/core/
│  Desugar → Cook →     │
│  Transform → Verify   │
└───────────────────────┘
        │
        ▼
┌───────────────────────┐
│   Evaluation Phase    │  src/eval/
│  STG Compile → VM →   │
│  Memory Management    │
└───────────────────────┘
        │
        ▼
┌───────────────────────┐
│    Export Phase       │  src/export/
│  JSON/YAML/TOML/etc   │
└───────────────────────┘

Module Structure

eucalypt/
├── src/
│   ├── bin/eu.rs           # CLI entry point
│   ├── lib.rs              # Library root
│   ├── common/             # Shared utilities
│   ├── syntax/             # Parsing and AST
│   │   └── rowan/          # Rowan-based incremental parser
│   ├── core/               # Core expression representation
│   │   ├── desugar/        # AST to core transformation
│   │   ├── cook/           # Operator fixity resolution
│   │   ├── transform/      # Expression transformations
│   │   ├── simplify/       # Optimisation passes
│   │   ├── inline/         # Inlining passes
│   │   ├── verify/         # Validation
│   │   └── analyse/        # Program analysis
│   ├── eval/               # Evaluation engine
│   │   ├── stg/            # STG syntax and compiler
│   │   ├── machine/        # Virtual machine
│   │   └── memory/         # Heap and garbage collection
│   ├── driver/             # CLI orchestration
│   ├── export/             # Output format generation
│   └── import/             # Input format parsing
├── lib/                    # Standard library (eucalypt source)
│   ├── prelude.eu          # Core prelude
│   ├── test.eu             # Test framework
│   └── markup.eu           # Markup utilities
└── docs/                   # Documentation

Parsing Pipeline

The parsing pipeline transforms source text into a structured AST using Rowan, an incremental parsing library that preserves full source fidelity including whitespace and comments.

Lexer

Implementation: src/syntax/rowan/lex.rs, src/syntax/rowan/string_lex.rs

The lexer (Lexer<C>) tokenises source text into a stream of SyntaxKind tokens:

#![allow(unused)]
fn main() {
pub struct Lexer<C: Iterator<Item = char>> {
    chars: Peekable<C>,           // Character stream with lookahead
    location: ByteIndex,           // Source position tracking
    last_token: Option<SyntaxKind>, // Context for disambiguation
    whitespace_since_last_token: bool,
    token_buffer: VecDeque<(SyntaxKind, Span)>,
}
}

Key features:

• Unicode-aware identifier and operator recognition
• Context-sensitive tokenisation (distinguishes OPEN_PAREN from OPEN_PAREN_APPLY)
• String pattern lexing with interpolation support ("Hello {name}")
• Preserves trivia (whitespace, comments) for full-fidelity AST

Token categories:

• Delimiters: `{ } ( ) [ ] : , ``
• Identifiers: foo, 'quoted name', +, &&
• Literals: Numbers, strings, symbols (:keyword)
• Annotations: Whitespace, comments (#)

Parser

Implementation: src/syntax/rowan/parse.rs

The parser uses an event-driven recursive descent approach:

#![allow(unused)]
fn main() {
pub struct Parser<'text> {
    tokens: Vec<(SyntaxKind, &'text str)>,
    next_token: usize,
    sink_stack: Vec<Box<dyn EventSink>>,
    errors: Vec<ParseError>,
}
}

Parse events:

#![allow(unused)]
fn main() {
enum ParseEvent {
    StartNode(SyntaxKind),  // Begin syntax node
    Finish,                  // Complete node
    Token(SyntaxKind),      // Include token
}
}

Key parsing methods:

• parse_unit() - Top-level file (no braces required)
• parse_expression() / parse_soup() - Expression sequences
• parse_block_expression() - { ... } blocks with declarations
• parse_string_pattern() - Interpolated strings

The parser maintains systematic error recovery for LSP support:

• Expression-level recovery: missing }, ], or ) delimiters trigger recover_to() which advances to the next enclosing boundary, wrapping consumed tokens in ERROR_STOWAWAYS.
• Declaration-level recovery: headless declarations (e.g. a trailing backtick with no following name: value) still produce a DECLARATION node with an empty head. Declaration::validate() detects this and emits a MalformedDeclarationHead error; the ERROR SyntaxKind is defined for future use but is not yet emitted by the parser.
• All parser panics in validate.rs are converted to proper errors.

AST

Implementation: src/syntax/rowan/ast.rs

The AST uses a two-layer design:

1. SyntaxNode (Rowan) - Rich, source-preserving tree
2. AST Nodes - Typed wrappers via macros

#![allow(unused)]
fn main() {
macro_rules! ast_node {
    ($ast:ident, $kind:ident) => {
        pub struct $ast(SyntaxNode);
        impl AstNode for $ast { ... }
    }
}
}

Key AST types:

Core Expression Representation

The core representation is an intermediate language that facilitates powerful transformations while maintaining source information for error reporting.

Expression Type

Implementation: src/core/expr.rs

The Expr<T> enum (where T: BoundTerm<String>) represents all expression forms:

#![allow(unused)]
fn main() {
pub enum Expr<T> {
    // Variables
    Var(Smid, Var<String>),           // Free or bound variable

    // Primitives
    Literal(Smid, Primitive),          // Number, string, symbol, bool, null

    // Binding forms
    Let(Smid, LetScope<T>, LetType),   // Recursive let binding
    Lam(Smid, bool, LamScope<T>),      // Lambda abstraction

    // Application
    App(Smid, T, Vec<T>),              // Function application

    // Data structures
    List(Smid, Vec<T>),                // List literal
    Block(Smid, BlockMap<T>),          // Object/record literal

    // Operators (pre-cooking)
    Operator(Smid, Fixity, Precedence, T),
    Soup(Smid, Vec<T>),                // Unresolved operator soup

    // Anaphora (implicit parameters)
    BlockAnaphor(Smid, ...),
    ExprAnaphor(Smid, ...),

    // Access
    Lookup(Smid, T, String, Option<T>), // Property access

    // Metadata
    Meta(Smid, T, T),                   // Expression with metadata

    // Intrinsics
    Intrinsic(Smid, String),           // Built-in function reference

    // Error nodes
    ErrUnresolved, ErrRedeclaration, ...
}
}

Primitive types:

#![allow(unused)]
fn main() {
pub enum Primitive {
    Str(String),
    Sym(String),
    Num(Number),
    Bool(bool),
    Null,
}
}

Standard wrapper: RcExpr provides reference-counted immutable expressions with substitution and transformation methods.

Transformation Pipeline

The core pipeline transforms expressions through several phases:

AST → Desugar → Cook → Simplify → Inline → Verify → STG

Desugaring

Implementation: src/core/desugar/

Transforms parsed AST into core expressions:

• Converts block declarations into recursive let bindings
• Extracts targets and documentation metadata
• Handles imports and cross-file references
• Processes both native AST and embedded data (JSON/YAML)

Cooking

Implementation: src/core/cook/

Resolves operator precedence and anaphora:

1. Fixity distribution - Propagate operator precedence info
2. Anaphor filling - Infer missing implicit parameters ((+ 10) → (_ + 10))
3. Shunting yard - Apply precedence climbing to linearise operator soup
4. Anaphor processing - Wrap lambda abstractions around anaphoric expressions

Example transformation:

(+ 10)        →  (λ _ . (_ + 10))
a + b * c     →  (+ a (* b c))      // with standard precedence

Simplification and Inlining

Implementation: src/core/simplify/, src/core/inline/

• Compression - Remove eliminated bindings
• Pruning - Dead code elimination
• Inlining - Inline marked expressions

Verification

Implementation: src/core/verify/

Validates transformed expressions before STG compilation:

• Binding verification
• Content validation

STG Compilation and Evaluation Model

Eucalypt uses a Spineless Tagless G-machine (STG) as its evaluation model, providing lazy evaluation with memoisation.

Two execution engines share one STG

The STG syntax described below is the intermediate representation that both of eucalypt's execution engines consume. The engines differ only in how they run that syntax, not in what it means:

• The HeapSyn tree-walk engine (src/eval/machine/vm.rs) walks a materialised STG tree of heap-allocated nodes directly. It was historically the only engine and is retained as the performance baseline and the differential-testing oracle. Select it with EU_HEAPSYN=1.
• The bytecode engine (BV1) (src/eval/bytecode/) compiles the same STG syntax to a flat bytecode program and runs that. Since 0.12.0 it is the default; EU_BYTECODE=1 is a now-redundant explicit opt-in, and EU_HEAPSYN=1 takes precedence over it.

Both engines produce byte-identical rendered output on every input — this is enforced by a differential test suite (src/eval/bytecode/differential.rs) and is the invariant that lets the bytecode engine be the default while HeapSyn remains as a cross-check.

The next four subsections (STG Syntax, STG Compiler, the tree-walk Virtual Machine, Continuations and Lazy Evaluation) describe the shared IR and the HeapSyn engine that walks it. The Bytecode Engine below then describes how the default engine executes the same syntax.

STG Syntax

Implementation: src/eval/stg/syntax.rs

The STG syntax represents executable code:

#![allow(unused)]
fn main() {
pub enum StgSyn {
    Atom { evaluand: Ref },              // Value or reference
    Case { scrutinee, branches, fallback }, // Pattern matching (evaluation point)
    Cons { tag: Tag, args: Vec<Ref> },   // Data constructor
    App { callable: Ref, args: Vec<Ref> }, // Function application
    Bif { intrinsic: u8, args: Vec<Ref> }, // Built-in intrinsic
    Let { bindings: Vec<LambdaForm>, body }, // Non-recursive let
    LetRec { bindings: Vec<LambdaForm>, body }, // Recursive let
    Ann { smid: Smid, body },            // Source annotation
    Meta { meta: Ref, body: Ref },       // Metadata wrapper
    DeMeta { scrutinee, handler, or_else }, // Metadata destructure
    BlackHole,                            // Uninitialized marker
}
}

Reference types:

#![allow(unused)]
fn main() {
pub enum Reference<T> {
    L(usize),  // Local environment index
    G(usize),  // Global environment index
    V(T),      // Direct value (Native)
}
}

Lambda forms control laziness:

• Lambda - Function with explicit arity
• Thunk - Lazy expression (evaluated and updated in-place)
• Value - Already in WHNF (no update needed)

STG Compiler

Implementation: src/eval/stg/compiler.rs

The compiler transforms core expressions to STG syntax:

#![allow(unused)]
fn main() {
impl Compiler {
    fn compile_body(&mut self, expr: &RcExpr) -> ProtoSyntax;
    fn compile_binding(&mut self, expr: &RcExpr) -> ProtoBinding;
    fn compile_lambda(&mut self, expr: &RcExpr) -> ProtoSyntax;
    fn compile_application(&mut self, f: &RcExpr, args: &[RcExpr]) -> ProtoSyntax;
}
}

Key decisions:

• Thunk creation: Expressions not in WHNF and used more than once become thunks
• WHNF detection: Constructors, native values, and metadata wrappers are WHNF
• Deferred compilation: ProtoSyntax allows deferring binding construction until environment size is known

Virtual Machine

Implementation: src/eval/machine/vm.rs

The STG machine is a state machine executing closures:

#![allow(unused)]
fn main() {
pub struct MachineState {
    root_env: SynEnvPtr,           // Empty root environment
    closure: SynClosure,           // Current (code, environment) pair
    globals: SynEnvPtr,            // Global bindings
    stack: Vec<Continuation>,      // Continuation stack
    terminated: bool,
    annotation: Smid,              // Current source location
}
}

Execution loop:

#![allow(unused)]
fn main() {
fn run(&mut self) {
    while !self.terminated {
        if self.gc_check_needed() {
            self.collect_garbage();
        }
        self.step();
    }
}
}

Instruction dispatch (handle_instruction):

Continuations

Implementation: src/eval/machine/cont.rs

Four continuation types manage control flow:

1. Branch - Pattern matching branches for CASE
2. Update - Deferred thunk update (memoisation)
3. ApplyTo - Pending arguments for function application
4. DeMeta - Metadata destructuring handler

Lazy Evaluation

Laziness is achieved through thunks and updates:

1. Thunk creation (compile time): Non-WHNF expressions become LambdaForm::Thunk
2. Thunk evaluation (runtime): When a thunk is entered, push Update continuation
3. Memoisation: After evaluation, update the environment slot with the result

#![allow(unused)]
fn main() {
// When entering a local reference
if closure.update() {
    stack.push(Continuation::Update { environment, index });
}

// After evaluation completes
Continuation::Update { environment, index } => {
    self.update(environment, index);  // Replace thunk with result
}
}

The Bytecode Engine (BV1, the default)

Implementation: src/eval/bytecode/ (opcode.rs, program.rs, encode.rs, closure.rs, cont.rs, env_builder.rs, machine.rs, predecode.rs)

The default engine compiles STG syntax one step further, into a flat bytecode program, and interprets that. The motivation is a garbage-collection one: in the HeapSyn engine the code itself is a tree of heap-allocated HeapSyn nodes, so every code node must be scanned, marked and potentially evacuated by the collector. Bytecode moves the code off the GC heap entirely — it lives in a plain Vec<u8> that never moves — so closures need no code-pointer fix-up during collection.

What gets compiled

encode.rs flattens each STG tree into a post-order byte stream: children are emitted first at low offsets and parents refer to them by absolute u32 offset (a CodeRef). There is one opcode per StgSyn variant — Atom, Case, Cons, App, Bif, Let, LetRec, Meta, DeMeta and so on (opcode.rs) — plus two encoder-introduced superinstructions: DirectApp for known-callable applications and FusedPrimop, which collapses the force-both-operands-then-dispatch tree of a whitelisted set of strict binary primops (arithmetic and comparison) into a single opcode.

Values that cannot live in a byte stream — heap-backed strings and interned symbols — are hoisted once into a constant pool (program.rs) and referenced by index; they are rooted for the whole run. The compiled BytecodeProgram also carries pre-encoded templates (data-constructor nodes, partial-application trampolines, fixed-shape apply nodes) so that intrinsics and the IO runner can build closures with no per-call code allocation.

A bytecode runtime value (closure.rs) is either a code closure — an info table carrying a CodeRef plus a pointer to its environment frame — or a WHNF native carried directly. The environment-frame cactus stack and the continuation model are shared verbatim with the HeapSyn engine (cont.rs mirrors machine::cont::Continuation one-for-one, with CodeRef offsets in place of node pointers); only the code representation differs.

How dispatch works

The interpreter loop (machine.rs) keeps a program counter into the code buffer. Each step reads one opcode byte, decodes it (Op::from_u8), reads that opcode's inline operands from the following bytes, and acts — pushing continuations, allocating environment frames, forcing thunks and returning data constructors exactly as the tree-walk machine does. GC is polled on a countdown (every 500 steps by default), matching HeapSyn.

The pre-decoded IR (lever a, EU_PREDECODE)

The classic byte-stream interpreter re-reads and re-decodes operands from the buffer on every tick. The pre-decoded execution IR (predecode.rs) removes that per-tick cost: at machine load the whole program is decoded once into a flat array of fixed-width, typed Instr records (16 bytes each) plus a set of off-heap side pools (argument-reference lists, application arg ordinals, Let/LetRec form headers and densified Case branch tables). Dispatch then reads typed fields instead of re-parsing bytes. Two representation changes accompany the decode: a CodeRef becomes an instruction ordinal rather than a byte offset, and source annotations move into a side table keyed by ordinal so Ann nodes are peeled at decode time and never cost a dispatch step. The byte stream is retained unchanged as the serialisation format; pre-decoding is purely an execution-time transform, and with pre-decoded dispatch off, behaviour is byte-identical to the byte-stream path. Nothing in the pre-decoded structures is a GC pointer, so code stays off the collector's scan set just as the byte stream does.

As of Phase 2 of the lever-(a) rollout (eu-vcr8), pre-decoded dispatch is the default — unset or EU_PREDECODE=1 selects it; EU_PREDECODE=0 opts out to the byte-dispatch path, which is retained and soaked through this release (CI's test-byte-dispatch-baseline job keeps it exercised) before Phase 3 deletes it, per the design's phased landing plan (docs/superpowers/specs/2026-07-13-predecoded-execution-ir-design.md §6).

Why bytecode is the default, and the performance story

The bytecode engine wins decisively on garbage-collection-heavy and allocation-bound workloads, where keeping code off the managed heap and out of every mark/sweep pays for itself; it also starts faster, because the prelude ships pre-encoded in the blob (below) rather than being compiled from source. On op-dense, allocation-light workloads the byte-stream interpreter's per-tick re-decode cost historically left it slower per tick than the HeapSyn tree-walk; closing that remaining gap is exactly what the pre-decoded IR and the fused-primop superinstructions target.

All engine-versus-engine performance numbers in this project are governed by a checked-in measurement protocol (docs/superpowers/engine-ab/PROTOCOL.md): deterministic VM ticks and allocation counts first, interleaved median-of-N wall timings second, a canonical eight-bench suite, and a mandatory confidence label (measured-verified / measured-single / projected) on every figure. Because those figures are machine- and load-sensitive and evolve release to release, this document deliberately states the shape of the trade-off rather than quoting ratios; consult the protocol's ledger (results.jsonl) and the dated transition-review reports under docs/superpowers/reports/ for current, labelled measurements.

Memory Management and Garbage Collection

Eucalypt uses an Immix-inspired memory layout with mark-and-sweep collection.

Memory Layout

Implementation: src/eval/memory/heap.rs, src/eval/memory/bump.rs

Block (32KB)
├── Line 0 (128B) ┐
├── Line 1 (128B) │ 256 lines per block
├── ...           │
└── Line 255      ┘

Size classes:

• Small (< 128 bytes) - Single line
• Medium (128B - 32KB) - Multiple lines within block
• Large (> 32KB) - Dedicated Large Object Block

Heap state:

#![allow(unused)]
fn main() {
pub struct HeapState {
    head: Option<BumpBlock>,           // Active small allocation
    overflow: Option<BumpBlock>,       // Active medium allocation
    recycled: VecDeque<BumpBlock>,     // Blocks with reusable holes
    rest: VecDeque<BumpBlock>,         // Used blocks pending collection
    lobs: Vec<LargeObjectBlock>,       // Large objects
}
}

Object Headers

Implementation: src/eval/memory/header.rs

Every object has a 16-byte header:

#![allow(unused)]
fn main() {
pub struct AllocHeader {
    bits: HeaderBits,                  // Mark bit + forwarded flag
    alloc_length: u32,                 // Object size
    forwarded_to: Option<NonNull<()>>, // For potential evacuation
}
}

Garbage Collection

Implementation: src/eval/memory/collect.rs

Mark phase:

1. Reset line maps across all blocks
2. Breadth-first root scanning from machine state
3. Transitive closure following object references
4. Mark lines containing live objects

Sweep phase:

1. Scan line maps in each block
2. Identify holes (2+ consecutive free lines)
3. Move recyclable blocks to recycled list

Collection triggering:

• When --heap-limit-mib is set and limit exceeded
• Check performed every 500 VM execution steps
• Emergency collection on allocation failure

See gc-implementation.md for detailed analysis.

The Prelude and Standard Library

Intrinsic Functions

Implementation: src/eval/intrinsics.rs, src/eval/stg/

Built-in functions are implemented in Rust and indexed by position:

Categories:

• Control flow: __IF, __PANIC, __TRUE, __FALSE, __NULL
• Lists: __CONS, __HEAD, __TAIL, __NIL, __REVERSE
• Blocks: __MERGE, __DEEPMERGE, __ELEMENTS, __BLOCK, __LOOKUP
• Arithmetic: __ADD, __SUB, __MUL, __DIV, __MOD, comparisons
• Strings: __STR, __SPLIT, __JOIN, __MATCH, __FMT
• Metadata: __META, __WITHMETA
• Time: __ZDT, __ZDT.PARSE, __ZDT.FORMAT
• I/O: __io.ENV, __io.EPOCHTIME
• Emission: __RENDER, __EMIT* family

Each intrinsic implements the StgIntrinsic trait with direct access to machine state.

Prelude

Implementation: lib/prelude.eu

The prelude (~29KB) is written entirely in eucalypt, wrapping intrinsics with ergonomic functions:

List functions:

• take, drop, nth (!!), fold/foldr, map, filter
• append (++), concat, reverse, zip, group-by, qsort

Block functions:

• merge-all, keys, values, map-kv, map-keys, map-values
• lookup-path, alter-value, update-value

Combinators:

• identity, const, compose (∘, ;), flip, curry, uncurry

String functions:

• str.split, str.join, str.match, str.fmt, str.letters

Loading:

• Prelude is embedded in the binary at compile time
• Loaded by default unless --no-prelude / -Q flag is used

The Pre-Compiled Prelude Blob

Implementation: src/eval/stg/blob.rs, generated by cargo xtask prelude-compile

Compiling ~2,200 lines of prelude source on every eu invocation would dominate startup, so the prelude is pre-compiled once, at development time, into lib/prelude.blob and embedded in the binary. The blob is serialised with postcard (a compact binary format) and is the runtime's default source for the prelude; the build falls back to compiling from source only when the blob is absent or stale.

Staleness is detected by a hash: the blob records SHA-256(lib/prelude.eu ‖ bytecode-wire-format-version), and build.rs recomputes it. Folding the bytecode wire-format version (currently 3) into the hash means a change to the serialised code layout invalidates a stale-format blob even when the prelude source itself is unchanged.

The blob is not a single artefact but a set of sections, each a snapshot or derived artefact of a specific compiler stage. blob.rs's module documentation is the authoritative anatomy; the load-bearing sections are:

A naming convention keeps these honest: the word core is reserved for fields that are a faithful snapshot of a named pipeline stage at a named granularity (hence desugared_unit_cores — the desugared stage, per unit). A field that has been pre-expanded, re-tagged or otherwise transformed beyond a stage snapshot is named for the artefact it actually is — hence inlinable_bindings, not a "core".

Driver and CLI Architecture

Entry Point

Implementation: src/bin/eu.rs, src/driver/options.rs

The CLI uses clap v4 with derive macros:

#![allow(unused)]
fn main() {
#[derive(Parser)]
struct EucalyptCli {
    #[command(subcommand)]
    command: Option<Commands>,
    files: Vec<String>,
    // Global options...
}

enum Commands {
    Run(RunArgs),
    Test(TestArgs),
    Dump(DumpArgs),
    Fmt(FmtArgs),
    Explain(ExplainArgs),
    ListTargets(ListTargetsArgs),
    Version,
}
}

Modes of Operation

Run (default):

eu file.eu                    # Implicit run
eu -e "expression" file.eu    # With evaluand
eu -x json file.eu            # JSON output
eu -t target file.eu          # Select target

Test:

eu test tests/              # Run all tests in directory
eu test -t specific file.eu  # Run specific test target

Format:

eu fmt file.eu              # Print formatted to stdout
eu fmt --write file.eu      # Modify in place
eu fmt --check file.eu      # Check formatting (exit 1 if needs format)

Dump:

eu dump ast file.eu          # Dump AST
eu dump desugared file.eu    # Dump after desugaring
eu dump stg file.eu          # Dump STG syntax
eu dump runtime              # Dump intrinsic definitions

Output Formats

Implementation: src/export/

Emitters for each format implement the Emitter trait:

• YAML (yaml.rs) - Uses yaml_rust, supports tags from metadata
• JSON (json.rs) - Uses serde_json
• TOML (toml.rs) - Structured output
• Text (text.rs) - Plain text
• EDN (edn.rs) - Clojure-like format
• HTML (html.rs) - Markup with serialisation

Input Handling

Inputs are merged in order:

1. Prologue: Prelude, config files, build metadata, IO block
2. Explicit: Files and options (-c/--collect-as)
3. Epilogue: CLI evaluand (-e)

Names from earlier inputs are available to later inputs.

Key Design Decisions and Trade-offs

Why STG?

The STG machine provides a well-defined reference point for lazy functional language implementation:

• Clear semantics for lazy evaluation with memoisation
• Established compilation strategies
• Potential for future optimisations

Trade-off: More complex than direct interpretation but provides a solid foundation.

Why Rowan for Parsing?

Rowan provides:

• Incremental parsing for IDE support
• Full source fidelity (preserves whitespace and comments)
• Error recovery for partial parsing

Trade-off: More complex API than traditional parser generators.

Core as Intermediate Language

The core representation enables powerful transformations:

• User-definable operator precedence resolved by syntax transformation
• Block semantics (binding vs structuring) separated cleanly
• Source information preserved through Smid for error reporting

Trade-off: Additional compilation phase, but enables experimentation.

Block Duality

Eucalypt blocks serve two roles:

1. Name binding - Like let expressions
2. Data structuring - Like objects/records

The core phase separates these into distinct Let and Block expressions.

Trade-off: Elegant surface syntax at cost of semantic complexity.

Immix-Inspired GC

The memory layout provides:

• Efficient bump allocation
• Cache-friendly organisation
• Effective hole reuse

Current limitation: No evacuation/compaction (mark-sweep only).

See gc-implementation.md for detailed analysis.

Embedded Prelude

The prelude is:

• Written in eucalypt itself
• Compiled into the binary
• Loaded unless explicitly disabled

Benefit: Dogfooding, consistent semantics Trade-off: Slower startup if prelude is large

Performance Characteristics

Compilation

• Parsing: O(n) with incremental support
• Desugaring: O(n) pass over AST
• Cooking: O(n log n) for operator precedence resolution
• STG compilation: O(n) with binding analysis

Execution

• Bump allocation: O(1) for most objects
• Thunk updates: O(1) memoisation
• GC: O(live objects) for marking, O(total blocks) for sweeping

Memory

• 16-byte header overhead per object
• Block-level allocation granularity
• Large objects get dedicated blocks

Code Organisation Summary

Further Reading

• development/gc-implementation.md - Detailed GC documentation
• guide/command-line.md - CLI usage guide
• reference/syntax.md - Language syntax reference
• reference/operators-and-identifiers.md - Operator definitions
• guide/anaphora.md - Implicit parameter handling