Coding and Reasoning with Purity, Strong Types, and Monads

Doug Beardsley (mightybyte)

January 29, 2012

Programmers will ALWAYS make mistakes

Monad press missing the point

Monads in static and dynamic languages

return :: a   -> m a
(>>=)  :: m a -> (a -> m b) -> m b

Monads in static and dynamic languages

return :: a   -> m a
(>>=)  :: m a -> (a -> m b) -> m b
return :: U   -> U
(>>=)  :: U   -> (U -> U)   -> U

Monads in static and dynamic languages

return :: a   -> m a
(>>=)  :: m a -> (a -> m b) -> m b
return :: U   -> U
(>>=)  :: U   -> (U -> U)   -> U

Case Study 1: Data Fusion

Speculative refactoring to improve performance

synchronized ( entity ) {
  updateEntity(entity, newInput);
}
newEntity = updateEntity(entity, newInput);
entities.insert(newEntity); // uses CAS instruction for non-blocking insert

How it might be done in Java

public class ImmutableEntity {
  public ImmutableEntity(Entity e);
  // only define getter methods
}

How it might be done in Java

public class ImmutableEntity {
  public ImmutableEntity(Entity e);
  // only define getter methods
}
Position p = immutableEntity.getPosition();
p.setX(5); // Wait a minute...

How it might be done in Java

public class ImmutableEntity {
  public ImmutableEntity(Entity e);
  // only define getter methods
}
Position p = immutableEntity.getPosition();
p.setX(5); // Wait a minute...
public class ImmutablePosition {
  public ImmutablePosition(Position e);
  // only define getter methods
}

How it might be done in Java

public class ImmutableEntity {
  public ImmutableEntity(Entity e);
  // only define getter methods
}
Position p = immutableEntity.getPosition();
p.setX(5); // Wait a minute...
public class ImmutablePosition {
  public ImmutablePosition(Position e);
  // only define getter methods
}

Haskell solves this easily

updateEntity :: Entity -> Input -> m ()
updateEntity :: Entity -> Input -> Entity
swapEntity :: Entity -> m ()
return :: a   -> m a
(>>=)  :: m a -> (a -> m b) -> m b

Case Study 2: Heist

data Node = TextNode Text
          | Comment Text
          | Element
            { name     :: Text
            , attrs    :: [(Text, Text)]
            , children :: [Node]
            }

DOM transformations with splices

<h1><user:login/></h1>
<ul>
  <li>Age: <user:age/></li>
</ul>
type Splice m = Node -> m [Node]
type Splice m = HeistT m [Node]

Powerful but slow

Speed up by changing to a compiled language

HeistT m [Node]

...becomes

HeistT n IO (DList (Chunk n))

Chunks compiled into a run time render function

[ Pure "<h1>", Runtime getUserLogin, Pure "</h1><ul><li>Age: "
, Runtime getUserAge, Pure "</li></ul>"]

Implementation

Benefits of doing this in Haskell

How might it look in Java?

How might it look in Java?

How might it look in Java?

A Deeper Dive

newtype HeistT n m a = HeistT {
    runHeistT :: Node
              -> HeistState n
              -> m (a, HeistState n)
}
data HeistState n = HeistState
    { _spliceMap           :: HashMap Text (HeistT n n [Node])
    , _compiledSpliceMap   :: HashMap Text (HeistT n IO (DList (Chunk n)))
    , ...
    }

Types are both stringent and flexible

HeistT n n [Node]             -- Interpreted (run time) splice
HeistT n IO (DList (Chunk n)) -- Compiled (load time) splice
data PersonType = Grunt
                | Manager
                | Executive deriving (Show, Enum, Bounded)
enumSelectSplice :: Show a
                 => Text     -- ^ Name attribute
                 -> [a]
                 -> HeistT n n [Node]
personSelect = enumSelectSplice "person-type" [minBound..maxBound]

Types are both stringent and flexible

HeistT n n [Node]             -- Interpreted (run time) splice
HeistT n IO (DList (Chunk n)) -- Compiled (load time) splice
data PersonType = Grunt
                | Manager
                | Executive deriving (Show, Enum, Bounded)
enumSelectSplice :: Show a
                 => Text     -- ^ Name attribute
                 -> [a]
                 -> HeistT n n [Node]
personSelect = enumSelectSplice "person-type" [minBound..maxBound]
HeistT n m [Node]             -- Generic splice

Restricting Times of Execution

withLocalSplices :: [(Text, Splice n)]
                 -> HeistT n IO a
                 -> HeistT n IO a

A Compiled Splice Example

fooSplice :: MonadIO n => HeistT n IO (DList (Chunk n))
fooSplice = do
    -- :: HeistT n IO
    lift $ putStrLn "This executed at load time"
    C.yieldRuntimeText $ do
        -- :: RuntimeSplice n a
        lift $ putStrLn "This executed at run/render time"
        val <- lift getValueFromDatabase
        return $ pack $ show (val+1)

Parting thoughts

In case you're wondering about performance...

Appendix

Compiled splice formulations with run time data