commit 58a33b2e7a6a07d40af12ff49f42dfdc406192da
parent b986b624e16f8f8279b12d6bcf9d1b0b4f3e4f6a
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Sat, 25 Apr 2026 10:25:20 -0700
Audit scheme1: document deviations and known issues
Marks the original 10-task checklist done, then enumerates everything
that diverges from the LISP.md / LISP-C.md spec or from the original
plan. Sections cover open bugs (spawn-via-run, no heap-overflow check,
unbounded primitives), spec features still missing (set!, and/or,
pmatch, much of the primitive list, strings/chars in the reader),
hacks and fragile invariants (NUL-as-whitespace, bytevector NUL-
termination via headroom, parameterized PRIM data slot, recursion-
bounded helpers), test caveats (each test that has a workaround,
hard-coded constant, or untested case), and the m1pp text_buf bump.
Includes a suggested order for closing the gaps.
Diffstat:
1 file changed, 324 insertions(+), 12 deletions(-)
diff --git a/docs/scheme-shell-todo.md b/docs/scheme-shell-todo.md
@@ -2,36 +2,348 @@
Checklist for getting `lisp/shell.scm` running under scheme1.
-**Workflow:** every item is red-green TDD. Add a failing `tests/scheme1/NN-*.scm` (with `.expected-exit` and/or `.expected`) first, run the suite to confirm it fails for the expected reason, then implement until green. Multi-arch suite (`make test SUITE=scheme1`) must stay clean before moving on.
+**Workflow:** every item is red-green TDD. Add a failing
+`tests/scheme1/NN-*.scm` (with `.expected-exit` and/or `.expected`) first,
+run the suite to confirm it fails for the expected reason, then
+implement until green. Multi-arch suite (`make test SUITE=scheme1`)
+must stay clean before moving on.
-## Checklist
+## Checklist (original plan)
-- [ ] **1. Reader: `;` comments, `'datum`, `'()`, `#xNN` hex literals.**
+- [x] **1. Reader: `;` comments, `'datum`, `'()`, `#xNN` hex literals.**
Hook `;` into `skip_ws` (skip until LF/EOF). Add `'` to `parse_one` as a prefix that reads the next datum and wraps in `(quote …)`. Intern `quote` at startup. Extend the `#`-cascade with `x`/`X` → hex parse.
-- [ ] **2. Top-level `define`.**
+- [x] **2. Top-level `define`.**
`eval_define` → `sym_set_global`. Recognize `(define (f a b . rest) body…)` sugar by rewriting to `(define f (lambda (a b . rest) body…))`. Returns UNSPEC.
-- [ ] **3. Variadic `.`-tail.**
+- [x] **3. Variadic `.`-tail.**
Reader: `parse_list` recognizes `.` followed by ws inside a list as the dotted-pair separator; `parse_atom` rejects a bare `.`. `bind_params`: when `params` is a non-pair, bind `params` to the remaining args list and stop.
-- [ ] **4. `cond` and the `let` family.**
+- [x] **4. `cond` and the `let` family.**
`cond` driver walks clauses; intern `else` at startup and pointer-compare it. `let` / `let*` / `letrec` / named `let`. `letrec` pre-binds names to UNSPEC, evaluates inits in the new env, then writes each value via `%st(val, pair, 7)` on the binding cell — no new primitive required.
-- [ ] **5. Arith + list primitives.**
+- [x] **5. Arith + list primitives.**
Batch in: `cons`, `car`, `cdr`, `null?`, `pair?`, `zero?`, `not`, `eq?`, `+`, `-`, `*`, `=`, `<`, `bit-and`, `bit-or`, `arithmetic-shift`, `apply`. Each is a leaf with the `prim_sys_exit_entry` shape; `register_primitives` grows a table-style init.
-- [ ] **6. Bytevectors.**
+- [x] **6. Bytevectors.**
Encode length in the upper 56 bits of the header (`hdr = (len << 8) | HDR.BV`). Allocator + `make-bytevector` (1- and 2-arg), `bytevector-length`, `bytevector-u8-ref`, `bytevector-u8-set!`, `bytevector-copy` (3-arg), `bytevector-copy!` (5-arg).
-- [ ] **7. `define-record-type`.**
+- [x] **7. `define-record-type`.**
Desugar at eval time by constructing the equivalent s-expression (a `begin` of `define`s for the td, ctor, predicate, and accessors/mutators) and recursing into `eval`. Cleaner than hand-rolling closures and reuses every existing path. Add the internal `%record-*` primitives. Depends on (1) for the quoted type-name symbol.
-- [ ] **8. Syscall primitives.**
+- [x] **8. Syscall primitives.**
Wrap libp1pp's `sys_read/write/close/openat/exit/clone/execve/waitid` macros as scheme primitives returning the `(#t . val)` / `(#f . errno)` convention. Promote argv to a BSS slot at startup so `sys-argv` can rebuild a list of bytevectors on demand. Add `EOF` as a sixth `IMM` and expose `eof-object` / `eof-object?`.
-- [ ] **9. Prelude.**
+- [x] **9. Prelude.**
Embed `lisp/prelude.scm` as a bytevector literal in `scheme1.P1pp`. Parse-and-eval it before the user file at startup. Contents per LISP-C.md §Prelude: `list`, `length`, `reverse`, `append`, `list-ref`, `map`, `for-each`.
-- [ ] **10. Port `shell.scm` into the prelude.**
+- [x] **10. Port `shell.scm` into the prelude.**
Concatenate `lisp/shell.scm` (or a shell-prelude variant) into the embedded source after the base prelude. Add an end-to-end test that uses `spawn` / `run` / a file-I/O round-trip.
+
+---
+
+# Audit: deviations and known issues
+
+The boxes above are checked because each task's tests pass on all three
+arches, but several items diverge from the original plan or from the
+LISP.md / LISP-C.md spec. Everything below is a real bug, hack, or spec
+gap that must be addressed before calling scheme1 shippable.
+
+## Open bugs
+
+- [ ] **Prelude `spawn` reached through `run` errors with "unbound variable"
+ in the parent.** `(run prog)` from user code fails even though
+ `(spawn prog)` inline at user level with the identical body works.
+ Root cause not identified (`apply_build_args` walking the variadic
+ list, closure env capture, or env extension with the dotted-tail
+ param `args` are all suspects). See test
+ `tests/scheme1/45-shell-spawn.scm` — it works around the bug by
+ redefining `spawn` at user level. Until this is understood, the
+ prelude's `spawn` and `run` are effectively unverified.
+
+- [ ] **No heap-exhaustion check.** `cons` and `alloc_hdr` bump
+ `heap_next` past the 64 KiB heap arena without a runtime test. Past
+ `&ELF_end + 0x20000` writes silently corrupt the symtab arena. The
+ comment at `:cons` references "LISP-C.md milestone 3" but never adds
+ the check.
+
+- [ ] **No symtab-name copy bound.** `intern` allocates a fresh copy of
+ every name into the heap. A program that interns lots of unique
+ symbols will exhaust the heap (see above).
+
+- [ ] **Bytevector-u8-set! / -ref / -copy / -copy! have no bounds check.**
+ Out-of-range index silently corrupts adjacent heap memory. LISP.md
+ says "primitive failure is undefined behavior", but no abort path is
+ installed.
+
+- [ ] **`car` / `cdr` of non-pair, `quotient`/`remainder` of zero, etc.,
+ are silent UB** — same policy as above, no abort path.
+
+## Spec features still missing
+
+Per LISP.md and LISP-C.md, but not implemented:
+
+- [ ] **Reader gaps**:
+ - `"…"` string / bytevector literals with `\n \t \r \\ \"` escapes
+ - `#\char` literals (printable ASCII, named forms, `#\xNN`)
+ - Source-location side table (line:col → pair) used by `error`
+- [ ] **Special forms missing**: `set!`, `and`, `or`, `pmatch`, `cond`'s
+ `=>` arrow form. `pmatch` is called out by LISP-C.md as a built-in
+ special form needed by the self-hosted compiler.
+- [ ] **Primitives missing** (LISP.md lists them as required):
+ - Equality: `eqv?`, `equal?` (we only have `eq?`)
+ - Predicates: `boolean?`, `integer?`, `string?`, `procedure?`,
+ `record?`, `record-type?`
+ - Numeric: `quotient`, `remainder`, `modulo`, `<=`, `>=`, `>`,
+ `positive?`, `negative?`, `abs`, `min`, `max`, `bit-xor`,
+ `bit-not`, `number->string`, `string->number`
+ - Pair / list: `set-car!`, `set-cdr!`, `length`, `list-ref`, `map`,
+ `for-each` as primitives (we provide them via the prelude only)
+ - Bytevector: `bytevector-append`, `bytevector=?`, `string->symbol`,
+ `symbol->string`
+ - I/O / control: `error`, `display`, `write`, `format`
+- [ ] **`+ - * = <` are 2-arg only.** R7RS allows any arity.
+- [ ] **`apply` is variadic on the trailing list** but otherwise
+ unverified for arity edge cases.
+- [ ] **Type names are not bound by `define-record-type`.** The TD is
+ reachable only via the parameterized prims that close over it; no
+ `record-type-of`, no way to inspect a TD from user code. Spec is
+ ambiguous on this; LISP-C.md's example uses a generated `<point-td>`
+ binding.
+- [ ] **`sys-execve` always passes `envp = NULL`.** shell.scm's contract
+ ("parent env is inherited by the child") is not satisfied.
+- [ ] **`sys-clone` is hard-wired to `SIGCHLD` only.** No `CLONE_VM`,
+ thread support, etc.
+- [ ] **No `sys-pipe`, `sys-dup2`, `sys-fcntl`, `sys-fork`** — needed
+ for any real shell pipeline / redirection.
+- [ ] **`sys-wait` adapter only handles `CLD_EXITED` and signal kill;
+ `CLD_STOPPED` and `CLD_CONTINUED` collapse into the kill branch.**
+- [ ] **shell.scm's port record-type, `stdin`/`stdout`/`stderr` ports,
+ `open-input` / `open-output` / `read-line` / `read-bytes` /
+ `read-all` / `bv-concat-reverse` / `write-bytes` / `write-line` are
+ NOT in the prelude.** Only the process-management half of shell.scm
+ is ported.
+- [ ] **Prelude is a strict subset of `lisp/prelude.scm`.** The embedded
+ copy has only `list / length / reverse / append-pair / append /
+ list-ref / map / for-each` plus the shell helpers; it's missing
+ `<= >= zero? positive? negative? abs caar cadr cdar cddr caddr
+ list? assoc member filter fold equal?` and the vector helpers
+ (`vector->list`, `list->vector`, `equal?-vector`, etc.). The
+ vector helpers reference `vector-ref` / `vector-length` /
+ `make-vector` which we don't have, so they cannot be embedded
+ unchanged.
+- [ ] **`error` primitive** — exits with no formatted message; no
+ "at file:line:col:" prefix.
+
+## Hacks and fragile invariants
+
+These work today but are easy to break.
+
+- [ ] **`skip_ws` treats NUL (`\0`) as whitespace.** The embedded
+ prelude is a chain of `"…"` literals separated by `'0a'` (LF), and
+ M0 auto-NUL-terminates each `"…"`. Without the NUL skip the parser
+ treats those NULs as the start of a new symbol. Side effects:
+ - User source files that contain literal NULs are silently skipped,
+ which is non-standard.
+ - `parse_atom` does **not** skip NULs — an atom that ends exactly at
+ a M0 string-literal boundary in the prelude would absorb the
+ trailing NUL into the token. The current prelude doesn't trigger
+ this because every line ends on a paren or whitespace, but
+ re-flowing the prelude can break it silently.
+
+- [ ] **Bytevector NUL-termination via headroom.** `bv_capacity_for`
+ returns the smallest power of two strictly greater than `n`. The
+ byte at index `length` is the zero-init NUL terminator and we hand
+ the raw `data_ptr` directly to syscalls expecting C strings
+ (`sys-openat`, `sys-execve`, the per-arg pointers in
+ `build_execve_argv`). If user code calls `bytevector-u8-set!` past
+ `length`, that NUL is gone and the next syscall reads garbage.
+ Capacity is never reset by `bytevector-copy!` or any other op, so
+ the invariant only protects fresh / never-overwritten bytevectors.
+
+- [ ] **`bytevector-grow!`** is a public primitive (`bv_grow`) that's
+ effectively only there to make the doubling path testable
+ (test 34). Not in R7RS, not in LISP.md. Either expose it as part of
+ a documented mutable-bytevector API or delete and demote `bv_grow`
+ to internal.
+
+- [ ] **`%record-*` primitives are exposed publicly** in `prim_table`
+ alongside the parameterized record entries. LISP-C.md says "internal,
+ not part of the user-facing primitive list".
+
+- [ ] **PRIM size grew from 16 to 24 bytes uniformly** to fit the
+ parameterized data slot used by record ctors / preds / accessors /
+ mutators. Plain primitives (sys-exit, cons, +, …) waste those 8
+ bytes per instance.
+
+- [ ] **`apply` modification: prim ptr is now passed in `a1`** alongside
+ args in `a0`. All existing primitives ignore `a1`, but any future
+ primitive that uses `a1` for anything else will silently break.
+
+- [ ] **Recursive helpers, host-stack-bound depth.**
+ - `eval_args` recurses once per arg; very long arg lists (>~10k)
+ blow the host stack.
+ - `apply_build_args` recurses once per prepended arg.
+ - `bind_params` is iterative (good).
+
+- [ ] **No tail-call optimization across the named-let body.**
+ `eval_let_named` ends with `%tail(&apply)`, so the apply itself is a
+ tail call. Inside the body the closure can recurse via the bound
+ name only because every tail position in the interpreter uses
+ `%tail`. Worth confirming with a deep-recursion test.
+
+- [ ] **Symbol-table linear scan.** `intern` walks the table from idx 0
+ on every call. LISP-C.md describes a 16384-slot open-addressing
+ hash; we have a 1024-slot linear scan that exits with code 5 on
+ overflow.
+
+- [ ] **No GC.** Bump allocator only. The static arenas are 64 KiB
+ each (heap, symtab, readbuf) — easy to exhaust, no diagnostic.
+
+- [ ] **`m1pp` text_buf was bumped from 256 KiB to 512 KiB and shifted
+ into the previously-unused gap before `OFF_source_tokens`.** This is
+ a toolchain change, not a scheme1 change. Anyone rebuilding `m1pp`
+ from an older `M1pp/M1pp.P1` will overflow text_buf again.
+ Downstream consumers of `m1pp` (M1pp / pokem / hello tests) all
+ pass, but the change should be called out in
+ `vendor/`/`docs/M1.md` as well.
+
+## Test suite caveats
+
+Issues *in* the test files themselves that need fixing or revisiting
+before the suite can be considered authoritative.
+
+- [ ] **`tests/scheme1/15-dot-symbol.scm`** — defines `.foo` (a leading
+ `.` identifier). LISP.md says "a lone `.` is **not** a symbol — it's
+ reserved for dotted-pair syntax", but the spec is silent on whether
+ `.foo` is admissible. Behavior depends on whether the byte after `.`
+ is whitespace/paren (handled by `parse_list`'s peek). Useful as a
+ regression test for the dotted-tail detector but not necessarily
+ desired surface syntax.
+
+- [ ] **`tests/scheme1/19-letstar.scm`** — comment claims "outer x;
+ let*'s x must shadow inside the body" but the test only checks the
+ inner shadow path. Nothing exercises that the outer `x` is *not*
+ affected after the `let*` body returns.
+
+- [ ] **`tests/scheme1/20-letrec.scm`** — uses `(if n n (f #t))` to test
+ letrec self-reference. Recurses *once* (n=44 → truthy → returns 44)
+ so it doesn't actually trigger the recursive case. The comment
+ acknowledges the workaround ("Without numeric primitives we
+ terminate by passing #t at the recursive call"). Needs a real
+ recursion test now that the let family + arith primitives are
+ available; `21-letrec-recursion.scm` partially fills this.
+
+- [ ] **`tests/scheme1/22-named-let.scm`** — recursion is bounded by a
+ flag (`first`) flipping from `#t` to `#f`. Deep iteration not
+ exercised.
+
+- [ ] **`tests/scheme1/27-apply.scm`** — only tests 2-arg
+ `(apply f arglist)` and 3-arg `(apply f x arglist)`. `(apply f)` is
+ unspecified; `(apply f a b … last)` for N>3 is unverified.
+
+- [ ] **`tests/scheme1/40-sys-argv.scm`** — hard-codes `expected-exit =
+ 2`, the count of argv entries the runner happens to pass
+ (`./binary tests/scheme1/40-sys-argv.scm`). Any change to
+ `scripts/run-tests.sh`'s invocation or a wrapper that injects extra
+ args breaks this test silently.
+
+- [ ] **`tests/scheme1/41-fileio.scm`** — opens itself by reading
+ `(car (cdr (sys-argv)))` and passing the bytevector as a path.
+ Relies on the `bv_capacity_for` headroom invariant for NUL
+ termination (no explicit `chars->bv`). Doesn't exercise the
+ `(#f . errno)` branch of `sys-openat` (e.g., a non-existent path).
+ Hard-codes `O_RDONLY = 0` and `mode = 0` instead of using named
+ constants.
+
+- [ ] **`tests/scheme1/42-clone-wait.scm`** — bypasses `sys-wait` /
+ `decode-wait-status` entirely; reads `siginfo_t.si_status` (offset
+ 24) directly from the buffer with `bytevector-u8-ref`. Encodes
+ Linux-x86_64-and-aarch64 siginfo layout; non-portable to other
+ Linux ABIs and to any non-Linux target.
+
+- [ ] **`tests/scheme1/43-prelude.scm`** — verifies `for-each` only by
+ running `(for-each (lambda (x) x) ys)` and checking it doesn't
+ error; doesn't check that `for-each` actually invokes the lambda
+ for each element (no side-effect verification).
+
+- [ ] **`tests/scheme1/44-shell-run.scm`** — name is misleading. It
+ tests `sys-wait` + `decode-wait-status` against a `sys-clone` child
+ but never calls `run`. `run` is what test 45 was supposed to cover,
+ and it doesn't because of the spawn-via-run bug.
+
+- [ ] **`tests/scheme1/45-shell-spawn.scm`** — works around the prelude
+ spawn bug by redefining `spawn` at user level. The prelude's
+ `spawn` / `run` are therefore covered by zero passing tests.
+
+- [ ] **`tests/scheme1/38-record-internal-prims.scm`** — the
+ `%record-*` primitives are tested via the Scheme surface; the only
+ way to invoke them is through the public binding, which conflicts
+ with LISP-C.md's "internal" classification.
+
+- [ ] **No test verifies `(set-car! …)` / `(set-cdr! …)`** — the
+ primitives don't exist; spec requires them.
+
+- [ ] **No test verifies that mutating a literal pair (`'(1 2 3)`) is
+ UB** — undefined behavior is policy, but the policy isn't pinned
+ down by a test.
+
+- [ ] **No test verifies tail-call correctness on deep recursion** —
+ named let, `letrec`, and the eval/apply tail positions all rely on
+ `%tail`/`%tailr`, but nothing recurses thousands of times to confirm
+ no host-stack growth.
+
+- [ ] **No multi-arg `+` / `-` / `*` / `=` / `<` test** because they
+ don't support more than 2 args.
+
+- [ ] **No `(define x …)` followed by `(set! x …)` test** because
+ `set!` doesn't exist.
+
+- [ ] **No quoted-pair test (`'(1 . 2)`)** — only quoted lists are
+ tested. The reader handles dotted pairs but no test pins this.
+
+- [ ] **No `#xHEX` with negative literal `#x-1a` test** — though
+ `parse_one`'s hex branch supports leading `-`, it's untested.
+
+- [ ] **No `#X` (uppercase) test.** The reader accepts both `#x` and
+ `#X`; only the lowercase form is tested.
+
+- [ ] **`tests/scheme1/06-comment.scm`** — verifies `;` comments inside
+ a single form. Doesn't verify a full-line comment between top-level
+ forms.
+
+- [ ] **`tests/scheme1/16-cond.scm`** — verifies short-circuit in the
+ positive direction (later truthy clauses don't fire). Doesn't
+ verify that a `(cond)` with no matching clause and no `else` returns
+ UNSPEC (or whatever the policy is — currently it does, but
+ unspecified by spec).
+
+## Toolchain side-effects
+
+- [ ] **`M1pp/M1pp.P1` was patched** to grow `M1PP_TEXT_CAP` from
+ 256 KiB to 512 KiB and shift `OFF_text_buf` from 0x100680 to
+ 0xc0680. Both tests/M1pp and tests/P1 still pass, but downstream
+ documentation (`docs/M1.md` if any, vendor/seed README, etc.)
+ doesn't mention this and a future pruner walking the m1pp build
+ could undo the change.
+
+## Suggested next steps before shipping
+
+In rough priority order:
+
+1. Track down and fix the prelude `spawn`-via-`run` bug; remove the
+ workaround in test 45.
+2. Add heap, readbuf, and symtab overflow checks; surface them through
+ `error`.
+3. Implement `error`, `display`, `write`, `format` so the abort paths
+ produce something readable.
+4. Fill in the spec-required primitives (`equal?`, `eqv?`, `set-car!`,
+ `set-cdr!`, the comparison family, the bytevector family, the
+ number/string converters).
+5. Variadic arithmetic.
+6. `set!`, `and`, `or`, `pmatch`.
+7. Reader: `"…"` strings, `#\char`, source locations.
+8. Port shell.scm's port record + I/O wrappers.
+9. Add `sys-pipe` / `sys-dup2` / `sys-fork` for real shell pipelines.
+10. Replace the 1024-slot linear-scan symtab with an open-addressing
+ hash per LISP-C.md.
