On Sun, 2007-09-16 at 19:00 -0700, Erick Tryzelaar wrote:
> I put this up on trac in case anyone is interested.
> > I'm sure it'd be a lot of effort to pull this off, but it'd be interesting
> > if we could extend this to data structures so we could implement:
> >
> > {{{
> > union hlist[T with Show[T]] =
> > | HEmpty
> > | HCons of T * hlist[T]
> > ;
> > }}}
Not sure I understand:
/////////////////////////////
#import <flx.flxh>
union hlist[T with Show[T]] =
| HEmpty
| HCons of T * hlist[T]
;
var x= HEmpty[int];
println$ caseno x;
////////////////////////////
[EMAIL PROTECTED]:/work/felix/svn/felix/felix/trunk$ f ex
0
////////////////
you should note there is a 'bug' in typeclasses.
Typeclasses are ignored. Typeclasses are just like
C++ class templates specialisations (in Haskell too).
In Felix, the there is no typechecking at all.
What this means is that if you instantiate something
using say
Show[T] = Repr[T] + Str[T]
and you only use the str part of it .. it will work,
even if the type doesn't support Repr. All the checking
is done on use. This is the same as C++ class template
method specialisations.
This is not really what should happen.. there are routines
to do instance checking at binding time, but they're horribly
messy and don't work anyhow. Messy because they have to deal
with unbound symbols. Don't work because there's no way to
locate an instance without global analysis.
Although transfer of constraint as in:
fun f[T with X[T]] (x:T) => g x;
fun g[T with X[T] ..
CAN be checked after binding, that is, the call g x here
could be checked, as in Haskell, this is not enough.
If you 'open' a typeclass, say X[int], then a call
g 1
cannot be checked just against the calling function's encapsulated
typeclass .. you have to check against the opened typeclasses too.
This is the same as nested functions: the parent typeclasses are
available to children.
THAT IS: typeclasses come from two places, the current function
type parameters AND the enclosing context. The enclosing context
can contain instances, parameters usually only have constraints.
The thing is: to check
g 1
ignoring instances, the result is 'alway true' provided X typeclass
is defined at all .. and it must be or g couldn't be compiled.
This is true even inside a function. EG even if the constraint
X[T]
inside f is not enough to ensure
g (x,x)
works .. it doesn't need to be .. the call is still valid
if the 'instance'
open[T] X[T]
is specified. This is so hard to check. EG if you write:
typeclass X[T] ..
instance X[int]
fun g[T with X[T] ..
g 1;
what happens? Is the call disallowed because the constraint
wasn't propagated? Or do we take the instance as satisfying it?
If the latter .. well, it isn't possible to FIND all the instances
at type checking time, except by exhaustive searching.
Felix doesn't bother any more. It just checks individual methods
are instantiable. It only bugs out if you call a virtual which
is not instantiated. It fails to bug out if you do that but one
of the other required virtuals isn't instantiated.. if you don't
call it, no error.
This is not right, but it Felix isn't Haskell .. it's a global
analyser and it handles this the same way as C++: at global
analysis time (link time in C++) all methods have to be instantiated.
Note that type checking *recursive* instantiation is a real problem..
there's no problem instantiating them though.
There are two types of recursion: polymorphic recursion (not really
recursion!) and real recursion.
If you're Showing a list with Str, and you use a recursion which applies
Str on the tail after displaying the head then:
* the head display is merely polymorphic recursion
* the tail display is a real recursion
Note polymorphic recursion where the types agree is real recursion.
Polymorphic recursion is a bitch because it can diverge.. we have
a test where that happens. Felix doesn't have second order unification
so it can't detect this. Eg
str (x:T)=>str (x,x)
creates an infinite set of instances of str for t =
int
int * int
(int * int) * (int * int)
etc. The type diverges. Note, the *function* calls aren't not recursive,
its just that there is an infinite set of functions which call each
other in a chain.
What diverges .. is the Felix compiler. There's no easy way to detect
this because the polymorphic recursion doesn't have to be self,
there could be two mutually polymorphically recursive functions.
[BTW: Haskell does do second order unification and it does detect
this and bug out]
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2005.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
