\documentclass{entcs} \usepackage{prentcsmacro} \usepackage{graphicx} % The following is enclosed to allow easy detection of differences in % ascii coding. % Upper-case A B C D E F G H I J K L M N O P Q R S T U V W X Y Z % Lower-case a b c d e f g h i j k l m n o p q r s t u v w x y z % Digits 0 1 2 3 4 5 6 7 8 9 % Exclamation ! Double quote " Hash (number) # % Dollar $ Percent % Ampersand & % Acute accent ' Left paren ( Right paren ) % Asterisk * Plus + Comma , % Minus - Point . Solidus / % Colon : Semicolon ; Less than < % Equals =3D Greater than > Question mark ? % At @ Left bracket [ Backslash \ % Right bracket ] Circumflex ^ Underscore _ % Grave accent ` Left brace { Vertical bar | % Right brace } Tilde ~ \usepackage{amssymb} \usepackage{comment} \usepackage{url} \usepackage{ifthen} \def\lastname{L{\"a}mmel} \newcommand{\citeSF}{\cite{Strafunski,LV02:PADL,Laemmel02:WRS,LV02:RULE,LV02:justtwo,LV03:PADL}} \newcommand{\citeSYB}{\cite{Boilerplate,LPJ03,LPJ04}} \newcommand{\syb}{``\emph{Scrap Your Boilerplate}''} \newcommand{\Strafunski}{\emph{Strafunski}} \newlength{\basewidth} \newlength{\topwidth} \newcommand{\superimpose}[2]{% \settowidth{\basewidth}{#1}% \settowidth{\topwidth}{#2}% \ifthenelse{\lengthtest{\basewidth > \topwidth}}% {\makebox[0pt][l]{#1}\makebox[\basewidth]{#2}}% {\makebox[0pt][l]{#2}\makebox[\topwidth]{#1}}% } \newcommand{\lchoice}[2]{\ensuremath{#1\,\superimpose{$\leftarrow$}{$+$}\,#2}} \newcommand{\all}[1]{\ensuremath{\Box(#1)}} \newcommand{\one}[1]{\ensuremath{\Diamond(#1)}} \newcommand{\extend}[2]{\ensuremath{#1\,{\lhd}\,#2}} \begin{document} \begin{frontmatter} \title{Programmable rewriting strategies in Haskell\\ {\large ---~White Paper~---}}\thanks[?]{This white paper served as an invited position paper for the 4th International Workshop on \emph{Reduction Strategies in Rewriting and Programming} (WRS 2004), June 2, 2004, Aachen, Germany. The paper was presented at the WRS 2004 round table ``\emph{Strategies in programming languages today}''.} \author{Ralf \lastname\,$^{1,2}$} \address{ $^1$\ Vrije Universiteit, Amsterdam\\ $^2$\ Centrum voor Wiskunde en Informatica, Amsterdam} \begin{abstract} Programmable rewriting strategies provide a valuable tool for implementing traversal functionality in grammar-driven (or schema-driven) tools. The working Haskell programmer has access to programmable rewriting strategies via two similar options: (i) the \Strafunski\ bundle for generic functional programming and language processing, and (ii) the \syb\ approach to generic functional programming. Basic rewrite steps are encoded as monomorphic functions on datatypes. Rewriting strategies are polymorphic functions composed from appropriate basic strategy combinators. \medskip \noindent We will briefly review programmable rewriting strategies in Haskell.\\ \noindent We will address the following questions: \begin{itemize} \item What are the merits of Haskellish strategies? \item What is the relation between strategic programming and generic programming? \item What are the challenges for future work on functional strategies? \end{itemize} {\small \noindent \textbf{Acknowledgements.} \medskip \noindent The \Strafunski\ project~\citeSF\ is joint work with Joost Visser. The \syb\ approach~\citeSYB\ is joint work with Simon Peyton Jones. } \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{frontmatter} \newpage \section{Strategic programming} \label{S:sp} Our use of the term `strategy' originates from the work on programmable rewriting strategies for term rewriting \`a la Stratego~\cite{LV97,VBT98,Visser01:RTA}. Strategic programmers can separate basic rewrite steps from the overall scheme of traversal and evaluation. These schemes are programmable by themselves! There are one-layer traversal primitives that facilitate the definition of whatever recursion pattern for traversal. There are further, perhaps less surprising, basic combinators for controlling the evaluation in terms of the order of steps, the choices to be made, the fixpoints to be computed, and others. An extended exposition of what we call `strategic programming' can be found in~\cite{EOSP}. \medskip \noindent Related forms of programmable strategies permeate computer science. For instance, evaluation strategies without any traversal control are useful on their own in rewriting~\cite{CELM96,BKK96}. In theorem proving, one uses a sort of strategies as proof tactics and tacticals~\cite{Paulson83}. In parallel functional programming, one uses a sort of strategies to synthesise parallel programs~\cite{THLPJ98}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Functional strategies in \Strafunski} \label{S:Strafunski} The \Strafunski\ project~\citeSF\ incarnated programmable rewriting strategies for functional programming, namely for Haskell. Strategies are essentially polymorphic functions on datatypes (or `term types'). The basic rewrite steps are readily specified as monomorphic functions on datatypes. For instance, the following rewrite step encodes some sort of constant elimination for arithmetic expressions: {\footnotesize \begin{verbatim} const_elim :: Expr -> Maybe Expr const_elim ((Const 0) `Plus` x) = Just x const_elim _ = Nothing \end{verbatim} } \noindent In concrete syntax, and without Haskellish noise, this reads as ``\verb!0 + x -> x!''. In the example, we wrap the result of the rewrite step in the \texttt{Maybe}\ monad, which allows us to observe success vs.\ failure of a rewrite step. We can use stacked monads (rather than just \texttt{Maybe}) in rewrite steps and strategies. This allows us to deal with state, environment, nondeterminism, and backtracking. \medskip \noindent In \Strafunski, there are two (monadic) types of strategies: % \begin{itemize} \item \texttt{TP}~---~type-preserving strategies: domain and co-domain coincide. \item \texttt{TU}~---~type-unifying strategies: all datatypes are mapped to one result type. \end{itemize} % \Strafunski's strategy library is based on primitive strategy combinators: %{\small \begin{itemize} \item \texttt{idTP}~---~the identity function. \item \texttt{failTP}~---~the always failing strategy. \item \texttt{adhocTP}~---~update strategy in one type. \item \texttt{seqTP}~---~sequential composition. \item \texttt{choiceTP}~---~left-biased choice. \item \texttt{allTP}~---~apply a strategy to all immediate subterms. \item \texttt{oneTP}~---~apply a strategy to one immediate subterm. \item Similar operators are offered for \texttt{TU}. \end{itemize} %} \noindent Rewrite steps can be turned into functional strategies using the \texttt{adhocTP} combinator. The strategy % \verb!(idTP `adhocTP` const_elim)! % will succeed for all types other than \texttt{Expr}. The strategy % \verb!(failTP `adhocTP` const_elim)! % will fail for all types other than \texttt{Expr}. \medskip \noindent We can now define all kinds of reusable evaluation and traversal schemes, e.g.: {\footnotesize \begin{verbatim} -- Exhaustive application of a strategy repeatTP :: MonadPlus m => TP m -> TP m repeatTP s = (s `seqTP` (repeatTP s)) `choiceTP` idTP -- Full type-preserving traversal in top-down order full_tdTP :: Monad m => TP m -> TP m full_tdTP s = s `seqTP` (allTP (full_tdTP s)) -- Type-preserving traversal stopping at successful branches stop_tdTP :: MonadPlus m => TP m -> TP m stop_tdTP s = s `choiceTP` (allTP (stop_tdTP s)) -- One-hit type-preserving traversal in bottom-up order once_buTP :: MonadPlus m => TP m -> TP m once_buTP s = (oneTP (once_buTP s)) `choiceTP` s \end{verbatim} } \vspace{-42\in} \subsection*{The essence of ``The essence of strategic programming''~\cite{EOSP}} As an illustrative use case, the strategy % \begin{verbatim} once_buTP (failTP `adhocTP` const_elim) \end{verbatim} % attempts a single constant elimination when given a term. Applying this strategy exhaustively (cf.\ the evaluation strategy \texttt{repeatTP}), amounts to (naive) innermost normalisation. This use case demonstrates the overall tenor of strategic programming: % {\small \begin{quote}\itshape Separate problem-specific rewrite steps (i.e., \verb!const_elim!) from the overall, possibly reusable scheme for traversal and evaluation (i.e., \verb!once_buTP!). Both parts are put together by mere parameter passing, or by function composition. The schemes for traversal and evaluation are fully programmable by the virtue of one-layer traversal primitives (i.e., \texttt{allTP} and \texttt{oneTP}). \end{quote}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{What are the merits of Haskellish strategies?} \label{S:a} \subsection*{Applied setup} Haskellish strategies were born in an applied programming context. That is, we have designed them in an attempt to make functional programming fit for the implementation of program analyses and transformations~---~as relevant in the context of language implementation, software reverse engineering, re-engineering, and others. For instance, \Strafunski's functional strategies readily deal with huge systems of algebraic datatypes as opposed to making assumptions such as use of single datatypes~\cite{JJ00} or functorial encodings~\cite{SAS99}. Also, functional strategies are versatile in terms of the recursion schemes that can be accommodated~---~when compared to programming with merely generalised folds~\cite{MFP91}. Furthermore, functional strategies are conveniently customisable, whereas customisation is considered as a subordinated issue in other setups, which offer fully generic functions such as generic maps~\cite{JJ97,Hinze00:POPL}. Customisation is crucial for strategic programming because traversal strategies involve type-specific cases on a regular basis. \medskip \noindent Functional strategies have been used in various ways, e.g.: % \begin{itemize} % \item State-of-the-art Haskell refactoring tools~\cite{LRT03}. \item Language extension for Fortran~\cite{EF04:PADL}. \item Java refactoring~\cite{LV02:PADL} (a subset of Java to be precise). \item Simple software metrics for Java~\cite{LV03:PADL}. \item Reverse engineering for Cobol~\cite{LV03:PADL} (call-graph extraction). \item A framework for language-parametric refactoring~\cite{Laemmel02:RULE}. % \end{itemize} \subsection*{Language economy} Functional strategies are easily supported in Haskell. There are different implementational models~\cite{LV02:PADL,Laemmel02:WRS,LV02:justtwo}. No proper language extension is needed. For some bits, code needs to be derived per user-defined datatype, which is however automated for the convenience of the programmer. Most strategic idioms are readily provided by Haskell. Most notably, rewrite steps are just functions defined by pattern matching. Also, monads~\cite{Wadler92} fit nicely with the effects that one encounters during strategic programming. The \texttt{Maybe}\ monad models the potential of failure. The list monad (and friends) is used to deal with nondeterminism and backtracking, alike for the state and the environment monad. Haskell has a strong record in implementing combinator libraries for programming domains, e.g., for parsing, pretty printing, XML processing, graphical user interfaces, and data structures. \Strafunski's strategies come just as another combinator library. Strategic programming in Haskell means that debugging, compilation, type checking, type inference, etc.\ come for free. \subsection*{Strongly typed, first-class strategies} Strategy combinators are higher-order functions, which carry interesting types. So Haskell, again, is the right choice. Firstly, the type of a strategy combinator clarifies if it is type-preserving (``\texttt{TP}'') or type-unifying (``\texttt{TU}''). Secondly, the chosen \texttt{Monad}\ instance in the type points out effects including potential of failure. Thirdly, the type indicates possible arguments that need to be passed in addition to the term, on which traversal is performed. While the influential system Stratego is largely untyped (but it could be typed~\cite{Laemmel03:JLAP}), Haskellish strategies are typed in all beauty of polymorphism and higher-order functions. This is taken to a limit in ``\emph{The Sketch of a Polymorphic Symphony}''~\cite{Laemmel02:WRS}, where we define `the mother of traversal', which is a highly parametric traversal scheme. \medskip \noindent We adopt an example from~\cite{Laemmel02:RULE} to illustrates the virtue of typed, higher-order strategies. The following function signature types a strategy \texttt{extract} for a language-parametric program transformation. That is, the strategy models the \emph{extraction refactoring} for whatever abstraction form~---~be it a method declaration, a function declaration, or others: {\footnotesize \begin{verbatim} extract :: Abstraction abstr name tpe apply => TU [(name,tpe)] Identity -- Recognise declarations -> TU [name] Identity -- Recognise using references -> (apply -> Maybe apply) -- Recognise focused fragment -> ([abstr] -> [abstr]) -- Mark host for new abstraction -> ([abstr] -> Maybe [abstr]) -- Remove marking for host -> ([(name,tpe)] -> apply -> Bool) -- Side conditions on fragment -> name -- Name for new abstraction -> prog -- Input program -> Maybe prog -- Output program \end{verbatim} } \noindent The above Haskell type clearly identifies 4 type parameters for syntactical categories \texttt{prog} (programs), \texttt{abstr} (abstraction form), \texttt{name} (name of parameters and abstractions), and \texttt{tpe} (type of parameters) with a relationship \texttt{Abstraction} on them for the sake of making the function \texttt{extract} parametric with regard to the relevant abstraction form. \medskip \noindent Using an untyped \texttt{extract} is beyond a Haskell programmer's imagination. How would one possibly understand and correctly use an \emph{untyped} function with 8 value arguments; 6 of the 8 of a higher-order type; 2 out of the 6 of a strategically polymorphic type? %\subsection{Referential transparency} %\subsection{Higher-order strategies} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Aren't strategies just about generic programming?} \label{S:b} In \Strafunski, strategy types are opaque. \Strafunski's strategy library really provides an abstract datatype for strategies. This allows for different models of strategies. Some models have been described in the literature~\cite{LV02:PADL,Laemmel02:WRS,LV02:justtwo}. Some strategic improvements could be accommodated by new models without changing \Strafunski's API. The opaque status also encourages a point-free style (or combinator style) of strategic programming. We can clearly see that \Strafunski's strategy types are opaque because there are even basic combinators for strategy application, which resemble function application: \newpage {\footnotesize \begin{verbatim} applyTP :: (Monad m, Term t) => TP m -> t -> m t applyTP s t = ... -- opaque implementation omitted \end{verbatim} } \noindent However, strategy types are not inherently opaque, and in the \syb\ approach to generic programming~\citeSYB\ they indeed aren't. In this approach, generic traversal schemes and all that are just straight polymorphic functions, possibly of a rank-2 type (as supported by the GHC implementation of Haskell, but also elsewhere). The \syb\ approach is based on two Haskell classes \texttt{Typeable} and \texttt{Data} (the former being a superclass of the latter) for a handful of generic function combinators. (The GHC implementation of Haskell automatically derives instances of these classes per user-defined datatype.) \Strafunski's strategy library can be reconstructed in this framework~\cite{LV02:justtwo} by basically using just two of its combinators: \texttt{cast} for type-safe cast and \texttt{gfoldl} for one-layer traversal. \medskip \noindent Then, strategy types become non-opaque, concise and versatile: {\footnotesize \begin{verbatim} type GenericM m = forall a. Data a => a -> m a -- corresponds to TP m type GenericT = forall a. Data a => a -> a -- transformations type GenericQ r = forall a. Data a => a -> r -- queries \end{verbatim} } \noindent In \Strafunski, we did not favour variations like \texttt{GenericT} because this would have implied a proliferation of combinators for the various opaque types. To illustrate the use of these \texttt{forall} types, we reconstruct the traversal scheme \verb!stop_tdTP!: {\footnotesize \begin{verbatim} stop_tdTP :: GenericM Maybe -> GenericT stop_tdTP s x = case s x of Nothing -> gmapT (stop_tdTP s) x Just x' -> x' \end{verbatim} } \noindent We used the combinator \verb!gmapT :: GenericT -> GenericT!, which is the non-monadic variation on \texttt{allTP}~\cite{LPJ03}. The type of \verb!stop_tdTP! says that this combinator takes a polymorphic function and returns one. We use the type aliases for readability; we could as well inline the \texttt{forall} types. As an exercise in versatility, we have reconstructed a more specifically typed scheme \verb!stop_tdTP!. The original scheme involved the opaque type \texttt{TP m}, where \texttt{m} could be instantiated later to any instance of \texttt{MonadPlus}. The reconstructed scheme fixes the monad for the argument type to \texttt{Maybe}, which allows us to guarantee success of the composed strategy (cf.\ the non-monadic result type \texttt{GenericT}). \medskip \noindent Once we get used to forming generic function types, we will not limit ourselves to strategy types. That is, while strategies are unary polymorphic functions on datatypes, there are other polymorphic type schemes of interest. Generic functions do not need to be unary, neither do they need to be polymorphic in the argument position. For instance: {\footnotesize \begin{verbatim} type GenericEq = forall a b. (Data a, Data b) => a -> b -> Bool -- generic equality type GenericB = forall a. Data a => a -- build a term; no traversal! type GenericR m = forall a. Data a => m a -- read a term using a monad \end{verbatim} } \noindent So while the \Strafunski\ approach emphasised unary term traversal, the \syb\ approach to generic functional programming allows us to abstract over more than just unary term traversal. We can abstract over multi-parameter traversal, over term generation, serialisation, and de-serialisation, zipping, and others~\cite{LPJ04}. Especially the correspondence between term traversal and term building is a duality that was uncovered some time ago by squiggolists: given a regular datatype (such as lists), or perhaps even any datatype, one can fold a datum of the type (``traverse it''), and unfold it (``build it'')~\cite{MFP91,Augusteijn99}. Other generic programming approaches also serve this generality. For instance, generic programming extensions like PolyP~\cite{JJ97} or Generic Haskell~\cite{Hinze99:HW,Beryl} employ powerful techniques for structural induction on the type structure of data to be consumed or produced. In this context, the \syb\ approach is characterised as follows: % \begin{itemize} \item The approach blends well with normal Haskell programming. \item The approach is lightweight. It is based on two simple Haskell type classes. \item The approach does not require any compile-time code specialisation. \item Generic functions operate immediately on Haskell datatypes. \item Generic functions are first-class citizens: traversal schemes are higher-order. \item Generic functions are easily customised by (nominal) type case. \end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Where to go from here?} \label{S:c} Strategic programming is a young research field. Several challenges are readily waiting. The following list is biased towards functional strategies, and relates to the current \Strafunski\ and \syb\ implementations, but most challenges are relevant for programmable rewriting strategies in general. \subsection*{Analysis opportunities} The functional strategist might want to take advantage of analyses that improve static guarantees or run-time performance of his or her strategies. Some typical examples follow: % \begin{description} % \item[Termination] Strategic traversal schemes are like recursion schemes: they are meant as disciplined replacement for free-wheeling recursive programming. Nevertheless, the versatility of strategies makes it still quite easy to encode diverging strategies. For instance, \texttt{(repeatTP idTP)} will diverge. The implied usage pattern for fixpoint iteration with \texttt{repeatTP} is that the argument strategy should eventually fail. % \smallskip % \item[Stupidity] Just as there are `stupid casts' in object-oriented programming (i.e., type casts that cannot possibly succeed), so there are `stupid strategies' in strategic programming. For instance, the strategy \texttt{(full\_tdTP\ (failTP `adhocTP` f))} is stupid because a full traversal is meant to have a chance of succeeding for whatever type, but the given composition will undoubtedly fail for all types except for the domain of \texttt{f}. % \smallskip % \item[Shortcutting] On the basis of the type-specific cases of a strategy it would be often feasible to shortcut traversal leading to a more efficient traversal. For instance, the strategy \texttt{(full\_tdTP\ (idTP `adhocTP` f))} does not need to be pushed into a term any further if it is clear that subterms of \texttt{f}'s domain are out of reach~---~on the basis of static type information. For such hopeless branches, the strategy can be shortcut to \texttt{idTP}. % \smallskip % \item[Composability] Chains of strategies need to cooperate in the sense that a given strategy in the chain should be enabled, or at least not disabled by earlier elements in the chain. (One could call this an advanced form of stupidity perhaps, so it is not stupid!) Enabling and disabling can be understood in terms of pre- and post-conditions for strategies, in which case related work on program transformation might turn out to be of use~\cite{KK04,SML04}. % \end{description} \subsection*{Expressiveness opportunities} The functional strategist might even ask for extra expressiveness, which, in an extreme case, requires Haskell extensions. Alternatively, the extra-strategic expressiveness can also be accommodated by the virtue of a more open Haskell system, or by preprocessing, or perhaps by appropriate combinator libraries. Some prime examples follow: % \begin{description} % \item[Sexy types] There is a potential need for designated types to declare, check, and infer success behaviour, determinism, and some forms of pre- and post-conditions. Also, the effects involved in strategies (such as failure, state, environment) were more conveniently used with an effect type system perhaps~\cite{Filinski99}~---~as opposed to explicit monad transformers. A Haskell 20XX with a very open type system would be of use here. % \smallskip % \item[Object syntax] The prime application domain of strategic programming is program analysis and transformation. Encoding rewrite steps in terms of abstract syntax is relatively inconvenient for real-world programming languages. Haskell could support concrete syntax, just as rewriting technology like ASF+SDF~\cite{OldMeta,NewMeta} does already for a long time. Stratego was already equipped with concrete object syntax~\cite{Visser02:GPCE}; Haskell has to catch up. % \smallskip % \item[Graphs] Many program analyses and transformations favour \emph{graph-based} intermediate representations. Haskell's laziness allows for cyclic data structures. Node identities have to be `managed' carefully. Constructing and transforming many-sorted graphs is difficult in Haskell. We are in need of a typeful approach that retains the convenience of pattern matching and building, and that provides us with the illusion of destructive update. % \smallskip % \item[Attribute grammars] Strategies and attribute grammars are complementary in that the former are more operational, whereas the latter are more declarative. Also, the former emphasise traversal, whereas the latter emphasise attribute dependencies. Research on a possible marriage of strategies and attribute grammars promises interesting insights. Alike strategies, attribute grammars are conveniently embedded into Haskell~\cite{MBD00}. % \smallskip % \item[Constraint programming] Another unexplored combination of worlds is the integration of programmable strategies and constraint programming, or residuation and narrowing~---~as available in a hybrid language like Curry~\cite{Curry}. Constraints could provide a versatile means to make strategies less operational, more declarative. Constraints could also provide means to narrow down the search space for strategies. % \smallskip % \item[XML \& XPath] Next to language processing on the basis of syntaxes, strategies are thought to be useful for XML document processing. Functional combinator libraries for XML processing do exist~\cite{HaXml}, but they lack the typing strength of functional strategies. It should be possible to use strategies as a means to provide the illusion of an XPath-like language for controlling fully typed XML transformations. % \end{description} \subsection*{Strategy mining \& refactoring to strategies} The modularity and conciseness of legacy Haskell programs could benefit from the strategic style of programming. This calls for `strategy mining'. There exists related work on recovering recursion schemes like folds in legacy code~\cite{VO01}. When developing and enhancing existing Haskell programs, strategic style has to be installed or improved by means of refactoring. In fact, this is a form of `refactoring to patterns'~\cite{Kierievsky2004} because the strategic style of programming can be viewed as a collection of design patterns for traversal functionality~\cite{LV02:RULE}. In both cases, entangled traversal code is turned into strategically organised traversal code. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Concluding remark} We have briefly reviewed Haskell-based support for programmable rewriting strategies. We have also briefly discussed the link between rewriting strategies and generic programming. Finally, we have listed challenges for future work on Haskellish rewriting strategies. \medskip \noindent Please, stay tuned at~\cite{Strafunski,Boilerplate}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newpage %\bibliographystyle{plain} %\bibliography{paper} \begin{thebibliography}{10} \bibitem{Strafunski} {The \Strafunski\ web site: examples, downloads, browsable library, papers, background}, 2000--2004. \newblock \url{http://www.cs.vu.nl/Strafunski/}. \bibitem{Boilerplate} {The ``\emph{Scrap your boilerplate}'' web site: examples, browsable library, papers, background}, 2003--2004. \newblock \url{http://www.cs.vu.nl/boilerplate/}. \bibitem{Augusteijn99} L.~Augusteijn. \newblock {Sorting morphisms}. \newblock In S.D. Swierstra, P.R. Henriques, and J.N. Oliveira, editors, {\em {Advanced Functional Programming, 3rd International School, Braga, Portugal, September 12-19, 1998, Revised Lectures}}, volume 1608 of {\em LNCS}, pages 1--27. Springer-Verlag, 1999. \bibitem{BKK96} P.~Borovansky, C.~Kirchner, and H.~Kirchner. \newblock {Controlling Rewriting by Rewriting}. \newblock In Meseguer \cite{RWLW96}. \bibitem{NewMeta} M.G.J. van~den Brand, Arie~van Deursen, J.~Heering, H.A.~de Jong, M.~de Jonge, T.~Kuipers, P.~Klint, L.~Moonen, P.A. Olivier, J.~Scheerder, J.J. Vinju, E.~Visser, and J.~Visser. \newblock The {ASF}+{SDF} {M}eta-{E}nvironment: a {C}omponent-{B}ased {L}anguage {D}evelopment {E}nvironment. \newblock In R.~Wilhelm, editor, {\em Proc.\ Compiler Construction (CC 2001)}, volume 2027 of {\em LNCS}, pages 365--370. Springer-Verlag, 2001. \bibitem{Beryl} D.~Clarke, J.~Jeuring, and A.~L{\"o}h. \newblock {The Generic Haskell User's Guide}, 2002. \newblock Version 1.23~---~Beryl release. \bibitem{CELM96} M.~Clavel, S.~Eker, P.~Lincoln, and J.~Meseguer. \newblock {Principles of Maude}. \newblock In Meseguer \cite{RWLW96}. \bibitem{MBD00} O.~{de Moor}, K.~Backhouse, and S.D. Swierstra. \newblock {First Class Attribute Grammars}. \newblock {\em Informatica: An International Journal of Computing and Informatics}, 24(2):329--341, June 2000. \newblock Special Issue: Attribute grammars and Their Applications. \bibitem{EF04:PADL} M.~Erwig and Z.~Fu. \newblock {Parametric Fortran~--~A Program Generator for Customized Generic Fortran Extensions}. \newblock In B.~Jayaraman, editor, {\em {Proceedings Practical Aspects of Declarative Languages (PADL 2004)}}, LNCS, Dallas, Texas, USA, 2004. Springer-Verlag. \newblock To appear. \bibitem{Filinski99} A.~Filinski. \newblock Representing layered monads. \newblock In {\em {Proceedings 26th ACM SIGPLAN-SIGACT Symposium on Principles of programming languages}}, pages 175--188, San Antonio, Texas, USA, 1999. ACM Press. \bibitem{Curry} M.~Hanus. \newblock {The \emph{Curry} web site; Curry~---~A Truly Integrated Functional Logic Language}, 2004. \newblock \url{http://www.informatik.uni-kiel.de/~mh/curry/}. \bibitem{Hinze99:HW} R.~Hinze. \newblock {A generic programming extension for Haskell}. \newblock In {\em {Proceedings 3rd Haskell Workshop, Paris, France}}, 1999. \newblock Technical report of Universiteit Utrecht, UU-CS-1999-28. \bibitem{Hinze00:POPL} R.~Hinze. \newblock {A New Approach to Generic Functional Programming}. \newblock In {\em {Proceedings 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'00)}}, pages 119--132. ACM Press, 2000. \bibitem{JJ97} P.~Jansson and J.~Jeuring. \newblock Poly{P} - a polytypic programming language extension. \newblock In {\em {Proceedings 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'97)}}, pages 470--482, Paris, France, 1997. ACM Press. \bibitem{JJ00} P.~Jansson and J.~Jeuring. \newblock {A framework for polytypic programming on terms, with an application to rewriting}. \newblock In J.~Jeuring, editor, {\em {Proceedings Workshop on Generic Programming (WGP2000), Ponte de Lima, Portugal, Technical report ICS Utrecht University, UU-CS-2000-19}}, 2000. \bibitem{Kierievsky2004} J.~Kierievsky. \newblock {\em {Refactoring to Patterns}}. \newblock Addison Wesley, 2004. \newblock To appear. \bibitem{OldMeta} P.~Klint. \newblock {A} meta-environment for generating programming environments. \newblock {\em ACM Transactions on Software Engineering and Methodology}, 2(2):176--201, 1993. \bibitem{KK04} G.~Kniesel and H.~Koch. \newblock {Static Composition of Refactorings}. \newblock In R.~L{\"a}mmel, editor, {\em {Science in Computer Programming; Special issue on program transformation}}. Elsevier Science, 2004. \newblock To appear. \bibitem{Laemmel02:WRS} R.~L{\"a}mmel. \newblock {The Sketch of a Polymorphic Symphony}. \newblock In B.~Gramlich and S.~Lucas, editors, {\em Proceedings 2nd International Workshop on Reduction Strategies in Rewriting and Programming (WRS 2002)}, volume~70 of {\em ENTCS}. Elsevier Science, 2002. \newblock 21 pages. \bibitem{Laemmel02:RULE} R.~L{\"a}mmel. \newblock {Towards Generic Refactoring}. \newblock In {\em {Proceedings 3rd ACM SIGPLAN Workshop on Rule-Based Programming RULE'02}}, Pittsburgh, PA, USA, October 2002. ACM Press. \newblock 14 pages. \bibitem{Laemmel03:JLAP} R.~L{\"a}mmel. \newblock {Typed Generic Traversal With Term Rewriting Strategies}. \newblock {\em Journal of Logic and Algebraic Programming}, 54:1--64, 2003. \newblock Also available as arXiv technical report cs.PL/0205018. \bibitem{LPJ03} R.~L{\"a}mmel and S.~{Peyton Jones}. \newblock Scrap your boilerplate: a practical design pattern for generic programming. \newblock {\em ACM SIG{\-}PLAN Notices}, 38(3):26--37, March 2003. \newblock Proceedings ACM SIGPLAN Workshop on Types in Language Design and Implementation (TLDI~2003). \bibitem{LPJ04} R.~L{\"a}mmel and S.~{Peyton Jones}. \newblock Scrap more boilerplate: reflection, zips, and generalised casts. \newblock In {\em {Proceedings of the 9th {ACM} {SIGPLAN} International Conference on Functional Programming ({ICFP}-04)}}, 2004. \newblock 12 pages; To appear. \bibitem{EOSP} R.~L{\"a}mmel, E.~Visser, and J.~Visser. \newblock {The Essence of Strategic Programming}. \newblock Draft; Available at \url{http://www.cwi.nl/~ralf}, 2002--2004. \bibitem{LV02:RULE} R.~L{\"a}mmel and J.~Visser. \newblock {Design Patterns for Functional Strategic Programming}. \newblock In {\em {Proceedings 3rd ACM SIGPLAN Workshop on Rule-Based Programming RULE'02}}, Pittsburgh, USA, October 2002. ACM Press. \newblock 14 pages. \bibitem{LV02:justtwo} R.~L{\"a}mmel and J.~Visser. \newblock {Strategic polymorphism requires just two combinators!} \newblock Technical Report cs.PL/0212048, arXiv, December 2002. \bibitem{LV02:PADL} R.~L{\"a}mmel and J.~Visser. \newblock {Typed Combinators for Generic Traversal}. \newblock In S.~Krishnamurthi and C.R. Ramakrishnan, editors, {\em {Proceedings Practical Aspects of Declarative Languages (PADL 2002)}}, volume 2257 of {\em LNCS}, pages 137--154, Portland, OR, USA, January 2002. Springer-Verlag. \bibitem{LV03:PADL} R.~L{\"a}mmel and J.~Visser. \newblock {A Strafunski Application Letter}. \newblock In V.~Dahl and P.~Wadler, editors, {\em {Proceedings Practical Aspects of Declarative Languages (PADL 2003)}}, volume 2562 of {\em LNCS}, pages 357--375, New Orleans, LA, USA, January 2003. Springer-Verlag. \bibitem{LRT03} H.~Li, C.~Reinke, and S.~Thompson. \newblock Tool support for refactoring functional programs. \newblock In {\em Proceedings ACM SIGPLAN Workshop on Haskell}, pages 27--38, Uppsala, Sweden, 2003. ACM Press. \bibitem{LV97} B.~Luttik and E.~Visser. \newblock {Specification of Rewriting Strategies}. \newblock In M.P.A. Sellink, editor, {\em {2nd International Workshop on the Theory and Practice of Algebraic Specifications (ASF+SDF'97)}}, Electronic Workshops in Computing. Springer-Verlag, November 1997. \bibitem{MFP91} E.~Meijer, M.~Fokkinga, and R.~Paterson. \newblock {Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire}. \newblock In J.~Hughes, editor, {\em {Proceedings 5th ACM Conf.\ on Functional Programming Languages and Computer Architecture, FPCA'91}}, volume 523 of {\em LNCS}, pages 124--144. Springer-Verlag, Cambridge, MA, USA, August 1991. \bibitem{RWLW96} J.~Meseguer, editor. \newblock {\em {Proceedings 1st International Workshop on Rewriting Logic and its Applications, RWLW'96, (Asilomar, Pacific Grove, CA, USA)}}, volume~4 of {\em ENTCS}, September 1996. \bibitem{Paulson83} L.C. Paulson. \newblock {A Higher-Order Implementation of Rewriting}. \newblock {\em Science of Computer Programming}, 3(2):119--149, August 1983. \bibitem{SML04} G.~Sittampalam, O.~{de Moor}, and K.F. Larsen. \newblock Incremental execution of transformation specifications. \newblock In {\em {Proceedings 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2004)}}, pages 26--38, Venice, Italy, 2004. ACM Press. \bibitem{SAS99} S.D. Swierstra, P.R.A. Alcocer, and J.~Saraiva. \newblock Designing and implementing combinator languages. \newblock In S.D. Swierstra, P.R. Henriques, and J.N. Oliveira, editors, {\em {Advanced Functional Programming, 3rd International School, Braga, Portugal, September 12-19, 1998, Revised Lectures}}, volume 1608 of {\em LNCS}, pages 150--206. Springer-Verlag, 1999. \bibitem{THLPJ98} P.W. Trinder, K.~Hammond, H.-W. Loidl, and S.~{Peyton Jones}. \newblock Algorithm + {S}trategy = {P}arallelism. \newblock {\em Journal of Functional Programming}, 8(1):23--60, January 1998. \bibitem{VO01} G.~Villavicencio and J.N. Oliveira. \newblock {Reverse Program Calculation Supported by Code Slicing}. \newblock In P.~Aiken, E.~Burd, and R.~Koschke, editors, {\em {Proceedings Working Conference on Reverse Engineering (WCRE 2001)}}, pages 35--48. IEEE Computer Society Press, October 2001. \bibitem{Visser01:RTA} E.~Visser. \newblock {Stratego: A Language for Program Transformation based on Rewriting Strategies. System Description of Stratego 0.5}. \newblock In A.~Middeldorp, editor, {\em Proceedings Rewriting Techniques and Applications (RTA'01)}, volume 2051 of {\em LNCS}, pages 357--361. Springer-Verlag, May 2001. \bibitem{Visser02:GPCE} E.~Visser. \newblock {Meta-Programming with Concrete Object Syntax}. \newblock In D.~Batory, C.~Consel, and W.~Taha, editors, {\em {Generative Programming and Component Engineering (GPCE'02)}}, volume 2487 of {\em LNCS}, pages 299--315, Pittsburgh, PA, USA, October 2002. Springer-Verlag. \bibitem{VBT98} E.~Visser, Z.~Benaissa, and A.~Tolmach. \newblock {Building Program Optimizers with Rewriting Strategies}. \newblock In {\em {Proceedings ACM SIGPLAN International Conference on Functional Programming (ICFP'98)}}, pages 13--26, Baltimore, September 1998. ACM Press. \bibitem{Wadler92} P.~Wadler. \newblock The essence of functional programming. \newblock In {ACM}, editor, {\em Conference record of the Nineteenth Annual {ACM} {SIGPLAN-SIGACT} Symposium on Principles of Programming Languages, {Albuquerque, New Mexico}, {January} 19--22, 1992}, pages 1--14. ACM Press, 1992. \bibitem{HaXml} M~Wallace and C~Runciman. \newblock {Haskell} and {XML}: Generic combinators or type-based translation. \newblock In {\em {Proceedings ACM SIGPLAN International Conference on Functional Programming (ICFP'99)}}, pages 148--159, Paris, France, September 1999. ACM Press. \end{thebibliography} \end{document}