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

New issue

Closed

opened 2026-10-08 13:42:01 +00:00 by orion · 2 comments

orion commented

2026-10-08 13:42:01 +00:00

Collaborator

Goal

ConsStack<Item>: an implementation of Stack as a persistent cons list, so that a copy (var rest = stack) shares its tail and push/pop are O(1) with no copy (COLLECTIONS.md section 3.3 table, section 3.10 point 4). The tour (section 6, question 6) shows it doing what a List cannot.

Acceptance criteria

public type ConsStack<Item> with Stack<Item>, From<Iterate<Item>>; push, pop, peek, length, iterate (top first), clear, Equals/Hash as ArrayStack.
Copy semantics: pushing or popping on a copy never changes the original, and the copies share nodes (no copy of the tail).
ConsStack.of(...) / literal through From as for ArrayStack.
Conformance program including the persistence cases (undo/backtracking shape); benchmark against ArrayStack for keeping many versions.

Seed impact

None. A new public type in std/collections written in plain TorbScript over a List; no syntax change, no new native, no runtime change (runtime/list.c stays the one storage, COLLECTIONS.md section 3.10 point 5), and the compiler looks up none of the new names by string (section 6a). Not breaking: only additions.

Size

One PR, one feat(collections) commit (plus tests and docs in the same commit or a second test/docs one).

Common to the C7 types

Export from std/collections/src/lib.trb (public use ...), doc comments with the cost profile of the implementation, as ArrayQueue has.
A conformance program in tests/conformance/ (.trb + .expected), run natively and in the VM, in the style of queue-grows.trb.
A benchmark in benchmarks/ (one small program plus its C counterpart, see benchmarks/README.md) against the array implementation. It is a measurement, not a gate.
skills/ regenerated when docs change; the worker does not run gates locally, CI does.

Source

COLLECTIONS.md C7, parent #139

## Goal `ConsStack<Item>`: an implementation of `Stack` as a persistent cons list, so that a copy (`var rest = stack`) shares its tail and `push`/`pop` are O(1) with no copy (COLLECTIONS.md section 3.3 table, section 3.10 point 4). The tour (section 6, question 6) shows it doing what a `List` cannot. ## Acceptance criteria - [ ] `public type ConsStack<Item> with Stack<Item>, From<Iterate<Item>>`; `push`, `pop`, `peek`, `length`, `iterate` (top first), `clear`, `Equals`/`Hash` as `ArrayStack`. - [ ] Copy semantics: pushing or popping on a copy never changes the original, and the copies share nodes (no copy of the tail). - [ ] `ConsStack.of(...)` / literal through `From` as for `ArrayStack`. - [ ] Conformance program including the persistence cases (undo/backtracking shape); benchmark against `ArrayStack` for keeping many versions. ## Seed impact None. A new public type in `std/collections` written in plain TorbScript over a `List`; no syntax change, no new native, no runtime change (`runtime/list.c` stays the one storage, COLLECTIONS.md section 3.10 point 5), and the compiler looks up none of the new names by string (section 6a). Not breaking: only additions. ## Size One PR, one `feat(collections)` commit (plus tests and docs in the same commit or a second `test`/`docs` one). ## Common to the C7 types - Export from `std/collections/src/lib.trb` (`public use ...`), doc comments with the cost profile of the implementation, as `ArrayQueue` has. - A conformance program in `tests/conformance/` (`.trb` + `.expected`), run natively and in the VM, in the style of `queue-grows.trb`. - A benchmark in `benchmarks/` (one small program plus its C counterpart, see `benchmarks/README.md`) against the array implementation. It is a measurement, not a gate. - `skills/` regenerated when docs change; the worker does not run gates locally, CI does. ## Source - [COLLECTIONS.md C7](https://git.torb.dev/torbscript/language/blob/main/docs/design/COLLECTIONS.md#L992), parent #139

orion added the

loop

ready

labels

2026-10-08 13:42:01 +00:00

orion referenced this issue

2026-10-08 13:42:17 +00:00

collections: BankersQueue, a persistent queue with shared structure (C7) #199

orion referenced this issue

2026-10-08 13:42:17 +00:00

collections: RingList, ConsStack, BankersQueue, Heap (C7) #139