52 developing programs. Once you installed Scala, you can start |
52 developing programs. Once you installed Scala, you can start |
53 the interpreter by typing on the command line: |
53 the interpreter by typing on the command line: |
54 |
54 |
55 \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] |
55 \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] |
56 $ scala |
56 $ scala |
57 Welcome to Scala version 2.11.2 (Java HotSpot(TM) 64-Bit Server VM). |
57 Welcome to Scala version 2.11.8 (Java HotSpot(TM) 64-Bit Server VM). |
58 Type in expressions to have them evaluated. |
58 Type in expressions for evaluation. Or try :help. |
59 Type :help for more information. |
|
60 |
59 |
61 scala> |
60 scala> |
62 \end{lstlisting} |
61 \end{lstlisting} |
63 |
62 |
64 \noindent The precise response may vary due to the platform |
63 \noindent The precise response may vary due to the platform |
131 Scala. For example in ``every-day mathematics'' we define |
130 Scala. For example in ``every-day mathematics'' we define |
132 regular expressions simply by giving the grammar |
131 regular expressions simply by giving the grammar |
133 |
132 |
134 \begin{center} |
133 \begin{center} |
135 \begin{tabular}{r@{\hspace{2mm}}r@{\hspace{2mm}}l@{\hspace{13mm}}l} |
134 \begin{tabular}{r@{\hspace{2mm}}r@{\hspace{2mm}}l@{\hspace{13mm}}l} |
136 $r$ & $::=$ & $\varnothing$ & null\\ |
135 $r$ & $::=$ & $\ZERO$ & null\\ |
137 & $\mid$ & $\epsilon$ & empty string\\ |
136 & $\mid$ & $\ONE$ & empty string\\ |
138 & $\mid$ & $c$ & single character\\ |
137 & $\mid$ & $c$ & single character\\ |
139 & $\mid$ & $r_1 \cdot r_2$ & sequence\\ |
138 & $\mid$ & $r_1 \cdot r_2$ & sequence\\ |
140 & $\mid$ & $r_1 + r_2$ & alternative / choice\\ |
139 & $\mid$ & $r_1 + r_2$ & alternative / choice\\ |
141 & $\mid$ & $r^*$ & star (zero or more)\\ |
140 & $\mid$ & $r^\star$ & star (zero or more)\\ |
142 \end{tabular} |
141 \end{tabular} |
143 \end{center} |
142 \end{center} |
144 |
143 |
145 \noindent This grammar specifies what regular expressions are |
144 \noindent This grammar specifies what regular expressions are |
146 (essentially a kind of tree-structure with three kinds of |
145 (essentially a kind of tree-structure with three kinds of |
153 |
152 |
154 Implementing the regular expressions from above in Scala is |
153 Implementing the regular expressions from above in Scala is |
155 actually very simple: It first requires an \emph{abstract |
154 actually very simple: It first requires an \emph{abstract |
156 class}, say, \code{Rexp}. This will act as the type for |
155 class}, say, \code{Rexp}. This will act as the type for |
157 regular expressions. Second, it requires a case for each |
156 regular expressions. Second, it requires a case for each |
158 clause in the grammar. The cases for $\varnothing$ and |
157 clause in the grammar. The cases for $\ZERO$ and $\ONE$ do not |
159 $\epsilon$ do not have any arguments, while in all the other |
158 have any arguments, while in all the other cases we do have |
160 cases we do have arguments. For example the character regular |
159 arguments. For example the character regular expression needs |
161 expression needs to take as an argument the character it is |
160 to take as an argument the character it is supposed to |
162 supposed to recognise. In Scala, the cases without arguments |
161 recognise. In Scala, the cases without arguments are called |
163 are called \emph{case objects}, whereas the ones with |
162 \emph{case objects}, whereas the ones with arguments are |
164 arguments are \emph{case classes}. The corresponding Scala |
163 \emph{case classes}. The corresponding Scala code is as |
165 code is as follows: |
164 follows: |
166 |
165 |
167 \begin{lstlisting}[numbers=none] |
166 \begin{lstlisting}[numbers=none] |
168 abstract class Rexp |
167 abstract class Rexp |
169 case object NULL extends Rexp |
168 case object ZERO extends Rexp |
170 case object EMPTY extends Rexp |
169 case object ONE extends Rexp |
171 case class CHAR (c: Char) extends Rexp |
170 case class CHAR (c: Char) extends Rexp |
172 case class SEQ (r1: Rexp, r2: Rexp) extends Rexp |
171 case class SEQ (r1: Rexp, r2: Rexp) extends Rexp |
173 case class ALT (r1: Rexp, r2: Rexp) extends Rexp |
172 case class ALT (r1: Rexp, r2: Rexp) extends Rexp |
174 case class STAR (r: Rexp) extends Rexp |
173 case class STAR (r: Rexp) extends Rexp |
175 \end{lstlisting} |
174 \end{lstlisting} |
200 if there is the need for some non-standard initialisation, you |
199 if there is the need for some non-standard initialisation, you |
201 can of course define such a constructor in Scala too. But we |
200 can of course define such a constructor in Scala too. But we |
202 omit such ``tricks'' here. |
201 omit such ``tricks'' here. |
203 |
202 |
204 Note that Scala in its response says the variable \code{r} is |
203 Note that Scala in its response says the variable \code{r} is |
205 of type \lstinline[emph={ALT}]!ALT!, not \code{Rexp}. This |
204 of type \code{ALT}, not \code{Rexp}. This might be a bit |
206 might be a bit unexpected, but can be explained as follows: |
205 unexpected, but can be explained as follows: Scala always |
207 Scala always tries to find the most general type that is |
206 tries to find the most general type that is needed for a |
208 needed for a variable or expression, but does not |
207 variable or expression, but does not ``over-generalise''. In |
209 ``over-generalise''. In our definition the type \code{Rexp} is |
208 our definition the type \code{Rexp} is more general than |
210 more general than \lstinline[emph={ALT}]!ALT!, since it is the |
209 \code{Rexp}, since it is the abstract class. But in this case |
211 abstract class. But in this case there is no need to give |
210 there is no need to give \code{r} the more general type of |
212 \code{r} the more general type of \code{Rexp}. This is |
211 \code{Rexp}. This is different if you want |
213 different if you want to form a list of regular expressions, |
212 to form a list of regular expressions, for example |
214 for example |
213 |
215 |
214 \begin{lstlisting}[numbers=none] |
216 \begin{lstlisting}[numbers=none] |
215 scala> val ls = List(ALT(CHAR('a'), CHAR('b')), ZERO) |
217 scala> val ls = List(ALT(CHAR('a'), CHAR('b')), NULL) |
216 ls: List[Rexp] = List(ALT(CHAR(a),CHAR(b)), ZERO) |
218 ls: List[Rexp] = List(ALT(CHAR(a),CHAR(b)), NULL) |
|
219 \end{lstlisting} |
217 \end{lstlisting} |
220 |
218 |
221 \noindent In this case, Scala needs to assign a common type to |
219 \noindent In this case, Scala needs to assign a common type to |
222 the regular expressions so that it is compatible with the |
220 the regular expressions so that it is compatible with the |
223 fact that lists can only contain elements of a single type. In |
221 fact that lists can only contain elements of a single type. In |
299 produces another regular expression that can recognise the |
297 produces another regular expression that can recognise the |
300 reversed strings. They define this function as follows: |
298 reversed strings. They define this function as follows: |
301 |
299 |
302 \begin{center} |
300 \begin{center} |
303 \begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l} |
301 \begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l} |
304 $rev(\varnothing)$ & $\dn$ & $\varnothing$\\ |
302 $rev(\ZERO)$ & $\dn$ & $\ZERO$\\ |
305 $rev(\epsilon)$ & $\dn$ & $\epsilon$\\ |
303 $rev(\ONE)$ & $\dn$ & $\ONE$\\ |
306 $rev(c)$ & $\dn$ & $c$\\ |
304 $rev(c)$ & $\dn$ & $c$\\ |
307 $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ |
305 $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ |
308 $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ |
306 $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ |
309 $rev(r^*)$ & $\dn$ & $rev(r)^*$\\ |
307 $rev(r^*)$ & $\dn$ & $rev(r)^*$\\ |
310 \end{tabular} |
308 \end{tabular} |