miser

oMiser Technical Note m230900b
Hashing Cases

 orcmid.github.io>

miser> oMiser>


m230900b>
0.1.4 2026-01-25T23:11Z

Cases

There are 4 flavors of HashFlag creation:

  〈individual-name〉 ::= 〈plane-lindy〉 | ?〈plane-lindy〉
                    |  〈primitive〉   | ?〈primitive〉

  1. Individuals: The Hash for ordinary individuals is based on the name of the individual in oFrugal syntax [ob-exp:TERMS]. All but 〈primitive〉 are classified as symbolic-forms. The ?-prefixed forms are distinct are provided to allow an application (namely oFrugal) to continue despite certain defects in the script (cf. [obaptheory: Obap3)]).

  2. Pairs: The Hash of of a pair is a function of the HashFlags of the two components.

  3. Enclosures: The Hash of an enclosure is a function of the HashFlag of the constituent.

  4. Synthetics: The Hash of a synthetic individual is a function of the HashFlag of the ob-cell providing the definition of the synthetic as established in obapx.

Critical Invariance

In the case of individuals, including extension to synthetics, the uniqueness of individuals has to be preserved and duplication must be prevented. Any collision of Hashtags for individuals must be resolved simply by the ob-cell locations being different.

It is unnecessary to inspect anything about the creation of an individual to rely on its uniqueness.

External Identifiability

Every ob has a canonical Form (CFob). To report the CFob of an ob, the structure is presented in a formula for nested pairings and enclosures. Named individuals are identified by their namings.

In the oMiser implementation, ob-cells corresponding to named individuals are proximate to strings of their unique individual names. The cells can be accessed by searching on their names. Given the ob-cell of a particular individual, its unique name can be retrieved directly. The API functions for those actions are the means by which oFrugal, and any other applications, can establish individuals and also determine the names associated with given individuals.

Given this condition on ob-cells, it is important that any hash-table changes that occur in connection with insertions and (potentially) deletion of hash table entries never move an ob-cell which is still accessible by its address from any other reachable ob-cell.

The situation with synthetic individuals is similar except that a Synthetic has a distinct ob as its applicative interpretation and, in effect, as its name. Synthetics must also not be duplicated. That means subjecting them to hash-table lookups as well. In this case, the Hash from the synthetic’s HashTag should be useful. Extended canonical forms (CFobx) carry provisions for the text presentation of Synthetics as such individuals are introduced.

In the interesting case that there is already such a Synthetic as one being introduced, with the identical applicative interpretation, the already-established one shall prevail, just as for the introduction of any other named individual.

Finally, ob-cells for obs that have external identifiability are never released as long as the oMiser instance persists. Because there is such identifiability, including re-creation of a Synthetic, the condition essentially holds for all individuals, no matter their origin or current accessibility.

It appears that it must be possible to find individuals by their HashFlags, because the resolution of their definition requires it. In effect, it is for access to the definition of the individual, whether by its synthesis or its literal identifier. In both cases, the hash of a prospective first-occurrence is used to access existing definitions and determine if there already is one.

In all of these case, and only these, is the MOb required. The one difference is that Synthetics have no individual name.

There is a lingering case with respect to bindings. Bindings are naturally externally-identifiable (and generally only so associated) and they do not resolve to individuals, as such. It is undesirable to determine that an ob might be the the object of a binding by searching for it in the MOb. On the other hand, it would be handy to know that about an ob-cell. To address that temptation, one must reconcile the fact that an ob-cell can be the object of more than one binding, and that a binding can be removed or re-assigned in the course of operation. The pay-off would be the ability to abbreviate displayed obs by identifying (current) bindings. This may simply be far-fetched.

Resources

[Knuth1993b] Knuth, Donald E. The Stanford GraphBase: A Platform for Combinatorial Computing. Addison-Wesley (Boston: 1963). ISBN 978-0-321-60632-7 pbk.

[Knuth1998] Knuth, Donald E. Chapter 3, Random Numbers, in The Art of Computer Programming, vol.2: Seminumerical Algorithms, ed.3. Addison-Wesley (Reading, MA: 1998). ISBN 0-201-89684-2

[Knuth1998b] Knuth, Donald E. Section 6.4, Hashing, in The Art of Computer Programing, vol. 3: Sorting and Searching, ed.2. Addison-Wesley (Reading, MA), 1998. ISBN 0-201-89685-0.

I invite discussion about Miser Project topics in the Discussion section. Improvements and removal of defects in this particular documentation can be reported and addressed in the Issues section. There are also relevant projects from time to time.

Hard Hat Area You are navigating the Miser Project on Github

created 2025-09-24 by orcmid

This site is open source. Improve this page.