I'm still struggling with this. Apart from the fact one piece of code
is reversing the order of indices compared to another and I can't
decide which is the right order, there's another internal issue in
the compiler. I want to explain this (mainly so I can understand it
myself :)
Felix has two tuple representations internally, roughly:
// type
BTYP_tuple of type list
// fetch component
BEXPR_get_n (tuple, index)
is the general form, where index originally had to be a constant integer.
That way:
get ( (1,"hell","1.3), 1)
has type string. An array is just a tuple, but the representation is different:
BTYP_array of type * index
where the index is a constant integer. This is the same as a tuple type
except that it allows 10,000 components without blowing the compiler
away.
However the get function for an array has to allow the index
to be an expression (or you cannot write a loop). This is cool,
because the type is always the same. Originally, the implementation
was a C binding, the compiler didn't know anything about it.
The two things changed. First, I added some array abstractions
in the form of a type class. So that the various dynamic length
arrays (varray, darray, sarray, dsarray etc etc) could all use
a common syntax and common set of algorithms applied to them
once the basics like "length" and "get" and maybe "set" were defined.
The subscript operation in the abstraction is quite nice.
It is like this:
index array
array . index
For example:
(1,2,3) . (i + 1)
is just reverse application for
(i + 1) (1,2,3)
and we define
apply: int * array -> basetype
to map the syntax onto an abstract get function.
Conceptually here we're treating an integer applied to an array
as a projection function. This is conceptually the same as a tuple,
except that for arrays the return type is the array base type....
And now the rot starts to set in. If an array is really a special case
of a tuple, the projection functions of both should be the same.
In Felix array is a subtype of tuple: it is not merely an morphism,
but an actual embedding.
It is possible to index a tuple with an expression:
projection: 3 * (int * string * double) -> int + string + double
is the correct signature for a tuple type int * string * double.
It's a sum type. You have to do a pattern match to extract
the value. Naturally. If the index is a constant, we know
what the sum component is, but its "just wrong" to use the
fact the index is a constant rather than a general expression
to change the type of the generic projection function.
I got away with this before. Now, with polyadic arrays entering
the picture I did a bit of a cheat.
If you index an array or tuple with an integer, you get the existing
rules. For a tuple not an array, a constant index. For an array
you can use an expression. Both return a value of the type
of the component and that type is known because of the restriction.
To get better behaviour, for arrays (only) I also allow indexing
an array of type 3 with a value of type 3. Such an operation
is safe (cannot exceed bounds). However to make that work
I extended
BEXPR_get_n (base, index)
to allow an index of a "compact linear type". The type 3
is a compact linear type. So is 3 * 4 * 5, which is the type
of a tuple.
So now, the compiler is checking that the index has the right
type. If it is a constant integer literal or a compact linear
type, it is cool and the *compiler* implements the array
lookup directly. It's not done in the library now.
If you use an integer expression its done in the library.
In fact it is done by checking the index and coercing
it to a compact linear type and then invoking the compiler
implementation!
But now we have two kinds of indices and one kind is
using "get_n" in the compiler and the other is using
"apply" in the compiler. The apply is getting invoked sometimes
for compact linear types, so my modelling of them now has
to deal with two representations.
To make this even more confusing, types like
3 * 4 + 6 * 6
are also compact linear types. So the index presentation
has tuple and sums in it and guess what:
3 * 3
is represent by an array, not a tuple.
So the code is a bit of a mess, especially as some special
cases are singled out for optimisation.
The real problem, however, is that the indexing formula is incorrect:
the right way to index an array should return a sum type which
is then "smashed" to get rid of the sum.
To complicate things even more I've been looking at:
T ^ N ^ M <=> T ^ (N * M)
but a more basic law is:
T + T + T + T + T <=> 5 * T
This just says a choice between 5 different T values can be represented
by an index 0 .. 4 of which value you chose, plus the value. It's important
because:
smash : 5 * T -> T
then throws out the index. (Felix has this operator, its called "case_arg" or
something, couldn't do pattern matching without it).
So unfortunately, simply "regularising" array operations is jumping the gun.
We need to smash the result of generic projection application, which
means we also need to be able to handle sums of the same type
the same we products of the same type become arrays.
--
john skaller
skal...@users.sourceforge.net
http://felix-lang.org
------------------------------------------------------------------------------
Master Visual Studio, SharePoint, SQL, ASP.NET, C# 2012, HTML5, CSS,
MVC, Windows 8 Apps, JavaScript and much more. Keep your skills current
with LearnDevNow - 3,200 step-by-step video tutorials by Microsoft
MVPs and experts. SALE $99.99 this month only -- learn more at:
http://p.sf.net/sfu/learnmore_122412
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
