Changeset 2427 for Papers


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

More work on explanation.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • Papers/polymorphic-variants-2012/polymorphic-variants.tex

    r2425 r2427  
    8989When it comes to extending algebraic data types with new constructors in this way, we hit a problem: these types are `closed'.
    9090In 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.
     91This manual extension, coupled with the lifting of any existing functions into the new type, is cumbersome and error-prone.
    9192
    9293\begin{figure}[ht]
     
    9697  = Lit Int
    9798  | Add Term Term
    98   | Mul Term Term
    99 
    100 evaluate :: Term -> Int
    101 evaluate (Lit i)   = i
    102 evaluate (Add l r) = evaluate l + evaluate r
    103 evaluate (Mul l r) = evaluate l * evaluate r
     99
     100eval :: Term -> Int
     101eval (Lit i)   = i
     102eval (Add l r) = eval l + eval r
    104103\end{lstlisting}
    105104\end{minipage}
     
    107106\begin{minipage}[b]{0.45\linewidth}
    108107\begin{lstlisting}
    109 
     108interface Term {
     109  int eval();
     110}
     111
     112class Lit implements Term {
     113  private int v = 0;
     114  ...
     115  int eval() { return v; }
     116}
     117
     118class Add implements Term {
     119  private Term left, right = null;
     120  ...
     121  int eval() {
     122    return left.eval() + right.eval();
     123  }
     124}
    110125\end{lstlisting}
    111126\end{minipage}
     
    114129\end{figure}
    115130
    116 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).
    117 In mainstream object-oriented languages such as Java algebraic data types correspond to interfaces, or some base object.
    118 Constructors correspond to classes implementing this interface; branching by pattern matching is emulated using the language's dynamic dispatch mechanism.
     131However, we can look abroad to see what other families of programming languages do to solve this problem.
     132For 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).
     133In 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.
    119134The base interface of the object hierarchy specifies the permitted operations defined for the type.
    120 
    121 As all operations
     135Branching by pattern matching is emulated using the language's dynamic dispatch mechanism.
     136
     137As all permitted operations on
    122138it is hard to enlarge the set of operations defined over a given type without altering the entire class hierarchy.
    123139If the interface changes so must every class implementing it.
    124140However, 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.
     141
     142\begin{figure}[ht]
     143\begin{minipage}[b]{0.45\linewidth}
     144\begin{lstlisting}
     145...
     146data Term'
     147  = Lift Term
     148  | Mul Term' Term'
     149
     150eval' :: Term' -> Int
     151eval' (Lift t)  = eval t
     152eval' (Mul l r) = eval' l * eval ' r
     153\end{lstlisting}
     154\end{minipage}
     155\hspace{0.5cm}
     156\begin{minipage}[b]{0.45\linewidth}
     157\begin{lstlisting}
     158...
     159class Mul implements Term {
     160  private Term left, right = null;
     161  ...
     162  int eval() {
     163    return left.eval() * right.eval();
     164  }
     165}
     166\end{lstlisting}
     167\end{minipage}
     168\label{fig.extending.base.type}
     169\caption{Extending our simple language of arithmetic with a new grammatical element.}
     170\end{figure}
     171
     172\begin{figure}[ht]
     173\begin{minipage}[b]{0.45\linewidth}
     174\begin{lstlisting}
     175...
     176show :: Term -> String
     177show (Lit i)   = show i
     178show (Add l r) =
     179  show l ++ " + " ++ show r
     180\end{lstlisting}
     181\end{minipage}
     182\hspace{0.5cm}
     183\begin{minipage}[b]{0.45\linewidth}
     184\begin{lstlisting}
     185interface Term {
     186  int eval();
     187  String show();
     188}
     189
     190class Lit implements Term {
     191  private int v = 0;
     192  ...
     193  int eval() { return v; }
     194  String show() {
     195    return Int.toString(v);
     196  }
     197}
     198
     199class Add implements Term {
     200  private Term left, right = null;
     201  ...
     202  int eval() {
     203    return left.eval() + right.eval();
     204  }
     205  ...
     206  String show() {
     207    return left.show() + \
     208      " + " + right.show();
     209  }
     210}
     211\end{lstlisting}
     212\end{minipage}
     213\label{fig.extending.base.type}
     214\caption{Extending the permitted operations over our simple language of arithmetic.}
     215\end{figure}
    125216
    126217[dpm: reword the above --- hard to phrase precisely ]
     
    131222 \item Bounded vs not-bounded.
    132223\end{itemize}
     224
     225\begin{definition}
     226\label{defn.garrigues.calculus}
     227Inductively define a
     228\end{definition}
    133229
    134230\begin{figure}
Note: See TracChangeset for help on using the changeset viewer.