Denotational semantics for Sodium

I’ve written a denotational semantics document for Sodium which constitutes the formal definition. Here you’ll find a PDF file and some code:

When I’ve finished the book manuscript I’ll do some work on bringing everything up-to-date, as there have been some changes to the code. The Java version is currently the most up-to-date version and will act as reference for the updates to the other versions. Have fun!

Five things I want to do to Sodium

I’m busy writing my FRP book, but when I have some time again, there are FIVE issues that I want to address in Sodium:

  • [Already done in the Java version.] Get rid of the sampleNow infrastructure and replace it with something much simpler. The way it was done was problematic, and we only actually need something very simple.
  • Finish the renaming of Behavior -> Cell and Event -> Stream. This was urged by the publisher because of utterly different OOP meanings that ‘behavior’ and ‘event’ have.
  • We need to be able to say (Java syntax):
    LazyValue<Integer> x = bx.sampleLazy();
    LazyValue<Integer> newX = => x_ + 1);
    // Also applicative lift operations
    Cell<Integer> by = ey.holdLazy(newX);

    This gives us the complete ability to use sample() with looped values where the loop hasn’t been closed yet.

  • [EDIT: I probably won't do this. See below.] I would like to make it possible to have a Cell type that has no updates() or value() method, so we can make it so changes in Cells are not observable. This makes it possible to simulate continuous time without any possibility of leaks in the abstraction. Here’s what I’m thinking:
    • Make it so hold() returns a subclass of Cell, called StreamCell.
    • updates() and value() are defined on StreamCell only.
    • We’ll also need StreamCellSink and StreamCellLoop, liftSC and mapSC methods.
    • Is there a better name?

    Then we get the best of both worlds: Semantic purity and convenience.

  • I want to make a multi-language test case system, so that each test case is written in each language next to each other so they are easy to maintain. Run it and you’ll get a big table of language vs. test case, with a tick/cross in each square. It should be possible to use it on systems with only some of the languages installed.

If I can make these changes, then I’ll be happy that Sodium is finished. Then people can write code on a solid foundation, and in parallel people can work on performance and parallelism. We should always keep the reference implementations in each language separate from the performance/parallel implementations. Then it’s possible to easily test whether bugs are in the performance/parallel Sodium or in the application.

EDIT: updates() is needed in certain practical circumstances for normal work in non-lazy languages. An example of this is the Zombicus example described in chapter 7 of the book. The problem is that without doing this, others is a hard cyclic reference during start-up and this breaks it. StreamCell complicates the interface somewhat. Is it worth it for the benefit (waterproof continuous cells/behaviors)? I am trying to “sell” Sodium on the simplicity and practicality of its interface. I’d appreciate your thoughts.


Announcing: Book “Functional Reactive Programming” from Manning Publications

coverAnnouncing Functional Reactive Programming the book by Stephen Blackheath and Anthony Jones from Manning Publications

The book is in production and the first six chapters are now available through MEAP (Manning Early Access Program). The first chapter is free. The book will be Deal of the Day May 19th. 50% off with code dotd051915au

We’ve dealt with event handling frustrations over the years, and this led us to FRP and to writing Sodium. We think FRP is a game changer for user interfaces, video games, control applications and anywhere else an event-based programming model is found. So we decided to write a book that brings FRP to the coalface for a general programming audience. Underlying functional programming concepts are introduced along the way. We show you how to think in FRP using a range of FRP systems and languages.

Announcing: Scala implementation of Sodium

The Sodium team is delighted to announce that Mark H. Butler has ported Sodium to Scala! Thank you so much, Mark.

def testAccum() {
  val ea = new StreamSink[Int]()
  val out = new ArrayList[Int]()
  val sum = ea.accum[Int](100, (a, s) => a + s)
  val l = sum.updates().listen(out.add(_))
  List(5, 7, 1, 2, 3).foreach(ea.send(_))
  assertEquals(Arrays.asList(105, 112, 113, 115, 118), out)

Announcing: C# implementation of Sodium

The Sodium Project is proud to announce a C# implementation of Sodium, by Michael Lund. C# has been on our wish list for a long time, so thank you Michael for your hard work!

    public void TestAccum()
      var ea = new EventSink<Integer>();
      var @out = new List<Integer>();
      Behavior<Integer> sum = ea.Accum<Integer>(100, (a, s) => a + s);
      Listener l = sum.Value().Listen(x => { @out.Add(x); });
      CollectionAssert.AreEqual(new[] { 100, 105, 112, 113, 115, 118 }, @out.Select(x => (int)x));

Should ‘sample’ exist? Should ‘updates’ exist?

I posted this in response to a bug report: My musings about the philosophy behind ‘sample’ and ‘updates’.

Yes – execute + sample should be equivalent to snapshot. I have wrestled with the question of whether I should have done sample, and Anthony has questioned me on it, because in most cases you should use snapshot instead. I think it is correct that I have done it, though, for three reasons:

  1. collect can’t be defined without it (see below). Collect is a little strange, because it treats a behavior as an event. This is a different philosophical question – whether ‘updates’ and ‘value’ should exist, but I have decided that the usefulness of it outweighs the loss of FRP purity. It violates the principle that changes in behaviors should not be observable. I think Heinrich Apfelmus of Reactive Banana disagrees with ‘updates’ for this reason. If you are concerned about FRP purity, it is possible to scan the code to search for uses of ‘updates’. Some systems solve this with three types, Event, Behavior and a sort of Bevent where changes are observable, but the type awkwardness of this could be severe. One use case of ‘updates’ springs to mind: An animation clock as a Behavior of Double. It’s useful to treat it as a behavior and to use ‘updates’ to allow you to generate alarms from it. So in Sodium I have decided that FRP is hard enough as it is and we need all the help we can get for practical work, so this is a compromise, yes, but it seems tolerable to me. ‘value’ in Sodium – which is a bit magical in the way it works – seems to me to be so useful (especially in combination with switch) that it justifies all this agony. So, I am 98% happy with it.
  2. It seems reasonable to me that you should be able to poll a behavior with sample from your imperative code, asking for its current value.
  3. sample runs within a transactional context, so there is nothing actually directly wrong with it that I can see.
-- | Transform a behavior with a generalized state loop (a mealy machine). The function
-- is passed the input and the old state and returns the new state and output value.
collect :: Context r => (a -> s -> (b, s)) -> s -> Behavior r a -> Reactive r (Behavior r b)
collect f zs bea = do
    let ea = coalesce (flip const) (updates bea)
    za <- sample bea
    let (zb, zs') = f za zs
        bs <- hold (zb, zs') ebs
        let ebs = snapshot f ea (snd <$> bs)
    return (fst <$> bs)

There is one practical problem with sample in strict languages. Sample won’t work too well with a value that has been looped but not defined yet. With Haskell it’s fine because the za value doesn’t get evaluated until the end of the ‘sync’ transaction.

Perhaps the solution in strict languages is to throw an exception and tell the user to be careful about this case. This is a compromise that I’m not entirely happy with.

Sodium and GHCJS

geraldus has written a tutorial about his experiences with Sodium and GHCJS, the Haskell to Javascript compiler for writing client-side web apps in Haskell. With the new GHC release, GHCJS should get much easier to install very soon.

  • how to use Sodium’s merge and switch primitives;
  • how to listen “external” javascript events using GHCJS;
  • how to combine GHCJS and Sodium to create function reactive ui in browser.

Here’s the link… Tutorial. GHCJS and Sodium.

Programming reactively with both barrels

Over the last couple of months I’ve written 1,632 lines of purely reactive code in Sodium on the Times Tables Race Game for iOS using the GHC Haskell to iOS cross compiler. I know enough to express myself in the paradigm, and I know from experience that Sodium is not wanting in expressive power. (I have not had to “cheat” and do any part of the logic in an imperative/observer pattern style.) But this is the biggest chunk of reactive programming I have ever done in anger. It’s only really been possible to get stuck in now that I no longer have to develop Sodium at the same time.

If you are new to reactive programming as almost everyone is, there is a shift in understanding that’s required to think reactively. The following are the experiences of someone who has already gone through that and is now getting down to some real work.


(Note that you can load your own photos as backgrounds to the game!)

One thing I’ve found is that functions tend to have a lot of arguments and return values, typically 6 -> 3 for a checkBox widget and 9 -> 6 for a whole page (the settings page). This is mainly because reactive programming requires all inputs and outputs to be declared explicitly. There is a lot of scope for this to be abstracted away into such concepts as Widget, but in this simple game I have not done this.

The long argument lists have been a bit crufty at times, but we are in the early days of reactive programming. I expect the solutions to these niggles to become clearer in time.

I’ve found refactoring to be a dream, as with all functional programming. For example, having written the one player game, in the two-player game I needed to introduce a countdown 3.. 2.. 1.. between rounds. The eNextQuestion event was looping round and being fed back in to give the start of the next question. To add the countdown, all I needed to do was to pass the value out of the bottom of the function and eStartOfQuestion back in the top, so the looping of this value is done by the caller. Easy.

While the code can be a little long-winded if written directly in reactive primitives, the potential for abstraction is high, and it’s been easy to factor out common patterns and reuse code.

Factoring out these common patterns turns out to be quite important for keeping the code tidy. It can turn into spaghetti if the functions get too long. In fact, reactive programming is almost like designing a circuit, so it really is like spaghetti. Like the proverbial sea sponge in the blender, there is no order dependency whatsoever between lines of code. You could take any reactive function, and re-order the lines randomly and it would work exactly the same.

But when the code gets a bit spaghetti-like, it’s generally easy to fix. A lot of the refactoring has amounted to not much more than cut & paste. You can refactor with abandon, since the compiler is fussy it catches most mistakes, and the risk of breakage is very low.

The abstractions are often very neat, for example this code gives a value that increases over time from 0 to 1 triggered by a start event, as a building block for animating fades:

-- | Returns the fraction of the blend if it's running, and the
-- end-of-blend event.
blend :: Double     -- ^ Duration of blend
      -> Event ()   -- ^ Event to initiate the blend
      -> Behavior Double  -- ^ Clock
      -> Reactive (Behavior (Maybe Float), Event ())
blend duration eInitiate time = do
        blendStart <- hold Nothing $
                snapshotWith (\() t -> Just t) eInitiate time `merge`
                fmap (const Nothing) eEnd

        let eEnd = filterJust $ snapshotWith (\t mT0 ->
                case mT0 of
                    Just t0 | t - t0 >= duration -> Just ()
                    _                            -> Nothing)
              (changes time) blendStart

    let blend = liftA2 (\mT0 t -> case mT0 of
            Just t0 -> Just (realToFrac $ min 1 $ (t - t0) / duration)
            Nothing -> Nothing) blendStart time
    return (blend, eEnd)

“rec” declares a recursive block. All that does is allow for forward references (eEnd is referenced in the first statement), thus making loops possible.

The compiler catches most errors, and I’ve found the logic is easy to reason about. So much so, that things have tended to “just work” to a surprising extent. Interactions between different things in the logic tend to be more predictable, because the rules they follow are well-defined. For instance, if an event switches one thing off (e.g. a fade out) and another thing on (a fade in), then when combining the two later, you never have to worry that in some context there might be a detectable gap between them, because that is impossible.

Debugging has been easy enough with the occasional need to add trace messages to see what certain values are at runtime.

I’ve been very pleased with performance, which I was a little concerned about. Mobile phone processors are not fast compared to what we’re used to with PCs.

It’s been a long time since I would have attempted something like this in an imperative/observer pattern style, so it’s difficult for me to compare how long things take. Certainly there have been some areas that I breezed through that were complex enough that have given me fair anxiety in an imperative/observer context, such as all the complexities of image loading, evicting unused images from memory, and OpenGL generally. (These aspects were technically outside the reactive logic but ultimately controlled and shaped by it.)

Ultimately the goal of reactive programming is to deal with complexity on a very large scale. I believe that reactive programming does this, but it’s not until I’ve written 16,320 or 163,200 lines when that will prove itself, but my intuition is that it will.

Times tables and memory management

Since I finished my work on the GHC-iOS cross-compiler (which allows you to write apps for Apple iOS in Haskell), I’ve been working on a Times Tables game with a friend:

tables-2-small tables-3-small

I can’t show you the code, because we’re keeping it proprietary, but when we’ve finished, you can look for it on iOS and Android. My times tables have improved dramatically, and yours can too!

The game logic is implemented in Sodium (of course) in Haskell as a function from a touch events to a list of sprites to draw. The switch primitive is used when switching between screens.

This is the most complex logic I’ve done in Sodium and it brought up an interesting memory management bug. Memory management is one of a long list of tricky challenges in implementing reactive programming systems. If anyone tells you they implemented a reactive system and it was easy, they’re lying to you. The core of Sodium is only 862 lines long, but it has literally taken me years (not full time) to understand all the intricacies and get it right.

Here’s what the bug was [a bit technical]: The output of each reactive primitive must keep the last one alive. I previously achieved this by embedding…

touch listen

…in the callback processing [remember Sodium uses the observer pattern under the covers]. touch uses Control.Exception.evaluate to hold a reference to the listen (the observer mechanics) of the parent. Because I am using finalizers to do the cleanup, the reference was held until the finalizer runs. Normally garbage collection will happily clean up object networks that contain cycles, but under this method it breaks: the presence of a cycle caused the whole cycle to stay alive. So when you switched between screens in the game, some of the reactive primitives were not cleaned out of memory properly.

The solution (fixed in Sodium was to replace this mechanism with normal Haskell references, so the garbage collector would work as expected. The following is a simple wrapper type that throws away the type information of the contained value:

newtype Dep = Dep Any

dep :: a -> Dep
dep = Dep . unsafeCoerce

If any of these implementors of reactive systems tell you their code is nice and beautiful, don’t believe that either. Reactive systems may be beautiful on the outside (which is actually the whole point of them), but there is some serious ugliness hidden underneath. See how much suffering we are saving you from?

Dep allows us keep a reference to any type of value. We never retrieve the value – it’s only used to keep something alive (so it doesn’t get garbage collected). Then we just stuff the reference into a field of Event, like this:

data Event Plain a = Event {
         getListenRaw :: Reactive (Listen a),
         evCacheRef   :: IORef (Maybe (Listen a)),
         eDep         :: Dep

and, for example with filterJust, we simply construct the Event with a reference to the input event:

-- | Unwrap Just values, and discard event occurrences with Nothing values.
filterJust :: Event (Maybe a) -> Event a
filterJust ema = Event gl cacheRef (dep ema)
    cacheRef = unsafeNewIORef Nothing ema
    gl = do
        (l, push, nodeRef) <- ioReactive newEventImpl
        unlistener <- later $ linkedListen ema (Just nodeRef) False $ \ma -> case ma of
            Just a -> push a
            Nothing -> return ()
        addCleanup_Listen unlistener l

If this is all done perfectly, then the test cases pass, the Tables game works, and no memory leaks occur.