How To Write A Perfect Program

Kris Nuttycombe – @nuttycom

May 13, 2014

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

https://github.com/nuttycom/startup_week-2014

Start Very Simple

True
  

This program doesn’t have any bugs.

nuttycom@crash: ~ $ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> True
True
  

Learn To Count

data Bool = True | False

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

How many states could boolProgram inhabit?

intProgram :: Int32
  

strProgram :: String
  

Learn to Count

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

inhabitants Bool = 2
inhabitants Int32 = 2^32
  

Learn to Add

-- Maybe there's one of these...
data Maybe a = Just a | Nothing

inhabitants (Maybe a) = inhabitants a + 1

-- Either there's one of these, or one of those...
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.

Learn to Multiply

tuple :: (Bool, Int32)
  

• fst :: (a, b) -> a
  • (fst tuple) has 2 inhabitants
    
    
• snd :: (a, b) -> b
  • 2³² inhabitants if (fst tuple) == True
  • 2³² inhabitants if (fst tuple) == False
    
    
• 2 * 2³² = 2³³

With tuples, we always multiply.

Learn to Multiply

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
  

We call these “product” types.

Isomorphic Types

These types have the same inhabitants.

-- expressed as a product
tuple :: (Bool, Int32) -- 2^33 inhabitants

-- expressed as a sum
either :: Either Int32 Int32 -- 2^33 inhabitants
  

Choose whichever one is most convenient

eitherBoolOrInt :: Either Bool Int32 -- 2 + 2^32 inhabitants
  

Add if you can, multiply if you must

inhabitants (Either Bool Int32) = 2 + 2^32
  

Most languages emphasize products.

Bad ones don’t let you define a type
with 2 + 2³² 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);
  }
}

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

The Vampire Policy

Don’t let him in.

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 ()
  

Questions?