Hello,<br><br><div><span class="gmail_quote">On 11/5/06, <b class="gmail_sendername">Bruno Oliveira</b> <<a href="mailto:bruno.oliveira@comlab.ox.ac.uk">bruno.oliveira@comlab.ox.ac.uk</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hello all,<br><br>Pablo Nogueira asked me to post this email in the mailing list since he<br>had some problems trying to post himself. Here is the text:</blockquote><div><br>[...] </div><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Perhaps the entry would attract the attention of people with other definitions<br>of generic programming in mind, such as users of the C++ Standard Template<br>Library. C++ Templates are often roughly equated with a static version of
<br>parametric polymorphism, but in the STL data types are abstract, not<br>algebraic. This is an important difference.</blockquote><div><br>Just to make things clearer for me, what would the entry be for C++ STL?<br><br>
[...] <br></div><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br>3. Support for data abstraction is "generic" if generic programmers can write
<br> a single generic function definition for all (or many) abstract types. This<br> is better than providing definitions *for each* abstract type. I hope you<br> agree with me that the latter is not *generic* programming. I believe none
<br> of the existing generic programming approaches support this. Perhaps it is<br> time to think about it when designing a generic library.<br><br>In Generic Haskell, support for abstract types is more complicated because,
<br>unlike SYB, the language is designed to deal with types of arbitrary<br>kind. Just to pinpoint a particular problem, there is a lack of<br>parametrisation on type-class constraints. There follows some *pseudocode*<br>
examples to illustrate the point.<br><br>Type-specific instances of generic functions would seem easy to define:<br><br> gsize<Queue> :: Queue a -> Int<br> gsize<Queue> = gsize<List> . QueueToList<br>
<br> gsize<OrdSet> :: Ord a => OrdSet a -> Int<br> gsize<OrdSet> = gsize<List> . OrdSetToList<br><br>but a more generic version for types t::*->* equipped with a, say, overloaded<br>"toList" operation would have to be parametric on the constraint "c", which
<br>might be "empty":<br><br> gsize<t::*->*> :: c a => t a -> Int<br> gsize<t> = gsize<List> . toList</blockquote><div><br>At the moment Generic Haskell cannot handle abstract data types because it cannot have access to their representations, which is something that the compiler needs to generate a structural representation type and later to specialize a generic function to the ADT.
<br><br>However, the ADT provider could perfectly specify the things needed for GH, that is, a structural representation, and embedding projection pair. This fits nicely with ADTs because the embedding projection functions (especially the 'to' direction) can preserve the data type invariants that motivated the use of abstraction in the first place.
<br><br>This also fits nicely with the idea of Generic Views because ADTs was the motivation for Views in Wadler's original paper.<br><br>Just to make things more concrete, this is what the Queue library writer would have written in order to enable generic programming on Queues:
<br><br>-- snippet --<br>-- We use a similar structure to lists:<br>data repr(Queue a) = () `Sum` a `Prod` Queue a<br>ep(Queue a) :: EP (Queue a) (repr(Queue a))<br>ep (EP fromQueue toQueue)<br><br>fromQueue :: Queue a -> repr(Queue a)
<br>fromQueue q<br> = case deQueue q of<br> Just (e,q') -> Inr (e :*: q')<br> Nothing -> Inl ()<br>toQueue (Inl (e :*: q)) = e `prependToQueue` q<br>toQueue (Inr ()) = emptyQueue<br>-- end of snippet --<br>
<br>The gsize function would be left as it is, while still enabling generic application to Queue and other abstract data types. This is not implemented in GH, but it should not be difficult to do so.<br></div><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
To conclude this long email, I think data abstraction should be considered<br>from the start in the design of a generic programming library. On the one<br>hand, this should force us to see the internal representation of types as (1)
<br>a parameter (cause we want to be generic), and (2) as something more abstract<br>than an encoding of the *implementation* of the type. On the other hand,<br>perhaps polytypic programming can then be conveyed to an object-oriented
<br>setting without using naive encodings of algebraic data types as the<br>"objects".</blockquote><div><br>In our framework the representation of ADTs is dictated by the view chosen (and the structure provided by the ADT implementor). For other frameworks I suppose similar techniques would be used.
<br><br>To be honest, I am a bit confused as how the C++ STL programming style corresponds to generic programming as discussed in this list. In my view the STL stuff looks more related to type classes than to data type generic programming. Maybe you can clarify your point further.
<br><br>Cheers,<br><br>Alexey <br></div><br></div>