# 0003 — Widen C integer domain to match Python and asm

**Status:** open (design only — no code changes in this ticket)
**Reporter:** blackops (audit finding, prompted by fox's isqrt review)
**Implementer:** tbd
**Opened:** 2026-04-24

## Problem

Our three implementations disagree on integer width:

| impl | integer representation | exact range |
|---|---|---|
| Python (`lumbda.py`) | native `int` | unbounded (bignum) |
| C (`c/lumbda.h`) | NaN-boxed 48-bit payload, `TAG_INT = 1` | ±2^47 = ±140,737,488,355,328 |
| asm (`asm/lumbda.s`) | tagged int, `sarq $3` / `shlq $3` | 61-bit signed = ±2^60 |

C's ceiling is the lowest. Any integer magnitude > 2^47 silently
truncates in C because `VAL_INT(n)` masks with `PAYLOAD_MASK`
(`0xFFFFFFFFFFFF`). This breaks the *"bit-for-bit identical across
Python ↔ C ↔ asm"* claim made in ticket 0001 and in the whitepaper's
portal section.

### Concrete repro

```bash
cd ~/git/lumbda
cat > /tmp/bigint-test.lsp <<'EOF'
(display (* 1000000 1000000))    (newline)   ; 10^12  — fits 48-bit
(display (* 10000000 10000000))  (newline)   ; 10^14  — fits 48-bit
(display (* 100000000 100000000)) (newline)  ; 10^16  — overflows 48-bit
EOF

python3 lumbda.py /tmp/bigint-test.lsp
# 1000000000000
# 100000000000000
# 10000000000000000      ← correct

./asm/lumbda /tmp/bigint-test.lsp
# 1000000000000
# 100000000000000
# 10000000000000000      ← correct (61-bit tagged int)

./c/lumbda /tmp/bigint-test.lsp
# 1000000000000
# 100000000000000
# -133099161583616       ← silent truncation, not even an error
```

### Exposure surface

- `*`, `expt`, `+` composition: anything producing > 2^47.
- `(random-int n)` (ticket 0001) with `n > 2^47`.
- `(random-state)` returns eight integers in `[0, 2^32)` — fits today,
  but any future design that stores 64-bit words directly breaks.
- Portal round-trip: Python seeds, saves a u64 counter at 10^15, C
  resumes and reads a truncated value. `tests/portal-cross-test.sh`
  does not yet exercise this because its workloads stay under 2^47.
- `isqrt` from commit `6e9d3ea` happens to hide the defect (output is
  always smaller than input) but its callers (cryptographic digest
  code, simulation step counters) do not.

### Why fox's isqrt review caught this

isqrt of a 10^18 input would need a 61-bit argument. Today Python and
asm accept it; C silently truncates the input before isqrt even runs.
No error, no warning — a correct-looking but wrong result.

## Goals

1. C can represent any integer Python can (up to available memory).
2. Portal save from any impl, resume in any other impl, preserves
   integer value exactly. Cross matrix stays 9/9 green.
3. Existing 48-bit fast paths stay fast for the common case
   (most integers in real workloads fit in 48 bits).
4. No change to Python. No change to asm.
5. MOAD-0001 clean: bignum add/mul must not be O(n²) the obvious way
   (see Risk section).

## Non-goals

- Widening asm past 61 bits. Its tagged-int discipline is fine for the
  workloads we ship; a second ticket can take it to bignum if needed.
- Making rational numerator/denominator bignum. Rationals today are
  two `int64_t`; lift separately when a real user hits the ceiling.
- GMP dependency in asm or Python.
- Changing the portal wire format for integers that already fit 48 bits
  (backwards compatible for existing portal files).

## Options weighed

### Option A — Heap-allocated bigint, new `TAG_BIGINT`

New NaN-box tag `TAG_BIGINT = 6`. Small integers (fits 48-bit signed)
stay inline `TAG_INT = 1`. Large integers get boxed as a heap
`Bigint` struct (sign + length + array of 32-bit or 64-bit limbs).

```c
typedef struct Bigint {
    ObjHeader hdr;
    int32_t sign;     // -1, 0, +1
    uint32_t nlimbs;
    uint64_t *limbs;  // little-endian, limb[0] = least significant
} Bigint;
```

Arithmetic dispatch:
- Both inline? Try 64-bit op with overflow check; on overflow, promote.
- Either heap? Call bignum path; result normalizes back to inline if
  it fits.

**Pro:** NaN-boxing stays. Cache-friendly for small ints (still 8
bytes, not 16). JIT fast path for 48-bit arithmetic keeps working
unchanged — the JIT still sees `TAG_INT`; bignum fallback is in the C
runtime, called via existing num_* helpers when the fast guard fails.

**Pro:** Portal format extends cleanly: bigints serialize as decimal
strings (matches Python's `repr(int)`), preserving exact value across
tiers without a wire-format renegotiation for small ints.

**Con:** Every arithmetic op needs a "did this overflow 48 bits?"
guard on the inline path. Cheap if we use `__builtin_mul_overflow` and
friends; costs a branch per op.

**Con:** `TAG_BIGINT` competes for tag space. We use tags 0–5 today; 6
is free. 7 is the last slot (3-bit tag field).

**Con:** GC awareness: `Bigint.limbs` must be `GC_MALLOC`ed (when
Boehm is on) so it is traced/freed. One extra indirection.

**Size:** ~400 lines of new C (add/sub/mul/divmod/compare/from_int64/
to_int64/to_string/from_string) + integration.

### Option B — Abandon NaN-boxing, use a 2-word Value struct

```c
typedef struct { uint64_t tag; uint64_t payload; } Value;
```

Tag word holds type; payload holds any 64-bit value including full
int64_t. For wider integers, payload is a pointer.

**Pro:** Clean. No bit-packing. Doubles, 64-bit ints, and pointers all
sit in payload without tricks.

**Pro:** Debugger-friendly.

**Con:** Every Value is 16 bytes, not 8. Every `Pair`, `Vector`,
`Env`, stack slot, register spill — doubles in size. The VM passes
Values through registers constantly; this is a real perf regression.

**Con:** The entire codebase passes `Value` by value in signatures
(`Value f(Value a, Value b)`). x86_64 SysV passes one `Value` in a
register today; two doubles that. Every builtin signature, every VM
opcode handler, every macro (`VAL_INT`, `VAL_NIL`, `IS_INT`) — touched.

**Con:** The JIT in `c/jit.c` is built around 64-bit values in a
single register. A 16-byte value needs two registers everywhere or a
stack round-trip. Rewrite, not port.

**Size:** The entire C implementation. ~4–6 weeks.

### Option C — Document the 48-bit ceiling, do not fix

Add a note to `docs/whitepaper` and to portal envelope header
documenting that C rejects (or truncates) integers past ±2^47.

**Pro:** Zero code change.

**Con:** Truncates silently. If we switch to loud rejection we
*break* programs that run fine in Python and asm today. Either way,
the cross-impl "bit-for-bit identical" promise becomes conditional.

**Con:** Violates the planet-patching mission. Downstream users who
build simulations (fox's stochastic experiments, Zoe's RNG portal
work) would hit this ceiling and blame Lumbda, not their code.

**Con:** Our own test suite — `tests/functional.lsp` — would need a
guard rail noting "do not exercise integers > 2^47 in shared tests."
That is the wrong direction. A shared test should describe *what
Scheme is*, not what our weakest impl tolerates.

## Recommendation — Option A (heap-allocated bigint, new `TAG_BIGINT`)

Aligned against the eight capital queues:

- **Intellectual capital (gain):** we ship a clean bignum in public
  domain C, portable, no GMP dependency, ~400 LOC. Downstream projects
  that embed Lumbda inherit a bignum for free. Open capital, not rent.
- **Living capital (gain):** the fix removes a class of silent-wrong
  results from simulations downstream users run. No more
  `-133099161583616` when you asked for 10^16. A simulation that
  reports correct numbers serves living systems better than one that
  reports fast but wrong ones.
- **Experiential capital (gain):** "it just works across all three
  impls" becomes true without asterisks. fox's stochastic workflow
  does not need to learn "avoid C for > 2^47" as folklore.
- **Financial capital (neutral):** no rent extraction either way.
- **Material capital (slight cost):** more memory per large integer
  (heap allocation + limb array). Acceptable — small ints still free.

Option B is an attractive redesign but a demolition project, not
cleanup crew. Option C abandons the cross-impl promise. Option A
preserves our existing investment (NaN-boxing, JIT fast path, portal
format for small ints) while extending the domain exactly where it is
broken.

## Migration path — ordered

**Phase 0 — Add the inline overflow guard only (loud, no bignum yet).**
Lets us ship a fail-loud interpreter immediately, buying time for the
bignum work without shipping another release that silently truncates.

1. `c/lumbda.h`: add inline `VAL_INT_CHECKED(n)` that calls
   `lisp_error` if `n` does not fit 48-bit signed. Wire it into
   `c/reader.c` large-literal path and all arithmetic return paths in
   `c/types.c`.
2. `tests/functional.lsp`: add two assertions that exercise 48-bit-fit
   arithmetic; mark any > 2^47 test as C-xfail until Phase 3.

**Phase 1 — Bignum struct and primitives (standalone, no integration).**

3. New file `c/bignum.c` (declarations in `c/lumbda.h`):
   - `Bigint *bi_from_int64(int64_t)`
   - `int64_t bi_to_int64(Bigint *, bool *fits)`
   - `Bigint *bi_add(Bigint *, Bigint *)`, `bi_sub`, `bi_mul`, `bi_neg`
   - `void bi_divmod(Bigint *a, Bigint *b, Bigint **q, Bigint **r)`
   - `int bi_cmp(Bigint *, Bigint *)`
   - `char *bi_to_string(Bigint *)`, `Bigint *bi_from_string(const char *)`
   - `Bigint *bi_normalize(Bigint *)` — trims leading-zero limbs, may
     return a caller-known sentinel meaning "fits in int64_t, unbox me".
4. Unit test `c/bignum_test.c` — add/sub/mul against known-good
   decimal strings from Python. No VM integration yet.

**Phase 2 — Wire bignum into the Value type.**

5. `c/lumbda.h`: add `TAG_BIGINT = 6`, `IS_BIGINT`, `AS_BIGINT`,
   `VAL_BIGINT`, add `OBJ_BIGINT` to `ObjType`.
6. `c/types.c`: rewrite `num_add`, `num_sub`, `num_mul`, `num_neg`,
   `num_cmp`, `to_rational`:
   - Fast path: both inline `TAG_INT`, use `__builtin_*_overflow`. On
     overflow, promote to bigint.
   - Slow path: promote inline to bigint, operate, normalize result
     back to inline if it fits.
7. `c/reader.c` `parse_atom`: when `strtoll` fails with `ERANGE` or
   the value does not fit 48-bit, call `bi_from_string` and return
   `VAL_BIGINT`.
8. `c/printer.c`: `show` for bigint calls `bi_to_string`.

**Phase 3 — JIT fast path.**

9. `c/jit.c`: JIT today compiles arithmetic that assumes `TAG_INT`
   operands. Keep that fast path intact. On overflow check
   (`__builtin_mul_overflow`-equivalent in emitted asm, or use
   `jo`/`jno` after an `imul`), branch out of the JIT fast path into
   the C runtime's `num_mul` (which handles promotion). Bignum never
   runs inside JIT'd code — JIT only handles the inline case.
   - This keeps the fast path at its current speed.
   - Guard: any JIT'd arithmetic that today assumes no overflow must
     add the `jo` trampoline. Missing one = silent truncation regression.

**Phase 4 — Portal.**

10. `c/portal.c` JSON writer: for bigint, emit as
    `{"t":"bigint","v":"1234..."}`. Decimal string, arbitrary length.
11. `c/portal.c` JSON reader: on encountering `{"t":"bigint",...}`,
    call `bi_from_string`, normalize, return a `Value`.
12. `lumbda.py` portal reader: accept `{"t":"bigint",...}` and map to
    Python `int(...)`. Writer emits `{"t":"bigint",...}` only when
    `abs(v) > 2^47` (backwards compatible — small ints stay as bare
    JSON numbers).
13. `asm/lumbda.s`: text portal (`;; lumbda-portal v1`) emits bigints
    as their decimal string — already handles arbitrary int print via
    `number->string`; just needs reader to route strings-that-parse-as-
    integers-larger-than-61-bit into... (deferred to a later asm
    bignum ticket; for now asm rejects portal files containing bigints
    with a clear error, rather than truncating).

**Phase 5 — MOAD audit and tests.**

14. `~/git/unmoad.com/unmoad c/bignum.c` — bignum schoolbook mul is
    O(n·m) in limb counts; that is fine. What MOAD catches: a loop
    that calls `bi_mul` inside `for_each` on a growing list, which
    would be O(n³) in bit-length. Keep bignum ops out of hot loops in
    the runtime itself.
15. `tests/portal-cross-test.sh`: new workload saves `(expt 10 30)`,
    resumes across all 9 producer×consumer cells.
16. `tests/functional.lsp`: add assertions with 10^20 and `(factorial 25)`.

## Test strategy

All must pass before the ticket closes:

1. **Unit (new) — `c/bignum_test.c`**: decimal-string round-trips,
   add/sub/mul against Python `hex(n)` reference vectors, divmod
   against Python `divmod()`, compare with sign/zero edge cases.
2. **Shared functional — `tests/functional.lsp`**: add 20+ assertions
   that exercise integers past 2^47. Because this file runs under
   Python and C, both tiers must agree. (Asm runs this file too but
   its 61-bit ceiling is a separate future ticket — we gate via an
   existing impl-specific skip mechanism or split into
   `functional.lsp` + `functional-bigint.lsp` loaded by Python+C only.)
3. **Portal cross — `tests/portal-cross-test.sh`**: new large-int
   workload. All 9 producer×consumer cells green. Any cell that has a
   bigint consumer which does not support bigints yet must report a
   clear error, not silently truncate.
4. **MOAD scan — `~/git/unmoad.com/unmoad c/`**: clean on all changed
   files.
5. **Perf check — `tests/web-benchmark.sh`**: C tier throughput does
   not regress by more than 5% on workloads that stay inside 48-bit.
   Inline path is the 99th percentile case; regression there is real
   cost.
6. **The original repro** above prints `10000000000000000` under C.

## Risk section

**MOAD-0001 in bignum itself (the scariest risk).**
- Schoolbook multiply is O(n·m) in limb counts — acceptable for n, m
  up to a few thousand limbs (realistic max for our users).
- String formatting the obvious way (`repeated divide by 10`) is O(n²)
  in digit count. Use a divide-and-conquer base conversion for output
  of numbers with > 100 digits. Cite a source in the code comment.
- Ticket 0001 lesson: ML agents (blackops included) propagate O(n²)
  loops by default. `unmoad` on bignum.c is **mandatory**, not
  optional.

**JIT regression (silent wrong answers).**
- The JIT today assumes `TAG_INT` arithmetic does not overflow 48
  bits. Phase 3 adds the `jo`/`jno` trampoline. A single missed JIT
  emit site = regression back to silent truncation, worse than
  today because portal tests might pass while random production
  workloads truncate.
- Mitigation: add a JIT property test that runs every JIT'd op on
  inputs straddling the 48-bit boundary and asserts the result
  matches the interpreter path.

**Portal backwards compatibility.**
- Old portal files (written before this ticket ships) contain bare
  JSON integers only. New readers must accept both bare and
  `{"t":"bigint",...}`. Writers should prefer bare for small ints to
  keep files readable.

**Memory and GC.**
- `Bigint.limbs` must be allocated via `GC_MALLOC` (Boehm on) so it
  gets freed when the `Bigint` becomes unreachable. Without Boehm,
  limbs leak today (consistent with how other heap objects behave in
  the non-GC build — not worse, but worth naming in code comments).

**Asm divergence.**
- This ticket does NOT fix asm's 61-bit ceiling. A program that
  uses 2^62 in Python + C will still misbehave in asm. The whitepaper
  and `asm/README` must acknowledge this, and a follow-up ticket
  (0004?) can apply the same pattern to asm (hand-rolled bignum via
  the asm heap bump allocator, new tag above the 3-bit region).

**Effort estimate.**
- **Medium** (Phase 0–4, Python+C): ~2 weeks with tests.
- **Large** if we also do asm: +2 weeks.
- **Small** if we ship Phase 0 alone (fail-loud, no bignum): ~1 day.
  Proposal: ship Phase 0 immediately as a stopgap under this same
  ticket, then the full fix as a follow-on.

## Deliverables (on full implementation)

- [ ] `docs/tickets/0003-c-int-widening.md` (this ticket)
- [ ] `c/bignum.c`, `c/bignum_test.c` — new
- [ ] `c/lumbda.h` — `TAG_BIGINT`, `OBJ_BIGINT`, `Bigint` struct,
      `VAL_BIGINT`, `AS_BIGINT`, `IS_BIGINT`
- [ ] `c/types.c` — `num_*` routed through bignum on overflow
- [ ] `c/reader.c` — large-literal fallthrough to `bi_from_string`
- [ ] `c/printer.c` — bigint show
- [ ] `c/portal.c` — JSON read/write for bigint
- [ ] `c/jit.c` — overflow trampoline on inline `TAG_INT` fast path
- [ ] `lumbda.py` — portal read/write bigint (emit only for > 48-bit)
- [ ] `tests/functional.lsp` — 20+ new bigint assertions
- [ ] `tests/portal-cross-test.sh` — large-int workload across 9 cells
- [ ] Whitepaper — update §x noting C integer domain now unbounded
- [ ] `make test-all` green
- [ ] `unmoad` clean on `c/bignum.c` and all changed files
