- Trabb Pardo-Knuth algorithm
The Trabb Pardo-Knuth algorithm is a program introduced by
Donald Knuth andLuis Trabb Pardo to illustrate the evolution of computerprogramming language s.In their 1977 work "The Early Development of Programming Languages", Trabb Pardo and Knuth introduced a trivial program which involved
array s, indexing, mathematical functions,subroutine s,I/O ,conditional s anditeration . They then wrote implementations of the algorithm in several early programming languages to show how such concepts were expressed.The simpler
Hello world program has been used for much the same purpose.The algorithm
ask for 11 numbers into sequence S reverse sequence S for each item in sequence S 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.
Implementations
ALGOL 60 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
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.Ruby version
The Ruby version takes advantage of some of its features:
Ruby handles numerical overflow by returning
Infinity
, which is greater than 400.Ocaml version
The Ocaml version using imperative features such as for loops:
A functional version can also be written in Ocaml:
References
* "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)
External links
* [http://cs.fit.edu/~ryan/compare Implementations in several modern languages]
Wikimedia Foundation. 2010.