Reactivity in LuaGravity

The reactivity in LuaGravity is achieved with implicit method invocation. So what?

Suppose we have the following class definition:

MyClass = class {
   function init (self, name)
       self._name = name
   end,
   function ping (self)
       print('ping', self._name)
   end,
   function pong (self)
       print('pong', self._name)
   end,
}

That is, a simple class with a property name and two methods: ping and pong.

Now we create three objects and link some of their methods:

a = MyClass('a')
b = MyClass('b')
c = MyClass('c')

LINK(a.ping, b.pong)
LINK(b.pong, c.ping)
LINK(c.ping, a.pong)

Then, a simple call to a.ping yields in:

> a.ping()
ping    a
pong    b
ping    c
pong    a

That simple! A method is implicitly called in reaction to a call in another condition method.
Comparing to event-driven programming, there's no need to define or post events, it's all made implicitly. Much less verbosity.

---

The reactive variables of LuaGravity (shown here and here) override Lua's default behavior for attribution. So:

b = a
a = 2

Is equivalent to:

LINK(a.update, b.update)
a.update(2)

Variables are, instead, special objects with an update method.

The parameter in a method call is propagated through its link chain as in a pipeline.
This way the value 2 is also passed to b.update.

---

A simple example of using LuaGravity in multimedia applications would go like this:

LINK(video1.start, video2.start)
LINK(video3.stop,  video4.start)

The first link makes video1 and video2 play in parallel, while the second link makes video3 and video4 play in sequence.

By overloading the operators + and * one could just write:

video1 + video2  -- play in parallel
video3 * video4  -- play in sequence

---

In LuaGravity, event definition is implicit, event posting is implicit and event linking may also be implicit (through operator overloading).

Given the amount of times the word implicit appears in this text, could LuaGravity be considered an implicit implicit invocation system?

The problem with Events

Following the discussion from here and here...

Some problems arise from event-driven programming adoption:

1. Inversion of control:

Commanded by the environment, event-driven programs must quickly answer requests to keep the system up and running.
For instance, if a program wants to perform a time consuming operation (e.g. I/O), it must demand it to be done in the background and register a callback to continue the previous operations. If a logical sequence has three of these time consuming operations, the job must be separated into that many callbacks.
This characteristic leads to difficulty in visually understanding the applications' control flow and is known as callback soup.

Another bad consequence of this code separation is that the state kept in callbacks are independent of each other as all local variables residing in their stacks are lost on returning. To keep state, their stacks must be manually reconstructed in the heap and passed as extra parameter from callback to callback.
This phenomenon is known as stack ripping.

In this sense, threads offer a more natural way of programming as the programmer may use the conventional sequential flow, keeping all state in thread's single stack.


2. Multi-core processors:

Another issue with the event-driven approach is the challenge to take advantage of multi-core architectures.

In a common event-driven dispatcher, handlers must be run in sequence as they all share global state. When parallelized, two handlers would access the shared memory at the same time, leading to data corruption.

This is not the case with threads which are already artificially run in parallel even in single-core, thus having all shared memory protected manually with programmed instructions.
Well written multi-threaded programs take advantage of multi-core for free.


3. Listener life cycle:

Once a handler is registered for events it remains listening to them until a call to unregister is made.
In some sense, this is similar to manual memory management. The system is not capable of deciding by itself when a listener must be unregistered.
There is no such concept as "listen while some rule is valid".

---

The first (and worst) problem is solved with cooperative multi-tasking.
A paper [1] explores this issue and shows this interesting graphic where the sweet spot is viewed as an improvement over both event-driven and multi-threading choices.

The second problem is a new one as multi-core architectures are still debuting.
I do have some ideas on this issue and believe that smarter people also do.
Giving different "colors" to unrelated callbacks is an option already in use [2].

The third problem arose on my own research and I'm searching for works to see if someone had already pointed that out. I'm working on a "listening scope" concept and wondered if something similar exists.

To conclude, I think that event-driven programming had always been seen more as technique than a true paradigm. Support in languages is very limited and always offered as a library layer that creates a small synchronous world for specific tasks.

[1] "Cooperative Task Management without Manual Stack Management":
www.stanford.edu/class/cs240/readings/usenix2002-fibers.pdf
[2] "Multiprocessor Support for Event-Driven Programs": people.csail.mit.edu/nickolai/papers/usenix2003-slides.pdf

Some graphical examples

The following are two graphical applications written in LuaGravity with respective videos and source codes.

---

The first example shows some flying rectangles whose size and speed increase as they get closer to the screen base.

Here's the source code:

for i=1, 15
do
 local r = root:_add(
     Rect()
         ._fill {r=255,g=200,b=100}
         .x { pc=0, dim=true }
         .y { p2=0, dim=true }()
     )

 r.x.pc = root.x.pc + INT(math.random(-15,15))

 local y2 = r.y.p2

 local v = 1 + y2^1.3/root.y.p2
 r.y.p2 = INT(math.random(1,15)*v)

 local dim = 1 + y2/5
 r.x.dim = dim
 r.y.dim = dim
end

---

The second example shows the mouse cursor surrounded by orbiting rectangles.
The orbit radius may be changed explicitly.
It's based on an example found in the FrTime distribution.

Here's the source code:

local secs = INT(1)
local sin  = L(math.sin)
local cos  = L(math.cos)
local C    = 2/3 * math.pi

radius = 50

for i=1, 3
do
 root:_add(
     Rect()
         ._fill {r=255,g=0,b=0}
         .x { dim=20, pc=(mouse.x + radius * sin(secs+C*i)) }
         .y { dim=20, pc=(mouse.y + radius * cos(secs+C*i)) }()
     )
end

"Cada Macaco no seu Galho"

Or: "A place for everything and everything in its place".

In applications like games and multimedia systems several entities run concurrently, leading to a high degree of internal and external interactivity among them.
Internal entities might be game characters, graphical widgets, AI actions and so on, while external entities might be the mouse, keyboard, network and also the time.

Interaction may be better defined as synchronization in this scope.
Using a shooter game as an example, a character movement is synchronized with user controls, as a gun sight is with the mouse position. Also, animations must be synchronized, so that all objects move together.

Currently, when realizing that asynchronous threads are not adequate for these applications, most programmers use event-driven or observer pattern techniques (I'll use the general term implicit invocation).

Synchronous functionality is present in some conventional languages, unfortunately they are barely used when known.
Continuations or coroutines are examples of such features present in languages like Scheme and Lua.
With coroutines, the programmer can keep state between successive calls to the same callback and avoid issues in implicit invocation such as inversion-of-control and stack-ripping.
It's not by chance that Lua is so popular in the game industry.

A place is still reserved for asynchronous threads: exactly where you don't need a high degree of synchronization.
If you want to compute the product of some 1000x1000 matrices, there's no point on doing it synchronized, just go async.
You can still have some degree of synchronization, though. That would be in specific (and obvious) points like a memoization table for calculated results.

Well, this is only an opinion, still in the need for a more solid background.
I would like to see more papers around this topic, although it's not easy to find bibliography defending asynchronous threads.
Maybe their advocates are just indifferent to this discussion or too busy debugging their applications.
What do you think?

Here is some bibliography:
[1] "Event-driven programming for robust software"
(pdos.csail.mit.edu/~rtm/papers/dabek:event.pdf)
[2] "Why Threads Are A Bad Idea (for most purposes)"
(www.stanford.edu/class/cs240/readings/threads-bad-usenix96.pdf)
[3] "The Problem with Threads"
(www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf)
[4] "Why events are a bad idea for high-concurrency servers"
(capriccio.cs.berkeley.edu/pubs/threads-hotos-2003.pdf)

A first glance at LuaGravity

As a pragmatic programmer, I'll try to mix the academic bla,bla,bla with practice, so...

LuaGravity is the name of my toy language that implements the synchronous approach for concurrency (I'll dig into it sometime).
(Actually, it's a *serious* toy language as a I'm very concerned to it and keep adding features and tweaking it all the time.)

When running it without a filename, you'll see a prompt just like in the Lua Language [1].
As you type the statements and expressions you'll attest that it's just normal Lua...

Except, it's reactive!

The video above shows that the variables a and b reacts to the current time, a - b to a and to b, and so on.

The INT function integrates its argument over dt (remember it from Calculus?).
It's used here only to create a time reference for the application.
The L function states to its arguments that they should behave reactively (the name comes from "function Lifting").

The result of the expression a - b shows the perfect synchronism between its arguments: no need for locks, no milliseconds difference, no text blinking, just zero as it is expected.

LuaGravity is roughly based on Esterel [2] and FrTime [3], two synchronous languages, the former having an imperative style, the latter being functional.
The example above shows only some functional features.

Here are some LuaGravity Implementation Facts:

• It's implemented over the Lua language runtime (there's no need to parse source code).
• The engine running the system is "just" an event handler.
• The elapsed time during an event handling determines the dt value used by INT and varies over the time.
  
• The prompt you see is a collection of graphical objects (no, it's not a magical raw terminal).
• It's single threaded, of course.
• The engine's whole source has about 300 lines of Lua code.
• Chuck Norris wrote a version in assembly in 2 hours.

In the next examples we'll escape from the dry command line and see a lot of graphics, where LuaGravity really rocks.

[1] http://www.lua.org
[2] http://www-sop.inria.fr/meije/esterel/esterel-eng.html
[3] http://www.cs.brown.edu/research/pubs/techreports/reports/CS-03-20.html

Threads Are Evil

I never refuse to express my opinion about threads: they are Evil.

Using threads is like selling your soul to Satan without even noticing it.
They offer you the paradise with concurrency and shared memory for your programs.
After the first week using it, you see yourself working full time to correct the "special cases" you weren't aware of. After one month you become a slave of your own program.

The other (not so) common approach to concurrency is message passing.
It seems that it is always gaining popularity, but its use is still restricted to niches. It was never really adopted by a mainstream language.
Message passing eradicates memory corruption and is seen as a safer model.

What is common with these models is that they are both asynchronous and non-deterministic.
By asynchrony I mean that the concurrent entities run unaware of each other. If they want to synchronize, they must use a language primitive for it (receive, lock, synchronized, etc).
The non-determinism is also inherent here, one can never be sure when the scheduler will preempt a running entity. This is, of course, a source of non-deterministic bugs.

What is the point of using asynchronous languages to write synchronous programs?
We feel (probably we learnt) that we have no option: If we want to synchronize code we must do it explicitly.
That is so not true as I'll try to defend here...