TPK algorithm

From Wikipedia for FEVERv2
Revision as of 05:12, 7 January 2021 by imported>Unknown user
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

The TPK algorithm is a program introduced by Donald Knuth and Luis Trabb Pardo to illustrate the evolution of computer programming languages. TPK algorithm_sentence_0

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

They then wrote implementations of the algorithm in several early programming languages to show how such concepts were expressed. TPK algorithm_sentence_2

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). TPK algorithm_sentence_3

In a talk based on the paper, Knuth said: TPK algorithm_sentence_4

In the paper, 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. TPK algorithm_sentence_5

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

The algorithm TPK algorithm_section_0

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

ALGOL 60 implementation TPK algorithm_section_1

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 algorithm_sentence_8

C implementation TPK algorithm_section_2

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

Python implementation TPK algorithm_section_3

This shows a Python implementation. TPK algorithm_sentence_10

Rust implementation TPK algorithm_section_4

This shows a Rust implementation. TPK algorithm_sentence_11


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/TPK algorithm.