Saturday, September 20, 2014

Building Gtk2Hs GUIs with queries

Please comment on reddit
In my previous post Haskell::Reddit helped me find out that the continuation monad can be used to make an interesting query like interface. I've been using this interface to refactor my toy editor program and it's been working fairly well. I still haven't fixed the issue that started this tangent (opening a file twice results in two tabs) but that's side project coding for you.


My toy editor is not very complicated but it still took a while to build directly. Gtk2Hs is a great library but not as easy to use as HTML + JS. The web has made some amazing progress in making UIs easier to build and I'm hoping that some of those insights can be transferred to the native GUI world.



When you use the gtk api directly, you tend to build things in a hierarchical way based on how you want things laid out. But a lot of the times you want connections between components (I'm hoping to have components that aren't Gtk widgets eventually) that cross hierarchies:

This isn't too bad but once right click menus are added it could get messy. And even when the connections match the hierarchy, you don't want to tie layout to event handling logic.

Glade is supposed to be a solution to this but for my side project coding I'd rather work with direct code.

In the original version of the editor I had to have a second initialization phase after I did my layout to setup the callbacks correctly.
main :: IO ()
main :: IO ()
main = do
    initGUI
    window <- windowNew
    set window [windowDefaultWidth := 800, windowDefaultHeight := 600]
    
    mainBox <- vBoxNew False 0
    _ <- containerAdd window mainBox

    buttonBar <- hBoxNew False 0
    
    button <- buttonNewWithLabel "Open Project"
    saveButton <- buttonNewWithMnemonic "_Save Files"
    refreshButton <- buttonNewWithMnemonic "S_ynchronize Folders"
    boxPackStart buttonBar button PackNatural 0
    boxPackStart buttonBar saveButton PackNatural 0
    boxPackStart buttonBar refreshButton PackNatural 0
    widgetShowAll buttonBar
    
    boxPackStart mainBox buttonBar PackNatural 0
          
    editor <- makeEditor
    
    
    onClicked button $ newFileChooser $ loadFile editor
    onClicked saveButton $ saveFiles editor
    onClicked refreshButton $ refreshFolders editor
    
    onRowActivated (_fileTreeView editor) $ openFileChooserFile editor
    
    boxPackStart mainBox (mainPane editor) PackGrow 0
             

    onDestroy window mainQuit
    widgetShowAll button    
    widgetShowAll mainBox
    widgetShowAll window
    mainGUI

makeEditor  = do
        {- widget creation setup..etc -}
    let editorWindow =  EditorWindow { mainPane = mainVPane, 
                          _fileTreeView = fileTreeView, 
                          _fileTreeStore = treeStore, 
                          notebook = noteBook, 
                          _rootPath = filePath, 
                          nextGuiId = guiId,
                          sourceBuffers = buffers
                        } 
    consoleBookInitializer editorWindow
    return editorWindow
So these lines came after
editor <- makeEditor
:
    onClicked button $ newFileChooser $ loadFile editor
    onClicked saveButton $ saveFiles editor
    onClicked refreshButton $ refreshFolders editor

Because opening a project and refreshing the folders meant updating the file tree (it should also clear the tabs when opening a project... another bug), the callback needed to get the file tree somehow. But the buttons were created before the file tree since they are on top. Also EditorWindow needs to have the file tree created before it can be created.

I decided to tag components with a String identifier, like HTML ids, then I could query for the component based on the identifier. Like jQuery if the query does not find anything then nothing happens. So then I could setup callbacks without worrying about the order of creating components.

I could store each of the components in a separate container but after trying it out I gave up and went with Data.Dynamic. String identifiers and Data.Dynamic steps aren't the Haskell way but it was the best idea I had at the time. For some extra type-safety I added constants that put the identifiers together with their types.

data Named a = Named { _identifier :: String, _content :: a}
data Widgets = Widgets {  _widgets :: HaskQuery.Relation (Named Dynamic) (OrdIndex.OrdIndex String)}

type WidgetRef a = Named (Proxy a)

widgetReference :: String -> WidgetRef a
widgetReference identifier = Named { _identifier = identifier, _content = Proxy}

HaskQuery (as of this post) is just where I put all my query stuff. HaskQuery.Relation is a wrapper around Data.IntMap that makes the interface more SQL-like.

data Relation a b = Relation { _relation :: Data.IntMap.Lazy.IntMap a , 
    _lastRowId :: Int, _indices :: UpdatableIndex a b} 
    deriving (Show)

selectDynamicWithTypeM :: (Data.Typeable.Typeable a, Monad m) 
=> Data.Proxy.Proxy a 
-> Data.Dynamic.Dynamic 
-> Control.Monad.Trans.Cont.Cont (b->m b) a
selectDynamicWithTypeM proxy value = 
    Control.Monad.Trans.Cont.cont (\continuation -> 
                                        (\seed -> (case Data.Dynamic.fromDynamic value of 
                                                                    Just typed -> continuation typed seed 
                                                                    Nothing -> return seed)))

selectM :: Monad m => Relation a c -> Control.Monad.Trans.Cont.Cont (b -> m b) a
selectM relation = Control.Monad.Trans.Cont.cont (\continuation -> 
    (\seed -> Data.IntMap.Lazy.foldl 
        (\foldSeed value ->  foldSeed >>= continuation value) 
        (return seed) 
        (_relation relation)))

selectWidget :: Typeable a => Widgets -> String -> Proxy a -> (HaskQuery.Cont (b -> IO b) a)
selectWidget widgets identifier typeProxy = do        
        widget <- HaskQuery.selectM $ _widgets widgets
        HaskQuery.filterM $ (_identifier widget) == identifier
        selectedWidget <- HaskQuery.selectDynamicWithTypeM typeProxy (_content widget)
        return selectedWidget

selectWidgetRef :: Typeable a => Widgets -> WidgetRef a -> (HaskQuery.Cont (b -> IO b) a)
selectWidgetRef widgets widgetRef = selectWidget widgets (_identifier widgetRef) (_content widgetRef)

Ok, with that I could now change the direct file tree lookup for refreshing the file list to one that did a lookup for the file tree:

Before

makeEditor  = do
        {- widget creation setup..etc -}
    let editorWindow =  EditorWindow { mainPane = mainVPane, 
                          _fileTreeView = fileTreeView, 
                          _fileTreeStore = treeStore, 
                          notebook = noteBook, 
                          _rootPath = filePath, 
                          nextGuiId = guiId,
                          sourceBuffers = buffers
                        } 
    consoleBookInitializer editorWindow
    return editorWindow

refreshFolders editor = do
  canonicalRootPathMaybe <- atomically $ readTVar (_rootPath editor) 
  case canonicalRootPathMaybe of 
        Just canonicalRootPath -> do
                                    forest <- getDirContentsAsTree canonicalRootPath
                                    let fileTreeStore = _fileTreeStore editor 
                                    treeStoreClear fileTreeStore  
                                    treeStoreInsertForest fileTreeStore [] 0 forest
                                    return ()
        Nothing -> return ()

After

fileTreeStoreRef :: WidgetRef (TreeStore DirectoryEntry)
fileTreeStoreRef = widgetReference "fileTreeStore"

makeEditorWindow ::  IO EditorWindow
makeEditorWindow = do
    filePath <- atomically $ newTVar Nothing
    buffers <- atomically $ newTVar IntMap.empty
    propertyRelation <- atomically $ newTVar HaskQuery.empty
    widgetTVar <- atomically $ newTVar emptyWidgets
   
    guiId <- newIORef 0
    
    let editorWindow =  EditorWindow {   
                          _editorWidgets = widgetTVar,   
                          _rootPath = filePath, 
                          nextGuiId = guiId,
                          sourceBuffers = buffers,
                          _properties = propertyRelation
                        } 
    return editorWindow

refreshFolders :: EditorWindow -> IO ()
refreshFolders editor = do
  canonicalRootPathMaybe <- atomically $ readTVar (_rootPath editor) 
  case canonicalRootPathMaybe of 
        Just canonicalRootPath -> do
            forest <- getDirContentsAsTree canonicalRootPath
            _ <- HaskQuery.runQueryM $ do
                 widgets <- getWidgets (_editorWidgets editor)
                 fileTreeStore <- selectWidgetRef widgets fileTreeStoreRef 
                 HaskQuery.executeM $ do
                     treeStoreClear fileTreeStore  
                     treeStoreInsertForest fileTreeStore [] 0 forest
            return ()
        Nothing -> return ()

The new code is uglier but it's a lot easier to move pieces of code around and separate layout code from event connection code. EditorWindow can now be created without any Gtk widgets which might be useful for writing test code. Another nice thing is that I can now remove the file tree and replace it at run time. This might be useful if I want to rebuild parts of the layout.

I'm still experimenting with the best way to use queries and what the tradeoffs are but it has definitely helped me decouple my GUI code and it's making this project a lot more fun. The code version as of this post is at github/stevechy/HaskellEditor.

Friday, April 18, 2014

Finding an interesting interface for simple io in Haskell

(This is going to be a long post, but there were a lot of wrong turns and bumps that I encountered that might be helpful to others, kind of a postmortem.
Comments on reddit
Turns out I ended up getting the Cont monad, have a lot to learn, thanks reddit user rampion!)

I had an annoying bug in my editor side project (link).  If you opened the same file twice then you would get two tabs with the same file.   The save button also saves all tabs so if I accidentally opened the same file twice, one of them could overwrite the other.

Should be an easy fix, unfortunately my data structure wasn't going to help:

data EditorWindow = EditorWindow { mainPane:: VPaned,
                                   _fileTreeStore :: TreeStore DirectoryEntry,
                                   _fileTreeView:: TreeView,
                                   notebook :: Notebook,
                                   _rootPath :: TVar (Maybe FilePath),                                  
                                   nextGuiId :: IORef (Int),
                                   sourceBuffers :: TVar ( IntMap.IntMap (String, SourceBuffer))
                                   }

I'd have to write something to go over the sourceBuffers and match the strings.  Ugh.  Then I thought that it would be really nice to write queries over the gui state like jQuery.  Would be nice for the file system too.

Seemed like it should be possible, I'd been reading a lot of good things about core.logic, watched Adam Foltzer's Molog presentation, Phil Wadler's LINQ presentation.  Looked at some core.logic presentations, went over the "Essence of LINQ" paper, started looking at pieces of William Byrd's miniKanren dissertation, LogicT paper, and List monad stuff.

After all that I figured that I just needed something that did nested loop type stuff like the List monad or an SQL query.  And it would be really great if I could get it into do notation.  For directory reading I had to get the directory entries then after that figure out if they were files or directories.  It would be nice if it looked like this:


dirContents dirPath = do
    filePath <- selectM (directoryContentsRelation dirPath)
    fileNode <- selectM (directoryType filePath)
    return fileNode



The TLDR is that after much goose chasing the above actually works. Still haven't organized it, it's in here for now RelationalTest.hs

The Goose Chase



Didn't look like I could get it into a monad, but at least this Beyond Monads post showed me that you could chain a custom bind >>>= in a pretty readable way so that wasn't too bad.

Seemed like it would be easier to start with files. So something that "selected" from a file would loop over the lines, then collect the results. Since most of the operations would be appends, I stuck in a DList. So the file would provide a source of data, and it would call a consumer to add results to the DList.

type SeedConsumer b = Data.DList.DList b -> IO (Data.DList.DList b)
type IOAccumulator a b = a -> SeedConsumer b
type IOSource a b = Data.DList.DList b -> IOAccumulator a b-> IO (Data.DList.DList b)

readFileRelation :: IOSource String b
readFileRelation seed consumer = withFile "LICENSE" ReadMode (readFileStep seed consumer)

readFileStep :: Data.DList.DList b -> IOAccumulator String b -> Handle -> IO ( Data.DList.DList b )
readFileStep seed consumer handle = do
   isEof <- hIsEOF handle
   if isEof 
       then return $ seed
       else do 
                 line <- hGetLine handle
                 result <- consumer line seed
                 readFileStep result consumer handle

This looked pretty good, it could do query like things like filter out lines:


sat :: Data.DList.DList a -> Bool -> a -> Data.DList.DList a
sat seed True elem = Data.DList.snoc seed elem
sat seed False elem = seed

tests :: Test
tests = TestList [
        TestLabel "Should Query File" $ TestCase $ do
            fileRelations <- readFileRelation emptySeed (\ line seed  -> return (Data.DList.snoc seed line) ) 
            putStrLn $ showDlist $ fileRelations
            assertEqual "Queried file"  "a" "a"
        ,TestLabel "Should Query File" $ TestCase $ do
            fileRelations <- readFileRelation emptySeed (\ line seed  -> return $ (sat seed (length line <= 10) line) )  
            putStrLn $ showDlist $ fileRelations
            assertEqual "Queried file" "a" "a"
]


Then I added some convenience functions:

selectPipe :: IOSource a b -> IOAccumulator a b -> SeedConsumer b
selectPipe source accumulator = \seed  -> source seed accumulator

It was kind of annoying to pass through the seed all the time, and I was thinking that most of the time the consumer would not modify the seed, so I added some functions to manage the seed separately. This actually ended up side tracking my thinking a bit but made writing the code a bit easier.

type IOConsumer a b = a -> IO (Data.DList.DList b)

accum ::  IOConsumer a b -> IOAccumulator a b
accum consumer = \ input seed -> do
    result <- consumer input
    return $ Data.DList.append seed result

select :: IOSource a b -> IOConsumer a b -> SeedConsumer b
select source consumer = selectPipe source (accum consumer)


flatDirectoryContents :: DirectoryPath -> IOSource FileNode b
flatDirectoryContents dirPath seed consumer = 
    applySeed seed $ selectPipe (directoryContentsRelation dirPath) $ \ filePath ->
        selectPipe (directoryType filePath) $ consumer

fileTree :: DirectoryPath -> IO( Data.DList.DList FileTree )
fileTree dirPath = 
    applySeed emptySeed $ select (flatDirectoryContents dirPath) $ \fileNode -&gt
        if traversable fileNode
            then do 
                subTrees <- fileTree (fileNodePath fileNode)
                    return $ having True $ (Tree fileNode (Data.DList.toList subTrees)) 
            else return $ having True $ (Leaf fileNode) 



I played around with select and selectPipe a bit more and was starting to think that this was really close to a monad. And I really wanted the nice do syntax. So what were the elements of the monad? It looked like the source was a good thing:

type IOSource a b = Data.DList.DList b -> IOAccumulator a b-> IO (Data.DList.DList b)

But then I didn't know how to write >>=. Maybe I could use free monads. I pulled out operational, added the GADT extension, tried to make IOSource a command of the free monad.

The b parameter ended up being a problem. I tried hiding the b in the GADT but I couldn't get it to typecheck. It ended up with an error where some outside b1 looked like it was exactly b but it wasn't able to match them. I tried tweaking it a bunch more times but it wouldn't work.

Well I'm not the greatest person with types, I've actually taken a category theory course before (not really type systems but kind of similar). I even audited it again to try and get more out of it, but I have no intuition for it and can pretty much only crunch through the definitions manually.

So I went back to square one. I thought it over and over. Then I wondered why I was doing this on a Sunday. Then I wondered why I was spending all this brain time on a side project. Then I went for a walk to the store. Then an idea popped up.

The b type parameter never changed through all of the bind applications. Actually all the types with b never changed. So Data.DList.DList b and IO (Data.DList.DList b) were kind of constants when binding. So I really wanted IOSource to look more like:

type IOSource a b =  IOAccumulator a b-> Data.DList.DList b -> IO (Data.DList.DList b)

Which was actually:

type IOSource a b =  (a -> Data.DList.DList b -> IO (Data.DList.DList b)) -> Data.DList.DList b -> IO (Data.DList.DList b)

And then I really wanted the b to be applied first:

type IOSource b a =  (a -> Data.DList.DList b -> IO (Data.DList.DList b)) -> Data.DList.DList b -> IO (Data.DList.DList b)

Now, (IOSource b) looked like a monad, the b parameters didn't matter since they would be fixed from the monad point of view. Maybe I could write >>= now. I didn't really want to rewrite my IOSource code yet though, so since they were just synonyms I tried to make a type for this new thing that might be a monad.

data RelationMonad b a = RelationMonad { source ::  (a -> Data.DList.DList b -> IO (Data.DList.DList b)) -> Data.DList.DList b -> IO (Data.DList.DList b)  }

Now I had to fill in the instance functions:

instance Monad (RelationMonad b) where
    return x = ?
    relationMonad >>= f = ?

So what was return? Thinking of the file IOSource, return x would be kind of like a one line file. So it would just call the consumer with x.

return x = RelationMonad { source = \ accum -> accum x}

What about >>= ? Well what would f be in this case? It would take in an input from the source then produce another source...

But the >>= would have to produce a new source. It looked like the source was kind of a function with a hole in it, kind of like the "one hole context" idea.

And the hole is an accumulator, something that takes an input and adds it to the seed.

 So >>= would have to take a source1 with a hole, a function from the "output" (lines of the file) of source1 to a source2 then produce a new source3 with a hole with source2's "output" type.

Still pretty fuzzy, what are the types of these things? The b is now fixed so make it z to get it out of the way.

--Not exactly code

relationMonad :: (RelationMonad z) a

f :: a -> (RelationMonad z) b

source3 :: (RelationMonad z) b
source3 = relationMonad >>= f

source3 :: RelationMonad { source ::  (b -> Data.DList.DList z -> IO (Data.DList.DList z)) -> Data.DList.DList z -> IO (Data.DList.DList z)  }


Oh, so now I have to make a new source that takes in a hole thing of type (b -> Data.DList.DList z -> IO (Data.DList.DList z)) using relationMonad and f.

Well if I apply f to the output of relationMonad then I get a source like that, but I still have to run relationMonad.

I guess I have to make a new accumulator of type (a -> Data.DList.DList z -> IO (Data.DList.DList z)) then pass that to relationMonad.

But to make an accumulator from a source I have to fill the hole with another accumulator.

Oh, that's going to be the accumulator that is passed in to the new source3.

--Not exactly code

newSource :: a -> (RelationMonad z) b
newSource = \input -> (source (f input))

newAccumulator :: (a -> Data.DList.DList z -> IO (Data.DList.DList z))
newAccumulator :: (\input -> (source (f input)) accum)

relationMonadWithNewAccumulator ::  Data.DList.DList z -> IO (Data.DList.DList z)
relationMonadWithNewAccumulator = (source relationMonad) (\input -> (source (f input)) accum) 

source3 :: RelationMonad { source ::  \accum -> (source relationMonad) (\input -> (source (f input) accum)   }

Ok, does that work?

instance Monad (RelationMonad b) where
    return x = RelationMonad { source = \ accum -> accum x}
    relationMonad >>= f = RelationMonad { source =  \accum -> (source relationMonad) (\input -> (source (f input)) accum) }

It typechecks and it runs.


runMonad :: RelationMonad (Data.DList.DList b -> IO (Data.DList.DList b)) b -> IO (Data.DList.DList b)
runMonad relationMonad = ((source relationMonad) (\ input seed -> return $ Data.DList.snoc seed input)) Data.DList.empty

selectM :: IOSource a b -> RelationMonad (Data.DList.DList b -> IO (Data.DList.DList b)) a
selectM src = RelationMonad { source = (\accum seed -> src seed accum )}

dirContents dirPath = do
    filePath <- selectM (directoryContentsRelation dirPath)
    fileNode <- selectM (directoryType filePath)
    return fileNode

tests :: Test
tests = TestList [
     TestLabel "Monad"  $ TestCase $ do
            dirRelations <- runMonad $ dirContents (DirectoryPath "." "sandbox")
            putStrLn $ ""
            putStrLn $ showDlist $ dirRelations
            assertEqual "Queried DirMonad" "a" "a"
    ]


So this is pretty neat interface for reading files and looping over things. Any function that fits the signature will work, so it could loop over filenames then use those filenames to loop over GUI elements. Also can loop over file names, read the files, then collect the results in a list. Cool, wow almost didn't think it was going to work.

But there's still something kind of weird, we didn't really touch the (Data.DList.DList b -> IO (Data.DList.DList b)) part:

data RelationMonad b a = RelationMonad { source ::  (a -> Data.DList.DList b -> IO (Data.DList.DList b)) -> Data.DList.DList b -> IO (Data.DList.DList b)  }

does this work?

data RelationMonad b a = RelationMonad { source ::  (a -> b) -> b  }

Strangely it does. I don't know what this thing is now. Maybe Binder? It kind of does part of what >>= does in other monads.

EDIT: Turns out this is the Cont monad, guess I need to study more :)

Is it actually a monad? Well I always thought Gabriel Gonzalez's equational reasoning tutorial was pretty neat, so might as well try it out:


data Binder b a = Binder { source ::  (a -> b) -> b  }
 instance Monad (Binder b) where
    return x = Binder { source = \ accum -> accum x}
     relationMonad >>= f = Binder { source =  \accum -> (source relationMonad) (\input -> (source (f input)) accum) }


Monad laws
 Left identity:
 return a >>= f
 ≡
 f a

 Proof:
 return a >>= f
 ≡ (apply definition of return)
 Binder { source = \ accum -> accum a} >>= f
 ≡ (apply definition of >>=)
 Binder { source =  \accum -> (source Binder { source = \ accum1 -> accum1 a}) (\input -> (source (f input)) accum) }
 ≡ (cancel source)
 Binder { source =  \accum -> ( \ accum1 -> accum1 a) (\input -> (source (f input)) accum) }
 ≡ (apply (\input -> (source (f input)) to \accum1... )
 Binder { source =  \accum -> ((\input -> (source (f input)) a)  accum) }
 ≡ (apply a to \input ...)
 Binder { source =  \accum -> (source (f a)) )  accum) }
 ≡
 Binder { source =  source (f a) }
 ≡
 f a


 Right identity:
 m >>= return
 ≡
 m

 Proof:

 m >>= return
 ≡ (apply definition of >>=)
 Binder { source =  \accum -> (source m) (\input -> (source (return input)) accum) }
 ≡ (apply definition of return)
 Binder { source =  \accum -> (source m) (\input -> (source (Binder { source = \ accum1 -> accum1 input})) accum) }
 ≡ (cancel source)
 Binder { source =  \accum -> (source m) (\input -> (\ accum1 -> accum1 input) accum) }
 ≡ (apply accum to \accum...)
 Binder { source =  \accum -> (source m) (\input ->  accum input ) }
 ≡
 Binder { source =  \accum -> (source m) accum }
 ≡
 Binder { source = source m } ≡ m


 Associativity:
 (m >>= f) >>= g
 ≡
 m >>= (\x -> f x >>= g)

 Proof:

 (m >>= f) >>= g
 ≡ (apply definition of >>=)
 Binder { source =  \accum -> (source m) (\input -> (source (f input)) accum) } >>= g
 ≡ (rename) 
Binder { source =  \accum1 -> (source m) (\input1 -> (source (f input1)) accum1) } >>= g
 ≡ (apply definition of >>=)
 Binder { source =  \accum -> (source RelationMonad { source =  \accum1 -> (source m) (\input1 -> (source (f input1)) accum1) }) (\input -> (source (g input)) accum) }
 ≡ (cancel source)
 Binder { source =  \accum -> (\accum1 -> (source m) (\input1 -> (source (f input1)) accum1)) (\input -> (source (g input)) accum) }
 ≡ (apply (\input -> (source (g input)) accum) to \accum1 ...)
 Binder { source =  \accum -> (source m) (\input1 -> (source (f input1)) (\input -> (source (g input)) accum))  }
 ≡ (rename)
 Binder { source =  \accum -> (source m) (\input ->   (source (f input)) (\input1 -> (source (g input1)) accum))  }



 Other side:
 m >>= (\x -> f x >>= g)
 ≡ (apply definition of >>=)
 m >>= ( \x ->  Binder { source =  \accum -> (source (f x)) (\input -> (source (g input)) accum) })
 ≡ (rename)
 m >>= ( \x ->  Binder { source =  \accum1 -> (source (f x)) (\input1 -> (source (g input1)) accum1) }) 
≡ (apply definition of >>=)
 Binder { source =  \accum -> (source m) (\input -> (source (( \x ->  Binder { source =  \accum1 -> (source (f x)) (\input1 -> (source (g input1)) accum1) }) input)) accum) }
 ≡ (apply input to \x ...)
 Binder { source =  \accum -> (source m) (\input -> (source ( Binder { source =  \accum1 -> (source (f input)) (\input1 -> (source (g input1)) accum1) } )) accum) }
 ≡ (cancel source)
 Binder { source =  \accum -> (source m) (\input ->  (\accum1 -> (source (f input)) (\input1 -> (source (g input1)) accum1)) accum) }
 ≡ (apply accum to \accum1)
 Binder { source =  \accum -> (source m) (\input ->   (source (f input)) (\input1 -> (source (g input1)) accum))  }

 (m >>= f) >>= g



Ok, so it's quite possible I made a mistake but it looks like it is a monad. I don't know what this monad really is though since I'm still just thinking of it in terms of sources and accumulators. Anyone have an idea?

Thursday, March 6, 2014

Experimenting with game engine concepts in Haskell

I've had Jason Gregory's excellent Game Engine Architecture (GEA) on my bookshelf for a while and every time I skim through I want to try out the ideas in it. Watching John Carmack talk about Haskell at QuakeCon got me thinking about trying them out in Haskell.

Armed with some notion that this was a good idea and some idea of how real games are set up I worked out a few details in haskellGame.  It's not even a demo at this point, but so far I've learned some things that I'd like to share.


(Thanks to Kenny.nl for awesome free game graphics!)

Game Loop

Most games are driven by a game loop.  The loop grabs events, applies them to the game state then renders it.  In an imperative language, this might look like:


 

while(!gameEngine.done()) {
    currentTicks = getTicks();
    frameDelay = currentTicks - lastTicks;
    gameEngine.updateGameObjects();
    gameEngine.applyPhysics(frameDelay);
    gameEngine.detectAndResolveCollisions();
    gameEngine.render();
    lastTicks = currentTicks;
}


GEA describes reasons why most engines update objects in batched phases.  This works out nicely in Haskell as it naturally operates on batches of objects of the same type.

In Haskell, each of these phases can be implemented as a function from GameState -> GameState. Then the loop just needs to apply all the phases to the game state on every run through. I later had to add some communication between the phases, which I represented as GameEventQueues. So a game phase is now (GameState, GameEventQueues) -> (GameState, GameEventQueues).

Could the GameState contain the event queues?  Maybe, I don't have a good idea of which is better at this point.

 

gameLoop :: (GameState -> IO t) -> IO Event -> GameState -> GHC.Word.Word32 -> IO ()
gameLoop drawAction eventAction gameState lastFrameTicks = do
 
  events <- HaskellGame.HumanInterface.Manager.pollEvents eventAction []
  let gameEvents = GameEventQueues { gameActions = concat $ Data.List.map (HaskellGame.HumanInterface.Manager.playerGameAction playerId) events,
                                  physicsActions = [] }
  
  let state = Data.Maybe.isNothing $ find (\x -> x == Graphics.UI.SDL.Events.Quit) events 
  
  currentTicks <- Graphics.UI.SDL.Time.getTicks
  
  let frameDelay = fromIntegral $ currentTicks - lastFrameTicks
   
  let (finalState, finalQueues) = 
        Data.List.foldl' ( \ currentGameState gameStep -> gameStep currentGameState) (gameState, gameEvents) 
                   [ HaskellGame.Gameplay.Simulator.processGameStateOutputEvents, 
                     HaskellGame.Physics.Simulator.applyPhysicsChanges, 
                     HaskellGame.Physics.Simulator.applyPhysics frameDelay, 
                     HaskellGame.Physics.CollisionDetector.detectAndResolveCollisions frameDelay
                   ]        
  
  
  _ <- drawAction finalState

  case state of
    True -> do 
      Graphics.UI.SDL.Time.delay 30
      gameLoop drawAction eventAction finalState currentTicks
    False -> return ()




Game State

The game loop applies phases that operate on different slices of data.  Well that was the theory at least, most of these update position information.  The original theory seemed to work well with what GEA calls a "pure component model" for game objects.  Entities in the game are just distinct components that are bound together by a unique identifier.

With that in mind, the GameState became mostly a collection of IntMaps from identifiers to game components:

type BoundingBoxState = Data.IntMap.Lazy.IntMap BoundingBox

type PhysicsState = Data.IntMap.Lazy.IntMap VelocityAcceleration

type WorldState = Data.IntMap.Lazy.IntMap Position

type AnimationStates = Data.IntMap.Lazy.IntMap AnimationClip

type RenderingHandlers = Data.IntMap.Lazy.IntMap RenderingHandler

type ActorStates = Data.IntMap.Lazy.IntMap ActorState

data GameState = GameState { worldState :: WorldState, 
                             _resources :: GraphicResources, 
                             actorStates :: ActorStates, 
                             physicsState::PhysicsState, 
                             boundingBoxState :: BoundingBoxState,
                             _animationStates :: AnimationStates,
                             renderingHandlers :: RenderingHandlers, 
                             _font :: Font }


I was trying to push the design a bit to see where it breaks by separating Position and VelocityAcceleration.  A funny thing came out of it, I can omit the VelocityAcceleration component of platforms and the physics phase won't be able to move them.

Originally I initialized each of the maps separately, but calling code that adds entities will usually want to define all of the components together.  First I added a union type to work with the cases, but later, I added a convenience typeclass.  I've been trying to avoid using a lot of typeclasses but this one seemed to work out well.

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-}
module HaskellGame.Game where

-- .... snipped code

data GameComponent = PositionComponent Position 
                       | CollisionComponent BoundingBox 
                       | PhysicsComponent VelocityAcceleration 
                       | RenderingComponent RenderingHandler 
                       | ActorComponent ActorState
                       | AnimationComponent AnimationClip

class GameComponentStore a where
    toComponent :: a -> GameComponent

instance GameComponentStore Position where
    toComponent = PositionComponent 

instance GameComponentStore BoundingBox where
    toComponent = CollisionComponent 

instance GameComponentStore VelocityAcceleration where
    toComponent = PhysicsComponent 

instance GameComponentStore RenderingHandler where
    toComponent = RenderingComponent 

instance GameComponentStore ActorState where
    toComponent = ActorComponent 

instance GameComponentStore AnimationClip where
    toComponent = AnimationComponent 




This makes entity definition a lot easier since the caller does not need to know the union constructor names.


initializeGameState :: GameState -> GameState
initializeGameState gameState = 
    insertEntities gameState [GameEntity randomSquareId [toComponent (BoundingBox 0 0 10 10), 
                                              toComponent (Position 300 5),
                                              toComponent HaskellGame.Rendering.Renderer.rectRenderer ],
                              GameEntity playerId [toComponent $ Position 5 5,
                                                    toComponent $ VelocityAcceleration {vx = 0, vy = 0.00, ax = 0, ay = 0.0002},
                                                    toComponent $ BoundingBox 0 0 66 92,
                                                    toComponent $ Idle,
                                                    toComponent $ HaskellGame.Rendering.Renderer.animatedRender,
                                                    toComponent $ AnimationClip {_resourceId = playerId, _startTime = 0, _rate = 125}
                                                    ],
                              GameEntity floorId  [toComponent $ Position 0 400,
                                                     toComponent $ HaskellGame.Rendering.Renderer.rectRenderer,
                                                     toComponent $ BoundingBox 0 0 640 10
                                                    ],
                              GameEntity platformId  [toComponent $ Position 500 300,
                                                     toComponent $ HaskellGame.Rendering.Renderer.rectRenderer,
                                                     toComponent $ BoundingBox (-25) (-25) 50 50
                                                    ]
                             ] 

Testing

This structure should lead to easier tests, one nice thing is that only the components that are being tested need to be added to the test case.

I've only made two HUnit tests so far, specifically for this blog post, but I hope to add more as it goes:

 
ts :: Test
tests = TestList [   
    TestLabel "AccelTest"
        (TestCase 
            (do  let intialGameState = HaskellGame.Types.emptyGameState
                 let playerEntityId = 201404
                 let playerEntity = GameEntity playerEntityId [toComponent $ Position 5 5,
                                                         toComponent $ VelocityAcceleration {vx = 0, vy = 0.00, ax = 0, ay = 0.0002},
                                                         toComponent $ BoundingBox 0 0 66 92]
                 let gameState = insertEntity intialGameState playerEntity
                 let physicsTimeInterval = 1000
                 let (gameStateAfterPhysics, _) = HaskellGame.Physics.Simulator.applyPhysics physicsTimeInterval (gameState, HaskellGame.Types.emptyGameEventQueues)
                 let positionAfterPhysics = Data.IntMap.Lazy.lookup playerEntityId $ worldState gameStateAfterPhysics
                 assertEqual "Force was applied" (Just $ Position 5 205) positionAfterPhysics)
        ),
    TestLabel "Collision Test"
        (TestCase 
            (do  let intialGameState = HaskellGame.Types.emptyGameState
                 let playerEntityId = 20140401
                 let playerEntity = GameEntity playerEntityId [toComponent $ Position 5 5,                                                         
                                                         toComponent $ BoundingBox 0 0 10 10]
                 let enemyEntityId = 20140402
                 let enemyEntity = GameEntity enemyEntityId [toComponent $ Position 5 5,                                                         
                                                         toComponent $ BoundingBox 0 0 5 5]
                 let gameState = insertEntities intialGameState [playerEntity, enemyEntity]
                 
                 let [((collisionEntityA,_,_), (collisionEntityB,_,_)) ] = HaskellGame.Physics.CollisionDetector.collisions gameState
                 assertEqual "Collisions detected" (playerEntityId, enemyEntityId) (collisionEntityA, collisionEntityB))
        )
    ]


HUnit produces pretty decent errors, wondering if something like Hamcrest would help though.

 

### Failure in: 0:AccelTest               
Force was applied
expected: Just (Position {_x = 1, _y = 205})
 but got: Just (Position {_x = 5, _y = 205})
### Failure in: 1:Collision Test          
Collisions detected
expected: (20140401,20140403)
 but got: (20140401,20140402)
Cases: 2  Tried: 2  Errors: 0  Failures: 2



Next steps and general impressions

I've implemented the basics of an animation system, an animation clip points to an array of images, but now the current game time needs to be threaded through the GameState, which will be also be needed to pause and save the game.  Eventually the clips will have to change based on changes to entity states, but because the animation frame is just a function of the current time and the start time of the clip, AnimationClip itself does not need to change.  This could help for background elements that just repeat a single animation cycle.

Having Int typed time is also inconvenient in a lot of places so I'll have to think about how to change it.

I cheated to play around with animation by adding a separate SDL getTicks call in the animation handler.  It's definitely wrong, but I've found it's kind of nice to have IO pockets here and there to cheat a bit, as long as it's clear that it's happening.

 

data AnimationClip = AnimationClip { _resourceId :: GameEntityIdentifier , _startTime :: Int, _rate :: Int }



So far I've been pretty happy with the project, and I haven't gotten really stuck at this early stage.  Refactoring to move the individual phases into different modules cleared a lot of things up and I've learned a lot.  I've been trying to prefer constructs that reduce the impact of changes over those that produce shorter code, though it's more of a feeling that I can't put into writing at the moment.

Changes are starting to get easier, and are starting to feel more localized.  Pattern matching is awesome but sometimes it feels like it introduces too much coupling.  Naming record fields with underscores got rid of a lot of compiler warnings, though there are still a lot left to clean up.

Eventually I need to work through a full usage of the event passing mechanism for some more involved game mechanics, work on saving the game, better resource loading, menu screen, then loading/storing levels and more.

I guess I'm saying if you're looking for a Haskell side project, a game engine will definitely burn some cycles :)

Wednesday, December 4, 2013

Writing elementary Haskell for fun and learning

(EDIT: decided to change the name of this to elementary)

I've been playing around with Haskell on and off for a while now.  I guess I wrote my first Haskell program around 2005.  It's been pretty slow going but I've started to get used to it more and more, and it has replaced Python as my main language for side projects alongside Java.

One of the great things about the Haskell community is that it is continually trying to find more elegant, more efficient and more powerful ways of solving problems.  Over the years this has resulted in a large body of knowledge that seems to be growing by leaps and bounds every month.

For a beginner though, even a long time beginner like myself, it can be intimidating and it can discourage you from learning more about this wonderful language.  You might feel that if your program that doesn't use the hottest techniques, idioms, and libraries then it will be obsolete before it's even completed.

The fact is though, that even if you write fairly bad Haskell, you will still learn a lot and you will learn even more refactoring that code as you go on.  Despite all of the sophisticated new concepts that people are developing in Haskell, the basic language is still incredibly powerful and expressive, and this is easy to miss if you are following the cutting edge developments.

As a response I purposely try to write elementary Haskell, and this helps me write more Haskell programs.  When programming elementary Haskell:

  • Use simple data structures.  Plain records, union types, and containers.  
  • Make specific data types first, parameterization can be done later
  • You probably don't need your own typeclasses yet
  • When in doubt, implement it in IO first and pull out pieces of pure code
  • Use wrapper types so you can change data structures later, e.g. data BookCollection = BookCollection [Books]
  • Use wrapper types to decouple code, especially to decouple application logic from complicated libraries
  • Stick to the plain IO monad, avoid monads like State,Reader, and Writer for pure code
  • Use IO to decouple code if needed.  
The thing about IO is that in your regular programs it's all over the place anyway.  It doesn't need to be removed instantly now that it's explicit.

Some extra things I've been trying to work on for general readability but haven't been doing enough of yet are:
  • Limit the number of direct dependencies a module has, use the number of imports as a guide
  • Isolate special language features in sub modules, see if the part that is needed can be wrapped in a simpler interface
  • Prefer qualified imports
Two side projects that I've been trying to use this on are:



I ended up wanting to create the editor after noticing that I really just wanted a tabbed editor for haskell files and found that emacs buffer switching was just encouraging me to make larger and larger modules.  If I can integrate it with command line applications through shelly then I should be ready to start using it regularly.

Eventually I might outgrow this practice but I think it results in code that strikes a good balance between taking advantage of Haskell's expressiveness while being fairly easy to understand and hopefully even easy to train other people to work with.  I probably need to work in lens for easier data manipulation and pipes or conduit to manage resources but so far it seems like I can still build some fun and enjoyable programs in this limited space.

Thursday, December 27, 2012

Free monads for structuring Haskell web apps

As it often happens, I found out pretty soon after my last post that there was a much easier way to work with free monads in Haskell already existing. The operational package makes it fun and easy to get started with free monads and avoids a performance problem with the naive implementation.

Purify code using free monads has a great description of how free monads can further isolate IO actions. Free monads allow you to have multiple "run" or "interpret" functions that actually carry out the actions of the monad. This allows you to:

  • Change implementations without changing client code
  • Manage configuration in the run function rather than in client code
  • Run client code in purely functional test harnesses

I've started experimenting with using free monads for these purposes in a web application. It's not in any way ready but the experience has been pretty interesting so far, so I've decided to post about it.

Managing configuration


Yesod and Snap already provide everything needed to make a web application but I wanted to experiment a bit more. I decided to use the Warp webserver directly through the Wai interface, which should expose more gritty configuration issues. I liked Dropwizard's approach: have a Configuration class serialized as YAML and have main read this to configure the app. Eventually I want run time configuration but this is a nice way to start.

So far the only configuration is the location of an sqlite3 database file.

Configuration.yaml


 databaseFile: sandboxData/cakeStore.sqlite3  

Configuration/Types.hs


 {-# LANGUAGE DeriveGeneric #-}  
 module Configuration.Types where  
 import GHC.Generics (Generic)  
 import Data.Aeson (FromJSON, ToJSON)  
 data Configuration = Configuration { databaseFile :: String }  
   deriving (Show, Generic)  
 instance ToJSON Configuration  
 instance FromJSON Configuration  

Configuration/Util.hs

 module Configuration.Util  
 where  
 import Data.Yaml  
 import Configuration.Types  
 readConfiguration :: FilePath -> IO (Maybe Configuration)  
 readConfiguration filePath = decodeFile filePath  

Database setup


We can now use this to read in our database configuration.
So far I've just got a basic script to initialize the database and add tables. As you can see there are still some embarrassing test values hanging around.

Ops/DataSetup.hs

 import Database.HDBC   
 import Database.HDBC.Sqlite3  
 import System.Environment  
 import qualified Configuration.Util as ConfigurationUtil  
 import qualified Configuration.Types as ConfigurationTypes  
 main :: IO ()  
 main = do  
    args <- getArgs  
    let configFile = head args  
    print $ "Reading config file " ++ configFile  
    maybeConfiguration <- ConfigurationUtil.readConfiguration configFile  
    case maybeConfiguration of  
         Just configuration -> runConfiguration configuration  
      Nothing -> return ()  
 runConfiguration configuration = do  
    conn <- connectSqlite3 $ ConfigurationTypes.databaseFile $ configuration  
    tables <- getTables conn  
    print tables  
    withTransaction conn $ createTest tables  
    disconnect conn  
 createTest tables conn = do    
   if not $ elem "users" tables  
      then do  
         run conn "CREATE TABLE users (id INTEGER NOT NULL PRIMARY KEY, name VARCHAR(256))" []  
         run conn "INSERT INTO users (name) VALUES ('DatabaseBob')" []  
         query <- quickQuery' conn "SELECT * from users where id < 2" []  
         print query  
         return ()  
      else return ()  
   if not $ elem "cakes" tables  
      then do  
         run conn "CREATE TABLE cakes (id INTEGER NOT NULL PRIMARY KEY, name VARCHAR(256))" []          
         return ()  
      else return ()  

The setup script can directly connect to the database, but the app itself needs something a little more structured. In Java-land data access objects are usually used to manage persistence details.
This is a good place for the first free monad.

Data/DataHandler.hs (summary)

I'd like to have a data layer, a collection of data access actions that can only (1) perform database transactions (2) call other data access actions. I'll probably have to switch the database library from hdbc to one of the *-simple libraries at one point, and I'd like to only have to change these details in the data access actions when I do. This type signature doesn't lock down the code too much but does provide a hint to other developers that only database access should be done in this monad.

 data DataInstruction a   
   where CallData :: DataCall a -> DataInstruction a  
      WithTransaction :: (Connection -> IO a) -> DataInstruction a  

A quick declaration with the operational package and we have a monad:

 type DataMonad a = Program DataInstruction a  

Now to interpret data access actions, data calls are interpreted by just running them and returning the result. Transactional actions are interpreted by connecting to the sqlite3 database, running the transaction. Eventually this should be changed so the connection should be held until the web request doesn't need it anymore, and connection pooling should be added with resource-pool.

 runDataMonadWithConfiguration :: DataConfiguration -> DataMonad a -> IO a  
 runDataMonadWithConfiguration dataConfiguration = eval.view  
  where   
   eval :: ProgramView (DataInstruction) a -> IO a  
   eval (Return x) = return x  
   eval (CallData (DataCall {execution=exec}) :>>= k ) =   
    do  
     result <- runDataMonadWithConfiguration dataConfiguration exec  
     runDataMonadWithConfiguration dataConfiguration $ k result  
   eval ((WithTransaction trans) :>>= k) =  
    do  
     result <- bracket (connectSqlite3 $ databaseFile $ dataConfiguration)  
              (\conn -> disconnect conn)  
              (\conn -> withTransaction conn trans )  
     runDataMonadWithConfiguration dataConfiguration $ k result   

Data/Users.hs


With the run function handling the connection details, data access actions can be defined in other modules. These modules can now be very light, they only have to import Database.HDBC and Data.DataHandler. I've made a strange choice here of wrapping the actions into a DataCall data structure. This is mostly to experiment with logging and mocking, but this data type also makes a nice hook for other free monads to connect to.

 getUsersCall :: Data.DataHandler.DataCall [[SqlValue]]  
 getUsersCall = Data.DataHandler.DataCall {  
  Data.DataHandler.name = "getUsersCall",  
  Data.DataHandler.execution = selectUsers,  
  Data.DataHandler.provideResult = Data.DataHandler.provideBlank   
  }  
 selectUsers :: Data.DataHandler.DataMonad [[SqlValue]]  
 selectUsers = do  
  let selectUsersQuery connection = quickQuery' connection "SELECT * from users" []  
  users <- Data.DataHandler.withTrans selectUsersQuery   
  return users  

Assembling the data layer


Now there's enough code to put together the data layer and run a test. There's some STM code here that isn't really used, I eventually want to use STM for runtime configuration.

Tests/DataTest.hs

 {-# LANGUAGE OverloadedStrings #-}  
 module Tests.DataTest  
 (tests)  
 where  
 import Test.HUnit  
 import Data.DataHandler  
 import Data.Users  
 import qualified Configuration.Util  
 import Control.Concurrent.STM  
 import Database.HDBC  
 tests = TestList [  
  TestLabel "database test"  
  $ TestCase $ do  
   Just configuration <- Configuration.Util.readConfiguration "Configuration.yaml"  
   configurationTVar <- setupDataMonad configuration  
   dataConfiguration <- atomically $ readTVar configurationTVar  
   users <- handleWithConfiguration dataConfiguration getUsersCall    
   assertBool "Successfully queried" (users == [[SqlByteString "1",SqlByteString "DatabaseBob"],[SqlByteString "2",SqlByteString "Steve"]])  
  ]   

Service layer


From here we just continue the plumbing up the stack. Service layer actions can only call other service layer actions or make data layer calls.
 data ServiceInstruction a  
   where CallService :: ServiceCall a -> ServiceInstruction a  
      CallData :: Data.DataHandler.DataCall a -> ServiceInstruction a  

Tests/ServiceTest.hs

  TestLabel "service to database test"  
  $ TestCase $ do  
   Just configuration <- Configuration.Util.readConfiguration "Configuration.yaml"  
   configurationTVar <- Data.DataHandler.setupDataMonad configuration  
   serviceConfiguration <- Service.ServiceHandler.setupServiceMonad configuration configurationTVar  
   user <- Service.ServiceHandler.handleWithConfiguration serviceConfiguration Service.Users.getUser  
   assertBool "Some users" ( (length user) > 0)  

Web layer

Finally up to the web layer. The web layer can only make service calls and render bytestrings to the client. The ServiceCall type prevents the web layer from making data calls directly. This layer needs a lot more work, especially parameter parsing, but the nice thing is that these actions should be easily runnable within other web servers/frameworks if needed. Handling the Wai interface is moved to the run function so most of the application code does not need to know about it.

Web/WebHandler.hs

 data HandlerInstruction a  
   where RenderView :: BlazeBuilder.Builder -> HandlerInstruction ()  
      CallService :: ServiceHandler.ServiceCall a -> HandlerInstruction a  

All view rendering can then be pulled into separate modules.
 listCakes :: Web.WebHandler.HandlerMonad ()  
 listCakes = do      
  cakes <- Web.WebHandler.callService Service.Cakes.getCakes  
  Web.WebHandler.renderView $ Web.View.Cake.render $ cakes  
  return ()  

Summary

So far with this experiment I've found:
  • Free monads can be used to separate application layers in a fairly usable way.
    • This adds a decent amount of extra code in the beginning but provides a lot of flexibility and I expect this code would stay fairly constant as the application grows.
    • A command line application that hits the service layer was easy to make.
  • Moving configuration management to monad run functions is handy. An interesting possibility is to have the run function keep a reference to its configuration in STM. The run function could then be configured by passing it configuration actions that change the configuration.
  • Wrapping actions allows some new options for organizing code although it is ugly. Some of these could probably be achieved with newtype, but there's still more experimenting to do. One idea is restricting the web layer to only call AuthenticatedServiceCalls but allowing the service layer to call both AuthenticatedServiceCalls and plain ServiceCalls

Mock testing and free monads:


I'd really like to do some mock testing with free monads. Growing Object Oriented Software Guided by Tests is one of my favourite books and I think a lot of its ideas can be used in building Haskell applications. It will probably take some work to translate the concepts over though. I certainly haven't done TDD with the code so far, but in its current state it doesn't seem too far off.

Mock testing would do a lot to help this situation. A workable way to program in action return values could also lead to a very powerful way to test applications using LogicT or QuickCheck to generate expectations.

I managed to hack in some sort of mocking using Data.Dynamic but it's not pretty. This test case happens to "know" that the only DataCall made will return a list of Cakes, but I really want to match on the signature of the call and then provide the appropriate data back.

  TestLabel "mock getCakes"  
   $ TestCase $ do    
    let interpretGetCakes = eval . view  
      eval :: ProgramView (Service.ServiceHandler.ServiceInstruction) a -> IO a  
      eval (Return x) = return x       
      eval (Service.ServiceHandler.CallData call :>>= k) = do  
       let result = Data.DataHandler.provideResult call (toDyn [Model.Cake.Cake 0 "Black Forest"])  
       interpretGetCakes $ k result  
    result <- interpretGetCakes $ Service.ServiceHandler.execution Service.Cakes.getCakes  
    assertBool "Expecting cakes" (result == [Model.Cake.Cake 0 "Black Forest"])  


Everything here is still a work in progress but it's worked out a lot better than I would have thought so far. All the code here is available at https://github.com/stevechy/HaskellCakeStore which I hope to keep updating it as the experiments continue.

Saturday, February 5, 2011

How monads sequence actions: A code driven example

Monads are abstract but how they are used to sequence things is mechanical. It's hard to see this in most monads because the building of the monad is combined with the sequencing.

To see how this works we're going to start by defining a monad that makes the building part simpler.


data ConversationMonad a = Ask a | Return a | Combination (ConversationMonad a) [(a -> ConversationMonad a)]


We want this monad to represent a computation that can Ask the outside world a question, and receive an answer of the same type back. The Ask constructor represents the action of asking a question, the other two constructors set up the monad structure.

What we are defining is not quite a monad, so we have to define our own interface.


class NotQuiteMonad m where
bind :: m a -> (a -> m a) -> m a
ret :: a -> m a


An m monad must have a way to build a return monad given a value, and a way to build a bigger m monad by adding a computation step to a monad. What I'm calling a computation step is a one argument function that returns a monad. The return monad is used as plumbing, it feeds a value to the next computation step and should not do anything else.

Let's provide these operations for our ConversationMonad.


instance NotQuiteMonad ConversationMonad where
bind monad computeStep = case monad of
Combination innerMonad list -> Combination innerMonad (list ++ [computeStep])
a@_ -> Combination a [computeStep]

ret k = Return k


This definition makes the Combination constructor a representation of binding and Return a representation of Return.

If you go back and read the definition of ConversationMonad, you can see that any ConversationMonad must be either an action asking a question, plumbing that passes on a value, or a combination of a ConversationMonad and a computation step.

A way to see this is that there is one basic action, Ask, a way to sequence these actions, Combination, and some plumbing for the sequencing Return.

You should also be able to see that the only thing we can do with the ConversationMonad is build different instances of it. For this monad the building is very simple. None of the computation step functions are evaluated, they are just put in a list.

Now we want to interact with the monad, so let's hook it up to the console by writing some code to run it:


runMonadString :: ConversationMonad String -> IO String
runMonadString m =
do
case m of
Ask saidString ->
do
putStrLn saidString
answer <- getLine
return answer
Return returnString ->
do
return returnString
Combination monad [] ->
runMonadString monad
Combination monad (computeStep:rest) ->
do
intermediateValue <- runMonadString monad
computeStepIntermediateValue <- runMonadString (computeStep intermediateValue)
runMonadString (Combination (Return computeStepIntermediateValue) rest


To run the Ask action, output the question and ask the user for a response. To run the return action, just return the value to pass it into the next step.

To run a ConversationMonad that was built from a bind, we have to run the 2 parts, the monad, and the list of compute steps.


  1. We run the monad, which will return a value that we store.
  2. We then apply the computation step to that value to get another ConversationMonad.
  3. We run the monad we got back to get another value which we use to process the rest of the list of computation steps.


Step 2 is where it is important that our computation step returns a ConversationMonad rather than another String. This is because the computation step can return a ConversationMonad built from a bind, which means it can return another computation step. This gives computation steps the power to implement looping.

By using closures you can pass values to later computation steps without going through the monad.

To see this, and test out our console hookup, let's build a ConversationMonad:


echoMonad :: ConversationMonad String

echoStep :: String -> ConversationMonad String
echoStep = (\response ->
if response == "Quit"
then Return "Quit!"
else
bind (Ask response) echoStep)

echoMonad = bind (Ask "How are you?") echoStep


echoStep is a looping computation step. It just asks whatever it got back as an answer the last time. echoStep by itself is not a ConversationMonad, so we need to bind it to one to make it one.

Everything is hooked up, let's run it:


main =
do
runMonadString echoMonad



ghc monadTutorial.hs
./a.out
How are you?
hi
hi
asdf
asdf
asdfe
asdfe
re
re
adf
adf
Quit


The implementation of the side effects of Ask is completely contained in the run function, which isn't tied to the type at all. So we can a different run function that does something else.

Let's write a run function that gets responses from a list of Strings, so instead of running it with side effects, we now run it purely functionally.

To run ConversationMonads functionally, we're going to need to store the state in some structure and update it functionally. This will work like the seed in a left fold.


data LoggingRunState = RunState {
runLog :: [String],
listOfResponses ::[String],
intermediateValue :: String,
validState :: Bool
} deriving (Show)


The state is going to be a log of what has happened in the run, a list of responses to use, the value to pass in to the next computation step and a flag indicating if the computation has failed or not.


initialRunState responseList = RunState {
runLog = [],
listOfResponses = responseList,
intermediateValue = "",
validState=True
}


Now we define the run function, it takes an state and processes the actions in the monad on that state, yielding a new state.


runMonadFunctional :: LoggingRunState -> ConversationMonad String -> LoggingRunState

{- Use the list of responses to pass answers into the monad and log these actions -}
runMonadFunctional runState (Ask saidString) =
case listOfResponses runState of
[] ->
RunState {
runLog = runLog runState,
intermediateValue="Out of messages!",
listOfResponses=[],
validState=False
}
cannedResponse:rest ->
RunState {runLog = (runLog runState) ++ ["Monad asked:" ++ saidString, "Reply " ++ cannedResponse],
intermediateValue =cannedResponse,
listOfResponses=rest,
validState=True
}

runMonadFunctional runState (Return returnString) =
runState {intermediateValue = returnString}

runMonadFunctional runState (Combination monad computeStepList) =
let intermediateState = runMonadFunctional runState monad
in runMonadFunctionalComputeSteps intermediateState computeStepList


runMonadFunctionalComputeSteps :: LoggingRunState -> [String -> ConversationMonad String] -> LoggingRunState

{- If we are out of steps to run return the currrent state -}
runMonadFunctionalComputeSteps runState [] = runState

{- Once we hit an error state, stop running the monad and just return the state -}
runMonadFunctionalComputeSteps runState (computeStep:restOfComputeSteps) =
case validState runState of
False -> runState
True ->
let monad = computeStep (intermediateValue runState)
computeStepRunState = runMonadFunctional runState monad
in
{- Run rest of compute steps and return the value -}
runMonadFunctionalComputeSteps computeStepRunState restOfComputeSteps



Let's run it:


main =
do
runMonadString echoMonad
putStrLn (show (runMonadFunctional (initialRunState ["first", "second", "third", "Quit"]) echoMonad ))
putStrLn (show (runMonadFunctional (initialRunState ["first", "second", "third" ]) echoMonad ))



./a.out
How are you?
Fine thanks and you?
Fine thanks and you?
I'm well
I'm well
That's good
That's good
Quit
RunState {runLog = ["Monad asked:How are you?","Reply first","Monad asked:first","Reply second","Monad asked:second","Reply third","Monad asked:third","Reply Quit"], listOfResponses = [], intermediateValue = "Quit!", validState = True}
RunState {runLog = ["Monad asked:How are you?","Reply first","Monad asked:first","Reply second","Monad asked:second","Reply third"], listOfResponses = [], intermediateValue = "Out of messages!", validState = False}

Wednesday, December 15, 2010

The NZSTM Software transactional memory

Another look at NZTM: Nonblocking Zero-indirection Transactional
Memory (pdf)
and NZTM appendix.

Last year around this time I was planning to write a blog post about NZSTM since I had just read the paper on it at SPAA 2009. Then work kicked in and I lost the text. I just realized the pictures I made up were still on the drive.

I'm even busier now, but I figure it took me a while to make these pictures, so even a quick tour through them should be worth something even if software transactional memory isn't as hot these days.

There are a lot of STMs out there, but I figure this is the one to start with, it's practical in many ways and has some really neat techniques.

So you've got a bunch of objects that you want to be managed by NZSTM. You add 3 fields to each object. Owner type, owner pointer, and a backup pointer. There are only going to be a two owner types so you can store the type and the pointer in a single word, this will be important since compare and swap (CAS) only works on word sized items.

Assume sequential consistency here, no weird memory models.

Objects will be acquired by updating the owner field (o-type,o-pointer). I'll talk about the backup pointer and the owner type more later.



In the normal case, the owner of an object is going to be a transaction object. You create a transaction object when you start a transaction. These transactions aren't nested so you can assume each thread is only going to be using one at a time.

The transaction object just stores the state of the transaction. But also, importantly, it occupies a unique position in memory. This is a picture of the states that the transaction can be in and how you can move between them.



If we have a transaction and the object does not have an owner, we can acquire it by CASing in the pointer to our transaction into the owner field of the object.



This puts the object into an acquired state.



To commit a transaction in NZSTM, you use CAS to change its state as shown above. CAS is used because the owner of a transaction can commit it, but other threads may try to abort the transaction. A commit only involves the transaction object, you don't have to go back and access all of the objects involved.

To acquire an object that has already been used in a transaction, you have to


  1. Get the owner of the object, at this point, it will always be a transaction
  2. Get the transaction status
  3. If the transaction is committed or aborted, you can CAS your transaction in to acquire the object.


Once the transaction is committed or aborted, it cannot move to any other state and will not be used to access any of the objects it owns anymore, so we can safely take ownership of the object from it.



With this set of operations on objects, you can make a blocking STM, which you could just call locks with a different interface. Locking STMs are usually faster than non-blocking STMs because they avoid copying and avoid pointer chasing. The nice thing about NZSTM is that it acts just like a locking STM in the normal case so you get the performance benefits, but also gives you an option to abort another transaction if needed.

How does that option work?

To add the option, we need to add code to back up objects before you write to them. This is done by

  1. Making a copy of the object
  2. Setting the backup pointer to point to the object (plain write, no CAS)


The important part here is that all the bits are written to the copy before you set the backup pointer, otherwise other threads may see a partial copy.




To abort a transaction, we can CAS its state from ACTIVE to ABORT REQUEST. Only the owning thread of a transaction can move the transaction from ABORT REQUEST to ABORTED. If a thread checks its transaction and realizes that it has been requested to ABORT, it can move into the ABORTED stage which lets other threads know that it will no longer write to the objects it owns using that transaction.

If you want to acquire an object that is owned by an ABORTED transaction, you:

  1. Get the owner transaction object and read that it is ABORTED
  2. CAS in your own transaction object to kick it out
  3. If the CAS was successful, copy the backup data back to the object to undo any changes the ABORTED transaction may have done. Because the transaction is ABORTED, you know that there will be no more writes related to that transaction on the object, so for instance, something wouldn't suddenly change after you copied the backup data back over.




So far so good, but this only works if the thread that owns the transaction is able to realize that it has an ABORT REQUESTED and move to the ABORTED stage. To be able to work on objects owned by a thread that suddenly dies or just goes to sleep forever, we have to add in pointer indirection like other STMs.

The cool part is that this indirection only needs to be used as a last resort, so if it doesn't happen very often, most of the time the only price you pay is to make an extra copy of the objects you are writing to. But the actual reading and writing is done directly to the object, so they stay the same speed.

This is where the owner type field comes in. In the normal case, the owner of an object will be a transaction, so the type will be transaction. In the normal case objects are directly written and read to.

In the new case, the owner of the object will be a locator, the type will be a locator, and we will write and read from a copy of the object that we point to.

Using a locator, we can acquire an object owned by an transaction in ABORT REQUEST state without waiting for it to move to ABORTED. This picture calls it ABORT REQUEST "ABORTING" I guess I hadn't changed it.



We come across this object, which is in the ABORT REQUEST state, we can't acquire it in the normal way, so first we create a locator. The problem is that until the owner is ABORTED we can't do anything with the data actually in the object because it might be written to at any time.

The backup copy is safe though, so we:

  1. (aborting transaction) Get the pointer to the ABORT REQUEST transaction
  2. (backup) Get a pointer to the backup copy
  3. (updated copy) Copy the backup copy to a local copy to modify and use
  4. (owner)Get a pointer to our transaction


And put all of these things in a data structure called a locator:



After the locator is created, we CAS it in to the owner field to acquire the object. If the CAS was successful, no other thread managed to do this before us.



This puts the object in what is called an inflated state. An object is inflated if its owner is a locator type.




To read and write an inflated object, you have to go to its locator, get the update copy, and read and write that. It's slower but it lets you work on the object when a locking STM would not allow you to do anything.

I'm out of pictures, so it'll have to be text only for the end. Now that there are inflated objects we need be able to acquire an inflated object with a locator pointing to a committed transaction, and acquire an inflated object with a locator pointing to an abort requested or aborted transaction.

My memory is a bit off in this case, but the steps are mostly the same in all these cases. The object is inflated so it will be owned by a locator, call it the enemy locator.

  1. (aborting) get the aborting transaction of the enemy locator
  2. (owner) get a pointer to our transaction
  3. If the owner transaction of the enemy locator is COMMITTED:

    1. (updated) get a copy of the enemy locator update data
    2. (backup) point this to the enemy locator update data

  4. If the owner transaction of the enemy locator is ABORTED or ABORT REQUESTED:

    1. (updated) get a copy of the enemy locator backup
    2. (backup) point this to the enemy locator backup data



Put all these things into a locator, and CAS it in to the owner field of the object. If the CAS succeeds then you own the inflated object. The enemy can continue to modify its local copy of the object, but it will not affect anything else.

Finally, to finish it off, inflated objects are slower so we need to be able to deflate objects to their faster deflated forms. This can only be done if the aborting transaction, the one that still has direct access to the object, has moved the transaction to the ABORTED state. To do this, roughly the idea is:


  1. Acquire the object in inflated mode, meaning you will have to create a locator.
  2. Check the aborting transaction of the locator and see that it is ABORTED
  3. CAS the backup pointer of the locator to the backup pointer of the object
  4. CAS your transaction in with type transaction to the object owner, replacing your locator as the owner.
  5. Copy the backup data to the object.


There might be a modification to these steps to make sure the backup pointer is updated properly. The main idea is that you might become ABORT REQUESTED before copying the backup data to the object, but that is ok because any other transactions will only look at the backup data at that point anyway.

And since you can only deflate by CASing out your own locator, it makes sure that no other transaction acquired the object in between, or the CAS would fail.

The object will now point to a transaction type, and so it won't be inflated anymore.

That completes the system, a non blocking transactional memory with low overhead and direct object access in the common case with low contention.

One of the key ideas of NZSTM is that the pointer structure combined with the data in the structure encodes a state that an object can be in. Every form of acquiring an object uses a sequence of mini transactions involving one CAS to move the object into another state. At any of these states there is a sequence of mini transactions that can get you to an acquired state, that makes NZSTM nonblocking.

I was pretty loose about how CAS was used. Usually you read the field to get the compare value, then possibly do some other reads to create a swap value, then swap it in.

How do you reason about systems like NZSTM? My opinion is that with some work it can become fairly straightforward to write decent detailed proofs of correctness for them that cover the subtle logic involved and may even be able to involve weak memory models. Fully formal proofs may take some further time after that. I went through the process of making these kinds of proofs in my research and I really think it's just a matter of interest and time.

Are people interested in this kind of reasoning? There are definitely some groups doing a lot of good research in this area, but outside of it? I'm really not sure.