Content deleted Content added
Shreevatsa (talk | contribs) move up the ALGOL 60 implementation, as it is from the paper itself (and not OR). It does seem redundant to have so many descriptions of the algorithm, but whatever. Remove comment about overflow. |
|||
| (13 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 25 ⟶ 26:
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:<ref name="edpl"/>
<syntaxhighlight lang="Pascal" line>
Line 40 ⟶ 43:
</syntaxhighlight>
As many of the early high-level languages could not handle the TPK algorithm exactly, they allow the following modifications:<ref name="edpl"/>
▲== Implementations ==
In the paper, which covered "roughly the first decade" of the development of high-level programming languages (from 1945 up to 1957), 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"/>▼
* 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>.
▲
=== Implementations in more recent languages ===
Line 77 ⟶ 89:
<syntaxhighlight lang="python" line>
from math import sqrt
def f(t):
return sqrt(abs(t)) + 5 * t
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
</syntaxhighlight>
Line 94 ⟶ 105:
<syntaxhighlight lang="Rust" line>
use std
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
*t = input.unwrap().parse().unwrap();
}
a.iter().enumerate().rev().for_each(|(i, &t)| match f(t) {
Some(y) => println!("{i} {y}"
});
}
Line 116 ⟶ 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}}
| |||