TPK algorithm: Difference between revisions

Revision as of 16:58, 20 September 2021

Latest revision as of 08:24, 1 April 2025

(15 intermediate revisions by 5 users not shown)

Line 1:

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

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.

Line 26 ⟶ 27:

== Implementations ==

=== Implementations in morethe recentoriginal languagespaper ===

In the paper, 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"/>

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

=== Implementations in more recent languages ===

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

<syntaxhighlight lang="Pascal" line>

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

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

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

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

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

InWith thethese papermodifications 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.

Line 79 ⟶ 89:

<syntaxhighlight lang="python" line>

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)

print(i, "TOO LARGE")

else:

print(i, y)

</syntaxhighlight>

Line 96 ⟶ 105:

<syntaxhighlight lang="Rust" line>

use std::io::{selfio, prelude::*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 a.iter_mut().iter::zip(&mut a, io::stdin().lock().lines()) {

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

}

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

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

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

});

}

Line 118 ⟶ 128:

{{reflist|refs=

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