Equal Rights for Functional Objects or, The More Things Change, The More They Are the Same

✨ Summary

Summary

Henry G. Baker argues that object identity should be defined by observable side effects: two objects are distinct when a program can mutate one, or observe mutation, without observing the same effect through the other. This makes mutability—not memory address—the semantic basis of identity.

The paper proposes a single equality predicate, EGAL, intended to replace the collection of partially overlapping predicates found in Common Lisp and Scheme. EGAL compares mutable objects by identity, while it recursively compares immutable objects by their components. Immutable components are treated as part of an object’s identity because they cannot be separated from it through mutation. The resulting relation is intended to remain stable over time, satisfy the properties of an equivalence relation, and avoid distinctions caused solely by representation choices such as pointer versus immediate-value storage.

The approach explains why conventional equality operations create difficulties for numbers, strings, lists, closures, hash-table keys, and property lists. Structural equality is appropriate for immutable structures but can be unstable or non-terminating for mutable or cyclic structures. Conversely, pointer equality is appropriate for mutable objects but is unnecessarily fine for immutable values. The paper therefore treats the traditional EQ/EQUAL distinction as a type-and-mutability problem rather than as a need for many unrelated equality predicates.

Baker extends the model to function closures by comparing their code and essential environments. Mutable captured variables are represented through assignable cells, which preserve distinct identity; closures whose captured environments are immutable can be compared recursively. The paper acknowledges that true behavioral equivalence for functions is undecidable and consequently uses representational equivalence as a computable approximation.

The same identity model is applied to hash tables, streams, copying, lazy values, abstract data types, and type equivalence. In the proposed cell model, immutable structures form the backbone of finite trees, while mutable cells act as the carriers of identity. Recursive types and opaque abstract types are consequently associated with intentional mutability and identity-bearing nodes rather than requiring unrestricted recursive structural comparison.

A major systems implication is that immutable objects can be copied, replicated, moved, and transmitted without synchronization or global localization. This can reduce locking, journaling, communication, forwarding-pointer, and distributed garbage-collection costs in persistent, parallel, distributed, and multilingual systems. The paper consequently advocates mostly functional programming, including immutable lists, strings, arrays, and structures.

For parameter passing, Baker argues for call-by-object-reference as the uniform semantic model. Functional objects may be passed by copying or sharing because the implementation choice is unobservable; mutable objects must preserve identity. This removes the need for ad hoc distinctions between call-by-value and call-by-reference and avoids implicit, timing-dependent coercions of mutable objects into values.

Influence

The paper’s EGAL design has had identifiable influence on later language and library designs. Clojure’s official documentation explicitly identifies Baker’s EGAL as an inspiration for Clojure’s = operation, while also documenting differences involving mutable collections, lazy values, and closures. (clojure.org) A later analysis of equality operators describes EGAL as the model used by Clojure and as a basis for Pyret’s distinction between reference equality, “equals-always,” and value equality. (cs.tufts.edu) The Racket ecosystem also includes rackjure/egal, documented as an implementation of the paper’s mutability-sensitive equality relation. (plt.cs.northwestern.edu) A Common Lisp extension, MW-EQUIV, applies the same basic rule: mutable objects are compared by identity, while frozen objects are compared recursively by their constituents. (quicklisp.org)