On Sun, Nov 4, 2012 at 7:10 PM, Boyko Bantchev <[email protected]> wrote:
> 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.
Independent?
> 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;
Here, I am bemused by two issues, one is the parallel between names
(APL and CPL) the other is the parallel in structure (Iverson's APL
was based on notation he had used to teach at Harvard in the
late '50s.)
> -- 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.
I remember encountering a variety of ways of implementing cartesian
products in APL2, but anyways...
> 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.
1) Being more general is not always an advantage.
2) APL, the language, implements -/
3) I do sometimes write algorithms I want the generality of fold,
where I have an initial value and result type which in Haskell would
be a different type from the array. But I also see the value in using
different notation for this than for the simpler case where they are
the same "type".
4) For what it's worth, here's foldl in J:
FoldL=: 1 :0
:
>u~&.>/(<"_1 |.y),(<x)
)
FoldR is simpler to implement in J than FoldL:
FoldR=:1 :0
:
>u&.>/(<"_1 y),(<x)
)
I do not know Haskell (nor the jargon of category theory) well enough
to know how this would be expressed in Haskell. I imagine that boxing
in J, like this, is analogous to constructing a monad in Haskell, with
> being like a Haskell monad's "return". But since I'd have to
construct a single typed "insert" based on FoldR I'd probably have to
deal with a lot of "what's the point"?
I will agree that you could not write the above FoldL/FoldR in the
original APL -- you'd need APL2 or a more recent instance for that.
I might also agree that J might use a more abstract concept of "array"
where an axis corresponds to a lazy computation, and where the
programmer decides whether asking for all of the array (for example,
asking for the array's shape, or using something like this FoldL)
means "wait for it" or "error". There's a lot of things that could
fit within J's definition (some of which I have seen in APL
implementations -- like a compiler and a type inference system) that
we do not currently have implemented.
I'm not sure, though, that the concept of "catamorphism" is any more
useful than the above implementation of FoldL.
> 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.
Once you have abstracted out the need to represent the array, this
concept can be equivalent to a sequence of arbitrary actions, so I
think you are describing some terminology for "programming".
A more interesting issue, from my point of view, is the subject of
what kinds of things are simpler to describe this way than other ways
(which, of course, depends on what "other ways" we are considering,
and how we judge "simplicity").
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
