On Fri, 2006-09-08 at 10:53 -0400, Peter Tanski wrote:
> On Sep 8, 2006, at 6:58 AM, skaller wrote:
> As I understand it, the 'covariance' problem comes up when you have
> the inheriting methods or types may override methods of superclass
> they inherit from. This is not a problem with type classes because
> you cannot override the rules inherited from the class.
That makes it every worse of a problem :)
> > Eq and Ord are 'subkinds' of *, it's a subset of the types of
> > all the types, which admit equality and ordering, respectively.
>
> They are not "subkinds," they are simply any kind ( 'a' roughly
> equals *), for which certain function signatures have been defined;
> there is no effect on the nature of the underlying type except
> restrictions over which functions may be applied.
If I say:
instance Ord int where ..
I'm saying int is ordered. Not all types are ordered.
Only a subset of * is able to support Ord: Ord is that
subset .. it's a subkind. In particular, Ord is a subkind
of Eq, for example function types are not in Eq so they
cannot be in Ord.
But enough of this for the moment: the question is how
to implement typeclasses in Felix!
My idea is .. we already HAVE a lame form of them:
module Int[t] {
fun add: t * t -> t = "$1+$2";
..
}
For C bindings, it is often that the function 'defaults' are
enough because they're polymorphic.
At the moment, the above not only works, but it is possible
(I think :) to constrain the set t can take on with a constraint:
module Int[t:fast_ints] { .. }
where fast_ints is the set of C integer types. This is a
hack, because you'd have to modify the set 'fast_ints'
to add new cases. There's another hack: the constraint
can only be a finite typeset.
So one might consider starting with
typeclass Int[T] = {
fun add: t * t -> t = "$1+$2";
virtual sub: t * t -> t; // must be overridden
..
}
and allowing
module Short = Int[short] with ...
The implementation technique seems simple: copy the typeclass,
specialising t and replacing overridden routines.
Unfortunately .. this can't work. The reason is: Felix does not
bind (lookup, alpha-conversion) sequentially. Which means the
instantiation might require binding *before* the typeclass.
This requires the typeclass be 'recursively' bound, without
it being entered in the symbol table -- in fact since
the typeclass is just syntactic sugar it never gets into
the bound symbol table.
This issue arises in other places. For example, you can
use a variant constructor before it is bound:
union u = U of int;
fun f(a:u)=> match a with | U ...
Assume here f is being bound first, then all the calculations
regarding u and U have to be done without the 'union u'
definition being entered into the bound symbol table.
What is fixed is that u and U have unique identifiers
(integers), however the type of the argument 'int' is not
known, it is still literally a string "int" at this point.
As you can imagine this makes overload resolution tricky,
since it has to be done entirely on the unbound symbol table.
This is why lookup takes 60% of all compile time :)
Anyhow the point is that this can work if, and only if,
'binding on the fly' is invariant, that is, it always gives
the same results no matter when it is done. In particular
it cannot introduce any fresh variables (except for binders
and variables they bind of course).
Instantiation of a typeclass actually seems to require
doing that if it instantiation is implemented by literally copying
and specialising the default methods .. if this were done a second
time, it would assign fresh integers to the functions as identifiers.
To solve this, I tried to make the lookup a view: that is,
when you lookup
Int[short]::add
you first find:
add:t * t -> t
and you couple that with the substitution
t -> short
and return that. The effective signature is then
add: short-> short
but add is still the original default method. In other words,
lookup of functions, which current returns a list:
293, 3484, 4735, 666
which are indices into the symbol table (both bound and unbound),
would have instead to return a list whose entries were a base
function index PLUS a chain of substitutions.
Then, for overloading, the type is that of the base function
type specialised by applying all the substitutions.
The point being, in this form, lookup will always return the
same result.
After a weeks work, and finding hundreds of points in the
code that needed to account for the changed data structure,
I still couldn't make it work: not only did just about every
function in the lookup code need changing, the effects propagated
into other data structures.
I tried to make this work twice. Several years ago Felix also
had Ocaml style functors .. and I chucked them for the same
reason: I couldn't make it work. It's really hard taking
on a difficult algorithm based on an idea that mightn't
even be sound .. and not having colleagues to bounce the
ideas off. Perhaps now it can be done: Erick is actually
an Ocaml programmer, as is Jacques, and both Peter and Jacques
know some actual theory.
There are many related issues: the way I handled type constraints
is pretty lame. Even the existing unification engine can
handle more general kinds of constraints than finite sets.
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
Felix-language mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/felix-language
