Posted on April 6, 2013

As part of my master thesis at the University Utrecht I developed a library for OO programming in Haskell. With this library I was able to port a subset of wxWidgets (written in C++) to Haskell making it possible to compile wxAsteroids down to JavaScript using UHC and run it inside the web browser. The result is visible here:

The original wxAsteroids wxAsteroids running in the web browser

I know that it might sound strange, OOP in Haskell, but it turns out that with some clever tricks it is not impossible. A quick search on Google shows that at least on stackoverflow the topic OOP vs Haskell shows up now and then which makes me think that there might be some people out there that are interested in the relationship between the two. I hope that by sharing some of the insights that went into developing the library I can add a bit to the understanding of how Haskell relates to OOP and vice versa.

Obviously I’m not the first who tried OOP in Haskell. There are two well-documented approaches that have been known to the insiders for quite a few years already: O’Haskell and OOHaskell. The former is a new language based on Haskell with subtype polymorphism, whereas the latter shows that many OOP techniques are already achievable by making nifty use of Haskell’s advanced type-level programming capabilities. Unfortunately I was not able to use OOHaskell due some limitations of the UHC which forced me to explore some alternatives. Eventhough I initially thought OOHaskell had already explored almost every corner it came as a surprise to me that one of the more primitive OO encodings turned to be more expressive. After some extensive fiddling with the type system I was able to beef it up to something sufficiently expressive for my purposes whilst not being extremely to tedious to program with.

In order to give you an impression what it takes to do OO programming in Haskell I’ll walk through an example that is often used as a benchmark for OO languages. Below is an UML diagram that shows the abstract class Shape with two concrete subclasses Rectangle and Circle.

A Shape maintains a position and provides methods to directly moveTo a new position, move relative to current position rMoveTo, or draw the Shape in question. Rectangle and Circle augment their superclass with additional geometric data and implement the abstract draw method. To exercise subtype polymorphism different kinds of shapes are placed inside a collection of shapes. The collection is then iterated over drawing each individual shape.

First, we translate the Shape class to a plain Haskell record.

data IShape a = IShape {
     getX        :: IO Int
   , getY        :: IO Int
   , setX        :: Int -> IO ()
   , setY        :: Int -> IO ()
   , moveTo      :: Int -> Int -> IO ()
   , rMoveTo     :: Int -> Int -> IO ()
   , draw        :: IO ()
   , _shapeTail  :: Record a
}
DefineClass(Shape,IShape,shapeTail,,1)

As you can see record selectors correspond to methods in the Shape class. There is a special method _shapeTail which makes it possible to extend the record with new methods. This technique is referred to as type extension through polymorphism*. Finally, we use a C pre-processor macro for deriving some of the record manipulation boilerplate (Lenses would have been more appropriate here).

Now the implementation of the Shape class is simply given by a function:

shape newx newy concreteDraw tail self = do
    -- Create references for private state
    x <- newIORef newx
    y <- newIORef newy
    -- Return a Shape
    return IShape {
         getX       = readIORef x 
       , getY       = readIORef y
       , setX       = writeIORef x
       , setY       = writeIORef y
       , moveTo     = \newx newy -> do
          self # setX $ newx
          self # setY $ newy
       , rMoveTo    = \deltax deltay -> do
          x <- self # getX
          y <- self # getY
          (self # moveTo) (x + deltax) (y + deltay)
       , draw       = concreteDraw self
       , _shapeTail = tail
    }

It takes the two initial values for x and y, an implementation for the draw method, an extension of the record, a self-reference, and returns an instance of Shape (i.e. a value of IShape). The concreteDraw parameter makes it explicit that we cannot obtain an instance of Shape unless we provide it with an implementation of draw. Interestingly, we are not in any way forced to create a subclass of Shape in order to implement draw. We can simply supply the implementation of draw as an argument - in Java you would need an anonymous inner class.

The tail parameter represents a possible extension of the record and should only be used at _shapeTail. Interestingly, self is given as a parameter whereas in most OO languages it is treated as something special. For stylistic purposes we use some syntactic sugar to distinguish between regular functions and methods:

(#) :: a -> (a -> b) -> b
o # f = f o

The Rectangle class is transcribed similarly except that we use a different macro for deriving the boilerplate:

data IRectangle a = IRectangle {
     _getWidth      :: IO Int
   , _getHeight     :: IO Int
   , _setWidth      :: Int -> IO ()
   , _setHeight     :: Int -> IO ()
   , _rectangleTail :: Record a
}
DefineSubClass(Rectangle,Shape,IRectangle,rectangleTail,,,,1,)

Here is the implementation of Rectangle:

rectangle x y width height =
   (wrapper `extends` shape x y draw) noOverride set_Shape_Tail
   where
   wrapper tail super self = do
      w <- newIORef width
      h <- newIORef height
      return IRectangle {
           _getWidth       = readIORef w
         , _getHeight      = readIORef h
         , _setWidth       = writeIORef w 
         , _setHeight      = writeIORef h
         , _rectangleTail  = tail
      }

   draw self = printLn ("Drawing a Rectangle at:(" <<
                  self # getX << ", " << self # getY <<
                  "), width "  << self # getWidth << 
                  ", height " << self # getHeight)

We use the extends combinator in order to make Rectangle a subclass of Shape. It combines the implementation of Rectangle given by rectangle with that of its superclass. The right-hand side of extends is analogous to calling the superclass constructor. In between the extension of the superclass with its subclass there is an opportunity to override functionality defined in the superclass. The function that allows for this to happen is also passed as a parameter to extends. Because Rectangle does not override any functionality we simply pass in noOverride which is essentially the identity function. The last parameter is simply used for combining the methods of a Shape with those of a Rectangle.

Notice how we left out the underscores on the methods when invoking them on self. The reason for doing this is that we cannot directly call for example _getWidth. If you think of the type inferred for self this should become obvious.

self :: IShape (IRectangle a)

What we actually first need to do is perform the method lookup. Since the representation of objects is not hidden like in any typical OO language we have to deal with this ourselves. For example, calling getWidth requires a method lookup for _getWidth:

getWidth = _getWidth . unRecord . get_Shape_Tail

I leave out the type definition and implementation of Circle because it is similar to Rectangle’s and continue with implementing a piece of OO code that will loop over a list of shapes and draw them to the screen.

myOOP = do
   s1 <- new $ rectangle 10 20 5 6
   s2 <- new $ circle 15 25 8

   let scribble :: [IShape ()]
       scribble = consUb s1 (consUb s2 nilUb)
  
   sequence_ $ 
      map (\shape -> do 
            shape # draw
            (shape # rMoveTo) 100 100
            shape # draw
          ) scribble   
    

We use the new combinator for creating instances. Notice that we cannot simply place s1 :: Rectangle and s2 :: Circle inside a list of shapes because the types do not form an exact match. In any OO language this would work just fine as a virtue of subtype polymorphism. In Haskell lacks this general form of subtype polymorphism and requires some additional help. Hence we use a helper function consUb that automatically converts the type to Shape before it cons the element onto the list.

ghci> myOOP
Drawing a Rectangle at:(10, 20), width 5, height 6
Drawing a Rectangle at:(110, 120), width 5, height 6
Drawing a Circle at:(15,25), radius 8
Drawing a Circle at:(115,125), radius 8

Using the library it is also possible to discriminate on the type of an object. The following function only draws shapes that are at least a Rectangle:

selectiveDraw :: IShape () -> IO ()
selectiveDraw shape =
  when (shape `instanceof` (undefined :: IShape (IRectangle ())))
       (shape # draw)

By now you might be wondering about what the implementation of the combinators looks like. Although it comprises not more more than 300 lines the details are quite intricate and are devoted an entire chapter. If you are interested you can read my thesis which also contains much more examples including the ones where the approach starts to break.

* F. Warren Burton: Type extension through polymorphism

comments powered by Disqus