[Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
OCaml has been getting a lot of mileage from its polymorphic variants (which allow structural subtyping on sum types) especially on problems relating to AST transformations and the infamous expression problem. Has there been any work on extending Haskell's type system with structural subtyping? What is the canonical solution to the expression problem in Haskell? What techniques do Haskellers use to simulate subtyping where it is appropriate? I bring this up because I have been working on a Scheme compiler in Haskell for fun, and something like polymorphic variants would be quite convinent to allow you to specify versions of the AST (input ast, after closure conversion, after CPS transform, etc.), but allow you to write functions that work generically over all the ASTs (getting the free vars, pretty printing, etc.). -- Alan Falloon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
Al, Has there been any work on extending Haskell's type system with structural subtyping? Koji Kagawaga. Polymorphic variants in Haskell. In Andres Loeh, editor, Proceedings of the 2006 ACM SIGPLAN Workshop on Haskell, Portland, Oregon, USA, September 17, 2006, pages 37--47. ACM Press, 2006. [1] What is the canonical solution to the expression problem in Haskell? Not canonical but Loeh and Hinze have proposed open data types: Andres Loeh and Ralf Hinze. Open data types and open functions. In Annalisa Bossi and Michael J. Maher, editors, Proceedings of the 8th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, July 10--12, 2006, Venice, Italy, pages 133--144. ACM Press, 2006. [2] Cheers, Stefan [1] http://portal.acm.org/citation.cfm? id=1159842.1159848coll=ACMdl=ACMtype=seriesidx=1159842part=Proceedi ngsWantType=Proceedingstitle=HaskellCFID=24140934CFTOKEN=52915302 [2] http://portal.acm.org/citation.cfm? id=1140335.1140352coll=ACMdl=ACMtype=seriesidx=1140335part=Proceedi ngsWantType=Proceedingstitle=International%20Conference%20on% 20Principles%20and%20Practice%20of%20Declarative% 20ProgrammingCFID=24141725CFTOKEN=61657761 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
I bring this up because I have been working on a Scheme compiler in Haskell for fun, and something like polymorphic variants would be quite convinent to allow you to specify versions of the AST (input ast, after closure conversion, after CPS transform, etc.), but allow you to write functions that work generically over all the ASTs (getting the free vars, pretty printing, etc.). Proper subtyping or at least extendable ADTs would be nicer, but you can have type-checked progress flags using phantom types, e.g.: data LT flag = L String (LT flag) | A (LT flag) (LT flag) | Var String data Input data Renamed data CPSed data ConstPropd rename :: LT Input - LT Renamed cps :: LT Renamed - LT CPSed constantPropagate :: LT CPSed - LT ConstPropd dumpExpr :: (forall a. LT a) - String -- ignores progress flag This way you have at least a way to check that the proper phases have been run before. It might even be possible to store different things in the nodes (not tested), like in: newtype Ident = MkIdent String class VarType flag vt | flag - vt instance VarType Input String instance VarType Renamed Ident instance VarType CPSed Ident instance VarType ConstPropd Ident data LT flag = (VarType flag vt = L vt (LT flag)) | ... (This probably doesn't work, but you get the idea.) / Thomas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
On Thursday 31 May 2007 15:36:13 Al Falloon wrote: I bring this up because I have been working on a Scheme compiler in Haskell for fun, and something like polymorphic variants would be quite convinent to allow you to specify versions of the AST (input ast, after closure conversion, after CPS transform, etc.), but allow you to write functions that work generically over all the ASTs (getting the free vars, pretty printing, etc.). Although this is the theoretical justification for OCaml's polymorphic variants, it is not their most common use. They are more commonly used to implement overlapping enumerations (see LablGL), to avoid sum type declarations with short scope (e.g. [`Some|`None| `Maybe] inside a single function) and when sum types keep changing during development. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
Mark T.B. Carroll wrote:
I don't know what the infamous expression problem is, nor am I
familiar with polymorphic variants or structural subtyping, but have you
looked at the Data.Generics.* stuff and Scrap Your Boilerplate papers?
They may be relevant.
The expression problem is a new name for an old problem, basically
being able to extend a data type and functions over the data type in
seperate modules with no knowledge of each other. Here is a link to (I
think) the original description:
http://www.daimi.au.dk/~madst/tool/papers/expression.txt
Structural subtyping is something like duck typing in dynamic
languages, but checked at compile time. For records, it means that if
you only access two labels then the function will work on any record
that has those labels with those types, even if it may have more labels.
For variants (or sum-types, or tagged unions, or whatever they are
called in Haskell) it means that if your function can handle certain
cases, then it can also handle values that range over less cases. So in
pseudo-Haskell with imaginary subtyping:
data Vertical a = U a | D a
data Horizontal a = L a | R a
data Direction a = #Vertical a | #Horizontal a -- borrowing ocaml
syntax: this means that Direction shares constructors with Vertical and
Horizontal
getData :: Direction a - a
getData (U a) = a
getData (D a) = a
getData (L a) = a
getData (R a) = a
getLeftStick :: IO (Vertical Int)
getRightStick :: IO (Horizontal Int)
main = do { accel - getLeftStick; print (getData accel) }
So getData doesn't care that accel is Horizontal and not Direction
because Horizontal is a sub-type of direction. Of course, in this syntax
since you named the subtyping relationship its more technically nominal
subtyping (like in traditional static OO languages) not structural
subtyping (which figures out the subtype relationship from the structure
automatically, so if we just reused the U,D,L, and R constructors in
Direction).
I have looked into SYB briefly. I will probably end up using it to keep
the amount of code to a minimum, but it won't save me from having to
define a different data type for each version of the AST if I want to
preserve type safety.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
On Thursday 31 May 2007, Al Falloon wrote: OCaml has been getting a lot of mileage from its polymorphic variants (which allow structural subtyping on sum types) especially on problems relating to AST transformations and the infamous expression problem. Has there been any work on extending Haskell's type system with structural subtyping? What is the canonical solution to the expression problem in Haskell? What techniques do Haskellers use to simulate subtyping where it is appropriate? I bring this up because I have been working on a Scheme compiler in Haskell for fun, and something like polymorphic variants would be quite convinent to allow you to specify versions of the AST (input ast, after closure conversion, after CPS transform, etc.), but allow you to write functions that work generically over all the ASTs (getting the free vars, pretty printing, etc.). I'm not sure if it qualifies (as, I don't know OCaml), but you might want to look into some of the papers proposing extensible record systems for Haskell. Some of them note that the same type system extensions for records can be used for variants. Specifically, Daan Leijen's paper Extensible records with scoped labels goes into how they might work, although there may be other good papers on the subject. Would such a proposal be comparable to what OCaml has? Unfortunately, I don't think implementing such a proposal is high on the to-do list for any of the compilers currently. There's too little time in the day to build all the type system fanciness everyone could want, I guess. :) -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
stefan: Al, Has there been any work on extending Haskell's type system with structural subtyping? Koji Kagawaga. Polymorphic variants in Haskell. In Andres Loeh, editor, Proceedings of the 2006 ACM SIGPLAN Workshop on Haskell, Portland, Oregon, USA, September 17, 2006, pages 37--47. ACM Press, 2006. [1] What is the canonical solution to the expression problem in Haskell? Not canonical but Loeh and Hinze have proposed open data types: For a short term solution, we used Typeable + type classes to provide a open Message data type. Similar techniques are used in Simon Marlow's extensible exceptions paper. -- An open Message type class Typeable a = Message a -- -- A wrapped value of some type in the Message class. -- data SomeMessage = forall a. Message a = SomeMessage a -- -- And now, unwrap a given, unknown Message type, performing a (dynamic) -- type check on the result. -- fromMessage :: Message m = SomeMessage - Maybe m fromMessage (SomeMessage m) = cast m -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
