1	Events, synchronicity, and recursive aspect-orientation Nils Klarlund
2	Goal To lay a practical foundation for the solution of two problems fundamental to the programming of reactive systems: Events v. synchronization Event abstraction
3	We’re talking of pervasive problems Bedevil attempts to formulate declaratively temporal behavior of reactive programs Without such notations, building sophisticated concurrent system is very, very diffficult Example: lack of undo and seek mechanisms in IVR (interactive voice response systems)
4	Part I. Introduction Two fundamental problems in the design of reactive systems
5	Events v. synchronization problem How events, which take place over time, and synchronization, which is instantaneous, are related is not well-understood
6	Rest of talk Part I. Introduction Part II. Big Picture Part III. Event woes Part IV. Solution: Reaction trees Part VI. Towards a foundation for SMIL-like, reactive langauges
7	Part II. Big Picture Three kindred approaches to both problems: StateCharts Aspect-oriented programming SMIL
8	Abstraction problem How to describe behavior in hierarchical manner Example: Spoken dialogue system, where High level behavior deals Taking turns Defining possible inputs Low level behavior Speech recognizer time-outs Loading grammars
9	Abstraction solutions Idea: lower level drives higher level Theory-inspired: simplicity Hierarchical automata models (60’s) Statecharts (David Harel) What’s done in practice: messy world of Call-backs, event registration, listeners But also: Aspect-oriented programming SMIL
10	Harel’s Statecharts Events are propositions Not consumed, but generated in a reaction On {e} as stimulus, least fixed point is {e,f}
11	Advice of Aspect-Orientation Advice (Lisp CLOS, AspectJ, AspectC++, etc.) expresses “wrappers” around existing functions Arguments can be changed or augmented Results can be changed Original function perhaps not called at all
12	Aspect-oriented programming An aspect is a “cross-cutting” module that defines variables, data types, and advice Advice consists of Declaration of a set of program points (e.g. function call sites) Code executing before or after or even wrapping around the original code Binding mechanisms allowing advice code to access actual parameters of function calls
13	Computing with advice Original program text not modified Easy to maintain code variants Easy to write logging information such as Before any call of methods Draw* of class PaintObject, print the value of the size parameter Advice code is “weaved” with original code
14	SMIL SMIL (Synchronous Multimedia Language) tries to bridge the worlds: Declarative and very convincing approach to managing the sequential and parallel activities of UI Does for the temporal dimension what HMTL does for the two dimensions of layout
15	SMIL basics In SMIL, you can say “time containers I and J are to start at the same time” “time container” = “interval” We use “thread” Example: two videos to be started together <video src=’head’ id=’I’ begin=’J.begin’/> …... <video src=’side’ id=’J’ begin=’I.begin’/> Sync arc from I to J and from J to I synchronizing start of video
16	Binding world of synchronization to programmatic world of events Declarative notion inadequate in general External events myButton.click used to activate time containers Programmatic way to begin an element; that is, way to go from push events into declarative world I.beginElement()forces I to begin And by synchrony J begins
17	More bindings between worlds Also, SMIL (Microsoft implementation) offers Programmatic inspection of declarative world I.isActive property (is interval I active or does thread I run?) Casting of causality in synchronization to events onbegin event fired when thread starts
18	Event/synchronization summary Events are instantaneous But they cause each other, indirectly, through effects of resumed threads (or they are caused by external stimuli) Thus a programmer has a clear picture of temporal progression in mind when understanding a reactive event-based program
19	Event/synchronization summary II But, synchronization is about doing things at the same time according to causal rules A rigorous pursuit of synchronization has lead to practical successes such as Esterelle (with a pure synchronous semantics) StateCharts (which often has a non-synchronous semantics, however) But significant semantic problems in general The problem is to reconcile events and instantaneous causality
20	Part III. Event woes SMIL Emacs Statecharts
21	Event woes I: SMIL Example This example illustrates the naturalness of coupling intervals in SMIL And the difficulty of understanding casual dependencies as events The particular mechanism that breaks is time seek, a kind of temporal undo Link to example (only for IE 5.5 or 6)
22	The SMIL declaration <SMIL:seq repeatCount="indefinite"> <button class="time" end="c.click" id="c"> Click to launch! </button> <SMIL:par end="clip.click" id="example"> <span class="time">Launching!</span> <SMIL:video src="spaceshuttle.avi" id="clip"> <SMIL:animate begin="10s" dur="5" to="true" attributeName="mute"/> </SMIL:video> <SMIL:seq begin="rewind.click" dur="0" onend="rewind(example);"/> </SMIL:par> </SMIL:seq>
23	SMIL Example (continued) The problem occurs as follows: Click on “Click to launch!” Let movie clip run for a few seconds Then click “rewind” The display now shows at the same time both subelements of the <SMIL:seq> element!!! This is not a problem with the IE implementation of SMIL, but a sign of deeper semantic trouble: external events and declarative meaning do not mix well
24	Time seek and undo are hard Because how events, which take place over time, and synchronization, which is instantaneous, are related is not well-understood But creators would probably say: SMIL is not a reactive language, it is a declarative notation Still SMIL is supposed to be used with scripting So we need to tie events and synchronous causality together Then, solving undo and seek semantics become rather simple
25	Event woes II: Emacs An event (mouse click, key press) is an abstraction unit Namely, in keyboard macros Events are queued in unread-command-events A macro is a sequence of events A macro can be assigned to a key Thus, macros are definable in terms of macros
26	Queues: examples of renegade thinking? Does execute-kbd-macro add events to front or to back of queue? Neither works in case of macro of macros! Analogy: consider a programming language where yet-to-be-executed procedures are kept in a queue. One procedure at a time, from the front of the queue, is picked for execution Is this a good idea? For ShortTalk prototype written in 10,000 lines of Emacs Lisp Event model creates serious headaches
27	Event woes III: Statecharts Events are propositions (an unusual point of view) Not consumed, but generated in a synchronous reaction On {e} as stimulus, least fixed point is {e,f}
28	"MP1" MP1 {I: * ® f \| J: g ® f \| K: f ® g }
29	Part IV. Solution: reaction trees Causality Principle of no self-causation
30	Concepts towards an understanding An event is identified by a name A target is a block (that’s where event appears) bE = beginElement b = begin event ? = accept/receive/read/handle (pattern) event @ target ! = emit/fire/raise/signal (statement) A handler is of form pattern ® {statement ;}* Co-routine model: one handler executed at a time
31	Modeling bE to b and sync arcs
32	Cyclic dependencies lead to cyclic behaviors
33	Co-events happen when? Augment I and J with isActive variable We expect “true” and “true” to be printed History for bE signaled at I event b at I(execute handler now? no!) co-event b@I at J (observation) bE at J b at J So, co-event must be handled before execution of handler for b
34	Temporal ordering of co-events bE? ® b!I; I.isActive := true; b@J-? ® bE!I b? ® print(J.isActive)
35	The reaction tree The root is an empty node (document node) It holds the external event or injected event After an event is handled, the signaled events are appended as children in left-to-right order with time each child is accompanied by its pre-events, which are siblings inserted in front of it When an event has executed its post-events are inserted after it as siblings, and the next node in pre-order traversal is selected for handling
36	Example of tree growth
37	When to be able to handle? A guard of true(*) is always enabled? Goes against idea of event consumption So, tie this predicate to an event! Which one? The external event Not every event!
38	Reify reaction tree
39	Node matching: XSLT/XPath Convention: a pattern is now that of XSLT Examples: / the root, but never signaled/handled e the event named e /* any external event /click the external event click /*//click any mouse click that was synthesized
40	Use filters /[not(//g)] an external event, but only if g has not been signaled so far ///e[not(ancestor::f) and not(ancestor::g] any e, when not external and when not indirectly caused by f or g
41	"MP1:" MP1: {I: /*@MP1 -? ® f !MP1\| J: g ® f !MP1 \| K: f ® g !MP1 }
42	Mystery Program 1 Let us inject e at location MP1 This event is never handled There is no handler! Still f is generated as expected
43	Mystery Program 2 Let us inject e at location MP2 Post-event generates f
44	Namespace for event values Events, of course, are not atomic, but are trees So reaction tree is tree of trees! Use namespace notation with ReaxEvt for top element of an event ReaxEvtPre top element of pre-event ReaxEvtPost for top element of post-event
45	Example of namespace use <ReaxEvt:e loc=’id1’> <ReaxEvtPre:f at=’id3’ loc=’id4’/> <name>Anna</name> <ReaxEvtPre:f> <ReaxEvt:f loc=’id3’> <name>Anna</name> <ReaxEvt:f> <person gender=’male’> <name>Bob</name> </person> <ReaxEvt:e/>
46	XML for locations as well Broadcast for event signals Observe several places for co-events So, program syntax itself should be XML Then, we can write //* any location id(helperProc)//* any location within helperProc .. for the block above
47	Modeling exceptions try S{… throw e; … throw f; …} catch {e ® Se ; f ® Sf } becomes init@I!; I:{init ® S{… e!; break; … … f!; break; …} e ® Se; exit; f ® Sf; exit; }
48	Related work Esterel UML Statecharts As in our approach, one event is presented at a time. If several transitions are enabled, then either they are in different threads or the deepest one takes precedence By default all events are broadcast [Varro 2002] A Formal Semantics of UML Statecharts by Model Transitions Uses a hierarchy of queues
49	Part VI. Towards a foundation for SMIL-like, reactive langauges
50	UI issues and undo & seek In principle, we can now with confidence explain a SMIL-like language With declarative synchronization and temporal features Based on one event model comprises Reified causality Principle of no self-causation And, we can augment this notation with undo and seek as built-in mechanisms
51	Time seek and undo Add to ReaX Notion of module Checkpoints to identify unit tasks that are to be undone Ways of categorizing events as Undoable With or without specific undo event Various roll-back characteristics of modules Not undoable Notion of real time and module that allow time seek See my Web-site for more details
52	Appendix. ReaX overview Syntax Semantics
53	ReaX expressions LocE ::= XPath expression with context node = node of innermost block containing expression EvtE ::= XPath expression with context node = current event being handled E ::= EvtE or XSLT-like tree fragment In XPath: event()refers to current event
54	ReaX syntax: I Stmt::= while EvtE do {Stmts}; \| if EvtE then {Stmts} else {Stmts};\| var := E; \| EvtNnm@LocE ! ( < \| > ); \| break; \| exit; \| Handlrs \| Decls Stmts::= Stmt*
55	ReaX syntax: II Decls ::= {(var VarNvm (:= E)?;)* Stmts}; Handlrs ::= {(EvtNme{[EvtE]}? \| EvtNme@locE {[EvtE]}?{+ \| -}?) ® Stmts)*};
56	Run-time model The run status of a thread is none, waiting, or executing When status is waiting or executing, the thread has a program counter Between reactions all thread statuses are none or waiting Co-routine model: at most one thread is executing at a time If a thread is waiting, then its parent is, too
57	The reaction Add(e@l at p): Append pre-events of e@l as children of p Append e@l Process(e@l at p): If there is a handler e[EvtE] ® Stmts at l with thread of l waiting at l and with EvtE evaluating to true, then execute Stmts as a subthread For each e@L that is signaled, Add(e@L at p) Append post-events as siblings of p Process(event at next node) [in pre-order traversal] Pre-events and post-events are processed similarly No additional pre- and post-events added
58	Statement execution Simple do the obvious, advancing the PC of the thread, until a handlers block in encountered; then stop This is where the thread waits A subthread’s run status is (still) none If break or end of thread is encountered, then stop The thread’s run status becomes none (parent thread still waiting) If exit is encountered Make run status none for this thread and all siblings Continue execution of parent thread after parent block
59	Add co-events for e@l For each e @ locE [EvtE]- ® Stmts at location l_t such that locE evaluated at l_tcontains l EvtE evaluates to true add e @ l @ l_tto set of co-events Order co-events according to document order on l_t(or use static priority declarations)
60	Termination property If every while loop terminates, then the ReaX semantics guarantee termination of a reaction Proof König’s Lemma states that a finitely branching tree is infinite only if it has an infinite path Termination of while loops imply that the reaction tree is finitely branching Principle of no self-causation implies no infinite paths
61	Exceptions through transformations,… try S{… throw e; … throw f; …} catch {e ® Se ; f ® Sf } becomes init@I!; I:{init ® S{… e!; break; … … f!; break; …} e ® Se; exit; f ® Sf; exit; }