Constructor classes implementation

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Constructor classes implementation

Sean Seefried-2
Hey all,

If you're interested in an implementation of constructor classes  
(type classes which can take constructors as arguments; already  
implemented in Haskell) please see:

http://www.cse.unsw.edu.au/~sseefried/code.html

This should help understanding the paper by Mark P. Jones called "A  
system of constructor classes: overloading and implicit higher-order  
polymorphism" much easier.

The implementation not only infers the type but also prints out a  
trace of the derivation tree for the syntax directed rules.

Cheers,

Sean

p.s. If you find any bugs, please let me know.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Constructor classes implementation

Daniel Fischer-4
Am Freitag, 17. Februar 2006 03:34 schrieb Sean Seefried:

> Hey all,
>
> If you're interested in an implementation of constructor classes
> (type classes which can take constructors as arguments; already
> implemented in Haskell) please see:
>
> http://www.cse.unsw.edu.au/~sseefried/code.html
>
> This should help understanding the paper by Mark P. Jones called "A
> system of constructor classes: overloading and implicit higher-order
> polymorphism" much easier.
>
> The implementation not only infers the type but also prints out a
> trace of the derivation tree for the syntax directed rules.
>
> Cheers,
>
> Sean
>
> p.s. If you find any bugs, please let me know.

Re bugs:

1. printGamma [] would print an unmotivated " }", as witnessed by
typeInf [] term14.

2. the case
unify (ConT c) (AppT t1 t2)
is missing.

3. too many shadowed bindings, this is always dangerous, I believe

4. I'm not sure, the datatypes are appropriate; as far as I know, expressions
have a type and not a kind, which is what the use of the same Var type for
Type and Exp entails.

I have only just glimpsed at Jones' paper, so I don't yet see, what this type
inference algorithm (quite nice, btw) has to do with constructor classes. If
I still don't after reading it, I'll come back to ask.

Cheers,
Daniel

--

"In My Egotistical Opinion, most people's C programs should be
indented six feet downward and covered with dirt."
        -- Blair P. Houghton

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Constructor classes implementation

Daniel Fischer-4
Am Montag, 20. Februar 2006 13:35 schrieb Daniel Fischer:

> >
> > Cheers,
> >
> > Sean
> >
> > p.s. If you find any bugs, please let me know.
>
> Re bugs:
>
> 1. printGamma [] would print an unmotivated " }", as witnessed by
> typeInf [] term14.
>
> 2. the case
> unify (ConT c) (AppT t1 t2)
> is missing.
>
and unifying a tyvar with itself fails. That probably doesn't occur in the
inference-algorithm, but still...

> 3. too many shadowed bindings, this is always dangerous, I believe
>
> 4. I'm not sure, the datatypes are appropriate; as far as I know,
> expressions have a type and not a kind, which is what the use of the same
> Var type for Type and Exp entails.

and that led to an error: in generalise, we are interested in the free
constructor-variables in the environment, not the term-variables, hence
-- Free variables in ...
-- ... schemes
fv_scheme :: Scheme -> [Var]
fv_scheme (Scheme vs ps ty)
     = nub (fv_preds ps ++ fv ty) \\ vs

-- ... environments
fv_gamma :: Gamma -> [Var]
fv_gamma gamma = nub (concatMap (fv_scheme . snd) gamma)

and not
fv_gamma gamma = nub (map fst gamma)

>
> I have only just glimpsed at Jones' paper, so I don't yet see, what this
> type inference algorithm (quite nice, btw) has to do with constructor
> classes. If I still don't after reading it, I'll come back to ask.
>
I still don't see clearly. So you've implemented the type inference algorithm
from Jones' paper, good. But is there any significance or gain, apart from it
being a nice and interesting exercise?

Cheers,
Daniel

--

"In My Egotistical Opinion, most people's C programs should be
indented six feet downward and covered with dirt."
        -- Blair P. Houghton

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Constructor classes implementation

Sean Seefried-2
Thank you for taking the time to look through the code.

>> 1. printGamma [] would print an unmotivated " }", as witnessed by
>> typeInf [] term14.
>>
>> 2. the case
>> unify (ConT c) (AppT t1 t2)
>> is missing.
>>
>
> and unifying a tyvar with itself fails. That probably doesn't occur  
> in the
> inference-algorithm, but still...
>

And that case is in the paper, so I should have implemented it.  I  
have now.

>> 3. too many shadowed bindings, this is always dangerous, I believe
>>
>> 4. I'm not sure, the datatypes are appropriate; as far as I know,
>> expressions have a type and not a kind, which is what the use of  
>> the same
>> Var type for Type and Exp entails.
>

Thank you. This was a glaring mistake in the code and it has been  
fixed.  Type variables are the only ones that have kinds now. I have  
used your definition of fv_gamma too.

> and that led to an error: in generalise, we are interested in the free
> constructor-variables in the environment, not the term-variables,  
> hence
> -- Free variables in ...
> -- ... schemes
> fv_scheme :: Scheme -> [Var]
> fv_scheme (Scheme vs ps ty)
>      = nub (fv_preds ps ++ fv ty) \\ vs
>
> -- ... environments
> fv_gamma :: Gamma -> [Var]
> fv_gamma gamma = nub (concatMap (fv_scheme . snd) gamma)
>
> and not
> fv_gamma gamma = nub (map fst gamma)
>
>>
>> I have only just glimpsed at Jones' paper, so I don't yet see,  
>> what this
>> type inference algorithm (quite nice, btw) has to do with constructor
>> classes. If I still don't after reading it, I'll come back to ask.
>>
> I still don't see clearly. So you've implemented the type inference  
> algorithm
> from Jones' paper, good. But is there any significance or gain,  
> apart from it
> being a nice and interesting exercise?

No. Nor did I state that there was.  There's a reason I posted this  
to Haskell-cafe and not Haskell.  I just thought the code might be  
useful for other people who were similarly trying to understand how  
constructor classes are implemented.  The only other code I found  
(that wasn't inside a compiler) was that associated with the "Typing  
Haskell in Haskell" paper.  The nice thing about the algorithm in "A  
system of constructor classes: ..." is that it is small and to-the-
point.

Cheers,

Sean
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Constructor classes implementation

Donald Bruce Stewart
sean.seefried:

> >>
> >I still don't see clearly. So you've implemented the type inference
> >algorithm from Jones' paper, good. But is there any significance or
> >gain,  apart from it being a nice and interesting exercise?
>
> No. Nor did I state that there was.  There's a reason I posted this  
> to Haskell-cafe and not Haskell.  I just thought the code might be  
> useful for other people who were similarly trying to understand how  
> constructor classes are implemented.  The only other code I found  
> (that wasn't inside a compiler) was that associated with the "Typing  
> Haskell in Haskell" paper.  The nice thing about the algorithm in "A  
> system of constructor classes: ..." is that it is small and to-the-
> point.

Seems like useful code to me. The more the merrier  :)

-- Don
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe