7 — The seam

Wirth’s parser called gen(f, l, a) directly:

constant: gen(lit, 0, val);
varible: gen(lod, lev-level, adr);

That is a fine program, and it has one consequence: the parse and the p-code are one thing. The parse cannot exist without the stack machine, and the stack machine cannot be replaced without rewriting the parse.

This chapter is about the one change that separates them, what it costs, and what it buys.

The sixteen operations

The seam is an interface with sixteen operations. That is the entire vocabulary in which the front end can speak to a back end:

struct Backend {
    /* A procedure opens, and the handle a call will name it by is answered. */
    Procedure (*begin_procedure)(Backend* backend, const char* name, int level);

    /* The declarations close and the statement part opens, stating how many
     * variables the activation record holds. */
    void (*begin_body)(Backend* backend, Procedure procedure, int variable_count);

    /* The statement part closes and its return is planted. */
    void (*end_procedure)(Backend* backend, Procedure procedure);

    /* A jump target is reserved before it is placed. */
    Label (*new_label)(Backend* backend);
    void (*place_label)(Backend* backend, Label label);
    void (*jump)(Backend* backend, Label label);
    void (*jump_if_false)(Backend* backend, Label label);

    /* A literal value is pushed. */
    void (*load_constant)(Backend* backend, int value);

    /* A variable's value is pushed, named by how many nesting levels out its
     * declaration lies and by its offset inside that activation record. */
    void (*load_variable)(Backend* backend, int level_difference, int address);
    void (*store_variable)(Backend* backend, int level_difference, int address);

    /* A procedure declared the given number of levels out is invoked. */
    void (*call)(Backend* backend, int level_difference, Procedure target);

    void (*negate)(Backend* backend);
    void (*arithmetic)(Backend* backend, ArithmeticOperation operation);
    void (*odd)(Backend* backend);
    void (*compare)(Backend* backend, Comparison comparison);
};

Read it as a specification of what a PL/0 back end is. Anything that can do those sixteen things can be the back end of this compiler.

Two decisions worth stealing

Most of that interface is unremarkable. Two choices in it are not, and both are the kind of decision that determines whether an interface survives its second implementation.

1. A stack discipline, not an expression tree.

load_constant and load_variable push. The arithmetic and comparison operations pop their operands and push their result. store_variable pops.

Nothing in that protocol says where the stack is. Wirth’s back end is a stack machine, so it implements arithmetic by emitting one instruction and letting the stack exist at run time. The Dragon back end keeps the stack at compile time — it pops two operand names and emits one three-address instruction — so nothing is on a stack when the program runs.

A protocol that had said “emit an add instruction” would have forced the first shape on everyone. A protocol that says “pop two, push their result” does not.

2. Labels, not addresses.

Label (*new_label)(Backend* backend);
void (*place_label)(Backend* backend, Label label);

Wirth patched the address field of a jump after the fact — the backpatch, in appendix A:

cx1 := cx; gen(jpc, 0, 0);
statement(fsys); code[cx1].a := cx

That works, and it requires the caller to know that a jump has an address field, that instructions live in an array, and that positions in that array are meaningful. Three facts about the target, leaking into the parser.

A label says the same thing without any of them. new_label hands out an identity; place_label says where it landed; how the two are reconciled is the back end’s business. The p-code back end backpatches, exactly as Wirth did. The Spectra back end simply emits a label, because its representation has them natively.

An interface should name what the caller wants, not what the first implementation happens to do. That is the whole lesson of this chapter, and labels are the clearest instance of it in the compiler.

How C spells it

A struct of function pointers, and the implementation embeds it as its first member:

typedef struct {
    Backend backend;        /* first — so a Backend* and a PCodeBackend* are one address */
    Instruction code[MAX_PCODE];
    int code_count;
    ...
} PCodeBackend;

Because backend is first, a Backend* and a PCodeBackend* are the same address, and a method recovers its own state by casting:

static void pcode_load_constant(Backend* seam, int value) {
    pcode_emit((PCodeBackend*)seam, fn_lit, 0, value);
}

Filling the table is one initializer:

void pcode_backend_init(PCodeBackend* backend) {
    memset(backend, 0, sizeof *backend);
    backend->backend = (Backend){
        .begin_procedure = pcode_begin_procedure,
        .begin_body = pcode_begin_body,
        .end_procedure = pcode_end_procedure,
        .new_label = pcode_new_label,
        .place_label = pcode_place_label,
        .jump = pcode_jump,
        .jump_if_false = pcode_jump_if_false,
        .load_constant = pcode_load_constant,
        ...
    };
}

If that shape looks familiar, it should: this is a vtable, hand-written. It is what C++ generates for a class with virtual methods, what Go generates for an interface value, and what a Rust dyn Trait is at run time. Writing it out by hand once is the fastest way to understand all three.

The call site is a double indirection:

parser->backend->load_constant(parser->backend, entry->value);

How Mica spells it

Mica has no function pointers at all. Not “discouraged” — the language does not have them. So the C spelling is unavailable, and the twin has to say the same thing another way:

{ the two back ends one parse can drive - the seam's selector, and the reason there is a seam at all }
exp Backend = (PCodeBackend, SpectraBackend);

and every operation dispatches on it:

{ a procedure opens on whichever road is active, and the shared handle series advances - the parse hands out
  one numbering, so a handle means the same procedure to both back ends }
function BeginProcedure(c : pointer Compilation, level : int32) : int32;
var
    handle : int32;
begin
    handle := c.ProcedureCount;

    case c.Active of
        PCodeBackend: BeginProcedure := POpenProcedure(address c.Oracle, handle)
    else
        BeginProcedure := SOpenProcedure(address c.Road, handle, level)
    end;

    c.ProcedureCount := c.ProcedureCount + 1;
end;

Sixteen small routines, each a two-armed case. The parse below them never mentions either back end by name — which is the property that mattered, and it is preserved exactly.

Which is better?

Neither, and the comparison is the useful part.

This is the expression problem, and it is one of the genuinely fundamental trade-offs in language design. Open-ended in one dimension costs you closure in the other:

• Function pointers / interfaces / subclasses make it cheap to add implementations and expensive to add operations.
• A closed sum type and a dispatch make it cheap to add operations and expensive to add implementations.

PL/0 has exactly two back ends and will not grow a third, while the seam’s operations were still being adjusted while the compiler was written. For this program, the closed form is the better fit — and that is not a general verdict, it is a verdict about this program’s actual axis of change.

Mica’s language design takes the position that a program’s dispatch should be visible where it happens; the twin is that position, applied. C’s design takes the position that an interface is a value you can hand around; the other twin is that. Reading both is the fastest way to develop an opinion of your own.

The seam’s one asymmetry

There is a place where the two twins’ file layout differs, and it follows directly from the above.

In C, Backend is a type, and an interface type belongs to whoever calls through it — so the parser’s header declares it, and the two back ends include that header to fill one in.

In Mica, the seam is a dispatch, so the parser imports the two back ends and does the switching itself.

C:      diagnostics ← scanner ← symbols ← parser ← { pcode, spectra } ← driver
Mica:   diagnostics ← scanner ← symbols ← pcode ← spectra ← parser ← driver

The arrow between the parser and the back ends reverses. Everything else in the two trees is identical, file for file. That one flipped arrow is the shape of the difference between an interface you pass and a dispatch you write, made visible in a directory listing.

What the seam cost

One struct of function pointers, or sixteen two-armed case statements.

What it bought: a second back end that shares the entire front end, and — less obviously but more importantly — a reference implementation. Because the same parse drives both, any disagreement between them is a bug in one of them, and the simple one is almost never the one that is wrong.

That is the subject of chapter 10, and it is the strongest practical argument for naming a seam that this series can make.

Next: 8 — The oracle, the back end that defines what a program means.