Trabb Pardo-Knuth algorithm

Encyclopedia : T : TR : TRA : Trabb Pardo-Knuth algorithm

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

In their 1980 work "The Early Development of Programming Languages", Trabb Pardo and Knuth introduced a trivial program which involved arrays, indexing, mathematical functions, subroutines, I/O, conditionals and iteration. 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.

Contents

1 The algorithm
2 Perl golf
3 Python version
4 References
5 External link

The algorithm

In ALGOL:

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

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.

Perl golf

The following Perl implementation is 147 bytes. It is shown here on several lines due to page width considerations, but it could be run as a one-liner.

print map$_.$/,reverse map"@$_",
map[$$_[0],$$_[1]>400?'TOO LARGE':$$_[1]],
map[$$_[0],sub->($$_[1])],
map[$_+0,$_=<>],0..10

Python version

The following Python version of the algorithm uses the common Python idiom of using a list instead of an array, (although there is an array module available):

from math import sqrt
def f(t):
return sqrt(abs(t))+5*t**3
a = []
for i in range(11):
a.append(int(raw_input()))
for i in range(10,-1,-1):
y = f(a[i])
if y > 400:
print i, "TOO LARGE"
else:
print i, y

References

"The Early Development of Programming Languages" in A History of Computing in the Twentieth Century, New York, Academic Press, 1980. ISBN 0124916503 (Reprinted in Knuth, Donald E., et al, Selected Papers on Computer Languages, Stanford, CA, CSLI, 2003. ISBN 1575863820)

External link

[Implementations in several modern languages]

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.