How To Write A Perfect Program

Dec 10, 2014

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

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

The First Form

Not on my board / trail of awesome.

Utility of types - we want machines to help us as much as they can.

At the time you write the code, you have a mental model of what operations are legal with a given value. That mental model is a type.

The Simplest Program Possible

This program doesn’t have any bugs:

()

This is a very simple program - a value interpreted by an interpreter.

How the interpreter presents that value to the person running it can vary.

Only has one state.

The empty tuple - does everybody know the difference between a tuple and a list?

kris@floorshow ~ » ghci
GHCi, version 7.8.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> ()
()

Learn To Count

data Bool = True | False

boolProgram :: Bool
boolProgram = --hidden

“::” is pronounced “has type”

How many states can a program of type Bool be inhabited by?

-- let's imagine haskell had type-level functions ... 
inhabitants :: Type -> Nat

inhabitants Bool = inhabitants True + inhabitants False
inhabitants Bool = 1 + 1
inhabitants Bool = 2

Counting Higher

How many states in a program does a value of type Int32 represent?

intProgram :: Int32

inhabitants Int32 = inhabitants -2147438648 
                  + inhabitants -2147439647
                  + ...
                  + inhabitants 2147439647

inhabitants Int32 = 2^32

This one is just awful…

strProgram :: String

inhabitants String = ?????

Learn to Add

data Bool = True | False

inhabitants Bool = 1 + 1

-- 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.

Learn to Multiply

boolAndInt :: (Bool, Int32)

inhabitants (Bool, Int32) = inhabitants Bool ??? inhabitants Int32

                          = inhabitants Int32 -- if _1 == True
                          + inhabitants Int32 -- if _1 == False
  
                          = inhabitants Bool * inhabitants Int32

                          = 2 * 2^32

                          = 2^33

Tuples (and objects) are called “product” types.

Different Shapes, Same Implications

inhabitants (Bool, Int32)      = inhabitants Bool * inhabitants Int32
                               = 2 * 2^32
                               = 2^33 

inhabitants Either Int32 Int32 = inhabitants Int32 + inhabitants Int32
                               = 2^32 + 2^32
                               = 2^33

These types are isomorphic

toEither :: (Bool, a) -> Either a a
toEither (True, a) = Right a
toEither (False, a) = Right a

fromEither :: Either a a -> (Bool, a)
fromEither (Right a) = (True, a)
fromEither (Left a)  = (False, a)

Add if you can, multiply if you must

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

Most languages emphasize products.

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

Sapir-Whorf

Most mainstream languages today make products easy, sums hard.

Too easy to define types with too many inhabitants.

Haskell

Prelude> data Either a b = Left a | Right b

Prelude> let printEither (Left b)  = putStrLn $ "It's a left: "  ++ show (not b)
Prelude|     printEither (Right i) = putStrLn $ "It's a right: " ++ show (i + 1)
Prelude| in  traverse printEither [Left True, Right 1, Left False, Right 2]

It's a left: False
It's a right: 2
It's a left: True
It's a right: 3
[(),(),(),()]

Scala

scala> :paste
// Entering paste mode (ctrl-D to finish)

sealed trait Either[A, B]
case class Left[A, B](a: A) extends Either[A, B]
case class Right[A, B](b: B) extends Either[A, B]

// Exiting paste mode, now interpreting.

scala> val xs : List[Either[Boolean, Int]] =
     |   List(Left(true), Right(1), Left(false), Right(2))

scala> xs foreach {
     |   case Left(b)  => println(s"It's a left: ${!b}")
     |   case Right(i) => println(s"It's a right: ${i + 1}")
     | }
It's a left: false
It's a right: 2
It's a left: true
It's a right: 3

JavaScript

function left(a) {
  return function(ifLeft, ifRight) { return ifLeft(a); };
}

function right(b) {
  return function(ifLeft, ifRight) { return ifRight(b); };
}

var xs = [left(true), right(1), left(false), right(2)];

for (i = 0; i < xs.length; i += 1) {
  var eitherVal = xs[i]
  eitherVal(
    function(b) { console.log("It's a left: " + !b) },
    function(i) { console.log("It's a right: " + (i + 1)) }
  )
}

It's a left: false
It's a right: 2
It's a left: true
It's a right: 3

Java

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);
  }
}

Java

  public static void main(String[] argv) {
    List<Either<Boolean, Integer>> xs = new ArrayList<>();
    xs.add(new Left<Boolean, Integer>(true));
    xs.add(new Right<Boolean, Integer>(1));
    xs.add(new Left<Boolean, Integer>(false));
    xs.add(new Right<Boolean, Integer>(2));

    for (Either<Boolean, Integer> x : xs) {
      x.accept(
        new EitherVisitor<Boolean, Integer, Void>() {
          public Void visitLeft(Left<Boolean, Integer> left) {
            System.out.println("It's a left: " + (!left.value));
            return null;
          }

          public Void visitRight(Right<Boolean, Integer> right) {
            System.out.println("It's a right: " + (right.value + 1));
            return null;
          }
        }
      );
    }
  }

Java

kris@heartland ~/personal/fsb_4-2014/src/main/java » java EitherJava
It's a left: false
It's a right: 2
It's a left: true
It's a right: 3

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

The Vampire Policy

Don’t invite errors into your program.

To do this, we need to minimize the state space of our program.

What types should we not let 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

Strings are worse than any other potentially infinite data structure because they’re convenient.

A very common misfeature is to use strings as a serialization mechanism.

Appealing because human readable.

Introduce bugs so that you can have a debugging tool?

Good for being read by humans. But not for machines. Don’t turn your value into a string until it’s about to be turned into photons headed at eyeballs.

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 valuesunless it’s to putStrLn or equivalent.

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

If a string is serving any purpose other than display in your system, then it has semantic meaning that should be tracked by the type system.

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 (2564 + 1). Given the inputs, that’s the best we can do.

This approach applies to virtually every primitive type.

Stake

**import scalaz._**

Three very useful types:

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

Sum types where the error type conventionally comes on the left.

Going to quickly look at each of them.

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 _ }

There is a functor isomorphism between \/ and validation.

Types have the same information content, but compose differently.

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

“Real world” interaction.

How To Write A Perfect Program

nuttycom

How To Write A Perfect Program

0 0

fsb_4-2014

How To Write A Perfect Program

The Simplest Program Possible

Learn To Count

Counting Higher

Learn to Add

Learn to Multiply

Different Shapes, Same Implications

Add if you can, multiply if you must

Haskell

Scala

JavaScript

Java

Java

Java

The Vampire Policy

Strings (Ugh.)

Garlic

Holy Water

Stake

Questions?

How To Write A Perfect Program

nuttycom

How To Write A Perfect Program

0 0 (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/platform.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();

fsb_4-2014

How To Write A Perfect Program

The Simplest Program Possible

Learn To Count

Counting Higher

Learn to Add

Learn to Multiply

Different Shapes, Same Implications

Add if you can, multiply if you must

Haskell

Scala

JavaScript

Java

Java

Java

The Vampire Policy

Strings (Ugh.)

Garlic

Holy Water

Stake

Questions?

0 0