search

SagiK-Repository / C_Sharp_Deep_Learn

C#을 깊게 배웁니다.
0 stars 1 forks source link

[논문] Reactive Programming without Functions #14

Closed SAgiKPJH closed 3 months ago

SAgiKPJH commented 6 months ago

Reactive Programming without Functions

SAgiKPJH commented 6 months ago

Reactive Programming without Functions

Abstract

Context

Reactive programming (RP) is a declarative programming paradigm suitable for expressing the han- dling of events. It enables programmers to create applications that react automatically to changes over time. Whenever a time-varying signal changes — e.g. in response to values produced by event stream (e.g., sensor data, user input...) — the program state is updated automatically in tandem with that change. This makes RP well-suited for building interactive applications and reactive (soft real-time) systems.

Inquiry

RP Language implementations are often built on top of an existing (host) language as an Embedded Domain Specific Language (EDSL). This results in application code in which reactive code and non-reactive code is inherently entangled. Using a mechanism known as lifting, one usually has access to the full feature set of the (non-reactive) host language in the RP program. However, lifting is also dangerous. First, host code expressed in a Turing-complete language may diverge, resulting in unresponsive programs: i.e. reactive programs that are not actually reactive. Second, the bi-directional integration of reactive and non-reactive code results in a paradigmatic mismatch that, when unchecked, leads to faulty behaviour in programs.

Approach

We propose a new reactive programming language, that has been meticulously designed to be reactive-only. We start with a simple (first-order) model for reactivity, based on reactors (i.e. uninstantiated descriptions of signals and their dependencies) and deployments (i.e. instances of reactors) that consist of signals. The language does not have the notion of functions, and thus unlike other RP languages there is no lifting either. We extend this simple model incrementally with additional features found in other pro- gramming languages, RP or otherwise. These features include stateful reactors (that allow for time-based accumulation), signals with dynamic dependencies by means of conditionals and polymorphic deployments, recursively-defined reactors, and (anonymous) reactors with lexical scope.

Knowledge

In our description of these language features, we not only describe the syntax and semantics, but also how each features compares to the problems that exist in (EDSL) RP languages. I.e. by starting from a reactive-only model, we identify which reactive features (that, in other RP languages are typically expressed in non-reactive code) affect the reactive guarantees that can be enforced by the language.

Grounding

We base our arguments by analysing the effect that each feature has on our language: e.g., by analysing how signals are updated, how they are created and how dependencies between signals can be affected. When applicable, we draw parallels with other languages: i.e. similarities shared with other RP languages will be highlighted and thoroughly analysed, and where relevant the same will also be done with non-reactive languages.

Importance

Our language shows how a purely reactive programming is able to express the same kinds of programs as in other RP languages that require the use of (unchecked) functions. By considering reactive programs as a collection of pure (reactive-only) reactors, we aim to increase how reactive programming is comprehended by both language designers and its users.

1 Introduction

Reactive Programming (RP) languages are languages where developers specify what time-varying values make up their program, without specifying exactly how they are changed over time [3]. RP languages provide a convenient way for variables to be au- tomatically updated if the variables they depend on change (i.e. by re-evaluating the expressions that define them). Reactive programming languages typically call these variables time-varying signals, or signals for short [15]. The ideas of RP provide an al- ternative approach to update the various components that make up a large program. Using RP yields distinct advantages over classical event handling approaches like call- backs, which are known to be unsafe to compose [30, 33] as they typically rely on (global) variables that may be read and written to by different callbacks. Correctly using callbacks therefore requires programmers to have a rigorous understanding of the evaluation order of these callbacks, lest they introduce bugs in the event handling code which is a frequent issue in application development [39]. Furthermore, it has been shown that RP programs are easier to write and comprehend than programs with callbacks [45]. In the last decades, many reactive programming languages (and libraries) have emerged, targeting various application domains such as animation [15], GUIs [8, 12], game development [37], robotics [23, 46], networking [31, 55], stage lighting [49] and distributed systems [14, 35, 43, 48]. Many of these languages are built as an embedded domain-specific language (EDSL), i.e. as languages that extend an existing general-purpose language. This approach allows existing code to be integrated with reactive code, and allows programmers to use the ecosystem of the host language (libraries, compilers, IDEs...) [8, 44]. We will refer to these languages as two-layered RP languages. The first layer, the base layer, governs the non-reactive semantics. This layer corresponds to the host language, which is usually a functional or imperative language. The second layer, the reactive layer, governs the reactive semantics. This layer provides the reactive abstractions and the mechanisms to keep them updated. Next to EDSL implementations, there exist also self-contained RP languages [12, 46, 57]. While these languages do not benefit from an existing host language (e.g., its ecosystem), the language implementation has complete control over the semantics of the language. Nonetheless, existing self-contained RP languages are very similar to their EDSL siblings as they are also two-layered: i.e. the reactive language is embed- ded in a non-reactive subset language. The full language (i.e. the reactive superset language) then uses this subset language to implement the behaviour of the various types of signals that make up programs.

1.1 Problem Statement

A central concept in every two-layered language is the notion of lifting [15]. Lifting al- lows programmers to write (base-layer) functions, and to apply them — in lifted form — to signals. When the value of one or more signals changes its value, all lifted func- tions that have been applied to these signals will be re-executed. As a consequence, EDSL RP languages constantly needs to switch between reacting (i.e. propagating signal updates) and computing (i.e. evaluating lifted code to determine a signal’s up- dated value). This combination of evaluating reactive and non-reactive (lifted) code can be cumbersome and exhibit undesirable behaviour. Moreover, it makes these lan- guages more difficult to formalise and reason about, given the bi-directional seman- tic dependencies between both layers. These issues have been identified in earlier work [51, 53].

ReactiveThreadHijackingProblem

Whenatwo-layeredRPlanguageevaluatesalifted function, the reactive runtime needs to wait until the function call returns. Lifted code therefore can hijack the evaluation thread of the reactive runtime (e.g., when the lifted code — implemented in the base layer language — contains unbounded loops). I.e. lifted code may diverge or exhaust the system’s resources. In the case of the former, the reactive runtime never regains control over the evaluation of the program, never to react to new data. In the case of the latter, the program crashes. In both cases, the program becomes unresponsive, which is an undesirable state for a reactive system to be in. Furthermore, embedded RP languages often require a host program to construct the signals that make up the RP program. If this host program diverges for any reason, the program is never able to start at all, which would also not make for a responsive system.

Reactive/Imperative Impedance Mismatch

Reactive programs do not follow the same control flow path as traditional sequential programs. The order in which lifted functions are executed is determined by the implementation of the reactive run- time. Nonetheless, RP programs often need fine control over various side-effecting operations. E.g., operations concerning files, network communication...(i.e. IO). If these are evaluated in an incorrect order, unbeknownst to the reactive runtime, bugs may arise. Some RP languages tackle this issue by disallowing side effects in lifted functions, others by simply discouraging their use in documentation. How- ever, this means that at the fringes of the RP program (where there is an interac- tion with the outside world), IO code is still needed to perform effects. We argue that side-effecting operations are essential and that this impedance mismatch be- tween reactive and imperative code requires dedicated language support.

1.2 Contribution

To tackle the issues that plague two-layered RP languages, we propose a new lan- guage that is reactive all-the-way-through. The basic abstraction type of the language, which we call a reactor, serves as the sole construct for expressing (reactive) compu- tations. Functions are absent, and therefore there is no function lifting either. E.g., the language does not have a + function to compute the addition of two numbers once for every invocation, it only has a + reactor that automatically updates each time one of its source signals updates. This is the first contribution of this paper. Using this language, we tackle the problems stated in Section 1.1 as follows:

2. First-Order Reactors

We now present Haai, a pure reactive programming language that has been designed from first principles. Our programming model features reactors as the unit of (reac- tive) computation. The computational model of our language can be summarised as follows: reactors will, when instantiated, create the time-varying signals that make up the reactive program. And at run-time, values will be emitted by these signals to keep the program up-to-date with respect to the received input values. Functions are absent in our language model, there are only reactors. This pure model of only having reactors (i.e. Uniform Reactor Model) is familiar to other approaches in pro- gramming language design. It can be compared to the Uniform Object Model that has been popularised by languages like Smalltalk [18] and Self [50]. Like these lan- guages, uniformity makes the design of the language simple and easy to understand.

2.1 Language Overview

We begin our discourse on Haai by means of a prototypical example: a unit conver- sion between temperature values [3]. Listing 1 presents a reactor named to-celsius. It converts incoming temperature readings in Kelvin to degrees Celsius. While the code in Listing 1 looks similar to Scheme [25] and Lisp [32] due to the use of S-expressions, it employs reactive semantics. By reactive semantics, we mean that reactors will need to be instantiated on time-varying signals to produce new time-varying signals. In- stead of this instantiation producing a single value (e.g,. a number), it produces one or more signals whose value changes over time. In other words, when the reactor in Listing 1 is instantiated (e.g., on a signal containing temperature readings from a ther- mometer), it will keep the temperature in °C up-to-date whenever the thermometer produces a new value (in Kelvin). We will call instances of reactors deployments. Each deployment corresponds to the signals that were created during the instantiation of a reactor. The (- ...) expression constitutes a deployment of the - reactor. Reactors in Haai can have more than one sink signal. An example of a reactor with two sinks is shown in Listing 2 which, given two time-varying signals (a and b), produces their sum (s) and product (p) as two separate sink signals. The out form, which is used here to denote which signals are considered as the reactor’s sinks, is optional if there is only one sink, as shown earlier in Listing 1. We visualise reactors using so-called reactor graphs (Figure 1). A reactor graph is a box-and-arrows diagram that — usually — consists of three regions that partition the nodes in the graph into source, internal and sink signals. Signals are ordered from top-to-bottom in the source and sink regions. In a reactor graph signals are drawn as ellipses or circles, and operations on them as boxes (with the name of the operator shown in the box). Note that for to-celsius (Figure 1a), the constant 273.15 is also shown as a signal: in Haai a literal is interpreted as a signal that — on a conceptual level — produces the literal value. We refer to these signals as constant signals.

2.2 Evaluation Model

Haai is a push-based reactive programming language [8, 12, 44]. A push-based eval- uation model means that signals propagate their value directly to those that depend on them and that signals are updated whenever any of their dependencies change. In other words, expressions like (> x y) will update when either x changes, y changes, or when both update at the same time. This evaluation model is different to pull-based languages, where signals effectively pull values from their dependencies [37, 58]. Like other push-based RP languages, Haai will update signals in a glitch-free [8] manner. A signal with multiple dependencies will only be updated if all the depen- dencies are current. For example, the expression (> (+ x 1) x) produces a signal whose value should always equal to true. When x changes, the update of > will be postponed until the update of the + signal has also been propagated. We will refer to each in- stant of the logical clock that drives the propagation of values in the program as an update turn, or turn for short. This terminology has been inspired by actor systems, which often process messages in a turn-based manner [13]. In brief, one can view the evaluation model of a Haai program as a perpetually- running loop that constantly pushes data (e.g., from external sources) into the sources of the reactive program. The values pushed to these sources will cause a cascade of signal updates that eventually reaches the sinks of the program.

2.3 Syntax

The syntax rules of Haai are shown in Figure 2. In brief, a Haai program consists of reactor definitions (which use the defr keyword) and signal definitions (which use the def keyword). The latter form supports multiple variable declarations (e.g., as in Listing 2) to support deployments of multiple-sink reactors.1 Reactor definitions con- tain (internal) signal definitions, and a definition of sinks. When a reactor has only one sink signal, the out form can be omitted, the last expression in the body will then determine the single sink signal. Expressions are either literals (which correspond to constant signals), variables (which refer to signals or reactors by name) or deploy- ment expressions (which combine other expressions). Deployment expressions are similar to application expressions in non-reactive languages: they combine an opera- tor with operands. Note that no syntax is provided for conditionals, yet. Conditional signals will be discussed in Section 4.1.

2.4 Standard Library of Reactors

In the absence of lifting, the Haai language has a set of built-in primitive reactors that enable programs to perform basic computations on numbers, strings, and basic data structures (pairs and vectors), similar to Scheme [25]. To avoid the Reactive/Imper- ative Impedance Mismatch only primitive procedures that are referentially transpar- ent have a reactor counterpart. There are no reactors that can perform side effects (e.g., vector-set!), perform IO (e.g., read), evaluate data (e.g., eval) or are involved with continuations (e.g., call/cc). The obvious difference between these procedures in Scheme and their reactor counterparts is that reactors will continuously re-run their computation whenever a signal changes. Besides these reactors, Haai features dedicated built-in reactors that are more suitable in a reactive setting, we discuss these at relevant points in the paper.

2.5 Producer and Consumer Signals

To allow Haai programs to react on values from the outside world, we propose a set of specialised reactors that produce signals that can act as (external) data producers. Vice versa, we also propose a set of specialised reactors that processes — external to the RP program itself — the output values produced by the reactive program. These two groups of reactors make it possible for Haai programs to perform IO, without those programs needing to implement IO themselves. We explain these reactors by means of an example. Listing 3 contains a basic re- active program that determines whether a thermometer is reading freezing temper- atures. On Line 1 the ws-in reactor is deployed, which is a Data Producing Reactor. Its sole argument specifies an address of a WebSocket server in which the reactive program will be able to connect to such that it receives the data that it broadcasts. We thus make it the responsibility of the language runtime (i.e. the interpreter) to actu- ally maintain that WebSocket connection, without requiring a programmer to write any imperative code in their reactive program. This is similar to primitive methods in Smalltalk [18] which are internally annotated to be evaluated using native (VM) code, transparent to the Smalltalk user. On Line 3 the the ws-out (a Data Consuming Reactor) is used which does the opposite. Its sole argument specifies the address of another WebSocket server in which the reactive program can send data to. The exact application protocol used by these primitives is irrelevant to the discussion of this paper, and is therefore not discussed. These special reactors provide a clear separation between sensing and actuating (i.e. with side effects in the real world) and the reactive program (i.e. the program with reactors and signals). The main idea here is that future language implementa- tions can provide domain-specific operators: e.g., a variation of Haai for embedded devices can provide specialised operators for the various sensors and actuators in a physical device (similar to from_topic and to_topic in RxROS [27] for ROS [29]). In the rest of this paper, we will not consider these specialised operators, as they are not essential to Haai’s semantic model.

2.6 Reactivity Guarantees

In earlier work [53], we defined three different levels of reactivity guarantees that classify a RP program (or language’s) ability to process all incoming events. These are related to the Reactive Thread Hijacking Problem from Section 1.1. We briefly sum- marise these three levels below:

Strongly reactive

A strongly reactive programming language enforces a constant up- per bound on the evaluation time of each turn. In other words, regardless of the values that flow over the reactive program’s signals: a constant upper-bound can be determined statically on the evaluation time of each turn. Strong reactivity is a desirable property for (soft) real-time systems.

Eventualreactive

An eventual reactive programming language is one for which a con-stant upper bound does not exist, but one that can guarantee that every turn will terminate in finite time. As a consequence, an eventual reactive program might appear temporarily unresponsive.

Weakly reactive

A weakly reactive programming language is one which cannot pro- vide any guarantees at all on the evaluation time of each turn. A turn in a weakly reactive language might diverge and never terminate. I.e., the reactive evaluation thread might get hijacked, resulting in a program that can forever be unresponsive.

A reactive programming language is a language that is used to make reactive ap- plications. I.e. applications that respond in a timely manner to any event that triggers a re-computation by letting each turn run to completion. Therefore, we claim that a reactive programming language should be carefully designed such that it can guar- antee the right level of reactivity needed for the targeted application. The basis of Haai is — as we will discuss in Section 2.7 — strongly reactive. In later sections of this paper, we will present various extensions, and we will analyse for each (group of) feature(s) the impact on this classification. An overview of features with their classification is shown near the end of this paper (Table 1).

2.7 ReactivityGuaranteesofFirst-OrderHaai

We now discuss first-order Haai’s reactivity classification. We start by considering what a Haai program looks like, and how it behaves at run-time. A first-order Haai program consists of a finite set of signal and reactor definitions. Each signal definition deploys the reactor(s) that it contains, which result in a (cascade of) deployments of the constituent reactors. Without recursive reactor definitions,2 the hierarchy of deployed reactors follows the syntactical structure in the source code. I.e., while re- actors can be composed of other reactors, each reactor has access to a smaller number of possible constituent reactors. Given this structure of reactor deployments, a first- order Haai program will, once deployed, always consist of the same (number of) deployments. And as each deployment has a fixed set of signals, the total number of signals also remains constant. Therefore, propagating values in each turn will — in a worst-case scenario where all signals are affected by a change — take a constant amount of time, which is a requirement for a strongly reactive language. Unfortunately, some built-in reactors have a computational complexity that is not constant (i.e. not in O (1)). For example, reactors that like their Scheme counterparts operate on data structures of arbitrary sizes or contain (as part of their implementa- tion) a form of iteration. If these reactors are considered as being part of the standard library, we consider first-order Haai to be an eventually reactive language, instead of strongly reactive one. We have therefore limited the standard library in Haai to re- actors that can be implemented to have a O (1) time complexity, and claim that this makes the language strongly reactive. This restriction does limit expresiveness, a de- sign decision that will be further discussed in Section 8.

3 Stateful Reactors

State is a fundamental aspect of an RP language. Not only do RP languages typically retain the most recent value produced by a signal to incrementally evaluate turns, RP languages often provide a mechanism to delay a signal: i.e. to get access to the past value(s) in later turns. For example, an application that processes real-time sensor values may have to apply damping to reduce jitter, or a program may only need to produce an alert if a certain condition has been sustained for a certain duration. In these applications, the behaviour of the program can no longer be expressed from just the current values.

3.1 Trampoline Variables

Typically, an RP language provides stateful operators that hide a stateful variable in their implementation. Examples include integral [9, 15], pre [58], latch [54], and foldp [8, 12, 34]. We propose a different approach that makes mutable state an explicit part of the language model. In Haai, deployments are able to accumulate state by means of so-called trampoline variables — or trampolines for short. They provide programmers with a general notion of state in the RP model. In essence, a trampoline is a variable, local to each deployment, that is updated after each turn. The semantics of trampoline variables is best understood with an example. Listing 4 shows a reactor min-max that keeps track of the minimum and maximum values ob- served of a numerical signal. The state maintained by this reactor is the minimum and maximum values observed so far: i.e. its trampoline variables. They are defined next to the source signals, a vertical bar (|) separates the formal parameters from the trampoline variables. Each trampoline variable has a name and an expression that determines its initial value. For min-max, both trampoline variables are defined by taking the current, at-deployment time, value of the source signal. From the value stored in the trampoline variable and the current value of the source signal, the new minimum and maximum can be computed: i.e. the signals mi and ma. These two signals are used both as sink signal of the min-max reactor, and as the signals that update the trampolines at the end of the turn. Another vertical bar separates the or- dinary sinks (i.e. those that will be made available to the deployment-site) from the expressions that denote the new value of the trampoline variables (they denote an internal assignment managed by the language). Figure 3 shows the modified syntax rules for defining reactors with trampolines, as used in Listing 4. Square parenthesis denote optional parts here. Trampoline variables are always updated at the end of the turn, hence providing access to an old value of a signal in a later turn. This update does not cause an immediate reaction (i.e. a new turn). It is only when a reactor deployment is updated in reaction to a change to a source signal that the value of the trampoline variable is propagated. Figure 4 visualises min-max. Trampolines are contained in a new region and have two incoming arrows. The left arrow identifies the signal that initialises the trampo- line. The bottom arrow identifies the signal that updates the trampoline. Note that trampolines may introduce cycles in the reactor graph. These cycles should disappear when the the (delayed) update arrow is omitted. Trampolines can be used to implement trampoline reactors that have similar be- haviour to the stateful operators of other RP languages. Listing 5 implements pre, an operator that delays the value of a signal by one turn. Each time a source signal s produces a value, (pre s init) produces the previously-produced value of s (except the very first time when the value of the init signal is produced). Other stateful operators, mentioned earlier in this section, can be implemented similarly.

3.2 Impact on Reactivity Guarantees

Trampoline variables do not impact the reactivity guarantees. While a program may consist of many trampolines, the total number of trampolines is fixed (similar to how the total number of signals is fixed). Therefore, at the end of each turn, the same amount of work needs to be performed to keep these trampolines updated (i.e. taking the value of the indicated update signals and storing it for the next turn). This makes stateful reactors in Haai a strongly reactive feature. Compared to two-layered RP languages Often, RP languages contain one or more op- erators that requires a function to update a stateful signal: e.g., Elm’s [12] foldp. The function supplied to foldp is applied (using base-layer semantics) each time the in- coming signal is updated. If these functions are unchecked, as is the case in Elm, the RP language becomes weakly reactive as the function supplied to foldp may (acciden- tally) diverge.

4 Higher-Order Reactors

The introduction of higher-order reactors means that some deployments become poly- morphic. As such the dependencies of signals may change at run-time. Before we discuss these polymorphic deployments, we first discuss conditional signals as they provide a gentle introduction to signals with dynamic dependencies.

4.1 Conditional Signals

In Haai, conditional signals are signals whose value is determined in relation to a specified condition. Depending on the value of the (time-varying) condition either the value of one signal or another signal will be produced. At run-time, conditional signals will toggle their active dependencies between two possible states, depending on the value produced by the conditional signal. Conditional signals are created using the if form whose syntax is standard, but shown nonetheless in Figure 5. Listing 6 shows a reactor that uses the if form to reactively compute the next num- ber in a Collatz sequence [26]. Depending on the parity of n, (collatz-step n) produces either the values of (/ n 2) or (+ (* n 3) 1). The reactor graph of collatz-step is shown in Figure 6. The signal nodes that correspond with the consequent and alternate ex- pressions of the if are grouped together by a grey box, to highlight that all signals contained therein either react together, or not at all. An important aspect of if is that either the signals in the consequent or alternative expression are instantiated during the deployment of a reactor that uses if. It is only when the truth value of the conditional signal changes, in a later turn, that the other signal(s) will be instantiated. This makes the semantics of if equivalent to a more general approach to programs with dynamic signal dependencies, which we now discuss in more detail.

4.2 Dynamic Deployments

We now make reactors in Haai first-class values: i.e. they can now be emitted by signals. We will call signals that only emit reactors reactor signals. The semantics of deployment expressions changes in a remarkable manner, if a reactor signal is used in operator position: deployment expressions become polymorphic. This gives rise to a phenomenon called dynamic deployments: deployments created while the program is running. An example of a reactor (temp-locale) in which a dynamic deployment oc- curs is shown in Listing 7. On Line 2, a reactor signal r is defined whose value is either equal to the to-celsius reactor or the to-fahrenheit reactor. This signal is then used in operator position on Line 5 which causes the program to toggle between deployments of these two reactors. As a consequence, the signal that the temp-locale reactor cre- ated, continuously toggles between the sink signal of these two deployments. Note here that signals are not first-class values. A reactor graph of temp-locale is shown in Figure 7. Note here that a consequent or alternate expression consisting of single named signal or reactor is not contained in a grey-coloured box. These signals (reactors) already exist and are updated inde- pendent of the conditional signal. Semantically, a reactor deployment is only active when needed by a dynamic de- ployment. I.e. during the very first turn either the to-celsius or to-fahrenheit reactor will be deployed, depending on the parity of seconds. One second later, when the parity of seconds changes, the other reactor will be deployed and the other deploy- ment will be deactivated. Another second later, the previously-allocated deployment will be re-activated and the other one will be deactivated. This type of switching is not a new idea [11], but differs from most other RP languages. E.g., Yampa [37] and FrTime [8] will disconnect signals if they are replaced by other signals. In these lan- guages, signals disconnected by switching are removed from memory by relying on a garbage collector (as provided by their respective host languages).

4.3 Impact on Reactivity Guarantees

Conditional signals and dynamic deployments result in a language that is still strongly reactive. Both features allow for the creation of reactive programs where the amount of signals may change depending on the number of deployments that have been activated. These deployments may be created dynamically and thus the amount of work a single turn may take is not constant, as it depends on actual deployments that are active of the dynamic deployments. Nonetheless, an upper-bound can still be calculated for each possible path by analysing which reactor values flow over the reactor signals (e.g., by means of a flow analysis). Compared to two-layered RP languages In general, we have identified two categories of RP languages that support signals with dynamic dependencies. Some languages (e.g., Elm [12]) do not allow for the run-time creation of new signals: a conditional signal can then only toggle between two existing signals. We would consider condi- tional signals in those languages also as strongly reactive. Other RP languages allow for new signals to be created while the program is running: either by allowing a signal graph to be created (e.g., Yampa [37] and Dunai [40]) and be swapped with some operator, or by allowing (lifted) code to create new signals incrementally (e.g., REScala [44]). We consider these languages weakly reactive as this creation is driven by unchecked (base-layer) host code.

5 Recursive Reactors

Existing RP languages often have support for two different kinds of recursion. The first kind, which we call lifted recursion, occurs when a recursive function is lifted. A lifted recursive function can be applied on a signal and the reactive runtime uses the semantics of the base layer to evaluate the lifted function. The second kind, which we call graph recursion, occurs when the recursive (or looping) abilities of the host language are used to recursively generate signals.3

5.1 Graph Recursion in Haai

In the absence of functions, the only supported form of recursion in Haai is graph re- cursion. Surprisingly, (graph) recursion in Haai is simple to understand as it behaves the same as regular recursion in other programming languages: i.e. by using self- reference. Instead of functions that can apply themselves at reaction-time, reactors in Haai can deploy themselves, providing a base case to stop recursive deployments (e.g., using if). An example of a recursive reactor is shown in Listing 8. It defines a recursive reactor named collatz-length to reactively compute the length of a Collatz sequence. Figure 8 shows the reactor graph of collatz-length. The recursive deploy- ment of collatz-length is included in the second grey-coloured rectangle. It is only active, and thus deployed, in a turn when num is not equal to 1. We admit that the use of graph recursion is quite atypical for this example. In a two-layered reactive programming language, the same program would usually be implemented by lifting a (recursive) function. A more practical example of graph recursion is constructing reactive sorting networks [38].

5.2 Impact on Reactivity Guarantees

Recursion is — as in any programming language — not without any risks: deploy- ments of recursive reactors may also diverge. This makes recursion a weakly reactive language feature. There are some subtleties regarding reactive recursion, specific to RP. We discuss these now. First, note that a program like (defr (loop t) (loop (+ t 1))) will never be able to be fully deployed. Deploying (loop time) causes the creation of an infinite chain of signals that all transitively depend on time (each signal incrementing the value of the previous signal in the chain by one). The same cannot be said of (defr (loop2 t) (if (= t 100) 0 (loop (+ t 1)))). If (loop2 time) is deployed, it will — like before — construct chain of deployments, except that this time the size of the chain will be limited in the presence of a recursive base case. However, if the time signal’s value itself becomes bigger than 100 in a later turn, the program will create an infinite deployment loop as the base case will then never be reached. In other words, depending on the val- ues produced by the time-varying signals that populate an RP program, a recursive deployment may diverge. This may happen in any turn, not just the first.

Restricting Recursion

To avoid programs to become weakly reactive, the use of re- cursion needs to be restricted (at the cost of expressiveness). One approach could be to apply techniques from termination detection systems [6, 28] such as primitive and structural recursion [56], or size change termination [6, 36]. Note that termination in this context does not mean termination of the RP program in its entirety — which would be undesirable — but the termination of the deployment loops that recursive reactors may manifest. This should guarantee a system that is at least eventually re- active. An overview of the integration of termination checkers, to ensure eventual reactivity in Haai-with-recursion, is outside the scope of this paper.

Compared to two-layered RP languages

We have already — at many points in this paper — discussed how two-layered languages can make an RP program weakly reactive, and will not do so again. We do, however, note the following: while at first sight only supporting graph recursion in Haai looks like a fundamental limitation, programs that would in other RP languages make use of lifted recursion can still be expressed (which will be discussed in more detail in Section 8.3). One fundamental difference to note here though — with respect to two-layered RP languages — is that it is pure reactive code in our model that is responsible for the recursive creation of signals. In two-layered RP languages, this is often the responsibility of (lifted) base-layer code [8, 44].

6 Anonymous Reactors

Similar to functional languages, Haai has a construct to make anonymous abstractions for computations.

6.1 Reactors with Scope

Unlike functional languages, which usually use the λ symbol or lambda keyword, we denote anonymous reactors using ρ or rho, to emphasise that they create reactors, not functions. Figure 9 presents the modified syntax rules. Anonymous reactors in Haai are lexically scoped. As a consequence, deployments of anonymous reactors have two types of sources: explicit sources (i.e. sources that are passed at deployment-time) and implicit sources (i.e. sources captured when the encompassing reactor was being deployed). The use of anonymous reactors is exem- plified by Listing 9. The implementation of make-temp-locale shows how a reactor creates an anonymous reactor. The in-celsius source signal determines whether to convert temperatures to either °C or °F. The make-temp-locale reactor itself emits (on a constant signal) a representation of this anonymous reactor (a capture, c.f. a clo- sure) that has this signal in scope. Deployments of that capture will react accordingly whenever in-celsius changes (even if it is not part of the reactor’s explicit sources). The reactor graph of make-temp-locale is shown in Figure 10. The grey-coloured box represents the rho expression. We used this visual notation earlier in Figures 6 and 8 for if. Like if, rho delays the deployment of certain signals. Unlike if, however, is that the signals contained therein are not necessarily deployed by the same deploy- ment. Remember that signals are not first-class. To pass around signals, an expression like (rho () x) can make a (first-class) run-time representation of an x signal. To use this signal elsewhere, this capture needs to be deployed. In other words, captures make it possible to store signals in data structures, not just the values that they produce. This approach results in a general model of higher-order reactive programming, without any specialised higher-order operators.

6.2 Impact on Reactivity Guarantees

Deployed captures are like ordinary reactors, except that they have additional signals in scope (i.e. captured signals). As such, they should not directly affect the language’s reactivity tier. We could therefore prematurely claim that anonymous reactors are a strongly reactive language feature, but unfortunately that is not the case. Similar to non-reactive languages, a recursive fixpoint combinator can be implemented. List- ing 10 provides a possible definition of a recursive fixpoint reactor. It closely resembles the call-by-value Y-combinator [42]: the only difference being the use of rho instead of lambda. This reactive fix is similar to a fix in a call-by-value language: the expansion occurs for every new recursive deployment, allowing for self-deployment (cf. self- application), which has similar consequences as ordinary recursion, by self-reference as discussed in Section 5.2. This makes anonymous reactors a weakly reactive lan- guage feature, quite a degradation with respect to our earlier assumption. When the creation of Y-combinators is restricted (e.g., by forgoing the capture semantics, or by an occurs check to find recursive type definitions on reactors, i.e. the simply typed lambda calculus) anonymous reactors should not affect the reactivity classification. Under these conditions, we can classify rho as a strongly reactive feature.

Compared to two-layered RP languages Anonymous abstractions in RP are not a com- pletely new idea. Signal functions, as introduced by Yampa [37], are closely related to (anonymous) reactors. However, unlike anonymous reactors, Yampa’s signal func- tions cannot capture signals. Furthermore, signal functions in Yampa can be created by the evaluation of non-reactive (base-layer) code.

7 Implementation

The Haai language has a prototypical implementation developed in Racket [16]. An interactive interpreter loads and runs code provided by a programmer, akin to a Read-Eval-Print Loop. Reactor definitions are loaded as entries in a so-called reac- tor table. Signal definitions are immediately deployed (i.e. global deployments) and automatically react to changes. The implementation employs an asynchronous — thread-based — evaluation model. One thread is responsible to sense the environ- ment for new data of any real-world sources, another thread is responsible to read expressions entered by the programmer and a third thread is responsible for perform- ing update turns (i.e. to propagate changes received by the other two threads: i.e. to either instantiate new signals or propagate values through signals created earlier). The prototypical implementation has support for various kinds of Data Producing and Consuming Reactors (Section 2.5). Besides WebSockets and other network-based communication protocols the language provides simple primitives to build GUI wid- gets, inspired by [12, 24]. In the future, we aim to extend our prototypical interpreter to support more kinds of application environments.

8 Evaluation

In this section, we discuss how Haai tackled the issues identified in two-layered RP languages, and compare its level of expressivity to those languages.

8.1 Reactive Thread Hijacking Problem

An overview of every language feature and their corresponding reactivity level clas- sification is shown in Table 1. It shows that most of Haai’s features are — assuming a first-order base language where all primitive reactors update sinks in O (1) time complexity — strongly reactive. In other words, programs written using (only) these features result in a program that is guaranteed to be responsive: each turn has a fixed (constant) upper-bound on the number of operations needed to update all sig- nals, regardless of the actual values propagated by these signals. The cost of an RP language being strongly reactive is that some programs might no longer be express- ible. Nonetheless, we have identified various other strongly reactive languages (even ones that are not strictly speaking RP languages) which shows that — at least for some problem domains — strong reactivity surmounts expressivity. We discuss such languages in Section 9.

8.2 Reactive/Imperative Impedance Mismatch

The specialised Data Producing and Data Consuming Reactors — as the only means to perform effects in a pure language — mitigate the adverse consequences that may emerge from the Impedance Mismatch. These operators drive the interaction between the world of pure reactors and the real world of sensors (which can serve as sources of the RP program) and actuators (which take the values produced by the sinks of the RP program). These operators are — in practice — only used in the top-level, resulting in a clean separation between the reactive world and the outside world.

8.3 Expressivity of a Pure Reactive Language

The Haai Language does not feature functions, only reactors. This raises the question whether or not this limits expressivity. If we ignore RP programs with embedded im- perative side effects, we claim that there is no fundamental restriction with regards to expressivity. We base this claim on an observation found in two-layered reactive programming languages. In these languages, there is no observable difference be- tween a signal created by a lifting a composed function, and a signal that depends on intermediate signals that correspond with the internal structure of the original function. The designers of FrTime discussed this too in the context of deep lifting [7], which is an optimisation technique that “eliminate[s] the large dataflow graphs that lifting would otherwise create”. Figure 11 visualises the ideas behind deep lifting. Fig- ure 11a shows a signal that directly computes the average of two other signals and Figure 11b uses an intermediary signal that first computes their sum. Both resulting signals are semantically equivalent. In the case of Haai, only programs with intermediary signals (as in Figure 11b) can be implemented. To show that expressiveness is not limited, we have to show that programs that use composed functions can also be expressed with intermediary signals. For simple programs involving only lifted functions, the composed function can be decomposed into it constituents. However, functions may be used in different ways besides plain lifting. Consider FrTime’s collect-e operator [8]. collect-e takes a procedure as an argument that is then applied to the values produced by a signal and the current value of an accumulator. Operators like collect-e apply said procedures not on the signals themselves, but on the values produced by signals. In most cases, there is no difference between a function being applied to the values of a signal, or to the signal’s value being passed to the procedure. Only primitive functions require the actual value of a signal [7]. Such operators are absent from Haai, but are, effectively, a trick needed to sample a signal’s value for a stateful accumulation (which are the semantics of trampoline variables). As such, we conclude that expressivity in Haai is comparable to two-layered RP languages.

9 Related Work

In this section, we present an overview of languages (RP or otherwise) that tackle similar problems.

9.1 Reactive Thread Hijacking Problem

We now discuss languages that we would classify as being either eventually reactive or strongly reactive. For brevity, weakly reactive languages are not discussed.

Reactive Programming

RT-FRP [58] is a functional reactive programming (FRP) lan- guage that we consider to be strongly reactive. The language has support for lifting and multi-modal signals (i.e. switching). To ensure strong reactivity, the language only allows functions from the simply-typed lambda calculus (i.e., without recursion, nor self-application [41]) to be lifted. The semantics of E-FRP [57] are expressed in terms of RT-FRP. We therefore also consider E-FRP to be strongly reactive. EmFRP [46] is a reactive programming language that targets embedded devices. We also consider it to be strongly reactive. The language has no support for recursion (neither lifted recursion nor graph recursion). A reactive program consists of a static set of signal definitions and supports no switching. The Stella language [51, 53] has a reactive language embedded within an actor- based one. At run-time, the Stella implementation checks that these lifted functions terminate (by performing dynamic size change termination [36]). The reactive lan- guage of Stella does not support switching: the internal dependencies between sig- nals can be derived statically. However, there is support for replication: parts of a program can be replicated, where each copy is connected to a different element in a (time-varying) set. As these sets are constrained to finite sets, this replication is bounded [52]. We therefore consider Stella to be an eventually reactive language. ActiveSheets [22, 54] is an RP language contained within a spreadsheet program. ActiveSheets supports cells connected to time-varying data streams, and changes to these cells are propagated automatically. Most primitive operations in ActiveSheets have a worst-case time complexity of O (1). However, some spreadsheet operations (e.g., those that search like VLOOKUP) are not. Nonetheless, these operations are guar- anteed to terminate, making ActiveSheets eventually reactive. There exist also various formal systems that aim to prove liveness (i.e. eventual reactivity) for reactive programs and streams [2, 47]. The main difference is that these models assume a streaming model, where programmers are explicitly in control over how a stream evolves over time (by means of a functional program), similar to streams in [1]. This model is different from RP presented in this paper, where signals compute their value in terms of the values of their dependencies.

Synchronous Programming

The ideas of (strong) reactivity can also be found in other paradigms: e.g., Synchronous Programming (SP) [19]. We discuss two SP languages that closely resemble Haai: Lustre [20] and Lucid Synchrone [5]. Similar to our lan- guage, programs expressed in these languages consist of dataflow graphs that ex- press how each time-varying value is computed. Signals in both Lustre and Lucid Synchrone have statically encoded timing information (“a clock”) which is used to determine which signals can be composed together (i.e. applying a simple function like + on two signals that do not share the same clock is disallowed). This is the main difference between SP and RP. In RP, signals are always updated with the current values of their dependencies.

9.2 Reactive/Imperative Impedance Mismatch

To solve the issues of the Reactive/Imperative Impedance mismatch, reactive code must clearly be separated from imperative code. As Haai is — to the best of our knowledge — the first pure reactive language, we list languages here where this separation has been made explicit by other means. In Yampa [37], signal functions are created by the application of pure functions that are unable to perform side effects. To run a Yampa program, a signal function needs to be combined with IO actions that provide inputs (sense) and perform actions with the outputs (actuate), using a function named the reactimate [10]. I.e. reactimate returns an IO action that is the actual RP program. Therefore, a working Yampa ap- plication contains both reactive and imperative (IO) code. FRP anguages inspired by Yampa, such as SFRP [4] and Dunai [40], share this style of combining reactive and IO code. Besides these languages, we also note two languages that target embedded applications that, like Yampa, have an explicit separation between RP and IO code. EmFRP [46] compiles reactive programs into C/C++ code which needs to be supple- mented with the actual driver (IO) application before the application (as a whole) can be subsequently compiled. Juniper [21] allows C/C++ code to be inlined in the Juniper program itself, such that it can be compiled into a full program. Finally, the aforementioned Stella language [53] proposes a clear separation be- tween reactive and imperative code by only allowing actors to perform side effects, and reactors to be pure. A working Stella program also requires both imperative and reactive code, which means that Stella is not a pure language either.

10 Conclusion

This paper presented Haai, a reactive programming language designed from first principles. Inspired by Self and Smalltalk’s Uniform Object Model, Haai employs a Uniform Reactor Model where programs are composed of reactors and every run- time value is passed over signals spawned by deploying these reactors. We presented Haai in a layered approach. Section 2 presented Haai’s first-order language model. Reactors are the computational abstraction of Haai to denote dependencies between signals. Sections 3 to 6 then presented various extensions. For each extension we discussed the effects they had on so-called reactivity guarantees, i.e. how strict the language is to enforce a certain degree of responsiveness of programs written in the language with the discussed features. Certain powerful features were identified in RP languages that hamper a language’s ability to enforce the right degree of respon- siveness. While these issues are also present in our language, our pure model allowed us to abstract over the integration of the reactive code in a non-reactive model, and consider each feature in isolation. This allowed us to increase our understanding of the RP paradigm in general.

Acknowledgements

We would like to thank the anonymous reviewers for their con- structive comments. Bjarno Oeyen is funded by the Research Foundation - Flanders (FWO) under grant number 1S93822N.