Introduction

LuaGravity is a reactive language that implements the synchronous approach for concurrency. It is roughly based on Esterel and FrTime, two synchronous reactive languages, the former having an imperative style, the latter being functional.

Reactivity Mechanisms

The link and await primitives are the supported reactivity mechanisms of LuaGravity.

Follows an introductory example illustrating their use:

rA = luagravity.create(
    function ()
        print 'a1'     -- sub-node (1)
        luagravity.await(rB)
        print 'a2'     -- sub-node (2)
    end)

rB = luagravity.create(
    function ()
        print 'b'
    end)

luagravity.link('eA', rA)

We define two reactors rA and rB, linking the string event 'eA' to rA. This way, rA executes and prints 'a1' whenever 'eA' is triggered, due to the link between them. Then, rA awaits the execution of rB. When rB is executed somewhere, it prints 'b' and awakes rA, which now prints 'a2'.

The Reactive Scheduler

In LuaGravity, a program is a dynamic dependency graph of reactors waiting for external changes to react. In the graph, nodes are reactors with dependency relations represented by directed edges connecting them.

The scheduling policy of reactors is determined only by the dependency graph, leading to what we call a reactive scheduler.

Starting from an external stimulus, the scheduler traverses the graph running all dependent reactors until it reaches "leaf" reactors. We call this process a full propagation chain, which takes an infinitesimal time to complete. A full propagation chain is also our definition for an instant within the notion of discrete time of synchronous languages.

The two reactivity primitives are responsible for populating the dependency graph with respective kinds of edges:

• Link edges: Created by link(X,Y) calls. The edge connects the reactor X (source reactor) to Y (destiny reactor) so that when the source reactor terminates successfully, the destiny reactor is implicitly triggered.
• Await edges: Created by await(X) calls. The edge connects X (reactor to await) to the continuation of the reactor being suspended. Await edges are temporary, as the scheduler removes them as soon as the suspended reactor is awakened.

In both cases, the parameter X can also be a string event.

In the dependency graph for introductory example the sub-nodes 1 and 2 represent the code chunks of reactor rC separated by the call to await.

Spawning Reactors

Reactors may be explicitly spawned from inside other reactors. The spawn(r) primitive acts like a fork, instantaneously scheduling the reactor passed as parameter and the continuation of the calling reactor to run concurrently.

Follows an example, with corresponding dependency graph, illustrating the use of spawn:

rA = luagravity.create(
    function ()
        print 'a1' -- (A1)
        luagravity.spawn(rB)
        print 'a2' -- (A2)
        luagravity.await(rB)
        print 'a3' -- (A3)
    end)

rB = luagravity.create(
    function ()
        print 'b1'      -- (B1)
        luagravity.await(rC)
        print 'b2'      -- (B2)
    end)

rC = luagravity.create(
    function ()
        print 'c1'
    end)

The execution of reactor rA prints 'a1' and spawns the reactor rB (chunk A1). The call to spawn immediately schedules rB and the continuation of rA (chunk A2) to execute concurrently. The scheduler chooses non-deterministically which one to execute first. When chunk A2 is executed, it prints 'a2' and awaits the termination of rB, creating a temporary await edge from rB to the last continuation of rA (chunk A3). When rB is spawned, it prints 'b1' and awaits rC, creating the temporary edge from rC to the continuation of rB (chunk B2). The execution of rC awakes rB, which, in turn, awakes rA, and both temporary edges are destroyed.

(Non)Determinism

LuaGravity is single threaded, meaning that any concurrent reactor runs atomically. This way, there are no critical regions in programs and, hence, no need for a locking mechanism.

However, the execution order of concurrent reactors is non-deterministic. In the example below it is not possible to know which spawned reactor runs first:

a = 0
luagravity.spawn(function()
    a = a + 1
    print(a)   -- prints 1 or 2
end)
luagravity.spawn(function()
    a = a + 1
    print(a)   -- prints 1 or 2
end
luagravity.await(0)
print(a)       -- prints 2, for sure

Environments

As reactors run as consequence of changes (input events) in the environment, LuaGravity applications must have access to such events. Each environment, which is defined independently from LuaGravity, must document its available input events and also output primitives.

There are two supported execution models for LuaGravity applications:

In the loop execution model, LuaGravity takes control of the environment, requesting new events from it whenever the applications becomes idle. The luagravity.loop call receives the application (main reactor) to run, and a function provided by the environment to requests new events. luagravity.loop only returns when the application terminates.

The following example uses the ldirectfb environment, which follows the loop execution model:

-- initialization code
local gvt = require 'luagravity'
local ldirectfb = require 'luagravity.env.ldirectfb'

-- event loop
gvt.loop(ldirectfb.nextEvent,
    function ()
        -- application code
        ...
        gvt.await('key.press.ESCAPE')
        ...
    end)

In the step execution model, the environment takes control of LuaGravity, issuing steps in the application whenever new events are available. The luagravity.start call receives the application to run, starts it, and returns an opaque identifier to be used by the step function. The luagravity.step call receives the application identifier, the event to trigger, and a value associated with the event. A step returns once the full propagation chain reacting to the issued event terminates, what should take an infinitesimal time.

Follows how the luagravity.loop call can be implemented on top of the step model:

function luagravity.loop (nextEvent, app)
    app = luagravity.start(app)
    while app.state ~= 'ready' do
        local evt, param = nextEvent()
        luagravity.step(app, evt, param)
    end
end

The step model permits that several LuaGravity applications coexist, as it does not block.

Known Environments

We try to separate LuaGravity itself from the environments in which it is used. This decoupling eases the adaptation of the language to different realms. For instance, when programming games, the environment typically provides input events for key presses and collisions between sprites, and ways to draw graphical primitives on screen. In a robotics environment, input comes from reading sensors, and output from commanding on actuators; and so on.

Another reason to separate the language kernel from environments is that LuaGravity is implemented in pure Lua, while environments usually require a C module to interact with the operating system and, hence, are not portable.

The Meta Language

We chose to write the LuaGravity kernel as an API supporting every possible mechanism in the language. Above it, we provide a layer extending Lua with the semantics of LuaGravity. This approach follows the usual idea in the Lua world of separating mechanism from policy.

Download & Install

Acknowledgements

This work is the result of my period at PUC-Rio as an MSc student supervised by Prof. Roberto Ierusalimschy.

License

LuaGravity is free software: it can be used for any purpose, including commercial purposes, at absolutely no cost. No paperwork, no royalties, no GNU-like "copyleft" restrictions, either. LuaGravity is certified Open Source software. Its licenses are compatible with GPL.

The MIT License

Copyright (c) 2009-2010 Francisco Sant'Anna

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

API

reactor = luagravity.start (app, param)

Starts the main reactor representing the application.

luagravity.step (app, evt, param)

Performs an execution step in the application with the given event.

A step returns once the full propagation chain reacting to the issued event terminates, what should take an infinitesimal time.

luagravity.loop (nextEvent, app)

Runs the given application to completion.

It is equivalent to the following code:

function luagravity.loop (nextEvent, app, param)
    app = luagravity.start(app, param)
    while app.state ~= 'ready' do
        local evt, param = nextEvent()
        luagravity.step(app, evt, param)
    end
end

The function nextEvent blocks until a new event is returned from the environment.

reactor = luagravity.create (body, t)

Creates a new reactor from a function body.

The reactor body must follow the signature:

function ([obj], param) ... end

Parameters:

• body: [function] The actual code to be executed by the reactor.
• t: [table] An optional table supporting the following fields:
  • name: [string] reactor's name (for debugging purposes only).
  • obj: [table] if set, the reactor body is always called with obj as its first parameter.
  • inst: [boolean] sets whether the reactor is instantaneous, that is, if its body contains no await calls. In this case LuaGravity performs an important optimization, not creating a coroutine to run it.

Returns:

• ref: [reactor] A reference to the created reactor.

The inst parameter allows an important optimization for reactors that do not await on their bodies. However, for reactors that do await, this parameter must be passed false.

reactor = luagravity.spawn (reactor, param)

Spawns the execution of the given reactor, passing a parameter.

The spawned reactor runs concurrently with the continuation of the running reactor.

Parameters:

• reactor: [reactor] Reactor to execute. May also be an anonymous function that is automatically transformed into a reactor.
• param: [any] Parameter to pass to the reactor.

Returns:

• reactor: [reactor] A reference to the spawned reactor.

ret = luagravity.call (reactor, param)

Executes the given reactor passing a parameter, awaiting its termination.

The callee reactor continues its execution only after the called reactor and all reactions to it terminate.

Parameters:

• reactor: [reactor] Reactor to execute.
• param: [any] Parameter to pass to the reactor.

Returns:

• ret: [any] The return value of the called reactor.

luagravity.kill (reactor)

Terminates the execution of the given (awaiting) reactor, cancelling it.

Reactors linked to (or awaiting) it are not triggered.

Parameters:

• reactor: [reactor] Reactor to kill.

Returns:

• nothing

luagravity.link (src, dst)

Creates a link between src and dst.

luagravity.unlink (src, dst)

Breaks the link between src and dst.

Parameters:

• src: [reactor|string] Source reactor or string event.
• dst: [reactor] Destiny reactor.

Returns:

• nothing

ret = luagravity.await (p1, p2, ...)

Makes the running reactor await for any condition passed as parameter. Further actions in the running reactor are not executed until it is awakened.

luagravity.deactivate (reactor)

Deactivates the awaiting reactor passed as parameter.

A deactivated reactor is not resumed when the event it is awaiting is triggered. If the reactor is awaiting on Timers associated to deactivated reactors are paused.

Parameters:

• reactor: [reactor] The reactor to deactivate.

Returns:

• nothing

luagravity.reactivate (reactor)

Reactivates the deactivated reactor passed as parameter.

Parameters:

• reactor: [reactor] The reactor to reactivate.

Returns:

• nothing

return luagravity.cancel

Terminates the running reactor, cancelling it.

Reactors linked to (or awaiting) it are not triggered.