Ok, typeclasses are up to the critical point. The data flow works
up to overload resolution now.
Here's the problem. At present Felix uses something like a list
of hastables for lookup. The tables go:
string -> int
The result of a lookup is roughly
int, ts
where ts is a list of types. This list represents a type substitution
as follows: when we lookup the integer key in the symbol table,
we get a list of type variables used as universal quantifiers.
For example
fun f[t,u] (x:t, y:u) => ...
Here function f is entry 1234 in the symbol table, and the
symbol record contains the list
t,u
The ts list might be
int, float
which makes a binding:
t-> int, u-> float
This is encoded directly into the generated intermediate
language with an Ocaml combinator such as
`BEXPR_closure (1234,[int_term;float_term])
The instantiator tracks that
i, [int;float]
is required, and generates an instantiation j
(i,[int;float]) -> j
stored in another hashtable. This is used to (a) uniquely
number the C++ class which will be generated, (b) ensure
instantiations are unique, and (c) ensure unused combinations
do NOT get instantiated.
Now, if we 'add' the scope of a typeclass into the environment,
everything will work very well.
The problem is it will work TOO well. It will bind function
calls by specialising the type variables of the typeclass
separately on EVERY call.
What we ACTUALLY need to do is: specialise the typeclass
based on the types supplied in the function in the
where clause, so the type variables are all expressed
in terms of the functions own type variable list,
which also 'marks' then as independent, rather than
dependent variables, so they can NOT be solved for
in unification/matching: for the purpose of lookups
in the function body the type variables are argumentless
constructors(constants).
For example here:
typeclass X[u,v] { fun add: u * v -> u; }
fun f[s,t where X[s,t]] (x:s,y:t) { .. add(x,y) .. }
we need to inject X[s,t] into scope, that is:
fun add: s * t -> s
The lookup of add(x,y) will search for
add: s * t
and find it, with an exact match (in this case).
[If the typeclass itself, or the candidate function,
is parametrically polymorphic THAT type variable
will be bound however.]
The problem here is exactly equivalent to this:
open X[s,t];
were X a module: we want to open an *instance* of X
for lookup, for which u,v are replaced by the arguments s,t.
I tried to implement this before and failed.
I want to be very clear what the problem is: the Felix lookup
routines expect a symbol table entry with a list of type
variable names, meta-variable 'vs', and it uses a match
of the function signature, expressed in these variables,
against the actual call signature, to find a most general
unifier, using unification, with a constraint on the unification
algorithm it is only permitted to find substitutions for the vs.
[In other words, 'solves these equations for a specified set
of dependent variables, the RHS containing independent variables]
The problem is we have to have
add: s * t -> s
in the symbol table .. where s and t are NOT type variables ..
with a unique number for its index .. we will get that
number back from lookup.
The ONLY way to do this is to create a completely new symbol table
which contains the specialised version of the typeclass,
and after lookup, arrange to replace the fresh indices so created
with a binding to the original it was specialised from,
together with replacing the returned substition S with
a composite:
S . S'
where S' is the substitution on the typeclass variables,
in the example:
S' = t,u -> r,s
S = identity
Having done that we can now throw away the temporary symbol
table and name mapping, we have a binding to a function
in the typeclass now.
We have to do all this, to ensure the bindings all
go to the one typeclass instance X[s,t] specified
in the function.
This is extremely hard to do efficiently, in fact,
it is extremely hard to do it at all. The reason is that
the temporaries we're creating here are UNBOUND, that is,
all the names in them are just strings.
The PROBLEM is alpha-conversion. We can't just substitute
the names of the type variables in the functions in,
because they're not meaningful in the typeclass environment,
the names must actually refer to the calling environment.
This *would* be easy to do if lookup used already bound
(alpha-converted, lookup'ed) forms, but it doesn't :)
--
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
