# Systematic Software with Scala

1 Apr 2019

1. Systematic?
2. Demonstration
3. Semantics of Strategies
4. Strategies
5. Summary

# Demonstration

• FRP
• The Red book
• FrTime
• Scala.React
• .Net Rx
• etc.

## A `Stream` is like a `List`

(where data is ordered by time, instead of space)

## A `Stream` is like a `List`

Great artists steal

``````trait Stream[A] {
def map[B](f: A => B): Stream[B] = ???
def zip[B](that: Stream[B]): Stream[(A,B)] = ???
def flatMap[B](f: A => Stream[B]): Stream[B] = ???
def run[B](zero: B)(f: (B, A) => B): B = ???
}

object Stream {
def fromIterator[A](source: Iterator[A]): Stream[A] =
???
}``````

### Many APIs are algebraic.

``````// Introduction forms
def fromIterator: Iterator[A] => Stream[A]

// Combinators
def map: Stream[A] => (A => B) => Stream[B]

// Elimination forms
def run: Stream[A] => (B, (B, A) => B) => B``````

plus laws

## How do we implement the `???`s?

``````trait Stream[A] {
def map[B](f: A => B): Stream[B] = ???
def zip[B](that: Stream[B]): Stream[(A,B)] = ???
def flatMap[B](f: A => Stream[B]): Stream[B] = ???
def run[B](zero: B)(f: (B, A) => B): B = ???
}

object Stream {
def fromIterator[A](source: Iterator[A]): Stream[A] =
???
}``````

Reification

Reification

``````sealed trait Stream[A] {
...
def map[B](f: A => B): Stream[B] = Stream.Map(this, f)
...
}

object Stream {
...
final case class Map[A,B](source: Stream[A], f: A => B) extends Stream[B]
...
}``````

Reification

``````sealed trait Stream[A] {
import Stream._

def map[B](f: A => B): Stream[B] = Map(this, f)
def zip[B](that: Stream[B]): Stream[(A,B)] = Zip(this, that)
def flatMap[B](f: A => Stream[B]): Stream[B] = FlatMap(this, f)
def run[B](zero: B)(f: (B, A) => B): B = ???
}

object Stream {
final case class Map[A,B](source: Stream[A], f: A => B) extends Stream[B]
final case class Zip[A,B](left: Stream[A], right: Stream[B]) extends Stream[(A,B)]
final case class FlatMap[A,B](source: Stream[A], f: A => Stream[B]) extends Stream[B]
final case class FromIterator[A](source: Iterator[A]) extends Stream[A]

def fromIterator[A](source: Iterator[A]): Stream[A] =
FromIterator(source)
}``````

Reification

how do we run it?

``def run[B](zero: B)(f: (B, A) => B): B = ???``

Interpreter

Structural Recursion

Interpreter

Structural Recursion

``````def run[B](zero: B)(f: (B, A) => B): B = {
def loop[C](stream: Stream[C])(zero: B)(f: (B, C) => B): B =
stream match {
case Map(s, f2) => ???
case Zip(l, r) => ???
case FlatMap(s, f2) => ???
case FromIterator(s) => ???
}

loop(this)(zero)(f)
}``````

Structural Recursion

how do we implement the `???`s?

``````def run[B](zero: B)(f: (B, A) => B): B = {
def loop[C](stream: Stream[C])(zero: B)(f: (B, C) => B): B =
stream match {
case Map(s, f2) => ???
case Zip(l, r) => ???
case FlatMap(s, f2) => ???
case FromIterator(s) => ???
}

loop(this)(zero)(f)
}``````

Structural Recursion

``````def run[B](zero: B)(f: (B, A) => B): B = {
def loop[C](stream: Stream[C])(zero: B)(f: (B, C) => B): B =
stream match {
case Map(s, f2) => loop(s)(zero)((b, d) => f(b, f2(d)))
case Zip(l, r) => ???
case FlatMap(s, f2) => ???
case FromIterator(s) => ???
}

loop(this)(zero)(f)
}``````

``````def run[B](zero: B)(f: (B, A) => B): B = {
def loop[C](stream: Stream[C])(zero: B)(f: (B, C) => B): B =
stream match {
case Map(s, f2) => loop(s)(zero)((b, d) => f(b, f2(d)))
case Zip(l, r) => loop(l)(zero)((b, d) =>
loop(r)(zero)((b, e) => f(b, (d, e)))
)
case FlatMap(s, f2) => loop(s)(zero)((b, d) => loop(f2(d))(zero)(f))
case FromIterator(s) => s.foldLeft(zero)(f)
}

loop(this)(zero)(f)
}``````
``````val s1 = Stream.fromIterator(Iterator(1, 2, 3))
val s2 = Stream.fromIterator(Iterator(4, 5, 6))``````
``````s1.map(_ + 1).run(List.empty[Int])(_ :+ _)
// res4: List[Int] = List(2, 3, 4)``````

operational

vs.

denotational

# Strategies

Read the Literature: great artists steal

Follow the Types: types before impl

``````sealed trait Stream[A] {
def map[B](f: A => B): Stream[B] = ???
}``````

Algebraic Data Types: ANDs and ORs

``````sealed trait Shape

case class Circle(radius: Double) extends Shape
case class Rect(height: Double, width: Double) extends Shape``````

``````sealed trait Shape {
def draw(): Unit =>
this match {
case Circle(r) => ???
case Rect(h, w) => ???
}
}``````

Sequencing: what must happen after something else, and what things can happen at the same time.

`Applicative` & `Monad`

Interpreters: separate what from how

Reification: functions as data

Church-Encoding: data as functions

# Summary

## Thank you!

Adam Rosien `@arosien`

Inner Product LLC inner-product.com

Hire us to teach your team! ☝︎

Special thanks to Noel Welsh for his hard work in codifying these strategies.