Signatures Stitched in Structure

A bookbinder works with signatures—folded bundles of pages, usually four sheets nested to make sixteen pages. You stitch them together along the spine, and once bound, the book is permanent. You can’t yank page 47 out without destroying the structure. You can add an appendix, sure, but the original remains intact. If you want a different version, you bind a new copy.

Persistent data structures work exactly this way. When you “modify” a persistent vector in Clojure, you’re not actually changing anything—you’re creating a new version that shares most of its structure with the old one. The original remains, untouched, available for anyone still holding a reference to it.

Clojure’s vectors are built on wide tries with a branching factor of 32. Adding an element means copying only the path from root to the affected leaf—usually three or four nodes. Everything else is shared:

(def volume-one ["preface" "chapter-1" "chapter-2" "index"])
(def volume-two (conj volume-one "appendix-a"))

(println volume-one)  ; ["preface" "chapter-1" "chapter-2" "index"]
(println volume-two)  ; ["preface" "chapter-1" "chapter-2" "index" "appendix-a"]

;; Both exist. Neither destroyed the other.

Ada doesn’t have built-in persistent structures, but you can approximate the idea with access types and explicit sharing. Here’s a minimal singly-linked list where “prepending” creates a new head pointing to the existing spine:

with Ada.Text_IO; use Ada.Text_IO;
procedure Signatures is
   type Node;
   type List is access Node;
   type Node is record
      Page : String (1 .. 10);
      Next : List;
   end record;

   First   : List := new Node'("chapter-1 ", null);
   Edition : List := new Node'("preface   ", First);  -- shares First
begin
   Put_Line (Edition.Page);       -- preface
   Put_Line (Edition.Next.Page);  -- chapter-1
   Put_Line (First.Page);         -- chapter-1 still exists independently
end Signatures;

The first edition and the second both exist. Adding a preface didn’t unbind the original.

Phil Bagwell’s 2001 paper on ideal hash tries formalized the structure Clojure uses, but the idea of preserving history through structural sharing goes back to Driscoll, Sarnak, Sleator, and Tarjan’s 1986 work on making data structures persistent. The trade-off is memory—you’re keeping old versions around, at least until garbage collection claims them. But the gain is fearless concurrency: if no one can mutate the structure, no one needs a lock.

The notebook I bound yesterday will never change. The thread went through the signatures; the paste dried on the spine. I can make a new edition, but that first volume holds whatever I wrote in it, permanently. Clojure’s vectors understand the same commitment.