Design Patterns for Functional Strategic Programming
% \alignauthor Ralf L{\"a}mmel
\affaddr{Vrije Universiteit}
\affaddr{De Boelelaan 1081a}
\affaddr{NL-1081 HV Amsterdam}
\affaddr{The Netherlands}
\affaddr{CWI}
\affaddr{P.O. Box 94079}
\affaddr{1090 GB Amsterdam}
% In previous work, we introduced the fundamentals and a supporting combinator library for strategic programming. This an idiom for generic programming based on the notion of a functional strategy: a first-class generic function that cannot only be applied to terms of any type, but which also allows generic traversal into subterms and can be customized with type-specific behaviour. This paper seeks to provide practicing functional programmers with pragmatic guidance in crafting their own strategic programs. We present the fundamentals and the support from a user's perspective, and we initiate a catalogue of strategy design patterns. These design patterns aim at consolidating strategic programming expertise in accessible form. %
abstract.tex
\begin{abstract} 
%
In previous work, we introduced the fundamentals and a supporting
combinator library for \emph{strategic programming}. This an idiom for
generic programming based on the notion of a \emph{functional
strategy}: a first-class generic function that cannot only be
applied to terms of any type, but which also  allows generic
traversal into subterms and can be customized with type-specific
behaviour.

This paper seeks to provide practicing functional programmers with
pragmatic guidance in crafting their own strategic programs. We
present the fundamentals and the support from a user's perspective,
and we initiate a catalogue of \emph{strategy design patterns}. These
design patterns aim at consolidating strategic programming expertise
in accessible form.
%
\end{abstract}
catalog.tex
%\section{Catalog}
%
%In this section we capture strategic programming expertise in a set of
%\emph{design patterns}. Each pattern systematically names, motivates,
%and explains a general design for addressing certain recurring program
%construction problems.


%
% Basic patterns
%
\input{RewriteStep}
\input{GenericRewriteStep}
\input{Traversal}
\input{KeyholeOperation}
\input{SuccessAndFailure}
\input{Circuitry}
\input{RolePlay}
%
% Elaborated patterns
%
\input{TraversalScheme}
\input{LocalEffect}
%\input{LambertsCrush}
\input{Propagation}
\input{GenericContainer}
\input{TypeArgument}
\input{MetaScheme}



%\input{StagedTraversal}
%\input{LittleResultLanguage}
%\input{TraversalCombinator}
%\input{DBC}




Circuitry.tex
\begin{cpattern}{Circuitry}{Basic}
%\pitem{Aka}
%  ...
\pitem{Intent}
%
  Use composition and recursion to assemble strategies into a
  composite traversal with appropriate control and data flow.
%
\pitem{Motivation}
  When composing traversals, one should take care to sequence the
  ingredient steps in the right order, to pass data to the steps that
  need them, and to traverse the appropriate parts of the input
  term. By connecting your steps with appropriate combinators and
  recursive calls you can wire up the control and data flow between
  them.
%
\pitem{Schema}
%
\input{snip/circuitry-schema.math}
%
\pitem{Description}
%
  Typical choices for the composition operators $\mathit{co}_i$ are
  the \emph{seq}, \emph{let}, and \emph{choice} combinators. The
  \emph{seq} operators are used to prefix a strategy with a
  type-preserving strategy. The \emph{let} operators are used to
  compute a value via a type-unifying strategy and to pass it on. The
  \emph{choice} operators are meant for branching control-flow. All
  the composed strategies potentially include recursive references to
  \emph{strategy}.
%
%\pitem{Consequences}
%
%
\pitem{Sample code}
%
\input{snip/circuitry-sample.math}
%
The above strategy performs free variable analysis on arbitrary
Haskell program fragments. Free variables are obtained by subtracting
(cf.\ ``$\mathbin{\char92 \char92 }$'') the locally declared variables
\emph{decs} from the \emph{union} of the locally referenced variables
\emph{refs} and the free variables \emph{frees} from the subterms. We
use two generic rewrite steps \emph{refHsVars} and \emph{decHsVars}
for the identification of declaring and referring occurrences of
Haskell variables. The strategy is recursively defined to descend into
terms via \emph{allTU}. The \emph{letTU} combinator is used to connect
all the type-unifying computations.
%
%\pitem{Implementation}
%
%
\pitem{Related Patterns}
  The \textsc{Success by Failure} pattern shows how partiality of
  strategies can be modeled, and how it can be used to realize
  branches in the control and data-flow between your strategic
  components.
%
\end{cpattern}

concluding.tex
\section{Conclusion}



\paragraph{Contribution}

We have identified 6 basic and 7 advanced design patterns for generic
programming with functional strategies. A programmer who knows just
the basic ones will already to a large extent be able to take
advantage of the Strafunski style of generic programming. These
patterns are not far removed from the combinatorial styles of
programming familiar to most functional programmers. Their added value
is in the mixture of genericity and specificity, and in the support
for generic traversal. By employing generic traversal, one can
concisely deal with large syntaxes, formats and systems of datatypes.
In addition to the basic ones, we have indicated an open-ended list of
advanced design patterns that deal with sophisticated means of
parameterization, composition and representation. We extracted the
basic and advanced patterns from our applications in strategic
programming, e.g., from those discussed in
\cite{LV02-PADL,Essence,Laemmel02-TGR,KL02-FDT}. These applications
deal with program analyses and transformations for various languages
such as Cobol, Haskell, and Java.



\paragraph{Related work}

\begin{Description}
%
\Ditem{Object-oriented design patterns}
%
  We have taken our inspiration from the literature on object-oriented
  design patterns~\cite{GHJV94}. As indicated in
  Section~\ref{S:patterns}, we have made some modifications to
  accommodate the characteristics of functional programming. A general
  comparison reveals further differences. The object-oriented design
  patterns are predominantly concerned with code organization,
  distribution of responsibilities over classes and objects, tuning
  dependencies to maximize variability and maintainability. The
  functional design patterns are more concerned with issues of
  behaviour, parameterization, and reusability. We conjecture that
  these differences are (partly) due to the available abstraction
  mechanisms in both paradigms.  As an aside, functional programming
  idioms have served as a source of inspiration for the formulation of
  some object-oriented design patterns \cite{Kuehne99}. The resulting
  patterns even have partly to do with generic traversal. 
%  This is a
%  further indication that design patterns for generic functional
%  programming are in place.
%
\Ditem{Further functional design patterns}
%
  Our catalogue of patterns aims to communicate expertise in deploying
  the combinators of Strafunksi's strategy library. A range of
  combinator libraries are in existence, and these may profit from design
  patterns to give guidance to their users. These include libraries
  for parsing~\cite{JFP::Page1998},
  pretty-printing~\cite{HughesJohn1995c}, and polytypic
  programming~\cite{JJ98}. For language
  embedding~\cite{swierstra98designing} and sorting
  morphisms~\cite{Augusteijn99} presentations have been given in a way
  that primary `usage patterns', and recurring problems are
  discussed in some free format. One can recently observe an emerging
  interest to define patterns for functional programming (see the
  initiative \cite{HsPatterns}). In addition to the aforementioned
  domains, We envision that the following themes will definitely
  benefit from a design-pattern approach of explanation:
%
\begin{itemize}
\item programming with monad transformers,
\item strictification,
\item first-class polymorphism,
\item dynamic typing,
\item parallel and distributed programming.
\end{itemize}
%
%\Ditem{Generic programming}
%
\begin{comment}
  The Strafunski style of generic programming emphasizes generic
  traversal, combinator-style, mixture of genericity and specificity.
  The style is geared towards implementation of language processors,
  and transformation systems. There are several other flavours of
  generic programming, and it is not immediately clear if our design
  experience can be adopted for these other flavours, or what other
  pattern catalogue would be appropriate instead. To give an example,
  in polytypic programming~\cite{Meertens96,JJ97,BJJM99}, the notion
  of genericity is very much driven by the idea of \emph{mathematical
  program construction}. Several languages for generic programming
  lack some characteristic of strategies (recall: generic, specific,
  traversal, first-class; see introduction) crucial for the Strafunski
  style, e.g., traversal functions in \cite{BKV01} without support for
  user-definable traversal schemes, first-order as opposed to
  first-class templates in XSLT~\cite{XSLT}, single parameterized
  datatypes in PolyP~\cite{JJ97}, and Generic
  Haskell~\cite{Hinze99,HJ01} without support for type case as needed
  for the \emph{adhoc} combinators. This implies that the our patterns
  are language- and style-dependent as it is the case for most pattern
  catalogues.
\end{comment}
%
\end{Description}



\paragraph{Future work}

%
\begin{Description}
%
\Ditem{Functional program refactoring}
%
Further inspiration can be taken from the object-oriented
literature. The notion of \emph{refactoring}~\cite{OpdykePhD,Fowler99}
seems particularly helpful. This is also proposed in \cite{1334}.
In~\cite{Laemmel00-SFP99}, the first author motivates and specifies a
few functional program refactorings. The style and vocabulary employed
in our functional pattern catalogue can serve as a starting point for
the elaboration of a catalogue of refactorings for functional
programs. In some pattern descriptions we have already hinted at how
one design can be transformed into another, e.g., to extract a
\textsc{Traversal Scheme} from an application-specific
\textsc{Traversal}. The formal foundations of functional program
transformation are reasonably well-understood~\cite{BD77,PP96} but a proper
catalogue of refactorings is not available. This is true in particular
for refactoring generic programs.
%
\Ditem{Language processors as functional programs}
%
Our impression is that functional strategies are very appropriate for
language processing in general (i.e., refactoring tools, program
optimizers, program analysers, metrics tools, etc.), and for
\emph{functional} language processing, in particular---as indicated by
several Haskell examples in this paper, but see
also~\cite{KL02-FDT}. The design patterns we presented should provide
guidance to the functional language implementor and tool developer in
applying strategies in these domains.
%
\end{Description}
 


GenericContainer.tex
\begin{cpattern}{Generic Container}{Advanced}
%\pitem{Aka}
%  ...
%
\pitem{Intent}
%
  Use a strategy as a generic data container.
%
\pitem{Motivation}
%
  Sometimes terms of different types need to be stored in the same
  container. Such a generic container can be modelled with strategies.
%
\pitem{Schema}
%
\input{snip/generic-container-schema.math}
%
\pitem{Description}
%
  Just as monomorphic functions can be used to represent homogeneous
  data structures such as maps and sets, strategies can be used as
  heterogeneous data structures. Define your generic container type as
  a data structure that involves a strategy type $S$. Define the
  operations on your container in terms of strategy combinators.
  Operations modifying a container involve function modification
  lifted to the strategy level. Looking up data from a container
  involves strategy application.
%
\pitem{Sample code}
%
\input{snip/generic-container-sample.math}
%
  The type \emph{Coder} assigns unique integers to terms of arbitrary
  types. It contains a counter as first component that records the
  highest code issued so far. The second component is a type-unifying
  strategy which represents the mapping from terms to codes assigned
  so far.  We can provide an initial coder with \emph{no} codes
  assigned, \emph{get} a code of a term, \emph{set} the code for a
  term, and generate the \emph{next} code. When a given term is
  \emph{enCode}n, the \emph{Coder} is only modified if no code was
  previously assigned to the term.
%
\pitem{Consequences}
%
  Generic containers can be made observable only per type, i.e.,
  element retrieval or enumeration can only be done if the type of
  the elements are provided as input.
%
%\pitem{Implementation}
%  ...
%
\pitem{Related Patterns}
%
  Container operations are usually \textsc{Keyhole Operation}s.
%
\end{cpattern}

GenericRewriteStep.tex
\begin{cpattern}{Generic Rewrite Step}{Basic}
%
%\pitem{Aka}
%  ...
\pitem{Intent}
%
  Lift type-specific rewrite steps to the strategy level,
  making them applicable to terms of all types.
%
\pitem{Motivation}
%
  Each individual rewrite step captures a computation that deals with
  data of a single type. At some point in the synthesis of generic
  programs, type-specific rewrite steps need to be made generic. This
  involves the composition of possibly several type-specific rewrite
  steps (for different types) and the indication of a generic default
  for all the types that are not covered by the type-specific
  computations.  This entire composition is called a generic rewrite
  step.
%
\pitem{Applicability}
  The non-generic rewrite steps composed into a generic one must be
  specific for \emph{different} types. To compose rewrite steps that
  are specific for the same type, use the \emph{choice} combinator,
  following \textsc{Success By Failure}.
\pitem{Schema}
%
\input{snip/generic-rewrite-step-schema.math}
%
\pitem{Description}
%
  To compose rewrite steps $s_1$, \ldots, $s_n$ for different types
  into a strategy for \emph{any} type, use (repeated application of)
  the \emph{adhoc} combinators. Start from a default strategy
  \emph{def} to deal with all types not covered by $s_1$, \ldots,
  $s_n$. Typical defaults are the strategies \emph{fail},
  \emph{identity}, or \emph{build}. Since strategies are always
  monadic entities in Strafunski, you must make the specific rewrite
  steps monadic, if they are not yet by themselves. The
  \emph{identity} monad is the most basic choice.
%
%\pitem{Consequences}
%  ...
\pitem{Sample code}
%
\input{snip/generic-rewrite-step-sample.math}
%
  In this sample we reuse the type-specific rewrite steps
  \emph{decTypes} and \emph{refTypes} that illustrate the
  \textsc{Rewrite Step} pattern. These steps are specific to the types
  \emph{HsDecl} and \emph{HsType}. We combine them into a single
  generic rewrite step with $\mathit{build}\ [\,]$ as default. The
  composed function identifies type constructor names in a given term,
  both in declaration and use sites. The chosen generic default
  specifies that the empty list should be returned when faced with
  terms of any other type than \emph{HsDecl} or \emph{HsType}. The
  non-generic rewrite steps are made monadic by composing them with
  \emph{return}. We have opted for the trivial \emph{Identity} monad.
%
%\pitem{Implementation}
%  ...
\pitem{Consequences}
  By making a rewrite step generic, it can be applied to terms of any
  type, and it becomes amenable to specialization with further
  type-specific behaviour.
\pitem{Related Patterns}
  Lifting rewrite steps to the strategy level, i.e., turning them into
  generic rewrite steps is a prerequisite for passing them as
  arguments to a \textsc{Traversal Scheme}, and for using them as
  building blocks in \textsc{Circuitry}.
\end{cpattern}

guide.tex
\section{Design patterns}
\label{S:patterns}

The novelty of the strategic programming idiom implies that few are
experienced and well-versed in it. Though Strafunski's library
provides an extensive array of predefined strategy combinators,
deployment of these combinators for program construction is an acquired
skill, as is any (functional) programming style. In this section, we
attempt to convey our (limited) deployment expertise in a set of
\emph{design patterns}.

\paragraph{What is a design pattern?}

The notion of a \emph{design pattern} is well-established in
object-oriented programming. In the first pattern catalogue, design
patterns are defined as \emph{``descriptions of communicating objects
and classes that are customized to solve a general design problem in a
particular context''}~\cite[page 3]{GHJV94}. Each pattern
systematically names, motivates, and explains a common design
structure that addresses a certain group of recurring program
construction problems. After the initial 23 patterns of the first
catalogue, numerous further patterns have been described in roughly
the same style and format.

We contend that design patterns can be an effective means of
consolidating and communicating program construction expertise for
functional programming just as they have proven to do in
object-oriented programming. Of course, a few modifications are in
order to accommodate the characteristics of functional programming and
the space limitations of this
publication. Figure~\ref{Fig:pattern-template} shows the format we
have chosen to describe each pattern.
%
\begin{figure}
\begin{Pattern}{Name}{Category}
\pitem{Aka*}
Alternative names.
\pitem{Intent}
Short statement of the pattern's purpose.
\pitem{Motivation}
Description of a particular design problem and a brief indication of
how the pattern can be used to solve it.
\pitem{Applicability*}
Preconditions for using the pattern.
\pitem{Schema}
A schematic code fragment that indicates the participants in the
pattern and their relationships.
\pitem{Description}
Explanation of the schema that details the responsibilities of all
participants and describes how they collaborate to carry them out.
\pitem{Sample code}
Actual working Haskell code in which the pattern is
used.
\pitem{Consequences*}
Description of the results and trade-offs of applying the pattern.
%\pitem{Implementation*}
%Technical details one should be aware of when implementing the
%pattern.
\pitem{Related patterns*}
Similarities, differences, and connections to other patterns.
\end{Pattern}
\vspace{-3ex}
\caption{Format of each design pattern description.}
\label{Fig:pattern-template}
\end{figure}
%
This format is very similar to the one known from object-oriented
literature. We have chosen to make particular items optional
(indicated by an asterisk). Also, the diagrams of object-oriented
class structures seem to have no obvious functional counterparts, so
we provide schematic Haskell code fragments instead. Finally, it seems
that the conciseness of functional programming with respect to
object-oriented programming carries over to our strategic design
patterns.



\begin{figure}[ht!]
\begin{center}
\begin{tabular}{|l|l|}
\hline
Pattern
	& Concerns\\
\hline\hline
\textsc{Rewrite Step}
	& non-generic computation step\\\hline
\textsc{Generic Rewrite Step}
	& generic computation step\\\hline
\textsc{Traversal}
	& traversal behaviour \emph{vs.}\\
        & computation step\\\hline
\textsc{Keyhole Operation}
	& strategic behaviour \emph{vs.}\\
        & strategy-free interface\\\hline
\textsc{Success by Failure}
	& traversal control\\\hline
\textsc{Circuitry}
	& control- and data-flow \emph{vs.}\\
	& computation steps\\\hline
\textsc{Role Play}
	& analyses \emph{vs.} guards \emph{vs.}\\
	& side-effects \emph{vs.} transformations\\\hline
\textsc{Traversal Scheme}
	& purely generic traversal behaviour\\\hline
\textsc{Propagation}
	& environment passing\\\hline
\textsc{Local Effect}
	& effectful behaviour \emph{vs.}\\
	& effect-free interface \\\hline
\textsc{Generic Container}
	& heterogeneous datatypes \\\hline
\textsc{Type Argument}
	& type-specific behaviour \emph{vs.}\\
	& specifically typed values \\\hline
\textsc{Meta Scheme}
	& skeleton of a traversal scheme\\\hline
\end{tabular}
\end{center}
\vspace{-3ex}
\caption{Concerns that each pattern isolates or separates.}
\label{Fig:variability}
\end{figure}



\paragraph{Organizing the catalogue}

Each design pattern is aimed at solving only a single design
problem. Clearly, in actual applications design problems never come
alone, and combinations of patterns must be used. The selection of
appropriate design patterns for a given set of design problems can be
guided by categorizing the patterns according to various criteria.  We
briefly discuss three such criteria.

Firstly, we have divided our design patterns into two main groups:
%
\begin{Description}
\Ditem{Basic}
  Patterns in this group address design problems encountered by any
  strategic programmer. Required reading.
\Ditem{Advanced}
  Patterns in this group address less frequent design problems. Read
  these when you are ready to bring your strategic programming skill
  to a higher level.
\end{Description}

Secondly, each design pattern can be characterized by the kind of
isolation and separation of concerns that can be accomplished with
them. Figure~\ref{Fig:variability} provides an overview. To give an
example, the design pattern \textsc{Traversal Scheme} isolates the
concern of purely generic traversal behaviour in the sense that all
type-specific behaviour will be supplied by the instantiation of a
traversal scheme.

Thirdly, we can categorize by used means of parameterization. We can
classify the parameters of functional strategies with respect to
several dimensions: (i) whether it is monomorphic or polymorphic, (ii)
whether explicit quantification inside the strategy type is used, or
implicit quantification at the top level, (iii) whether it is intended
to contribute type-specific behaviour, (iv) whether it is intended to
involve traversal behaviour, and (v) what its order and arity are. To
give an example, let us sketch how a traversal over some
application-specific data is organized according to the design pattern
\textsc{Traversal}. We first select for instance a traversal scheme
with one strategy argument. So it is a unary first-order strategy
combinator (see v). The strategy argument is polymorphic (see i), and
it is explicitly quantified (see ii). The argument is supposed to
contribute type-specific behaviour (see iii), but traversal behaviour
is not mandatory (see iv). Parameterization is the prime abstraction
mechanism offered by functional programming. The strategy design
patterns help a generic programmer to put this abstraction mechanism
to work.






introduction.tex
\section{Introduction}

Strategic programming is a novel generic programming idiom in which
the notion of a \emph{strategy} plays a crucial
role~\cite{Essence}. In~\cite{LV02-PADL}, we presented a realization
of the strategic programming idiom in the functional programming
paradigm, and we introduced the notion of a \emph{functional
strategy}. A functional strategy is a function with the following
characteristics:
%
\begin{Description}
\Ditem{generic}
  It can work on arguments of \emph{any} type.
\Ditem{specific}
  For specific types it can display customized behaviour.
\Ditem{traversal}
  It can traverse into subterms.
\Ditem{first-class}
  It can be named, passed as argument, etc.
\end{Description}
%
The example in Figure~\ref{Fig:example} illustrates these
characteristics.  The function $\mathit{increment}$ is a functional
strategy that increments all integers in a data structure by 1,
regardless of the type of the data structure and of where the integers
occur. This is demonstrated by its application to terms of type
$\mathit{[(Bool,Int)]}$ and $\mathit{Maybe\;(Int,([Int],Int))}$. The
functions $\mathit{topdown}$, $\mathit{adhoc}$, and
$\mathit{identity}$ are library combinators that will be discussed in
more detail in Section~\ref{S:Strafunski}.
%
\begin{figure}
\begin{boxedminipage}{\linewidth}
\input{snip/increment.math}\hfill\vspace{-75\in}
\end{boxedminipage}
\vspace{-3ex}
\caption{Example of a functional strategy.}
\label{Fig:example}
\end{figure}

As the example illustrates, the expressiveness of functional
strategies goes beyond that of ordinary parametrically polymorphic and
ad-hoc polymorphic functions. Note that \emph{increment} is
essentially of type $\forall \alpha.\ \alpha \to \alpha$. 
%
The only parametrically polymorphic inhabitant of this type is the
identity function, to which \emph{increment} is clearly not
equivalent.
%
Ad-hoc polymorphism is usually based on overloaded function
declarations, but \emph{increment} is composed by customizing
\emph{identity} with \emph{inc} using a function
\emph{combinator}, namely \emph{adhoc}.
%
The most direct way to type strategies involves the use of rank-2
types to point out that strategy combinators operate on generic
functions. Alternatively, one can use first-class polymorphism or
dynamic typing. In any case, additional effort is required to cope
with traversal and type-specific customization. In Haskell, a range
of different encodings are feasible~\cite{LV02-PADL,Laemmel02-SPS}.
%
In the current paper, however, we will consider the types of
strategies as \emph{abstract}; we will not be bothered with their
definition, only their use.

Strategic programming, i.e., program construction with strategies,
constitutes a novel generic programming idiom with numerous benefits.
It helps to attain separation of concerns, reusability, robustness,
and conciseness when dealing with many-sorted data structures, such as
documents and parse trees. The additional expressiveness of strategic
programming has proven to pay off in application areas such as program
transformation and analysis~\cite{JVV2000a}, reverse
engineering~\cite{DV02-IWPC}, and grammar engineering~\cite{Essence}.

Strafunski\footnote{\url{http://www.cs.vu.nl/Strafunski}} is a
Haskell-based bundle that supports generic programming with functional
strategies. It contains an extensive library of reusable strategy
combinators which can be composed, customized, and applied to
construct application programs.

To effectively make use of the power that the idiom of strategic
programming offers, more is needed than a combinator
library. Deployment expertise must be gathered through practical
experience, and consolidated in accessible form. In this paper, we
take the perspective of the working functional programmer who wants to
employ strategies. In Section~\ref{S:Strafunski}, we review the
fundamentals of strategies and we outline Strafunski's support for
development of and with strategies. In Section~\ref{S:patterns} we
present a catalogue of strategy design patterns. Each pattern is
illustrated with code samples. Rather than choosing a trivial syntax
to be processed by our sample strategies, or an arbitrary language, we
have chosen samples dealing with the analysis or transformation of
Haskell programs.\footnote{The corresponding system of datatypes is
given in the appendix.}





KeyholeOperation.tex
\begin{cpattern}{Keyhole Operation}{basic}
%
\pitem{Aka}
  Wrapper Worker
%
\pitem{Intent}
%
  Do not expose strategies to the top level.
%
\pitem{Motivation}
%
  In the Strafunski-style, strategies are generic functions, subject to
  function application via \emph{applyTP} and \emph{applyTU}. When
  they serve as argument or result, this can be observed via the
  types \emph{TP} and \emph{TU}. If you want to use strategies without
  exposing them to the outside, you can use a keyhole operation. On
  the inside, you can dispose of the full power of strategies, while
  on the outside, all you see is a plain function without any
  trace of \emph{TP} or \emph{TU}.
%
\pitem{Schema}
%
\input{snip/keyhole-operation-schema.math}
%
\pitem{Description}
%
  Divide the functionality of your algorithm over a top-level
  \emph{wrapper} function which directly operates on terms, and a
  nested \emph{worker} strategy.  Use \emph{adhoc} when specific
  argument strategies are used in the definition of the worker. Use
  \emph{apply} to define the specific wrapper in terms of the generic
  worker.
%
\pitem{Sample code}
%
\input{snip/keyhole-operation-sample.math}
%
  The operation \emph{isFreshType} implements a predicate to test if a
  certain type constructor name $n$ is fresh (i.e., not yet used) in a
  given Haskell module. Note that this is a completely monomorphic
  function. The wrapped worker is basically the traversal
  \emph{allTypes} that illustrates the \textsc{Traversal} pattern but
  postfixed by a membership test \emph{isNotElem}. After wrapping the
  worker we further postprocess the result with \emph{runIdentity} to
  get out of the trivial \emph{Identity} monad. The second example
  above deals with selection of terms from a focus where the helper
  \emph{getFocus} for focus detection is passed to a keyhole
  operation. Internally, the traversal scheme \emph{select} is used.
%
\pitem{Consequences}
  With a keyhole operation you fit a non-generic interface on generic
  functionality. This means you can apply the wrapper function with
  ordinary function application, instead of using \emph{apply}. On
  the other hand, if you want to pass the generic functionality to a
  traversal scheme, or update it with \emph{adhoc}, you will have to
  go around the wrapper and use the worker directly.
%
%\pitem{Implementation}
%  The generic worker can be hidden differently than by nesting it
%  inside the wrapper, e.g.\ by putting it inside a module that does
%  not export it. This way, the worker can be reused, updated and
%  applied generically within the scope of the module.
%\pitem{Related Patterns}
%  ...
\end{cpattern}


LocalEffect.tex
\begin{cpattern}{Local Effect}{Advanced}
%\pitem{Aka}
%  ...
\pitem{Intent}
  Do not expose monadic effects beyond where they are needed.
\pitem{Motivation}
  Effects such as partiality, non-determinism, and state can be used in
  strategic programming by employing appropriate (stacked) monads. Often, such
  effects are only needed locally. With a local effect you can prevent locally
  needed monads to pollute the rest of your program.
\pitem{Schema}
%\begin{verbatim}
% effectful  :: TP MEffect
% effectful  =  .. effect ..
% 
% effectless :: TP M
% effectless =  msubstTP m2m effectful
%               where m2m :: MEffect -> M
%                     m2m =  return . runME
%\end{verbatim}
%
  \input{snip/local-effect-schema.math}  
%
\pitem{Description}
  Implement the functionality that requires an effect in a combinator
  that exposes the corresponding monad \emph{MEffect}. Call this
  $\mathit{effectful}$ combinator from a second combinator that
  exposes a different monad \emph{M}, without the effect. Use the
  $\emph{msubst}$ combinator to substitute one monad by the other,
  using a function $\mathit{m2m}$ that runs the effectful computation and
  returns its value inside the monad without effect. Instead of using
  unrelated monads, you can construct \emph{MEffect} by applying a
  monad transformer to \emph{M}. The function $\mathit{m2m}$ should then
  `unlift' the transformed monad to recover the original monad.
%\pitem{Consequences}
%
\pitem{Sample code}
%
  \input{snip/local-effect-sample.math}
%
  The \emph{deBruijn} strategy replaces all Strings in a given input
  term by unique identifiers, starting with \texttt{\char34 1\char34}, and then adding a prime at each step. Internally, a state
  monad transformer is used to keep track of the most recently
  generated identifier. Externally, i.e., looking at the type of
  \emph{deBruijn}, there is no trace of this state monad. This is
  accomplished with the \emph{localStT} combinator, which converts a
  strategy that employs a monad with state transformer into a strategy
  on the same monad, without the transformer. The parameter \emph{s}
  represents the initial state. The conversion is accomplished by calling 
  \emph{msubstTP} with a function \emph{unlift}
  that evaluates the state transformer initialized with $s$.


%  
%\pitem{Implementation}
%  Monad transformers allow an effect to be added to a given monad. 
\pitem{Consequences}
  Localizing a monadic effect can improve not only readability of your
  code. The performance of your program may benefit as well.
\end{cpattern}

MetaScheme.tex
\begin{cpattern}{Meta Scheme}{Advanced}
%
%\pitem{Aka}
%  ...
\pitem{Intent}
%
Parameterize an algorithm by higher-order strategies.
%
\pitem{Motivation}
%
  The most basic and common way in which strategy combinators are
  parameterized is by plain strategies, i.e., constant
  combinators. This kind of parameterization is heavily used for
  traversal schemes to separate out type-specific behaviour. A more
  flexible algorithm can be obtained if a meta-scheme is established,
  i.e., when some parameters are non-constant combinators
  themselves. This allows you to vary, for instance the traversal
  scheme employed by an algorithm or the composition operators of its
  circuitry.
%
\pitem{Schema}
%
\input{snip/meta-scheme-schema.math}
%
\pitem{Description}
%
  Parameterize your strategy definition by strategy combinators.
  There is potential for binary combinator arguments $b_1$, \ldots,
  $b_n$, unary combinator arguments $u_1$, \ldots, $u_m$, and plain
  strategy arguments $s_1$, \ldots, $s_k$. Combinators with more than
  two arguments are possible as well but note that all basic strategy
  combinators and most library schemes are unary or binary.
%
  You can introduce parameters for aspects such as traversal control,
  data-flow and control-flow.
% 
  When you instantiate the higher-order parameters of a meta-scheme,
  you are turning it into a plain traversal scheme.
%
%\pitem{Consequences}
%  ...
\pitem{Sample code}
%
\input{snip/meta-scheme-sample.math}
%
  The combinator \emph{traverse} is a highly parameterized traversal
  scheme. It is parameterized in a binary combinator $o$ for the
  composition of node processing and recursive descent. It is further
  parameterized in a unary combinator $t$ to control the traversal in
  the sense of how to descend into subterms. Finally, \emph{traverse}
  carries a nullary strategy argument $s$ for node processing. Note
  that \emph{traverse} is still neutral with respect to
  type-unification vs.\ type-preservation. In fact, the instantiations
  of \emph{traverse} employ the overloaded basic strategy combinators
  according to Strafunski's \emph{OverloadingTheme}, e.g., \emph{allS}
  and \emph{choiceS}. We use the postfix ``...\emph{S}'' to point out
  overloading as opposed to commitment to either \emph{TP} or
  \emph{TU}. The first instantiation \emph{totaltdS} can be resolved
  to an equivalent of either the type-preserving \emph{topdown} or the
  type-unifying \emph{crush} from Strafunski's \emph{TraversalTheme}
  (see Figure~\ref{Fig:themes}).
%
%\pitem{Implementation}
%  ...
%\pitem{Related Patterns}
%  ...
\end{cpattern}

paper.tex
%\documentclass{acm_proc_article-sp}
\documentclass{sig-alternate-no-pb}

\usepackage{times}
\usepackage{graphics}
\usepackage{verbatim}
\usepackage{alltt}
\usepackage{moreverb}
\usepackage{url}
%\usepackage{html}
\usepackage{xspace}
\usepackage{new-commands}
\usepackage{boxedminipage}
\usepackage{lhs2TeXPreamble}

\renewcommand{\qquad}{\hspace{40\in}}

\hyphenation{else-where}

%%


\begin{document}

\title{Design Patterns for Functional Strategic Programming}

\numberofauthors{2}
\author{%
\alignauthor Ralf L{\"a}mmel\\
	\affaddr{Vrije Universiteit}\\
	\affaddr{De Boelelaan 1081a}\\
	\affaddr{NL-1081 HV Amsterdam}\\
	\affaddr{The Netherlands}\\
	\email{ralf@cs.vu.nl}
\alignauthor Joost Visser\\
	\affaddr{CWI}\\
	\affaddr{P.O. Box 94079}\\
	\affaddr{1090 GB Amsterdam}\\
	\affaddr{The Netherlands}\\
	\email{Joost.Visser@cwi.nl}
}

\date{}
\maketitle


\input{abstract}
\input{introduction}
\input{strafunski}
\input{guide}
\clearpage
\input{catalog}
\input{concluding}

%\section{Pattern Assessment}
%
%\input{assessment}
%
%\input{old-stuff}
%
%\bigskip
%
%
%\noindent
%\textbf{Acknowledgement}
%

\bibliographystyle{abbrv}
\bibliography{paper}

\newpage
\appendix

%This appendix is provided for the convenience of the reviewers.

The following Haskell datatypes approximate the Haskell~98 abstract
syntax as defined in the \emph{hsparser} project ({\scriptsize
\url{http://www.pms.informatik.uni-muenchen.de/mitarbeiter/panne/haskell_libs/hsparser.html}}). In
the sample code in the paper, we refer to these datatypes. They are
included here for easy reference.

Note that the mere size of this grammar, i.e., the number of types and
data constructors, clearly demonstrates the benefits of
\emph{robustness} and \emph{conciseness} of strategic
programming. While our sample code includes non-trivial functionality
for the entire Haskell syntax, only a handful of the types and
data constructors needed to be mentioned explicitly.
%
%We
%included the datatypes for convenience so that the reader can verify
%the Haskell patterns in the text. Also, just the mere size of this
%grammar and the many sorts of program fragments indicate that generic
%programming is indispensable if a non-trivial language syntax needs to
%be processed.

\bigskip

\noindent
{\scriptsize%
\input{snip/hsparser.math}
}

\end{document}

Propagation.tex
\begin{cpattern}{Propagation}{Advanced}
%
\pitem{Aka}
%
  Hand Me Down
%
\pitem{Intent}
%
  Propagate data downwards into the traversed tree.
%
\pitem{Motivation}
%
  What you do with lower nodes in the tree might be dependent on
  information collected or constructed at higher nodes. With
  Propagation, such information is handed down via a parameter of the
  recursive call of a traversal.
%
\pitem{Schema}
%
\input{snip/propagation-schema.math}
%
\pitem{Description}
%
  To add data propagation behaviour to a traversal, you should first
  parameterize the node action(s) of your traversal with the type of
  this data. Furthermore, you should add two parameters to your
  \emph{traversal}. First, initial data to start the traversal with.
  Second, a function to modify the data at each step downward during
  traversal. This function takes current data and current node as
  input, and computes new data. At each node, three things
  happen. Firstly, the node \emph{action} is applied, using the
  current data $e$. Secondly, the current data is modified. Thirdly,
  the new data is used in a recursive call of the complete
  \emph{traversal}.
%
%\pitem{Consequences}
%  ...
\pitem{Sample code}
%
\input{snip/propagation-sample.math}
%
  The shown strategy combinator unites propagation with selection.  It
  is an elaboration of the simpler traversal scheme \emph{select}. It
  uses \emph{choiceTU} and \emph{oneTU} in the same manner as
  \emph{select} (see Figure~\ref{Fig:themes}). All the additional
  behaviour directly implements the \textsc{Propagation} pattern. The
  \emph{selectenv} combinator is used in program analyses when a
  type-unifying node processor relies on environment propagation,
  e.g., to maintain bound variables along the way down to a focused
  fragment. For other predefined traversal schemes, a propagating
  version can be given in a similar way.
%
%\pitem{Implementation}
%  ...
\pitem{Related Patterns}
  Instead of using Propagation, you might use a reader monad to
  propagate information down the tree. The \textsc{Local Effect}
  pattern explains how to keep the monadic propagation effect local.
\end{cpattern}

RewriteStep.tex
\begin{cpattern}{Rewrite Step}{Basic}
%\pitem{Aka}
%  ...
\pitem{Intent}
%
  Capture a single type-specific computation step.
\pitem{Motivation} 
%
  Generic programming involves type-specific and generic
  functionality.  By capturing type-specific computations and
  assigning a name to them, they can easily be reused in different
  contexts. A rewrite step is such a reusable piece of type-specific
  functionality.
%
\pitem{Schema}
  \input{snip/rewrite-step-schema.math} 
%
\pitem{Description} 
%
  Model a rewrite step with a unary function \emph{step} on a specific
  term type $T$. The result type $T'$ may or may not coincide with
  $T$, and may or may not be monadic. Define the function with
  equations that pattern-match on the argument.  If the pattern-match
  cases are not exhaustive, then the function needs to be complemented
  by a catch-all case. You can use the \emph{Maybe} type constructor
  to indicate when the step fails to fire. Alternatively, the
  catch-all equation can return the input term itself, or a
  distinguished value, such as the empty list.
%
%\pitem{Consequences}
%  ...
%
\pitem{Sample code}
%
  \input{snip/rewrite-step-sample.math}
%
  The two above rewrite steps deal with name analysis for Haskell
  programs.  They work on the abstract syntax of type expressions and
  declarations, respectively. The first step retrieves the name of a
  type constructor referred to by the type expression, if any. The
  second step retrieves the name of a type constructor declared in the
  given declaration, if any. We use lists of names as result type so
  that we are able to deal with cases where there is one type name, no
  type name, and potentially even several type names. In both cases,
  we need a catch-all case because obviously not all syntactical
  patterns are covered by the pattern-match cases. The catch-all cases
  simply return the empty list.
%
%\pitem{Implementation}
%  Since a rewrite step is simply a function of a specific form, 
\pitem{Consequences}
  By capturing relatively small pieces of type-specific behaviour in
  separate rewrite rules, this behaviour can be used as building
  blocks for larger strategic programs.
\pitem{Related Patterns}
  The construction of rewrite steps is a prerequisite for creating
  \textsc{Generic Rewrite Step}s, but they can also be passed as
  actual parameters to \textsc{Keyhole Operation}s.
\end{cpattern}

RolePlay.tex
\begin{cpattern}{Role Play}{Advanced}
%
%\pitem{Aka}
%  Pipeline
%
\pitem{Intent}
%
  Define a transformation as a pipeline of steps with
  designated roles.
%
\pitem{Motivation}
%
  A transformation can usually be decomposed into separate steps with
  limited responsibilities, such as analyses, guards, side effects,
  atomic transformations, and others. When each step has its own
  sharply delimited role to play, it becomes easier to construct,
  understand, and modify the transformation. The individual steps can
  be formed into a complete transformation pipeline with appropriately
  selected composition operators.
%
%A Role Play points out such different steps
%  and theirs roles.  Appropriate means of sequential composition are
%  chosen.  The resulting pipelines impose impose extract structure on
%  strategies and support evolution and experimentation.
%
\pitem{Schema}
%
\input{snip/role-play-schema.math}
%
\pitem{Description}
%
  Decompose the transformation task you need to implement into basic
  roles. An \emph{analysis} is type-unifying, and does not modify its
  input term. A \emph{guard} checks whether a particular condition is
  satisfied by its input term. It is typically implemented as a
  Boolean expression wrapped by the \emph{guard} function, or a
  strategy of type $\mathit{TU}\ ()\ m$, where the monad \emph{m}
  supports partiality. Side effects are realized by access to an
  extended monad interface for a state. Atomic \emph{transformation
  steps} are type-preserving.

  There are two kinds of pipelines. Depending on whether you need the
  pipeline itself to be a strategy, you may either compose strategies,
  or keyhole operations and other monadic functions. The composition
  operators $\mathit{co}_i$ are \emph{let} and \emph{seq} combinators
  when composing strategies. The monadic bind operator ``$\bind$'', or
  do-notation are used when composing keyhole operations.
%
\pitem{Sample code}
%
\input{snip/role-play-sample.math}
%
  The \emph{toAlias} pipeline implements a simple refactoring for
  Haskell datatypes. Assuming that a focus has been placed on some
  type expression $t$, we want to replace $t$ by a type synonym (or
  alias) named $n$. A pre-condition for this replacement is that $n$
  is defined as $t$ in the given Haskell module $m$. The
  transformation is implemented as a sequence of keyhole operations
  and a simple guard. For brevity, we do not show the definitions of
  the keyhole operations.  Firstly, we look up the type expression $t$
  from the focus via \emph{selectTypeFocus}. This is an
  analysis. Secondly, we look up the right-hand side expression $t'$
  from the declaration for $n$ via \emph{getAlias}. This is again an
  analysis. Then, we place a guard to enforce that the focused type
  expression $t$ actually coincides with $t'$. Finally, we perform the
  actual transformation that replaces the focussed type expression by
  a reference to $n$ via \emph{replaceTypeFocus}.
%
\pitem{Related Patterns}
%
  The \textsc{Circuitry} pattern explains how to wire the data and
  control flow between the individual steps of a pipeline.
%
\end{cpattern}

strafunski.tex
\section{Strategic programming}
\label{S:Strafunski}

In this section, we discuss both the fundamentals of functional
strategic programming, and Strafunski's support for it.



\subsection{The essence of strategies}

In the introduction, functional strategies were defined by enumerating
their defining characteristics. They are functions that (i) work on
arguments of any type, (ii) can display type-specific behaviour, (iii)
can traverse into terms, and (iv) are first-class citizens. This
abstract definition can be made more concrete by establishing a
minimal set of basic strategy combinators that realizes these
characteristics. Figure~\ref{Fig:basic-combinators} shows such a set.
%
\begin{figure*}[ht!]
{\small%
\begin{boxedminipage}{\linewidth}
\begin{tabular}{@{}c@{}c@{}}
\begin{minipage}{.50\linewidth}
\input{snip/basic-combinators.math}
\end{minipage}&
\begin{minipage}{.40\linewidth}
\input{snip/basic-combinators-comments.math}
\end{minipage}
\end{tabular}
\end{boxedminipage}
\vspace{-3ex}}
\caption{Strategy types and basic strategy combinators.}
\label{Fig:basic-combinators}
\end{figure*}
%
Two strategy types are distinguished: $\mathit{TP}$ for
type-preserving strategies (output type coincides with input type) and
$\mathit{TU}$ for type-unifying strategies (output type is always
$\mathit{a}$). Both types are parameterized with a monad $\mathit{m}$,
such that monadic effects can be used in strategic programming.

The basic strategy combinators come in pairs: one for each strategy
type as pointed out by the postfix ``...\emph{TP}'' vs.\
``...\emph{TU}''. The $\mathit{apply}$ combinators justify our claim
that strategies are generic functions (recall i). The $\mathit{adhoc}$
combinators support type-specific customization of a strategy (recall
ii). If $\mathit{f}$ is a function on some type $\mathit{T}$, the
strategy $\mathit{adhoc\,s\,f}$ will behave like $\mathit{f}$ when
applied to a term of type $\mathit{T}$ and like $\mathit{s}$ on terms
of any other type.

Out set contains the following nullary combinators.  The \emph{identity}
combinator is a generic version of the monad member $\mathit{return}$
(which in turn is just the monadic identity function), i.e.,
\emph{identity} returns the input term.  The \emph{compute}
combinator ignores the input term and always returns its argument.
It is the generic counterpart of the $\mathit{const}$ function. 
The combinators $\mathit{failTP}$ and $\mathit{failTU}$ denote the
always failing strategy in the sense of a \emph{MonadPlus} with a
member \emph{mzero} for failure. To instantiate the monad parameter
$m$ of \emph{TP} and \emph{TU} with such a monad allows us to deal
with partiality, recovery from failure, and backtracking.

The $\mathit{seq}$ and $\mathit{let}$ combinators perform their two
argument strategies in sequence. For the $\mathit{seq}$ combinators,
the first argument strategy is type-preserving, and its output is
given to the second argument strategy as input. For the $\mathit{let}$
combinators, the first argument strategy is always type-unifying, and
the second argument is a strategy parameterized with a value of the
unifying type $\mathit{a}$. The result value of the first argument is
used to instantiate the parameter of the second argument. The
$\mathit{choice}$ combinators support recovery from failure of a
strategy relying on the \emph{mplus} member of the \emph{MonadPlus}
class. They attempt application of their first argument strategy, and
if this fails, they apply their second argument strategy instead.  In
principle, the $\mathit{choice}$ combinators could also serve for a
more general combination of alternatives in the sense of
non-determinism or backtracking depending on the actual monad
instance.

The $\mathit{all}$ and $\mathit{one}$ combinators are non-recursive
generic traversal combinators (recall iii). In a sense, they push
their argument strategy one level down into their input term. To be
precise, $\mathit{all}$ applies its argument strategy to \emph{all}
immediate subterms, while $\mathit{one}$ tries it left-to-right on
each of the immediate subterms and stops after the first
succeeds. Hence, the potentially failing strategy passed to the
\emph{one} combinators involves \emph{MonadPlus} to point out fitness
of a child. The type-preserving variants of the traversal combinators
preserve the outermost constructor of the input term. The type-unifying
$\mathit{allTU}$ relies on the $\mathit{mappend}$ operator of a
$\mathit{Monoid}$ to reduce the results of processing the subterms to
a single result.

The \emph{msubst} combinators can be used to migrate from one monad to
another. This is useful, for example, if we want to hide the fact that
a certain strategy has the potential to fail while the overall
strategy cannot due to recovery of failure.  In this case we would
migrate from the \emph{Maybe} to the \emph{Identity} monad.

Note that Strafunski's combinator style of generic programming indeed
relies on the fact that strategies are first-class functions (recall
iv): they can be named, passed as arguments, returned as results, and
stored in data structures. Even traversal and type-specific
customization are expressed via combinators.




\subsection{Strafunski}

Strafunski is a Haskell-based bundle that supports generic programming
with functional strategies. Figure~\ref{Fig:Strafunski-arch} provides
an overview of the elements of Strafunski, and their relation to an
application constructed with it.
%
\begin{figure}
\resizebox{\linewidth}{!}{\includegraphics{Strafunski-arch.eps}}
\vspace{-4.5ex}
\caption{$\mathit{Strafunski} = \mathit{Library} + \mathit{Precompiler}$}
\label{Fig:Strafunski-arch}
\vspace{-3ex}
\end{figure}
%
Strafunski consists of two components: a \emph{library} and a
\emph{precompiler}, which we will discuss in turn.

\paragraph{Library}

%
\begin{figure*}[ht!]
{\small%
\begin{boxedminipage}{\linewidth}
\begin{tabular}{@{}c@{}c@{}}
\begin{minipage}{.50\linewidth}
\input{snip/themes.math}
\end{minipage}&
\begin{minipage}{.40\linewidth}
\input{snip/themes-comments.math}
\end{minipage}
\end{tabular}
\end{boxedminipage}
\vspace{-3ex}}
\caption{Excerpts from Strafunski's theme modules.}
\label{Fig:themes}
\end{figure*}
%
The library of Strafunski consists of a number of Haskell modules that
address various aspects of strategic programming.
\begin{Description}
\setlength{\itemsep}{0\itemsep}%
\setlength{\topsep}{0\topsep}%
%\setlength{\leftmargin}{0pt}% ineffecive !!??
%\setlength{\labelwidth}{0pt}%
%\setlength{\listparindent}{0pt}%
\setlength{\parindent}{0pt}
%
\Ditem{StrategyLib}
  This is the top-level module of the library, provided for
  convenience. It allows the user to import the entire library with a
  single import statement.
%
\Ditem{Themes}
  A series of modules is provided that covers a range of generic
  programming themes. For example, the \emph{FixpointTheme} deals with
  iterative term transformation which terminates when some kind of
  fixpoint is found. The \emph{TraversalTheme} defines various
  traversal schemes. The $\mathit{NameTheme}$ provides abstract
  algorithms for different kinds of name analysis, useful in language
  processing applications. In the $\mathit{OverloadingTheme}$, the
  basic strategy combinators of Figure~\ref{Fig:basic-combinators} are
  overloaded to implement the intuition that the combinators usually
  come in pairs, one combinator for \emph{TP} and another for
  \emph{TU}. When defining new strategies, such overloading allows one
  to postpone commitment to a particular strategy type and, in a
  sense, to define two strategies at once.
%
  With each version of Strafunski, more themes are added and existing
  themes are elaborated. Excerpts of the current state of affairs are
  shown in Figure~\ref{Fig:themes}.
%
\Ditem{StrategyPrimitives}
  This module provides basic strategy types, and a basic set of
  strategy combinators. Together they form an \emph{abstract}
  datatype, whose internals are not exposed beyond the module. In
  fact, we have experimented with several implementations of the
  datatype that each have different characteristics with respect to
  performance, extensibility, and use of type features.
%
\Ditem{TermRep}
  This module provides a generic term interface as a type class
  $\mathit{Term}$, as well as a universal representation of typed
  terms which is employed by this interface. The current implementation
  of the basic strategy combinators relies on \emph{TermRep} to 
  deal with dynamic typing and generic traversal while the module
  remains hidden for the rest of the library, and the user code.
%
\end{Description}



\paragraph{Precompiler}

To use the Strafunski library in an application, instances of the
\emph{Term} class must be provided for the datatypes of the
application. This can be done manually, but Strafunski provides a
precompiler to automate the process. This is possible because these
\emph{Term} instances  follow a very simple scheme for all algebraic
datatypes. Currently, the precompiler is implemented as an extension
of the DrIFT tool (formerly known as Derive~\cite{Winstanley97}). If
the following directive is added to a Haskell source file:
\begin{quote}
\verb#{-! global: Term !-}#
\end{quote}
the precompiler will generate and insert $\mathit{Term}$ instances for
all datatypes in the file. For the sample code in the present paper,
we precompiled the abstract syntax of Haskell~98 (see the appendix) to
enable traversal over Haskell parse trees.


\medskip
\noindent
Thus, functional strategic programming with Strafunski proceeds along the
following steps:
%
\begin{enumerate}
\setlength{\itemsep}{0\itemsep}%
\setlength{\topsep}{0\topsep}%
\setlength{\leftmargin}{0pt}% ineffecive !!??
%\setlength{\labelwidth}{0pt}%
%\setlength{\listparindent}{0pt}%
\item
  Apply the precompiler to the system of datatypes that represent the
  terms on which to operate.
\item
  Import the precompiled datatypes and $\mathit{StrategyLib}$ into an
  application module.
\item
  Select, combine, and specialize appropriate strategy combinators
  from Strafunski's library, and apply the resulting strategies to the terms
  that need to be processed.
\end{enumerate}
%
Clearly, the last of these steps deserves elaboration.


\begin{comment}

\begin{figure}[t]
\begin{center}
$\begin{array}{|l|l|}
\hline
\mbox{Combinator}   & \mbox{Definition}\\
\hline
\mathtt{choice}(s,s')  & \IF{s}{\id}{s'}\\
\mathtt{not}(s)        & \IF{s}{\fail}{\id}\\
\mathtt{try}(s)        & \mathtt{choice}(s,\id)\\
\mathtt{test}(s)       & \IF{\mathtt{not}(s)}{\fail}{\id}\\
\mathtt{repeat}(s)     & \mathtt{try}(s;\mathtt{repeat}(s))\\
\mathtt{topdown}(s)    & s;\all(\mathtt{topdown}(s))\\
\mathtt{bottomup}(s)   & \all(\mathtt{bottomup}(s));s\\
\stratt{once-bu}(s)    & \IF{\one(\stratt{once-bu}(s))}{\id}{s}\\
\stratt{while-td}(s)   & \IF{s}{\all(\stratt{while-td}(s))}{\id}\\
\stratt{naive-innermost}(s)
                       & \stratt{repeat}(\stratt{once-bu}(s))\\
\mathtt{innermost}(s)  & \all(\mathtt{innermost}(s));
                          \mathtt{try}(s;\mathtt{innermost}(s))\\
\mathtt{below}(s_b,s_t) & \stratt{once-td}(s_t;\stratt{once-td}(s_b))\\
\stratt{strict-below}(s_b,s_t)
                        & \mathtt{below}(\mathtt{one}(s_b),s_t)\\
\hline
\end{array}$
\end{center}
\vspace{-3ex}
\caption{Some defined strategy combinators}
\label{Fig:defined-combinators}
\end{figure}

\paragraph{Benefits of strategies}

\begin{description}
\item[Separation of concerns]
  Strategies allow one to implement conceptually separable concerns in
  distinct modules, whilst otherwise they would be entangled in a
  single code fragment.  As a result, these concerns can be
  understood, reasoned about, developed, tested, maintained, and
  reused separately. Examples of (categories of) concerns that we
  encountered include traversal, evaluation, computation, control,
  accumulation, state, testing.
\item[Reuse]
  Strategies enable reuse in several dimensions. Within an
  application, a single concern, such as a particular traversal
  strategy or applicability condition, needs to be implemented only
  once in a reusable strategy. Across applications, strategies can be
  reused that capture generic behaviour.  Examples are defined
  combinators for traversal and control, such as \stratt{topdown}\ and
  \stratt{repeat}, but also combinators that capture generic
  algorithms, e.g., for free variable analysis or
  refactoring~\cite{Visser00,LV02-PADL,Laemmel02-TGR}.
\item[Robustness]
  Using strategies, each concern can be implemented with explicit
  reference only to types and operations that are relevant to it. As a
  result, changes in specific data structures will not unduly affect
  the implementation of the concern. This isolation from changes in
  class hierarchy, term signatures, or algebraic data type definitions
  (depending on the paradigm) diminishes the resistance to change of
  software systems, and makes them more maintainable.

\item[Concision]
  When programming on heterogeneous data structures, strategic
  programming can be radically more concise than non-generic
  programming. Due to the generic access to specific data structures,
  the strategic programmer does not need to repeatedly implement for
  each type the behaviour that is conceptually generic to them
  all. Instead, generic behaviour can be captured in first-class
  combinators and reused across types.
\end{description}

\end{comment}

SuccessAndFailure.tex
\begin{cpattern}{Success by Failure}{Basic}
%
\pitem{Intent}
%
Use a potentially failing computation to control traversal.
%
\pitem{Motivation}
%
  To correctly implement certain traversals, their constituent rewrite
  steps should only be performed under certain conditions. For
  instance, a particular rewrite step should trigger only if another
  does not, or vice versa. To model success and failure of rewrite
  steps and strategies, you can use the \emph{Maybe} monad or a
  backtracking monad. Generic failure is captured by the \emph{fail}
  combinators, and the \emph{choice} combinators allow you to recover
  from failure.
%
\pitem{Schema}
%
\input{snip/success-and-failure-schema.math}
%
%
\pitem{Description}
%
  A \emph{partial} strategy, i.e., one that potentially fails, is
  typically constructed from type-specific rewrite \emph{step}s that
  use the \emph{mzero} of a \emph{MonadPlus} to encode failure. When
  lifting such a partial \emph{step} to the strategy level with
  \emph{adhoc}, the generic \emph{fail} combinator is used as default
  strategy. Finally, the \emph{choice} combinator is used to combine
  potentially failing generic rewrite steps.
%
\pitem{Sample code}
%
\input{snip/success-and-failure-sample.math}
%
  A prime example of a partial strategy combinator is \emph{select}.
  Its argument strategy is meant for the identification of selectable
  entities. This process must be necessarily partial. A \emph{choice}
  is used in the definition of \emph{select} because selection can
  recover from failure of identification for a given node by recursing
  into the children. If the identification strategy fails at all
  levels, selection will altogether fail.

  The second sample illustrates the use of potentially failing
  strategies to merge rewrite steps that are specific for the same
  type. The partial rewrite steps \emph{typeCon} and \emph{dataCon} are
  both specific for type \emph{HsDecl}. The \emph{decCon} strategy
  reverts to the second if the first fails.
%
\pitem{Related Patterns}
If you want to prevent the monadic effects of partiality or
non-determinism to invade parts of your code that do not rely on them,
you may want to use \textsc{Local Effect}.
\end{cpattern}
TraversalScheme.tex
\begin{cpattern}{Traversal Scheme}{Advanced}
%
\pitem{Aka}
%
  Abstract Algorithm, Recursion Scheme.
%
\pitem{Intent}
%
  Capture traversal control in a fully generic, reusable strategy
  combinator, which abstracts over any type-specific operations.
%
\pitem{Motivation}
%
  The traversal behaviour of many traversals can be captured in a
  reusable traversal \emph{scheme}. To ensure its reusability,
  type-specific computations should not be hard-wired into it, but
  should rather be supplied via appropriate parameters. Thus, a
  traversal scheme captures generic traversal behaviour in an abstract
  algorithm.
%
\pitem{Schema}
%
\input{snip/traversal-scheme-schema.math}
%
\pitem{Description}
%
  Divide your algorithm into a fully generic \emph{scheme} with formal
  parameters for type-specific computations. These parameters are
  either of strategy types, or they are place holders for monomorphic
  functions. The scheme itself should not make use of \emph{adhoc}
  combinators. Rather, the actual parameters that are supplied when
  the scheme is instantiated should implement type-specific behaviour
  via \emph{adhoc} combinators.
%
%\pitem{Consequences}
%  The full genericity of the schema allows it to be reused for many different
%  systems of datatypes.
%
\pitem{Sample code}
%
\input{snip/traversal-scheme-sample.math}
% 
  The free names (e.g., variables) in a given program fragment can be
  collected by a strategy which looks up the names from all the
  relevant patterns dealing with names in the given language. The
  sample code for the \textsc{Circuitry} pattern defines a
  Haskell-specific free variable analysis. The above \emph{freeNames}
  combinator implements a generic scheme for free name analysis by
  separating out the type-specific ingredients of the traversal. By
  supplying appropriate actual parameters for recognition of referred
  variables and declared variables, we can obtain different concrete
  name analysis algorithms, e.g., for free Haskell variables, free
  Haskell \emph{type} variables, or free Java variables.

  Examples of simpler traversal schemes are the predefined combinators
  of Strafunski's \emph{TraversalTheme} (see
  Figure~\ref{Fig:themes}).
%
%\pitem{Implementation}
%  You can group the parameters of a schema into a record, using the field
%  names to document the roles of each parameter.
%
\pitem{Related Patterns}
%
  Instantiation of a traversal scheme to synthesize an actual
  traversal is described in the \textsc{Traversal} pattern.
%
\end{cpattern}

Traversal.tex
\begin{cpattern}{Traversal}{Basic}
%\pitem{Aka}
%  ...
\pitem{Intent}
%
  Instantiate a traversal scheme with generic rewrite steps.
%
\pitem{Motivation}
%
  Traversal is at the heart of strategic programming.  Many schemes of
  traversal are readily available in Strafunski's combinator
  library. You can construct a traversal by passing your own rewrite
  steps to an appropriate predefined traversal scheme.
%
\pitem{Schema}
%
\input{snip/traversal-schema.math}
%
\pitem{Description}
%
  To select an appropriate traversal scheme from the library you must
  first decide whether you need a type-unifying one (for analysis) or
  a type-preserving one (for transformation). Further, you must decide
  on the desired order of traversal (e.g., top-down or bottom-up),
  whether the traversal should be cut-off below certain nodes (stop
  conditions), how to combine intermediate results, and more. These
  decision will usually lead to the identification of a library
  scheme.  Then, you have to identify the rewrite steps required to
  solve the problem.  These rewrite steps are usually generic, and
  they serve as the actual parameters $\mathit{ap}_1$, \ldots,
  $\mathit{ap}_n$ that \emph{instantiate} the traversal \emph{scheme}.
%
%\pitem{Consequences}
%  ...
\pitem{Sample code}
%
\input{snip/traversal-sample.math}
%
  The strategy \emph{allTypes} uses the generic rewrite step
  \emph{anyTypes}, that illustrates the \textsc{Generic Rewrite Step}
  pattern, to collect all possible declaring and referring occurrences
  of type constructor names. For this purpose we selected the
  traversal scheme \emph{crush}, which performs deep reduction in
  top-down order over the entire input term (no cut-off). The
  intermediate results are combined via a \emph{Monoid}'s binary
  operator. Since we use lists as monoids, this binary operator will
  be resolved to the append operator ``$\plus$''. The resulting
  traversal can be applied to terms of any type.

  An example of a type-preserving traversal is provided by the
  \emph{increment} strategy of Figure~\ref{Fig:example}. Note that, to
  adhere to Strafunski's naming conventions in this figure,
  $\mathit{adhocTP}$ should replace $\mathit{adhoc}$, and
  $\mathit{applyTP}$ should be prefixed to the application examples.
%
%\pitem{Implementation}
%  ...
\pitem{Related Patterns} If you discover that the particular traversal
  scheme you need is not present in Strafunski's library, then you may
  consult \textsc{Traversal Scheme} to find out how to roll your own.
  Traversals can be disguised by a \textsc{Keyhole Operation}, and can
  be used to fulfill various roles in a \textsc{Role Play}.
\end{cpattern}


TypeArgument.tex
\begin{cpattern}{Type Argument}{Advanced}
%\pitem{Aka}
%  ...
\pitem{Intent}
%
  Parameterize behaviour by a type argument.
%
\pitem{Motivation}
%
  Sometimes, you want your strategy to display type-specific behaviour
  even though it does not directly consume or produce any values that
  involve this specific type. By adding a type argument you can specify
  your type of choice.
%
%\pitem{Applicability}
%  Use a type argument when your strategy is polymorphic in the
%  specific type for which it displays type-specific behaviour, but
%  does consume or produce values of that type.
%
\pitem{Schema}
%
\input{snip/type-argument-schema.math}
%
\pitem{Description}
%
  Type arguments have to be modelled as value arguments. The challenge
  is to prevent having to supply a value of the intended type. Type
  arguments can be modeled in various ways. In general, you need a
  dedicated type constructor \emph{TypeArg}, and you need an actual
  representation of the type argument, say, \emph{typeArg}. A strategy
  \emph{foo} which is controlled by a type argument then takes an
  argument of type $\mathit{TypeArg}\ a$. The strategy employs the
  type argument \emph{ta} to internally disambiguate unresolved
  polymorphism. An actual instance \emph{fooT} of \emph{foo} will
  simply construct the appropriate type argument by type annotation.
%  ...
%\pitem{Consequences}
%  ...
%
\pitem{Sample code}
%
\input{snip/type-argument-sample.math}
%
  Here we model type arguments by functions with the intended type as
  domain, and \emph{()} as co-domain. The \emph{typeTick} combinator
  is controlled by a type argument which it uses internally to
  disambiguate the polymorphism of the non-generic argument of
  \emph{adhocTU}. In fact, \emph{typeTick} returns 1 if a term of the
  intended type is encountered, and 0 otherwise. The function
  \emph{countHsDecls} counts all Haskell declarations within the given
  Haskell module. It is structured as a keyhole operation around an
  instantiation of \emph{typeTick} that takes \emph{HsDecl} as actual
  type argument. The type-unifying traversal scheme \emph{crush} is
  used to traverse an input term with the instantiated type argument.
  Here, we rely on the fact that all numeric types (class \emph{Num})
  instantiate the \emph{Monoid} class.
%
%\pitem{Implementation}
%  ...
\pitem{Related Patterns}
  Type arguments can be used for strategies that perform per-type
  element retrieval or enumeration on \textsc{Generic Container}s.
\end{cpattern}

paper.bbl
\begin{thebibliography}{10}

\bibitem{HsPatterns}
{Common Haskell Idioms}, 2002.
\newblock Haskell wiki:
  {\small\url{http://haskell.org/wiki/wiki?CommonHaskellIdioms}}.

\bibitem{Augusteijn99}
L.~Augusteijn.
\newblock Sorting morphisms.
\newblock In S.~Swierstra, P.~Henriques, and J.~Oliveira, editors, {\em
  Advanced Functional Programming, Third International School, AFP'98}, volume
  1608 of {\em LNCS}, pages 1--27, Braga, Portugal, Sept. 1999.
  Springer-Verlag.

\bibitem{BD77}
R.~M. Burstall and J.~Darlington.
\newblock A transformation system for developing recursive programs.
\newblock {\em J.~ACM}, 24(1):44--67, Jan. 1977.

\bibitem{JVV2000a}
M.~de~Jonge, E.~Visser, and J.~Visser.
\newblock {XT}: a bundle of program transformation tools.
\newblock In M.~van~den Brand and D.~Parigot, editors, {\em Electronic Notes in
  Theoretical Computer Science}, volume~44. Elsevier Science Publishers, 2001.
\newblock Proc. of Language Descriptions, Tools and Applications (LDTA 2001).

\bibitem{DV02-IWPC}
A.~v. Deursen and J.~Visser.
\newblock Building program understanding tools using visitor combinators.
\newblock In {\em 10th International Workshop on Program Comprehension
  ({IWPC~2002})}. To Appear, 2002.

\bibitem{Fowler99}
M.~Fowler.
\newblock {\em {Refactoring---Improving the Design of Existing Code}}.
\newblock Addison Wesley, 1999.

\bibitem{GHJV94}
E.~Gamma, R.~Helm, R.~Johnson, and J.~Vlissides.
\newblock {\em Design Patterns: Elements of Reusable Object-Oriented Software}.
\newblock Addison-Wesley, 1994.

\bibitem{HughesJohn1995c}
J.~Hughes.
\newblock The design of a pretty-printing library.
\newblock In J.~Jeuring and E.~Meijer, editors, {\em Advanced Functional
  Programming}, volume 925 of {\em LNCS}. Springer Verlag, 1995.

\bibitem{JFP::Page1998}
G.~Hutton and E.~Meijer.
\newblock Functional pearl: Monadic parsing in {Haskell}.
\newblock {\em Journal of Functional Programming}, 8(4):437--444, July 1998.

\bibitem{JJ98}
P.~Jansson and J.~Jeuring.
\newblock {PolyLib}---{A} library of polytypic functions.
\newblock In R.~Backhouse and T.~Sheard, editors, {\em Proc.\ of WGP'98,
  Marstrand, Sweden, 18 June 1998}. Dept.\ of Computing Science, Chalmers
  Univ.\ of Techn.\ and G{\"o}teborg Univ., June 1998.

\bibitem{KL02-FDT}
J.~Kort and R.~L{\"a}mmel.
\newblock {A Framework for Datatype Transformation}.
\newblock Technical report, CWI Amsterdam, Mar. 2002.
\newblock In preparation; Available at
  {\small\url{http://www.cwi.nl/~ralf/fdt/}}.

\bibitem{Kuehne99}
T.~K{\"u}hne.
\newblock {\em A Functional Pattern System for Object-Oriented Design}.
\newblock Verlag Dr.\@ Kova\v{c}, {ISBN 3-86064-770-9}, Hamburg, Germany, 1999.
\newblock PhD thesis, Darmstadt University of Technology.

\bibitem{Laemmel00-SFP99}
R.~L{\"a}mmel.
\newblock {Reuse by Program Transformation}.
\newblock In G.~Michaelson and P.~Trinder, editors, {\em {Functional
  Programming Trends 1999}}. Intellect, 2000.
\newblock Selected papers from the 1st Scottish Functional Programming
  Workshop.

\bibitem{Laemmel02-SPS}
R.~L{\"a}mmel.
\newblock {The Sketch of a Polymorphic Symphony}.
\newblock Technical Report cs.PL/0204013, arXiv, Apr.8 2002.
\newblock 16 pages.

\bibitem{Laemmel02-TGR}
R.~L{\"a}mmel.
\newblock {Towards Generic Refactoring}.
\newblock Technical Report cs.PL/0203001, arXiv, Mar.1 2002.
\newblock Available at {\small\url{http://www.cwi.nl/~ralf}}.

\bibitem{Essence}
R.~L{\"a}mmel, E.~Visser, and J.~Visser.
\newblock The essence of strategic programming -- an inquiry into
  trans-paradigmatic genericity.
\newblock Draft, submitted for publication, 2002.

\bibitem{LV02-PADL}
R.~L{\"a}mmel and J.~Visser.
\newblock {Typed Combinators for Generic Traversal}.
\newblock In S.~Krishnamurthi and C.~Ramakrishnan, editors, {\em {Proc.\ of
  PADL 2002, Portland, OR, USA}}, volume 2257 of {\em LNCS}. Springer-Verlag,
  Jan. 2002.

\bibitem{OpdykePhD}
W.~F. Opdyke.
\newblock {\em {Refactoring Object-Oriented Frameworks}}.
\newblock PhD thesis, University of Illinois at Urbana-Champaign, 1992.

\bibitem{PP96}
A.~Pettorossi and M.~Proietti.
\newblock {Rules and Strategies for Transforming Functional and Logic
  Programs}.
\newblock {\em ACM Computing Surveys}, 28(2):360--414, June 1996.

\bibitem{swierstra98designing}
S.~D. Swierstra, P.~R.~A. Alcocer, and J.~Sariava.
\newblock Designing and implementing combinator languages.
\newblock In {\em Advanced Functional Programming}, pages 150--206, 1998.

\bibitem{1334}
S.~Thompson and C.~Reinke.
\newblock {Refactoring Functional Programs}.
\newblock Technical Report 16-01, Computing Laboratory, University of Kent at
  Canterbury, October 2001.

\bibitem{Winstanley97}
N.~Winstanley.
\newblock {Derive User Guide, version 1.0}.
\newblock Available at {\small\url{http://www.dcs.gla.ac.uk/~nww/Derive/}},
  June 1997.

\end{thebibliography}
