TheTPK algorithm is a simpleprogram introduced byDonald Knuth andLuis Trabb Pardo to illustrate the evolution of computerprogramming languages. In their 1977 work "The Early Development of Programming Languages", Trabb Pardo and Knuth introduced a small program that involvedarrays, indexing, mathematicalfunctions,subroutines,I/O,conditionals anditeration. 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 toGrimm's law (which concerns the consonants 't', 'p', and 'k'), the sounds in the word "typical", and their own initials (Trabb Pardo and Knuth).^[1] In a talk based on the paper, Knuth said:^[2]

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.

Knuth describes it as follows:^[3]

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${\displaystyle a_0,a_1,\dots ,a_{10}}$; then it outputs a sequence of eleven pairs${\displaystyle (10,b_{10}),(9,b_9),\dots ,(0,b_0),}$ where

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 sequenceSreverse sequenceSfor eachitemin sequenceScall a function to do an operationifresult overflowsalert userelseprintresult

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.

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 ofALGOL 60", noting that ALGOL 60 was a later development than the languages actually discussed in the paper:^[1]

TPK:beginintegeri;realy;realarraya[0:10];realproceduref(t);realt;valuet;f:=sqrt(abs(t))+5×t↑3;fori:=0step1until10doread(a[i]);fori:=10step-1until0dobeginy:=f(a[i]);ify>400thenwrite(i,'TOO LARGE')elsewrite(i,y);endendTPK.

As many of the early high-level languages could not handle the TPK algorithm exactly, they allow the following modifications:^[1]

• If the language supports only integer variables, then assume that all inputs and outputs are integer-valued, and thatsqrt(x) means the largestinteger not exceeding${\displaystyle \sqrt{x}}$.

• If the language does not support alphabetic output, then instead of the string'TOO LARGE', output the number 999.

• If the language does not allowany input and output, then assume that the 11 input values${\displaystyle a_0,a_1,\dots ,a_{10}}$ have been supplied by an external process somehow, and the task is to compute the 22 output values${\displaystyle 10,f(10),9,f(9),\dots ,0,f(0)}$ (with 999 replacing too-large values of${\displaystyle f(i)}$).

• If the language does not allow programmers to define their own functions, then replacef(a[i]) with an expression equivalent to${\displaystyle \sqrt{|a_i|}+5x^3}$.

With these modifications when necessary, the authors implement this algorithm inKonrad Zuse'sPlankalkül, inGoldstine andvon Neumann'sflow diagrams, inHaskell Curry's proposed notation, inShort Code ofJohn Mauchly and others, in the Intermediate Program Language ofArthur Burks, in the notation ofHeinz Rutishauser, in the language and compiler byCorrado Böhm in 1951–52, inAutocode ofAlick Glennie, in theA-2 system ofGrace Hopper, in theLaning and Zierler system, in the earliest proposedFortran (1954) ofJohn Backus, in theAutocode forMark 1 byTony Brooker, in ПП-2 ofAndrey Ershov, in BACAIC of Mandalay Grems and R. E. Porter, in Kompiler 2 of A. Kenton Elsworth and others, in ADES of E. K. Blum, the Internal Translator ofAlan Perlis, inFortran of John Backus, inARITH-MATIC andMATH-MATIC fromGrace Hopper's lab, in the system ofBauer andSamelson, and (in addenda in 2003 and 2009) PACT I and TRANSCODE. They then describe what kind of arithmetic was available, and provide a subjective rating of these languages on parameters of "implementation", "readability", "control structures", "data structures", "machine independence" and "impact", besides mentioning what each was the first to do.^[1]

This shows a C implementation equivalent to the above ALGOL 60.

#include<math.h>#include<stdio.h>doublef(doublet){returnsqrt(fabs(t))+5*pow(t,3);}intmain(void){doublea[11]={0},y;for(inti=0;i<11;i++)scanf("%lf",&a[i]);for(inti=10;i>=0;i--){y=f(a[i]);if(y>400)printf("%d TOO LARGE\n",i);elseprintf("%d %.16g\n",i,y);}}

This shows a Python implementation.

frommathimportsqrtdeff(t):returnsqrt(abs(t))+5*t**3a=[float(input())for_inrange(11)]fori,tinreversed(list(enumerate(a))):y=f(t)print(i,"TOO LARGE"ify>400elsey)

This shows a Rust implementation.

usestd::{io,iter};fnf(t:f64)->Option<f64>{lety=t.abs().sqrt()+5.0*t.powi(3);(y<=400.0).then_some(y)}fnmain(){letmuta=[0f64;11];for(t,input)initer::zip(&muta,io::stdin().lines()){*t=input.unwrap().parse().unwrap();}a.iter().enumerate().rev().for_each(|(i,&t)|matchf(t){None=>println!("{i} TOO LARGE"),Some(y)=>println!("{i} {y}"),});}

• Implementations in many languages atRosetta Code
• Implementations in several languages

• 1977 in computing
• Donald Knuth
• Test items in computer languages
• Computer programming folklore

• Articles with short description
• Short description matches Wikidata
• Articles with example ALGOL 60 code
• Articles with example Python (programming language) code