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:

A game project 

And a haskell editor.

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.

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.
• STM is a natural place to store read often/write seldom configuration information.  The paper Contextual Effects for Version-Consistent Dynamic Software Updating and Safe Concurrent Programming explores this idea.  
• 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.

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}

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.

Code layout experiements

I managed to get my Black Triangle for the code layout project that I rambled on about earlier.

It has been pretty fun, getting to this stage I realize how long it's been since I got to sink in a good chunk of time into a side project. Also, making these ideas more solid convinces me that I wasn't on a total wild goose chase.

Let's start with a pretty typical view of Java code in an editor, in this case, emacs.



There are a few problems with reading code in this format:

• The modifiers place the name of the class, member methods and members in an unpredictable place.
  
  
  
  • If you scan down the source code it's hard to pick out the method names because you have to scan left each time.
    
  • Take a look at how JavaDoc tries to make this easier. But there is still a problem, if you are scanning for names, it's hard to scan for arguments at the same time.
    
  • Scanning for extends and implements, very important pieces, also takes some time.
    
  
  
• Indentation is used to separate the class header from its member declarations, but this space is wasted since there aren't too many top level classes in a file.
  
• A lot of colors are needed to emphasize the various pieces of syntax, and the colors switch a lot as you are scanning through the text, which can be distracting.
  

Some of these can be solved by changing around the whitespace conventions, but these can only go so far. Looking at a few books on graphic design you will quickly realize that there are so many more effective ways to organize information.

Here's my first attempt at addressing these issues:

• I've tried to stay away from colors, and use size and space to organize the information.
  
• Modifiers aren't handled yet, I'm thinking of using something small like icons to indicate that information.
  
• A lot of brackets, parentheses, and other punctuation have been removed. I think this makes everything look a lot less cluttered. The layout will have to make sure that it's still possible to see what's going on.
  
• Indentation is reduced, and the class header and method declarations become more like headers in regular documents.
  
• I've been experimenting with different ways of displaying the arguments, the current one which is a table with the types greyed out looks pretty good so far.
  
• The for loop layout isn't fully worked in yet, it's trying to bring the initial and update pieces of the loop closer together.
  
• I rely on Cairo for the text render dimensions, this gives me inconsistent results if the text happens to have/not have descenders or ascenders.
  

Ok, so IANAGD (I Am Not A Graphic Designer) but enough is set up now so that many different possible layouts are possible.
I'm hoping that this will be a nice sandbox that can be used to try out all sorts of different ways of laying out code.

It's written in Python and uses Cairo to render. To represent the Java syntax, I made a class for each grammar element that I figured made sense, then the layout class just does a big isinstance dispatch to render all the pieces. This seemed like the best way to allow multiple layout engines for any particular format. All grammar elements provide a text() method that allow you to have a fallthrough case, giving it a bit of graceful degradation.

The layout works in a TeX-ish way, building boxes into horizontal and vertical boxes with baseline information with another basic box type for Cairo rendered text. It only does the straightforward computations, not the more complicated line breaking and constraint solving.

Academic work is probably about to ramp up again, so this project is back on the back-burner, but I still have more that I hope to work in:

• Integrate ANTLR parsing of Java files using Terrence Parr's Java 1.5 grammar. I've figured out mostly how to do this, so what's left is to go through the pain of coding it. Also it will take a fair bit of work to shape actual parse tree into the type of AST that I want. So some grammar hacking to get the right tree out, then additional processing to get it into a form that's friendly for the layout engine.
  
• Implement horizontal and vertical "rules" or lines.
  Since I based this version on the functional version of TeX's layout, boxes have no notion of parent. It seems like the best way to make these work is to add in parents, which will also open up room for more interesting features. Hopefully some ideas from Hopscotch port over.
  
• Work in some clipping, vertical boxes do not have to render contents outside of the window bounds... etc. Then add scrollbars.
  
• More layout features. A basic table container has already been written, but I'd like something more general, maybe linear constraints, that would allow more flexible grid layouts. These would be used in small areas since they are harder to optimize.
  
• A few more TeX features, fraction and exponent layout.
  
• Interactivity! I didn't plan on this originally, but now that I'm at this stage, I have a fairly good idea of how this could work. Implementing vertical rules will give me an easy way to display a cursor.
  

Moving On

So far this blog experiment has worked out well, I've been writing regularly and getting a decent amount of words out in a fairly short amount of time.

I don't like the quality of the posts I've done so far though, so I'm going to start something new, where there is still a regular posting schedule, but I set aside enough time to make high quality posts.

I'll probably still post on here, but not on a regular schedule.

Open source

I've been using open source software on and off for quite a while, and it constantly amazes me how much there is out there and how well supported it is. That the huge package repositories of Debian and Gentoo actually get tested and sometimes maintain their own patch sets of different software packages seems like an incredible amount of work, and it's volunteer supported.

There are recurring complaints about open source, but in some ways its a measure of what people come to expect from it. Say 10 years ago, you had to muck around with a lot of stuff and eventually it worked and that was good enough, some of the good projects had a small dedicated group and you could get pretty good help from the forum or mailing list. These days it almost seems like every large project has an army of people doing everything from testing, to documenting and programming.

A major complaint used to be about the huge number of window managers available. A lot of the complaints were saying that there wasn't enough standardization, that these other projects were diluting the effort. But then GNOME and KDE got more mature, and those complaints died down. It seems like the number of window managers wasn't the real problem, just the lack of some nice defaults.

This is great, because I happen to really like this whole scene of experimentation that goes on because you can change the window manager, rip stuff out, add stuff in, and have different ways of organizing how you work with your computer. The other thing that is nice about this is that the X.org people think about how to introduce new features in a window manager friendly way. This slows development down, but just looking at the new things that are coming in to X.org such as indirect rendering, new architectures for drivers and MPX makes me think that there's only more good stuff to come.

There's a lot of back-end work going on that doesn't look too impressive, especially when your other software stops working for random reasons, but from a programmer's viewpoint, it looks clean and thoughtfully designed. I can't wait to see what's going to be built on top of it.