Data.Intern

A deterministic first-seen interner: names to dense integer ids.

Interning a name the first time allocates the next id in sequence, counting from zero; interning it again answers the id it already holds and leaves the table alone. An id is therefore a pure function of the order names were first seen, and of nothing else: no hash, no address, no allocation counter. Two runs that intern the same sequence assign the same ids, so a table can be rebuilt from a replayed trace of names without the ids ever being written down, and a program that keys on interned ids replays byte for byte.

Both directions are kept. ids carries a name to its id and names carries an id back to its name, so the reverse lookup a diagnostic needs costs a lookup rather than a scan of the table. The two agree by construction because the single allocating operation extends both.

The table is an ordinary persistent value, so holding an older one holds the smaller table it was. That is what makes speculative interning cheap to abandon: a pass that interns while exploring a branch it then discards keeps the pre-branch table and the discarded names never occupied an id.

let (t, ids) = intern_all(intern_empty, ["b", "a", "b"])
(ids, intern_name(t, 0), intern_size(t))

([0, 1, 0], Some(b), 2)

Opt-in: not in Base.

Types

`Intern`

type Intern = Intern {
  ids: Map(String, Int),
  names: Map(Int, String),
  next: Int
}

A table of interned names: the forward direction, the reverse direction, and the id the next unseen name receives.

Functions and Values

`intern_empty`

intern_empty : Data.Intern.Intern

The empty table. Nothing is interned, and the first name seen takes id 0.

intern_size(intern_empty)

`intern`

intern : (Data.Intern.Intern, String) -> (Data.Intern.Intern, Int)

Intern name, answering the updated table and its id. A name already in the table keeps its id and the table is returned unchanged; a new one takes the current intern_size as its id.

let (t, i) = intern(intern_empty, "x")
let (t2, j) = intern(t, "y")
let (_t3, again) = intern(t2, "x")
(i, j, again)

(0, 1, 0)

The table’s central verb, named for the operation rather than prefixed with the type it operates on.

`intern_all`

intern_all : (Data.Intern.Intern, List(String)) -> (Data.Intern.Intern, List(Int))

Intern every name in order, answering the final table and the ids in the same order as the names. Repeats within the list resolve to the id their first occurrence allocated.

snd(intern_all(intern_empty, ["a", "b", "a", "c"]))

[0, 1, 0, 2]

`intern_id`

intern_id : (Data.Intern.Intern, String) -> Option(Int)

The id of name, or None when it has never been interned. The lookup never allocates an id, so a probe cannot perturb the numbering a later run has to reproduce.

let (t, _i) = intern(intern_empty, "x")
(intern_id(t, "x"), intern_id(t, "y"))

(Some(0), None)

`intern_name`

intern_name : (Data.Intern.Intern, Int) -> Option(String)

The name that was interned as id, or None when no name holds it.

let (t, _ids) = intern_all(intern_empty, ["a", "b"])
(intern_name(t, 1), intern_name(t, 7))

(Some(b), None)

`intern_size`

intern_size : (Data.Intern.Intern) -> Int

How many distinct names are interned, which is also the id the next unseen name receives. Interning a name already in the table leaves it unchanged.

let (t, _ids) = intern_all(intern_empty, ["a", "b", "a"])
intern_size(t)

Keyboard shortcuts

Prism