Although Iverson is apparently the first to propose the reduce
operation on vectors, there is a strong evidence that the higher-order
function 'fold' (a.k.a. reduce, accumulate, etc.), as known in today's
programming languages, have an independent origin.
That origin is almost as old as Iverson's proposal (and has nothing to
do with Lisp, to which REDUCE is somewhat foreign even today!).
In the early 1960s, Christopher Strachey was designing a language that
he named CPL. CPL had many innovative features, including support for
functional programming. Together with David Barron, Strachey published
the following paper, aiming to popularize CPL (although the language
was never fully implemented):
D.W.Barron and C.Strachey. Programming. Chapter 3 (pp.49-82)
of 'Advances in Programming and Non-numerical Computation',
Pergamon Press, 1966.
This text itself is hard (for me) to find, but it was commented
elsewhere in the literature. Thus we know that it:
-- is based on lecture notes used at a summer school held in
Oxford in 1963;
-- contains surprisingly modern (from today's perspective)
functional-programming techniques, including composing a
program from simpler parts;
-- among others, presents the following example:
let Product[L] = Lit[f,List1[NIL],L]
where f[k,z] = Lit[g,NIL,k]
where g[x,y] = Lit[h,y,z]
where h[p,q] = Cons[Cons[x,p],q]
The above defined function, Product, finds the Cartesian product of
arbitrary number of lists, each one arbitrarily long. The function
itself is truly brilliant, but it is no less amazing that the CPL
function Lit (for list iterator) used in it is exactly what we now
know as foldr in ML, Haskell, etc.
It must be noted that Lit is more general than Iverson's definition
of '/' (reduce) in several respects:
-- the list element type for Lit is arbitrary (not just numeric
or Boolean ('logical'));
-- the two-argument function that is the first argument to Lit
does not need to be associative (in the 1960 article that
Roger mentioned Iverson is explicit about the associativity;
in 'A Programming Language', 1962
(http://www.jsoftware.com/papers/APL.htm) he does not mention
it explicitly but seems to assume it);
-- beside the function and the list, Lit has a third argument
(actually, the second in order), which provides Lit's result
for empty lists and initiates the computation for non-empty
lists;
-- the result type of the function argument of Lit (along with
the result type of Lit) can be different from the type of the
list elements.
The Lit function was studied by different people afterwards and
eventually became today's foldr. Of particular interest has been
what computations can be expressed through fold, and what cannot be.
A generalization from lists to arbitrary constructive types brought
the notion of catamorphism.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
