Behind every interesting programming language is an interesting model of computation. One such example is the model of rank polymorphism, developed by Iverson for the programming languages APL and J, and for which he was awarded the Turing Award in 1979.
The rank-polymorphic computational model is interesting for several reasons:
It is fundamentally a model where every value is an array.
Control structure, or iteration space, is reified by the shape of the arrays on which functions operate.
It is inherently parallel.
It constitutes an answer to Backus’ “von Neumann bottleneck.” Well-written programs in this model do not fetch scalars from arrays. No loops; no indexing. Instead, programs operate upon entire data aggregates at a time.
It famously permits programs to be written very succinctly.
In this talk, I will provide an introduction to the general idea of rank polymorphism, introducing the key mechanisms of (1) frame/cell distribution, (2) principal-frame replication, and (3) reranking (a form of typed eta-expansion). Then we will explore how these mechanisms work together when writing programs in a rank-polymorphic language.
Time permitting, at the end of the talk, I’ll briefly discuss recent work Justin Slepak, Panagiotis Manolios and I have been doing on developing a dependent type system that statically captures the structure of rank-polymorphic programs, for exploitation by compilers.
APL, the canonical example of a rank-polymorphic language, is also famous for its impenetrable syntax… none of which will appear in this talk.