# HG changeset patch # User Christian Urban # Date 1479951878 0 # Node ID ca5884c2e3bdaea6a07dde13eedd5b0877e55851 # Parent 3506b681c191f7a8f73a36c5335012c5ecfd022f updated diff -r 3506b681c191 -r ca5884c2e3bd progs/lecture3.scala --- a/progs/lecture3.scala Wed Nov 23 13:32:01 2016 +0000 +++ b/progs/lecture3.scala Thu Nov 24 01:44:38 2016 +0000 @@ -1,18 +1,307 @@ -// regular expressions -// ?? polymorphism +// Scala Lecture 3 +//================= + + +// One of only two places where I conceded to mutable +// data structures: The following function generates +// new labels + +var counter = -1 + +def fresh(x: String) = { + counter += 1 + x ++ "_" ++ counter.toString() +} + +fresh("x") +fresh("x") + +// this can be avoided, but would have made my code more +// complicated + + +// Tail recursion +//================ + +def my_contains(elem: Int, lst: List[Int]) : Boolean = lst match { + case Nil => false + case x::xs => + if (x == elem) true else my_contains(elem, xs) +} + +my_contains(4, List(1,2,3)) +my_contains(2, List(1,2,3)) + +my_contains(1000000, (1 to 1000000).toList) +my_contains(1000001, (1 to 1000000).toList) + + +//factorial 0.1 + +def fact(n: Long): Long = + if (n == 0) 1 else n * fact(n - 1) + +fact(10000) + -A function should do one thing, and only one thing. +def factT(n: BigInt, acc: BigInt): BigInt = + if (n == 0) acc else factT(n - 1, n * acc) + + +factT(10000, 1) + +// my_contains and factT are tail recursive +// you can check this with + +import scala.annotation.tailrec + +// and the annotation @tailrec + +// for tail-recursive functions the compiler +// generates a loop-like code, which does not +// to allocate stack-space in each recursive +// call; scala can do this only for tail-recursive +// functions + +// consider the following "stupid" version of the +// coin exchange problem: given some coins and a, +// total, what is the change can you get -Make your variables immutable, unless there's a good reason not to. +val coins = List(4,5,6,8,10,13,19,20,21,24,38,39, 40) + +def first_positive[B](lst: List[Int], f: Int => Option[B]): Option[B] = lst match { + case Nil => None + case x::xs => + if (x <= 0) first_positive(xs, f) + else { + val fx = f(x) + if (fx.isDefined) fx else first_positive(xs, f) + } +} + + +def search(total: Int, coins: List[Int], cs: List[Int]): Option[List[Int]] = { + if (total < cs.sum) None + else if (cs.sum == total) Some(cs) + else first_positive(coins, (c: Int) => search(total, coins, c::cs)) +} + +search(11, coins, Nil) +search(111, coins, Nil) +search(111111, coins, Nil) -You can be productive on Day 1, but the language is deep, so as you go -along you’ll keep learning, and finding newer, better ways to write -code. Scala will change the way you think about programming (and -that’s a good thing). +val junk_coins = List(4,-2,5,6,8,0,10,13,19,20,-3,21,24,38,39, 40) +search(11, junk_coins, Nil) +search(111, junk_coins, Nil) + + +import scala.annotation.tailrec + +@tailrec +def asearch(total: Int, coins: List[Int], acc_cs: List[List[Int]]): Option[List[Int]] = acc_cs match { + case Nil => None + case x::xs => + if (total < x.sum) asearch(total, coins, xs) + else if (x.sum == total) Some(x) + else asearch(total, coins, coins.filter(_ > 0).map(_::x) ::: xs) +} + +val start_acc = coins.filter(_ > 0).map(List(_)) +asearch(11, junk_coins, start_acc) +asearch(111, junk_coins, start_acc) +asearch(111111, junk_coins, start_acc) + +// moral: whenever a recursive function is resource-critical +// (i.e. works on large recursion depth), then you need to +// write it in tail-recursive fashion + + +// Polymorphism +//============== + +def length_int_list(lst: List[Int]): Int = lst match { + case Nil => 0 + case x::xs => 1 + length_int_list(xs) +} + +length_int_list(List(1, 2, 3, 4)) + + +def length[A](lst: List[A]): Int = lst match { + case Nil => 0 + case x::xs => 1 + length(xs) +} + -Of all of Scala’s benefits, what I like best is that it lets you write -concise, readable code +def map_int_list(lst: List[Int], f: Int => Int): List[Int] = lst match { + case Nil => Nil + case x::xs => f(x)::map_int_list(xs, f) +} + +map_int_list(List(1, 2, 3, 4), square) + + +// Remember? +def first[A, B](xs: List[A], f: A => Option[B]): Option[B] = ... + + +// polymorphic classes +//(trees with some content) + +abstract class Tree[+A] +case class Node[A](elem: A, left: Tree[A], right: Tree[A]) extends Tree[A] +case object Leaf extends Tree[Nothing] + +def insert[A](tr: Tree[A], n: A): Tree[A] = tr match { + case Leaf => Node(n, Leaf, Leaf) + case Node(m, left, right) => + if (n == m) Node(m, left, right) + else if (n < m) Node(m, insert(left, n), right) + else Node(m, left, insert(right, n)) +} + + +// the A-type needs to be ordered + +abstract class Tree[+A <% Ordered[A]] +case class Node[A <% Ordered[A]](elem: A, left: Tree[A], right: Tree[A]) extends Tree[A] +case object Leaf extends Tree[Nothing] + + +def insert[A <% Ordered[A]](tr: Tree[A], n: A): Tree[A] = tr match { + case Leaf => Node(n, Leaf, Leaf) + case Node(m, left, right) => + if (n == m) Node(m, left, right) + else if (n < m) Node(m, insert(left, n), right) + else Node(m, left, insert(right, n)) +} + + +val t1 = Node(4, Node(2, Leaf, Leaf), Node(7, Leaf, Leaf)) +insert(t1, 3) + +val t2 = Node('b', Node('a', Leaf, Leaf), Node('f', Leaf, Leaf)) +insert(t2, 'e') -ScalaTest download page: http://www.scalatest.org/download +// Regular expressions - the power of DSLs +//========================================= + + +abstract class Rexp +case object ZERO extends Rexp +case object ONE extends Rexp +case class CHAR(c: Char) extends Rexp +case class ALT(r1: Rexp, r2: Rexp) extends Rexp +case class SEQ(r1: Rexp, r2: Rexp) extends Rexp +case class STAR(r: Rexp) extends Rexp + + +// (ab)* +val r0 = ?? + + +// some convenience for typing in regular expressions +import scala.language.implicitConversions +import scala.language.reflectiveCalls + +def charlist2rexp(s: List[Char]): Rexp = s match { + case Nil => ONE + case c::Nil => CHAR(c) + case c::s => SEQ(CHAR(c), charlist2rexp(s)) +} +implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList) + + +val r1 = STAR("ab") +val r2 = STAR("") +val r3 = STAR(ALT("ab", "ba")) + + +implicit def RexpOps (r: Rexp) = new { + def | (s: Rexp) = ALT(r, s) + def % = STAR(r) + def ~ (s: Rexp) = SEQ(r, s) +} + +implicit def stringOps (s: String) = new { + def | (r: Rexp) = ALT(s, r) + def | (r: String) = ALT(s, r) + def % = STAR(s) + def ~ (r: Rexp) = SEQ(s, r) + def ~ (r: String) = SEQ(s, r) +} + +val digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" +val sign = "+" | "-" | "" +val number = sign ~ digit ~ digit.% + + + +// Lazyness with style +//===================== + +// The concept of lazy evaluation doesn’t really exist in +// non-functional languages, but it is pretty easy to grasp. +// Consider first + +def square(x: Int) = x * x + +square(42 + 8) + +// this is called strict evaluation + + +def expensiveOperation(n: BigInt): Boolean = expensiveOperation(n + 1) +val a = "foo" +val b = "foo" + +val test = if ((a == b) || expensiveOperation(0)) true else false + +// this is called lazy evaluation +// you delay compuation until it is really +// needed; once calculated though, does not +// need to be re-calculated + +// a useful example is +def time_needed[T](i: Int, code: => T) = { + val start = System.nanoTime() + for (j <- 1 to i) code + val end = System.nanoTime() + ((end - start) / i / 1.0e9) + " secs" +} + + +// streams (I do not care how many) +// primes: 2, 3, 5, 7, 9, 11, 13 .... + +def generatePrimes (s: Stream[Int]): Stream[Int] = + s.head #:: generatePrimes(s.tail filter (_ % s.head != 0)) + +val primes: Stream[Int] = generatePrimes(Stream.from(2)) + +primes.filter(_ > 100).take(2000).toList + +time_needed(1, primes.filter(_ > 100).take(2000).toList) +time_needed(1, primes.filter(_ > 100).take(2000).toList) + + + +// streams are useful for implementing search problems ;o) + + + + +// The End +//========= + +// A function should do one thing, and only one thing. + +// Make your variables immutable, unless there's a good +// reason not to. + +// You can be productive on Day 1, but the language is deep. + +// I like best about Scala that it lets you write +// concise, readable code diff -r 3506b681c191 -r ca5884c2e3bd slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r 3506b681c191 -r ca5884c2e3bd slides/slides03.tex --- a/slides/slides03.tex Wed Nov 23 13:32:01 2016 +0000 +++ b/slides/slides03.tex Thu Nov 24 01:44:38 2016 +0000 @@ -3,6 +3,7 @@ \usepackage{../graphics} \usepackage{../langs} %\usepackage{../data} +\usepackage[export]{adjustbox} \hfuzz=220pt @@ -18,7 +19,7 @@ \newcommand{\bl}[1]{\textcolor{blue}{#1}} % beamer stuff -\renewcommand{\slidecaption}{PEP (Scala) 02, King's College London} +\renewcommand{\slidecaption}{PEP (Scala) 03, King's College London} \begin{document} @@ -28,7 +29,7 @@ \frametitle{% \begin{tabular}{@ {}c@ {}} \\[5mm] - \huge PEP Scala (2) + \huge PEP Scala (3) \end{tabular}} \normalsize @@ -44,50 +45,171 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Why Scala?\end{tabular}} - +\begin{frame}[c, fragile] +\frametitle{The Joy of Immutability} \begin{itemize} -\item \large {\bf You can avoid \textcolor{blue}{\texttt{null}}}: -\end{itemize} - +\item If you need to manipulate some data in a list say, then you make + a new list with the updated values, rather than revise the original + list. Easy!\medskip -\begin{textblock}{6}(1,5) - \begin{bubble}[10.5cm]\small - ``I call it my billion-dollar mistake. It was the invention of - the null reference in 1965. At that time, I was designing the - first comprehensive type system for references in an object - oriented language (ALGOL W). My goal was to ensure that all use - of references should be absolutely safe, with checking performed - automatically by the compiler. But I couldn't resist the - temptation to put in a null reference, simply because it was so - easy to implement. This has led to innumerable errors, - vulnerabilities, and system crashes, which have probably caused - a billion dollars of pain and damage in the last forty years.'' - \hfill Sir Tony (Hoare) -\end{bubble} -\end{textblock} + {\small + \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] + val old_list = List(1, 2, 3, 5) + val new_list = 0 :: old_list + \end{lstlisting}} -\begin{textblock}{5}(11.8,1) -\includegraphics[scale=0.20]{hoare.jpg}\\ -\end{textblock} - +\item You do not have to be defensive about who can access the data + (concurrency, lazyness). +\end{itemize} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{\huge\textbf{\texttt{return}}} +\begin{frame}[t] +\frametitle{Email: Hate 'val'} + +\mbox{}\\[-25mm]\mbox{} + +\begin{center} + \begin{bubble}[10.5cm] + Subject: \textbf{Hate '\textbf{\texttt{val}}'}\hfill 01:00 AM\medskip\\ + + Hello Mr Urban,\medskip\\ + + I just wanted to ask, how are we suppose to work + with the completely useless \textbf{\texttt{val}}, that can’t be changed ever? Why is + this rule active at all? I’ve spent 4 hours not thinking on the + coursework, but how to bypass this annoying rule. What’s the whole + point of all these coursework, when we can’t use everything Scala + gives us?!?\medskip\\ -\begin{center}\LARGE -you should never use it + Regards.\\ + \mbox{}\hspace{5mm}\textcolor{black!50}{<>}\\ + \end{bubble} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\mbox{}\\[-25mm]\mbox{} + +\begin{center} + \begin{bubble}[10.5cm] + Subject: \textbf{Re: Hate '\textbf{\texttt{val}}'}\hfill 01:02 AM\bigskip\bigskip\\ + + \textcolor{black!70}{ + \textit{\large<>}}\bigskip\bigskip\bigskip + + PS: What are you trying to do where you desperately want to use \texttt{var}? + \end{bubble} \end{center} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c,fragile] + +\begin{textblock}{6}(0.5,0.5) +\begin{bubble}[11.5cm] + \small + Subject: \textbf{Re: Re: Hate '\textbf{\texttt{val}}'}\hfill 01:04 AM\medskip\\ + + \textbf{Right now my is\_legal function works fine:} + +\footnotesize\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] + def is_legal(dim: Int, path: Path)(x: Pos): Boolean = { + var boolReturn = false + if(x._1 > dim || x._2 > dim || x._1 < 0 || x._2 < 0) { + else { var breakLoop = false + if(path == Nil) { boolReturn = true } + else { for(i <- 0 until path.length) { + if(breakLoop == false) { + if(path(i) == x) { + boolReturn = true + breakLoop = true + } + else { boolReturn = false } + } else breakLoop + } + } + boolReturn + } +\end{lstlisting} +\end{bubble} +\end{textblock} + +\begin{textblock}{6}(8.2,11.8) +\begin{bubble}[5.5cm]\footnotesize\bf +\ldots{}but I can’t make it work with boolReturn being val. What approach would +you recommend in this case, and is using var in this case justified? +\end{bubble} +\end{textblock} + +\only<2>{ +\begin{textblock}{6}(0.3,11.8) + \begin{bubble}[3.1cm] + \textbf{Me:} \includegraphics[scale=0.08, valign=t]{../pics/throwup.jpg} + \end{bubble} +\end{textblock}} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t,fragile] + +\mbox{}\\[-25mm]\mbox{} + +\begin{textblock}{6}(0.5,2) + \begin{bubble}[11.5cm] + Subject: \textbf{Re: Re: Re: Hate '\textbf{\texttt{val}}'}\hfill 01:06 AM\bigskip\\ + \small + + OK. So you want to make sure that the \texttt{x}-position is not outside the + board....and furthermore you want to make sure that the \texttt{x}-position + is not yet in the path list. How about something like\bigskip + +\footnotesize\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] + def is_legal(dim: Int, path: Path)(x: Pos): Boolean = + ...<>... && !path.contains(x) +\end{lstlisting}\bigskip + + \small Does not even contain a \texttt{val}. + \end{bubble} +\end{textblock} + +\begin{textblock}{6}(7,12) +\footnotesize\textcolor{black!50}{(This is all on one line)} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t,fragile] + +\mbox{}\\[-15mm]\mbox{} + +\begin{textblock}{6}(1,3) + \begin{bubble}[10.5cm] + Subject: \textbf{Re: Re: Re: Re: Hate '\textbf{\texttt{val}}'}\hfill 11:02 AM\bigskip\bigskip\\ + + THANK YOU! You made me change my coding perspective. Because of you, + I figured out the next one\ldots + \end{bubble} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{Types} @@ -122,11 +244,32 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\begin{frame}[t] +\frametitle{Where to go on from here?} + +\begin{itemize} +\item Martin Odersky (EPFL)\ldots he is currently throwing out everything + and starts again with the dotty compiler for Scala\medskip + +\item Elm (\url{http://elm-lang.org})\ldots web applications with style\medskip + +\item Haskell, Ocaml, Standard ML, Scheme +\end{itemize} +\end{frame} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{\begin{tabular}{c}\\[3cm]\alert{Questions?}\end{tabular}} -\mbox{} +\mbox{}\footnotesize +Thanks: ``\it{}By the way - Scala is really getting quite fun +when you start to get the hang of it\ldots'' + \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}