Baker Saturation Engine

Baker: A Key Ingredient to Composer

Gerard Huet’s 1997 paper on “The Zipper” introduced a method for navigating immutable tree structures by carrying context during traversal. For years many have viewed this as a purely functional curiosity. But in the architecture of Composer, it solves a problem that often baffles developers coming from managed runtimes or imperative systems programming: bridging the gap between high-level intent and low-level execution while maintaining what is essential to both.

For the .NET developer, the “floor” of abstraction is often the Intermediate Language (IL). You trust the JIT to handle the messy details of memory and registers. For the Rust or Go developer, you are accustomed to seeing the metal, but often at the cost of the expressiveness that functional programming offers.

Composer seeks to lower that floor while keeping the ceiling high. SpeakEZ Technologies has take a view to bring the rich, expressive syntax of the Clef language, with its pattern matching, higher-order functions (HOFs), and discriminated unions, and translate it into a representation that is not just “executable,” but semantically complete. The Fidelity framework is the embodiment of the belief that the future of computing is not just ‘full stack’, but multi-stack.

Baker’s development within the Composer compiler tracks that vision. Early iterations relied on a complex “two-tree zipper” to manually correlate the Clef abstract syntax tree (AST) with the typed tree. This architecture has evolved. The manual correlation of trees has been superseded by a native type universe (NTU) and a robust nanopass infrastructure. Baker is now our Saturation Engine. It applies semantic meaning using a model of Recipes and Ingredients.

The Landscape: Elaboration and Saturation

Elaboration makes the semantics of an admitted source operation explicit. Baker carries that work into typed PSG structure: operand evaluation, callbacks, branches, captures and the relationships required to justify their implementation. Saturation settles the applicable facts before Alex witnesses the construction. The current Baker architecture owns the engineering details and current APIs; the code below illustrates the recipe style.

This includes ordinary native operations and higher-order constructs. Platform bindings contribute their declared external contracts. A recipe can construct both executable nodes and joint relations over their participants; fold-in must retain the correspondence. A range or placement result may be a local coeffect, while the guard, values, stores and consumer that justify it form a multi-participant relation in the same graph.

  flowchart TD
    subgraph Input
        PSG[Initial Pruned PSG]
    end

    subgraph Baker [Baker Elaboration and Saturation]
        Discovery[Fan-Out: Discovery Zipper] --> Sites{Saturation Site?}
        Sites -- Yes --> Recipe[Apply Recipe]
        Recipe --> Primitives[Typed Nodes and Joint Relations]
        Primitives --> FoldIn2[Fold-In: Preserve Identities and Dependencies]
        FoldIn2 --> Settle[Settle Required Facts]
    end

    Input --> Baker
    Contracts[Admitted Operation and Platform Contracts] --> Recipe
    Baker --> Alex[Alex: Backend Witness]

When you write a List.map or a recursive match expression, Baker constructs the algorithm and relationships required by its source semantics. Alex consumes the settled construction; it cannot repair missing source semantics from a physical slot or a familiar operation name. A recipe’s presence alone does not establish complete native coverage.

The proposed bidirectional extension follows that boundary. Its operation contract would specify how forward results, backward requirements, effects and resource uses connect. Compiler analysis reaching a fixed point would not establish that a recursive source computation is productive. Nor would a reverse dependency imply an inverse program or a saved history. A Path Less Traveled explains those distinctions and links the coordinated implementation plan.

The Nanopass Infrastructure

One of the major architectural decisions that have led to many hard-forked projects in the Clef ecosystem is a move away from recursive patterns that weave many compiler pipeline. This is a vestige of older designs, and while it works, it makes following a single transformation through the interwoven recursive passes very difficult. Instead, we use a nanopass infrastructure, which is more stratified, more testable, and easier to follow across the pipeline. Each pass is a focused transformation over one part of the graph, small enough to test on its own.

Baker executes within the PSGSaturation stage using a Fan-Out / Fold-In pattern:

Fan-Out (Discovery): A specialized zipper, our navigator, traverses the reachable compute graph. It identifies “saturation sites” where things like HOFs (higher order functions), sequence expressions, match statements or similar constructs require expansion. Saturation: Baker applies a “Recipe” to each site. This generates a sub-graph of primitives that compose up to satisfy the inent of the HOF or similar construct. This step occurs in parallel. Each decomposition is isolated, so it is labeled “fan out”.
Fold-In: The generated sub-graphs merge into the main PSG. This step establishes parent-child relationships and updates references. Because of common/spanning concerns like node ID numbering and graph “edge” connections this must be done serially.

Separating discovery and application from fold-in keeps our “Recipes” clear of the compiler’s global state. A Recipe needs to know only how to cook that specific dish.

A nanopass compilation strategy opens the potential for embarrassingly parallel compilation stages.

A Functional Kitchen

Baker embraces a consistent hierarchy for code generation built on XParsec parser combinators. The metaphor may be considered a bit cute by some, but we feel like it deserves a bit of color; using “ingredients” and “recipes” perfectly fits the model of composition we are establishing.

We eschew imperative and functional “push” code for PSG node construction. There is no graph.AddNode(...) scattered through the pipeline. Instead, Saturation Combinators allow the assembly of complex logic using declarative patterns. This makes the code both reusable and more concise in reasoning through the transforms.

1. The Ingredients (Primitives)

Ingredients are the elemental building blocks. They wrap the lowest-level PSG operations, like cons, head, tail, or ifThenElse, into type-safe, semantic units.

The construction APIs concentrate primitive node creation in Ingredients, with reusable structures and recipes composed above them. This is an architectural boundary maintained through API use, review and graph checks; F# assembly visibility does not enforce a folder-level restriction. An illustrative Ingredient looks like this:

// An Ingredient: Safe, atomic wrapper around a primitive
let cons head tail elemTy =
    saturation {
        // 'emitPrimitive' is the internal builder
        let! node = emitPrimitive "cons" [head; tail] elemTy
        return node
    }

2. The Recipes (Abstractions)

Recipes are compositions of Ingredients. They typically require only 5 to 15 lines of code. A Recipe implements a high-level feature by chaining Ingredients together.

Because we use XParsec as the binding layer, a Recipe for List.map resembles the recursive algorithm itself, rather than a sequence of opaque API calls. It reads like a description of the behavior:

// A Baker Recipe: Composing Ingredients to implement List.map
let listMapRecipe mapper list elemTy =
    foldRight
        (emptyList elemTy)           // Base case: empty list
        (fun head recurse ->         // Recursive step
            saturation {
                // Apply the mapper function
                let! mapped = app1 mapper head
                // Cons the result onto the recursive tail
                return! cons mapped recurse
            })
        list

This code doesn’t “run” the map; it generates the graph nodes that perform the map. It is a meta-program that describes the shape of the computation.

Only Pay For What You Use

This architecture builds on our reachability analysis. In the .NET ecosystem, referencing a library pulls in its transitive dependencies and their type metadata whether or not your code touches them. A single function call can drag in metadata for hundreds of types you never use, bloating the binary.

Composer operates on a Stroustrup style “only pay for what you use” philosophy. Baker runs post-reachability. We first prune the graph to include only the code paths your application actually traverses.

If your program uses List.map but never touches List.sort, the logic for sorting is never saturated. It never enters the graph.

This results in a targeted optimization where Reachability removes the dead code, and Baker saturates only the edges that remain in the graph. The final native binaries are concise, containing only the code, memory patterns, and computational logic required for the tasks at hand. This is how we approach the density of C with the expressiveness of Clef: an unused abstraction adds nothing to the binary.

Pipeline Evolution

The “two-tree zipper” was a useful tool for exploration during our early prototypes; its removal marks the architectural maturity of the Fidelity framework. Manual synchronization of AST and Typed Tree representations is no longer necessary. It was a non-trivial amount of work to pivot to the Native Type Universe (NTU). But in doing so we also were able to wed the AST to the NativeTypedTree construct and produce a connected, cohesive initial semantic graph. Post reachability analysis, the PSG provides a unified context that flows throughout the nanopass pipeline, carrying the type information we need without any adverse structural overhead.

We still employ a coeffect strategy to compute metadata about the graph, such as SSA assignment and mutability, but this now happens alongside the saturation process.

Baker has transformed from a complex correlation mechanism into a streamlined engine that facilitates the early stages of tranforming functional abstraction into direct native computation. It completes full, detailed, deterministic semantic meaning to fulfill the Fidelity framework’s promise: high-level expressiveness with the performance and footprint of hand-tuned native code.