miser

oMiser Technical Note m230900b
Hashing Cases

 orcmid.github.io>

miser> oMiser>


m230900b>
0.1.2 2025-09-28T03:48Z

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.

Resources

[Knuth1993b](../../../../../bib/authors.htm#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.