Università di Pisa
Dipartimento di Informatica
Dottorato di Ricerca in Informatica
Ph.D. Thesis
EvReact:
a reactive approach to distributed and
persistent programming
Andrea Canciani
Supervisor Prof. Antonio Cisternino
Abstract
Distributed systems are becoming pervasive, thanks to the increased availability of connectivity and smart devices, combined with the increase in the amount of data to be managed. The interest in actor-based frameworks and reactive programming has recently grown in response to their ability to ease the implementation of such distributed applications.
In fact, actors are a very effective way to express a message-driven computation as finite-state automata, while functional reactive programming is an extremely convenient way to represent event-driven data-flow computations. While both these options are very convenient in several cases, they lack the ability to express the control flow of a distributed application in a declarative and compositional way.
Another domain in which applications are commonly event-driven is that of User Interfaces. Even though the Observer Pattern is currently very widespread in this field, several alternatives which provide more structure and guarantees are well-known. This thesis work stems from GestIT, a framework which was designed specifically to provide a domain-specific language in which custom event patterns (“gestures”) could be defined and composed.
This gesture recognition language was conceived to handle a wide range of input devices and was tested on several of them. Nonetheless it was not possible to use it effectively with generic event sources. This thesis analyses some of the limitations of GestIT and attempts to resolve them. The new event pattern language, named EvReact, extends the approach of GestIT to enable its usage in a more general problem domain. This is achieved by means of a slightly increased expressiveness and stronger compositionality guarantees. EvReact has been implemented in two widely used programming languages and it has been evaluated by implementing applications from different domains, including UI gesturing and IoT services.
Acknowledgements
First of all, I would like to express my gratitude to my supervisor Antonio Cisternino. His support has been crucial and his diverse interests allowed me to get in touch with several different topics.
Credit is due to Dr. Davide Spano for investigating the application of declarative event composition to gesturing and introducing us to this research area. His work on gesturing has been both a reference and the starting point for my work.
Marta Martino deserves special thanks for being the first person who helped me recognise some of the shortcomings in the original approach. The experiments she performed were fundamental to envision the direction of this work.
Leonardo Festa, Francesco Crecchi, Andrea Serreli, and Dr. Nicole Lazzeri made it possible to understand the limitations of the event-based framework I was studying and developing, by tackling increasingly complex tasks within it.
Prof. Vincenzo Gervasi provided precious help and advice both on the writing of this thesis and on the research topic itself. His understanding of technical matters did not prevent him from appreciating the human aspect; instead he was able to provide me with motivation and a grand vision.
In the CVS laboratory I met some of the smartest geeks I know and I think it is awesome that now most of them are good friends of mine. We had great times both when tackling problems together in the lab and when spending time together outside. Among them, Leonardo Bartoloni should be mentioned because I learned a lot hacking and playing together with him.
Many colleagues and professors at the Computer Science Department have indi-rectly contributed to this result. The research I did under the supervision of Prof. Antonio Brogi together with my colleague Dr. Jacopo Soldani has been particularly significant in this respect.
vi
Prof. Pierpaolo Degano has repeatedly shown a fatherly patience towards me. The support my parents provided me has been fundamental throughout my stud-ies. None of my accomplishments would have been possible without them.
Contents
1 Introduction 1
1.1 Contributions . . . 2
1.2 Motivation . . . 3
1.3 Structure of the chapters . . . 5
1.4 Programming paradigm . . . 6
1.5 Getting started: show me the code! . . . 9
2 Background 13 2.1 Finite State Automata . . . 13
2.2 Interface Automata . . . 16 2.3 Petri Nets . . . 19 2.4 Process calculi . . . 24 2.5 Actors . . . 26 3 Language 29 3.1 Design . . . 29
3.1.1 Event-driven paradigm extension . . . 29
3.2 GestIT . . . 30 3.2.1 Ground term . . . 31 3.2.2 Iterative operator . . . 32 3.2.3 Sequence . . . 32 3.2.4 Parallel . . . 33 3.2.5 Choice . . . 34 3.2.6 Disabling . . . 37 3.2.7 Order independence . . . 39
viii CONTENTS
3.2.8 Achievements . . . 39
3.2.9 Compositionality limitations . . . 40
3.2.10 Implementation-related issues . . . 42
3.3 Reaction with aborts . . . 43
3.3.1 Ground term . . . 44
3.3.2 Iteration . . . 44
3.3.3 Sequence . . . 45
3.3.4 Parallel . . . 46
3.3.5 Choice . . . 46
3.3.6 Differences from the original GestIT . . . 48
3.3.7 Properties . . . 48 3.3.8 Limitations . . . 49 3.4 EvReact . . . 50 3.4.1 Grammar . . . 50 3.4.2 Ground term . . . 53 3.4.3 Iteration . . . 54 3.4.4 Concatenation . . . 54 3.4.5 Conjunction . . . 55 3.4.6 Disjunction . . . 56 3.4.7 Restriction . . . 56 3.4.8 Reaction . . . 57 3.4.9 Finally . . . 58
3.4.10 Regular expression-like subset . . . 58
3.4.11 Finite state automaton translation . . . 59
3.4.12 Operational semantics . . . 64
4 Experiments 73 4.1 Human Interface Devices . . . 73
4.1.1 Mouse and touchpad . . . 73
4.1.2 Touchless devices . . . 79
4.1.3 Continuous gesturing and rollback . . . 82
4.2 A scripting DSL for storyboarding . . . 83
0.0. CONTENTS ix
4.2.2 Translation to EvReact . . . 88
4.3 Distributed systems: IoX . . . 91
4.3.1 A runtime for the Internet of Things . . . 91
4.3.2 The architecture of IoX . . . 93
4.3.3 Example: UDP tunnel modules . . . 94
4.4 Aspect-Oriented Programming . . . 96 5 Implementation 101 5.1 Overview . . . 101 5.2 Public interface . . . 101 5.3 Internals . . . 106 5.3.1 Events . . . 106 5.3.2 Expressions . . . 107 5.3.3 Orchestrators . . . 109 5.4 Translation . . . 112 5.4.1 Recognisers . . . 115 5.4.2 Ground terms . . . 116
5.4.3 Unary operators: iter . . . 119
5.4.4 Unary operators: reaction and finally . . . 121
5.4.5 Concatenation . . . 121
5.4.6 Commutative operators: disjunction and conjunction . . . 124
6 Related work 127 6.1 Event-driven programming . . . 127
6.2 Workflows . . . 128
6.3 Statecharts . . . 130
6.4 Event pattern matching DSLs . . . 131
6.5 Observer pattern . . . 131
6.6 Comparison . . . 133
7 Conclusions 135 7.1 Future work . . . 137
List of Figures
1.1 An example application modelled using a statechart . . . 4
2.1 Example finite state automaton . . . 15
2.2 Example interface automaton for a simple component . . . 17
2.3 Example interface automaton that power-cycles components . . . 18
2.4 Example interface automaton cross-product . . . 19
2.5 Example Petri net . . . 20
2.6 Example non-autonomous Petri net . . . 23
3.1 The gesture recognition building block expression F1[p] . . . 31
3.2 The iterative operator expression F1[p]∗ . . . 32
3.3 The sequence operator expression F1[p] F2[q] . . . 33
3.4 The parallel operator . . . 34
3.5 The choice operator (immediate variant) . . . 34
3.6 The choice operator (best effort variant) . . . 36
3.7 The disabling operator . . . 38
3.8 The order independence operator . . . 39
3.9 Simple event recogniser of x/p . . . 45
3.10 Petri net for A∗ . . . 45
3.11 Petri net for A B . . . 46
3.12 Petri net for A||B . . . 47
3.13 Petri net for A[]B . . . 47
3.14 Petri net for xp/r . . . 53
3.15 Petri net for A+ . . . 54
3.16 Petri net for +(x) . . . 55
xii LIST OF FIGURES
3.18 Petri net for A ∧ B . . . 56
3.19 Petri net for A ∨ B . . . 57
3.20 Petri net for A 7→ f . . . 57
3.21 Petri net for A ,→ f . . . 58
3.22 Interface automaton for a/b . . . 60
3.23 Interface automaton for A+ . . . 61
3.24 Interface automaton for A.B . . . 62
3.25 Interface automaton for A ∨ B . . . 63
3.26 Interface automata that combined are A ∨ B . . . 65
3.27 Interface automaton for A ∧ B . . . 66
4.1 Recognition of multiple independent touch sequences . . . 77
4.2 Gestures recognised by the Leap Motion controller . . . 81
4.3 The IoX web interface . . . 92
Chapter 1
Introduction
Most models of computations assume that both the program and the data it will process are known in advance, but real systems are not detached from the external world. Instead, it is common for sensors and input devices to send notifications about changes in their measurements to the operating system and applications.
In the fields where the fundamental behaviour is accepting events and reacting to them, the need to express such interactions has led to the design of event-oriented models and to the development of domain-specific languages. For the same reason, various approaches to event-driven programming have also been integrated in general purpose programming languages, through libraries and language extensions.
Unfortunately, most of these frameworks only provide a data-flow paradigm and do not try to express control-flow: in order to implement it the programmer needs to explicitly write what needs to be enabled and disabled. This issue is worsened by the fact that sometimes it is not possible to do so in an efficient way. These shortcomings are particularly evident when the events to which the program should react are mostly involved in program state changes instead of computations, i.e. if the part of the program which should be active depends on the event pattern.
We propose a domain-specific language aimed at event-driven programming that addresses this issue by providing a declarative way to compose event expressions that manage the control-flow.
2 CHAPTER 1. INTRODUCTION
1.1
Contributions
The core contribution is the observation that the reification of a message-driven control-flow to a serialisable data structure is a modern way to describe computations that are not attached to a single process nor to a specific location. This makes it possible to persist or communicate the control flow through the components of a distributed system. Additionally, it eases the interactions between components written in different languages, which is essential in complex distributed systems.
This work also leads to some general insights on the design of languages for the domain of pattern matching in reactive programming:
• event-based reactive pattern matching can be based on a close analogy with regular expressions, which is a natural correlate to the intrinsic semantics of the problem area; this naturally lends to a declarative approach, i.e. the expression specifies what should be matched, not how to do it;
• Petri nets provide a convenient notation to guide implementation; if appropri-ate care is taken to ensure compositionality, they can express the behaviour of the operators and the interfaces for combining them in complex expressions;
• having both a semantics describing the behaviour of the recognisers on the incoming event stream as well as a translation (e.g. to Petri nets or finite state automata) to guide implementation provides a correctness condition for whether the implementation meets expectations and opens up opportunities for formally-verified optimisations;
• recognisers and the handlers they invoke may both fit in a common language. This offers an explicit representation of the system as a transducer and al-lows for static analysis of the interaction between each recogniser and other components;
• to avoid fragility, the recognisers should ignore irrelevant events; only explicitly undesired events should terminate a recogniser.
1.2. MOTIVATION 3
1.2
Motivation
The traditional paradigm in which each application is a single process has been recognised as limited in several fields. An alternative approach that has been used for a long time to improve performance and reliability is that of distributed applications. Recently this type of application has become more widespread in the form of web applications and mobile apps.
Web applications usually keep some data (at least the part that is currently being updated) in the browser, i.e. on the client side. In order to work correctly, these applications need to eventually communicate with the remote server, to commit the changes to a storage. The application logic can be distributed, so that the client itself performs a part of the computation. This reduces the load on the server, which in extreme cases might only have to validate and store the data.
Instead, mobile applications broke the process model to reduce energy consump-tion and to free resources: applicaconsump-tions can be terminated and restored by the operating system, but ideally this should not be perceived by the user.
These are examples of applications in which the control flow is mainly driven by events. The ability to serialise this state is obviously desirable in both cases, as it eases operations such as restoring the state of (parts of) the distributed application and it makes it possible to communicate it by means of messages.
Developers should not be concerned with the details of how this state is rep-resented and updated. For this purpose, a declarative approach is extremely con-venient: instead of explicitly controlling the state, they should only be required to provide an abstract specification of what can affect it and in which ways these fundamental elements should be combined.
For example figure 1.1 shows how the execution of a simple application could be modelled using a statechart. Performing an operation can change the state of the service, which in turn determines which operations are available.
A declarative approach only requires the developer to describe what should hap-pen instead of providing an implementation. A declarative language and its runtime can automatically determine how to perform the desired operations, freeing the de-veloper from the burden of these low-level detail.
desir-4 CHAPTER 1. INTRODUCTION
Figure 1.1: An example application modelled using a statechart
able to use a language which is declarative and compositional: it allows the developer to focus on relevant problems and to express the program logic more clearly. Reac-tive programming is usually focused on achieving this by means of the definition of a data-flow structure which describes the relationships between values. Instead, in our framework we focused on control flow: the input is not treated as notifications of changes to observable properties, but instead of events that update a state. The EvReact framework provides a language which can be used to define serialisable fragments of control flow driven by events in a compositional and declarative way.
For this purpose, we first tried reusing GestIT, a project that shares the declar-ative and compositional approach with ours, and that aims at providing a frame-work that enables developers to create new gestures. This is achieved by means of workflow-like expressions, which can be composed with each other in order to obtain complex gestures. These workflows are conceptually modelled as non-autonomous Petri nets, even though the implementation is actually based on finite state au-tomata. The resulting language proved to be very effective and convenient for de-scribing touch and mouse gestures, but it also has severe limitations that became apparent when it was applied to a wider range of devices, such as the Leap Motion sensor and the Microsoft Kinect. The experiments we conducted show that using GestIT outside of its original domain is impractical, therefore it is unsuitable for general-purpose event processing. Section 3.2 provides an overview of the GestIT language and of these issues.
This work started as a continuation of the the GestIT project, motivated by these limitations. Instead of targeting only the gesturing aspect, it tries to provide a general-purpose way to define and compose event pattern matching expressions. The new language we developed was successfully used in several case studies, in-cluding mouse and NUI (natural user interface) gesture recognition, adventure-game
1.3. STRUCTURE OF THE CHAPTERS 5
scripting and service coordination.
This thesis discusses the design and development of EvReact and the experiments that we performed. More specifically, it starts with an assessment of the strengths and limitations of GestIT and identifies some problems about its compositionality, predictability, and fragility. These issues guided the design and implementation of two frameworks, namely “reaction with aborts” and EvReact. Their semantics and design are explained as an evolution that removes some of the issues from GestIT, by enhancing its declarativeness and compositionality.
1.3
Structure of the chapters
The outline of the thesis is the following one.
This chapter presents the topic of the thesis and some introductory material to the theory beneath the reactive programming paradigm and to its representation as actual code.
The following chapters are divided into two separate groups: the former focuses on the theoretical foundations of the work, while the latter presents the practical aspects, such as the implementation and validation of the framework. These two groups have been intentionally kept as independent as possible. This makes it possi-ble for the reader to skip or postpone the theoretical part and immediately jump to the experiments or to the implementation chapters; instead the reader should focus on the first chapters if he wishes to learn about the evolution and abstract design of the reactive language.
More specifically, chapter 2 provides some background about the main formalisms that have been used to model concurrent and interactive systems.
Chapter 3 presents three variants of the event pattern recognition language. The first one is GestIT, a language designed for gesture recognition that was originally presented in [45]. This language is defined in section 3.2, while section 3.3 describes a revision that addresses some issues in the compositionality of the original approach. Finally, section 3.4 presents the final revision of the language, which was motivated by the need to make it easier to express complex reaction patterns that arose in real applications.
6 CHAPTER 1. INTRODUCTION
to evaluate the effectiveness of using the language and that have driven its evolution. Section 4.1 focuses on the application of these languages to gesture recognition, the domain for which GestIT was originally designed. Section 4.2 analyses an experiment performed on a different task: the development of an event-driven scripting language for adventure games. In section 4.3 the latest revision of the language is applied to the development of distributed agents.
The details of the F# implementation of the final version of the language are analysed in chapter 5.
Chapter 6 discusses alternative practical approaches to event-based systems. It describes some state-of-the-art design patterns, languages, and libraries that are currently used to develop event-driven and reactive applications.
Finally, the concluding remarks and some directions for future work are sum-marised in chapter 7.
1.4
Programming paradigm
The way applications are developed has changed over time with a trend towards more complex applications that are composed of multiple parts, possibly distributed among different devices.
Such applications rely on data being passed between the various components; this has several advantages in terms of the resulting architecture, as it makes it possible to decouple the components, thus enabling scalable and more robust architectures. On the other hand, this decoupling requires explicit communication between the components, which increases the complexity of the system.
This complexity is essentially the consequence of a concurrent system in which communication is asynchronous; most traditional programming paradigms expect the code to be driving computations, while in this case a more appropriate per-spective is that computations are performed depending on the availability of the data.
For example, let’s assume that a component needs to invoke a function. If the function can be executed by that component, most languages allow a straightforward and efficient function call. If that function must be performed by another component, some mechanism such as inter-process call, or possibly even network communication
1.4. PROGRAMMING PARADIGM 7
must be used to delegate the execution to the other component. Depending on the language and runtime, this might result in a blocking operation, which might be inefficient or even cause deadlocks in case of cyclic dependencies.
var data = getData ();
// g e t D a t a b l o c k s u n t i l the r e s u l t is a v a i l a b l e useData ( data );
Some modern languages (such as C++11, C#, F#, and modern JavaScript) provide explicit support for asynchronous computations. Instead of completely re-designing the languages, asynchronous data is usually exposed to the developer by means of Futures or Promises. These types encapsulate a result so that an asynchronous operation can be started without blocking the code until its result is actually needed.
getDataPromise (). then (( data ) => {
// this c a l l b a c k has been i n v o k e d b e c a u s e // data has b e c o m e a v a i l a b l e
useData ( data ) });
// data is not a v a i l a b l e
// but the code can p e r f o r m o t h e r o p e r a t i o n s performComputationsNotDependingOnData ();
Instead of a single result, it is obviously possible for an operation to return a collection; if it can be very big or if each element can be processed by itself, a stream representation is usually more convenient. In the traditional code-driven paradigm, such stream is usually an Iterator or Iterable object, i.e. an abstraction of the collection which allows elements to be extracted one by one.
var squares_sum = 0;
for (var el of getDataIterable ()) { // the e l e m e n t el is a v a i l a b l e squares_sum += el * el;
8 CHAPTER 1. INTRODUCTION
// all of the e l e m e n t s have been p r o c e s s e d useResult ( squares_sum );
The reactive programming paradigm is based on the representation of asyn-chronous events as streams. These streams can be manipulated and composed by means of filters, transformations, aggregation functions. More generally, they can be used as generic streams, just like an iterable collection or a generator function.
// n a i v e RXJS v e r s i o n of the o p e r a t i o n a b o v e getDataStream (). subscribe ({ next : (el) => { // the e l e m e n t el has b e c o m e a v a i l a b l e squares_sum += el * el; }, complete : () => {
// all of the e l e m e n t s have been p r o c e s s e d useResult ( squares_sum );
}, });
// the s t r e a m c o m p u t a t i o n runs a s y n c h r o n o u s l y
// in the meantime , o t h e r o p e r a t i o n s can be p e r f o r m e d performOtherComputations ();
As in the function call vs. promise, the main difference between iterable streams and event streams is the pull/push behaviour: iterable streams are driven by the consumer, which can request more data from the producer and block until it becomes available. Instead, event streams are driven by the producer, which provides the data to the consumer(s) as soon as it becomes available.
This approach results in an application that behaves as a responsive system, i.e. it reacts to data as soon as it becomes available. This can conveniently represent a response, as in the case of the example above, but it could also be incoming data, such as user input in a UI or client requests in a service.
1.5. GETTING STARTED: SHOW ME THE CODE! 9
modern and convenient way to ease the development of robust, distributed and scal-able systems based on message-passing components. Although its implementation poses some major challenges, several languages now support it in some form through libraries and DSLs [6] and its paradigm is influencing the design of programming languages.
1.5
Getting started: show me the code!
Before delving into the core part of the thesis, some preliminary examples are a convenient way to get accustomed to the language and conventions. These examples, just like most of the code in this thesis, are written in F#. An in-depth discussion of the EvReact language independent from the F# language is in section 3.4. The details of the F# implementation are presented in chapter 5. The full source code, the binary packages and a tutorial are available online [11].
Following the usual conventions, the first example is a simple program that writes “Hello world!” to the output. This can be written in EvReact as follows:
open EvReact
open EvReact . Expr
let orch = EvReact . Orchestrator . create ()
let evt = new Event <_ >() // Create a standard F# Event
evt. Trigger ("As expected , this is ignored ")
// Use the associated IEvent in an EvReact expression
( simple evt. Publish |-> printfn "%s")
|> start "" orch // and start the expression matcher // So far , no output
evt. Trigger (" Hello world !") // -> Hello world !
evt. Trigger (" test string ") // No output ?!?
10 CHAPTER 1. INTRODUCTION
• a prelude makes the types and functions from the EvReact library available in the current namespace;
• then the code creates an Orchestrator; • an Event (standard F# type) is created;
• finally the event is used to create an EvReact expression, which is in turn started;
• the event is triggered several times.
The first time the event is triggered it is not surprising that it does nothing, because no handler has been associated with it.
After the start of the EvReact expression, triggering the event causes the event payload to be written to the output. This happens because the expression (simple x |-> f) means that when the x event occurs, the f function should be invoked with the payload as argument. Even such a simple expression is not atomic: it is composed by the simple x expression, which is combined to f using the reaction operator |->.
The simple x expression (sometimes shortened as !!x) is the basic expression in EvReact: it represents an event recogniser that accepts the event x. After accepting the event, this expression completes and will not do anything unless it is restarted. This is the reason why the "test string" is not shown.
The e |-> f expression (or its function form react f x) is not as fundamental, but |-> is one of the most widely used operators. It allows the binding of a “reaction” to an expression. This corresponds to the handlers that are attached to events when using the observable pattern.
In order to make the expression accept any number of events, it is sufficient to wrap it in an iter operator (+):
+( simple evt. Publish |-> printfn "%s") |> start "" orch
evt. Trigger (" Hello world !") // -> Hello world !
1.5. GETTING STARTED: SHOW ME THE CODE! 11
The + operator automatically restarts the sub-expression whenever it completes. This means that the sub-expression will keep waiting for events forever, unless some-thing explicitly terminates it. This can be achieved with the restrict operator (/):
let evt = new Event <_ >()
let exitLoop = new Event <_ >()
+(!! evt. Publish |-> printfn "%s") / [| exitLoop . Publish |]
|> start "" orch
evt. Trigger (" Hello world !") // -> Hello world !
evt. Trigger (" test string ") // -> test string
exitLoop . Trigger ("")
evt. Trigger ("not shown ") // no output
When one the events in the right expression is triggered and the left expression is unable to to accept it, the restrict operator terminates its left sub-expression. This makes it possible to interrupt the iter operator.
Even though each of these 4 operators is quite simple, together they can be combined in a complex pattern such as the guarded loop just shown.
A very natural extension to this pattern involves a guard for entering the loop:
let evt = new Event <_ >()
let enterLoop = new Event <_ >()
let exitLoop = new Event <_ >()
!! enterLoop . Publish - +(!! evt. Publish |-> printfn "%s") / [| exitLoop . Publish |]
|> start "" orch
evt. Trigger ("not shown ") // no output
enterLoop . Trigger ("")
evt. Trigger (" Hello world !") // -> Hello world !
evt. Trigger (" test string ") // -> test string
exitLoop . Trigger ("")
12 CHAPTER 1. INTRODUCTION
The loop enter guard in this example is obtained using the - operator (con-catenation, cat), which provides temporal sequencing: the left sub-expression can be recognised immediately, while the right expression is started when the sub-expression completes.
There are other 4 operators provided by EvReact:
expr1 &&& expr2 completes when both sub-expressions complete, therefore it is called parallel operator;
expr1 ||| expr2 completes when any of the sub-expressions completes, hence the name choice operator;
cond e p (infix form e %- p) is similar to simple, but it only accepts the event x if the predicate p holds true;
finallyDo expr f (infix form expr |=> f) is similar to react, but instead of in-voking the function f when the sub-expression expr completes, it calls f when exprterminates. This makes it possible to associate a function to be executed when an expression is aborted because of a restriction.
Chapter 2
Background
Several models of computations have been used to describe and study the behaviour of systems which can receive events and act accordingly. Finite state automata (and translators) are generally regarded as the most basic event-driven systems. Petri nets and Grafcets have been used to model logic controllers [14]. Expert systems, which can be regarded as implementations of situation calculus, are widely used to automatically react in an appropriate domain-dependent way to the new data that is provided to the application. π-calculus has been used as a basis for workflow and service modelling languages.
Although most of these models that originated from a theoretical background have practical applications, not all of them are equally suitable for a simple and efficient implementation. Moreover, although from a mathematical point of view they are very expressive, they are not usually designed to be easy to use when developing actual applications.
The following sections introduce the models that guided the design and imple-mentation of GestIT and EvReact.
2.1
Finite State Automata
Finite state automata are one of the most basic models of computation. Conceptu-ally they represent a system that at any moment in time can be in any state from a given finite set. The current state of the automata can change depending on the input that is provided to it according to a transition table. This provides a natural
14 CHAPTER 2. BACKGROUND
way to model a system which evolves depending on an sequence of input data. This can also be used to model event-driven status changes, as the input sequence can be used to model the incoming events.
Definition 1. A finite state automaton is a quintuple hΣ, S, S0, F, δi where
• Σ is the alphabet of input symbols, i.e. the finite set of symbols which can be accepted by the automaton;
• S is the finite set of states; • S0 ⊆ S is the set of initial states;
• F ⊆ S is the set of final (acceptance) states;
• δ : S × Σ → P(S) is the transition function that specifies, given the current state and an input symbol, what is the next set of states.
The most common graphical way to represent a finite state automaton is a di-rected multi-graph, whose nodes are the states S and are drawn as circles. The initial states S0 are usually marked with an incoming arc that has no source, while
final states F are represented as two nested circles. The arcs of the graph are ob-tained by the transition function in the following way: if dst ∈ δ(src, x), the arc (src, dst) (from src to dst) belongs to the graph and is labelled with the symbol x. An example of such representation can be seen in figure 2.1. This automaton has three states identified by the numbers from 1 to 3 and the alphabet of input symbols includes a, b and c. The state 1 is marked as initial state by the incoming arc. The other arcs are labelled with symbols from the alphabet and connect the nodes in such a way to allow a specific pattern, corresponding to the language of strings of this form (ab∗c)∗c. In other words, the states 1 and 2 are connected in a
loop that makes it possible to repeat any number of times the sequence starting with a, followed by any number of b symbols and terminated by a single c, but neither 1 nor 2 is a final state. In order to reach the final state 3 (marked by the double circle), after any number of iterations between state 1 and 2 a terminating c symbol must occur when the automaton is in state 1.
Because of the finite state, these automata are less expressive than many other models of computations; in particular they are not an universal computation model,
2.1. FINITE STATE AUTOMATA 15
3
1
c
2
a
c
b
Figure 2.1: Example finite state automaton
as they are not Turing-complete. Instead finite state automata have the same ex-pressive power as regular expressions; in fact automata are often used to implement regular expressions. This also means that is possible to characterise regular lan-guages are those that can be generated (or equivalently recognised) by a finite state automaton.
If the automaton has exactly one current state at any time, it is said to be deterministic; otherwise it is nondeterministic. Determinism can be guaranteed if the initial state set contains a single element and if the transition function always maps to a single state.
Definition 2. A finite state automaton is deterministic iff
• S0 = {s0}, i.e. the set of initial states is a singleton, therefore there is only
one initial state;
• ∀s ∈ S, x ∈ Σ, ∃y ∈ Σ.δ(s, x) = {y}, i.e. for any input symbol the transition function maps each state to exactly one state.
The two conditions imply that the automaton will always be in a single state independently of the input symbols sequence. A informal sketch of the actual proof of this invariant is the following induction: it holds for the initial state S0 and it is
16 CHAPTER 2. BACKGROUND
Although the requirements for deterministic automata are stricter than the ones for nondeterministic ones, any nondeterministic automaton can be transformed into an equivalent one which is deterministic. From this point of view they have the same expressive power; the deterministic version might have many more states than the original nondeterministic automaton (exponentially as many in the worst case), therefore this transformation can sometimes be undesirable.
Several transformations, such as minimisation and the construction of the deter-ministic automaton, and properties such as language containment and disjointness can be computed for finite state automata [25].
Because of their simplicity and of the ease in evaluating and implementing them, finite state automata are widely used in several different fields. Besides from parsing and recognising languages (as implied by their relationship with regular expressions), they are often used to specify the behaviour of components and the protocols through which they communicate.
Even though finite state automata are very effective in modelling event-driven systems, they are unable to express concurrency. For this reason other formalisms are sometimes preferred notwithstanding the additional complexity they involve.
2.2
Interface Automata
Interface automata are a generalisation of finite state automata that extends them with the possibility of interacting with an external environment (or other automata) by means of messages. They have been introduced in [15] and they have seen adoption in modelling of component-based systems as they can effectively decouple modules that only interact through an interface.
Definition 3. An interface automaton is a sextuple hS, Sinit, AI, AO, AH, T i where • S is the set of states in which the automaton can be;
• Sinit ⊆ S is the set of initial states;
• AI, AO, and AH are respectively the input, output and internal actions; A =
2.2. INTERFACE AUTOMATA 17
• T : S × A → P(S) is the transition function that specifies, given the current state and an action, what is the next set of states.
Informally, the definition indicates that the states and transition function of an interface automaton correspond directly to those of finite state automaton, while the alphabet is partitioned into input, output and internal actions. Input and out-put actions are used to synchronise with the external environment, while internal steps represent actions that the automaton will perform autonomously. Interface automaton do not have a notion of final state, as they are not usually to recognise or generate regular languages, but rather to describe the behaviour of components.
stopped loading start? running ready! stop?
Figure 2.2: Example interface automaton for a simple component
Using the notation from [15], the example in figure 2.2 shows a simple automaton that can be stopped, loading or running. If the automaton in stopped it can accept a start? action (the question mark is used to denote input actions) which will cause it to go to the loading state. From this state it will go to the running state as soon as it manages to perform a ready! output (!) action. Then it will eventually go back to stopped when the stop? action is performed.
The actions constrain the composability of two automata as they can only share actions if they are inputs for one of the automata and outputs for the other one. Any other sharing is disallowed. Formally:
18 CHAPTER 2. BACKGROUND
hSQ, SQinit, AIQ, AOQ, AHQ, TQi are composable iff
AIP ∩ AI Q= ∅
AOP ∩ AOQ= ∅ AHP ∩ AQ= ∅
AP ∩ AHQ = ∅
The set of shared actions shared(P, Q) is
shared(P, Q) = AP ∩ AQ= (AIP ∩ A O Q) ∪ (A O P ∩ A I Q)
The automaton from figure 2.2 would not be composable with itself, just like any non-trivial automaton. Instead, it would be composable with the automaton in figure 2.3: the two automata share the start and stop actions and have no internal actions.
off
start!
on
stop!
Figure 2.3: Example interface automaton that power-cycles components
The cross-product of two composable interface automata is another interface automaton, in which the shared actions are internal and correspond to a synchroni-sation between the two automata1.
Definition 5. The cross-product P ⊗ Q of two compatible interface automata P = hSP, SPinit, AIP, AOP, AHP, TPi and Q = hSQ, SQinit, AIQ, AOQ, AHQ, TQi is an interface au-1Interface automata also provide a notion of composition that is stricter than that of
2.3. PETRI NETS 19
tomaton such that:
SP ⊗Q = SP × SQ
SP ⊗Qinit = SPinit× Sinit Q AIP ⊗Q = (AIP ∪ AI Q) − shared(P, Q) AOP ⊗Q = (AOP ∪ AO Q) − shared(P, Q) AHP ⊗Q = AHP ∪ AH Q ∪ shared(P, Q)
Figure 2.4 shows the composition of the automata from figure 2.2 and figure 2.2. The shared actions shared between the two automata are now marked as internal (;) and the only external action is ready!. The new automaton will autonomously start; to go from the initial state stopped/off to loading/on and when it manages to perform the ready! action it will go to the running/on and then immediately (without any further interaction with the environment) back to stopped/off (and so on). stopped/off loading/on start; running/on ready! stop;
Figure 2.4: Example interface automaton cross-product
2.3
Petri Nets
Petri Nets [43] are a powerful way to model concurrent systems. An informal def-inition is rather simple: they are graphs whose nodes can be of two types: some
20 CHAPTER 2. BACKGROUND
nodes are places (usually represented as circles), while the other ones are transitions (represented as black rectangles). The arcs of the graph can only connect places to transitions or transitions to places, but they can never connect two nodes of the same type, i.e. the graph is directed and bipartite. Additionally, places can contain any number of tokens (represented as dots). These tokens can move through the graph and such evolution of the state of the net corresponds to a computation. Definition 6. A Petri net is a quadruple hP, T,•·, ·•i where P is the set of places,
T is the set of transitions (with P ∩ T = ∅), and •·, ·•
: T → P → N are functions assigning to each transition its pre-set and post-set.
This definition allows transitions to also destroy and generate multiple tokens in each place upon firing. In most of the following , we will be working with Petri nets whose transitions consume or produce at most one token in each place, in which case the pre-set and post-set are proper sets.
A B C D E split store join loop
Figure 2.5: Example Petri net
The example in figure 2.5 is such a Petri net with 5 places A, B, C, D, and E. It has 4 transitions:
• the split transition consumes one token from the A place and emits one token in the B place and one in the C place;
• the store transition removes a token from B and adds a token to D;
• the join transition consumes one token from the B place and one token from the C place and adds one token to the E place;
2.3. PETRI NETS 21
• the loop transition removes a token from E and adds a token to A;
Besides from the graph structure, a Petri net has a marking that represents the tokens that are in its places. Mathematically a marking is a function from the places to natural numbers: M : P → N. This is fundamental for the computation performed by the Petri net, because it is the state that evolves when transitions happens.
Specifically, a transition is enabled when its pre-set is satisfied. An enabled transition can fire. This results in a new marking, in which the tokens in the pre-set are destroyed and the ones in the post-set are generated. Moreover transition can fire in a concurrent fashion, i.e. more than one transition can fire at the same time, as long as their combined pre-sets are satisfied.
Definition 7. A set of transitions U is enabled for a marking M iff ∀p ∈ P, M (p) ≥X
t∈U •
t(p) .
If such set of transition fires, the net will change marking from M to M0, which
is defined as
M0(p) = M (p) +X
t∈U
t•(p) −•t(p) .
For example if the net of figure 2.5 had one token in B and one token in C, both join and store would be enabled, hence either one could fire, but it would not be possible for them to fire together. Instead, if C contained one token and B contained two (or more) tokens, it would also be possible for them to fire at the same time.
Depending on the convention, in some cases the definition of Petri net also in-cludes the initial marking M0, which is the state of the tokens over the places at
the beginning of the computation.
The basic definition of Petri nets does not provide any way for a Petri net to interact with its environment, which is a fundamental requirement for modelling re-active systems. This problem has been tackled in several ways and in the following we will present two different approaches: open Petri nets, which allow the environ-ment to modify the contents of some places, and non-autonomous Petri nets, which have transitions that can only fire in response to an event.
22 CHAPTER 2. BACKGROUND
According to [7], an open Petri net is an ordinary Petri net with a distinguished set of (open) places that are intended to represent the interface of the net towards the external environment. An open place can be either an input or an output place (or both), meaning that the environment can put or remove tokens from those places.
Definition 8. An open Petri net is a pair Z = hNZ, OZi, where
• NZ = hP, T, •·, ·•i is an ordinary Petri net, and
• OZ = hOZ+, O −
Zi : 2P × 2P are the input and output sets of open places.
The places in P \ (O+ Z ∪ O
−
Z) will be referred to as internal places.
A non-autonomous Petri net is a Petri net in which a events can be associated to transitions. In such a net, the enabled transitions will not be able to fire, until the associated event occurs, at which point they will immediately fire.
Definition 9. A non-autonomous Petri net is a triple Z = hNZ, EZ, SyncZi, where
• NZ = hP, T,•·, ·•i is an ordinary Petri net,
• EZ is the set of external events, and
• SyncZ : T → EZ∪ e (where e is the always occurring event) is a function that
associates an event to each transition.
In this type of nets, if a transition t is enabled it is said to be receptive to the associated event SyncZ(t). If this event is the always occurring event e, the
transition will immediately fire. Otherwise the transition will fire as soon as the associated event occurs.
Definition 10. If the marking is M, when the event x ∈ EZ∪ e occurs, the set of
transition U that will fire must satisfy the following conditions: • they are enabled, i.e. ∀p ∈ P, M(p) ≥ Pt∈U
•t(p)
2.3. PETRI NETS 23 A B C D E e a b e
Figure 2.6: Example non-autonomous Petri net
Sometimes additional requirements on the choice of U are imposed, such as being maximal or being a singleton, but in general no specific choice of U is required.
An example non-autonomous Petri net is shown in figure 2.6. It has the same structure NZ as the Petri net in figure 2.5. The set of external events EZ contains
the events a and b and the value of SyncZ for each transition is shown instead of
the transition name:
• the split and loop transitions always fire immediately, because they are asso-ciated to the always-occurring event e;
• the store transition synchronises with the event a; • the join transition synchronises with the event b;
It is easy to notice that in this case at every iteration the choice of what happens is determined by the event that occurs. If a occurs when B contains a token, the store transition will fire; if b occurs when B and C each contain a token, the join transition will fire. If both a and b happen at the same time, either store or join can fire (non-deterministically), just like in the autonomous case.
Although autonomous Petri nets are simpler, non-autonomous Petri nets are eas-ier to combine with other systems, because they do not impose special requirements on the external environment. Autonomous Petri nets can only consume or emit tokens, therefore they are restricted to interacting with other Petri nets. Instead, non-autonomous Petri nets can be combined easily with other systems, because they can be treated as black boxes as long as the event-based interface matches.
24 CHAPTER 2. BACKGROUND
Finally, while Petri nets are sufficiently expressive to encode complex concurrent computations, they are very low-level. Their uniformity and simplicity can be con-venient because several properties correspond to the result of the application of an algorithm directly on the net graph. For this reason several higher-level concurrent languages are commonly translated to Petri nets in order to automatically prove properties or perform model checking. Conversely, for a human it is usually incon-venient to express complex computations in the formalism of Petri nets. For these reasons, (non-autonomous coloured) Petri nets were evaluated as a possible backend for EvReact, so that they would not be directly exposed to the final user.
2.4
Process calculi
Process calculi encompasses several languages used to formally describe concurrent processes, with a specific focus on the patterns of communication. Like Petri nets, process calculi have seen limited adoption in practical languages, but they have been used to analyse the behaviour of concurrent systems and communication protocols. While Petri nets are expressed as graphs, the processes of these languages are normally generated by a context-free grammars. Nonetheless, their behaviour is usually nontrivial to analyse and there is ongoing research on computing or approx-imating their properties. Part of this complexity comes from the fact that most members of the process calculus family are Turing-complete, usually thanks to the ability of spawning new processes. Even if such operation is not allowed, these lan-guages are usually endowed with nondeterministic semantics, which makes some of the problems harder to handle from a practical perspective.
There are many variants of process calculus, differing both in the specific gram-mar and in the associated semantics. One of the simplest and more compact for-malisms of the family is π-calculus [37, 38]. Its syntax is described by this grammar:
hP i ::= 0 | x(y).P | ¯xhyi.P | P1|P2 | (νx)P | !P
These syntactic constructs have the following meaning:
• 0 is the nil process, i.e. a process that has completed and that will not perform any further communication or synchronisation.
2.4. PROCESS CALCULI 25
• x(y).P is the process that receives a the y value from the x channel and pro-ceeds with the execution of P ; similar to this, ¯xhyi.P is the process that sends the value y on the channel x and proceeds with P ; these are the (synchronous) communication primitives of the language.
• P1|P2 is the parallel composition of the P1 and P2 processes; they are
concur-rent processes that can evolve independent of each other unless they perform an explicit synchronisation in the form of communication.
• (νx)P creates a new channel named x and runs the process P ; note that in π-calculus channels can be treated as values and sent to other processes. • !P repeats the process P an unlimited number of times (in parallel to each
other), i.e. !P ≡ P |!P .
Even though the language looks very simple, it is an universal model of com-putation. This was proved in [36] by showing an encoding of the λ-calculus into π-calculus. This result relies on the possibility of implementing recursion by means of process replication. If replication is not allowed, the language is not Turing-complete anymore and properties such as semantic equivalence (in the form of a bisimilarity relation) become decidable.
Besides π-calculus, CCS (Calculus of Communicating Systems [35]) and CSP (Communicating Sequential Processes [24]) are two of the most widely known process calculi. Their differ mainly in the grammar of the process expressions; however, their semantics is very similar: each step of computation is related to an event, which is a synchronous message exchange between two processes.
Calculus of Broadcasting Systems [42] is not as well-known, but is interesting as it works on a different assumption. Just like in other process calculi, there can be several processes waiting at the same time for a message on a single channel. The difference arises when a message is sent on such a channel: in π-calculus, CCS, and CSP, the message is delivered to only one of the possible recipients (chosen nondeterministically); instead in CBS the message is delivered to all of the recipients (i.e. it is broadcasted, as the name suggests).
Process calculi have been used to model and simulate both real-world and in-formation theoretical systems. For example, PEPA [23] (Performance Evaluation
26 CHAPTER 2. BACKGROUND
Process Algebra, a stochastic process algebra) was originally designed to evaluate the timing and rate of activities such as coordination of complex hardware and soft-ware systems and protocols. Nonetheless as processes can be used to represent a diverse range of activities, PEPA has also been integrated with other tools and used to model chemical reactions and biological systems.
The CSP and CCS calculi have been used as a base for the LOTOS (Language Of Temporal Ordering Specification) language, which was originally standardised in [26]. LOTOS can model several aspects of distributed and concurrent systems, and it has been mainly used to model-check networking protocols, even though the possible application fields are much wider.
2.5
Actors
Another approach which has seen wide adoption is that of the actor model [22, 2]. Actors are autonomous entities, whose internal state can change when they receive a message. From this point of view, they resemble objects of the Object-Oriented Programming paradigm, but they differ because while objects are usually sequential, actors feature a concurrent behaviour.
In the context of the actor model, the events are the communications that are performed by the actors, which can both receive and send events. Often such models also allow new actors to be spawned and to send each other addresses, thus dynami-cally restructuring the communication topology. This trades the ability to statidynami-cally prove properties of the system for expressiveness.
Although actors look similar to processes, there are also deep differences. The loose coordination of actors is akin to the concurrent behaviour of parallel processes and the spawning of new actors is similar to process replication. Conversely, the way in which communication takes place is very different: instead of communicating through synchronous channels, each actor owns a “mailbox” to which other actors can asynchronously send messages.
This means that a communication only guarantees that the message has been sent before it was received, therefore synchronising two actors requires a bidirectional handshake. Moreover the fact that messages are sent to addresses instead of channels means that several actors might be able to send messages to the same recipient
2.5. ACTORS 27
without being able to communicate with each other directly and the recipient might be unable to send messages to any of them, if the source addresses are neither known in advance nor part of the message. This is very different from what happens when communicating over channels, because any process that can send messages over a channel is also capable of receiving messages on it.
The actor model has been very influential from the theoretical perspective and it has been used as a foundational model for concurrency. Specifically, it is possible to represent every value, operator and agent as an actor. This resembles the approach of object-oriented languages, such as Smalltalk [18] and Simula [39] where everything is an object; in fact the actor model was also used as a starting point to formalise object-based languages [1].
In addition to the theoretical results and to the influence on the object-oriented paradigm, the actor model has also seen adoption in practical programming lan-guages, most notably Erlang [5]. Actors have also been integrated in other pro-gramming languages by means of libraries, such as Akka [9].
Chapter 3
Language
3.1
Design
3.1.1
Event-driven paradigm extension
The basic event-driven paradigm provides a simple and efficient way to associate a code fragment to be executed upon the firing of an event. This event is sometimes coming from an external source, but in most cases it is also possible to trigger events internally, which makes the trigger-handle pair somewhat like a procedure invocation.
Event-driven programming models that do not express structured event patterns can usually only express two kinds of event-handler bindings. The first one corre-sponds to a one-shot event handler, while the second one makes the event-handler binding permanent, so that each time the event is triggered, the handler is invoked. A very common extension allows some event data to be associated with each event firing. This makes it possible to model procedures called with that payload as an argument. Additionally, this is fundamental in functional reactive programming and in general in event-driven dataflow computations, as this makes it possible to communicate the data to be processed.
When multiple events are related to each other, it is possible to encode such structure, but often the facilities available to the developers are very primitive. They are often required to hand-code the event pattern structure explicitly, which can make it harder to combine multiple patterns together and to maintain the code.
30 CHAPTER 3. LANGUAGE
This task can be made easier by using actors and statecharts, as they provide a representation similar to that of finite state automata. While this simplifies the local reasoning, it can also hide the overall structure of the event pattern. A more declarative approach can be more effective, just like the intuition of the language defined by a regular expressions is often easier than that of the same language described by the FSA.
The main objective of GestIT was to create a language whose expressions de-fined gestures (i.e. patterns of input events from a user interface) in a declarative and compositional way. Due to the compositionality, it can construct expressions from simpler ones. The declararive approach hides from the developer the complex-ity of how the recognition is performed, focusing instead on what event pattern is represented.
This work is a continuation of the original GestIT project, with the aim of generalising it from a domain specific language for the construction of custom UI gestures. This was achieved by revisiting some aspects of the definition of the expression language and of the implementation. In this process, the design was often guided by the theoretical models presented in chapter 2. For example, the choice to ease the development of distributed systems that interacted asynchronously by means of messages treated as events is inspired by the actor model.
The result is a language which makes it possible to declare which event patterns should be detected without specifying the details of how such recognition should be performed. The patterns can be composed from simpler ones and handlers can be associated with each component, making it easy both to reuse expressions and to constrain them to a specific sub-pattern without explicitly enabling/disabling the handler.
3.2
GestIT
GestIT was presented by Spano in [45] as a framework to define gesture expressions in a declarative and compositional way, using operators similar to those of CTT [40]. The behaviour of these expressions was described by means of non-autonomous Petri nets, but the actual implementation of the recognition was performed by means of finite state machines.
3.2. GESTIT 31
Gesture expressions are constructed using the following grammar:
hGi ::= Fi[p] | G∗ | G1 G1 | G1||G2 | G1[]G2 | G1[> G2 | G1|=|G2. . . Gn1|=|Gn |
where Fi[p] is a ground term and G are gesture expressions.
The following sections will discuss these expression constructors and the proposed mapping to Petri nets.
3.2.1
Ground term
The ground term is the basic building block of the gesture expression grammar. They can only recognise the atomic events that are observed by the system.
A simple example of such events for a computer with a mouse consists in the mouseDown, mouseMove and mouseUp events, which cannot be further decom-posed and, in fact, are usually the exact events produced by the hardware. Con-versely, the well-known click events is actually a composite gesture, as it can be expressed by a sequence of mouseDown and mouseUp with the additional con-straint that it is entirely performed within a short time.
In GestIT, these events are raised when one or several features change.
These basic building blocks are represented as Fi[p], where F identifies the feature
that is observed by this expression and to the Boolean predicate p further constrains the triggering of the transition. For brevity and clarity, p will be omitted if it is always true.
var expr =
new SimpleTmpExp (
new MyContent (
Features .F1 , p));
Figure 3.1: The gesture recognition building block expression F1[p]
The Petri net associated with a ground term is shown in figure 3.1. The net is active when the Start place contains a token, which enables the transition f1, p(S).
32 CHAPTER 3. LANGUAGE
This transition will not fire autonomously, as it will only trigger when the f1 event
occurs, if the predicate p holds true.
3.2.2
Iterative operator
The iterative operator G∗ repeats the recognition of its sub-expression for an
indef-inite number of times. In order to avoid an infindef-inite gesture, it is usually combined with a disabling operator.
The Petri net for an iterative operator is shown in figure 3.2. It can be obtained from the net of the sub-expression simply adding a transition (with no constraints and triggered by the always occurring event) that connects its End transition with its Start place.
var expr =
new SimpleTmpExp (
new MyContent (
Features .F1 , p)); expr . Iterative = true;
Figure 3.2: The iterative operator expression F1[p]∗
The construction shown in figure 3.2 is the original one from [45] and is missing explicit annotations for the Start place and End transition of the iterative expres-sion. In order to ensure that this net can be correctly composed with other gestures, the Start place is interpreted to be the same one both for the sub-expression; in-stead the End transition is a never-firing transition, i.e. it starts from an empty place disconnected from the remaining of the net. As already mentioned, this im-plies that the iterative expression does not end by itself, but it is usually terminated by a disabling operator.
3.2.3
Sequence
The sequence operator combines two sub-expressions that should be recognised one after the other one. The tap gesture is the simplest example that can be constructed
3.2. GESTIT 33
using this operator:
T ap := T ouchStart T ouchEnd
The Petri net associated with G1 G2 is obtained by connecting the End
transition of the net associated to the first sub-expression with the Start place of the second sub-expression. The Start place of G1 and the End transition of G2 play
the same roles also for the composite expression, as shown in figure 3.3.
var g1 = new SimpleTmpExp (new MyContent ( Features .F1 , p));
var g2 = new SimpleTmpExp (new MyContent ( Features .F2 , q));
var g = new BinaryTmpExp (g1 , g2 , TmpOperator . Enabling );
Figure 3.3: The sequence operator expression F1[p] F2[q]
3.2.4
Parallel
The parallel operator || is used to define an expression which is recognised when its two sub-expressions are recognised at the same time, in a way resembling an AND operator. The Petri net translation is shown in figure 3.4. It duplicates the token from P arStart as soon as the parallel recogniser is started to immediately start both sub-expressions. When a sub-expression completes, it puts a token in its P arEnd place. When both P arEnd places contain a token, the End transition of the net can fire, merging the two tokens into one and completing the recognition.
It is noteworthy that, assuming that the sub-expression output a token for every token that is added to their Start place, the parallel operator does the same. This happens because even though tokens are duplicated before they are fed to the sub-expression nets, they are merged on exit.
34 CHAPTER 3. LANGUAGE
Figure 3.4: The parallel operator
3.2.5
Choice
The choice operator is recognised when exactly one of the two sub-expressions is recognised. This means that only one of the two sub-expressions can be recognised to the end. There are two alternatives that are compatible with this proposed in the original GestIT framework:
• an immediate variant, in which the first sub-expression that can match the beginning of the gesture is started as soon as possible and the other one never starts at all;
• a best effort variant, in which both sub-expressions nets are started, but as soon as one completes, the other one is aborted.
3.2. GESTIT 35
The immediate variant of the choice operator (applied to the trivial case of two ground term sub-expressions) is shown in figure 3.5. It is unfortunately impossible to construct it if nets only expose a Start place and an End transition. To over-come this issue, the outgoing transitions of the Start place need to be exposed as well. These transitions correspond to the Starting Ground term Set SGS, which is recursively defined as follows:
SGS(Fi[p]) = {Fi[p]} SGS(G∗) = SGS(G) SGS(G1 G2) = SGS(G1) SGS(G1||G2) = SGS(G1) ∪ SGS(G2) SGS(G1[]G2) = SGS(G1) ∪ SGS(G2) SGS(G1[> G2) = SGS(G1) SGS(G1|=|G2. . . Gn−1|=|Gn) = n [ i=0 SGS(Gi)
The transitions associated with the ground terms in the SGS need to be con-nected to all of the Start place of the sub-expression nets in order to obtain the structure depicted in figure 3.5.
The composition behaviour of the best effort variant is even more complex: it is not sufficient to expose only starting and ending places and transitions, it actually needs the ability to abort one of the two subnets at any time. To achieve this, [45] defines the Ground term Set GS as follows:
36 CHAPTER 3. LANGUAGE
Figure 3.6: The choice operator (best effort variant)
GS(Fi[p]) = {Fi[p]} GS(G∗) = GS(G) GS(G1 G2) = GS(G1) ∪ GS(G2) GS(G1||G2) = GS(G1) ∪ GS(G2) GS(G1[]G2) = GS(G1) ∪ GS(G2) GS(G1[> G2) = GS(G1) ∪ GS(G2) GS(G1|=|G2. . . Gn−1|=|Gn) = n [ i=0 GS(Gi)
3.2. GESTIT 37
and the Complementary Ground term Set1 as:
CGS(G, Fi[p]) = GS(G) − {Fi[p], Fi[¯p]}
.
The construction of the net associated to G1[]G2 given those of G1 and G2 is
rather simple:
• an OpF ail place is added to the composite net and it is connected to the ending transitions of both operands
• the input place of each ground term Fi[p] in GS(G1[]G2) is connected to
the OpF ail place by means of transitions which fire for any of the features in CGS(G, Fi[p]); since each transition fires when a single event occurs, to
implement the “any” behaviour, one transition is needed for each feature in CGS(G, Fi[p]).
In the original description it is not clear if the transitions to be added are those from CGS(G1[]G2, Fi[p])(i.e. the choice expression being translated to Petri net) or
those from CGS(G, Fi[p]) where G is the whole gesture expression. Unfortunately,
both definitions have some flaws, which will be highlighted by means of some exam-ples in section 3.2.9.
3.2.6
Disabling
The disabling operator defines a gesture in which the recognition of the second operand stops the recognition of the first one, disabling it. Its main use it to termi-nate the recognition of a iterative gesture.
It is constructed in a similar way to the immediate version of the choice operator, with the major difference that while the two operands are treated in the same way for the choice operator, in the disabling operator is not symmetrical. In particular, the first operator is the only one which receives a token when the net is activated;
1The original definition contains some typos as it treats F
iand Fi[p] as sets instead of elements
of the GS set. Moreover it is slightly redundant in the perspective where omitting p is the same as using the true predicate as p.
38 CHAPTER 3. LANGUAGE
consequently all of the starting transition of the nets only consume a single token from the Start place of the first operator.
Figure 3.7 shows the resulting Petri net for the expression (F∗
1)[> (F2[]F3). In
general, the construction of G1[> G2 () is as follows:
• each input place of GS(G1)is connected to a copy of each of the starting
tran-sition in SGS(G2); the same is also done for the places OIF lag and OIEnd
if G1 contains an order independence operator;
• each of these new transitions is connected to the appropriate place in SGS(G2);
if G1 duplicates token (for example if it contains a parallel), they need to be
merged in order to preserve the property that for each incoming token there is just one outgoing token.
Figure 3.7: The disabling operator
Although the construction looks simple, it is non-trivial to correctly hook up all of the new transitions, as it requires touching the internal part of the subnets. Simple cases can be handled with an approach similar to that described for the choice operator, but in general this shows some limitations in the compositionality of the mapping to Petri nets.
3.2. GESTIT 39
3.2.7
Order independence
The order independence operator is recognised when all of its sub-expressions are recognized in sequence, regardless of the order in which they are recognised. For any given length, this could be implemented by means of a combination of choice and se-quence; for example G1|=|G2recognises the same gestures as (G1 G2)[](G2 G1.
Such a translation would involve a simpler translation, but it would have exponential size: its size would be proportional to n! for the n-ary order independence operator. The construction shown in figure 3.8 is based on the idea that a single sub-expression is started as in the immediate choice operator and its execution is tracked by the OIF lag place. When a sub-expression is recognised, a token is put back into each of the starting places and one token is put in the OIEnd place of the sub-expression. When all of the sub-expressions have been recognised, the end transition will fire.
Figure 3.8: The order independence operator
3.2.8
Achievements
The GestIT framework provides a convenient way to structure gesture recognition, hiding the complexity of the management of the observer pattern from the
