Owning SYB

Simon Peyton-Jones simonpj at microsoft.com
Mon Jul 28 12:46:37 EDT 2008


Dear Generic folk

[I'm spamming libraries at haskell.org too, in case anyone interested in generics is not on generics at haskell.org.]

As you know, Claus has offered a somewhat-detailed proposal for changes to the SYB library (below).  But I don't think that we have an active maintainer for any of the generic-programming libraries (esp SYB) apart from Uniplate.  Then there's the related question of what generic-programming technology to promote for clients of the GHC API.

The obvious candidates are Claus himself, or Alexey Rodriguez, or Thomas Schilling; but perhaps there are others too?  Maybe no one has stepped forward because you all think that I'm on the job!  But I'm not... I'm busy with GHC itself, and would love a maintainer for SYB and associated gubbins.  I fear that otherwise we may lose the benefits of Claus's homework.

Simon



| -----Original Message-----
| From: generics-bounces at haskell.org [mailto:generics-bounces at haskell.org] On Behalf Of Claus Reinke
| Sent: 21 July 2008 14:16
| To: generics at haskell.org
| Subject: [Hs-Generics] Data.Generics with GPS (using Maps to avoid getting lost in Data)
|
|
| summary: speed up Syb with Uniplate-inspired techniques
|
| == Performance issues in Syb ==
|
| As it stands, classic Syb, while well-supported in GHC isn't exactly the
| fastest generic programming option. In fact, it routinely seems to come
| out last in performance comparisons, sometimes by a substantial factor.
|
| That isn't always a problem in practice, because the gains in
| expressiveness/conciseness/maintainability outweigh the loss in
| performance, because traversal performance is not the bottleneck, or
| because practical use often involves hand-tuned traversal schemes
| instead of the example schemes typically used in benchmarks.
|
| Be that as it may, performance is a consideration, negative results have
| been published, and it seems that performance of experimental code has
| led to Syb being abandoned in at least one project. While it would be
| unrealistic to expect Syb traversals to compete with hand-written ones
| with current compilers, there are several obvious areas where Syb
| traversal performance could be subjected to improvements:
|
| (a) traversing irrelevant parts of the structure (because everything is
|     treated generically)
| (b) combining results in simple, but inefficient ways ((++) nesting with
|     the structure)
| (c) repeated runtime type checks to determine which function in a
|     generically extended transformation/query to apply
|
| While runtime type checks are inherent in SYB (and alternatives have
| been proposed that claim to avoid them), all of a/b/c can be addressed
| to some extent in defining tuned traversals using the basic library.
| There tends to be a trade-off for a vs c, as avoiding senseless generic
| traversals of specific substructures implies additional runtime type
| checks to identify those substructures

[...rest snipped...]



More information about the Libraries mailing list