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 |
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 |
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. > 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 |
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 |
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 |
Free forum by Nabble | Edit this page |