Wednesday, 18 November 2026

🦆Part 5 — Looking Forward

What Phase 1 has

  • 75 tests passing on both backends
  • Structs, struct params, arrays of structs, local structs, nested structs
  • Array parameters of any element type (INT[], FLOAT[], CHAR[], STRUCT[])
  • Fixed-point Q16:16 arithmetic on both backends
  • SERIALIZE / DESERIALIZE with locked byte layout
  • File I/O (open, read, write, seek, tell, size, delete, flush, close)
  • Keyboard input (INKEY$, INPUT$(n))
  • SELECT CASE, FOR, WHILE, IF / ELSEIF / ELSE
  • String concatenation in PRINT
  • Hex / binary literals (0x, 0b, &H, &B)

What Phase 2 will add

  1. RND / RANDOMIZE — trivial to implement (LCG on NASM, rand() on C). Already planned.
  2. term.dkm — ANSI escape sequence parser in the standard library, not the compiler.
  3. resolve_name refactor — preventive cleanup, not blocking.
  4. FFI — for graphics, sound, networking, GUI/RAD. This is where the “gun on the platform’s shoulder” architecture becomes a feature rather than an implementation detail.
  5. OO — classes, methods, inheritance. Phase 2 language design.
  6. duckdb3.dkb — the milestone proof-of-concept: a DuckDB-flavored table engine with indexes, queries, and file I/O.
  7. Fullscreen editor — the “does this actually work?” test.

The architectural philosophy

Three principles emerged from building duckBASIC:

1. Platform where possible, own where necessary. The C backend uses rand(), strcpy(), memcpy(), printf() — all platform-provided. The NASM backend implements fixed_mul (60 lines of asm), _read_str (BIOS INT 21h, AH=0Ah), _print_int (custom decimal printer) — all hand-written, because the platform (bare 16-bit DOS) has nothing.

The “gun on the platform’s shoulder” philosophy is about not reimplementing what you can depend on, and owning what you can’t. Every function in runtime_c.c is a thin wrapper over libc; every function in runtime_com.inc is a hand-written implementation. The distinction is principled, not accidental.

2. Byte layout is a contract. SERIALIZE / DESERIALIZE works because the byte layout is documented, locked, and tested. It’s the reason a .dkb program can serialize on C and deserialize on NASM. It’s also the reason C’s int (4 bytes) vs NASM’s int (2 bytes) was caught early — as a design decision, not a bug.

3. Bug classes need bug-class fixes, but not always immediately. The three-path name lookup is a bug class. The right answer is resolve_name. The right timing is when you have a failing test. duckBASIC got both right: it fixed the symptom narrow (with tests 74–78 as proof), and deferred the refactor with a clear trigger condition. That’s what a mature codebase does.


Conclusion

duckBASIC is not a production compiler. It’s not going to replace GCC or LLVM, and it’s not going to be used to write the next PostgreSQL. What it is, though, is a complete implementation of a compiler pipeline with two real backends, a real test suite, and enough features to build real programs (Phase 2’s fullscreen editor is the proof point).

The project demonstrates several things that are worth writing down:

  • Two backends is better than one. The C backend made iteration fast; the NASM backend made every bug real.
  • Fixed-point math on 8086 is a solved problem if you’re willing to write 200 lines of assembly.
  • Byte layout is the hardest part of any serialization feature, and the easiest way to get it wrong is to trust that the platforms agree.
  • Cross-backend test suites catch things that single-backend test suites miss. Every bug I’ve described in this series was caught by a cross-backend test.
  • Refactoring is a response to pain, not a preventive measure. The right time to unify three name-lookup paths is when a test fails because they diverge — not before.

If you’re building your own compiler, I hope this series gives you some concrete patterns to steal. The test harness (dual backends, DOSBox verification) is the single most valuable design decision in the entire project, because it turns every bug into a reproducible failure rather than a suspected one. That’s worth more than any amount of clever parser design.

The complete Source code will be available to those who are interested


//factorial recursion in DuckBASIC.
FUNCTION factorial(n AS INT) AS INT
{
    IF n <= 1
    {
        RETURN 1
    }
    RETURN n * factorial(n - 1)
}

PRINT factorial(5)

The bellow image is the look of duckedit, the editor written in DuckBASIC

🦆Part 4 — Case Study: The Local Struct Bug, and What It Taught Us

The symptom

At V5.9d.8+.9 (the last commit before this work), a .dkb program containing:

FUNCTION foo()
{
    DIM tmp AS Point
    tmp.x = 5    // local struct field write
}

typechecked fine, but on the NASM backend, the emitted assembly contained:

mov [bp-4], ax      ; correct: local struct field write
mov [var_], ax      ; BUG: empty variable name

The second store wrote to a data-segment symbol with an empty name — which is to say, it wrote to whatever happened to be at var_ in the data segment. This was silent corruption.

Root cause diagnosis

The session notes said this:

Three separate name-lookup paths (parser, typechecker, NASM codegen) each handle global/param/local differently. Local struct vars fall through the cracks in some paths.

That was correct in spirit, but the specific bug was narrower: the NODE_ASSIGN case in gen_nasm_stmt.c had a series of if blocks for different LHS types:

if (lhs is field of array-of-struct) { ...; break; }
if (lhs is field of struct) {
    if (is_param) { ...; break; }
    if (is_local_struct) { ...; break; }  // ← the fix
    if (is_global_struct) { ...; break; }
}
if (lhs is array element) { ...; break; }

// FALLTHROUGH: scalar assignment
fprintf(out, "    mov [var_%s], ax\n", node->left->attr.name);

The scalar fallback read node->left->attr.name. But for a NODE_FIELD_ACCESS, that union field aliases node->left->attr.fieldAccess.object, which is a pointer. So attr.name was a garbage pointer, usually pointing at an empty string in memory. Hence mov [var_], ax.

The fix was to add the is_local_struct check before falling through. But the real fix — the one that eliminates the bug class — is to have a single resolver that all three passes use.

The proposed refactor

typedef enum {
    RESOLVE_GLOBAL,
    RESOLVE_PARAM,
    RESOLVE_LOCAL,
    RESOLVE_FAIL
} ResolveKind;

typedef struct {
    ResolveKind kind;
    int         offset;    // stack offset for param/local
    Symbol     *global;    // valid if kind == RESOLVE_GLOBAL
    StructField *field;    // valid if kind == RESOLVE_PARAM or LOCAL
} ResolvedName;

ResolvedName resolve_name(const char *name);

Backed by one linear walk:

ResolvedName resolve_name(const char *name) {
    ResolvedName r = {0};
    if (current_function) {
        // 1. Params
        StructField *p = current_function->metadata.function.parameters;
        while (p) {
            if (strcmp(p->field_name, name) == 0) {
                r.kind = RESOLVE_PARAM;
                r.offset = 4 + p->offset;
                r.field = p;
                return r;
            }
            p = p->next;
        }
        // 2. Locals
        StructField *l = current_function->metadata.function.locals;
        while (l) {
            if (strcmp(l->field_name, name) == 0) {
                r.kind = RESOLVE_LOCAL;
                r.offset = l->offset;
                r.field = l;
                return r;
            }
            l = l->next;
        }
    }
    // 3. Globals
    Symbol *g = symtable_lookup(global_sym_table, name);
    if (g) { r.kind = RESOLVE_GLOBAL; r.global = g; return r; }
    r.kind = RESOLVE_FAIL;
    return r;
}

Every existing branch in gen_nasm_expr.c and gen_nasm_stmt.c that walks function.parameters / function.locals / symtable_lookup inline would be replaced with resolve_name(name). That’s ~15 call sites, each simplified from 15–20 lines to 3–5.

This refactor was deferred. The bug was empirically dead — tests 74–78 (local structs in FOR loops, local struct arrays, struct-to-struct assignment, SERIALIZE through struct params) all passed on both backends. The resolver refactor is now scheduled as a Phase 2 architectural cleanup, to be triggered by a concrete failure (e.g., a duckdb3 bug that requires it) rather than a hypothetical one.

The lesson

The three-path name lookup isn’t a bug. It’s a bug class. Every new node type needs to know about it, and forgetting is invisible until something falls through. The session that fixed it did so by:

  1. Writing failing tests for every context (local, param, array, struct, loop body).
  2. Fixing the bug narrowly, confirming all tests pass.
  3. Deferring the resolver refactor because the narrow fix was correct.

The right answer to a bug class is usually “refactor to prevent recurrence” — but the right timing is usually “when you have a failing test.” This session’s decision was correct: the fix was tested comprehensively, and the refactor was deferred with a clear trigger condition. That’s how mature projects handle technical debt.

🦆Part 3 — Backends: C Transpiler and 16-bit NASM

The C backend

The C backend is the simpler of the two. It emits C source and lets gcc do the hard work.

Structure:

  • gen_c.c — top-level entry: emits preamble, structs, forward decls, globals, function definitions, then main().
  • gen_c_stmt.c — statements (DIM, ASSIGN, IF, WHILE, PRINT, etc.).
  • gen_c_expr.c — expressions (arithmetic, function calls, field access, array access).
  • gen_c.h — CGen state struct threaded through all emitters.

The runtime is a C file (runtime_c.c) that’s compiled into a string literal at build time and injected into every generated .c file. It provides _check_bounds, sys_open, sys_read, etc.

Key design decisions:

  1. All state is in a CGen struct. No globals. This makes reentrancy possible (though not currently used) and makes threading state through emitters explicit.

  2. Type mapping is done via static inline functions in gen_c.h — no separate TU needed.

  3. Array accesses get bounds checks via a runtime helper:

    buf[_check_bounds(i, 16, "buf")]
    

    The helper prints an error and calls exit(1) on violation.

  4. String assignment uses strcpy, comparison uses strcmp. The typechecker ensures STRING ops only happen where they’re valid.

  5. Struct field access emits .field for variables, ->field for params. The codegen knows which is which because it tracks current_function and checks the param list.

The NASM backend

The NASM backend is where the real engineering lives. Every operation must be expressed in 16-bit x86, with no libc, no linker, no relocations — just a flat binary loaded at 0x100.

Structure:

  • gen_nasm.c — entry point, string pool, symbol lookup, program emission.
  • gen_nasm_stmt.c — statements.
  • gen_nasm_expr.c — expressions.
  • gen_nasm_data.c — data segment emission, struct field offset lookup.
  • runtime_com.inc — runtime library (print, read, copy, etc.).
  • fixed.inc — Q16:16 fixed-point math.
  • fileio.inc — DOS file I/O wrappers.

Key design decisions:

  1. Every value lives in AX (and DX for FLOAT). This is a naive register allocation strategy — no spilling, no liveness analysis. It’s slow but correct.

  2. Binary operations use the stack:

    ; evaluate left into AX
    push dx
    push ax
    ; evaluate right into AX
    push dx
    push ax
    pop bx      ; right low
    pop cx      ; right high
    pop ax      ; left low
    pop dx      ; left high
    ; now DX:AX = left, CX:BX = right
    
  3. Q16:16 fixed-point arithmetic — no floating point unit on 8086, so all “floats” are stored as 32-bit fixed-point (16.16). Addition is add/adc. Multiplication and division are hand-written 32-bit signed routines in fixed.inc, each ~60 lines of assembly.

  4. String constants live in a string pool — deduplicated, emitted at the end of the binary, referenced as str_N.

  5. Everything is in a .COM file — flat binary, loaded at 0x100, no relocations. org 0x100 at the top.

  6. Runtime library is .inc-included — no linking. The %include directives pull in runtime_com.inc, fixed.inc, fileio.inc at assembly time.

The SERIALIZE / DESERIALIZE byte layout

Both backends implement a locked byte layout for struct serialization:

Field type Bytes
INT 2 (little-endian)
BOOL 2 (little-endian)
FLOAT (Q16:16) 4 (little-endian)
CHAR 1
STRING 256 (fixed-size, null-padded)

The layout is documented in both gen_c_stmt.c and gen_nasm_stmt.c, and it’s the contract that allows a .dkb program to serialize a struct on the C backend and deserialize it on NASM (or vice versa, across process boundaries).

The C backend emits byte-by-byte memcpy calls, truncating int to short on serialize and sign-extending on deserialize. This is necessary because C’s native int is 4 bytes but duckBASIC’s INT is 2 bytes — the layout must match the NASM backend’s.

The NASM backend emits mov sequences (and rep movsb for strings). No truncation needed since NASM’s INT is natively 2 bytes.

The byte layout was a deliberate design decision: it made SERIALIZE / DESERIALIZE work identically on both backends without any translation layer, and it exposed a number of lurking bugs (like C’s int being 4 bytes) that would have been catastrophic later.

🦆 Part 2 — Front End: Lexer, Parser, Symbol Table, Type Checker

Lexer (lexer.c)

The lexer is hand-written, single-pass, token-at-a-time. Nothing fancy — no DFA tables, no regex, just a switch on the first character.

Notable features:

  • Radix literals: 0x1F (hex), 0b1010 (binary), &HFF (QBasic-style hex), &B1010 (QBasic-style binary). The &H/&B forms are particularly nice because they round-trip cleanly to QBASIC programmers.
  • String escapes: \n, \t, \r, \\, \", \', \0.
  • Character literals: 'a' (single quotes). This interacts badly with QBASIC-style ' comments, which duckBASIC does not support — comments are //.
  • Token names array with a _Static_assert guarding against enum drift.

The lexer is intentionally simple. No diagnostic recovery, no multi-byte UTF-8, no raw strings. Every token is either recognized or produces TOKEN_ERROR and the parser will halt.

AST (ast.h, ast.c)

The AST is a tagged union of node types. Every node is an ASTNode struct:

typedef struct ASTNode {
    ASTNodeType type;
    DataType evalType;       // resolved type, set by typechecker
    bool print_no_newline;
    int line;

    struct ASTNode *left;
    struct ASTNode *right;
    struct ASTNode *next;    // statement chaining

    union {
        char *name;                          // identifier
        int32_t intVal;                      // int literal / float raw bits
        char *strVal;                        // string literal
        unsigned char charVal;               // char literal

        struct { ... } ifNode;
        struct { ... } whileNode;
        struct { ... } forNode;
        struct { ... } arrayAccess;
        struct { ... } functionDecl;
        struct { ... } functionCall;
        struct { ... } structDecl;
        struct { ... } fieldAccess;
        struct { ... } structVar;
        struct { ... } selectNode;
        struct { ... } caseNode;
        struct { ... } serializeNode;
    } attr;
} ASTNode;

The union keeps nodes compact (about 100 bytes each). The next pointer chains statements into a linked list, so a block is just a NODE_BLOCK whose left is the first statement and each statement’s next points to the following one.

The union overlap is a known footgun. attr.name (a char*) and attr.fieldAccess.object (also a pointer) occupy the same bytes. Reading attr.name on a NODE_FIELD_ACCESS produces a garbage pointer, which is exactly what caused the mov [var_], ax bug we spent a session debugging.

Symbol table (symtable.c)

The symbol table is a linked list of Symbol structs. It uses three pointer fields to maintain two separate lists simultaneously:

typedef struct Symbol {
    char name[128];
    DataType type;
    int offset;
    int class_type;          // SYM_SCALAR, SYM_ARRAY, SYM_STRUCT_DEF, etc.
    int is_local;
    int is_builtin;
    short stack_offset;

    union {
        struct { ... } array;
        struct { ... } struct_def;
        struct { ... } struct_var;
        struct { ... } function;
        struct { ... } constant;
    } metadata;

    struct Symbol *next;       // active scope lookup chain
    struct Symbol *all_next;   // master allocation chain (for cleanup)
} Symbol;
  • next is the active lookup chain — it changes as scopes are pushed and popped.
  • all_next is the master allocation chain — never modified after insertion. This is how symtable_free iterates all symbols for cleanup.
  • head points to the current scope’s head. all_head points to the master list.

Scope push/pop is done via snapshots:

ScopeSnapshot snap = symtable_save_scope(p->symTable);
// ... insert local symbols ...
symtable_restore_scope(p->symTable, snap);

Restoring just resets table->head to the snapshot’s head. Memory is never freed until symtable_free at the very end.

This design is simple but not scalable — lookups are O(n) linear scans. For a 16-bit compiler, that’s fine. For a production compiler, you’d want a hash table.

Parser (parser.c + parser_*.c)

The parser is recursive descent for statements and precedence climbing for expressions. Each grammar production is a function.

The parser is split across multiple files by grammar area:

  • parser.c — core (statement dispatch, expression engine, block parser, DIM handling)
  • parser_if.c, parser_while.c, parser_for.c — control flow
  • parser_function.c — function declarations, calls, returns
  • parser_struct.c — struct definitions
  • parser_array.c — array access
  • parser_select.c — SELECT CASE
  • parser_serialize.c — SERIALIZE / DESERIALIZE
  • parser_import.c — IMPORT statement (file inclusion)

The expression engine uses precedence climbing:

ASTNode* parse_expression(Parser *p, int precedence)
{
    // 1. Parse a prefix (literal, identifier, unary operator, paren)
    // 2. While the next token has higher precedence than the argument:
    //    - Consume the operator
    //    - Parse RHS with the operator's precedence
    //    - Build a binary node
    return left;
}

Precedence levels (highest to lowest):

  1. . (field access) — 12
  2. [ (array subscript) — 11
  3. * / % — 10
  4. + - — 9
  5. << >> — 8
  6. < <= > >= — 7
  7. == != — 6
  8. & — 5
  9. ^ — 4
  10. | — 3
  11. && — 2
  12. || — 1

Error recovery is panic-mode: on failure, skip tokens until a \n, }, or EOF, then continue. This means a syntax error in one statement doesn’t cascade into forty subsequent errors.

Type checker (typecheck.c)

The type checker walks the AST after parsing and before codegen. It does two things:

  1. Annotates every expression node with evalType so codegen can trust it without re-deriving.
  2. Validates type compatibility and increments g_error_count on mismatch.

Key rules:

  • BOOL cannot appear in arithmetic.
  • STRING + is only valid inside PRINT (concatenation).
  • Array indices must be INT.
  • Function call arguments must be type-assignable.

The typechecker re-creates function scope by re-inserting parameters and locals into the symbol table, then checks the body, then restores scope. This is a second pass over the AST — the parser already did one symbol-table pass — which is why there are two name-lookup paths (parser + typechecker) plus the codegen’s third path.

This duplication is the source of the “three lookup paths” bug class. Fixing it properly would require a unified resolve_name helper used by all three passes — a Phase 2 refactor.

🦆 duckBASIC: A Modern 16-bit BASIC Compiler — Design & Implementation

🦆 Introduction

This series documents the design and implementation of duckBASIC, a compiler for a modern dialect of BASIC. The Philosophy is to create a usable teachable tool for students or hobyists who are interested in Compiler and interpreter writing. DuckBASIC targets both C (for portability) and 16-bit real-mode MS-DOS via NASM assembly (.COM executables). The project was built iteratively, feature by feature, with a test suite that validates both backends in parallel against identical source programs.

Old timers who have soiled their hands with QBASIC/GWBASIC/BASICA/VB may find similar environment but in C style 🦆🦆🦆

Over the course of development, duckBASIC grew from a simple expression evaluator into a compiler with:

  • Two full backends (C transpiler and NASM 16-bit assembler emitter)
  • Structured types: structs, struct parameters, arrays of structs, local structs, nested structs
  • Fixed-point Q16:16 arithmetic implemented in hand-written x86 assembly
  • A locked byte layout for SERIALIZE/DESERIALIZE that guarantees cross-backend binary compatibility
  • A real file I/O API (SYS_OPEN, SYS_READ, SYS_WRITE, SYS_SEEK, etc.)
  • Cross-platform keyboard primitives (INKEY$, INPUT$(n)) and array parameters (INT[], FLOAT[], CHAR[], STRUCT[])
  • 75+ tests running on both backends, most of which are verified by running the resulting .COM file inside DOSBox and comparing output byte-for-byte

The project is interesting not because it implements a compiler — plenty of toy compilers exist — but because it implements two of them simultaneously, with a shared test suite, and verifies they produce identical output on real 16-bit hardware.


Part 1 — Architecture Overview

The pipeline

Every compiler is a pipeline, and duckBASIC’s is deliberately simple:

Source (.dkb)
    ↓
Lexer (tokens)
    ↓
Parser (AST + symbol table)
    ↓
Semantic resolution (function calls)
    ↓
Type checker (evalType annotations)
    ↓
Code generation (two backends)
    ↓
    ├── C source (.c) → gcc → native binary
    └── NASM source (.asm) → nasm → .com → DOSBox

The top-level structure

The compiler is a single executable, duckbas, built from ~15 C files. The entry point in main.c orchestrates the phases:

// Phase 1: Lexical analysis
lexer_init(&compiler_lexer, source_code);

// Phase 2: Parsing
symtable_init(&compiler_table);
parser_init(&compiler_parser, &compiler_lexer, &compiler_table);
ASTNode *program_tree = parser_parse_program(&compiler_parser);

// Phase 2.5: Semantic resolution (function calls)
resolve_function_calls(program_tree, &compiler_table);

// Phase 2.75: Type checking
int tc_errors = typecheck_program(&compiler_parser, program_tree);

// Gate: if any phase errored, stop before codegen
if (g_error_count > 0) { ... exit(1); }

// Phase 5: Code generation
if (opt.target == TARGET_C) {
    gen_c_program(program_tree, &compiler_table, output_path);
} else {
    gen_nasm_program(program_tree, &compiler_table, output_path);
}

Three global counters (g_error_count, g_warning_count, g_verbosity) coordinate diagnostics across phases.

The two backends

The C backend transpiles duckBASIC AST to C source, which is then compiled by gcc. This is the “reference” backend — anything that works here is by definition semantically correct. It’s also the fast one to iterate on: change a C emitter, recompile with gcc, done in 2 seconds.

The NASM backend emits 16-bit x86 assembly for MS-DOS .COM executables. This is the “authentic” backend — every feature must be implemented in raw assembly or wrapped around DOS/BIOS interrupts. It’s the hard one: fixed_mul is 60 lines of hand-rolled signed multiplication, _read_str uses BIOS INT 21h, AH=0Ah, SYS_OPEN wraps INT 21h, AH=3Dh.

The two backends share nothing at the codegen level. They each have their own AST walkers (gen_c_stmt.c, gen_c_expr.c vs gen_nasm_stmt.c, gen_nasm_expr.c). But they share the entire front end — parser, symbol table, type checker — which is what guarantees semantic consistency.

The test harness

The test suite (tests/*.dkb) runs each program through both backends and compares:

  1. C backend output — compile to .c, gcc, run, capture stdout.
  2. NASM backend assembles — nasm -f bin, verify it produces a .com.
  3. NASM output in DOSBox — run .com inside DOSBox, capture output, compare byte-for-byte with C output.

For interactive tests (INKEY$, keyboard input), DOSBox runs with a scripted keystroke file.

The suite currently has 75 tests, 72 pass, 0 fail, 3 skip. The skipped tests are Phase 2 features (graphics, sound, etc.) that aren’t implemented yet.

🦆Part 5 — Looking Forward What Phase 1 has 75 tests passing on both backends Structs , struct params, arrays of structs, local structs...