On 20/12/2012, at 3:53 AM, srean wrote:
>
> The C world and Fortran world are split on this issue.
Not really: Fortran has multi-dimensional arrays, C does not.
If Fortran allowed arrays of arrays they'd work the same way as in C.
The issue is like this: I will use named methods here for clarity.
vget ( vget (aa, i), j) ==> mget ( mat (aa) , pair (j, i) )
Is this right? Or should the arguments to pair be i,j?
Here 'v' means vector and 'm' matrix.
Before you get too hasty, let me change the methods a bit:
proj (j, proj (i, aa) ) ==> proj ( pair (j,i), mat(aa))
So now, purely as a matter of visual syntax, but using "proj"
instead of get, now the apparent reversal of index order is gone.
In Felix terms, whether the index order is reversed visually or not
depends on whether you write:
(j,i) m <===> m . (j,i)
because by definition these have the same meaning: operator . means
reverse application.
The choice of order seems arbitrary. Actually it isn't quite arbitrary
because there seems only one sane way to write the type coercion:
(T ^ J) ^ I ==> T ^ (J * I)
BUT this is purely notational too. There is a forward syntax for exponentiation:
D -> C <====> C ^ D
which reverses the order. Felix gives these different meanings: the LHS
is function call and the RHS is array access, but conceptually these two
operations are the same. With that you will see that the index rule
above becomes:
I -> ( J -> T) <==> J * I -> T
You should note the "confusion" here: operator -> is RIGHT associative so
the LHS above could be written:
I -> J -> T
as well. Expressed this way you can see a confusion:
f i j <==> (f i) j ==> f (j,i)
because application is LEFT associative. It takes a minute to realise
why left associative application requires right associative
function type notation. But the shape changing rule here has
nothing to do with arrays! The ==> rule above is just called
uncurrying (and the reverse rule is called currying).
The problem here is that Felix currying/uncurrying does NOT
swap the order of arguments. From lib/std/categ.flx:
//$ change star into arrow (2 components)
fun curry[u,v,r] (f:u*v->r) : u -> v -> r => fun (x:u) (y:v) => f (x,y);
It seems kind of logical that
f x y == curry (f) (x,y)
But this is not what the index rule I cited above says.
Note that the method syntax is now changed to this:
(a i) j
which looks like "get" syntax -- except now the order
of the indicies has been swapped. This is because
we're using the array itself as the projection function.
The question is: if index i:I is applied first and j:J is
applied second (fastest moving) should the multi-index
be written (j,i) or (i,j).
If we follow the currying rule the answer is that the first
index is applied first and the second fastest moving
one second.
in other words there's an issue with consistency within
Felix here. Note again that:
(T ^ J) ^ I
the i:I index is applied first, the j:J index is fastest moving.
if we agree with the currying rule then
(T ^ J) ^ I ==> T ^ (I * J)
because the currying rule says the first applied index I
is written FIRST in the product.
The problem is the usual index rules disagree with this:
d ^ a ^ b == d ^ (a * b)
is what you see in kids maths books, eg you'd say
2 ^ 3 ^ 5 == 2 ^ (3 * 5)
or 15 bits.
So I'm now lost, which is the point. I actually didn't think
about the currying rule before. The choice of order is
really about notational conventions. Currying suggests one
thing, Fortran another. C doesn't HAVE 2D matrices so
there isn't a disparity between C and Fortran, the problem
is when you have a Fortran matrix the index order is
the visual opposite of the one you'd expect in C i.e.
F ( j, i) <==> f[i][j]
but that has nothing to do with the storage order of the matrices.
It has to do with the fact Fortran dictated a particular index rule
because the choice is arbitrary. If fortran has arrays of arrays then:
F (j,i) ==> F (i) (j)
i.e. the order would be the same as C because there's no choice.
Roughly: we have two different notations for the same thing
and ONE of them has to reverse the order when the index
rule is applied. I suspect the current currying rule actually
dictates Fortran order, i.e. the index order is swapped
(but I'm so confused now I can't tell :) :)
*************
We need to review notational conventions.
In Felix if you can write forward notation:
sin x
you can also write
x . sin
The effect is not just reversing the order of the function and argument.
If you can write:
sin (cos x)
you can also write:
x . cos . sin
so the function order is reversed. Considering a function of two arguments:
apply f a == (apply f) a
we can write that:
(f . apply) a
As Felix says that . is applied before whitespace this is also f . apply a.
[Just as you could write sin x.cos above]
And now a second transform:
a. (f . apply)
where the argument order is reversed, but now brackets are needed.
Note that both . and whitespace are left associative, So when you reverse
a notation with/without parens, you get one without/with parens :)
The type notation for application is:
f: A -> B -> C = f: A -> (B -> C)
which is right associative. So for apply:
apply: (A->B) -> (A -> B) == (A->B) -> A -> B
A similar case is map:
map: (A->B) -> list[A] -> list[B]
The important point with the notation is that although the argument
order appears reversed, this is not quite true: you need to throw
in parens to preserve the semantics.
Now, there's another notation for function types:
A -> B == B^A
Here the domain is written as the index of an exponential.
The value notation we use for this is as follows:
we use this exponential for arrays. So
double ^ 5
is a function:
5 -> double
which is an array of 5 doubles and we might write a value like:
a 2
or
2 . a
because we're applying an array as a function to index 2 to get the third
element
of the array, and the second notation drops out of the reverse application rule.
However there's another interpretation:
proj2 a == a. proj2
where proj2 is now a generic projection function for the second component
and is applied to the array. If we just write 2 instead of proj2 we get the
reverse notation from above:
2 a == a . 2
In both these cases there's a generic projection operator but they're distinct:
the first one models an array as a generic projection with an index parameter,
and the second one models the index as a generic projection taking
an array parameter.
a-as-p : double ^ 5 -> ( 5 -> double)
ix-as-p: 5 -> (double^5) -> double
We can allow both notations provided we don't allow arrays and indices
to get confused .. but this is precisely what DOES happen with multi-indices:
the index of a matrix is a pair of ints, which is an array of 2 ints.
So to rewrite generally:
a-as-p: V ^ I -> I -> V
ix-as-p: I -> V^I -> V
and we can only get confused if
V^ I = I
in other words the array type is the same as its own index type.
There are no such cases. However we have to be careful here
because, for example consider:
typedef uint32 = 2 ^ 32;
Now, uint32 is a bit array, but we also want it to be an integer and lo and
behold
in C we could sensibly index such an array with a unit32 :) This just shows
that "magic" conversions can lead to ambiguities.
The bottom line in all this: its CONFUSING!
The choice of index order in multi-indices is not as simple
as row major or column major!
Note even more confusion: We have been talking about the index rule:
double ^ 3 ^ 4 ==> double ^ ( 4 * 3)
or should that be 3 * 4??
But Felix compact linear types/polyadic array stuff goes much further
than this rule. It also implements the following index rule:
double ^ 3 * double ^ 4 ==> double ^ ( 3 + 4)
or should that be 4 + 3?? In case you don't understand
what that means, using a sum type as an index,
its actually very simple!! What is the type of this:
( ( 1.0, 2.0, 3.0), ( 4.0, 4.1, 4.2, 4.3) )
?? Duh! Its obviously:
double ^ 3 * double ^ 4
i.e. a tuple consisting of two arrays of different lengths.
And its completely obvious what the linear layout is:
(1,0, 2,0, 3.0, 4.0, 4.1, 4.2, 4.3)
And now its obvious what the index means too:
(a) first you pick which array to index
(b) if you picked the first one give an index in range 0-2 (type 3)
(c) if you picked the second one give an index in range 0-3 (type 4)
In fact Felix doesn't yet implement the lower level and more fundamental
isomorphism:
D * ( X + Y ) ==> D * X + D * Y
which is the distributive law. In fact I'm not sure if it implements the even
more fundamental laws:
(A * B) * C => A * ( B * C) => (A * B * C)
(A + B) + C => A + (B + C) => (A + B + C)
for example
type 2 * 3 is NOT equal to type 6
type 2 + 3 is NOT equal to type 5
These are isormorphic but not equal. The first law is evident in situations
like this:
(1,(2,3)) != ( (1,2), 3) != (1,2,3)
these tuples are isomorphic but not equal.
The IMPORTANT thing here is this: in Felix a "natural" coercion is a shape
change corresponding to any one of the isomorphisms AND FOR WHICH
THE UNDERLYING REPRESENTATION IS NOT CHANGED. This allows
the coercion to be converted to a reinterpret_cast in C++.
Other isomorphisms may require rebuilding a new structure. For example
(1,2) is isormophic to (2,1)
but you have to explicitly swap the components. This isn't true for records:
(a=1, b=2) is equal to (b=2, a=1)
because the representation is alphabetic order. Note that in Felix
some coercions are not natural: behind the scenes Felix may
do actual conversions. An example is the forgetful functor
(which is an epi-morphism not an isomorphism) applied to
record types:
(a=1, b=2) :>> (a:int)
This coercion builds a new record. This is a consequence of the fact
that in general "throwing out fields" of a record leads to a record
with a different layout. (This could also be handled by an array
of offsets, which requires a new offset array to be built, but leaves
the data intact: clearly this works fine if the record is immutable,
but as usual there's a sharing issue if we try to change something).
For tuples, a subtype consisting of the head of the tuple would
normally be a candidate for just casting a pointer to "forget"
the trailing fields.
In Felix this is NOT the case now we have compact linear types because
3 * 3 * double
has 3 fields in a C struct, but
3 * 3
is a compact linear type and is represented by a single integer.
Again the bottom line here is that the choice of notation and representations
really matter: the choice of index order in a multi-index is not quite as
arbitrary as it might seem. I just don't know the right choice :)
--
john skaller
skal...@users.sourceforge.net
http://felix-lang.org
------------------------------------------------------------------------------
LogMeIn Rescue: Anywhere, Anytime Remote support for IT. Free Trial
Remotely access PCs and mobile devices and provide instant support
Improve your efficiency, and focus on delivering more value-add services
Discover what IT Professionals Know. Rescue delivers
http://p.sf.net/sfu/logmein_12329d2d
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
