TPK algorithm: Difference between revisions

Revision as of 08:21, 16 April 2013

Latest revision as of 08:24, 1 April 2025

(129 intermediate revisions by 43 users not shown)

Line 1:

{{Short description|Program to compare computer programming languages}}

{{refimprove|date=November 2011}}

The '''TPK algorithm''' is a simple [[computer program|program]] introduced by [[Donald Knuth]] and [[Luis Trabb Pardo]] to illustrate the evolution of computer [[programming language]]s. In their 1977 work "The Early Development of Programming Languages", Trabb Pardo and Knuth introduced a small program that involved [[Array data structure|arrays]], indexing, mathematical [[Function (mathematics)|function]]s, [[subroutine]]s, [[I/O]], [[conditional (programming)|conditional]]s and [[iteration]]. They then wrote implementations of the algorithm in several early programming languages to show how such concepts were expressed.

{{in-text citations|date=November 2011}}

The '''Trabb Pardo–Knuth algorithm''' is a [[computer program|program]] introduced by [[Donald Knuth]] and [[Luis Trabb Pardo]] to illustrate the evolution of computer [[programming language]]s.

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).<ref name="edpl"/> In a talk based on the paper, Knuth said:<ref name="chm"/>

In their 1977 work "The Early Development of Programming Languages", Trabb Pardo and Knuth introduced a trivial program which involved [[Array data structure|arrays]], indexing, mathematical [[Function (mathematics)|function]]s, [[subroutine]]s, [[I/O]], [[conditional (programming)|conditional]]s and [[iteration]]. They then wrote implementations of the algorithm in several early programming languages to show how such concepts were expressed.

{{quote|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 simpler [[Hello world program]] has been used for much the same purpose.

==The algorithm==

Knuth describes it as follows:<ref>Donald Knuth, ''TPK in INTERCAL'', Chapter 7 of ''Selected Papers on Fun and Games'', 2011 (p. 41)</ref>

<code lang="pseudocode">

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

<math>b_i = \begin{cases}

f(a_i), & \text{if }f(a_i) \le 400; \\

999, & \text{if }f(a_i) > 400; \end{cases} \quad f(x) = \sqrt{|x|} + 5x^3.</math>

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''

Line 17 ⟶ 23:

'''else'''

'''print''' ''result''

</code>

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 ===

{{examplefarm|date=November 2011}}

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:<ref name="edpl"/>

<syntaxhighlight lang="Pascal" line>

===[[ALGOL 60]]===

TPK: begin integer i; real y; real array a[0:10];

<!-- Note that ALGOL is not correctly colored by <source>. -->

real procedure f(t); real t; value t;

<code lang="algol60">

f := sqrt(abs(t)) + 5 × t ↑ 3;

'''begin integer''' i; '''real''' y; '''real array''' a[0:10];

for i := 0 step 1 until 10 do read(a[i]);

'''real procedure''' f(t); '''real''' t; '''value''' t;

for fi := sqrt(abs(t))10 step -1 until +0 5*t^3;do

begin '''for''' iy := 0 '''step''' 1 '''until''' 10 '''do''' readf(a[i]);

if y > 400 then write(i, 'TOO LARGE')

'''for''' i := 10 '''step''' -1 '''until''' 0 '''do'''

'''begin''' y := f else write(a[i], y);

end

'''if''' y > 400 '''then''' write(i, "TOO LARGE")

end TPK.

'''else''' write(i,y);

</syntaxhighlight>

'''end'''

'''end'''

</code>

As many of the early high-level languages could not handle the TPK algorithm exactly, they allow the following modifications:<ref name="edpl"/>

The problem with the usually specified function is that the term <code>5*t^3</code> gives overflows in almost all languages for very large negative values.

* If the language supports only integer variables, then assume that all inputs and outputs are integer-valued, and that <code>sqrt(x)</code> means the largest ''integer'' not exceeding <math>\sqrt{x}</math>.

===[[Bash (Unix shell)|Bash]]===

* If the language does not support alphabetic output, then instead of the string <code>'TOO LARGE'</code>, output the number 999.

The following works with and outputs (rounded-off) integers only:

* If the language does not allow ''any'' input and output, then assume that the 11 input values <math>a_0, a_1, \ldots, a_{10}</math> have been supplied by an external process somehow, and the task is to compute the 22 output values <math>10, f(10), 9, f(9), \ldots, 0, f(0)</math> (with 999 replacing too-large values of <math>f(i)</math>).

<source lang="bash">

f() {

echo "sqrt(${1#-}) + 5 * $1 ^ 3" | bc

}

* If the language does not allow programmers to define their own functions, then replace <code>f(a[i])</code> with an expression equivalent to <math>\sqrt{|a_i|} + 5x^3</math>.

array=()

for i in {0..10}; do

read array[i]

done

With these modifications when necessary, the authors implement this algorithm in [[Konrad Zuse]]'s [[Plankalkül]], in [[Herman Goldstine|Goldstine]] and [[John von Neumann|von Neumann]]'s [[Flowchart|flow diagrams]], in [[Haskell Curry]]'s proposed notation, in [[Short Code (computer language)|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#Glennie's Autocode|Autocode]] of [[Alick Glennie]], in the [[A-0 System|A-2]] system of [[Grace Hopper]], in the [[Laning and Zierler system]], in the earliest proposed [[Fortran]] (1954) of [[John Backus]], in the [[Autocode#Mark 1 Autocode|Autocode]] for [[Manchester Mark 1|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 [[Friedrich L. Bauer|Bauer]] and [[Klaus Samelson|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.<ref name="edpl"/>

for ((i=${#array[@]}-1; i>=0; --i)); do

let x=$(f ${array[$i]})

(( x > 400 )) && echo 'TOO LARGE' || echo $x

done

</source>

=== Implementations in more recent languages ===

Although external programs can be used for unavailable (complex) functions, Bash is inherently incapable of floating-point arithmetic comparison.

====[[C (programming language)|C]] implementation====

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

<syntaxhighlight lang="C" line>

===[[C (programming language) | C]]===

#include <math.h>

<source lang="c">

#include <stdio.h>

#include <math.h>

double f(double t)

#define N 11

{

return sqrt(fabs(t)) + 5 * pow(t, 3);

double vals[N];

double f(double x) {

return sqrt(fabs(x)) + 5*x*x*x;

}

int main(void)
{

double a[11] = {0}, y;

int i;

for (int i = 0; i < 11; i++)

scanf("%lf", &a[i]);

for(i = 0; i < N; ++i)

scanf("%lf", &vals[i]);

for(i = N-1; i >= 0; --i) {

double x = f(vals[i]);

if(x > 400)

printf("TOO LARGE\n");

else

printf("%.3f\n", x);

}

for (int i = 10; i >= 0; i--) {

return 0;

y = f(a[i]);

if (y > 400)

printf("%d TOO LARGE\n", i);

else

printf("%d %.16g\n", i, y);

}

}

</syntaxhighlight>

</source>

====[[GroovyPython (programming language)|GroovyPython]] implementation====

This shows a Python implementation.

<source lang="Groovy">

<syntaxhighlight lang="python" line>

def grooVals = []

from math import sqrt

def scanner = new Scanner(System.in)

11.times {

grooVals << scanner.nextDouble()

}

grooVals = grooVals.reverse()

for (val in grooVals) {

def calcVal = f(val)

if (calcVal.isInfinite())

println 'TOO LARGE'

else

println calcVal

}

</source>

===[[Haskell (programming language)|Haskell]]===

<source lang="haskell">

import Control.Monad

main :: IO ()

main = mapM_ (maybe (putStrLn "TOO LARGE") print.f.read) . reverse =<< replicateM 11 getLine

def f(t):

f :: Double -> Maybe Double

f x = mfilter (<=400) $ Just $return sqrt (abs x(t)) + 5 * t**x^3

</source>

Haskell uses monads for input/output and the Maybe data type to signal overflow.

===[[Java_(programming_language)|Java 5]]===

<source lang="java">

import static java.util.Collections.reverse;

a = [float(input()) for _ in range(11)]

import java.util.LinkedList;

for i, t in reversed(list(enumerate(a))):

import java.util.Scanner;

y = f(t)

print(i, "TOO LARGE" if y > 400 else y)

</syntaxhighlight>

====[[Rust (programming language)|Rust]] implementation====

public class TrabbPardoKnuth {

This shows a Rust implementation.

private static double f(double x) {

return Math.sqrt(Math.abs(x)) + 5 * Math.pow(x, 3);

}

<syntaxhighlight lang="Rust" line>

public static void main(String[] args) {

use std::{io, iter};

LinkedList<Double> numbers = new LinkedList<Double>();

Scanner scanner = new Scanner(System.in);

try {

for (int i = 0; i < 11; ++i) {

numbers.add(scanner.nextDouble());

}

} finally {

scanner.close();

}

assert (numbers.size() == 11) : "input should be eleven numbers";

reverse(numbers);

for (double number : numbers) {

Double fx = f(number);

if (fx.isInfinite()) {

System.out.println("TOO LARGE");

} else {

System.out.println(fx);

}

}

}

}

</source>

fn f(t: f64) -> Option<f64> {

===[[Lua (programming language)|Lua]]===

let y = t.abs().sqrt() + 5.0 * t.powi(3);

A [[Lua (programming language)|Lua]] variant might look like this. [[Lua (programming language)|Lua]] is compiled with [[Double precision]] numbers by default, but any other format is possible.

(y <= 400.0).then_some(y)

<!-- Coloring for Lua seems to be only minimal. -->

<source lang="lua">

function f(x)

return math.abs(x)^0.5 + 5*x^3

end

t = {}

for i=1,11 do

table.insert(t, io.read())

end

for i=#t,1,-1 do

local r = f(t[i])

if r > 400

then print("TOO LARGE")

else print(r)

end

end

</source>

===[[OCaml]]===

The [[OCaml]] version using imperative features such as for loops:

<source lang="ocaml">

let () =

let f x = sqrt x +. 5.0 *. (x ** 3.0) in

let pr v = print_endline (if v > 400.0 then "overflow" else string_of_float v) in

let a = Array.init 11 (fun _ -> read_float ()) in

for i = 10 downto 0 do

pr (f a.(i))

done

</source>

A [[functional programming|functional]] version can also be written in OCaml:

<source lang="ocaml">

let tpk l =

let f x = sqrt x +. 5.0 *. (x ** 3.0) in

let p x = x < 400.0 in

List.filter p (List.rev_map f l)

</source>

===[[Pascal_(programming_language)| Pascal]]===

<source lang="pascal">

program TrabbPardoKnuth(input, output);

const

N = 11;

var

Vals: array[1..N] of real;

I, X: integer;

function F(X: real): real;

begin

F := Sqrt(Abs(X)) + 5 * X * X * X

end;

begin

for I := 1 to N do

ReadLn(Vals[I]);

for I := N downto 1 do

begin

X := F(Vals[I]);

if X > 400 then

WriteLn('Too large!')

else

WriteLn(X)

end

end.

</source>

===[[Perl]]===

A [[Perl]] version using exceptions might look like this:

<source lang="perl">

use feature 'say';

sub f {

sqrt(abs($_[0])) + 5*$_[0]**3

}

forfn main(1..11) {

let mut a = [0f64; 11];

push @inputs, scalar <>

for (t, input) in iter::zip(&mut a, io::stdin().lines()) {

}

*t = input.unwrap().parse().unwrap();

}

a.iter().enumerate().rev().for_each(|(i, &t)| match f(t) {

for (reverse @inputs) {

None => println!("{i} TOO LARGE"),

eval { say f($_) } or say "Problem with entry $_: $@"

Some(y) => println!("{i} {y}"),

});

}

</syntaxhighlight>

</source>

===[[Python (programming language)|Python]]===

<source lang="python">

import math

def f(x):

return math.sqrt(abs(x)) + 5 * x**3

vals = [float(raw_input()) for i in range(11)]

for i, x in enumerate(reversed(vals)):

y = f(x)

print('{0}: {1}'.format(i, y if y <= 400 else 'TOO LARGE'))

</source>

Floating point in Python on most platforms is [[IEEE-754]], which can return "nan" and "inf" values, or raise an appropriate Python exception.

===[[R (programming language)|R]]/[[S-PLUS]]===

In R/S-Plus the user is alerted of an overflow by NaN value. Three of many possible implementations are

<source lang="javascript">

# without an assignment

(function(t) sqrt(abs(t))+5*t^3)(rev(scan(nmax=11)))

# with an assignment

sqrt(abs(S <- rev(scan(nmax=11))))+5*S^3

# as a routine

tpk <- function(S = scan(nmax=11), t=rev(S)) sqrt(abs(t))+5*t^3

</source>

The last implementation makes use of the [[lazy evaluation]] mechanism of R for default values of parameters: <code>t</code> is evaluated only the first time it is used in a computation, after which <code>t</code> is well defined.

===[[Ruby (programming language)|Ruby]]===

The [[Ruby (programming language)|Ruby]] version takes advantage of some of its distinctive features:

<!-- Note that Ruby is not correctly colored by <source>. -->

<source lang="ruby">

def f(x)

Math.sqrt(x.abs) + 5*x ** 3

end

11.times.collect{ gets.to_i }.reverse.each do |x|

y = f(x)

puts "#{x} #{y.infinite? ? 'TOO LARGE' : y}"

end

</source>

===[[Scheme (programming language)|Scheme]]===

The following is tested with [[Chicken Scheme]].

<source lang="scheme">

(define (read-values n)

(if (zero? n)

'()

(cons (string->number (read-line))

(read-values (- n 1)))))

(define (f x)

(+ (sqrt (abs x)) (* 5 x x x)))

(for-each

(lambda (val)

(let ((result (f val)))

(print

(if (> result 400)

"TOO LARGE"

result))))

(reverse (read-values 11)))

</source>

==References==

{{reflist|refs=

* "The Early Development of Programming Languages" in ''A History of Computing in the Twentieth Century'', New York, Academic Press, 1980. ISBN 0-12-491650-3 (Reprinted in Knuth, Donald E., ''et al.'', ''Selected Papers on Computer Languages'', Stanford, CA, CSLI, 2003. ISBN 1-57586-382-0)

<ref name="edpl">Luis Trabb Pardo and Donald E. Knuth, "The Early Development of Programming Languages".

* First published August 1976 in [https://web.archive.org/web/20131102050629/http://www.textfiles.com/bitsavers/pdf/stanford/cs_techReports/STAN-CS-76-562_EarlyDevelPgmgLang_Aug76.pdf typewritten draft form, as Stanford CS Report STAN-CS-76-562]

* Published in ''Encyclopedia of Computer Science and Technology'', Jack Belzer, Albert G. Holzman, and [[Allen Kent]] (eds.), Vol. 6, pp. 419-493. Dekker, New York, 1977.

* Reprinted ({{doi|10.1016/B978-0-12-491650-0.50019-8}}) in ''A History of Computing in the Twentieth Century'', [[N. Metropolis]], [[Jack Howlett|J. Howlett]], and [[G.-C. Rota]] (eds.), New York, Academic Press, 1980. {{ISBN|0-12-491650-3}}

* Reprinted with amendments as Chapter 1 of ''Selected Papers on Computer Languages'', Donald Knuth, Stanford, CA, CSLI, 2003. {{ISBN|1-57586-382-0}})</ref>

<ref name="chm">"A Dozen Precursors of Fortran", lecture by Donald Knuth, 2003-12-03 at the [[Computer History Museum]]: [https://computerhistory.org/events/dozen-precursors-fortran/ Abstract], [https://www.computerhistory.org/collections/catalog/102622137 video]</ref>}}

==External links==

* [https://rosettacode.org/wiki/Trabb_Pardo%E2%80%93Knuth_algorithm Implementations in many languages] at ''[[Rosetta Code]]''

* [http://cs.fit.edu/~ryan/compare Implementations in several languages]

Line 333 ⟶ 141:

{{Donald Knuth navbox}}

{{DEFAULTSORT:Trabb Pardo-Knuth algorithm}}

[[Category:Programming1977 languagein topicscomputing]]

[[Category:Donald Knuth]]

[[Category:Articles with example ALGOL 60 code]]

[[Category:ArticlesTest withitems examplein Rubycomputer codelanguages]]

[[Category:TestComputer itemsprogramming folklore]]

[[Category:Articles with example Python (programming language) code]]