hash_consing: hash-consed terms whose Ids record a configurable 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 files declare.

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

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

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

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

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(_), 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_rewrite.sh prints what the rewrite makes of its fixtures, `test/hash_consing_fixtures/`, and is 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 rewritten subterms are Ids 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; 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 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_a(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 constructor'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). The heads above become step('__hash_consed_apply/2'('lambda/1', Handle)) and step('__hash_consed_apply/2'('closure_a/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 the template, so the Handle determines it and the store stays canonical.

THE CONFIGURATION IS A TEMPLATE, one syntax for every constructor (user, 2026-09-20: one syntax, not three; the template names the constructor, so no indicator beside it; a depth of zero is another feature and is not offered). An element of the directive's list is the constructor applied to one of these at each argument position (a constructor of arity zero is its atom):

_                  nothing is recorded about the argument
*                  the root constructor of the argument is recorded
a nested template  the root constructor is recorded and, when it is the
                   template's constructor, the template goes on below
                   it; alternatives are joined by `;`

lambda(_) records the root only and its Ids are '__hash_consed_lambda/1'(Handle). apply(*, _) gives apply(lambda(B), X) the shape 'lambda/1'; with apply(apply(*, _), _), apply(apply(lambda(B), Y), X) has the shape 'apply/2(lambda/1)' and apply(lambda(B), X) still 'lambda/1'. An argument that is no Id is written -. The reading has a precedent in SWI-Prolog's mode-directed tabling, :- table path(_, _, min).

THE SHAPE IS A FUNCTION OF THE TERM AND OF ITS OWN TEMPLATE, and of nothing else: at a * the root is read off the functor name of the argument's Id, with no lookup; each nested template costs an upsert one trie_term/2 on the argument's 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.

AT COMPILE TIME a pattern that determines everything its template records gets the atom written into the head; a pattern that determines only part of it gets an unbound shape, which is correct (the constructors of the pattern are still checked by the lookups of the body) and unindexed. A nested template reads the argument's own arguments off the occurrence of that argument in the same clause, or off the store when its Id was baked. A partial pattern is NOT expanded into one clause per completion: a file loaded later brings new shapes, which the expanded clauses would silently miss. So the deeper a template, the fewer patterns determine it.

ONE CONFIGURATION PER CONSTRUCTOR, PER PROCESS: a second declaration of a constructor with another template raises while the file loads, because two shapes of one term would not be == (agent design decision, 2026-09-20, not objected to by the user; 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).

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.

externalized/2 AND internalized/3 ARE THE BOUNDARY: the first replaces every Id by its term, recursively, for printing, for writing a file and for a content address; the second interns, bottom up, the instances of the constructors whose templates it is given, 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 =..).

:- 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). Every clause read after it in that file, included files counted, has each occurrence of a listed constructor turned into an Id pattern and a call of intern/2, 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. 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, for instance with one included file (user ruling, 2026-09-17).

THE REWRITE OF A CLAUSE:

head       fast path when the Handle of every top-level head occurrence
           is bound: look them up top down, then run the body, which
           keeps the last call; otherwise look up the bound ones top
           down, insert the ground ones bottom up, run the body, insert
           the rest bottom up (an instantiation error when a term is
           still not ground)
body goal  when the variables of its terms are bound: insert bottom up
           and call; otherwise insert the ground ones, 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)
ground     an occurrence that is ground in the source is interned while
           the file loads and its Id 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 is settled, ground or its Id bound, by the end of the goal it is handed to; a term handed over half built and filled in later raises an instantiation error. (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). Code that reads structure calls externalized/2 first, and code that builds an instance with them calls internalized/3 after; an instance 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.

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: on 2026-09-14, within tabled compiles near a full stack, trie_lookup/3 failed silently on a key of the store and left the resource error pending. Here such a failure turns an upsert into an insertion of an existing key, which raises, or a lookup into a failure, which reads as no answer rather than resource_error. A direct probe at 1m, 4m and 32m stacks on 2026-09-17 raised resource_error(stack) every time and did not reproduce it.

FIXME: the order of two Ids depends on the insertion history. Nothing checks that no code in an opted-in file reads that order; it is a rule of the file, stated above.

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, and the store lives in one thread's global variable.

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 cannot see it.