Summary
Addressing started as a simple way for computers to find data in memory. Over thirty years, it grew into a full mathematical theory that explains how to organize and work with arrays (collections of data). The authors show how this process connects programming languages, math for arrays, and computer hardware design. This math lets programmers describe, analyze, and implement data operations more clearly and efficiently.
What this means in practice
- •For programming language designers: Develop clearer, mathematically grounded languages for array and data indexing operations to enhance expressiveness and correctness.
- •For computer architects: Create hardware designs that optimize array data handling by applying theoretical insights on indexing and dimension lifting.
A theory result. No direct application yet.
Abstract
This article argues that a central development in the history of computing is the mathematical evolution of addressing. During the three decades separating Kateryna Yushchenko's Address Programming Language (1958) from Lenore Mullin's A Mathematics of Arrays (1988), addressing evolved from a machine-level mechanism for locating data into a formal theory of indexing, reduction, and machine realization, passing through Kenneth Iverson's algebra of arrays and Philip Abrams' recognition of shape as an architectural resource. Mullin's theory establishes indexing itself, via the function ψ, as the primitive from which array operations compose, reduce to a Denotational Normal Form, transform into an Operational Normal Form, and realize on hardware through dimension lifting. Historical claims are sourced against primary material, with inferences flagged as such; mathematical claims are stated as identities; performance claims are marked validated, theoretically established, or provisional. The result links programming languages, array mathematics, and computer architecture in one account.