The TPK algorithm is a simple program introduced by Donald Knuth and Luis Trabb Pardo to illustrate the evolution of computer programming languages. In their 1977 work "The Early Development of Programming Languages", Trabb Pardo and Knuth introduced a small program that involved arrays, indexing, mathematical functions, subroutines, I/O, conditionals and iteration. They then wrote implementations of the algorithm in several early programming languages to show how such concepts were expressed. To explain the name "TPK", the authors referred to Grimm's law (which concerns the consonants 't', 'p', and 'k'), the sounds in the word "typical", and their own initials (Trabb Pardo and Knuth). In a talk based on the paper, Knuth said:
You can only appreciate how deep the subject is by seeing how good people struggled with it and how the ideas emerged one at a time. In order to study this—Luis I think was the main instigator of this idea—we take one program—one algorithm—and we write it in every language. And that way from one example we can quickly psych out the flavor of that particular language. We call this the TPK program, and well, the fact that it has the initials of Trabb Pardo and Knuth is just a funny coincidence.
The algorithm Knuth describes it as follows:
We introduced a simple procedure called the “TPK algorithm,” and gave the flavor of each language by expressing TPK in each particular style. […] The TPK algorithm inputs eleven numbers a 0 , a 1 , … , a 10 {\displaystyle a_{0},a_{1},\ldots ,a_{10}} ; then it outputs a sequence of eleven pairs ( 10 , b 10 ) , ( 9 , b 9 ) , … , ( 0 , b 0 ) , {\displaystyle (10,b_{10}),(9,b_{9}),\ldots ,(0,b_{0}),} where
b i = { f ( a i ) , if f ( a i ) ≤ 400 ; 999 , if f ( a i ) > 400 ; f ( x ) = | x | + 5 x 3 . {\displaystyle b_{i}={\begin{cases}f(a_{i}),&{\text{if }}f(a_{i})\leq 400;\\999,&{\text{if }}f(a_{i})>400;\end{cases}}\quad f(x)={\sqrt {|x|}}+5x^{3}.}
This simple task is obviously not much of a challenge, in any decent computer language. In pseudocode:
ask for 11 numbers to be read into a sequence S reverse sequence S for each item in sequence S call a function to do an operation if result overflows alert user else print result
The algorithm reads eleven numbers from an input device, stores them in an array, and then processes them in reverse order, applying a user-defined function to each value and reporting either the value of the function or a message to the effect that the value has exceeded some threshold.
Implementations
Implementations in the original paper In the original paper, which covered "roughly the first decade" of the development of high-level programming languages (from 1945 up to 1957), they gave the following example implementation "in a dialect of ALGOL 60", noting that ALGOL 60 was a later development than the languages actually discussed in the paper:
As many of the early high-level languages could not handle the TPK algorithm exactly, they allow the following modifications:
… excerpt ends here. Continue reading the full article.
