Data representation, maybe reflection, laziness
People have been talking about transmitting Haskell values on the GHC users' list, and I wanted to ask some more general stuff, partly out of mild ignorance. Ralf Hinze and Simon Peyton-Jones wrote an interesting paper on generic programming and derivable type classes. It looked like maybe programmers would be able to write their own "deriving xml" stuff and whatever, which looked great because, if there's not already one out there, I'd love to derive some read/show analogue automatically for data in some encoding that's very efficient to write and parse (i.e. not XML (-:). I was also wondering how the ability to write "deriving" stuff related to what one might think of as being reflection - that is, for example, could a definition of deepSeq be derived that automatically knows how to recurse into and traverse data structures and make sure everything's evaluated? This leads me to the point that little of the code I write needs laziness, but many of my unpleasant performance surprises come from laziness. I do find it hard to figure out where to put strictness annotations to actually make things work - for instance, I think it's laziness things that are causing my uses of Control.Exception.evaluate to actually work more by trial and error. No doubt it'll all grow clearer in time. Maybe I need "laziness annotations" instead. (-: Still, I was wondering what current thinking and directions were with regard to any of the above! -- Mark
On Fri, Oct 31, 2003 at 03:06:57PM -0500, Mark Carroll wrote:
Ralf Hinze and Simon Peyton-Jones wrote an interesting paper on generic programming and derivable type classes. It looked like maybe programmers would be able to write their own "deriving xml" stuff and whatever, which looked great because, if there's not already one out there, I'd love to derive some read/show analogue automatically for data in some encoding that's very efficient to write and parse (i.e. not XML (-:).
I was also wondering how the ability to write "deriving" stuff related to what one might think of as being reflection - that is, for example, could a definition of deepSeq be derived that automatically knows how to recurse into and traverse data structures and make sure everything's evaluated?
DrIFT can do this. add {-! derive: NFData !-} to your types and run the program through DrIFT then 'rnf' will reduce it to to normal form. template haskell also (among other things) lets you do your own 'deriving' clauses. Something I have been meaning to work on is having DrIFT understand the same data types as TH, so code can be shared between them much more easily... here is a list of derivables DrIFT currently supports. more are always welcome :). Binary: Binary efficient binary encoding of terms Debugging: Observable HOOD observable General: NFData provides 'rnf' to reduce to normal form (deepSeq) Typeable derive Typeable for Dynamic Generics: HFoldable Strafunski hfoldr Term Strafunski representation via Dynamic Prelude: Bounded Enum Eq Ord Read Show Representation: ATermConvertible encode terms in the ATerm format Haskell2Xml encode terms as XML Utility: has hasfoo for record types is provides isFoo for each constructor test output raw data for testing un provides unFoo for unary constructors update for label 'foo' provides 'foo_u' to update it -- --------------------------------------------------------------------------- John Meacham - California Institute of Technology, Alum. - john@foo.net ---------------------------------------------------------------------------
Hi Mark, The boilerplate style of generic programming [1] should be of help here. For example, here you can see how to do a normal read and show: http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/libraries/base/Data/Generi... We are also using this style to do decode and encode (think of bit streams), or to read and show XML (just working on this as we speak). Data.Generics allows you to obtain access to constructors and type information, which is crucial for versatile read/show functionality. The rather inductive style underlying "derivable type classes", which you mentioned, does not provide such access, but could probably be extended to do so. You will also find a preliminary module Data.Generics.Reify at [1] that illustrates indeed that there is some link to reflection if you like this view. One of the applications that really requires getting a handle on type information is test-set generation. Regards, Ralf [1] http://www.cs.vu.nl/boilerplate/ (The code base shown here is as of GHC 6.2, but a simple version of Data.Generics was shipped with GHC 6.0.) Mark Carroll wrote:
People have been talking about transmitting Haskell values on the GHC users' list, and I wanted to ask some more general stuff, partly out of mild ignorance.
Ralf Hinze and Simon Peyton-Jones wrote an interesting paper on generic programming and derivable type classes. It looked like maybe programmers would be able to write their own "deriving xml" stuff and whatever, which looked great because, if there's not already one out there, I'd love to derive some read/show analogue automatically for data in some encoding that's very efficient to write and parse (i.e. not XML (-:).
I was also wondering how the ability to write "deriving" stuff related to what one might think of as being reflection - that is, for example, could a definition of deepSeq be derived that automatically knows how to recurse into and traverse data structures and make sure everything's evaluated?
This leads me to the point that little of the code I write needs laziness, but many of my unpleasant performance surprises come from laziness. I do find it hard to figure out where to put strictness annotations to actually make things work - for instance, I think it's laziness things that are causing my uses of Control.Exception.evaluate to actually work more by trial and error. No doubt it'll all grow clearer in time. Maybe I need "laziness annotations" instead. (-:
Still, I was wondering what current thinking and directions were with regard to any of the above!
-- Mark _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On vrijdag, okt 31, 2003, at 21:06 Europe/Amsterdam, Mark Carroll wrote:
Ralf Hinze and Simon Peyton-Jones wrote an interesting paper on generic programming and derivable type classes. It looked like maybe programmers would be able to write their own "deriving xml" stuff and whatever, which looked great because, if there's not already one out there, I'd love to derive some read/show analogue automatically for data in some encoding that's very efficient to write and parse (i.e. not XML (-:).
Johan Jeuring and I submitted a paper [1] to PLAN-X concerning this topic. In an earlier paper [2] we described a Haskell-XML data binding, that is, a type-safe translation scheme from (a sizeable subset of) XML Schema to Haskell. In [1] we describe a Generic Haskell program which automatically infers certain coercions between the translation of an XML Schema type, which is very large and ugly, and user-defined Haskell datatype capable of representing values of the Schema type. The idea is to infer the function that transforms values of the ugly type picked by the translator to values of a traditional, Haskellish datatype picked by the user. For example, our translator takes the Schema type doc (representing a bibliographic entry): <element name="doc" type="docType"/> <complexType name="docType"> <sequence> <element ref="author" minOccurs="0" maxOccurs="unbounded"/> <element ref="title"/> <element ref="pubDate" minOccurs="0"/> </sequence> <attribute name="key" type="string"/> </complexType> <element name="author" type="string"/> <element name="title" type="string"/> <complexType name="pubDateType"> <sequence> <element ref="year"/> <element ref="month"/> </sequence> </complexType> <element name="pubDate" type="pubDateType"/> <element name="year" type="int"/> <element name="month" type="int"/> to a certain ugly datatype X. [2] defines generic functions: parse{|t|} :: String -> Maybe t unparse{|t|} :: t -> Maybe String (Well, we only describe parse, but unparse is very easy...) Now say the user defines the following datatype in some module:
data Doc = Doc { key :: String, authors :: [String], title :: String, pubDate :: Maybe PubDate }
data PubDate= PubDate { year :: Integer, month :: Integer }
This is, IMO, the `ideal' translation of the Schema type. Now, although X /= Doc, there is in fact a `canonical' injection X -> Doc, determined by the types alone, which happens to do what one wants. In [1] we define generic functions: reduce{|t|} :: t -> Univ expand{|t|} :: Univ -> t where Univ is a universal type which you don't need to know anything about. The program
expand{|T|} . reduce{|S|} :: S -> T
denotes the canonical function, which is inferred generically by inspecting the types S and T, relieving the user of the burden of writing it out themselves. So now, say you want to write a GH program which reads in a document conforming to the Schema type `doc' from standard input, deletes all authors named "Dubya", and writes the result to standard output. Here it is: < main = interact work < toE_doc = unparse{|E_doc|} . expand{|E_doc|} . < reduce{|Doc|} < toDoc = expand{|Doc|} . reduce{|E_doc|} . < parse{|E_doc|} < work = toE_doc . < (\d -> d { authors = < filter (/= "Dubya") (authors d) }) . < toDoc And that's it. All the messy stuff is inferred by GH and the translator. OK, now the reason that I prepended this message with "FWIW": although we have an implementation of the translator and coercion inferencer, they're only prototypes and far from usable in practice. In fact, the translator doesn't read XML at all but rather operates on XML abstract syntax (a tree datatype). Frankly, I don't think I will take the time to turn the prototype into anything releasable, but I wouldn't mind turning over the sources (such as they are :) to someone who has a serious interest. Take a look at the papers and see if it appeals to you. Regards, Frank [1] @TechReport{ACJ03c, author = {Atanassow, Frank and Clarke, Dave and Jeuring, Johan}, title = {Scripting {XML} with {G}eneric {H}askell}, institution = {Utrecht University}, year = {2003}, url = {ftp://ftp.cs.uu.nl/pub/RUU/CS/techreps/CS-2003/2003-023.pdf}, number = "UU-CS-2003" } [2] @misc{AJ03, author = {Frank Atanassow and Johan Jeuring}, title = {Type isomorphisms simplify {XML} programming}, year = 2003, note = {Submitted to PLAN-X 2004}, url = {http://www.cs.uu.nl/~franka/pub}, urlpdf = {http://www.cs.uu.nl/~franka/planx04.pdf}, pubcat = {journal}, }
On dinsdag, nov 4, 2003, at 00:39 Europe/Amsterdam, Frank Atanassow wrote:
For example, our translator takes the Schema type doc (representing a bibliographic entry) ... to a certain ugly datatype X.
Oops. For "X" I should have written E_doc, that is, the translation of Schema type "doc" is named "E_doc" ("E" is for Element); it's used in the example at the end. < main = interact work < toE_doc = unparse{|E_doc|} . expand{|E_doc|} . reduce{|Doc|} < toDoc = expand{|Doc|} . reduce{|E_doc|} . parse{|E_doc|} < work = toE_doc . (\d -> d { authors = filter (/= "Dubya") (authors d) }) . toDoc Regards, Frank
participants (4)
-
Frank Atanassow -
John Meacham -
Mark Carroll -
Ralf Laemmel