 Timestamp:
 Nov 5, 2012, 11:14:45 AM (7 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

Papers/polymorphicvariants2012/polymorphicvariants.tex
r2425 r2427 89 89 When it comes to extending algebraic data types with new constructors in this way, we hit a problem: these types are `closed'. 90 90 In order to circumvent this restriction, we must introduce a new algebraic type with the additional constructor, lifting the old typeand any functions defined over itinto this type. 91 This manual extension, coupled with the lifting of any existing functions into the new type, is cumbersome and errorprone. 91 92 92 93 \begin{figure}[ht] … … 96 97 = Lit Int 97 98  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 100 eval :: Term > Int 101 eval (Lit i) = i 102 eval (Add l r) = eval l + eval r 104 103 \end{lstlisting} 105 104 \end{minipage} … … 107 106 \begin{minipage}[b]{0.45\linewidth} 108 107 \begin{lstlisting} 109 108 interface Term { 109 int eval(); 110 } 111 112 class Lit implements Term { 113 private int v = 0; 114 ... 115 int eval() { return v; } 116 } 117 118 class Add implements Term { 119 private Term left, right = null; 120 ... 121 int eval() { 122 return left.eval() + right.eval(); 123 } 124 } 110 125 \end{lstlisting} 111 126 \end{minipage} … … 114 129 \end{figure} 115 130 116 We can compare and contrast functional programming languages' use of algebraic data and pattern matching with the approach taken by objectoriented languages (see Figure~\ref{fig.patternmatching.vs.oop} for a concrete example).117 In mainstream objectoriented 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.131 However, we can look abroad to see what other families of programming languages do to solve this problem. 132 For instance, we can compare and contrast functional programming languages' use of algebraic data and pattern matching with the approach taken by objectoriented languages (see Figure~\ref{fig.patternmatching.vs.oop} for a concrete example). 133 In mainstream, classbased objectoriented languagessuch as Java, for examplealgebraic data types can be emulated by interfaces, coupled with a number of subclasses corresponding to constructors, implementing the `root' interface. 119 134 The base interface of the object hierarchy specifies the permitted operations defined for the type. 120 121 As all operations 135 Branching by pattern matching is emulated using the language's dynamic dispatch mechanism. 136 137 As all permitted operations on 122 138 it is hard to enlarge the set of operations defined over a given type without altering the entire class hierarchy. 123 139 If the interface changes so must every class implementing it. 124 140 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. 141 142 \begin{figure}[ht] 143 \begin{minipage}[b]{0.45\linewidth} 144 \begin{lstlisting} 145 ... 146 data Term' 147 = Lift Term 148  Mul Term' Term' 149 150 eval' :: Term' > Int 151 eval' (Lift t) = eval t 152 eval' (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 ... 159 class 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 ... 176 show :: Term > String 177 show (Lit i) = show i 178 show (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} 185 interface Term { 186 int eval(); 187 String show(); 188 } 189 190 class 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 199 class 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} 125 216 126 217 [dpm: reword the above  hard to phrase precisely ] … … 131 222 \item Bounded vs notbounded. 132 223 \end{itemize} 224 225 \begin{definition} 226 \label{defn.garrigues.calculus} 227 Inductively define a 228 \end{definition} 133 229 134 230 \begin{figure}
Note: See TracChangeset
for help on using the changeset viewer.