Trabb Pardo-Knuth algorithm

From Wikipedia, the free encyclopedia

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.

[edit] 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.

[edit] Implementations

[edit] 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.

[edit] Python version

The following Python version of the algorithm employs the common Python idiom of using a list in place of an array:

def f( i ):
    return math.sqrt(abs(i)) + 5*i**3
 
a = [int(raw_input()) for i in range(11)]
for i in reversed(a):
  try:
    y = f(i)
    if y > 400: raise Exception
    print y
  except Exception:
    print i, "TOO LARGE"

There are more concise ways of implementing the algorithm, but this shows the algorithm in a normal, modern programming style.

[edit] Ruby version

The Ruby version takes advantage of some of its features:

class TPK
  def f( x )
    return Math.sqrt(x.abs) + 5*x **3
  end
 
  def main
    Array.new(11) { gets.to_i }.reverse.each do |x|
      y = f(x)
      puts "#{x} #{(y>400) ? 'TOO LARGE' : y}"
    end
  end
end

Ruby handles numerical overflow by returning Infinity, which is greater than 400.

[edit] Ocaml version

The Ocaml version using imperative features such as for loops:

let tpk () =
   let f x = sqrt x +. 5.0 *. (x ** 3.0) in
   let pr f = print_endline (if f > 400.0 then "overflow" else string_of_float f) in
   let read () = float_of_string (read_line ()) in
   let a = Array.init 11 (fun _ -> read ()) 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.map f (List.rev l))

[edit] 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)

[edit] External links

• Implementations in several modern languages