Re: Arrays and general function representation

1992-09-04 Thread Paul Otto

date:  Thu, 3 Sep 92 15:58:43 CST
from:  [EMAIL PROTECTED] (Ken Sailor)

Arrays and general functions are isomorphic, certainly in theory.
In practice, however, they are different and the differences
are significant.

And finally, it makes sense to have separate syntax for arrays
and general functions, because different behavior is expected
for the two.

That argument would suggest that you should use a different
syntax for each different implementation of an abstract data
type.  (Since their performance tradeoffs are usually different.)
Do you advocate that?

Paul




Re: Arrays and general function representation

1992-09-03 Thread Ken Sailor

My humble opinion about arrays and general functions...

Arrays and general functions are isomorphic, certainly in theory.
In practice, however, they are different and the differences
are significant.

In general, although the set theoretic definition of a function
is a set of ordered pairs, it is convenient to think of a function
as a rule.  That is, given an input, the rule tells how to compute
the output.  It may be that for some special functions, we want
to encode the rule as a lookup on some table, but in fact this
technique is not generally applicable.  Why store a gazillion
values for + when we can implement the rule in hardware?

Typically arrays are boxes which contain values.  That is, they
are multi-dimensional tables in which values can be looked up.
In the imperative world, the lookup cost is typically a constant,
guaranteeing timing behavior for various algorithms.  

In the functional world, nobody has figured out how to get all the
practical benefits of imperative arrays, for a variety of reasons.
Until these benefits are achieved, functional languages will not
be practical for most, if not all, scientific programming applications.
(apologies to the sisal community in advance -- my own interest
is in lazy functional languages like Haskell, where arrays are
in greater disorder).

It entirely misses the point of why arrays are hard to say that
there are no differences between arrays and general functions.
In theory, arrays are a snap.  You can have them in a variety
of interesting forms, but they don't come with the performance
guarantees they have in the imperative world, and that is the
problem of arrays in a nutshell.

And finally, it makes sense to have separate syntax for arrays
and general functions, because different behavior is expected
for the two.

Ken Sailor
[EMAIL PROTECTED]




Re: Arrays and general function representation

1992-09-03 Thread Ken Sailor

My humble opinion about arrays and general functions...

Arrays and general functions are isomorphic, certainly in theory.
In practice, however, they are different and the differences
are significant.

In general, although the set theoretic definition of a function
is a set of ordered pairs, it is convenient to think of a function
as a rule.  That is, given an input, the rule tells how to compute
the output.  It may be that for some special functions, we want
to encode the rule as a lookup on some table, but in fact this
technique is not generally applicable.  Why store a gazillion
values for + when we can implement the rule in hardware?

Typically arrays are boxes which contain values.  That is, they
are multi-dimensional tables in which values can be looked up.
In the imperative world, the lookup cost is typically a constant,
guaranteeing timing behavior for various algorithms.  

In the functional world, nobody has figured out how to get all the
practical benefits of imperative arrays, for a variety of reasons.
Until these benefits are achieved, functional languages will not
be practical for most, if not all, scientific programming applications.
(apologies to the sisal community in advance -- my own interest
is in lazy functional languages like Haskell, where arrays are
in greater disorder).

It entirely misses the point of why arrays are hard to say that
there are no differences between arrays and general functions.
In theory, arrays are a snap.  You can have them in a variety
of interesting forms, but they don't come with the performance
guarantees they have in the imperative world, and that is the
problem of arrays in a nutshell.

And finally, it makes sense to have separate syntax for arrays
and general functions, because different behavior is expected
for the two.

Ken Sailor
[EMAIL PROTECTED]




Re: Arrays and general function representation

1992-08-26 Thread Rex Page

I like David Barton's idea of distinguishing between the
array representation of functions and the more familiar
computational representation at the declaration level
but not at the reference level.  With this appraoch
references to arrays and references to functions would
look the same in expressions, which is appealing because
they express the same concepts.   Declarations would give the
processor hints about possible economies of implementation.

At least one language I know of suggests, in its syntax,
the similarity between functions and arrays: Fortran.
Subsequent languages have, unfortunately, failed to follow
Fortran's good example in this regard.  I tried to get the
Fortran 90 standards committee to continue the metaphor to
data structures so that references to components would look
like function references and be distinguished from them only
in the declarations.  The committee didn't buy the idea,
however.

A question that came up in the Fortran 90 discussions on
the syntax of references to components of data structures:
Which is the function and which the argument?  Fortran
syntax views the array as the function and the subscript as
the argument.  The other way around seems better for data
structures because component names are constant entities and
different instances of the data structure are the (variable)
data that might act as arguments to (selector) functions
denoted by the names of components.

This might work for arrays, too:

traditional references
(array is function,   a 1,  a 2, ...
 subscript is argument)

other way around
(subscript is function,   1 a,  2 a, ...
 array is argument)

In the alternative formulation, the integers name
polymorphic functions mapping arrays of various types
into the base type of those arrays. But there is a problem
with dereferencing a variable subscript in this formulation:
(n a) should mean "apply the function named by the integer
value of n to the array a" rather than "apply the function
named n to a".

The traditional formulation gets the referencing right,
though, doesn't it?  And it seems to apply equally well
to lists.  Writing (lst n) to select the n-th element of
lst looks good and draws an appropriate analogy to functions.

Rex Page