TP

The Duality of Object and Event references

Mathematical duality [2] is a very useful and elegant concept that gives us a nice way of speaking about objects or structures that behave in some way exactly conversely. There is no clear definition of what duality is. However, the idea is that when we have two structures that behave conversely and we know that something is true about the first one, then we get the opposite statement about the other structure "for free" (if you know how to translate from one structure to the other).

In this article, I'll talk about an interesting example of duality that (to my best knowledge) wasn't described by anyone before. The two dual structures are references between objects in a normal program and references between events in a reactive application. The statement that is going to become obvious thanks to the duality principle is describing which of the objects (or events) are garbage and can be safely collected by garbage collector.

This topic is in much more details discussed in a paper [4] I wrote with Don Syme and that I presented at the ISMM Workshop (see also my trip report from PLDI). In this article, I'll try to give an accessible description of the most interesting idea from the paper...

Introduction

This concept of duality is quite useful in programming. In functional programming, the product type (usually called tuple or record) is dual of sum type (called discriminated union in F#). Let me demonstrate this using a simple example. Here are two simple type declarations:

// Color with R, G, B components   // Shape can be one of three types
type Color =                       type Shape = 
  { Red : int                        | Square of Point * int
    Green : int                      | Circle of Point * int
    Blue : int }                     | Triangle of Point * Point * Point

What is dual about these two types? When you have a record type consisting of three values (such as Color), you get three functions for extracting individual values from the record (reading Red, Green and Blue component). On the other hand, when you have a discriminated union type, you get three functions for constructing Shape from the three possible cases (creating a shape representing Square, Circle and Triangle). When we draw this idea using a simple diagram, you can easily see what the duality means:

The two diagrams are essentially the same, with the only difference that the arrows in the diagrams are reversed! In fact, most of the dualities usually mean just this - when you find some nice way of drawing the concept as a diagram with arrows, the dual concept looks exactly the same, just with the arrows reversed.

Other interesting examples of duality in the programming languages world are for example the duality between IEnumerable (representing pull-based sequence of values) and IObservable (representing push-based sequence of values) in .NET, which has been nicely described by Erik Meijer [1]. There are also some nice arrows involving IObservable in an article by Matthew Podwysocki [3]. The next example is covariance and contravariance of generic types, which is now available in C# 4.0. If you're wondering what arrows would be reversed in this case, you would change the orientation of arrows representing the inheritance, but I'll write about this in some future article.

Now, let's look at the duality between object references and event references that I wanted to talk about in this article. I'll first describe the two (idealized) dual world - the World of Objects and the World of Events and then we'll look what does that tell us about garbage collection...

World of Objects

Let's start by looking at references between objects in the usual environment. The diagram on the right gives an example - we have a root object called program that references two other objects (product and customer). The diagram also shows an object order which references product, but isn't referenced from any other object (we'll see that it can be garbage collected later).

There are two important facts about the World of Objects:

These two points describe essential information that is important for specifying what is a garbage. We don't want to dispose of any object that can do something useful. In this scenario, this means that we cannot collect roots (because they can be called from an external caller) and we cannot collect any object that is reachable from the roots (because the control flow may be transferred to it while the application is running). This leads to the usual definition of what is garbage in this environment:

As we'll see shortly, we can translate all of the points that I highlighted with bullets to the World of Events. We just need to write a few things in exactly the opposite way. However, first I should talk a little bit about what I mean by the World of Events...

World of Events

When talking about events, you can imagine events as they are used in .NET and first-class events in F# [5] (see also my earlier article about them). In general, an event is something that can emit a value at any time. You can create derived events that listen to some other events and emit the value that they receive only when it matches some predicate or for example emit a value that is calculated based on the original value. Let's demonstrate the idea using a simple snippet that uses first-class events in F#:

// Creates an event that emits a value whenever one of 
// the two events (MouseDown of btnOne or btnTwo) emit 
let anyButton = 
  Event.merge btnOne.MouseDown btnTwo.MouseDown

// Creates an event that emits a string "click!"
// whenever user clicks on any button with left-click
let anyLeft = anyButton 
  |> Event.filter (fun e -> 
    e.Button = MouseButtons.Left)
  |> Event.map (fun _ -> "click!")

These two examples are pretty simple, but they should illustrate the point. You can write pretty complicated event processing code just by creating and composing events. So, let's now imagine that we have an environment that contains only events. What would this kind of world look like?

The diagram on the right shows a simple scenario from the World of Events. Let's start from the click event. When it emits a value, the value will be forwarded to the right click event (which emits the value only when it was caused by right mouse button). The value is also forwarded to an event called handler - we'll talk about this event shortly. The next branch contains key press event which also sends values to handler.

The handler event is a special event that can also have observable effects. When it receives a value from other events (or from the "outside"), it can for example modify something in the user interface or print to the console. In the terminology used in .NET, those events actually represent event handlers that can be attached to events, but we can easily model them as special types of events.

Let's summarize the interesting aspects of the World of Events (you may want to compare the points with those that I wrote about the World of Objects):

Just like when discussing the World of Objects, these two points tell us which of the events are garbage. In general, we can dispose of any events that cannot cause an observable action. An observable action can be caused only by special leaf events (drawn in the green color). However, these events can be triggered by other events that have a reference to them (e.g. in the above example, the event click can trigger the event handler). Now, we can easily define what is a garbage when it comes to events:

These definitions are dual to the two points that we've seen earlier when discussing the World of Objects. In the next section, we'll compare the two in more detail and I'll explain the duality between them.

Garbage Collection and Duality

As I wrote in the introduction, duality usually means that two structures are the same, with the only difference that some arrows are reversed. This is exactly the case of garbage in the World of Objects and World of Events. In both of the cases, we draw objects (or events) as nodes and references as oriented links between them. When we want to find objects (or events) that are garbage, we need to check the following:

I highlighted the words from and to, so that you can easily see that they are swapped. Let's now look at the two diagrams that I used earlier in the discussion. The following version also shows which of the objects (events) are garbage and can be safely collected:

In this case, the duality between the two structures tells us how to implement garbage collection for the idealized World of Events. Instead of looking for objects that are not referenced from roots, we need to look for the dual of this description - events that do not reference any leaves.

We can also use duality in a different way. Let's say that we already have a standard garbage collection algorithm for objects and some graph of references between events. Now, we can collect events that are garbage using the algorithm for garbage collection in the non-reversed scenario. We just need to reverse all the links in the graph and then run the garbage collection algorithm for objects. The nodes that will be marked as garbage will be those that are garbage when talking about events. You can look at the two above diagrams and easily see that this trick would work!

Summary

The main point of this article was to demonstrate an elegant concept of duality that comes from mathematics and to show that it can be used when thinking about garbage collection in two dual worlds - the World of Objects and an idealized World of Events. If you want to read more about this topic, you can also read our paper [4], which also describes why this is an important problem when it comes to first-class events in F# and how to integrate the two worlds - if you wanted to model for example .NET application which contains both objects and events.

How can the ideas from this article be useful in practice? First of all, duality gives us a nice way of understanding the problem. When we know that something works in case of object references, we can easily find something that works for event references (just by replacing from with to and the other way round in the description). However, to take the idea further, I believe that a framework for reactive programming based on events could use the dual garbage collection described in this article to collect unused events...

References 

Published: Monday, 19 July 2010, 4:58 PM
Author: Tomas Petricek
Typos: Send me a pull request!
Tags: academic, research