From: jlg@cochiti.lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: Types, arrays, generality, and notation (was: Fortran90 and Arrays)
Date: 10 Apr 92 18:40:17 GMT
Article-I.D.: newshost.1992Apr10.184017.10041
Organization: Los Alamos National Laboratory

In article <STEPHEN.92Apr10055926@estragon.uchicago.edu>, stephen@estragon.uchicago.edu (Stephen P Spackman) writes:
|> [... static type tests ...]
|> Look at SELF. Hell, look at the internals of a competent FORTRAN
|> compiler. You're thinking in the stone age! :-)

But Fortran requires declarations!  If you haven't got declarations
AND you've got I/O, separate compilation, and the ability to assign
objects of _any_ type to _any_ identifier, you can't expect the 
compiler to be able to do compile-time type checking very well.
It means that you must infer constraints about objects which 
inherently aren't known until run-time.

|> [...]
|> It's not a question of if they could according to the language spec,
|> it's a question of whether they could according to the programme text
|> as interpreted under that language spec, and those are poles apart.

Agreed.  There is much that _can_ be done even without declared variables.
But, that is not as much as is _easily_ done if you have declarations.
If you have declarations AND sophisticated techniques, you can do 
better than if you have to go without one or the other.  And, as
I've repeatedly pointed out, declarations make the code more legible
to _humans_.

|> [...]
|> Separate compilation and optimisation are mutually incompatible
|> anyway, so don't worry about it in THIS context [...]

Separate compilation and optimization are not _that_ incompatible if
it's possible for most of the optimization to be carried out on the 
basis of declared attributes.  The loader can include checks to make 
sure the actual uses match the declarations.

|> [...]                                                 - in fact,
|> optimisation without prior execution is undesriable, too, so a decent
|> system with good performance is going to look a bit interpretive....

The explicit declarations available to a language _could_ include
usage statistics from test runs or preceeding versions.

|> [...]
|> Have you considered distributing the intermediate code instead?

That's what relocatable files _are_ (like C dot-oh files).

|> ...reaches for asbestos-type trousers...
|> 
|> What, you think I'm defending J, just because I don't like FORTRAN?
|> They're practically dialects of each other anyway, with their
|> array-o-centrism, type-o-phobia, line-oriented syntax, proliferation
|> of system-reserved mechanisms, encouragement of semantically
|> inexplicable floating-point arithmetic and general inattention to
|> actually solving the problem....

"Array-o-centrism" is an important feature for a large set of 
important applications.  I don't know what you mean by "type-o-phobia".
To be sure, Fortran hasn't got a complete set of type construction
tools (Fortran 90 makes this worse by introducing explicit pointers
as the only mechanism for recursive data structures, etc.).  I don't
know what you mean by "line-oriented syntax" either, but human factors
experiments have shown that people intuitively use lines in certain
ways and languages which don't conform to these ways induce larger
numbers of errors.  What's a "system-reserved mechanism"?  Come up
with an efficient method of calculating without floating-point and
I suspect Fortran (even J) would be quickly extended to support it.

As for "actually solving the problem", most of the other things you
mentioned are required in order to make "solving the problem" possible.
The problem is to run large scientific/numerical calculations on existing
hardware with existing software technology.  The existing hardware is
too slow, has too little memory, and the existing software technology
is inadequate at automatically making best use of the existing speed
and space based on a purely abstract problem definition.  

For example: a global weather simulation with one mile horizontal 
resolution and five layers vertically (this is a _very_ coarse mesh) 
would require a mesh with one *billion* cells.  Each cell needs to carry 
20 to 30 numbers around with it to describe temperature, pressure, 
composition, flow, vorticity, etc..  No existing machine can even run 
such a program, and no proposed machine (even for the fairly distant 
future) will be capable of running the simulation in real-time.

Running scientific/numerical calculations of any value at all requires
considerable control on the part of the programmer and considerably
powerful tools for manipulation of such things as arrays.  Numeric
calculations need to be as fast as possible (and still return useful
data) which is why floating-point will be with us for the forseeable
future.  (Note, the trade-off between speed and precision isn't ignored
by the programming community.  There is no scientific/numerical program
I know of which would accept IEEE single precision any more - calculations
run fast enough and long enough that even stable algorithms can accumulate
enough error to swamp a 24-bit significand.  IEEE double may be in similar
trouble a decade from now.  If you can propose faster arithmetic, or a
reasonably fast arithmetic which has better error characteristics, now's
the time - actually, any time would be the time.)

|> |[...]
|> |Ok.  This could be defined as the operation of REDUCE.  You'd have
|> |to add a way of passing the identity element (and a way of stating
|> |that there isn't one).
|> 
|> Gotta be one, if you're going to go the directional route. But you can
|> always use the end element of the array if you are SURE that's what
|> you want.

I thought the identity element was returned for _empty_ arrays.  The
end element of an array doesn't exist in this case.  What you want is
to give the _user_ the option of stating whether this should be considered
an error or not.  So, you pass an identity element as an additional 
optional argument to reduce and if it is omitted you treat empty arrays 
as errors.  

The Haskell standard prelude includes four definitions of reduce (which 
it calls `fold').  The four are foldl, foldr, foldl1 and flodr1.  The 
`l'and the`r' suffixes determine whether the reduction is left- or 
right-associated.  The `1' means that the identity element is the 
first (last) of the array, leaving off the one means that an identity 
element will be passed explicitly.  So:

      foldr :: (a -> b -> b) -> b -> [a] -> b
      foldr f z [] = z      -- foldr on empty array returns identity
      foldr f z (x:xs) = f x (foldr f z xs)

      foldr1 :: (a -> a -> a) -> [a] -> a
      foldr1 f [x] = x    -- foldr1 is not defined on an empty list
      foldr1 f (x:xs) = f x (foldr1 f xs)

      ... and so on for the other two ...

Note that the Haskell standard prelude does not have a definition
that allows reduction in unspecified order.  It does give complete
control over how the identity element is selected and used.

|> [... `scan' in unspecified order ...]
|> "Random", unlikely. "Underspecified", you bet. "Implementation's
|> choice", quite likely if the machine is a multiprocessor, a vector
|> machine, or....

I don't question the possibility of such a thing, but what would anyone
use it for?  As I said, I'll take you word for it that it _may_ be
useful, but I think I'd rather have the default version of `scan' not
allow it - such a rarely needed feature, if accidentally used, is almost certainly just an error.  Can you givean example of an algorithm which
can make sensible use of unordered scan results?

For example: let's scan addition across an list of integers (1,3,5,7,9).
What happens if the result is (16,8,5,15,25) [I summed from the middle 
element out, alternating left and right]?  Is this meaningful to any
algorithm you know?

Interestingly, the Haskell standard prelude (while I have it in front 
of me from the last paragraph) only has one scan defined -  left to 
right with an explicitly required initial result:

      scan :: (a -> b -> a) -> a -> [b] -> [a]
      scan f q xs = q : case xs of
                        [] -> []
                        x:xs -> scan f (f q x) xs

Haskell doesn't have these functions extended to directly handle
multi-rank arrays, much less arbitrary directions through them.
Such capability can only be handled by mapping the array into a 
list of sub-arrays (along the desired axis) and defining the 
function `f' on those sub-arrays.

By the way, at this point I've spent about the same amount of time
studying Haskell as J - cumulatively about five hours each.  I find
Haskell much more legible and easy to use (which isn't saying much).
Given that Haskell is a strict functional language and J isn't, if
the argument is that there is an advantage to functional programming,
then Haskell must be better according to that measure.

J. Giles
Newsgroups: comp.lang.misc