Me being the main dummy .. :)
Suppose we have a 10 x 10 x 10 matrix.
Suppose we have indices h, t, u.
I will explain why those letters are chosen in a second.
Then the matrix is really consecutive elements, and the formula
for finding an element is:
h * 100 + t * 10 + u
Now you see the meaning of the letters :)
When we're indexing an array of arrays of arrays the order is like this:
X . h . t . u
First, we make a big jump to select a 2D submatrix, then a medium
sized jump, to select a vector, then we select an element of the
vector. This order is fixed by the idea we have an array of arrays
of arrays, so the first mentioned array, the outermost, is the biggest
and has the biggest elements.
Now, let's decide we want to convert the array of arrays of arrays
to a single linear array, without moving anything about: in other
words we're just going to use a reinterpret cast.
To compensate, we have to use a new kind of index. If we flatten
the array structure we have to structuralise the index:
(h, t, u)
is our new index. It's a tuple! But arrays cannot be indexed by tuples
so we have to "convert" the tuple to an integer:
index = h * 100 + t * 10 + u
This kind of index is sometimes called a multi-index.
Now, the order of writing above is called BIG ENDIAN.
Because the highest order sub-index comes first.
So what is a compact linear type? In the first instance its
just a tuple of subranges of integers which is represented
by a single integer.
To decode a compact linear type is easy:
h = htu / 100 % 10
t = htu / 10 % 10
u = htu / 1 % 10
Obviously the divide by 1 is pointless in the last case, and clearly
the modulo by 10 is not required in the first case (assuming we
initialised the integer value: if we did component wise assignments
to an uninitialised value we need it).
The formula for assignment is a bit tricker!
You should note, division here is exactly the same as a right shift
if the base is a power of two. And, modulo is nothing more than a mask.
Well now you get the idea consider a 3 x 4 x 5 matrix.
It's all the same: the compact linear type 3 * 4 * 5 is packed into
an integer with multiply and add, and extracted with divide and modulo.
The compact linear representation is just a number system,
only now we have a different base in each digit slot.
if we call the indices:
d: 3 // german, drei = 3
v: 4 // german, vier = 4
f: 5 // german, funf = 5
then the encoding formula is:
(d,v,t) = d * 4 * 5 + v + 5 + t
which fixes the matrix representation by assuming tuples are BIG ENDIAN:
M . d. v . t
The type of this matrix is then
T ^ 5 ^ 4 ^ 3
Remember the righthand most index moves fastest in BIG ENDIAN.
So the *innermost* array is a vector of length 5.
The linear matrix we obtain is of type
T ^ (3 * 4 * 5)
which reverses the order. To preserve the order we have to use a LITTLE ENDIAN
representation. That makes the first index in the tuple move fastest.
Note compact means "no holes" and "linear" means in line.
Compact linear tuple representation uses minimum storage guaranteed,
however the components are not addressable with a simple address.
The big advantage that if you coerce an array of arrays ... of arrays
to a linear array with a compact linear type for an index, you can
fold or accumulate over it with a single loop, but using the index
as an integer. It's independent of the array rank, because you cast
that out of the array and into the index, but the information isn't
required for a fold. It's also efficient! No need to extract the
indices and calculate positions: the compact representation
is already the linear index.
There's more! Compact linear types don't just work on tuples
of subranges of integers.
They also work on tuples of tuples. And tuple of tuples of tuples.
It's just recursion. Its a number system, where some of the
"digits" are themselves numbers with a number system.
And compact linear types work for sums too, not just products.
Consider this:
( (1,2,3), (4,5) )
This is a tuple of two arrays. Its type is
int ^ 3 * int ^ 2
But wait! We know this is just 5 integers in a row!
So we do the same as we did for products, we cast
the array to linear and we get:
int ^ ( 3 + 2)
What's that mean? Well it means:
1) The + means: you have two choices, the first array or the second
array
Pick one.
2) If you chose the first array, give an index in 3
If you chose the second array give an index in 2
The formula is obviously:
choice ? index : 3 + index
I won't go on with this one, but the bottom line here is: a compact linear
types is:
0
1
the n-ary sum or product of any compact linear type (n>=2)
For example:
(1,2,3 (4, (6,7),8,(9,10)),11)
is an array of integers.
--
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
