simple-actors is my library for more structured concurrent programming based on the Actor model. It’s been a fun vehicle for exploring concurrent semantics, and an opportunity to solve some tricky API design problems in pretty clever ways. I want to present a handful of these problems, and the solutions I came up with, below.

Short digression: I love distributed systems, but this library has nothing to do with distributed programming. Also performance.

Goals and Constraints

To frame things, these were more or less the goals of the library design:

• create a friendly, light-weight (hopefully intuitive), non-leaky, non-brittle eDSL for concurrent algorithms
• base functionality on existing typeclasses and abstractions wherever possible
• employ an economy of concepts; avoid creating new things requiring names and explanations, unless absolutely necessary

And here are the three little case-studies.

Eschew channel abstraction

The first challenge was how to keep the abstraction for message routing as minimal as possible. Ideally we would like our spawn function to return a token (we call it a “Mailbox”) that is used by other actors as a reference for sending messages to the spawn-ed actor:

spawn :: Behavior a -> Action (Mailbox a)

But then how do you handle two actors sending messages to each other? Or an actor sending itself a message for that matter?

do a <- spawn $ senderTo b
   b <- spawn $ senderTo a
   c <- spawn $ senderTo c
   send a ...

The sequencing of monadic actions in a do block make scoping an issue here, so what can we do?

Should we insist that actors like a and b pass their mailboxes explicitly in messages? But then we’d have to build implicit access to an actor’s own Mailbox into our Behavior abstraction since we can’t even define a Behavior closed over it’s own Mailbox, as in c above.

What about separating channel creation and spawning into two distinct functions, where we spawn a Behavior listening on a channel? But then we have to decide what should happen when two actors are spawned on the same channel, etc. Let’s just not do any of that.

The solution turns out to be a matter of knowing the right classes, in particular the exotic MonadFix (read up on it here). Combined with GHC’s lovely DoRec extension, our crisis resolves itself, allowing:

{-# LANGUAGE DoRec #-}
do rec a <- spawn $ senderTo b
       b <- spawn $ senderTo a
       c <- spawn $ senderTo c
   send a ...

IMHO this looks much tastier than what erlang has to offer.

Mailbox should support a rich set of transformations

A second design challenge has been to try to realize the full potential of our internal “chan” pair type (of which Mailbox only is exposed) in terms of CT-ish transformations supported.

Some background: a concurrent Chan separated into a pair of “read” and “write” sides is attractive, because it suggests the possibility for the “read” end to have a Functor instance, while the “write” side suggests it could be a contravariant functor, supporting an operation:

contramap :: (Contravariant f)=> (b -> a) -> f a -> f b

Consider how Control.Concurrent.Chan doesn’t permit that possibility.

Initial versions of chan-split (used internally) defined Functor and Contravariant instances, supported with a clumsy GADT representation which looked like, e.g.

data InChan i where
    InChan :: (i -> a) -> C.Chan a -> InChan i

This was removed when I realized I could support the operations (“read” / “write”) and powerful transformations that weren’t possible before, by defining Mailbox as simply a wrapper around writeChan c itself. Likewise, our internal “write end” becomes a wrapped readChan c action:

newtype Mailbox a = Mailbox (a -> IO ())
newtype Messages a = Messages (IO a)

Here are the nice transformations we’ve defined so far; more are possible. N.B. that these don’t add anything in terms of expressiveness to the actor model, i.e. we could envision doing the same sort of thing trivially with actors.

Getting more expressive with join patterns

The final and most recent design bit I wanted to share address the problem of “synchronization”.

Consider how you would go about trying to definean actor that “pairs up” inputs received from a pair of actors; your solution would involve an actor that kept a possibly-ever-expanding buffer of unmatched messages. This is a limitation inherent in the actor model, and leads to needless tragedy like erlang’s “selective receive”.

What we want is to be able to define an actor that can block on multiple channels. How do we do that without weird channel abstractions creeping into our API?

I’d been mulling around the idea of creating a completely new beast, sort of dual to an Actor that could read from arbitrary chans, and feed inputs one-at-a-time to an actor. A “Reducer” or something.

Luckily I had a better idea while reading about process calculi, in particular the join calculus. The solution makes the library formally more expressive while removing complexity from the UI and leaving the semantics of behaviors and message-passing unchanged!

The trick was to come up with a class that would allow the spawn function to introduce assymetry between spawned Behavior inputs and Mailboxes, i.e. we create a spawn that can return multiple Mailboxes which are “joined” to a single Behavior input in the background:

sumTuple :: Behavior (Int, Int)

do b <- spawn sumTuple
   send b (4, 1) 
   -- or. like magic...
   (b1, b2) <- spawn sumTuple
   send b1 4
   send b2 1

See the docs for a few other examples of the new behavior of spawn. The Sources class works using TypeFamilies and an associated Joined type that is a function of the return type of spawn. Use the source.

Meta

Is this sort of post interesting, or is this kind of case study too esoteric or domain-specific to be useful? Let me know. And if you have ideas of your own or want to help with performance testing, do a

git clone https://github.com/jberryman/simple-actors.git

and play with it.

I finished this new zipper library which you can get with a

cabal install zippo

and fork it on github.

After working for a long time on pez, I wanted to try a zipper library that was also based on lenses, but where heterogenous move up operations would be type-checked, as would a move up past the “top” of the structure.

It looks as though instant-zipper is the only other zipper package that provides that kind of type safety.

Mini walk-through

The pieces that make up our zipper are

data Zipper st b = Zipper { hist  :: st b , viewf :: b }
data (:>) st b c = Snoc (st b) (c -> b) 
data Top a = Top

Which come together in types that might look like, e.g.

z :: Zipper (Top :> Tree a :> Tree a) a

for a zipper perhaps at the leaf element of a child node in some Tree a type. Of course in most cases, no type annotations will be given.

Here are the zipper enter and leave operations:

zipper :: a -> Zipper Top a
zipper = Zipper Top

close :: (Hist st a b)=> Zipper st b -> a
close (Zipper st b) = runHist st b

The close function was the only tricky part, and Daniel Wagner helped me get this version with nice defaulting using type equality annotations from the TypeFamilies extension:

class Hist st a c  where
     runHist :: st c -> (c -> a)
instance a ~ b => Hist Top a b where
     runHist _ = id
instance (Hist st a b) => Hist ((:>) st b) a c where
     runHist (Snoc st' cb) = runHist st' . cb

We provide two functions to “move down” through a type, for partial lenses (used for multiconstructor types) and safe pure lenses:

move :: (Monad m)=> LensM m b c -> Zipper st b -> m (Zipper (st :> b) c)
move l (Zipper st a) = 
    liftM (uncurry $ Zipper . Snoc st . fmap runIdentity) (runLens l a)

moveP :: (b :-> c) -> Zipper st b -> Zipper (st :> b) c
moveP l = runIdentity . move l

And finally a move upward is just runs the stored continuation on the focus:

moveUp :: Zipper (st :> b) c -> Zipper st b
moveUp (Zipper (Snoc st cont) c) = Zipper st $ cont c

I’ve finished a simulation-visualization of the very cool algorithm for generating a Maximal Independant Set from “A Biological Solution to a Fundamental Distributed Computing Problem” by Afek et al. (sorry I don’t have a link to the PDF, and respect you too much to link you to a paywall).

You can play with it or check out the code on GitHub; in particular, see “algorithm.js” for the didactic implementation of the algorithm.

It uses jQuery and Raphael.js for the visuals and events.

Goals for the project

1. create a fun visual simulation that can give a nice intuition for the algorithm

2. remain true to the algorithm as described in the paper, and to avoid anything novel or clever at this point

3. attempt to organize my code in such a way as to be a readable explanation of the algorithm as described in the paper, hiding or isolating implementation details

4. attempt to model the behavior of a real-world network of nodes using the OO abstraction, and (synchronous) events.

Trying to meet these demands was revealing. For one thing I was forced to break up the two message exchange steps into four discrete steps which must be performed synchronously across the network for things to work without race conditions.

Later

The pseudocode description is hiding some of the complexity and brittleness of the algorithm IMHO. I’d like to take it apart and try to rip out as many of the synchronous-network dependencies as I can, or explore how an identical but asynchronous system behaves: give all the nodes jittery clocks and without a coordinated start.

I recently needed to do some conversions/processing to a bunch of HTML files, which contained html canvas images, so I needed a way of converting all the canvas elements on the page to PNGs.

After a bit of research and tweaking, the following worked well enough for me:

Run it in your browser’s JS console on the page you want to process (we assume jQuery is already loaded on the page).

I just uploaded the first version of a lens library I’ve been working on, called yall. You can get it with a

cabal install yall

or check it out on github. There will be a Template Haskell library for automatically deriving lenses at some point in the future.

I was motivated primarily by the desire for a lens that is acceptable for pez (existing libs such as the excellent fclabels or data-lens didn’t fit the bill for assorted reasons), and to explore some abstractions and generalizations re lenses more deeply.

The result is fairly rough at this point, but I’m interested in feedback.

Distinguishing features

This is a bit of copy/paste from the docs I just wrote.

• Lenses are parameterized over two Monads (by convention m and w), and look like a -> m (b -> w a, b). this lets us define lenses for sum types, that perform validation, that do IO (e.g. persist data to disk), etc., etc.

• a module Data.Yall.Iso that complements Lens powerfully

• a rich set of category-level class instances (for now from categories) for Lens and Iso. These along with the pre-defined primitive lenses and combinators give an interface comparable to Arrow

Examples

And here is a little showcase of functionality. First, an illustration of partial lenses, appropriate for multi-constructor types.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

-- First, lenses for a sum type. This is something like what we'll generate
-- with template haskell.
data Test a = C1 { _testString :: String, _testA :: a }
            | C2 { _testString :: String, _testRec :: Test a }

-- pure lens, polymorphic in Monad for composability:
testString :: (Monad w, Monad m)=> Lens w m (Test a) String
testString = Lens $ \t-> return (\s-> return t{ _testString = s }, _testString t)

-- lenses that can fail. For now, use Maybe. In the TH library, I'll probably
-- generate lenses polymorphic in <http://hackage.haskell.org/package/failure>
testA :: LensM Maybe (Test a) a
testA = Lens f where
    f (C1 s a) = return (return . C1 s, a)
    f _ = Nothing

testRec :: LensM Maybe (Test a) (Test a)
testRec = Lens f where
    f (C2 s i) = return (return . C2 s, i)
    f _        = Nothing

-- conposing a pure and partial lens:
demo0 :: Maybe String
demo0 = getM (testString . testRec . testRec) (C2 "top" (C1 "lens will fail" True))

Now an example of a more creative use of monadic getter, allowing us to define a lens on the “Nth” element in a list, returning our results in the [] monad environment.

1
2
3
4
5
6
7
8
9
10

-- Here we have a lens with a getter in the list monad, defining a mutable view
-- on the Nth element of the list:
nth :: LensM [] [a] a
nth = Lens $ foldr nthGS []
    where nthGS n l = (return . (: map snd l), n) : map (prepend n) l
          prepend = first . fmap . liftM . (:)

-- This composes nicely. Set the Nth element of our list to 0:
demo1 :: [ [(Char,Int)] ]
demo1 = setM (sndL . nth) 0 [('a',1),('b',2),('c',3)]

Finally here’s a bit of a silly example illustrating a lens with Monadic setter (w) that does IO, in this case persisting a serialized version of the data we’re operating on to a text file.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

-- persist modifications to a type to a given file. An effect-ful identity lens.
persistL :: (Monad m) => FilePath -> Lens IO m String String
persistL nm = Lens $ \s-> return (\s'-> writeFile nm s' >> return s', s)

-- we'll use this one:
tmpFile = "/tmp/yall-test"
printFileContents = putStrLn . ("file contents: " ++) =<< readFile tmpFile

-- build a lens with some pre-defined Iso's that offers a [Int] view on a
-- string that looks like, e.g. "1 2 3 4 5":
unserializedL :: (Monad w, Monad m) => Lens w m String [Int]
unserializedL = isoL $ ifmap (inverseI showI) . wordsI

-- now add "persistence" effects to the above lens so everytime we do a "set"
-- we update the file "yall-test" to redlect the new type.
unserializedLP :: (Monad m) => Lens IO m String [Int]
unserializedLP = unserializedL . persistL tmpFile

demo2 :: IO ()
demo2 = do
    -- apply the lens setter to `mempty` for some Monoid ([Char] in this case)
    str <- setEmptyW unserializedLP [1..5]

    -- LOGGING: the string we got above (by setting [Int]) was written to a file:
    print str
    printFileContents

    str' <- modifyW unserializedLP (map (*2) . (6 :) . reverse) str

    -- LOGGING: now the file was modified to reflect the changed value:
    print str'
    printFileContents

Future

I still need to create TH deriving functionality for the package, and will announce when that happens. Been busy lately so I’m not sure when I’ll get to it, but let me know your questions/comments/concerns and I’ll try to address them promptly.