nicokosi/notes-on-funprog2.md

## notes-on-funprog2.md

      
    Raw
  

              notes-on-funprog2.md
            
          
    Week 1

lecture "Recap: Functions and Pattern Matching"

recursive function + case classes + pattern matching: example JSON printer (Scala -> JSON)
pattern matching in Scala SDK: PartialFunction is a Trait with def isDefinedAt(x: A): Boolean
lecture "Recap: Collections"


Iterable (base class)

Seq
IndexedSeq concrete implems below :

Vector
etc.


LinearSeq concrete implems below :

List : concrete implem
etc.


Set

etc.


Map

etc.


All collections have map, flatMap, filter, foldLeft, foldRight
Idealized implementation of these functions use pattern matching.
For expressions:

are interesting for simplifying combinations of map, flatMap and filter.
can use pattern matching in the left-hand side. Example:

val data: List[JSON] = ...
for {
  JObj(bindings) <- data // implicit filter
  JSeq(phones) = bindings("phoneNumbers")
  JObj(phone) <- phones
  JStr(digits) = phone("number")
  if digits starstWith "212"
} yield (bindings("lastname"))
lecture "Lecture 1.1 - Queries with For"

For expressions used as a DSL for database queries.
case classe Book(title: String, authors: List[String])

// mini database:
val book: List[Book] = List(
 Book(title="Effective Java", authors = List("Joshua Bloch"))

# queries:
// find books whose author's name is "Bird"
for (b <- books ; a <- b.authors if a startsWith "Bird")
yield b.title


// find names of all authors who have written at least 2 books
 {
  for {
   b1 <- books
   b2 <- books
   // if b1 != b2 # would return dupes
   if b1.title < b2.title
   a1 <- b1.authors
   a2 <- b2.authors
   if a1 == a2
 } yield a1
} distinct // otherwise, would return dupes

// or better, fix our model so that we don't need to use distinct in queries:
val book: List[Book] = Set( # use a Set instead of a List
 Book(title="Effective Java", authors = List("Joshua Bloch"))
lecture "Translation of For"

map, flatMap and filter can be implemented with for expressions.
But the compiler implement for expresions with higher-order functions map, flatMap and filter.
// case 1:
for (x <- e1) yield e2
// is translated to: e1.map(x => e2)

// case 2:
for (x <- e1 if f; s) yield e2
// is translated to: for (x <- e1.withFilter(x => f); s) yield e2
// withFilter is a lazy variant of filter that does not produce intermediate list

// case 3:
for (x <- e1; y <- e2; s) yield e3
// is translated to:
// e1.flatMap(x => for (y <- e2; s) yield e3)
// and the translation continues...
This translation is not onyly done for collections.
It is useful for parsers, databases, etc.
Examples :

ScalaQuery and Slick Scala libraries
Microsoft LINQ (C#)
If you provide map, flatMap and filter in your own type, you can use for expressions.

Functional random generators

Another use of for expressions: random value generator (strings, numbers, etc.)
trait Generator[T+] {
  def generate: T
}

val integers = new Generator[Int] {
 val rand = new java.util.Random
 def generate = rand.nextInt()
}

val booleans = new Generator[Boolean] {
 def generate = integers.generate > 0
}

val pairs = new Generator[(Int, Int)] {
 def generate = (integers.generate, integers.generate)
}

//etc.

How to reduce boiler-plate code?
trait Generator[T+] {
  
  self => // alias for 'this'
  
  def generate: T
  
  def map[S](f: T => S): Generator[S] {
   def generate = f(self.generate) // this.generate would lead to never-ending recursive call
   // other way : f(Generator.this.generate
  }
  
  def flatMap[S](f: T => Generator[S]: Generator[S] = new Generator[S] {
   def generate = f(self.generate).generate
  }
  
}

val booleans = for (x <- integers) yield x > 0

val pairs = for{
 x <- t
 y <- u
} yield (x, y)

def single ...

def oneOf[T](xs: T*) { //vararg
}

def lists: Generators[List[Int]] = for{
 isEmpty <- booleans
 list <- if (isEmpty) emptyLits else nonEmptyLists
} yield list

def emptyList = single(Nil)

def nonEmptyLists = for {
 head <- integers 
 tail <- lists
} yield head :: tail

example: tree generator
application: random testing via property-based testing (cf. ScalaCheck library)
Monads

Monad is a design pattern
A monad M is a parametric type M[T]:

with 2 operations: flatMap (or bind) and unit
having both of them gives map operation
that statify laws

Examples:
List is a monad with unit(x) = List(x)
Set is a monad with unit(x) = Set(x)
Option is a monad with unit(x) = Some(x)
Generator is a monad with unit(x) = single(x)
3 laws:

associativity: the result of two bind calls does not depend of their order ; ex: (x + y) + z = x + (y + z)
(m flatMap f) flatMap g == m flatMap ((x => f(x) flatMap g))
left unit: unit(x) flatMap f == f(x)
right unit: m flatMap unit == m

Monoid is a simple form of monad that does not return anything
Examples:
Option is a monad
Try is not a monad (left unit law fails)
Additional law: "monads with zero" also define withFilter
Week 2

Structural Induction on Trees

Proving session on trees:
To prove a property P(t) for all trees t of a certain type, we'll need to:

show that P(l) holds for all leaves l
for each type of internal nodes t with subtrees s1, ..., sn, show that:
P(s1) ^ ... ^ P(sn) implies P(t)

Example: IntSets
Stream

Streams are like lists with tail evaluated on demand (lazily)
=> short and elegant notation (/ recursive)
Example: find the second prime number between 1000 and 10000
((1000 to 10000) filter isPrime)(1)
see #:: that applies to streams (because :: produces a list, not a stream)
Implem:
trait Stream[+A] extends Seq[A] {
  def isEmpty: Boolean
  def head: A
  def tail: Stream[A]
}

object Stream {

 // note: the only difference with list is the type of the 2nd parameter:
 def cons[T] (hd: T, tl: => Stream[T]) = new Stream[T] {
  def isEmpty = false
  def head = hd
  def tail = tl
 }
 
 val empty = new Stream[Nothing] {
  def isEmpty = true
  def head = throw new NoSuchElementException("empty head")
  def tail = throw new NoSuchElementException("empty tail")
 }

}

class Stream[T+] {

 def filter(p: T => Boolean): Stream[T] {
  if (isEmpty) this
  elseif (p(head)) cons(head, tail.filter(p))
  else tail.filter(p)
 }

}
lecture "Lazy evaluation"

Previous implem has an issue: if tail is called several times, stream will be recomputed.
Solution: store th 1st tail evaluation
Haskell uses lazy evaluation, by default.
Scala:

uses strict evaluation, by default.
allows lazy with `lazy val"

lazy val x = expr

Fix in our Stream implem:
 def cons[T] (hd: T, tl: => Stream[T]) = new Stream[T] {
  def head = hd
  lazy val tail = tl
 }

lecture "Case study: infinite streams"

ex:
// all integers:
def from(n: Int): Stream[Int] = n #:: from(n+1)

val naturalNumbers = from()
val multiplesOf4 = nats maps (_ * 4)
// etc.
Usage #1 : Prime numbers via the Sieve of Eratosthenes

 def sieve(: Stream[Int]): Stream[Int}
  s.head #:: sieve(s.tail filter (_ % s.head != 0))

 val primes = sieves(from(2))
Usage #2 : square roots

 def srtStream(x: Double): Stream[Double] = {
 
  def improve(guess: Double) = (guess + x  / guess) / 2
  lazy val guesses: Stream[Double] = 1 #:: (guesses map improve)
  guesses
 }
 
 def isGoodEnough(guess: Double, x: Double) =
   math.abs((guess * guess - x) / x) < 0.0001

 sqrtStream(4) filter (isGoodEnough(_, 4))
lecture "Case study: Water pouring problem"

cf. "Design of computer programs" (more imperative solution in Python)
How to use:

a glass of 4 cl.
a glass of 9 cl.
a big jar
to fill to mesure 6 cl ?

Our model:
Glass: Int
State: Vector[Int]
Moves:
Empty(glass)
Fill(glass)
Pour(from, to)
class Pouring(capacity: Vector[Int]) {

 type State = Vector[Int]
 val initialState = capacity map (x => 0)
 
 trait  {
  def change(state: State): State
 }
 case class Empty(glass: Int) extends Move {
  def change(state: State) = state updated (glass, 0)
 }
 case class Fill(glass: Int) extends Move {
  def change(state: State) = state updated (glass, capacity(glass))
 }
 case class Pour(from: Int, to: Int) extends Move {
  def change(state: State) = {
   val amount = state(from) min (capacityt(to) - state(to))
   state updated (from, state(from) - amount) updated (to, state(to) + amount)
  }
 }
 
 val glasses = 0 until capacity.length
 
 val moves =
  (for (g <- glasses) yield Empty(g)) ++
  (for (g <- glasses) yield Fill(g)) ++
  (for (from <- glasses; to <- glasses if from != to) yield Pour(from, to)
  
}

class Path(history: List[Move], val endState: State) {
 def extend(move: Move) = new Path(move :: history, move change endState)
 override def toString = (history.reverse mkString " ") + "--> " + endState
}

val initialPath = new Path(Nil, initialState)

def from(path: Set[Path], explored: Set[Path]): Stream[Set[Path]] =
 if (paths.isEmpty) Stream.empty
 else {
  val more = for {
   path <- paths
   next <- moves map path.extend
  } yield next
  if (!explored contains next.endState) 
  paths #:: from(more)
 }

val pathSets = from(Set(initialPath), explored ++ (more map (_.endState)), Set(inialState)
def solution(target: Int) Stream[Path] =
 for {
  pathSet <- pathSets
  path <- pathSet
  if (path.endState contains targer)
 } yield path


object Test {}
 val problem = new Pouring(Vector(4, 7))
 problem.moves
 
 problem.solutions(6)
}
Guidelines:

name everything you can (do not use "single-letter variables like mathematicians")
put operations into natural scopes i.e. change method inside Move class)
keep degrees of freedom for future refinements

Week 3: Functions and State

lecture Functions and State

Until now, we wrote pure functions with immutable data.
=> side-effet free
But how to work with mutable state? When time is important?
Substitution model:
programs can be evaluated by rewriting (function applications).
All rewritings that terminate lead to the same result (cf. Church-Rosser theorem of lambda-calculus).
Stateful Objects:
Changes over time => state
An object has state if its behavior is influenced by its history.
Ex : a bank transaction depends on the state of bank accounts.
State implementation:
Via variables and assignments
class BankAccount {
 
 private var balance = 0
 
 def deposit(amount: Int): Unit =
  if (amount > 0) balance = balance + amount
  
 def withdraw(amount: Int): Int =
   if (0 < amount && amount <= balance) {
    balance = balance - amount
    balance
   } else throw new Error("insufficient funds")
  
  val account = new BankAccount
  account deposit 50
  account withdraw 20 # OK
  account deposit 40 # Error, different result

lecture "Identity and change"

When are objects the same?
On values, yes (cf. referential transparency:
 val a = E
 val b = E

But with variables and mutable state, no:
 val account1 = new BankAccount
 val account2 = new BankAccount

Being the same = operational equivalence.
i.e. no possible (black box) test can distinguish between them.
test(account1, account2)

The substitution model cannot be used with assignments (or it becomes very complicated).
lecture "loops"

Loops: main feature in imperative programming.
In FP:

while loops are modeled with recursive functions. (tail recursive)
classical for loops cannot be modeled via higher-order function (because of nested variable)
Scala has for-expressions like for (i <- 1 until 3) ... (cf. Collections#foreach)

lecture "Extended Example: Discrete Event Simulation"

Use mutable variables to simulate changing quantities in real world.
Also structure a system with layers, in particular with a Domain Specific Language.
Example: digital circuit simulator
Use wires to combine base components that a have a reaction time (delay):

inverter
AND gate
OR gate

half-adder (HA)

 // components with side effects
 def inverter(input: Wire, output: Wire): Unit
 def andGate(a1: Wire, a2: Wire, output: Wire): Unit
 def orGate(a1: Wire, a2: Wire, output: Wire): Unit


def halfAdder(a: Wire, b: Wire, s: Wire, c: Wire): Unit = {
 val d, e = new Wire // internal wires
 orGate(a, b, d)
 andGate(a, b, c)
 inverter(c, e)
 andGate(d, e, s)
}

def fullAdder(a: Wire, b: Wire, cin: Wire, sum: Wire):, cout: Wire): Unit = {
 val s, c1, c2 = new Wire // internal wires
 halfAdder(b, cin, s, c1)
 halfAdder(a, s, sum, c2)
 orGate(c1, c2, cout)
}

lecture "Discrete Event Simulation: API and Usage"

Implementation of class Wire and its functions.
A discrete event simulator performs actions at a given moment.
An action is a function:
 type Action = () => Unit

Time is simulated.
Layers: user -> circuits (higher-level components) -> gates (wires & base components)-> (abstract) simulation
trait Simulation {
 def currentTime: Int = ???
 def afterDelay(delay: Int)(block: => Unit): Unit ???
 def run(): Unit = ???
 
class Wire {

 private var sigVal = false; // current value
 private var actions: List[Action] = List()
 
 def getSignal: Boolean = sigVal
 
 def setSignal(s: Boolean): Unit = 
  if (s != sigVal) {
   sigVal = s
   actions foreach (_())
  }
  
 def addAction(a: Action): Unit = {
  actions = a :: actions
  a()
 }
}

def inverter(input: Wire, output: Wire) : Unit = {
 def invertAction(): Unit = {
  val inputSig = input.getSignal
  afterDelay(InverterDelay) { output setSignal !inputSig }
 }
 input addAction invertAction
}

def andGate(in1: Wire, in2: Wire, output: Wire) : Unit = {
 def andAction(): Unit = {
  val in1Sig = in1.getSignal
  val in2Sig = in2.getSignal
  afterDelay(AndGateDelay) { output setSignal (in1Sig && in2Sig) }
 }
 in1 addAction andAction
 in2 addAction andAction
}

def orGate(in1: Wire, in2: Wire, output: Wire) : Unit = {
 def orAction(): Unit = {
  afterDelay(OrGateDelay) { output setSignal (in1.getSignal | in2.getSignal) }
 }
 in1 addAction orAction
 in2 addAction orAction
}

lecture "Discrete Event Simulation: implement and test"

Simulation trait has an agenda of actions to perform.
trait Simulation {
 type Action = () => Unit
 
 case class Event(time: Int, action: Action) # case class => easy to pattern-match on
 
 private type Agenda = List[Event]
 private var agenda: Agenda = List()
 
 private var curtime = 0
 def currentTime: Int = curtime
 
 def afterDelay(delay: Int)(block => Unit) {
  val item = Event(curentTime + delay, () => block)
  agenda = inster(agenda, item)
 }
}

Summary:

State & assignments => more complicated (we lose referential transparency and substituion model)
but programs are simpler and concise.
=> trade-off