From: jlg@cochiti.lanl.gov (Jim Giles)
Subject: Re: Types, arrays, generality, and notation (was: Fortran90 and Arrays)
Organization: Los Alamos National Laboratory
Date: Mon, 13 Apr 1992 19:49:47 GMT

In article <STEPHEN.92Apr11043808@estragon.uchicago.edu>, stephen@estragon.uchicago.edu (Stephen P Spackman) writes:
|> [...]
|> Register allocation, type representation selection, calling
|> conventions, inlining, space/speed generation choices, argument format
|> checking, exception handling, and code placement. That's probably only
|> a quarter of the list of things that you can't get right on a
|> module-at-a-time basis. You really are straightjacketting yourself by
|> INSISTING on separate compilation.

And you are straightjacketting yourself by INSISTING that the language 
need not make any effort to support separate compilation.  Like most 
things, the user should be told the trade-offs and allowed to decide
for himself.  This doesn't mean that the implementor shouldn't try to
make the language as efficient as possible for the entire range of
possible user choices.

Further, by moving code generation into the _loader_, such things
_are_ possible with separate compilation.  Certainly, even without
such drastic measures, certain of these are appropriate work for 
the loader - like argument format checking.

|> |[...]
|> |The explicit declarations available to a language _could_ include
|> |usage statistics from test runs or preceeding versions.
|> 
|> But self-modifying source is a worse disaster than self-modifying
|> object. (Of course, there's a clean, standard solution in the form of
|> compiled, automatically-derived interface files).

Oh?  I see.  You are assuming that all declarations about a program
need to be in source.  This is not true (though, the user should have
the option of where to put declarations - if he wants the assertion
about usage statistics in source he should be allowed to put it there).

|> [...]
|> |That's what relocatable files _are_ (like C dot-oh files).
|> 
|> Ha ha. Try dumping one some day. Thre MAY be a few compilers that get
|> this right (in fact Mark Rain's Mary2 was supposed to, ten years gone
|> by), but they're not what you'd call common....
|> 
|> Here's the acid test: can you take your relocatable file and use it on
|> a machine with a different architecture? I thought not....

Here's the other acid test.  Can a software pirate move a copy of my
code to another machine/architecture without my permission?  I thought
not....  The _reason_ vendors prefer not to distribute code is to
limit piracy.  Why would they want an arbitrarily redistributable
intermediate code representation instead?  That makes piracy nearly
as easy a publishing the code would have.

|> [...]
|> |"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".
|> 
|> No it is not. SUPPORT for arrays is important - surely important
|> enough to justify that arrays be ONE of the type-construction methods
|> directly supported by the standard library. But giving it a
|> distinguished syntax is perhaps going too far - and giving it 90% of
|> the operator namespace (as in J) is criminal.

I think _all_ type-construction methods deserve a distinguished syntax.
There are only eight that I can think of (the same eight that C.A.R. Hoare
thought of in Structured Programming, Dijkstra, Dahl, and Hoare).  These
eight are:

   I) Intrinsic data types.  These should be chosen as appropriate for
      the intended problem domain(s) of the language.  Are you saying
      that there should be no distinguished syntax for, say, integer 
      literals?

  II) Enumerated data types.  Hoare calls these `Unstructured Data Types'.
      Among the appropriate distinguished syntax for these is, in my 
      opinion, that the enumerations should differ from ordinary
      identifiers in some recognizable way so they don't complicate
      the name space.  (Note: Hoare and others often regard integer
      subranges as enumerated types.  I prefer to think of them as
      subtypes of integer.)

 III) Record data types.  Hoare calls these `The Cartesian Product'.
      This is the same as Pascal records, C structs, and Fortran 90
      derived data types.  Their distinguished syntax includes a
      field selection symbol (Pascal and C use `.', Fortran 90 uses
      `%' - yes, I find `%' ugly too).

  IV) Discriminated Union data types.  Like Pascal variant records
      and C unions.  I think that they should be required to be
      explicitly discriminated.  Fortran 90 doesn't have them and
      C doesn't discriminate them.  Among the appropriate distinguished 
      syntax for these is some mechanism of specifying the discriminant
      in every assignment (that way you don't get it wrong).

   V) The Array.  This is a mapping from one or more index sets to
      values of a given base type.  Hoare limits these to rank one
      (higher ranks are simulated with arrays of arrays).  Syntax
      for element selection, whole array selection, selection of
      whole sub-array slices along any rank, etc. are all appropriate
      for distinguished syntax depending on the target users of the
      language.  Fortran does this better than Pascal or C (for 
      scientific/numerical users anyway).

  VI) The Set.  Hoare calls this the Powerset.  This is the one type
      construction mechanism I don't think should be built-in to a
      language.  The problem is that there are too many different
      implementation choices for sets: an array of bits, a hash table,
      a linked list, etc..  The user is the only person who can choose
      which is best and should be responsible to do so.  Building the
      feature into the language would require _lots_ of distinguished
      syntax to allow the user to select which implementation is wanted.
      Fortran 90 doesn't have them, nor does C.

 VII) The Sequence.  Hoare thinks of these as something like pascal
      File variables.  They could also be thought of as streams (also
      generally an I/O concept).  However, there is no reason to assume
      that I/O is the only application of these.  They are really just
      1-d arrays whose extent is unspecified (not as a type attribute
      anyway - the extent is part of the value).  Selection and 
      concatenation are appropriate candidates for distinguished 
      syntax.  Fortran and C don't have them, Pascal has a limited
      version.

VIII) Recursive data types.  Linked lists, trees, graphs, etc..  Once
      again, selection is appropriate for distinguished syntax.  As is
      some syntax for traversal of the structure.  Whether this is done
      with explicit pointers (you'd need an explicit dereference then)
      or not I will not address here.  Fortran 90, Pascal, and C use 
      explicit pointers.

These are the eight data types all general programming languages should 
support.  By allowing them to be used orthogonally (like: an array of
sequences, or a linked list of records, etc.) you can build any data type
I've ever come across.  Are there any Hoare left out?  In any case, it 
seems perfectly appropriate - even desirable - for each of these to have 
a distinguished syntax to improve legibility of the code.

Whether J has any of these other than the intrinsic types and the
arrays is unknown to me.  Obviously, with some difficulty, you can
implement most of these with dynamic arrays in one way or another.
This doesn't seem to me to be an appropriate thing to force the
user to do.
      
|> [...]
|> And by "type-o-phobia" I intended to suggest an attitude that types
|> are a "magic" mechanism which the user can't be allowed to use on hir
|> OWN behalf, to solve actual problems....

As seen above, I obviously don't support "type-o-phobia".  If you've
got other suggestions that aren't on the list, please point them out.

|> [...]
|> System-reserved mechanisms: fortran has keywords and weird syntaxes
|> for this and that. [...]

Yes, but no keywords are reserved in Fortran since the syntactic rules 
are such that it's always possible to distinguish keywords from other 
identifiers by position.  In fact, far from being a benefit, Fortran 
has been strongly criticized for this.  They are certainly not system 
reserved.  Further, Fortran 90 permits overloading all the operators 
for user defined meanings.  I would prefer that it allow definition 
of new operators constructed from an operator character set `@^*+-<>/\|' 
and maybe a few others - I would prefer this mostly becuase it would 
then be possible to discourage overloading the intrinsic operators 
for inappropriate meanings.  Fortran 90 also permits defining named 
operators which (like the named intrinsic operators: .and., .or., etc.  
must be enclosed between dots).

So, none of these things are reserved in Fortran - even though some 
people think they _should_ be.  Apparently, J DOES reserve most of
the special symbols for arcane purposes of its own.  It is a strange
case: those things that should be spelled out with a keyword for
clarity, it uses some arcane symbol for; and those things that 
symbols should be available to users for are prohibited.

|> 
|> |with an efficient method of calculating without floating-point and
|> |I suspect Fortran (even J) would be quickly extended to support it.
|> 
|> Fixed point with the compiler tracking the scaling factor, of course.

It's considerably slower than floating-point.  Also, it's not 
more accurate than floating-point, it just has _different_ error 
characteristics (unless you scale on _every_ operation, in which
case it _IS_ floating-point, just inefficiently simulated in
software).

|> Von Neumann pointed this out, and I concur: there aren't enough
|> things in nature with a dynamic range in excess of 2^64 to justify
|> giving hardware support to floating point; what it's actually USED for
|> is to avoid thinking about dynamic range at all, and that leads to
|> bugs.

The dynamic range, just of linear scale, of things scientists routinely
calculate is about 10^160.  For volume scaling in this same range you
need 10^480.  Further, it's desirable not to have to rescale intermediate
calculations and such - so a wider exponent range is valuable.  Further,
if over/underflow are what you are complaining about, the wider range 
makes this _less_ of a problem, not more.

|> [...]
|> In principle we could have 128-bit integers that are significantly
|> faster than IEEE floating point - and a lot more useful - and I think
|> it's really stupid that the FORTRAN community has such a stranglehold
|> on hardware architecture that people don't wake up and start demanding
|> good support for integers.

Yes, I think integers are important - but _independently_ of whether
floating-point is supported or not.

|> [... reduction on empty array ...]
|> Nono, you missed the point. Some operations (like "+") make SENSE for
|> empty arrays, and there you supply the appropriate value (0). Others
|> (like "min") only make sense on an empty array in an extended domain
|> (for present purposes: don't make sense) and so you REQUIRE at least
|> one element, pass THAT as the identity, and then reduce the REMAINDER
|> of the array (which will now be length 0 if the original was length
|> 1).

But, the _user_ should control which semantics he wants.  The compiler
shouldn't lock him into a given decision.  Further, except on intrinsic
operators, the compiler has no idea which to do.  Or are you saying that
reduction should only be supported for intrinsics?

|> [... how to use an unordered scan ...]
|> Yes. You are searching in a tree, and you want to use the natural tree
|> structure and not get it flattened to a vector. I *don't* know of a
|> language with a type structure in which this very practical problem
|> can be made to drop out notationally though - but wait another five or
|> ten years, and you'll see it cropping up. It'll look like an alternate
|> interface that makes an automatic coercion (an interface inheritance,
|> actually) unnecessary.

Hmm.  I would have regarded searching as a reduce, not a scan.  Also, 
whether this makes sense unordered or not depends upon whether the 
search function returns the matching element or the position of match.

Now, _sort_ would be a scan - I suppose you could do that with the data
arbitrarily reordered by the compiler on the way in.  It would lose the
strictness of the sort though.

|> [...]
|> |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?
|> 
|> You need to use "cons" instead of "+" to see how it might be
|> interesting - "+" has the wrong algebraic properties for this
|> operation, and that ought (in principle) to be a static type error.

How does the compiler know which user-defined functions have 
the right algebraic properties for an unordered scan?  Further,
it seem to me that "cons" applied to the list of integers does 
nothing but reorder the list.  Why would a compiler determined
reorder be useful - a reorder driven by the random number 
generator would - just an arbitrary compiler decision though?

J. Giles
Newsgroups: comp.lang.misc