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!

    [Test]
    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); });
      ea.Send(5);
      ea.Send(7);
      ea.Send(1);
      ea.Send(2);
      ea.Send(3);
      l.Unlisten();
      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
    rec
        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.

tables-game

(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
    rec
        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-1-small
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 0.6.0.2) 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)
  where
    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.

C++ implementation of Sodium is complete

Announcing the basic completion of the C++ implementation of the Sodium reactive programming library! You can start using it in your C++ programs right away, though your compiler must support the C++11 standard. It will receive some polishing over the coming weeks. The list of Sodium languages is now Java, Haskell and C++.

void test_sodium::gate1()
{
    event_sink<char> ec;
    behavior_sink<bool> pred(true);
    std::shared_ptr<string> out(new string);
    auto unlisten = ec.gate(pred).listen([out] (const char& c) { *out += c; });
    ec.send('H');
    pred.send(false);
    ec.send('O');
    pred.send(true);
    ec.send('I');
    unlisten();
    CPPUNIT_ASSERT_EQUAL(string("HI"), *out);
}

Java example: Flight booking

A trivial example can never do justice to reactive programming’s awesome power to tame the complexity of the observer pattern. But who wants to read a complex example? So I hope this example strikes a happy balance.

Note we’re using the new lambda syntax, which hasn’t become standard Java yet (at time of writing). You can download a prototype compiler from Project Lambda. To build this example…

  1. Check out the Sodium git repo.
  2. Go into the ‘java’ directory and build Sodium.jar using ant. Point your classpath at it.
  3. javac FlightBooking.java (it’s under java/examples/)
  4. java FlightBooking

Here’s the logic that’s implemented:

  • You select return flight or one-way flight
  • If one-way, the second date entry is disabled
  • If the departure date is not before the return date, the “Book!” button is disabled

You can browse the complete example code here.

So let’s start by improving JButton slightly, to bring it into the wonderful world of reactive programming:

class Button extends JButton
{
    public Button(Behavior<Boolean> enabled, String text)
    {
        super(text);
        l = enabled.values().listen(e -> {
            setEnabled(e);
        });
        clicked = SwingHelpers.buttonClicked(this);
    }

    public Event<Unit> clicked;

    private Listener l;

    public void removeNotify() {
        l.unlisten();
        super.removeNotify();
    }
}

A behavior is taken as input, telling us whether to enable or disable the button. A behavior is a “time-varying value”. We connect reactive values to the “real world” simply by using the observer pattern you already know, but the lambda syntax may be new to you. The removeNotify() is necessary to automatically unregister the listener when the Button gets cleaned up.

When working with the Sodium reactive programming system, you use the observer pattern only at the edges, to interface with the “real world”. The guts of the implementation is done using the reactive paradigm, which lifts you into a more idealized world – or at least, that’s the idea. This example illustrates some purely reactive code, but not much.

The output of our reactified Button class is an event, which fires when the button is clicked. An event is a “stream of discrete event occurrences”. SwingHelpers.buttonClicked() does that job, and it looks like this:

    public static Event<Unit> buttonClicked(JButton button)
    {
        EventSink<Unit> clicked = new EventSink<Unit>();
        button.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                clicked.send(Unit.unit);
            }
        });
        return clicked;
    }

Here we’re constructing an event, and pushing button clicks into it as they occur. Unit is just an empty java class to represent “no value” for situations like this, where the button click event has no associated information other than the fact that it occurred. Unit is an idiom from functional programming.

Now we’ll make our return / one-way selection as a JComboBox. We can turn the currently selected value into a behavior like so:

        String[] ticketTypes = new String[] {"return flight", "one-way flight"};
        JComboBox<String> ticketType = new JComboBox<String>(ticketTypes);
        add(ticketType);

        // A boolean behavior indicating whether 'return flight' is currently selected.
        Behavior<Boolean> isReturn = SwingHelpers.comboValue(ticketType)
                       .map(ty -> ty.equals(ticketTypes[0]));

SwingHelpers.comboValue() returns a Behavior<String>, and we use the reactive ‘map’ idiom to transform it into a boolean.

I’ve written a reactified DateField in a similar vein to our Button: It takes a Behavior<Boolean> to select whether it’s enabled or not as input, and a gives Behavior<Date> with the currently-entered date as output.

Here’s how we make it enable the end date only when ‘return flight’ was selected:

        DateField end = new DateField(isReturn);

Nice and simple! The start date we want always selected, and we do that with a constant behavior:

        DateField start = new DateField(new Behavior<Boolean>(true));

Behaviors generally change over time, but constant behaviors are ones that choose not to.

Here is how we create the output value for our FlightBooking. The currently selected booking can be expressed as a behavior, thus:

        Behavior<Booking> booking = Behavior.lift(
            (isRet, st, en) -> isRet ? new Booking(st, en)
                                     : new Booking(st),
            isReturn, start.date, end.date);

We “lift” a ternary function (expressed using lamba syntax) into three behaviors – isReturn, state.date and end.date. The output of this is a single behavior. The output behavior always reflects the current state of its inputs. If it’s a return flight, we construct a Booking using the start and end dates. If it’s one-way, we use the start date only.

Here’s our form validation, enabling the “Book!” button only when the form is valid (departure date is before return date):

        Behavior<Boolean> valid = booking.map(b ->
            b.isOneWay() || b.start.compareTo(b.end) < 0
        );

        Button bookButton = new Button(valid, "Book!");

When the user clicks the “Book!” button, we want to take a snapshot of the value of ‘booking’ at that time. This is how we do it:

        booked = bookButton.clicked.snapshot(booking, (clicked, bking) -> bking);

‘clicked’ is of type Unit and contains no useful information. What we want is the booking details ‘bking’, and so that’s what we return from the lambda.

‘booked’ is an event of type Event<Booking>. Unlike the Event<Unit> we saw before, this event has a payload. It encapsulates the fact of the occurrence of the event (triggered by clicking on “Book!”), but for each occurrence, it also has the details of the booking.

And lastly, we output this event to the console so we can see what booking was selected. Hey – this isn’t a tutorial on writing GUI programs!

        FlightBooking booking = new FlightBooking();
        Listener l = booking.booked.listen(bk -> { System.out.println(bk); });
        booking.addWindowListener(new WindowAdapter() {
            public void windowClosing(WindowEvent e) {
                l.unlisten();
                System.exit(0);
            }
        });

Again it’s the observer pattern, but using lambda syntax. Observer pattern listeners have to be explicitly deregistered. Here I’m setting you a good example by doing that when the window is closed (even though it’s hardly necessary in this case).

Though it’s difficult to achieve in a small example, I hope this gave you some insight into the power of reactive programming. Here’s the complete example code again.

Reactive to Embedded C

I’ve been experimenting with an Embedded Domain-Specific Language (EDSL) in Haskell that generates C code from reactive source. The idea is to write code like this…

react $ \ea -> do
    eb <- mapE (`plus` constant (1 :: Int32)) ea
    listen eb "x" "{ printf(\"x=%d\\n\", x); }"

…and it’ll generate code like this…

void react1(int32_t __a)
{
    react2(__a + (int32_t) 1);
}
void react2(int32_t __b)
{
    int32_t x = __b;
    {
        printf("x=%d\n", x);
    }
}

The code’s here if you want to take a look.