hash_consing: hash-consed terms selected by templates, whose Ids record a shape, and a term rewrite that makes a program use them

A GENERIC LIBRARY: it knows no constructor of any calculus and keeps no configuration but the templates that files and declared/1 declare.

HOW TO USE IT. A file is written as the program that does not intern, loads this library and names, by templates, the terms to intern:

:- module(steps, [step/2, built/2]).
:- use_module(library(hash_consing), []).
:- hash_consing:rewritten([apply(lambda(_), _), lambda(_), variable(_)]).

step(apply(lambda(Body), Argument), beta(Body, Argument)).

built(Function, Applied) :-
    Applied = apply(Function, variable(0)).

A term is interned when a template of its constructor matches it (TEMPLATES ARE PATTERNS, below); here an application is interned when its first argument is a lambda, and any other application stays a plain compound whose arguments are represented in turn. Files that hand such terms to each other declare the same templates, most simply by including one file that holds the directive. Code that did not go through the rewrite crosses the boundary explicitly:

?- hash_consing:internalized([apply(lambda(_), _), lambda(_), variable(_)],
                             apply(lambda(variable(0)), variable(1)), Id),
   steps:step(Id, Result),
   hash_consing:externalized(Result, External).
Id = '__hash_consed_apply/2'('lambda/1', <handle>),
External = beta(variable(0), variable(1)).

With the list [] the file loads unchanged, which is the program without interning. The test test/hash_consing.plt loads the fixtures in `test/hash_consing_fixtures/` and compares what the rewrite makes of them with the snapshots in `test/hash_consing_snapshots/`, the place to read exact rewritten clauses.

`intern(?Term, ?Id)` IS ONE RELATION WITH TWO DIRECTIONS (user, 2026-09-17: a binary predicate that upserts forwards and looks up backwards). Term is a ground term whose subterms are represented already. Called with Id bound it looks the term up (and with Term bound as well it is a check that inserts nothing); called with Id unbound, or bound to an Id pattern whose Handle is unbound, it inserts Term unless it is there and answers its Id. It fails, inserting nothing, when no template of Term's constructor matches Term (user, 2026-09-26: a term that matches no template is not interned, even when its constructor has templates), and raises existence_error(templates, Name/Arity) when the constructor has no template in this process, which is most likely a missing declaration (user, 2026-09-26, approving the change). A value that is no Id matches nothing and the call fails, as a pattern that does not match fails without interning (user ruling, 2026-09-17: an uninterned instance at an Id position fails to unify rather than raising). The store is canonical (the same term, the same Id), idempotent and monotone (it only grows and backtracking does not shrink it), so an answer once given is never contradicted. An Id is abstract: only ==, intern/2, represented/2, is_id/1 and the two boundary predicates look at it.

AN ID IS '__hash_consed_Name/Arity'(Handle) OR '__hash_consed_Name/Arity'(Shape, Handle). Name/Arity is the root constructor of the term and Handle the node handle of one trie, the store. The root is in the functor name so that the rewrite turns a head pattern apply(F, X) into an Id pattern that first argument indexing tells apart by constructor, and a value of another constructor, or no Id at all, fails at head unification without a lookup (probe, 2026-09-17: with one functor for every Id, 156 ms against 0.9 ms for 1000 calls over 2000 clauses). The prefix follows SWI-Prolog's convention for names a library synthesises (library(apply_macros)'s '__aux_maplist/N_...'); a leading $ is reserved for the system.

THE SHAPE is there for clauses told apart by an INNER constructor,

step(apply(lambda(Body), Argument)) :- ...
step(apply(closure(Capture), Argument)) :- ...

whose heads would otherwise be one Id pattern, every candidate clause paying a lookup before it fails. Shape is ONE ATOM that spells the constructors found below the root, as far as the term's template says (user, 2026-09-20: the Id keeps one layer, the shape may have several; the layers are joined into one atom, not kept as several shapes; how deep is configurable). Under the templates apply(lambda(_), _) and apply(closure(_), _) the heads above become step('__hash_consed_apply/2'('lambda/1', Handle)) and step('__hash_consed_apply/2'('closure/1', Handle)), and the deep index SWI-Prolog builds on the first argument of the first argument tells them apart without a lookup (benchmark, 2026-09-20: 1000 calls over 2000 such clauses, 621 ms without the shape and 3 ms with it; upserts 46 percent slower; the store no larger).

THE ID STILL HAS ONE LAYER. The shape is not in the functor name, because a shallow pattern apply(F, X) has to match the Ids of every shape and the set of inner constructors is open across files; and the Id holds no Id of a subterm, because a truncation would give one term two spellings and split == and the table keys. A shape is a function of the content and of the constructor's templates, so the Handle determines it and the store stays canonical.

TEMPLATES ARE PATTERNS, in one syntax for every constructor (user, 2026-09-20: one syntax, not three; user, 2026-09-26: hash_consing is based on patterns, not on constructors). An element of a list of templates is a constructor applied to one of these at each argument position (a constructor of arity zero is its atom):

_                  any argument; nothing is recorded
*                  any argument; its root constructor is recorded
a nested template  an argument whose root constructor is the template's
                   and whose arguments match the template's arguments;
                   its root is recorded, and what the template records
                   below it

* records the root constructor of the term the argument stands for, Name/Arity, whether that term is interned or not, and - for a number or a string. There is no alternative inside a template, and ; is an ordinary constructor: the alternatives of a constructor are several templates in the list, because Prolog's ; is a disjunction whose two sides can both hold, and templates are not predicates (user, 2026-09-26).

A CONSTRUCTOR'S TEMPLATES ARE TRIED IN ORDER, the order of the list, and the first that matches a term is the term's template; the templates after it are not looked at, and a term has one template or none (user, 2026-09-26: the parts where templates overlap use the first matching template; matching several templates at once has no meaning). The shape is what that template records, spelled as the recorded descriptions joined by commas, '' when it records nothing. Under apply(apply(*, _), _) then apply(*, _), the term apply(apply(lambda(B), Y), X) has the shape 'apply/2(lambda/1)' and apply(lambda(B), X) the shape 'lambda/1'; under apply(apply(*, _), _) alone the second is not interned. A template that one earlier template always takes first raises while it is declared, so a constructor whose templates record nothing has the one template `Name(_, ..., _)`, and its Ids have no shape; the Ids of any other constructor have one. Two templates that record different positions can spell the same atom for different terms, which only keeps the index from telling their clauses apart.

MATCHING AND RECORDING READ THE TERM, not how its subterms are represented: an argument that is an Id is read through the store and an argument that is a plain compound as it is, and both give the same root and arguments. At a * the root of an Id is read off its functor name, with no lookup; a nested template costs one trie_term/2 on an argument that is an Id. The spelling of a shape is remembered in a trie keyed by its structure, so an atom is built once per structure; the atoms are finitely many, bounded by the templates and the constructors.

ONE LIST OF TEMPLATES PER CONSTRUCTOR, PER PROCESS: the first declaration of a constructor, by rewritten/1, declared/1 or internalized/3, fixes its list, and another declaration with other templates or another order raises permission_error(reconfigure, interned_constructor, Name/Arity), because whether a term is interned and what its shape is must agree wherever it is handed (agent design decision, 2026-09-20, for one template, and 2026-09-26 for a list, in plans the user approved; between files the library checks nothing else, by the user's ruling of 2026-09-17: which files list which constructors is the user's to arrange, for instance with one included file). A constructor is never declared by being met.

THE STORE IS ONE TRIE, used through SWI-Prolog's trie API directly (user, 2026-09-17, after a benchmark of four candidate stores: "use the trie"). Its key is the term itself, constructor included (a trie shares a functor node among all its keys), and its value is the key's own handle, written back with trie_update/3 right after the insertion, because inserting an existing key with a different value raises instead of failing. It lives outside the table space and trie_property(Trie, value_count(Count)) counts it.

A TERM THAT IS NOT INTERNED STAYS AS IT IS (user, 2026-09-26): a plain compound of its constructor, whose arguments are represented in turn. The REPRESENTATION of a term is its Id when a template of its constructor matches it, and the term itself, with represented arguments, otherwise.

THE BOUNDARY: externalized/2 replaces every Id by its term, recursively, for printing, for writing a file and for a content address. internalized/3 declares the templates it is given and represents, bottom up, the instances of their constructors, for a term that did not come through the rewrite (a toplevel query, read_term/2, a module that did not opt in, a term built by =..). declared/1 only declares templates, for a program whose constructors are made at run time. is_id/1 tells an Id from any other value. `represented(?Layer, ?Representation)` relates one layer, a constructor applied to represented arguments, to its representation.

A LAYER POSITION holds a layer, not a representation: in a file that opts in, the term written there keeps its own constructor as a plain term and only its arguments are rewritten. The first argument of represented/2 is one; rewritten/2's option layer_arguments names more, in the heads and goals of the file, for a predicate of a module that does not opt in and hands out or takes the plain layer of a listed constructor (a reader of one layer). A variable there stays a variable.

:- hash_consing:rewritten(Templates). OPTS A FILE IN (user ruling, 2026-09-17: opt-in per file, the constructors passed to the directive, no setting). It declares the templates as declared/1 does, and every clause read after it in that file, included files counted, has each occurrence of a constructor of the list rewritten as below, the direction of each call decided at run time, so the file is written as the program that does not intern and needs no mode declaration. Several directives in one file add up, each declaring whole lists. An empty list rewrites nothing. The library checks no consistency between files: files that pass one constructor to each other must both list it, which the user arranges (user ruling, 2026-09-17). SHARE ONE DIRECTIVE BY include/1: keep the directive in one file that every file handing these terms to another includes; an included directive opts in the file that includes it. A file left out fails silently (the FIXME below).

AN OCCURRENCE IS CLASSIFIED while the file loads, by comparing its source pattern with each template of its constructor: every instance of the pattern matches the template, none does, or some do.

must intern       a template matches every instance: an Id pattern and
                  a call of `intern/2`; the shape is written in when the
                  first template that some instance matches matches them
                  all and each root it records is in the pattern
must not intern   no template matches any instance: the layer itself,
                  written where the occurrence stood
undetermined      otherwise: a fresh variable where the occurrence
                  stood, and a call of `represented/2`

A pattern whose variables are all filled with an atom no template names is taken by a template only when that template has _ or * there, and such a template takes every instance, so no occurrence is missed as must intern. The other two tests treat each occurrence of a variable apart, so a pattern with a repeated variable can be classified undetermined, or left without its shape, although its instances decide it; that is correct and unindexed. An undetermined occurrence at the top of a head costs its clause the first argument indexing of that argument: the clause is a candidate for every call, so a call that a clause before it answers leaves a choice point on it (measured 2026-09-26: with such a clause first in its predicate, calls on an Id, a plain term and the other constructors' Ids were deterministic; with it last, each of them left a choice point). Such a clause is not split into an Id version and a plain version: called with that argument unbound, both would run the body, and a cut in the first would prune the second.

THE REWRITE OF A CLAUSE:

head       fast path when every top-level occurrence is given (the
           handle of an Id pattern bound; the variable of an undetermined
           occurrence bound, and not to an Id pattern whose handle is
           unbound): relate them to their layers top down, then run the
           body, which keeps the last call; otherwise relate the given
           ones top down, represent the ground ones bottom up, run the
           body, represent the rest bottom up (an instantiation error
           when a term that must be interned is still not ground, or an
           undetermined one is still undecided)
body goal  when the variables of its layers are bound: represent bottom
           up and call; otherwise intern the ground ones and decide each
           undetermined one (its Id, an Id pattern whose handle is
           unbound, or the layer itself; an instantiation error when
           still undecided), call, and then settle every occurrence top
           down (a lookup when the call bound the Id, an insertion when
           it made the term ground, an instantiation error when
           neither). An Id occurrence over variables that occur once in
           the clause is unread: its Id pattern alone is passed, and
           after the call only its handle is checked
ground     an occurrence that is ground in the source is represented
           while the file loads, and its Id or its layer is written into
           the clause

Control constructs (`,`, ;, ->, *->, \+, call/1, forall/2, the goal of findall/3 and of catch/3, a module-qualified goal) are rewritten inside. A listed constructor in the template or the result of findall/3, in the catcher of catch/3, or in a DCG rule raises while the file loads. Directives are not rewritten.

TWO RULES FOR A FILE THAT OPTS IN. (1) An instance of a listed constructor whose interning is undetermined is decided when it is handed to a goal: what is bound of it settles whether a template matches every completion or none does, or the call raises an instantiation error; and every instance is settled, ground or its Id bound, by the end of the goal it is handed to. The first half is a DOWNGRADE of the rule before 0.2.0, which asked only for the second: a term that matches no template stays as it is (user, 2026-09-26), and a callee could not otherwise tell whether to receive an Id or a plain term. (2) Reflection sees Ids: =.., functor/3, arg/3, write/1, variant_sha1/2, term_hash/2 and ordering whose result depends on the order see '__hash_consed_Name/Arity'(Handle); the standard order of two Ids depends on the history of insertions into the store, not on their terms. Code that reads structure calls externalized/2 first, and code that builds an instance with them calls internalized/3 after; an instance that must be interned and is left uninterned fails to unify at every rewritten position. Using an Id as an opaque key, whose result does not depend on the order (an assoc key, a sort to remove duplicates), is fine.

THE STORE BELONGS TO THE PROCESS. The store and the spellings of the shapes are two tries made when this module is first loaded and kept in the fact process_stores/2, so every thread and every engine interns into the same store and reads the same Ids, with nothing to install. Reloading the module keeps them. A lookup that finds its key with its handle written back takes no lock; every write to the store, a value still pending settled included, is made under a mutex. The Prolog flag hash_consing_store_limit, infinite by default, bounds the bytes of the store: an insertion that would grow it past the limit raises resource_error(hash_consing_store), the way the stack and table limits do, and the store stays as it was. store_growth_bounded/1 bounds instead what one thread adds to the store from the call on, the way the stack and table limits bound one thread, so a thread that shares the store with others, or finds it already full of what earlier work interned, is charged with its own insertions only. A declaration, an insertion into the store and a new spelling each take a mutex (hash_consing_templates, hash_consing_store, hash_consing_spellings) and look again under it before they write. store_property/1 reads the size of the store.

AN ID IS NEVER FREED NOR REUSED. The store only grows: an Id stays valid, and stands for the same term, until the process ends. Two Ids are == exactly when the terms they stand for are ==, so an Id is a key of its term.

AN INTERNED TERM IS A VALUE, NOT A CELL. intern/2 stores a copy of the term as it is at the call: a later setarg/3 or nb_setarg/3 on the term that was interned, or on a layer read back from an Id, changes that copy only, never the store, and interning the old value again answers the same Id. So a mutable cell (a thunk, a memory cell updated in place) must stay outside the store; interning it freezes its value at that moment. An Id itself must never be mutated: an Id whose handle is set to another Id's handle is that other Id, and one set to any other integer crashes the process (the FIXME below on trie_term/2).

THIS MODULE REFLECTS ON SOURCE CLAUSES with =.. while a file loads, a mechanical boundary; nothing here chooses behaviour at run time by reflection, and no closure is handed to another module.

FIXME: trie_term/2 on an integer that is no node of the store crashes the process with a segmentation fault (measured 2026-09-14 on trie_term(42, _)); a forged '__hash_consed_apply/2'(42) reaches it. Only a bug makes such a value. Candidate fix: none in the trie API; the assertz backends of the benchmark raise instead, at the costs recorded there.

FIXME: an Id written into a clause while the file loads is a handle of this process. A file must be loaded from source, never qcompiled nor saved in a state.

FIXME: a file that uses a constructor another file interns, without listing it, passes its instances uninterned; the rewritten positions of the other file then fail to unify, silently. The library does not check it; one directive shared by include/1 (above) avoids it.