# Changeset 2427 for Papers/polymorphic-variants-2012

Ignore:
Timestamp:
Nov 5, 2012, 11:14:45 AM (8 years ago)
Message:

More work on explanation.

File:
1 edited

### Legend:

Unmodified
 r2425 When it comes to extending algebraic data types with new constructors in this way, we hit a problem: these types are closed'. In order to circumvent this restriction, we must introduce a new algebraic type with the additional constructor, lifting the old type---and any functions defined over it---into this type. This manual extension, coupled with the lifting of any existing functions into the new type, is cumbersome and error-prone. \begin{figure}[ht] = Lit Int | Add Term Term | Mul Term Term evaluate :: Term -> Int evaluate (Lit i)   = i evaluate (Add l r) = evaluate l + evaluate r evaluate (Mul l r) = evaluate l * evaluate r eval :: Term -> Int eval (Lit i)   = i eval (Add l r) = eval l + eval r \end{lstlisting} \end{minipage} \begin{minipage}[b]{0.45\linewidth} \begin{lstlisting} interface Term { int eval(); } class Lit implements Term { private int v = 0; ... int eval() { return v; } } class Add implements Term { private Term left, right = null; ... int eval() { return left.eval() + right.eval(); } } \end{lstlisting} \end{minipage} \end{figure} We can compare and contrast functional programming languages' use of algebraic data and pattern matching with the approach taken by object-oriented languages (see Figure~\ref{fig.pattern-matching.vs.oop} for a concrete example). In mainstream object-oriented languages such as Java algebraic data types correspond to interfaces, or some base object. Constructors correspond to classes implementing this interface; branching by pattern matching is emulated using the language's dynamic dispatch mechanism. However, we can look abroad to see what other families of programming languages do to solve this problem. For instance, we can compare and contrast functional programming languages' use of algebraic data and pattern matching with the approach taken by object-oriented languages (see Figure~\ref{fig.pattern-matching.vs.oop} for a concrete example). In mainstream, class-based object-oriented languages---such as Java, for example---algebraic data types can be emulated by interfaces, coupled with a number of subclasses corresponding to constructors, implementing the root' interface. The base interface of the object hierarchy specifies the permitted operations defined for the type. As all operations Branching by pattern matching is emulated using the language's dynamic dispatch mechanism. As all permitted operations on it is hard to enlarge the set of operations defined over a given type without altering the entire class hierarchy. If the interface changes so must every class implementing it. However, note it is easy to extend the hierarchy to new cases, corresponding to the introduction of a new constructor in the functional world, by merely adding another class corresponding to that constructor implementing the interface. \begin{figure}[ht] \begin{minipage}[b]{0.45\linewidth} \begin{lstlisting} ... data Term' = Lift Term | Mul Term' Term' eval' :: Term' -> Int eval' (Lift t)  = eval t eval' (Mul l r) = eval' l * eval ' r \end{lstlisting} \end{minipage} \hspace{0.5cm} \begin{minipage}[b]{0.45\linewidth} \begin{lstlisting} ... class Mul implements Term { private Term left, right = null; ... int eval() { return left.eval() * right.eval(); } } \end{lstlisting} \end{minipage} \label{fig.extending.base.type} \caption{Extending our simple language of arithmetic with a new grammatical element.} \end{figure} \begin{figure}[ht] \begin{minipage}[b]{0.45\linewidth} \begin{lstlisting} ... show :: Term -> String show (Lit i)   = show i show (Add l r) = show l ++ " + " ++ show r \end{lstlisting} \end{minipage} \hspace{0.5cm} \begin{minipage}[b]{0.45\linewidth} \begin{lstlisting} interface Term { int eval(); String show(); } class Lit implements Term { private int v = 0; ... int eval() { return v; } String show() { return Int.toString(v); } } class Add implements Term { private Term left, right = null; ... int eval() { return left.eval() + right.eval(); } ... String show() { return left.show() + \ " + " + right.show(); } } \end{lstlisting} \end{minipage} \label{fig.extending.base.type} \caption{Extending the permitted operations over our simple language of arithmetic.} \end{figure} [dpm: reword the above --- hard to phrase precisely ] \item Bounded vs not-bounded. \end{itemize} \begin{definition} \label{defn.garrigues.calculus} Inductively define a \end{definition} \begin{figure}