Ok, I seem to have compact linear types as values working
with the new formulation. Functional code should work.
The code is not (yet) optimised. I wanted to get it right first.
I have changed the "symbolic" representation by expanding the
existing C symbolic representation, which allows the special
compact linear type generators to interact directly with the
ordinary code (thus allowing recursion and arbitrary nesting depths).
There is a problem at the moment with pointers: you cannot have
a pointer to a component of a compact linear type. It's a bit, or
a trit, or something so we'd need a special representation
using "fat pointers".
It's not clear this can be done. The reason is: consider a pointer
to a bit. If the bit is inside a compact linear type we have a pointer
to the whole "int" storing the data plus some scaling factors.
However if the pointer is to a bit in a record, struct, or just
a non-compact tuple:
1,true,1 // type int * 2 * int
it's an ordinary pointer not a fat one. The point is that you cannot
tell which encoding to use: fat or skinny, from the type of the pointer.
We would have to use a new type, something like: pointer to a T inside
a U.
Therefore the program to get rid of assignment, and replace
a = b
with
(&a) <- b
universally cannot be achieved, at least not simply. So we have to
allow assignments to at least compact linear type components:
var x = true, false, true;
x . 1 = true;
Note this code does not work at the moment (it will, I just haven't handled
assignments with the new encoding scheme yet).
==================
So I want to explain that for a tuple you have to use a constant index:
(1,"hello",4.2) . 1
The index has to be a literal, so we know the type. Technically the index
is replaced by a projection function:
prj1 : int * string * double -> string
For arrays, the type is always the same, so an expression is allowed
for the index. This uses a different term
aprj: N -> T^N -> T
i.e. give me a value of type N (array length) and an array of length
N, and I'll give you the value in that slot.
NOW: Since we know we can have arrays:
T^N = T * T * T ... T // N times
and we can use an expression to fetch a value because all the components
are the same type .. what about the dual for sums?
N * T = T + T + T ... T // N times
We should be able to use an injection with an expression to select
the case number, since the argument of the constructor (injection)
is the same type for all cases.
However whilst for arrays T^N = T * T * .. * T by definition,
N * T
already has a meaning: its just a tuple consisting of an integer 0 .. N-1
together with a T value.
Now .. if you know anything at all about sum types .. this is PRECISELY the
representation use for all sums. In fact in Felix the general term is
struct _uctor_ { int variant; void *data; };
where data points at the T value, and variant is just the case number.
In special cases Felix uses a more compact representation.
However the point is, we have two functions
caseno (sum-typed-value)
argument (sum-typed-value)
which extract the case index and the argument respectively.
"caseno" reallyt exists in the concrete syntax, although the usual
use is internal when doing a match on a union type.
The argument function, however, is not normally exposed because the type
of the argument depends on the case. It is used in a match to cast the data
part of the _uctor_ to the type associated with the case being analysed.
So normally this function isn't safe to use. However there's a special case
where it is, namely, the one we've been discussing, where all the sum
components are the same type. For example using a union:
union U = | Fwd of int | Rev of int
there are two cases and both arguments have type int.
Now, if the sum REALLY were represented by an actual Felix tuple,
we could just write:
u . 0 // the case number
u . 1 // the case argument
and in particular, the isomorphism:
N * T = T + T + T ... T // N times
would be an equality. It would be interesting to try to make this
happen by simply *insisting* it has to be true, in other words,
add yet another compact representation for tuples of form
N * T
where N is a unitsum: the code for calculating these already exists
of course because it is already used to create such a representation
for union components, so it's just a matter of using those routines
in this special case.
There's just one problem .. if T is compact linear then so is N * T,
and the representation is *already* fixed. So the challenge then
is to look at the overlap cases, and get a suitably unified
representation, so the same encoding is used in both these cases.
This will add even more tricky encodings to Felix.
Note there's a very important issue behind all this.
A "generalised projection" exists for a tuple type:
gprj: 3 -> int * string * double -> int + string + double
This function is a projection that allows *expressions* even
for tuples, at the cost of having to return a sum type.
IN PARTICULAR:
gprj: 3 -> int * int * int -> int + int + int
in other words:
gprj: 3 -> int ^ 3 -> int + int + int
and it would be nice to have
gprj: 3 -> int ^ 3 -> 3 * int
NOW you can see that a generalised projection of an array returns
the input index as well as the array value.
If we iterate the array with this, we get (index, value) pairs.
This is important, because this is what we get for any other
associative store: for a dictionary we get (key, value) pairs.
What this shows is that most array iterators are wrong.
For example when you fold over an array, the function
should be the same as folding over a dictionary:
you should get the index as well as the value.
In particular you can now make "heterogenous" collections,
where the value type is really unified (homogenised) by a union
type. For example a tuple
int * string * double
can be turned into a list of type:
list[int + string + double]
and now you can use a list iterator. You get the position in the list
automatically since variant constructors always come with their
case numbers.
--
john skaller
skal...@users.sourceforge.net
http://felix-lang.org
------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance.
Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from
the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60133471&iu=/4140/ostg.clktrk
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
