Counter-fold
counter-fold reads the STATE of a binary counter — the SET of its set bits, one JSON non-negative integer bit-index per line (JSON Lines) — and folds it into the NEXT value by adding ONE, using a HAND-BUILT ripple carry (clear the trailing run of set low bits, set the next clear bit), with zero dependencies. The counter's value is the sparse binary number sum of 2**i over the set bits, and it is UNBOUNDED: a bit index is a POSITION, small even when the value is astronomical (a 2**100 counter is just bit {100}), so it counts past 2**53 with no loss — it never holds the value as a native number. Output is the SAME SHAPE as input — the new set of set bits, one index per line, sorted — so the gift is CLOSED UNDER ITS OWN I/O: its output pipes straight back into itself, and counter-fold | counter-fold == counter-fold --steps 2. That closed loop is the point: the counter's state circulating through its own output channel, each pass advancing it one tick — Shea's mercury delay line as a counter. --steps N adds N in-process (N=0 canonicalises: dedup + sort). Because the set bits are sorted and duplicates collapse, the SAME value in ANY order folds to a BYTE-IDENTICAL record. Same counter in → counter+1 out, in Node or a browser.
The honest edge
counter-fold is ONE deterministic binary counter incremented N times, its +1 a hand-built ripple carry — NOT a general adder (it adds ONE per step via --steps N; it does not add two counters), NOT a bounded register (it is sparse and unbounded, so it never overflows), and NOT a value printer (it emits the SET of set bits, the counter's state; value = sum of 2**i). The output is the same shape as the input, so it is closed under its own I/O (counter-fold | counter-fold == --steps 2). Fully order-independent — duplicates collapse, output sorted.
Run it
printf '%s\n' 0 1 | node counter-fold.js # counter+1 as sorted JSONL bit indices; --steps N (+N; 0 canonicalises); exit 0 ok | 2 input error
test_counter-fold.js (29/29: ripple-carry correctness on known values — 0->1, 3->4 through a run of ones, 11->12, 5->6 gap-stops-carry, 7->8 — agreement with an INDEPENDENT BigInt value-arithmetic oracle (decode bits->sum 2**i->+N->re-encode, a different method than the ripple carry) across 9 vectors x 5 step-counts; the TIER-B closure (--steps N == piping the fold into itself N times); UNBOUNDED past 2**53 ({60}/{100}/all-ones-0..59+1=={60}); determinism; order-independence shuffled==sorted; dedup + steps-0 canonicalisation; numeric/steps honesty throws) + out-of-band conformance conform_counter-fold.cjs (51/51 GREEN, subprocess-driven, signed 723dd8e8031bd2f2, independent BigInt value oracle + wrong-carry mutation bite proven RED 15/51)
Zero dependencies, Node or browser, deterministic
The code — every file that ships
counter-fold.js183 lineson GitHub →
#!/usr/bin/env node
/**
* counter-fold — a hand-built binary counter, one increment as a FOLD, in a trace loop.
*
* WHAT
* Reads the STATE of a binary counter -- the SET of its set bits, one non-negative
* integer bit-index per line (JSON Lines) -- and folds it into the counter's NEXT
* value by adding ONE, using a hand-built RIPPLE CARRY (clear the trailing run of
* set low bits, set the next clear bit). Output is the same shape as input: the new
* set of set bits, one index per line, sorted. So the gift is CLOSED UNDER ITS OWN
* I/O -- its output pipes straight back into itself:
* counter-fold < s0 | counter-fold | counter-fold == counter-fold --steps 3 < s0
* That feedback -- the counter's state circulating through its own output channel,
* each pass advancing it by one tick -- is Shea's mercury delay line as a COUNTER
* (Loop 1.0's loop-line memory generalized): a register that counts by feeding its
* own state back. It is the Tier-B property: the reducer transition stays the `fold`
* atom; the loop (↻) is only wrapped around it, no new primitive. --steps N
* internalizes that loop (adds N).
*
* THE INCREMENT (a hand-built ripple carry, not native +1)
* The counter's value is the sparse binary number whose set bits are the input:
* value = sum of 2**i over the set bits i. Adding one is a ripple carry: starting
* at bit 0, clear each set bit in the trailing run of ones, then set the first clear
* bit reached. {0,1,3} (value 11) -> clear 0, clear 1, set 2 -> {2,3} (value 12).
* The counter is UNBOUNDED and SPARSE: only set bits are represented, and a bit
* index is a position (small even when the value is astronomical), so the counter
* counts past 2**53 with no loss -- it never holds the value as a native number.
*
* USAGE
* node counter-fold.js [--steps N] [FILE] # stdin if no FILE
* printf '%s\n' 0 1 | node counter-fold.js # counter = 3, +1 -> 4
* -> 2
* --steps N add N in-process (default 1). N=0 canonicalises the input (dedups +
* sorts the bit set) without incrementing.
* --help
*
* EXIT CODES
* 0 success
* 2 input error: a line that is not a FINITE, NON-NEGATIVE INTEGER (a bit index);
* a bad --steps (non-integer or < 0); a missing file or a directory. Always a
* clean one-line message on stderr, never a stack trace.
*
* EDGE (what this is NOT)
* ONE deterministic binary counter incremented N times -- NOT a general adder (it
* adds ONE per step, via --steps N; it does not add two counters), NOT a bounded
* register (it is sparse and unbounded, so it never overflows), and NOT a value
* printer (it emits the SET of set bits, the counter's state -- value = sum of 2**i).
* Bits are unordered on input (a SET -- duplicates collapse, order is irrelevant)
* and SORTED on output (ascending), so the same counter value is a byte-identical
* record regardless of input order.
*
* Zero dependencies. Node builtin `require('fs')` for file reads only; runs in a
* browser with no require (attaches `counterFold` to window.ForestGifts). MIT.
*/
"use strict";
/* one +1 ripple-carry step over a Set of bit indices -> a new Set of bit indices */
function step(bits) {
var next = new Set(bits);
var i = 0;
while (next.has(i)) { next.delete(i); i++; } // clear the trailing run of set low bits
next.add(i); // set the first clear bit (the carry lands)
return next;
}
/* parse JSONL bit indices -> Set of ints; throws on a non-negative-integer line */
function parse(text) {
var bits = new Set();
var lines = String(text).split("\n");
for (var i = 0; i < lines.length; i++) {
var raw = lines[i];
if (raw.charCodeAt(raw.length - 1) === 13) raw = raw.slice(0, -1); // CRLF
if (raw.length === 0) continue; // blank line skipped
var v;
try { v = JSON.parse(raw); }
catch (e) { throw new Error("line " + (i + 1) + ": not valid JSON: " + raw); }
if (typeof v !== "number" || !isFinite(v) || Math.floor(v) !== v || v < 0) {
throw new Error("line " + (i + 1) + ": bit index must be a finite non-negative integer: " + raw);
}
bits.add(v);
}
return bits;
}
/* sorted array of bit indices from a Set (ascending) -> canonical order */
function sortedBits(bits) {
var arr = [];
bits.forEach(function (b) { arr.push(b); });
arr.sort(function (a, b) { return a - b; });
return arr;
}
/**
* Fold a JSONL bit-set forward N increments (+N).
* @param {string} text JSONL of non-negative integer bit indices (the counter's set bits)
* @param {{steps?:number}} opts steps N (integer >= 0; default 1)
* @returns {{steps:number, count:number, bits:number[]}} count = number of set bits
* @throws {Error} on a bad line or a bad steps value.
*/
function fold(text, opts) {
opts = opts || {};
var steps = opts.steps === undefined ? 1 : opts.steps;
if (typeof steps !== "number" || !isFinite(steps) || Math.floor(steps) !== steps || steps < 0) {
throw new Error("steps must be an integer >= 0 (got " + steps + ")");
}
var bits = parse(text);
for (var s = 0; s < steps; s++) bits = step(bits);
var arr = sortedBits(bits);
return { steps: steps, count: arr.length, bits: arr };
}
/* ------------------------------------------------------------------ exports */
if (typeof module !== "undefined" && module.exports) {
module.exports = { fold: fold, step: step, parse: parse, sortedBits: sortedBits };
}
if (typeof window !== "undefined") {
window.ForestGifts = window.ForestGifts || {};
window.ForestGifts.counterFold = fold;
}
/* ----------------------------------------------------------------- CLI main */
function main(argv) {
var args = argv.slice(2);
var steps = 1, file = null;
for (var i = 0; i < args.length; i++) {
var a = args[i];
if (a === "--help" || a === "-h") {
process.stdout.write(
"usage: counter-fold.js [--steps N] [FILE]\n" +
" --steps N add N in-process (default 1; N=0 canonicalises)\n" +
" (no FILE) read the counter's set bits from stdin\n" +
" FILE read the counter's set bits from a file\n" +
" --help\n" +
"Each non-blank line is one set bit as a JSON non-negative integer. Output is\n" +
"the next value's set bits, same shape, one index per line, sorted -- so\n" +
"`counter-fold | counter-fold` adds two (closed under its own I/O).\n"
);
process.exit(0);
} else if (a === "--steps") {
var nx = args[i + 1];
if (nx === undefined) { process.stderr.write("counter-fold: --steps requires a value\n"); process.exit(2); }
steps = Number(nx); i += 1;
} else if (a.indexOf("--steps=") === 0) {
steps = Number(a.slice(8));
} else if (a.charAt(0) === "-" && a !== "-") {
process.stderr.write("counter-fold: unknown option: " + a + "\n"); process.exit(2);
} else {
if (file !== null) { process.stderr.write("counter-fold: more than one FILE given\n"); process.exit(2); }
file = a;
}
}
function run(text) {
var rec;
try { rec = fold(text, { steps: steps }); }
catch (e) { process.stderr.write("counter-fold: " + e.message + "\n"); process.exit(2); return; }
// closed under I/O: emit the SET of set bits as JSONL (one index per line)
var out = "";
for (var i = 0; i < rec.bits.length; i++) out += JSON.stringify(rec.bits[i]) + "\n";
process.stdout.write(out);
}
if (file === null || file === "-") {
var chunks = [];
process.stdin.on("data", function (c) { chunks.push(c); });
process.stdin.on("end", function () { run(Buffer.concat(chunks).toString("utf8")); });
} else {
var fs = require("fs");
var text;
try {
var st = fs.statSync(file);
if (st.isDirectory()) { process.stderr.write("counter-fold: is a directory: " + file + "\n"); process.exit(2); return; }
text = fs.readFileSync(file, "utf8");
} catch (e) {
process.stderr.write("counter-fold: cannot read file: " + file + "\n"); process.exit(2); return;
}
run(text);
}
}
if (typeof require !== "undefined" && require.main === module) {
main(process.argv);
}
test_counter-fold.js92 lineson GitHub →
#!/usr/bin/env node
/* test_counter-fold.js — external battery for the counter-fold gift.
*
* node test_counter-fold.js -> exit 0 GREEN / non-zero RED
*
* Proves ripple-carry correctness on known counter values (0->1, 3->4 through a run
* of ones, 11->12), agreement with an INDEPENDENT value-arithmetic method (decode the
* bit set to a BigInt = sum of 2**i, add N, re-encode -- a different method than the
* hand-built ripple carry), the TIER-B closure property (--steps N equals piping the
* fold into itself N times -- the trace ↻ loop), UNBOUNDEDNESS past 2**53, plus
* determinism, order-independence, empty/steps-0, dedup, and numeric-honesty errors.
*/
"use strict";
var m = require("./counter-fold.js");
var fold = m.fold;
var pass = 0, fail = 0;
function ok(name, cond) { if (cond) pass++; else { fail++; console.error(" RED " + name); } }
function throws(name, fn) { try { fn(); fail++; console.error(" RED " + name + " (did not throw)"); } catch (e) { pass++; } }
function J(v) { return JSON.stringify(v); }
function jsonl(bits) { return bits.map(function (b) { return J(b); }).join("\n"); }
function toJSONL(rec) { return rec.bits.map(function (b) { return J(b); }).join("\n"); }
/* ---- independent method: bit set <-> BigInt value (NOT a ripple carry) ------ */
function bitsToVal(bits) { var v = 0n; for (var i = 0; i < bits.length; i++) v += (1n << BigInt(bits[i])); return v; }
function valToBits(v) { var b = [], i = 0n; while (v > 0n) { if (v & 1n) b.push(Number(i)); v >>= 1n; i++; } return b; }
function expectPlus(bits, n) { return valToBits(bitsToVal(bits) + BigInt(n)); }
/* ---- ripple carry on known counter values ---------------------------------- */
ok("0 -> 1 : {} +1 == {0}", J(fold("", { steps: 1 }).bits) === J([0]));
ok("1 -> 2 : {0} +1 == {1}", J(fold(jsonl([0]), { steps: 1 }).bits) === J([1]));
ok("3 -> 4 : {0,1} +1 == {2} (carry through a run of ones)", J(fold(jsonl([0, 1]), { steps: 1 }).bits) === J([2]));
ok("11 -> 12 : {0,1,3} +1 == {2,3}", J(fold(jsonl([0, 1, 3]), { steps: 1 }).bits) === J([2, 3]));
ok("5 -> 6 : {0,2} +1 == {1,2} (gap stops the carry)", J(fold(jsonl([0, 2]), { steps: 1 }).bits) === J([1, 2]));
ok("7 -> 8 : {0,1,2} +1 == {3}", J(fold(jsonl([0, 1, 2]), { steps: 1 }).bits) === J([3]));
/* ---- agreement with the INDEPENDENT value-arithmetic method, over vectors x N */
var vectors = [[], [0], [1], [0, 1], [0, 2], [0, 1, 2, 3], [5], [3, 7], [0, 1, 2, 3, 4, 5]];
var Ns = [1, 2, 3, 7, 16];
var allAgree = true;
vectors.forEach(function (v) {
Ns.forEach(function (n) {
if (J(fold(jsonl(v), { steps: n }).bits) !== J(expectPlus(v, n))) allAgree = false;
});
});
ok("agrees with independent BigInt value-arithmetic across vectors x steps", allAgree);
/* ---- TIER-B closure: --steps N == piping the fold N times ------------------- */
var seed = [0, 2, 5]; // value 37
function piped(text, n) { var t = text; for (var i = 0; i < n; i++) t = toJSONL(fold(t, { steps: 1 })); return t; }
[2, 3, 4, 8].forEach(function (n) {
ok("closed under I/O: --steps " + n + " == piped " + n,
toJSONL(fold(jsonl(seed), { steps: n })) === piped(jsonl(seed), n));
});
/* ---- UNBOUNDED: counts past 2**53 with no loss ----------------------------- */
ok("unbounded: {60} (2**60) +1 == {0,60}", J(fold(jsonl([60]), { steps: 1 }).bits) === J([0, 60]));
ok("unbounded: all ones 0..59 (2**60 - 1) +1 == {60}",
J(fold(jsonl([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59]), { steps: 1 }).bits) === J([60]));
ok("unbounded: {100} +1 stays exact (value > Number.MAX_SAFE_INTEGER)",
J(fold(jsonl([100]), { steps: 1 }).bits) === J([0, 100]));
/* ---- determinism + order-independence (a SET; shuffled == base) ------------- */
var shuffled = [5, 0, 2];
ok("order-independent: shuffled seed == sorted seed (1 step, byte-identical)",
J(fold(jsonl(shuffled), { steps: 1 }).bits) === J(fold(jsonl(seed), { steps: 1 }).bits));
ok("determinism: folds twice identical", J(fold(jsonl(seed), { steps: 3 })) === J(fold(jsonl(seed), { steps: 3 })));
/* ---- dedup: duplicate set bits collapse (a set) ---------------------------- */
ok("duplicate bits collapse (steps 0 canonicalises)",
J(fold("0\n0\n2\n", { steps: 0 }).bits) === J([0, 2]));
ok("steps 0 sorts + dedups", J(fold("3\n0\n3\n", { steps: 0 }).bits) === J([0, 3]));
/* ---- empty stream + record shape ------------------------------------------- */
ok("empty +0 -> {steps:0,count:0,bits:[]}", J(fold("", { steps: 0 })) === J({ steps: 0, count: 0, bits: [] }));
ok("count is the number of set bits (popcount)", fold(jsonl([0, 1, 2, 3]), { steps: 0 }).count === 4);
ok("blank lines skipped", J(fold("0\n\n2\n\n", { steps: 0 }).bits) === J([0, 2]));
ok("CRLF trimmed", J(fold("0\r\n1\r\n", { steps: 1 }).bits) === J([2]));
/* ---- numeric / shape honesty: hard errors ---------------------------------- */
throws("negative bit index -> throw", function () { fold("-1\n", { steps: 1 }); });
throws("non-integer bit index -> throw", function () { fold("0.5\n", { steps: 1 }); });
throws("non-finite bit index -> throw", function () { fold("1e999\n", { steps: 1 }); });
throws("non-number line -> throw", function () { fold("\"x\"\n", { steps: 1 }); });
throws("bad JSON line -> throw", function () { fold("0\nabc\n", { steps: 1 }); });
/* ---- bad steps guards ------------------------------------------------------ */
throws("steps=-1 -> throw", function () { fold("0", { steps: -1 }); });
throws("steps=1.5 -> throw", function () { fold("0", { steps: 1.5 }); });
console.log((fail === 0 ? "GREEN" : "RED") + ": " + pass + " assertions passed, " + fail + " failed [test_counter-fold]");
process.exit(fail === 0 ? 0 : 1);