Dataflow execution of reactive programs

Printer-friendly version
Info
Prerequisites: 
  • A working knowledge of concurrency models is certainly plus but not a requirement
  • An interest in programming languages and their implementation
Context: 

There are two trends that can be perceived in the context of ubiquitous computing. First, devices are getting smaller and overloaded with various kinds of sensors. For example, current smartphones can be considered to be full-fledged computers with the addition of a wide variety of sensors (e.g. thermometer, pedometer, ...). Second, these devices almost always house multiple cores dedicated to processing (a typical smartphone has a 4-core processor).

In order to program these devices one has two overcome two major challenges: multicore programming (as a consequence of the numerous cores on these devices) and event-driven programming (as a result of the plethora of sensors). The former problem is traditionally solved by applying a concurrency model to deal with the parallelisation of code (e.g. locks, actors) . The latter is traditionally solved by using callback-based code (i.e. one installs a listener on a particular sensor to trigger a lambda as soon as the sensor has generated some data).

However, These callbacks have led to what is now known as the callback hell due to a number of impracticalities tied to these callbacks (e.g. callbacks do not compose and obfuscate programme control flow). In order to avoid this callback hell, reactive programming has been presented as a possible solution. In a nutshell, reactive programming allows one to declaratively specify data dependencies in programs while relying on the language runtime to update values accordingly. An example of a reactive programme could be the following: (define x (+ temperature seconds)) (for a real-world example of reactive programming consider the video showed above). The example specifies a dependency between the variable x and so-called signals temperature and seconds. Concretely, as soon as either temperature or seconds changes the addition will be re-evaluated and x will reflect the updated value.

Moreover, as the name implies an essential property of these reactive programs is their ability to react to externally produced events at a pace dictated by the outside world (e.g. a user typing on a keyboard). Given the multitude of cores on modern devices and the multitude of sensors it is thus important to fully exploit the devices potential in order to keep reactive applications running on these devices responsive.

The dataflow model of computation is an alternative to the currently dominant von Neumann model. In the dataflow model there is no global memory, and no forced sequential execution of code. Instead, an operation is executed when the data it depends on becomes available. This property allows a dataflow runtime environment to extract all of the available parallelism from a given input program. Moreover, the synchronization which is present in the dataflow model removes the need for a concurrency model.

Goal & Research Activities: 

Reactive programming has seen a wide variety of applications since it's conception in the world of functional animations (e.g. robotics, distributed systems). However, few to virtually no research has been conducted towards the efficient, parallel, implementation of reactive languages. The goal of this thesis would be to investigate the potential of the dataflow execution model as an implementation platform for reactive programming languages. The dataflow execution model shows similarity with the reactive programming paradigm (both view a program as a directed graph of autonomous nodes). However, using the model as a platform to implement reactive languages will require you to gain intimate knowledge of both the field of reactive programming as well as dataflow execution. After this, it will be your task to reconcile both models in order to end up with a performant, parallel dataflow runtime for reactive programs.

Concretely we foresee the following steps as a high-level roadmap:

  • A literature study on reactive programming
  • A literature study on different dataflow execution models
  • The design of a modified dataflow execution engine for reactive programs
  • The adaptation of an existing reactive programming language to run on top of your execution engine
  • An extensive benchmark study showcasing the advantage of your engine compared to ad-hoc reactive language implementations
References: 
  • Bainomugisha, E., Carreton, A. L., Van Cutsem, T., Mostinckx, S., & De Meuter, W. (2012). A survey on reactive programming. In ACM Computing Surveys.
  • Czaplicki, E., & Chong, S. (2013, June). Asynchronous functional reactive programming for GUIs. In ACM SIGPLAN Notices (Vol. 48, No. 6, pp. 411-422). ACM.
  • Johnston, W. M., Hanna, J. R. P., & Millar, R. J. (2004). Advances in Dataflow Programming Languages. In ACM Computing Surveys.
  • Veen, A. H. (1986). Dataflow Machine Architecture. In ACM Computing Surveys.