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

The algorithm

``````ask for 11 numbers to be read into a sequence S
reverse sequence S
for each item in sequence S
call a function to do an operation
if result overflows
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.

Bash

The following works with and outputs (rounded-off) integers only:

```f() {
echo "sqrt(\${1#-}) + 5 * \$1 ^ 3" | bc
}

array=()
for i in {0..10}; do
done

for ((i=\${#array[@]}-1; i>=0; --i)); do
let x=\$(f \${array[\$i]})
(( x > 400 )) && echo 'TOO LARGE' || echo \$x
done
```

Although external programs can be used for unavailable (complex) functions, Bash is inherently incapable of floating-point arithmetic comparison.

C

```#include <stdio.h>
#include <math.h>

#define N 11

double vals[N];

double f(double x) {
return sqrt(fabs(x)) + 5*x*x*x;
}

int main(void) {
int i;

for(i = 0; i < N; ++i)
scanf("%lf", &vals[i]);

for(i = N-1; i >= 0; --i) {
double x = f(vals[i]);
if(x > 400)
printf("TOO LARGE\n");
else
printf("%.3f\n", x);
}

return 0;
}
```

C++

```#include <iostream>
#include <cmath>
using namespace std;

double f(double x) {
return sqrt(abs(x)) + 5*x*x*x;
}

int main() {
double vs[11];
for (auto& v : vs) cin >> v;
for (int i = 10; i >= 0; --i) {
auto x = f(vs[i]);
(x > 400 ? cout << "TOO LARGE" : cout << x) << endl;
}
}
```

Groovy

```def grooVals = []
def scanner = new Scanner(System.in)
11.times {
grooVals << scanner.nextDouble()
}
grooVals = grooVals.reverse()
for (val in grooVals) {
def calcVal = f(val)
if (calcVal.isInfinite())
println 'TOO LARGE'
else
println calcVal
}
```

```f :: Floating a => a -> a
f x = sqrt (abs x) + 5 * x ^ 3

message :: (Num a, Show a) => a -> String
message x
| x > 400   = "TOO LARGE"
| otherwise = show x

main :: IO ()
main = do
values <- replicateM 11 readLn
mapM_ (putStrLn . message . f) values
```

Java 5

```import static java.util.Collections.reverse;

import java.util.Scanner;

public class TrabbPardoKnuth {
private static double f(double x) {
return Math.sqrt(Math.abs(x)) + 5 * Math.pow(x, 3);
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
try {
for (int i = 0; i < 11; ++i) {
}
} finally {
scanner.close();
}
assert (numbers.size() == 11) : "input should be eleven numbers";
reverse(numbers);
for (double number : numbers) {
Double fx = f(number);
if (fx.isInfinite()) {
System.out.println("TOO LARGE");
} else {
System.out.println(fx);
}
}
}
}
```

Lua

A Lua variant might look like this. Lua is compiled with Double precision numbers by default, but any other format is possible.

```function f(x)
return math.abs(x)^0.5 + 5*x^3
end

t = {}

for i=1,11 do
end

for i=#t,1,-1 do
local r = f(t[i])
if r > 400
then print("TOO LARGE")
else print(r)
end
end
```

OCaml

The OCaml version using imperative features such as for loops:

```let () =
let f x = sqrt x +. 5.0 *. (x ** 3.0) in
let pr v = print_endline (if v > 400.0 then "overflow" else string_of_float v) in
let a = Array.init 11 (fun _ -> read_float ()) in
for i = 10 downto 0 do
pr (f a.(i))
done
```

A functional version can also be written in OCaml:

```let tpk l =
let f x = sqrt x +. 5.0 *. (x ** 3.0) in
let p x = x < 400.0 in
List.filter p (List.rev_map f l)
```

Pascal

```program TrabbPardoKnuth(input, output);

const
N = 11;

var
Vals: array[1..N] of real;
I, X: integer;

function F(X: real): real;
begin
F := Sqrt(Abs(X)) + 5 * X * X * X
end;

begin
for I := 1 to N do

for I := N downto 1 do
begin
X := F(Vals[I]);
if X > 400 then
WriteLn('Too large!')
else
WriteLn(X)
end
end.
```

Perl

A Perl version using exceptions might look like this:

```use feature 'say';

sub f {
sqrt(abs(\$_[0])) + 5*\$_[0]**3
}

for (1..11) {
push @inputs, scalar <>
}

for (reverse @inputs) {
eval { say f(\$_) } or say "Problem with entry \$_: \$@"
}
```

Python

```import math

def f(x):
return math.sqrt(abs(x)) + 5 * x**3

vals = [float(raw_input()) for i in range(11)]
for i, x in enumerate(reversed(vals)):
y = f(x)
print('{0}: {1}'.format(i, y if y <= 400 else 'TOO LARGE'))
```

Floating point in Python on most platforms is IEEE-754, which can return "nan" and "inf" values, or raise an appropriate Python exception.

q/KDB

```/input : 1 2 3 4 5 6 7 8 9 10 11
tpk:{[x] \$[400>res:sqrt[abs x] + 5* x xexp 3; res; `\$"TOO LARGE"]};
tpk each reverse input
```

q does not provide any function/operator for standard input.

R/S-PLUS

In R/S-Plus the user is alerted of an overflow by NaN value. Three of many possible implementations are

```# without an assignment
(function(t) sqrt(abs(t))+5*t^3)(rev(scan(nmax=11)))

# with an assignment
sqrt(abs(S <- rev(scan(nmax=11))))+5*S^3

# as a routine
tpk <- function(S = scan(nmax=11), t=rev(S)) sqrt(abs(t))+5*t^3
```

The last implementation makes use of the lazy evaluation mechanism of R for default values of parameters: `t` is evaluated only the first time it is used in a computation, after which `t` is well defined.

Ruby

The Ruby version takes advantage of some of its distinctive features:

```def f(x)
Math.sqrt(x.abs) + 5*x ** 3
end

11.times.collect{ gets.to_i }.reverse.each do |x|
y = f(x)
puts "#{x} #{y.infinite? ? 'TOO LARGE' : y}"
end
```

Scala

```object App {
def f(x: Double) = Math.sqrt(Math.abs(x)) + 5 * x * x * x
def main(args: Array[String]) {
val v = for (i <- 0 to 10) yield readDouble()
(0 to 10 reverse) map v map f map { x =>
println(if (x > 400) "TOO LARGE" else x)
}
}
}
```

Scheme

The following is tested with Chicken Scheme.

```(define (read-values n)
(if (zero? n)
'()
(read-values (- n 1)))))

(define (f x)
(+ (sqrt (abs x)) (* 5 x x x)))

(for-each
(lambda (val)
(let ((result (f val)))
(print
(if (> result 400)
"TOO LARGE"
result))))