# HG changeset patch # User Christian Urban # Date 1410013739 -3600 # Node ID 68d98140b90b45f093569c686da0592956d792e6 # Parent 527fdb90fffebee030d7a2ac813a823f3f41db29 added notation handout diff -r 527fdb90fffe -r 68d98140b90b handouts/notation.pdf Binary file handouts/notation.pdf has changed diff -r 527fdb90fffe -r 68d98140b90b handouts/notation.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/handouts/notation.tex Sat Sep 06 15:28:59 2014 +0100 @@ -0,0 +1,274 @@ +\documentclass{article} +\usepackage{../style} +\usepackage{../langs} + + + +\begin{document} + +\section*{A Crash-Course on Notation} + +\subsubsection*{Characters and Strings} + +In this module we will often use \defn{characters}. While they +are surely familiar, we will make one subtle distinction. If +we want to refer to concrete characters, like \code{a}, +\code{b} and so on, we use a typewriter font. So if we want to +refer to the concrete characters of my email address we shall +write + +\begin{center} +\pcode{christian.urban@kcl.ac.uk} +\end{center} + +\noindent If we need to explicitly indicate the ``space'' +character, we write \VS{}\hspace{1mm}. For example + +\begin{center} +\tt{}hello\VS\hspace{0.5mm}world +\end{center} + + +\noindent But often we do not care +about which characters we use. In such cases we us the italic +font and write $a$, $b$ and so on. So if we need a +representative string, we might write + +\begin{equation}\label{abracadabra} +abracadabra +\end{equation} + +\noindent We do not really care what the characters stand for, +except we do care about is that for example the character $a$ +is not equal to $b$. + +An \defn{alphabet} is a finite set of characters. Often the +letter $\Sigma$ is used to refer to an alphabet. For example +the ASCII characters \pcode{a} to \pcode{z} form an alphabet. +The digits $0$ to $9$ are another alphabet. If nothing else is +specified, we usually assume the alphabet consists of just the +lower-case letters $a$, $b$, \ldots, $z$. Sometimes, however, +we explicitly restrict strings to contain, for example, only +the letters $a$ and $b$. In this case we say the alphabet is +the set $\{a, b\}$. + +\defn{Strings} are lists of characters. Unfortunately, there +are many ways how we can write down strings. In programming +languages, they are usually written as \dq{$hello$} where the +double quotes indicate that we dealing with a string. But +since, strings are lists of characters we could also write +this string as + +\[ +[\text{\it h, e, l, l, o}] +\] + +\noindent The important point is that we can always decompose +such strings. For example, we will often consider the first +character of a string, say $h$, and the ``rest'' of a string +say \dq{\textit{ello}} when making definitions about strings. +There are some subtleties with the empty string, sometimes +written as \dq{} but also as the empty list of characters +$[\,]$. Two strings, for example $s_1$ and $s_2$, can be +\emph{concatenated}, which we write as $s_1 @ s_2$. Suppose we +are given two strings \dq{\textit{foo}} and \dq{\textit{bar}}, +then their concatenation, writen +\dq{\textit{foo}} $@$ \dq{\textit{bar}}, gives +\dq{\textit{foobar}}. Often we will simplify our life and just +drop the double quotes whenever it is clear we are talking +about strings, writing as already in \eqref{abracadabra} just +\textit{foo}, \textit{bar}, \textit{foobar} or \textit{foo $@$ +bar}. + +Some simple properties of string concatenation hold. For +example the concatenation operation is \emph{associative}, +meaning + +\[(s_1 @ s_2) @ s_3 = s_1 @ (s_2 @ s_3)\] + +\noindent are always equal strings. The empty string behaves +like a unit element, therefore + +\[s \,@\, [] = [] \,@\, s = s\] + +While for us strings are just lists of characters, programming +languages often differentiate between the two concepts. In +Scala, for example, there is the type of \code{String} and the +type of lists of characters, \code{List[Char]}. They are not +the same and we need to explicitly coerce elements between the +two types, for example + +\begin{lstlisting}[numbers=none] +scala> "abc".toList +res01: List[Char] = List(a, b, c) +\end{lstlisting} + + +\subsubsection*{Sets and Languages} + +We will use the familiar operations $\cup$ and $\cap$ for +sets. For the empty set we will either write $\varnothing$ or +$\{\,\}$. The set containing, for example, the natural numbers +$1$, $2$ and $3$ we will write as + +\[ +\{1, 2, 3\} +\] + +\noindent The notation $\in$ means \emph{element of}, so $1 +\in \{1, 2, 3\}$ is true and $3 \in \{1, 2, 3\}$ is false. +Sets can potentially have infinitely many elements. For +example the set of all natural numbers $\{0, 1, 2, \ldots\}$ +is infinite. This set is often also abbreviated as +$\mathbb{N}$. We can define sets by giving all elements, like +$\{0, 1\}$, but also by \defn{set comprehensions}. For example +the set of all even natural numbers can be defined as + +\[ +\{n\;|\;n\in\mathbb{N} \wedge n\;\text{is even}\} +\] + +\noindent Though silly, but the set $\{0, 1, 2\}$ could also be +defined by the following set comprehension + +\[ +\{n\;|\; n^2 < 9 \wedge n \in \mathbb{N}\} +\] + +\noindent Notice that set comprehensions could be used +to define set union, intersection and difference: + +\begin{eqnarray*} +A \cup B & \dn & \{x\;|\; x \in A \vee x \in B\}\\ +A \cap B & \dn & \{x\;|\; x \in A \wedge x \in B\}\\ +A \backslash B & \dn & \{x\;|\; x \in A \wedge x \not\in B\} +\end{eqnarray*} + +\noindent For defining sets, we will also often use the notion +of the ``big union''. An example is as follows: + +\begin{equation}\label{bigunion} +\bigcup_{0\le n}\; \{n^2, n^2 + 1\} +\end{equation} + +\noindent which is the set of all squares and their immediate +successors, so + +\[ +\{0, 1, 2, 4, 5, 9, 10, 16, 17, \ldots\} +\] + +\noindent A big union is a sequence of unions which are +indexed typically by a natural number. So the big union in +\eqref{bigunion} could equally be written as + +\[ +\{0, 1\} \cup \{1, 2\} \cup \{4, 5\} \cup \{9, 10\} \cup +\ldots +\] + +\noindent but using the big union notation is more concise. + +An important notion in this module are \defn{Languages}, which +are sets of strings. The main goal for us will be how to +(formally) specify languages and to find out whether a string +is in a language or not. Note that the language containing the +empty string $\{\dq{}\}$ is not equal to the empty language +(or empty set): The former contains one element, namely \dq{} +(also written $[\,]$), but the latter does not contain any. + + +For languages we define the operation of \defn{language +concatenation}, written $A @ B$: + +\begin{equation}\label{langconc} +A @ B \dn \{s_1 @ s_2\;|\; s_1\in A \wedge s_2\in B\} +\end{equation} + +\noindent Be careful to understand the difference: the $@$ +in $s_1 @ s_2$ is string concatenation, while $A @ B$ refers +to the concatenation of two languages (or sets of strings). +As an example suppose $A=\{ab, ac\}$ and $B=\{zzz, qq, r\}$, +then $A \,@\, B$ is + + +\[ +\{abzzz, abqq, abr, aczzz, acqq, acr\} +\] + +\noindent Recall the properties for string concatenation. For +language concatenation we have the following properties + +\begin{center} +\begin{tabular}{ll} +associativity: & $(A @ B) @ C = A @ (B @ C)$\\ +unit element: & $A \,@\, \{[]\} = \{[]\} \,@\, A = A$\\ +zero element: & $A \,@\, \varnothing = \varnothing \,@\, A = +\varnothing$ +\end{tabular} +\end{center} + +\noindent Note the difference: the empty set behaves like $0$ +for multiplication and the set $\{[]\}$ like $1$ for +multiplication. + +Following the language concatenation, we can define a +\defn{language power} operation as follows: + +\begin{eqnarray*} +A^0 & \dn & \{[]\}\\ +A^{n+1} & \dn & A \,@\, A^n +\end{eqnarray*} + +\noindent This definition is by induction on natural numbers. +Note carefully that the zero-case is not defined as the empty +set, but the set containing the empty string. So no matter +what the set $A$ is, $A^0$ will always be $\{[]\}$. (There is +another hint about a connection between the $@$-operation and +multiplication: How is $x^n$ defined and what is $x^0$?) + +Next we can define the \defn{star operation} for languages: +$A^*$ is the union of all powers of $A$, or short + +\[ +A^* \dn \bigcup_{0\le n}\; A^n +\] + +\noindent +Unfolding this definition + +\[ +A^0 \cup A^1 \cup A^2 \cup A^3 \cup \ldots +\] + +\noindent +which is equal to + +\[ +\{[]\} \,\cup\, A \,\cup\, A @ A \,\cup\, A @ A @ A \,\cup\, \ldots +\] + +\noindent we can see that the empty string is always in $A^*$, +no matter what $A$ is. This is because $[] \in A^0$. To make +sure you understand these definition, I leave you to answer +what $\{[]\}^*$ and $\varnothing^*$ are. + +Recall that an alphabet is often referred to by the letter +$\Sigma$. We can now write for the set of all strings over +this alphabet $\Sigma^*$. In doing so we also include the +empty string as a possible string over $\Sigma$. So if +$\Sigma = \{a, b\}$ then $\Sigma^*$ is + +\[ +\{[], a, b, ab, ba, aaa, aab, aba, abb, baa, bab, \ldots\} +\] + +\noindent or in other words all strings containing $a$s and +$b$s only. + +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: diff -r 527fdb90fffe -r 68d98140b90b handouts/scala-ho.pdf Binary file handouts/scala-ho.pdf has changed diff -r 527fdb90fffe -r 68d98140b90b handouts/scala-ho.tex --- a/handouts/scala-ho.tex Wed Sep 03 14:57:43 2014 +0100 +++ b/handouts/scala-ho.tex Sat Sep 06 15:28:59 2014 +0100 @@ -18,10 +18,11 @@ Android and JavaScript.} Unlike Java, however, Scala often allows programmers to write very concise and elegant code. Some therefore say Scala is the much better Java. A number of -companies, The Guardian, Twitter, Coursera, LinkedIn to name a -few, either use Scala exclusively in production code, or at -least to some substantial degree. If you want to try out Scala -yourself, the Scala compiler can be downloaded from +companies, The Guardian, Twitter, Coursera, FourSquare, +LinkedIn to name a few, either use Scala exclusively in +production code, or at least to some substantial degree. If +you want to try out Scala yourself, the Scala compiler can be +downloaded from \begin{quote} \url{http://www.scala-lang.org} diff -r 527fdb90fffe -r 68d98140b90b langs.sty --- a/langs.sty Wed Sep 03 14:57:43 2014 +0100 +++ b/langs.sty Sat Sep 06 15:28:59 2014 +0100 @@ -61,3 +61,4 @@ \newcommand{\code}[1]{{\lstinline{#1}}} +\newcommand{\pcode}[1]{{\lstset{language={},keywordstyle=\color{black}}\lstinline{#1}}} diff -r 527fdb90fffe -r 68d98140b90b style.sty --- a/style.sty Wed Sep 03 14:57:43 2014 +0100 +++ b/style.sty Sat Sep 06 15:28:59 2014 +0100 @@ -9,5 +9,32 @@ \definecolor{darkblue}{rgb}{0,0,0.6} \usepackage[colorlinks=true,urlcolor=darkblue,linkcolor=darkblue]{hyperref} -\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% +\newcommand\grid[1]{% +\begin{tikzpicture}[baseline=(char.base)] + \path[use as bounding box] + (0,0) rectangle (1em,1em); + \draw[red!50, fill=red!20] + (0,0) rectangle (1em,1em); + \node[inner sep=1pt,anchor=base west] + (char) at (0em,\gridraiseamount) {#1}; +\end{tikzpicture}} +\newcommand\gridraiseamount{0.12em} + +\makeatletter +\newcommand\Grid[1]{% + \@tfor\z:=#1\do{\grid{\z}}} +\makeatother + +\newcommand\Vspace[1][.3em]{% + \mbox{\kern.06em\vrule height.3ex}% + \vbox{\hrule width#1}% + \hbox{\vrule height.3ex}} + +\def\VS{\Vspace[0.6em]} + + +\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}} +\newcommand{\defn}[1]{\textit{\textbf{#1}}} +\newcommand{\dq}[1]{\mbox{\tt{"}}#1\mbox{\tt{"}}} + \definecolor{codegray}{gray}{0.9}