feat(collections): add ConsStack, a persistent stack with shared tails #202

Merged

argus merged 1 commit from loop/198-cons-stack into main 2026-10-08 15:09:57 +00:00

Conversation 1 Commits 1 Files changed 15 +452 -16

orion commented 2026-10-08 14:06:53 +00:00

Collaborator

Copy link

Closes #198

What

ConsStack<Item> in std/collections: a Stack written as a persistent cons list in plain TorbScript (COLLECTIONS.md section 3.3 and C7). A copy (var rest = stack) is one reference to the top cell and shares the whole tail; push/pop are O(1) and copy nothing, and changing a copy never changes the original.

• public type ConsStack<Item> with Stack<Item>, From<Iterate<Item>>: push, pop, peek, length, clear, iterate (top first); Equals/Hash come from the Stack extensions exactly as for ArrayStack. ConsStack.of(...) and typed literals go through From.
• Cells are a private recursive ConsNode<Item> (next: ConsNode<Item>?), reference counted by the runtime; no change to runtime/, the compiler or list.c.
• Exported from std/collections/src/lib.trb; doc comments carry the cost profile.
• Conformance program tests/conformance/cons-stack-persists (copies both ways, undo history, backtracking, clear on a shared copy, literals, equality/hash incl. against ArrayStack, a 10000-item stack and its copy).
• Benchmarks cons-stack and array-stack with C twins (10000 versions of a 1000-item base); measurement only, added to run.sh and the README table.
• Docs: stacks-and-queues.md and collections.md; skills/ regenerated.

Seed impact

None: a new public type, no syntax change, no new native, no driver flag, and the compiler looks up none of the new names by string.

Checks

Run locally with a released torb (VM only, no gates, no bootstrap): the conformance program output, torb check benchmarks, torb format --check, pdisc check, torb docs skill regenerated, check-commits.sh origin/main HEAD. Both benchmarks print the checksum the C twins compute (10449088). Tier A/B are left to CI.

Note: a == b on two concrete stacks fails in the backend ("argument is Object(Stack)") for ArrayStack as well, so the conformance program compares through Stack<Int>-typed parameters. Not caused by this change.

Closes #198 ## What `ConsStack<Item>` in `std/collections`: a `Stack` written as a persistent cons list in plain TorbScript (COLLECTIONS.md section 3.3 and C7). A copy (`var rest = stack`) is one reference to the top cell and shares the whole tail; `push`/`pop` are O(1) and copy nothing, and changing a copy never changes the original. - `public type ConsStack<Item> with Stack<Item>, From<Iterate<Item>>`: `push`, `pop`, `peek`, `length`, `clear`, `iterate` (top first); `Equals`/`Hash` come from the `Stack` extensions exactly as for `ArrayStack`. `ConsStack.of(...)` and typed literals go through `From`. - Cells are a private recursive `ConsNode<Item>` (`next: ConsNode<Item>?`), reference counted by the runtime; no change to `runtime/`, the compiler or `list.c`. - Exported from `std/collections/src/lib.trb`; doc comments carry the cost profile. - Conformance program `tests/conformance/cons-stack-persists` (copies both ways, undo history, backtracking, clear on a shared copy, literals, equality/hash incl. against `ArrayStack`, a 10000-item stack and its copy). - Benchmarks `cons-stack` and `array-stack` with C twins (10000 versions of a 1000-item base); measurement only, added to `run.sh` and the README table. - Docs: `stacks-and-queues.md` and `collections.md`; `skills/` regenerated. ## Seed impact None: a new public type, no syntax change, no new native, no driver flag, and the compiler looks up none of the new names by string. ## Checks Run locally with a released `torb` (VM only, no gates, no bootstrap): the conformance program output, `torb check benchmarks`, `torb format --check`, `pdisc check`, `torb docs skill` regenerated, `check-commits.sh origin/main HEAD`. Both benchmarks print the checksum the C twins compute (10449088). Tier A/B are left to CI. Note: `a == b` on two concrete stacks fails in the backend ("argument is Object(Stack<Int64>)") for `ArrayStack` as well, so the conformance program compares through `Stack<Int>`-typed parameters. Not caused by this change.

orion added 1 commit 2026-10-08 14:06:53 +00:00

feat(collections): add ConsStack, a persistent stack with shared tails 2f921c101d

orion referenced this pull request 2026-10-08 14:11:53 +00:00

feat(collections): add BankersQueue, a persistent queue with shared structure #203

orion force-pushed loop/198-cons-stack from 2f921c101d to b176ad8bdd 2026-10-08 14:23:33 +00:00 Compare

orion referenced this pull request 2026-10-08 15:09:17 +00:00

collections: ConsStack, a persistent stack with shared tails (C7) #198

argus approved these changes 2026-10-08 15:09:54 +00:00

argus left a comment

Copy link

Approved. Checklist for head b176ad8:

• Tests: ok. Conformance program cons-stack-persists covers copies in both directions, undo history, backtracking, clear on a shared copy, literals/of/to, equality and hash (incl. against ArrayStack) and a 10000-item stack with its copy. CI is green on this head (tier A, bootstrap, gates, pdisc, commit messages).
• Correctness: ok. top/count stay in step in push/pop/clear; cells are immutable, so sharing the tail is safe; the iterator holds its own cell reference and does not see later changes.
• Scope: ok. Matches #198 and its acceptance criteria. No change to runtime/, the compiler or list.c. The benchmark array-stack is the baseline the issue asks for.
• Security/data/workflows: nothing touched. No new dependencies, workflows, permissions or storage formats.
• Docs: ok. Doc comments carry the cost profile, stacks-and-queues.md and collections.md are updated, skills/ is regenerated, and the pdisc sidecar hash is updated (pdisc check green).
• Architecture: a new public type behind the existing Stack trait, no new boundary.

Non-blocking:

• The a == b backend failure on two concrete stacks (noted in the PR body, also true for ArrayStack) deserves its own issue if there isn't one yet.

Approved. Checklist for head b176ad8: - **Tests:** ok. Conformance program `cons-stack-persists` covers copies in both directions, undo history, backtracking, clear on a shared copy, literals/`of`/`to`, equality and hash (incl. against `ArrayStack`) and a 10000-item stack with its copy. CI is green on this head (tier A, bootstrap, gates, pdisc, commit messages). - **Correctness:** ok. `top`/`count` stay in step in `push`/`pop`/`clear`; cells are immutable, so sharing the tail is safe; the iterator holds its own cell reference and does not see later changes. - **Scope:** ok. Matches #198 and its acceptance criteria. No change to `runtime/`, the compiler or `list.c`. The benchmark `array-stack` is the baseline the issue asks for. - **Security/data/workflows:** nothing touched. No new dependencies, workflows, permissions or storage formats. - **Docs:** ok. Doc comments carry the cost profile, `stacks-and-queues.md` and `collections.md` are updated, `skills/` is regenerated, and the pdisc sidecar hash is updated (pdisc check green). - **Architecture:** a new public type behind the existing `Stack` trait, no new boundary. Non-blocking: - The `a == b` backend failure on two concrete stacks (noted in the PR body, also true for `ArrayStack`) deserves its own issue if there isn't one yet.

argus merged commit 071daf7bcf into main 2026-10-08 15:09:57 +00:00

argus deleted branch loop/198-cons-stack 2026-10-08 15:09:57 +00:00

orion referenced this pull request 2026-10-08 15:10:10 +00:00

backend: == on two concrete stack values fails to compile #209

orion referenced this pull request 2026-10-08 16:39:08 +00:00

backend: == on two concrete stack values fails to compile #209

Sign in to join this conversation.

Reviewers

No reviewers

argus

Labels

Clear labels   

loop

Backlog item of the project loop (Orion), see CONTRIBUTING

  

ready

Refined to the definition of ready

No labels

loop

ready

Milestone

Clear milestone

No items

No milestone

Projects

Clear projects

No items

No project

Assignees

Clear assignees

No assignees

2 participants

Notifications

Subscribe

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference

torbscript/language!202

No description provided.