Applications and libraries/Generic programming/Lightweight - Revision history
http://www.haskell.org/haskellwiki/index.php?title=Applications_and_libraries/Generic_programming/Lightweight&action=history
Revision history for this page on the wikienMediaWiki 1.19.5-1+deb7u1Wed, 03 Sep 2014 04:47:44 GMTJohanj at 12:51, 11 May 2007
http://www.haskell.org/haskellwiki/index.php?title=Applications_and_libraries/Generic_programming/Lightweight&diff=12993&oldid=prev
http://www.haskell.org/haskellwiki/index.php?title=Applications_and_libraries/Generic_programming/Lightweight&diff=12993&oldid=prev<p></p>
<p><b>New page</b></p><div>== Approach: A Lightweight Implementation of Generics and Dynamics ==<br />
<br />
== Required features/Portability ==<br />
<br />
<ul><br />
<li><p>Requires Haskell 98 + existential types</p></li><br />
<li><p>Should run in GHC, Hugs, others?</li></p><br />
</ul><br />
<br />
== Expressibility ==<br />
<ul><br />
<li><p>Can do both producer and consumer functions.</li></p><br />
<li><p>Multiple representations needed for generic functions of different <br />
arities.</li></p><br />
<li><p>No local redefinitions.</li></p><br />
</ul><br />
<br />
== Subset of data types covered ==<br />
<br />
<ul><br />
<li><p>The family of types supported is based on sums of products (together with extensions). This means that mutually recursive types and nested are supported.</li></p><br />
<li><p>The extensions can include Haskell primitive types, function spaces<br />
and Dynamic types (which have special attention in the paper)</li></p><br />
</ul><br />
<br />
== Usage ==<br />
<ul><br />
<li><p> ''Library Writer'': Responsible for the sums-of-products machinery,<br />
the representation(s) data type(s) to be defined in the library and <br />
defining the class and standard instances for "Representable". <br />
The library writer needs to be have a deep knowledge about generic <br />
programming.</p></li><br />
<li><p> ''Power User'': Defines the boilerplate for new data types. Needs to be fairly <br />
familiar with the implementation.</p></li><br />
<li><p> ''User'': defines generic functions by pattern matching on the structure of "Rep".<br />
This requires that he is comfortable with sums of products and isomorphisms.<br />
For convenience, the user should also provide a definition that uses the <br />
type class "Representable", which avoids the representations to be passed<br />
explicitly.</li></p><br />
<li><p> ''End User'': If "Representable" is used, then the end can just use generic functions <br />
in the same way as any other ad-hoc (that is, type class overloaded) functions.<br />
</li></p><br />
</ul><br />
<br />
== Error Messages ==<br />
<br />
<ul><br />
<li><p>Some messages may involve errors with existential types, which may be hard to grasp for programmers.</li></p><br />
</ul><br />
<br />
== Amount of work per data type (Boilerplate) ==<br />
<ul><br />
<li><p>Isomorphisms between sums of products and data types.</li></p><br />
<li><p>Instances of Representable.</li></p><br />
<li><p>Smart constructors for representation of data types.</li></p><br />
</ul><br />
<br />
== Extensibility == <br />
<ul><br />
<li><p>The ''Rep'' type (like all Haskell data types) is non-extensible.<br />
This means that the approach is not (obviously) extensible. However we can try to combine the approach with type classes to get some form of extensibility (RepLib proposes one solution like this). Alternatively, Ralf Hinze and Andres Loeh proposed "Open datatypes and functions" for tackling this problem.</li></p><br />
</ul><br />
<br />
== Reasoning ==<br />
<br />
TODO<br />
<br />
== Performance considerations ==<br />
<ul><br />
<li><p>Sums of products based and therefore involving considerable <br />
performance penalties. However, we could use partial evaluators to remove these intermediate layers.</li></p><br />
<li><p>Representations of types are passed at run-time, and interpreted.<br />
Passing and interpreting types at run-time is hard to avoid.</li></p><br />
</ul><br />
<br />
== Helpful extra features ==<br />
<ul><br />
<li><p> GADTs (already implemented in GHC) allow more direct definitions <br />
of generic functions, since there is no need to apply the type <br />
coercions explicitly</li></p><br />
<li><p>A boilerplate generation mechanism. This would effectively mean <br />
that power users would not be necessary.</li></p><br />
<li><p>Open data types and functions in order for extensibility.</li></p><br />
<li><p>Kind polymorphism, for eliminating the need for multiple <br />
representations.</li></p><br />
</ul><br />
<br />
== Discussion ==<br />
<br />
(''Bruno Oliveira'')<br />
<br />
An interesting approach which is quite lightweight and that is fairly easy to <br />
use (specially if we would not need to handle any of the boilerplate). It is a bit outdated because with GADTs, the use can be slightly simplified. However, this also takes us further away from Haskell 98 or even Haskell' (since GADTs will not be there).<br />
I think that LIGD is still a reference for a generic programming library that uses a data type for type representations and sums of products as a family of data types. <br />
<br />
A drawback may be performance, since we need to convert a data type into its <br />
isomorphic sum of products representation.<br />
<br />
(''James Cheney'')<br />
<br />
From what I've seen, Ralf's "Fun with phantom<br />
types", "generics for the masses" and from what I've heard Stephanie's<br />
RepLib (caveat: haven't read that paper carefully) are in a similar<br />
spirit and subsume much or all of what's in the LIGD paper. Also, much<br />
more now appears to be known about complementary things like GADTs,<br />
open/extensible types and functions which could help fix some of the<br />
limitations of the original LIGD approach.<br />
<br />
Assuming that GADTs do eventually become a standard feature, I'd<br />
definitely be in favor of using them instead of explicit to/from<br />
conversions in an implementation of LIGD, for efficiency if nothing<br />
else. In addition, as the FCPT paper notes, there are some natural<br />
seeming things that you can only do if equations are known to the type<br />
system. This was one motivation for our subsequent tech report on<br />
"first class phantom types", which essentially proposed extending<br />
Haskell 98 with equation guards on datatypes, i.e. GADTs. But, once you<br />
have GADTs a lot of things appear to get simpler, and simulating<br />
first-class generics/dynamics via type representations seem to be just<br />
one example.<br />
<br />
(''Johan Jeuring'')<br />
<br />
I think LIGD is quite a nice library, that needs almost no Haskell <br />
extensions. But it has its limitations.</div>Fri, 11 May 2007 12:51:35 GMTJohanjhttp://www.haskell.org/haskellwiki/Talk:Applications_and_libraries/Generic_programming/Lightweight