Re. Gavin Wraith's message on Types & Strictness

Date: Thu, 16 Mar 89 20:52:05 EST
Cc: ap%computer-lab.cambridge.ac.uk-LEftKC8aXbilgWnZye4G+Q@xxxxxxxxxxxxxxxx,
        gavinw%syma.sussex.ac.uk-LEftKC8aXbilgWnZye4G+Q@xxxxxxxxxxxxxxxx
In-Reply-To: Andrew Pitts's message of Thu, 16 Mar 89 09:31:01 EST 
<8903161431.AA01476-V7RBKq7CZw5JFtkRo5AIfbg7sE8m1Ewp@xxxxxxxxxxxxxxxx>


Gavin Wraith's message on Types and Strictness is very interesting.  I would
like to offer my point of view on some issues of strictness that he raised.

    >The functional programming community seem divided into two camps;
    >the major camp being proponents of normal order evaluation, a
    >minority arguing for applicative order.

Some of us who are interested in parallel evaluation actually constitute a
third camp: We like the the strictness properties of normal order, but
consider normal order an overkill to achieve them.  For example, in our
dataflow implementation of Id, a functional language, we do evaluate an
argument before it is demanded but, in parallel, we also invoke the function
body.  Depending on the whether the function body requires the argument or
not, it may even return a result before the argument has finished computing.

Thus, this ``dataflow order'' is also a normalizing strategy, though it is
not technically normal order.  Functional Id has exactly the same strictness
properties as lazy languages, but does not do lazy evaluation--- it may do
unneeded computation.

    >                                        Everybody agrees that the
    >latter is more efficient, but the former is necessary for easy
    >manipulation of infinite data-objects.
    > ...
    >Infinite data-objects arise as values of recursive product types.

1) In fact, in a parallel system, applicative order is less efficient than
the dataflow order in that it can have less parallelism, and so processors
may not be utilized as efficiently.  Consider the following Id program to
compute the fringe of a tree:

    type tree = Empty | Node num tree tree ;

    typeof fringe = tree -> (list num) ;

    def fringe t = aux t nil ;

    def aux Empty        xs = xs ;
    def aux (Node n l r) xs = aux l (n:(aux r xs)) ;

Under applicative order, this is a sequential traversal of the tree, and
takes time proportional to the number of nodes in the tree.  Under our
nonstrict dataflow order, both recursive calls to aux occur in parallel, and
the computation takes time proportional to the depth of the tree.

2) Nonstrictness (via dataflow or lazy evaluation) is very useful even for
finite objects.  For example, suppose we want to define an array containing
the first 20 Fibonacci numbers.  In Id, we express this as follows, using
Id's ``array comprehension'' notation:

    typeof fibs = (array num) ;

    fibs = {array (1,20)
            | [1] = 1
            | [2] = 1
            | [j] = fibs[j-1] + fibs[j-2] || j <- 1 to 20} ;

i.e., an array of size 20 with the first two locations containing 1 and
subsequent locations containing the sum of the previous two locations.  This
recurrence cannot be expressed in applicative order languages (Scheme and ML
only allow function definitions in recursive bindings).  This example is not
contrived: there are a many examples in scientific computation of (finite)
arrays defined using recurrences.

Rishiyur Nikhil

nikhil-7nwHvcHdrJGVc3sceRu5cw@xxxxxxxxxxxxxxxx
----------------------------------------------------------------