"A Synchronous Reactive Language based on Implicit Invocation"

We have moved!

The new address is:
http://thesynchronousblog.wordpress.com/

---

Observados os dispositivos do art. 6º da DELIBERAÇÃO 001/76, será defendida no dia 16/03/2009 às 10:00h, no local RDC511, a DISSERTAÇÃO DE MESTRADO intitulada ""A Synchronous Reactive Language based on Implicit Invocation"" do(a) aluno(a) Francisco Figueiredo Goytacaz Sant'Anna candidato ao título de Mestre em Informática.

Abstract:
The reactive programming paradigm covers a wide range of applications, such as games and multimedia systems.
Mainstream languages neglect reactive programming, lacking language-level
primitives that focus on synchronism and interactions within application parts.

We propose a new reactive synchronous language, with an imperative style, whose primitives are based on unconventional implicit invocation mechanisms.
With this work, we intend to unite the essential features of reactive languages while keeping a convenient imperative style of programming.
A reactive scheduler is responsible for executing reactors, our processing
units, based on dependency relations between them built dynamically.
Our language provides dataflow programming, sequential imperative execution, and deterministic use of shared-memory.

We have moved!

The new address is:
http://thesynchronousblog.wordpress.com/

Featuring: More video demonstrations.

About Determinism

Current approaches for concurrent systems, such as multi-threading and message-passing are inherently non-deterministic, leading to unpredicted execution.

In multi-threaded systems wherein memory is shared among threads, even if critical sections of code are protected, one is still subject to bugs due to non-determinism.

Suppose one writes the following code:

thread1 {
    ...     // do some processing
    lock {
        a = a + 2
    }
}

thread2 {
    ...     // do some processing
    lock {
        a = a * 2
    }
}

a = 1
start(thread1)
start(thread2)
wait(thread1, thread2)
print(a)

Depending on which thread assigns to `a` first, the value printed might be 6 or 4.
Moreover, each time the program is executed, the other result may be printed, as thread scheduling isn't deterministic either.

By using message-passing concurrency, non-determinism is also an issue.
In the code below, the value 6 or 4 might also be printed.

cspA {
    ...     // do some processing
    send(C, 4)
}
cspB {
    ...     // do some processing
    send(C, 6)
}
cspC {
    ...     // do long processing
    a = receive()
    a = receive()
    print(a)
}


The characteristic that makes such systems non-deterministic is that each command in the language takes an unbounded time to execute.
As each thread or process run in asynchrony with each other, we (or the compiler) can't predict where each thread will be at anytime, being impossible to detect simultaneous accesses to system resources.

---

Synchronous Concurrency, in the other hand, is deterministic.
Each command is conceptually instantaneous or takes exactly the time it says so.

For instance, in LuaGravity all commands but AWAIT are instantaneous:

_a = _a + 2           -- instantaneous
SPAWN(reaction)       -- instantaneous
AWAIT(reaction)       -- waits for `reaction` to finish
AWAIT(2)              -- waits 2 seconds


In the code below, we can predict simultaneous access to _a that would lead to non-deterministic behavior, and raise an error.

SPAWN(function()
    _a = _a + 2       -- line 2: simultaneous access to `_a` with line 8
end)
SPAWN(function()
    AWAIT(keyboard.press)
    _a = 10           -- deterministic access to `_a`
end)
_a = _a * 2           -- line 8: simultaneous access to `_a` with line 2

The execution of this program yields an error when the second simultaneous access to _a happens.
The prediction of simultaneous access could be even static, raising a compile-time error.

The Dinning Philosophers Problem

Ok, here's the classical synchronization problem.
I'll jump the description of the problem, as you probably remember it from your operating system class [1].
A common solution involves mutual exclusion to lock access to shared forks.
Besides deadlock, the solution should avoid starvation and livelock as well.

The result can be seen in the video below:

The solution in LuaGravity uses its AWAIT primitive.
The AWAIT command puts the running reaction (method) to sleep until one of its parameters happens (other reactions or a timeout).
It's like a LINK, but it is created in the middle of a reaction and is broken when triggered for the first time.
This primitive brings Esterel capabilities to LuaGravity, that is, imperative reactivity.

Here's a possible solution for the problem:

Phil = Class('phil', function ()
 function init (self, left, right)
     ...  -- initialization code omitted
 end
 function run (self)
     local left, right = self._left, self._right
     while true
     do
         -- think
         self.state = 'thinking'
         AWAIT(math.random(5))
         -- wait
         self.state = 'hungry!'
         while not (left.get(self) and right.get(self)) do
             AWAIT(0) -- controversial delay
             left.put(self)
             right.put(self)
             AWAIT(left.put, right.put)
         end
         -- eat
         self.state  = 'eating'
         self.total = self.total() + 1
         AWAIT(math.random(5))
         -- back to think
         left.put(self)
         right.put(self)
     end
  end
end)
local fork = {}
for i=1, 5 do
 fork[i] = Fork()  -- Fork definition omitted
end
local phil = {}
phil[1] = Phil(1, fork[1], fork[2])
phil[2] = Phil(2, fork[2], fork[3])
phil[3] = Phil(3, fork[3], fork[4])
phil[4] = Phil(4, fork[4], fork[5])
phil[5] = Phil(5, fork[5], fork[1])
for i=1, 5 do
  phil[i].s_run()
end

The important function is run, in the philosopher class.
It's a loop in which the philosopher thinks, waits for the forks and eats.
The think and eat steps are just an AWAIT on a random time between 1 and 5 seconds.

In the inner while, the philosopher first tries to get both forks.
If he succeeds, the loop is finished, otherwise the forks (the one he got) are put back in the table.
Then, he waits for any of his forks to be released by his neighbors to repeat the process.
The statement AWAIT(0) is used to avoid a cycle in a call to fork.put(), I'll dig into it anytime.

Just by changing the variables self.state and self.total is enough to update the screen - it's all about reactivity.

[1] http://en.wikipedia.org/wiki/Dining_philosophers_problem

Imperative Reactivity

The LINK primitive was already presented in this post.
LINK makes the use of event-driven paradigm easier, avoiding all the bureaucracy of events definition, posting and handling: they are all done implicitly.
However, in another post we pointed out three issues in this paradigm: inversion of control, multi-core processors and listener life cycle.

This post deals with the first and more annoying limitation of event-driven programming: inversion of control.
Event-driven programming demands that its callbacks execute very fast as the event handling is serialized: while one event is being handled, others are not - only one callback executes at a time.
Callbacks are, therefore, logically instantaneous and can't hold state. They commonly receive state (those void* parameters), decode it (to work like a state machine and know where it was left), update it and return.
The sequential execution paradigm is broken here, as control is now guided by the event queue (the environment).

LuaGravity supports reactivity inside its methods in some way like Esterel does.
The AWAIT primitive suspends the execution of a method and waits for another method (or timer) to happen.
For example, AWAIT(keyboard.ENTER.press) suspends the running method until ENTER is pressed.
AWAIT is like a LINK, but is broken when its condition happens and resumes (instead of calling) the suspended method.

A little bit confusing, huh?
Hope the following example helps.
Let's say we want an animation to change its direction following the sequence RIGHT, DOWN, LEFT and UP when the respective keys are pressed.
Without using the AWAIT primitive, we need to hold state between successive executions of animation.changeDirection.
With the use of AWAIT, we code the animation sequentially.

-- WITHOUT AWAIT LINK(RIGHT.press, animation.changeDirection) LINK(DOWN.press, animation.changeDirection) LINK(LEFT.press, animation.changeDirection) LINK(UP.press, animation.changeDirection) function animation.changeDirection (key) if (obj.state == 'right') and (key == 'DOWN') then obj.state = 'down' obj.x = obj.x() -- stay here obj.y = obj.y() + S(obj.speed) -- move down elseif (obj.state == 'down') and (key == 'LEFT') then obj.state = 'left' obj.x = obj.x() - S(obj.speed) -- move left obj.y = obj.y() -- stay here elseif (obj.state == 'left') and (key == 'UP') then obj.state = 'up' obj.x = obj.x() -- stay here obj.y = obj.y() - S(obj.speed) -- move up elseif (obj.state == 'up') and (key == 'RIGHT') then obj.state = 'right' obj.x = obj.x() + S(obj.speed) -- move right obj.y = obj.y() -- stay here end end

-- WITH AWAIT while true do AWAIT(RIGHT.press) obj.x = obj.x() + S(obj.speed) -- move right obj.y = obj.y() -- stay here AWAIT(DOWN.press) obj.x = obj.x() -- stay here obj.y = obj.y() + S(obj.speed) -- move down AWAIT(LEFT.press) obj.x = obj.x() - S(obj.speed) -- move left obj.y = obj.y() -- stay here AWAIT(UP.press) obj.x = obj.x() -- stay here obj.y = obj.y() - S(obj.speed) -- move up end

In the code above, obj.x() takes its current position, and S(obj.speed) animates the objects (position = integral of speed).
Much cleaner with AWAIT, isn't?
See the result in the video below:

Esterel: A Unique Language

Esterel was developed in the early '80s in France in parallel with other two languages, Lustre and Signal. These, together with Statecharts, are considered the first synchronous languages.
Esterel found its niche in control intensive real-time applications and evolves as a standard, with several implementations.

Unlike all early and also recent synchronous languages, Esterel is the only one to provide an imperative style of programming. This is kind of surprising for me considering the high popularity of imperative languages.
Why there's no attempts to create new languages based on the Esterel foundations?

I cannot argue about functional vs imperative style of programming, but I do feel more comfortable with the latter (most people do), and they will be around for the next years.
I like the Lua approach, which seems to favor imperative style but concisely support most functional features without bloat.

The example below, written in Esterel, implements the basic training for an athlete:

module Runner:
    input  Second, Morning, Step, Meter, Lap;
    output ...; % not used
    every Morning do
        abort
            loop
                abort RunSlowly when 15 Second;
                abort
                    every Step do
                        Jump || Breathe
                    end every
                when 100 Meter;
                FullSpeed
            each Lap
        when 2 Lap
    end every
end module

This imperative style is almost a software specification given as a recipe in natural English.

The communication in Esterel is made through broadcast input and output signals.
The synchronous preemption structures (every do, loop each, abort when, etc) are the heart of the language.
LuaGravity provides constructs based on them, which I consider even more useful than the functional facilities.

Multimedia (Digital TV) Languages

I'm currently working at the Telemídia Laboratory [1], which is responsible for the development of the middleware Ginga [2] for the Brazilian Standard for Digital TV (SBTVD).

A DTV middleware is a common layer above specific platforms responsible for harmonizing them, providing an unified way to create interactive applications. For instance, the DTV middleware provides the languages in which interactive applications must be authored.
Most early digital TV standards around the world followed the Web standards and chose to use HTML + JavaScript + Java as their authoring languages for broadcasted interactive applications.

---

SMIL (Synchronized Multimedia Integration Language) [3] and NCL (Nested Context Language) [4] are XML based languages that supports multimedia synchronization.

Here's an application written in SMIL:

<smil>
<body>
  <par>
      <video src="goals.mpg"/>
      <img src="pele.jpg" begin="10s" end="15s"/>
      <img src="zico.jpg" begin="30s" end="40s"/>
  </par>
</body>
</smil>

Now, the same application in NCL:

<ncl>
<body>
  <media id="videoGoals" src="goals.mpg">
      <area id="aPele" begin="10s" end="15s"/>
      <area id="aZico" begin="30s" end="40s"/>
  </media>
  <media id="imgPele" src="pele.jpg"/>
  <media id="imgZico" src="zico.jpg"/>
  <link xconnector="onBeginStart">
      <bind role="onBegin" component="videoGoals" interface="aPele"/>
      <bind role="start"   component="imgPele"/>
  </link>
  <link xconnector="onEndStop">
      <bind role="onEnd" component="videoGoals" interface="aPele"/>
      <bind role="stop"  component="imgPele"/>
  </link>
  <link xconnector="onBeginStart">
      <bind role="onBegin" component="videoGoals" interface="aZico"/>
      <bind role="start"   component="imgZico"/>
  </link>
  <link xconnector="onEndStop">
      <bind role="onEnd" component="videoGoals" interface="aZico"/>
      <bind role="stop"  component="imgZico"/>
  </link>
</body>
</ncl>

Look, NCL has a reactive behavior through its link primitive (which LuaGravity borrowed).
When the area "aPele" begins, the image "imgPele" is started and so on.

---

Well, there's much more to tell about them as well as how much they differ.
You can look at the references below if it is the case.

Both are designed to synchronize timed medias like audio and video.
HTML, on the other hand, was specified with text and image in mind and doesn't seem to be a clever option for TV applications.

Probably the biggest difference among SMIL and NCL, as seen in the above examples, is that SMIL does not separate the definitions for media content and synchronism, while NCL does.

Very simple applications are usually straightforward when written in SMIL (like the one above).
On the other hand, since reuse is one of NCL's main concerns, growing applications scale better with NCL than with its SMIL counterparts.

Both SMIL and NCL are XML based, keeping this tradition in the world of multimedia application authoring.

The middleware Ginga chose to use NCL with Lua as its scripting language.
SMIL is the W3C standard for describing multimedia presentations.

[1] http://www.telemidia.puc-rio.br/
[2] http://www.ginga.org.br/
[3] http://www.w3.org/AudioVideo/
[4] http://www.ncl.org.br/