An association-based model of dynamic behaviour

ByIan Piumarta

DOI 10.1145/2068776.2068779

Denotational & semantic program design Denotational & semantic program design Delegation mechanism Associative memory model [ ] associative read operator Dynamic dispatch [ ] associative write operator "Expressing delegation as a pair of β-transformations on keys in an associative memory emphasises a fundamental symmetry of the delegation mechanism that is ignored by most object-oriented programming languages."Hash tables Multi-dimensional delegation space n-way Associative Lookup Relational languages

TL;DR

N-way associative lookup — a single primitive operation m[k₁,...,kₙ] = v with corresponding read and write operators — suffices to derive flat physical memory, dictionaries, delegation-based prototype inheritance, class-based inheritance with the σ/τ key pair, multiple dispatch, and context-oriented programming as special parameterisations of the same underlying mechanism. By setting n=2 with α₁(k)=m[k,τ] and β₁(k)=m[k,σ], the model recovers exactly the dynamic binding mechanism of a Smalltalk-80-style class hierarchy. Each additional key dimension adds an orthogonal taxonomic axis, making object-oriented, subject-oriented, and context-oriented programming (and Worlds, TR-2010-001) distinguishable only by the number and arrangement of axes, not by fundamentally distinct mechanisms. The paper introduces the association-based model of dynamic behaviour (ABMDB), formalised as the primitive memory map m: K[*]→V with pre-transformations αᵢ and post-transformations βᵢ on keys; experiments with an in-memory SQLite database show the relational engine delivers dynamic binding operations several orders of magnitude slower than a dedicated runtime, ruling out that substrate for practical use. The paper argues this implies that diverse and apparently incompatible dynamic mechanisms are in fact symmetry-breaking specialisations of one parameterisable space, and that an efficient software or hardware implementation of the n-way associative primitive — scaling to billions of entries — would unify their implementation while also exposing genuinely new mechanism combinations not yet invented.

What to take away

1. A single primitive n-way associative lookup m[k₁,...,kₙ]=v, with read operator '[]' and write operator '[]←', is sufficient to derive physical memory (n=1), dictionaries/arrays (n=2), prototype delegation, class-based inheritance, multiple dispatch, and context-oriented programming as special cases.
2. Class-based inheritance with dynamic method lookup, as in Smalltalk-80, is completely characterised by three lines: n=2, α₁(k)=m[k,τ] (type pointer), and β₁(k)=m[k,σ] (supertype pointer), where τ and σ are two distinguished well-known keys.
3. An in-memory SQLite database — the fastest freely available in-memory relational engine — performs dynamic binding operations several orders of magnitude slower than a dedicated language runtime implementation, disqualifying relational databases as a practical substrate for the primitive.
4. Object-oriented, subject-oriented, and context-oriented programming, as well as Worlds (VPRI TR-2010-001), are distinguishable solely by the number of key-dimension axes used in lookup, not by qualitatively different mechanisms.
5. The β-transformation symmetry reveals that type-centric inheritance (delegating along the object k₁ axis) and selector-centric inheritance (delegating along the slot-name k₂ axis) are mirror images within the same two-dimensional associative space, a symmetry ignored by most OO languages.
6. Worst-case computational complexity of application-level models grows at most exponentially with n (the number of key dimensions), making the choice of n a critical design parameter for any hardware or software realisation.
7. Garbage collection is identified as the primary unsolved engineering challenge: when key kᵢ becomes unreachable in an n-way association, all entries for which any kᵢ=k must be deleted, a problem that becomes substantially harder as n grows beyond 2.
8. To replicate the delegation mechanism, a researcher can implement r(k₁,k₂) recursively as m[k₁,k₂] when non-ε, and r(m[k₁,σ],k₂) otherwise, using any hash-table or in-memory store for m, with σ as a globally interned sentinel key.
9. The paper raises the open question of whether the association primitive could support a relational-language semantics by allowing the unified variable to appear in any key position (not just the value position), with 'future unification' as a candidate mechanism for publish-subscribe, though it acknowledges the philosophical and practical costs are substantial.
10. The paper predicts that an efficient software implementation of the n-way associative primitive capable of scaling to billions of entries would constitute a substantial doctoral research contribution, with the hard problems residing in storage management rather than in the primitive operators themselves.

Peer brief — for seminar discussion

Ian Piumarta's VPRI Technical Report TR-2011-003, presented at the FREECO'11 workshop at ECOOP 2011 (Lancaster, UK, July 26, 2011) and supported by NSF Grant No. 0639876, proposes that a single primitive operation — n-way associative lookup on a memory map m: K[*]→V — is the common substrate from which flat physical memory, arrays, prototype delegation, class-based inheritance, multimethod dispatch, and context-oriented programming all emerge as special parameterisations. The method introduced is the association-based model of dynamic behaviour (ABMDB), formalised through two primitive operators (associative read '[]' and associative write '[]←') and two families of key-transformation functions: pre-lookup α-transformations and post-lookup β-transformations. The load-bearing finding is that Smalltalk-80-style dynamic binding collapses to exactly three specification lines (n=2, α₁(k)=m[k,τ], β₁(k)=m[k,σ]), and that object-oriented, subject-oriented, context-oriented programming (as defined by Hirschfeld et al. 2008 in JOT Vol. 7 No. 3), and Worlds (TR-2010-001) are distinguishable only by the count and arrangement of key-dimension axes. A critical empirical data point is that an in-memory SQLite database — stated to be the fastest freely available in-memory relational engine — delivers dynamic binding latencies several orders of magnitude above what a dedicated runtime achieves, ruling out Codd-style relational databases (1970, CACM Vol. 13 No. 6) as a practical implementation substrate. An alternative method the paper could have used to benchmark this claim is a custom hash-table implementation at n=2, which would establish a software performance floor without the overhead of SQL parsing and query planning. The paper's central hypothesis is that all known and as-yet-uninvented dynamic mechanisms are merely points within a dimensionally unbounded, self-similar associative space, and that recognising this should guide both language design and hardware architecture. The most contestable aspect is the empirical thinness of the performance claim: SQLite is used as a proxy for 'relational databases in general', but SQLite's query planner is not optimised for the repeated single-row keyed lookups the benchmark requires, making the several-orders-of-magnitude penalty an artefact of that mismatch rather than a principled result about the relational model's inherent suitability. A critical reader would also push back on the scope claim that 'maybe even all' useful information and behaviour organisations reduce to the primitive, since the paper explicitly defers arithmetic, logical operations, and general sequencing mechanisms, which are non-trivial omissions for a universality claim. The garbage-collection challenge for n>2, where unreachability of any single key kᵢ must trigger deletion of all associated tuples, is flagged as an open research problem whose difficulty scales with n and for which no solution is offered.

Methods (3)

[ ] associative read operator
Primitive operator that retrieves the value associated with keys k_i in memory m.
[ ] associative write operator
Primitive operator that updates memory m with a new value v for keys k_i.
Hash tables