\section{Extensions}
\label{sec-extensions}

\CYS supports some extensions in Curry programs that are not (yet)
part of the definition of Curry. These extensions are described below.

\subsection{Recursive Variable Bindings}

Local variable declarations (introduced by \code{let}\pindex{let}
or \code{where}\pindex{where}) can be (mutually) recursive in \CYS.
For instance, the declaration
\begin{curry}
ones5 = let ones = 1 : ones
         in take 5 ones
\end{curry}
introduces the local variable \code{ones} which is bound
to a \emph{cyclic structure}\index{cyclic structure}
representing an infinite list of \code{1}'s.
Similarly, the definition
\begin{curry}
onetwo n = take n one2
 where
   one2 = 1 : two1
   two1 = 2 : one2
\end{curry}
introduces a local variables \code{one2} that represents
an infinite list of alternating \code{1}'s and \code{2}'s
so that the expression \code{(onetwo 6)} evaluates to \code{[1,2,1,2,1,2]}.


\subsection{Functional Patterns}

Functional patterns \cite{AntoyHanus05LOPSTR} are a useful extension
to implement operations in a more readable way. Furthermore,
defining operations with functional patterns avoids problems
caused by strict equality (\ccode{=:=}) and leads to programs
that are potentially more efficient.

Consider the definition of an operation to compute the last element
of a list \code{xs} based on the prelude operation \ccode{++}
for list concatenation:
\begin{curry}
last xs | _++[y] =:= xs  = y   where y free
\end{curry}
Since the equality constraint \ccode{=:=} evaluates both sides
to a constructor term, all elements of the list \code{xs} are
fully evaluated in order to satisfy the constraint.

Functional patterns can help to improve this computational behavior.
A \emph{functional pattern}\index{functional pattern}\index{pattern!functional}
is a function call at a pattern position. With functional patterns,
we can define the operation \code{last} as follows:
\begin{curry}
last (_++[y]) = y
\end{curry}
This definition is not only more compact but also avoids the complete
evaluation of the list elements: since a functional pattern is considered
as an abbreviation for the set of constructor terms obtained by all
evaluations of the functional pattern to normal form (see
\cite{AntoyHanus05LOPSTR} for an exact definition), the previous
definition is conceptually equivalent to the set of rules
\begin{curry}
last [y] = y
last [_,y] = y
last [_,_,y] = y
$\ldots$
\end{curry}
which shows that the evaluation of the list elements is not demanded
by the functional pattern.

In general, a pattern of the form \code{($f$ $t_1$\ldots$t_n$)} for $n>0$
(or of the qualified form \code{($M.f$ $t_1$\ldots$t_n$)} for $n \geq 0$)
is interpreted as a functional pattern if $f$ is not a visible constructor
but a defined function that is visible in the scope of the pattern.
Furthermore, for a functional pattern to be well defined,
there are two additional requirements to be satisfied:

\begin{enumerate}

\item
If a function $f$ is defined by means of a functional pattern $fp$,
then the evaluation of $fp$ must not depend on $f$, i.e.,
the semantics of a function defined using functional patterns
must not (transitively) depend on its own definition.
This excludes definitions such as
\begin{curry}
(xs ++ ys) ++ zs = xs ++ (ys ++ zs)
\end{curry}
and is necessary to assign a semantics to funtions employing functional patterns
(see \cite{AntoyHanus05LOPSTR} for more details).

\item
Only functions that are globally defined may occur inside a functional pattern.
This restriction ensures that no local variable
might occur in the value of a functional pattern,
which might lead to an non-intuitive semantics.
Consider, for instance, the following (complicated) equality operation
\begin{curry}
eq :: a -> a -> Bool
eq x y = h y
 where
  g True  = x
  h (g a) = a
\end{curry}
where the locally defined function \code{g} occurs in the functional
pattern \code{(g a)} of \code{h}.
Since \code{(g a)} evaluates to the value of \code{x} whereas \code{a}
is instantiated to \code{True}, the call \code{h y} now evaluates to \code{True}
if the value of \code{y} equals the value of \code{x}.
In order to check this equality condition,
a strict unification between \code{x} and \code{y} is required
so that an equivalent definition without functional patterns would be:
\begin{curry}
eq :: a -> a -> Bool
eq x y = h y
 where
  h x1 | x =:= x1 = True
\end{curry}
However, this implies that variables occuring in the value
of a functional pattern imply a strict unification
if they are defined in an outer scope,
whereas variables defined \emph{inside} a functional pattern
behave like pattern variables.
In consequence, the occurrence of variables from an outer scope
inside a functional pattern might lead to an non-intuitive behavior.
To avoid such problems, locally defined functions are excluded
as functional patterns.
Note that this does not exclude a functional pattern inside a local function,
which is still perfectly reasonable.
\end{enumerate}
%
It is also possible to combine functional patterns with
as-patterns.\index{as-pattern}\pindex{"@}
Similarly to the meaning of as-patterns
in standard constructor patterns,
as-patterns in functional patterns are interpreted
as a sequence of pattern matching where the variable of the as-pattern
is matched before the given pattern is matched.
This process can be described by introducing an auxiliary operation
for this two-level pattern matching process.
For instance, the definition
\begin{curry}
f (_ ++ x@[(42,_)] ++ _) = x
\end{curry}
is considered as syntactic sugar for the expanded definition
\begin{curry}
f (_ ++ x ++ _) = f' x
 where
  f' [(42,_)] = x
\end{curry}
However, as-patterns are usually implemented
in a more efficient way without introducing auxiliary operations.


\paragraph{Optimization of programs containing functional patterns.}
Since functions patterns can evaluate to non-linear constructor terms,
they are dynamically checked for multiple occurrences of
variables which are, if present, replaced by equality constraints
so that the constructor term is always linear
(see \cite{AntoyHanus05LOPSTR} for details).
Since these dynamic checks are costly and not necessary for
functional patterns that are guaranteed to evaluate to linear terms,
there is an optimizer for functional patterns that checks
for occurrences of functional patterns that evaluate always to
linear constructor terms and replace such occurrences
with a more efficient implementation.
This optimizer can be enabled by the following possibilities:
\begin{itemize}
\item
Set the environment variable \code{FCYPP} to \ccode{--fpopt}
before starting \CYS, e.g., by the shell command
\begin{curry}
export FCYPP="--fpopt"
\end{curry}
Then the functional pattern optimization is applied if programs are compiled
and loaded in \CYS.
\item
Put an option into the source code:
If the source code of a program
contains a line with a comment of the form (the comment
must start at the beginning of the line)
\begin{curry}
{-# PAKCS_OPTION_FCYPP --fpopt #-}
\end{curry}
then the functional pattern optimization is applied
if this program is compiled and loaded in \CYS.
\end{itemize}
The optimizer also report errors in case of wrong uses of functional patterns
(i.e., in case of a function $f$ defined with functional patterns that
recursively depend on $f$).


\subsection{Order of Pattern Matching}

Curry allows multiple occurrences of pattern variables
in standard patterns. These are an abbreviation of equational constraints
between pattern variables.
Functional patterns might also contain multiple occurrences of
pattern variables.
For instance, the operation
\begin{curry}
f (_++[x]++_++[x]++_) = x
\end{curry}
returns all elements with at least two occurrences in a list.

If functional patterns as well as multiple occurrences of
pattern variables occur in a pattern defining an operation,
there are various orders to match an expression against such
an operation. In the current implementation, the order
is as follows:
\begin{enumerate}
\item Standard pattern matching: First, it is checked whether
the constructor patterns match. Thus, functional patterns
and multiple occurrences of pattern variables are ignored.
\item Functional pattern matching: In the next phase,
functional patterns are matched but occurrences of standard
pattern variables in the functional patterns are ignored.
\item Non-linear patterns: If standard and functional pattern matching
is successful, the equational constraints which correspond
to multiple occurrences pattern variables are solved.
\item Guards: Finally, the guards supplied by the programmer
are checked.
\end{enumerate}
The order of pattern matching should not influence the computed
result. However, it might have some influence on the termination
behavior of programs, i.e., a program might not terminate
instead of finitely failing.
In such cases, it could be necessary to consider the influence
of the order of pattern matching. Note that other orders of pattern matching
can be obtained using auxiliary operations.


\subsection{Type Classes}

The concept of type classes is not yet part of the Curry language report.
The recognized syntax of type classes is specified in
Section~\ref{sec:syntax}.
Although the implemented concept of type classes
is not fully described in this manual,
it is quite similar to Haskell 98 \cite{PeytonJones03Haskell}
so that one can look there to find a detailed description.


%%% Local Variables:
%%% mode: latex
%%% TeX-master: "manual"
%%% End:
