Now I have unions appearing to work so that a union of
one constructor is replaced by its argument. Eg

        union X = | R of int

is replaced by int. This is still not fully efficient, since you still need
to use a match to extract the value:

        let R ?r = x in ...l

and the match still uses an if/then/else chain on the constructor index:
roughly like:

        r = if (index x == 0) arg x else goto match_fail ...

You may see C++ compiler warnings about constant conditional
expressions and dead code. Basically Felix does matches early
long before there is any lookup, so the pattern of handling unions
is established before any optimisation can be done. We require
other tricks later to recover.

So now, the BIG one. First, understand that a union like:

        union list = | Empty | Cons of int * list

is represented by a packed pointer:

        0 --> Empty
        1 + pointer --> Cons

In case 0, the low two bits are 00, and the rest of the pointer isn't used.
In case 1, the low two bits are 01 and have to be masked away before
the pointer to the list node is dereferenced. Also note we hope (fingers 
crossed)
that the garbage collector will handle the fake pointer: hopefully the
address *including the low two bits* will be interior to the list node object,
and the GC will then find the pointer to the whole object automagically.
[This will fail if we ever allocate something small such as a char size 1.
The allocator needs to round up to at least 4 to ensure this can't break
the collector .. however we're using malloc so the pointer will
always be aligned: the issue is to make sure the size is rounded
up in the interior pointer to head address calculation]

But now, we want a new representation:

        0 --> NULL
        other -> a real pointer

This is of course your usual C pointer. It's very similar to the VR_packed
representation *except* that the low two bits count this time. That's because
this kind of union is going to be grafted onto pointers created by C functions
outside Felix control. And they might well be pointers to chars, we can't
assume alignment here.

It's a fact this representation, call it VR_cptr is you like, could also work
for the list case, and is probably more efficient (no need for any masking).
VR_packed has the advantage it handles up to 4 constructors.
[In theory, you could add a char or int into it, however Felix doesn't know
how big an int is.]

The reason I want this VR_cptr to work is that I want to introduce a new
type:

        union cptr[T] = nullptr | Ptr of &T;

for C pointers, so then Felix pointers &T cannot be NULL ever,
and C pointers can't be dereferenced. More precisely, the
deref operation will always do a null check as part of the match
required to find the actual pointer to deref.

The notation is too ugly so I may use:

        @T

to mean a null or object pointer.

This means you use either @T or &T in interfaces to C libraries.
You use &T in a return type if you're sure C will return a non-null
pointer.

You use &T in an argument type if the function *requires* a non-null
pointer.

You use @T in a return type if C can return a null, and @T as an
argument if it's OK to pass a null.


You should note &T is a subtype of @T (it has one less value 
do its value set is a subset). This means that as argument would
be covariant, you can pass a &T safely where a @T is required,
and, since returns are contravariant, you can accept a @T where
a &T is returned.

However Felix currently has no real support for subtyping.
So we'll probably need to provide a nice way to do the safe
conversion. We do NOT want to use a cast, because that can 
break things. 

Note that the reverse, unsafe, conversion is possible if you're
prepared to terminate the program if you're wrong about the type:
effectively it would be a match failure.

The two types of pointers are essential for getting performance
AND safety together.

BTW:  yet to be sorted out: generally pointers should not be
incrementable. Only pointers into arrays. With varray, you don't
need to increment pointers, you can just use an index.
However you do need to increment if you want to use an STL
like generalisation, i.e. write algorithms which mutate objects.
In Felix this means passing a pointer. To mutate array and struct
members obviously you need to add offsets to pointers.

With structs this is safe. With arrays, it is only safe if 

(a) we know the array length
(b) we prove we're not going past the end

Of course (b) is most easily done by a run-time check.
This is easy for a varray or plain Felix array since the number or elements is 
known.
It's not so easy for a C array.

One way to fix this is to convert the C array to a varray. At the moment this
cannot be done: you can do the construction but it copies the elements,
it doesn't *acquire* the C array.
 
--
john skaller
skal...@users.sourceforge.net





------------------------------------------------------------------------------
Virtualization & Cloud Management Using Capacity Planning
Cloud computing makes use of virtualization - but cloud computing 
also focuses on allowing computing to be delivered as a service.
http://www.accelacomm.com/jaw/sfnl/114/51521223/
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language

Reply via email to