TPK algorithm: Difference between revisions

Revision as of 04:39, 26 June 2007

Latest revision as of 08:24, 1 April 2025

(265 intermediate revisions by more than 100 users not shown)

Line 1:

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

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.

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.

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 1980 work "The Early Development of Programming Languages", Trabb Pardo and Knuth introduced a trivial program which involved [[array]]s, [[index (information technology)|indexing]], mathematical [[Function (mathematics)|function]]s, [[subroutine]]s, [[I/O]], [[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>

ask for 11 numbers into set S

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

reverse set S

<math>b_i = \begin{cases}

for each item in set S

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

do an operation

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

if result overflows

This simple task is obviously not much of a challenge, in any decent computer language.}}

alert user

else

print result

In pseudocode:

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.

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

==Versions==

== Implementations ==

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

=== Implementations in the original paper ===

<code> <!-- You use <source>, not <code>, if you use the lang attribute. Even so, ALGOL is not supported by <source>. -->

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"/>

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

</code>

<syntaxhighlight lang="Pascal" line>

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

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.

</syntaxhighlight>

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

===[[Perl golf]]===

The following [[Perl]] implementation is 79 [[byte]]s.

* 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>.

<source lang="perl">

map print(($_>400?"TOO LARGE":$_).$/),reverse map 5*($x=<>)**3+sqrt abs$x,1..11

</source>

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

===Python version===

The following Python version of the algorithm uses the common Python idiom of using a list instead of an array:

* 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="python">

* 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>.

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"/>

=== Implementations in more recent languages ===

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

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

<syntaxhighlight lang="C" line>

#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);

}

}

</syntaxhighlight>

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

This shows a Python implementation.

<syntaxhighlight lang="python" line>

from math import sqrt

def f(t):

return sqrt(abs(t)) + 5 * t**3

a = [int(raw_input()) for i in range(11)]

for i in range(10,-1,-1):

y = f(a[i])

if y > 400:

print i, "TOO LARGE"

else:

print i, y

</source>

===Ruby version===

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

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

<source lang="ruby">

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

Array.new(11) { gets.to_i }.reverse.each do |x|

y = f(t)

begin

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

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

</syntaxhighlight>

raise if y > 400

puts "#{x} #{y}"

rescue

puts "#{x} TOO LARGE"

end

end

</source>

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

Ruby handles extremely large values very easily, even on 64-bit systems, so the possibility of an overflow in the above program would be slim.

This shows a Rust implementation.

<syntaxhighlight lang="Rust" line>

use std::{io, iter};

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 iter::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}"),

});

}

</syntaxhighlight>

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

* [httphttps://csrosettacode.fit.eduorg/~ryanwiki/compareTrabb_Pardo%E2%80%93Knuth_algorithm Implementations in several modernmany languages] at ''[[Rosetta Code]]''

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

{{Standard test item}}

{{Donald Knuth navbox}}

{{DEFAULTSORT:Trabb Pardo-Knuth algorithm}}

[[Category:Algorithms]]

[[Category:1977 in computing]]

[[Category:Donald Knuth]]

[[Category:Articles with example Python code]]

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

[[Category:ArticlesTest withitems examplein Perlcomputer codelanguages]]

[[Category:Computer programming folklore]]

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