Applications and libraries/Generic programming/Strafunski

Approach: Strafunski

Reference: Strafunski home page.

Strafunski is a Haskell-centered software bundle for generic programming and language processing. On this page, we focus on the generic programming capabilities as offered by Strafunski's subpackage StrategyLib; for the language processing support of Strafunski, see the subsection on Language processing support.

The generic programming capabilities of Strafunski are less ambitious than some other generic functional programming approaches; it limits itself to enabling type-safe strategic programming as useful for the construction of generic traversals (transformations and queries) over large sets of first-order, non-parameterized algebraic datatypes, such as abstract syntax representations.

Strafunski is compatible with the scrap-your-boilerplate (SyB) approach to generic functional programming, in the sense that one of the available implementations of Strafunski's strategy combinator API relies on the Data.Generics module of SyB1.

Required features/Portability

Strafunski can be used with at least GHC and Hugs (others?). It relies on compiler extensions for overlapping and undecidable instances.

Strafunski is usually used in combination with DrIFT, though instances can of course be provided by hand.

If the Data.Generics implementation of Strafunski's strategy combinator API is activated, the requirements and portability are the same as those of SyB1. Also, instances can then be provided alternatively with DrIFT, by hand, or via the deriving clause.

Expressibility

Strafunski is based on the notion of a functional strategy. These are generic functions that can traverse into terms of any type while mixing type-specific and uniform behaviour. Strafunski's suite of basic strategy combinators can be found here:

StrategyPrimitives definitions source

Two kinds of functional strategies are supported: monadic type-preserving transformations (of type TP m, which corresponds to forall a . a -> m a), and monadic type-unifying queries (of type TU u m, which corresponds to forall a . a -> m u).

Among the strategy combinators are combinators for one-layer generic traversal into terms. These enable the construction of generic traversals of various kinds (partial or complete, fix-point or one-pass, bottum-up or topdown, etc.).

Type-specific and generic behaviour can be mixed on the basis of the so-called adhoc combinators. These specialize a generic function for a specific input type.

Subset of data types covered

Strafunski is primarily targeted at algebraic datatypes that represent language syntaxes. It supports non-parameterized algebraic datatypes without function components.

Usage

To enable Strafunski for new user-defined datatypes, one must run DrIFT on those datatypes.

To write new generic functions, one must import the StrategyLib module, or one or more of the submodules of the library, and use the available strategy combinators to compose new functions.

Generic functions can be called by normal functions without exposing this fact in their types. This is called the "Keyhole Operation" design pattern in "Design Patterns for Functional Strategic Programming" (Ralf Lämmel & Joost Visser, 2002). This enables the use of generic functions without knowing it.

End users (those that use generic functions, but do not define them) must make sure that they import the appropriate class instances for the datatypes to which they apply generic functions. Normal functions defined using generic functions can be used without such precautions.

Strafunski is suitable for generic programming over very large sets of algebraic datatypes, typically representations of language syntaxes. The size of these sets of datatypes makes it desirable to automatically create instances for these datatypes, not with the deriving mechanism, but with DrIFT. DrIFT allows instances to reside in a different file than the datatypes and to be compiled separately. The need for separate compilation explains why Strafunski is usually used in combination with DrIFT, even when the SyB implementation of its strategy combinator API is activated.

Error Messages

There do not seem to be strong usability problems with respect to error reporting.

Amount of work per data type (Boilerplate)

When new datatypes are added, DrIFT can be invoked to supply the necessary instances.

Extensibility

Strafunski enjoys good extensibility properties. New datatypes can be added without changing existing generic functions. New generic functions can be added without changing existing datatypes or their instances.

Reasoning

The set of generic function combinators of Strafunski has a well-understood semantics that does not rely on very advanced typing features. As a result, reasoning is quite straightforward. In fact, reasoning can be automated, as demonstrated in "Transformation of Structure-Shy Programs, Applied to XPath and Strategic Functions" (Alcino Cunha & Joost Visser, draft October 2006).

Performance considerations

Time and space behaviour of generic functions created with Strafunski seem to pose no problems in practice, given its successful application to non-trivial analysis and transformation of large language syntaxes (see Applications).

Helpful extra features

The current feature set of Haskell + overlapping and undecidable instances is sufficient.

Language processing support

Apart from the strategy combinator library StrategyLib, the Strafunski bundle provides generative tool support based on DrIFT and Sdf2Haskell, and parsing/unparsing support based on the Haskell ATerm Library and the scannerless, generalized LR parser SGLR.

Applications

Documented applications of Strafunski include the Haskell Refactorer HaRe (processing Haskell abstract syntax trees), the XsdMetz tool (processing XML Schema), the VooDooM tool (processing VDM-SL and producing SQL), and Sdf2Haskell (ingredient of the Strafunski bundle that generates Haskell datatypes from SDF grammars).

See also "A Strafunski Application Letter" (Ralf Lämmel & Joost Visser, 2003).

Discussion

Though limited in its generic functional programming capabilities with respect to other approaches to generic functional programming, Strafunski has proven quite effective in its primary application domain of language processing. Strafunski avoids boilerplate code for such applications, but relies on very few non-standard Haskell extensions.