TPK algorithm. 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:

The algorithm
Knuth describes it as follows:

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:

TPK: begin integer i; real y; real array a[0:10];
   real procedure f(t); real t; value t;
      f := sqrt(abs(t)) + 5 × t ↑ 3;
   for i := 0 step 1 until 10 do read(a[i]);
   for i := 10 step -1 until 0 do
   begin y := f(a[i]);
      if y > 400 then write(i, 'TOO LARGE')
                 else write(i, y);
   end
end TPK.

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

 If the language supports only integer variables, then assume that all inputs and outputs are integer-valued, and that sqrt(x) means the largest integer not exceeding .

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

 If the language does not allow any input and output, then assume that the 11 input values  have been supplied by an external process somehow, and the task is to compute the 22 output values  (with 999 replacing too-large values of ).

 If the language does not allow programmers to define their own functions, then replace f(a[i]) with an expression equivalent to .

With these modifications when necessary, the authors implement this algorithm in Konrad Zuse's Plankalkül, in Goldstine and von Neumann's flow diagrams, in Haskell Curry's proposed notation, in Short Code of John Mauchly and others, in the Intermediate Program Language of Arthur Burks, in the notation of Heinz Rutishauser, in the language and compiler by Corrado Böhm in 1951–52, in Autocode of Alick Glennie, in the A-2 system of Grace Hopper, in the Laning and Zierler system, in the earliest proposed Fortran (1954) of John Backus, in the Autocode for Mark 1 by Tony Brooker, in ПП-2 of Andrey 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 of Alan Perlis, in Fortran of John Backus, in ARITH-MATIC and MATH-MATIC from Grace Hopper's lab, in the system of Bauer and Samelson, 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.

Implementations in more recent languages

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

#include <math.h>
#include <stdio.h>

double f(double t)
{
    return sqrt(fabs(t)) + 5 * pow(t, 3);
}

int main(void)
{
    double a[11] = {0}, y;
    for (int i = 0; i < 11; i++)
        scanf("%lf", &a[i]);

    for (int i = 10; i >= 0; i--) {
        y = f(a[i]);
        if (y > 400)
            printf("%d TOO LARGE\n", i);
        else
            printf("%d %.16g\n", i, y);
    }
}

Python implementation
This shows a Python implementation.

from math import sqrt

def f(t):
    return sqrt(abs(t)) + 5 * t**3

a = [float(input()) for _ in range(11)]
for i, t in reversed(list(enumerate(a))):
    y = f(t)
    print(i, "TOO LARGE" if y > 400 else y)

Rust implementation
This shows a Rust implementation.

use std::{io, iter::zip};

fn f(t: f64) -> Option<f64> {
    let y = t.abs().sqrt() + 5.0 * t.powi(3);
    (y <= 400.0).then_some(y)
}

fn main() {
    let mut a = [0f64; 11];
    for (t, input) in zip(&mut a, io::stdin().lines()) {
        *t = input.unwrap().parse().unwrap();
    }

    a.iter().enumerate().rev().for_each(|(i, &t)| match f(t) {
        None => println!("{i} TOO LARGE"),
        Some(y) => println!("{i} {y}"),
    });
}

References

External links
 Implementations in many languages at Rosetta Code
 Implementations in several languages

1977 in computing
Donald Knuth
Articles with example ALGOL 60 code
Test items in computer languages
Computer programming folklore
Articles with example Python (programming language) code