How To Write A Perfect Program

Kris Nuttycombe – @nuttycom

April 19, 2014

“Let me take you on an adventure which will give you superpowers.” –@bitemyapp

https://github.com/nuttycom/lambdaconf-2014-workshop

Start Very Simple


True

This program doesn’t have any bugs.

Learn To Count


data Bool = True | False

bool :: Bool
-- "::" is pronounced, "has type"

1 + 1 = 2

applause


i :: Int32

This one is just awful…


s :: String

Learn to Add


data Maybe a = Just a | Nothing

inhabitants (Maybe a) = inhabitants a + 1


data Either a b = Left a | Right b

inhabitants (Either a b) = inhabitants a + inhabitants b

Bool, Maybe and Either are called sum types for the obvious reason.


tuple :: (Bool, Int32)

2³² inhabitants if the value on the left is True
2³² inhabitants if it’s False
2³² + 2³² = 2 * 2^32 = 2³³

Learn to Multiply


-- if haskell had unsafe type-level pattern matching... 
inhabitants :: Type -> Nat

inhabitants Bool = 2
inhabitants Int32 = 2^32

inhabitants (a, b) = inhabitants a * inhabitants b
inhabitants (Int32, Int32) = 2^32 * 2^32 = 2^64

inhabitants (a, b, c) = inhabitants a * inhabitants b * inhabitants c
inhabitants (Bool, Bool, Int32) = 2 * 2 * 2^32 = 2^34

With tuples, we always multiply.

We call these “product” types.

2 + 2³² = 2 * 2^32 = 2³³


either :: Either Int32 Int32
-- 2^33 inhabitants

tuple :: (Bool, Int32)
-- 2^33 inhabitants

These types are isomorphic.

Choose whichever one is most convenient.

Add if you can, multiply if you must


inhabitants (Maybe Int32) = 2^32 + 1

Most languages emphasize products.

Bad ones don’t let you define a type
with 2³² + 1 inhabitants easily.

interface EitherVisitor<A, B, C> {
  public C visitLeft(Left<A, B> left);
  public C visitRight(Right<A, B> right);
}

interface Either<A, B> {
  public <C> C accept(EitherVisitor<A, B, C> visitor);
}

public final class Left<A, B> implements Either<A, B> {
  public final A value;
  public Left(A value) {
    this.value = value;
  }

  public <C> C accept(EitherVisitor<A, B, C> visitor) {
    return visitor.visitLeft(this);
  }
}

public final class Right<A, B> implements Either<A, B> {
  public final B value;
  public Right(B value) {
    this.value = value;
  }

  public <C> C accept(EitherVisitor<A, B, C> visitor) {
    return visitor.visitRight(this);
  }
}

The Vampire Policy

“Bug fixing strategy: forbid yourself to fix the bug. Instead, render the bug impossible by construction.” –Paul Phillips

Strings (Ugh.)

The type String should only ever appear in your program when a value is being shown to a human being.

Two common offenders

Strings as dictionary keys
Strings as serialized form

Garlic

Use newtypes liberally.


newtype Name = Name { strValue :: String }
-- don't export strValue unless you really, really need it


case class Name(strValue: String) extends AnyVal

Never, ever pass bare String values
unless it’s to putStrLn or equivalent.

Never, ever return bare String values
except from readLn or equivalent

Holy Water

Hide your newtype constructor behind validation.


case class IPAddr private (addr: String) extends AnyVal

object IPAddr {
  val pattern = """(\d{1,3})\.(\d{1,3})\.(\d{1,3})\.(\d{1,3})""".r

  def parse(s: String): Option[IPAddr] = for {
    xs <- pattern.unapplySeq(s) if xs.forall(_.toInt <= 255)
  } yield IPAddr(s)
}

We’ve shrunk down an infinite number of states to (256⁴ + 1). Given the inputs, that’s the best we can do.

Stake

import scalaz._

Three very useful types:

A \/ B
Validation[A, B]
EitherT[M[_], A, B]

MyError \/ B

\/ (Disjunction) has a Monad biased to the right
We can sequentially compose operations that might fail
for comprehension syntax is useful for this


import scalaz.std.syntax.option._

def parseJson(s: String): ParseError \/ JValue = ???
def ipField(jv: JValue): ParseError \/ String = ???

def parseIP(addrStr: String): ParseError \/ IPAddr = 
  IPAddr.parse(addrStr) toRightDisjunction {
    ParseError(s"$addrStr is not a valid IP address")
  }

val ipV: ParseError \/ IPAddr = for {
  jv <- parseJson("""{"hostname": "nuttyland", "ipAddr": "127.0.0.1"}""")
  addrStr <- ipField(jv)
  ipAddr <- parseIP(addrStr)
} yield ipAddr

Validation[NonEmptyList[MyError], B]

Validation does not have a Monad instance.
Composition uses Applicative: conceptually parallel!
if you need sequencing, .disjunction


type VPE[B] = Validation[NonEmptyList[ParseError], B]

def hostname(jv: JValue): VPE[String] = ???

def ipField(jv: JValue): ParseError \/ String = ???
def parseIP(addrStr: String): ParseError \/ IPAddr = ???

def host(jv: JValue) = ^[VPE, String, IPAddr, Host](
  hostname(jv), 
  (ipField(jv) >>= parseIP).validation.leftMap(nels(_)) 
) { Host.apply _ }

EitherT[M[_], MyErrorType, B]

EitherT layers together two effects:
- The “outer” monadic effect of the type constructor M[_]
- The disjunctive effect of \/


// EitherT[M, A, _] <~> M[A \/ _]

def findDocument(key: DocKey): EitherT[IO, DBErr, Document] = ???
def storeWordCount(key: DocKey, wordCount: Long): EitherT[IO, DBErr, Unit] = ???

val program: EitherT[IO, DBErr, Unit] = for {
  doc <- findDocument(myDocKey)
  words = wordCount(doc)
  _ <- storeWordCount(myDocKey, words)
} yield ()

Side Effects

in other words, what was that IO thingy?

Managing Effects


// def findDocument(key: DocKey): EitherT[IO, DBErr, Document] = ???
// def storeWordCount(key: DocKey, wordCount: Long): EitherT[IO, DBErr, Unit] = ???

sealed trait DocAction
case class FindDocument(key: DocKey) extends DocAction
case class StoreWordCount(key: DocKey, wordCount: Long) extends DocAction

How can we build a program out of these actions?

This?

object DocAction {
  type Program = List[DocAction]

  def runProgram(actions: Program): IO[Unit] = ???
}

Obviously, this doesn’t work.
- can’t interleave pure computations
- no way to represent return values
- can’t produce a new DocAction from a Program
- can’t make later action a function of an earlier one
But, it is conceptually related to what we want.
- a data structure an ordered sequence of actions
- an interpreter that evaluates this data structure

Sequencing

Let’s, see, what is good for sequencing effects?


trait Monad[M[_]] {
  def pure[A](a: => A): M[A]
  def bind[A, B](ma: M[A])(f: A => M[B]): M[B]
}

State threads state through a computation…
Reader gives the same inputs to all…
Writer keeps a log…
Not going to be Option, List, …

Requirements

restrict the client to only permit actions in our sum
produce later actions as a function of earlier ones
interleave pure computations with effectful

Free


sealed trait Free[F[_], A]
case class Pure[F[_], A](a: A) extends Free[F, A]
case class Bind[F[_], A, B](s: Free[F, A], f: A => Free[F, B]) extends Free[F, A]
case class Suspend[F[_], A](s: F[Free[F, A]]) extends Free[F, A]

for a complete derivation of this type, see Functional Programming In Scala

Exercise 1: Write the Monad instance for Free.

Solution


object Free {
  def monad[F[_]] = new Monad[({ type λ[α] = Free[F, α] })#λ] {
    def pure[A](a: => A): Free[F, A] = Pure(a)

    // def bind[A, B](ma: Free[F, A])(f: A => Free[F, B]): Free[F, B] = Bind(ma, f)

    def bind[A, B](ma: Free[F, A])(f: A => Free[F, B]): Free[F, B] = ma match {
      case Bind(ma0, f0) => bind(ma0) { a => Bind(f0(a), f) }
      case other => Bind(other, f)
    }
  }
}

Capture The Rest of the Program

Here’s a little trick: store the rest of the program in each action.


// sealed trait DocAction
// case class FindDocument(key: DocKey) extends DocAction
// case class StoreWordCount(key: DocKey, wordCount: Long) extends DocAction
  
sealed trait DocAction[A]
case class FindDocument(key: DocKey, cont: Option[Document] => A) extends DocAction[A]
case class StoreWordCount(key: DocKey, wordCount: Long, cont: () => A) extends DocAction[A]

Write a Little Language


sealed trait DocAction[A]

object DocAction {
  case class FindDocument[A] private[DocAction] (
    key: DocKey, 
    cont: Option[Document] => A
    ) extends DocAction[A]

  case class StoreWordCount[A] private[DocAction] (
    key: DocKey, wordCount: Long, 
    cont: () => A
    ) extends DocAction[A]

  type Program[A] = Free[DocAction, A]

  def findDocument(key: DocKey): Program[Option[Document]] = 
    Suspend(FindDocument(key, Pure(_)))

  def storeWordCount(key: DocKey, wordCount: Long): Program[Unit] = 
    Suspend(StoreWordCount(key, wordCount, () => Pure(())))
}

Write a Perfect Program!


import DocAction._

val program: Program[Unit] = for {
  document <- findDocument(docKey)
  _ <- document match {
    case Some(d) => storeWordCount(docKey, countWords(d)) 
    case None => Free.monad[DocAction].pure(())
  }
} yield ()

A Pure Interpreter


type Memory = Map[DocKey, (Document, Option[Long])]

@tailrec def run[A](program: Program[A], memory: Memory): A = {
  program match {
    case Pure(a) => a

    case Suspend(FindDocument(key, cont)) => ???

    case Suspend(StoreWordCount(key, n, cont)) => ???

    case Bind(s, f) => ???
  }
}

A Pure Interpreter #2


type Memory = Map[DocKey, (Document, Option[Long])]

@tailrec def run[A](program: Program[A], memory: Memory): A = {
  program match {
    case Pure(a) => a

    case Suspend(FindDocument(key, cont)) =>
      run(cont(memory.get(key).map(_._1)), memory)

    case Suspend(StoreWordCount(key, n, cont)) => ???

    case Bind(s, f) => ???
  }
}

A Pure Interpreter #3


type Memory = Map[DocKey, (Document, Option[Long])]

@tailrec def run[A](program: Program[A], memory: Memory): A = {
  program match {
    case Pure(a) => a

    case Suspend(FindDocument(key, cont)) =>
      run(cont(memory.get(key).map(_._1)), memory)

    case Suspend(StoreWordCount(key, n, cont)) => ???
      val newValue = memory.get(key).map(_.copy(_2 = Some(n)))
      val newMemory = memory ++ newValue.map(key -> _)
      run(cont(), newMemory)

    case Bind(s, f) => ???
  }
}

A Pure Interpreter #4


type Memory = Map[DocKey, (Document, Option[Long])]

@tailrec def run[A](program: Program[A], memory: Memory): A = {
  program match {
    case Pure(a) => a
    case Suspend(FindDocument(key, cont)) => // implemented 
    case Suspend(StoreWordCount(key, n, cont)) => //implemented

    case Bind(s, f) => 
      s match {
        case Pure(a) => run(f(a), memory)

        case Suspend(FindDocument(key, cont)) =>
          run(Bind(cont(memory.get(key).map(_._1)), f), memory)

        case Suspend(StoreWordCount(key, n, cont)) =>
          val newValue = memory.get(key).map(_.copy(_2 = Some(n)))
          val newMemory = memory ++ newValue.map(key -> _)
          run(Bind(cont(), f), newMemory)

        case Bind(s0, f0) =>
          run(Bind(s0, (a: Any) => Bind(f0(a), f)), memory)
      }
  }
}

Exercise 2: Implement a pure interpreter for ASDF

Stretch Goals

Exercise 3: Refactor the tests to allow reuse against other interpreters.

Exercise 4: Implement an effectful interpreter for ASDF