Personal tools

Applications and libraries/Generic programming/SyB

From HaskellWiki

< Applications and libraries | Generic programming
Revision as of 12:52, 11 May 2007 by Johanj (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Contents

1 Approach: Scrap your Boilerplate (SyB) and Variants

References

2 Required features/Portability

For all proposals:

  • rank-2 types

Rank-2 types are supported by GHC and Hugs and are going to be part of Haskell'.

2.1 SyB1 and SyB2

  • type-safe cast (via deriving Typeable)

Type-safe cast is implemented in GHC. However other compilers do not support it and it is not going to be part of Haskell'.

2.2 SyB3

  • multiple-parameter type classes

  • Explicit type application

  • type class abstraction

  • non-standard instances (undecidable instances (recursive dictionaries) and overlapping instances)

Multiple-parameter type classes are supported in GHC and Hugs and should be part of Haskell'. (Note that this is a rare example where functional dependencies are NOT required. So regardles of the outcome of the FD/AT debate, this extension is likely to be supported in Haskell'.)

Explicit type application is also a relatively minor extension, requiring EmptyDataDecls (also likely to be a part of Haskell') to be encoded.

Type class abstraction could be an extension on its own but there is no Haskell implementation that actually supports it. However, type class abstraction can be emulated using MPTC.

SyB3 also requires the restriction on instance declarations to be relaxed in two ways: undecidable instances allow type classes constraints to be satisfied coinductively (the translation generates a recursive dictionary.)

Secondly, SyB3 relies on overlapping instances to override generic definitions of type-indexed functions for specific types. Overlapping instances are not an essential part of SyB, but they do simplify the use of type-indexed operations.

Questions:

- Is Haskell' going to relax the constraints on type class instances? If so, will SyB instances be valid Haskell' code?

2.3 SyB Reloaded and Revolutions (SyBRR)

  • GADTs

GADTs are required for the type representations (Spine view and variants). GHC supports GADTs and they may be part of Haskell'.

3 Expressibility

  • We can do both producers and consumers, but we required different representations/operations for both.</li>

  • To support generic functions of different arities we need, once more, different representations.</li>

  • No local redefinitions</li>

4 Subset of data types covered

  • Supports sums of products and it has been shown to support some forms of GADTs.</li>

5 Usage

  • Library Writer: Defines the generic machinery: the different views/operations (Data in SyB or Spine and variants in SyBRR); also defines the type representations (the class Typeable in SyB or Type in SyBRR); the higher-order generic combinators like everywhere, everything can also be defined by the library writer.

  • Power User: This kind of user is only needed in the SyBRR variant, where the type representations for new data types need to be provided manually. In SyB, there is no such need since the compiler (GHC) can automatically derive that code.

  • User: The user defines generic functions using the infrastructure provided by the library writer. When using SyB, the user can easily support new data types just by appending deriving Typeable and Data to the data type declaration. The user benifits more from

6 Error Messages

Users of SyB can probably give a better comment about error messages.

  • what are the kind of type- error messages you get when you make a mistake in your generic function?</li>

7 Amount of work per data type (Boilerplate)

  • With SyB, we just need to use the deriving mechanism (for Typeable & Data). If this is not supported, must define operations (gfoldl, gunfold, etc).</li>

  • With SyBRR, we need to provide the representations and extend the toSpine function.

8 Extensibility

  • SyB1/SyB2 are statically extensible.</li>

  • SyB3 is dynamically extensible.</li>

  • SyBRR is not extensible. Extensibility would require extensible/open data types.</li>

(Need to define statically vs dynamically extensibility).

9 Reasoning

  • Fermin Reig has done some work about reasoning with SyB.</li>

10 Performance considerations

  • With SyB1/SyB2 there is a performance impact due to the type-safe casts.</li>

  • SyB3 may have some performance impact due to the fact that generic functions are type-class overloaded. Instance specialization, may help here. </li>

  • SyBRR is a representation based approach and thus passing representations around will have some impact.

11 Helpful extra features

TODO (users may have good ideas for this section)

  • What features could Haskell have that would make the approach easier to use?</li>

  • Are those features realistically feasible?</li>

12 Discussion

TODO