CS Paper Radar

The Mathematical Evolution of Addressing: From Yushchenko's Address Programming Language to A Mathematics of Arrays How Addressing Evolved into a Mathematical Theory of Indexing, Array Computation, and Machine Realization

Lenore Mullin, Gaetan Hains

cs.GL cs.PL ·submitted 2026-09-20 20:15 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Expressing NumPy Broadcasting via Verb Rank in J

cs.PL cs.MS ·2026-09-13 ·Marcin Żołek
similarity 0.57
Abstract

The array programming paradigm applies operations to entire arrays rather than individual elements, eliminating explicit loops and abstracting many low-level details of computation. Two influential approaches have shaped array programming: NumPy's broadcasting and Kenneth Iverson's array-oriented notation, with the latter first introduced in APL and later developed in the J language. Although NumPy's array programming model was influenced by Iverson's work, the two systems formalize array operations differently: NumPy primarily through array shapes and broadcasting, and J through verb rank. This paper establishes a formal correspondence between NumPy broadcasting and J rank and presents an implementation of NumPy broadcasting in J. The results provide a formal connection between two influential approaches to array-oriented computation and show how they address the common problem of applying operations to arrays with differing shapes without explicit loops.

0.28

Executable Archaeology: Reanimating the Logic Theorist

cs.AI cs.LOcs.PLcs.SC ·2026-11-14 ·David Moews, Jeff Shrager
similarity 0.52
Abstract · This paper builds upon a previous ArXiv paper of a similar name: https://arxiv.org/pdf/2603.13514. This paper is NOT a mere rehash of the pr…

The Logic Theorist (LT), created by Allen Newell, J. C. Shaw, and Herbert Simon in 1955--1956, is regarded by some as the first artificial intelligence program. It was originally simulated by hand and written in a pseudocode called the Logic Language (LL), which was later called Information Processing Language One (IPL-I). LT was revised many times. The first machine-executed version was written in IPL-II and ran on the JOHNNIAC, and a late version was published in 1963 by Einar Stefferud as a pedagogical document and written in IPL-V, the only version of IPL that was formally released to the public. We describe a reanimation of both the IPL-I (LL) version of LT and the 1963 IPL-V version. Comparing the two reanimations illuminates the process of the invention of early AI algorithms and computer languages.

0.25

Grassmann: The Coordinate-Independent Linear Algebra Programming Language

cs.PL cs.MS ·2026-10-30 ·Theadora Fields Collin, Gilbert Bernstein, Oded Stein, Saman Amarasinghe
similarity 0.51
Abstract · 147 pages, including references and appendices

Scientists, engineers, and mathematicians often formulate algorithms using coordinate-independent linear algebra because its tools are composable and harder to misuse. For numerical processing, however, users must translate these ideas into coordinate-dependent array code. Most practitioners do so prematurely because tools such as NumPy lack coordinate-independent representations, while existing languages with such constructs do not model enough linear algebra for the situations where they matter. We propose Grassmann, a small language bridging coordinate-independent linear algebra and coordinate-dependent implementations. It uses dependent types, linear types, and partially (pseudo-)invertible computation to model situations arising in exterior algebra and differential geometry. It targets the linear algebra at a point on a manifold, a prerequisite for many specifications in scientific computing and computer graphics. A language for coordinates lets users move between these representations. We give a denotational semantics assigning meaning without coordinates and an operational semantics translating Grassmann to array code under a choice of coordinates. Our main metatheoretic result shows that operational evaluations agree with the denotational semantics under an arbitrary choice of coordinates. This models how practitioners translate linear algebra for computers and suggests an approach to algorithmic optimization at a high level of abstraction. Our optimized implementation generates code for exterior algebra operations with overheads no more than 10%.

0.25

A Simplified Layout Algebra for GPU Kernels

cs.PL ·2026-10-09 ·Nan An, Xiaotian Zhou
similarity 0.50
Abstract

The layout algebra behind NVIDIA's CuTe library describes how tensor tiles map onto threads and memory. A layout is a shape with a stride for each entry, so a coordinate's address is the sum of its indices times their strides. As formalized by Shah and by Cecka, its central operations (e.g., composition, complement, division, product) are guarded by at least six interacting admissibility conditions. We show that this complexity is an artifact of a representational choice, not of the domain. We present a layout algebra in which every layout names the space its inputs and outputs live in: logical, physical, or thread-value indices. A layout into logical or thread-value space must be a bijection from its $N$ coordinates onto $[0,N)$. A layout into physical space must be alias-free: distinct coordinates land on distinct addresses, except under broadcast, where many threads read one value on purpose and the layout must mark where. Nothing maps out of a physical index. Composing $f$ with $g$ requires only that $f$'s range be exactly $g$'s flattened coordinate set. The index arithmetic can always be emitted naively: compute $f$, split the result by division and remainder into $g$'s coordinates, and apply $g$. Often the composite simplifies to a layout; we show that when it does, there is a coarsest such form, whose digits every other one refines, and we emit that. A warp's or thread's slice is a \emph{restriction}. A restricted layout is no longer composable, which forces the user to settle the whole view of a tile before taking slices. We validate the algebra by reproducing within it CuTe's operations, such as composition, complement, and division. We implement it in OCaml and use the implementation to rederive CuTe's atoms and usage patterns. The decision procedure is proved correct in Rocq.

0.19

Michael Rabin's fingerprints across the theory of computation

cs.GL math.HO ·2026-10-19 ·Avi Wigderson
publishedunusual similarity 0.49
Abstract · 63 pages

Michael O. Rabin was a major founder and leader of theoretical computer science. He died on April 14, 2026, at the age of 94. This paper aims to survey the wide scope and lasting impact of his research.

0.40

Executable Archaeology of Programs That Model Programming: Reanimating the Heuristic Compiler (1961) and KBEmacs (1984)

cs.AI cs.HCcs.PL ·2026-10-26 ·Jeff Shrager, Kent M. Pitman, Mia Golec
similarity 0.47
Abstract

Early AI programs were often also theories of how people think, and programs that wrote programs were, in part, theories of how people program. Here we report on the reanimation of two such programs that offer two seemingly different theories of programming and were developed for quite different purposes. The first, Herbert Simon's Heuristic Compiler (1961), was an experimental model of programming as problem-solving, applying the means-ends analysis methods of the General Problem Solver to investigate the nature of the programming task. The second, KBEmacs (1984), was a working prototype of an intelligent programming assistant developed by MIT's Programmer's Apprentice project, built on the view that expert programmers recognize and combine familiar patterns, or "cliches." It let a programmer build up programs by combining cliches through a stylized English command language. We approach both through the methodology of Executable Archaeology, the study of historical computational systems by running their original code, a process we call "reanimation." Our reanimation of the Heuristic Compiler reproduces the compiled code appearing in Simon's 1963 paper, and our reanimation of KBEmacs reproduces the SQRT sequence of its December 1984 self-test. Examined side by side, the two theories turn out to have much in common: the Heuristic Compiler also works by adapting existing routines, and Simon later argued that search alone requires a large body of programming knowledge. To highlight the reflexivity of this project, we deliberately used a modern AI-assisted programming tool, Anthropic's Claude Code (Opus 5.5), to carry out much of the detailed reanimation work, building on a significant base of existing software. The explicit, executable theories of programming that both systems embodied are largely absent from today's far more capable AI coding assistants.

0.26

From Maps to Metabolism: Historical Precedents and a Unified Critique of Computationalism

cs.AI q-bio.NC ·2026-10-23 ·J. Mark Bishop, Slawomir J. Nasuto
similarity 0.47
Abstract

Alexander Lerchner's recent work on the 'abstraction fallacy' argues that computational functionalism confuses physical processes with abstract descriptions, and that symbolic computation alone cannot instantiate consciousness. Yet these claims were anticipated by Korzybski's map-territory distinction, Searle's critique of strong artificial intelligence, Floridi's levels of abstraction, Spencer et al.'s observer-relativity arguments, Winograd and Flores's account of computation as socially grounded practice, and Nasuto and Bishop's biological arguments. Synthesizing these contributions, this paper advances a form of non-computational physicalism: consciousness depends upon intrinsically organized, metabolically grounded physical dynamics rather than abstract computation, whilst leaving open the possibility of artificial consciousness. An objection is that this critique targets an outdated computationalism. Mechanistic computationalism, associated with Milkowski, Piccinini, Craver, Bechtel, and Kaplan, treats computation as a property of physically realized mechanisms rather than substrate-independent formalism. Although this represents an important advance, it does not dissolve the abstraction fallacy. Computational attributions remain dependent upon choices of state individuation, system boundaries, and interpretive mapping that are not determined by physical facts alone. Kaplan and Craver's 'model-to-mechanism mapping' constrains computational descriptions without eliminating their dependence upon an external observer. Grounding computation in neural mechanisms does not confer intrinsic significance or the normativity explored by Bickhard and Nasuto and Bishop. The abstraction fallacy persists wherever computational descriptions are treated as constitutive of, rather than descriptive of, physical reality.

0.24

RPyForth: Exposing a Call-Shared Data Stack to a Meta-Tracing JIT Compiler

cs.PL ·2026-09-20 ·Yusuke Izawa, Kota Hakamada
similarity 0.47
Abstract · 33 pages, 15 figures

Forth is a concatenative language whose words share one data stack across calls, with a depth and call effects that need not be known before execution. That leaves a meta-tracing JIT compiler with no stack location it can name: a cell is reached through the stack pointer, so its accesses stay in the compiled code, and declaring every cell of the stack array instead ties what the compiler carries to the capacity the array reserves rather than to the depth a program uses. We answer with a fixed-width window over the top of the stack, a shared spill holding every deeper cell, and a decoding function that joins the two, on top of which call-entry normalization and adaptive entry are policies. Decoding shows that all of them preserve the logical stack and that a trace exit rebuilds data-stack state bounded by the window's width, not by the stack's depth. RPyForth realizes this in an RPython interpreter covering Forth's Core word set, with two scalar fields and eight frame positions and no static stack-effect analysis, and RPyFactor realizes the same window for a subset of Factor. Exposing the window to the compiler, rather than merely caching cells in it, is what pays. With the layout and the call policy held fixed, annotating the window's fields makes eighteen Shootout kernels 1.44-1.45x faster and six Appbench applications about 1.60x faster on two x86-64 machines, and 1.42-1.56x in RPyFactor. How the window is shaped and whether calls normalize it matter much less, varying by program with no setting winning everywhere. As a complete system, RPyForth is faster than gforth-fast and SwiftForth on both suites and reaches 1.90-2.36x the speed of VFX Forth on the kernels, while the applications, whose stacks are deeper and whose calls are far more frequent, remain its weak point at 0.68-0.76x. All timings measure repeated execution of an already-loaded program.

0.30