Jean-Michaël Celerier
email: jcelerie@labri.fr

Myriam Desainte-Catherine
email: myriam@labri.fr

Jean-Michel Couturier

Extending dataflows with temporal graphs

Numeric musical and artistic creation is in great part based on well-known patcher softwares: Max, PureData, Open-Music, vvvv… Yet, handling temporal evolutions and structures on large scales remains a central problem: for instance, writing a song with introduction, chorus, verse, chorus, parts in Max presents many hurdles to the composer. Hence, multiple software have introduced tracks and automations to provide a temporal control of a given set of parameters in a single or even multiple concurrent time-lines. We present an extension to the dataflow paradigm used by patchers that allows to handle the execution of any parts of a computation in time. That is, instead of sending control messages to existing patchs, they are run in a time-line which orchestrates the data bindings between different parts of the dataflow. This enables dynamic behaviours when creating temporal compositions. An example is given with Pure Data patches and an i-score scenario.

Introduction

This work explores the association of macroscopic temporal semantics with the dataflow graphs generally used in music and signal processing. We analyze the meanings that can be given to processes executing in time, when these processes have a data dependency and do not execute at exactly the same time.

For instance, given two processes p 1 , p 2 , what can be said of a program where p 1 executes from t = 0 to t = 5 seconds, and p 2 from t = 3 to t = 6 when p 1 and p 2 operate on the same data? An example would be an audio filter: p 1 is a low-pass and p 2 a reverb; we want the reverb to activate only after an action of a performer and stop after a few seconds.

The simplest strategy can be to only allow execution when all processes are active and have been given a definite order of execution: in this case the overall program will only execute during the intersection of the activation of p 1 and

Copyright: ©2017 Jean-Michaël Celerier et al. This is an open-access article distributed under the terms of the Creative Commons Attribution

License 3.0 Unported, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

p 2 , which goes from t = 3 to t = 5. While safe from the point of view of software execution, we will show that other execution policies leveraging information from the temporal layout of the processes can provide composers with new creative capabilities, through an example that uses Pure Data. An environment associated with the dataflow graph is introduced; it contains the values of the inputs and outputs of the processes in this graph. Then, since a graph may not always be fully active, we show that it is also meaningful to have implicit connections between nodes of the graph, that will use the environment. This allows dynamic routing of the processes according to their temporal order during execution, and extends routing to pattern-matched elements of the environment instead of single values. Three different behaviors between the input and output parameters of the dataflow nodes are presented: strict, glutton, and delayed.

Time flow direction

Interactive trigger

State

Conditional

Synchronization

Span of time

Figure 1:

Part of an OSSIA scenario, showcasing the temporal syntax used. A full horizontal line means that the time must not be interrupted, while a dashed horizontal line means that the time of this time constraint can be interrupted to proceed to the following parts of the score according to an external event.

Related works

There is a long-standing interest in the handling of time in programming languages, which is intrinsically linked to how the language handles dynamicity. PEARL90 [START_REF] Halang | Safe object oriented programming of distributed real time systems in PEARL[END_REF] 1 provides temporal primitives allowing for instance to perform loops at a given rate for a given amount of time. More recently, Céu has been introduced as a synchronous language with temporal operators, and applications to multimedia [START_REF] Rodrigo | CÉU-MEDIA: Local Inter-Media Synchronization Using CÉU[END_REF]. OpenMusic is a visual environment which allows to write music by functional composition. It has been recently extended with timed sequences allowing to specify evolutions of parameters in time [START_REF] Garcia | Timed Sequences: A Framework for Computer-Aided Composition with Temporal Structures[END_REF].

Likewise, the Bach library for Max [START_REF] Agostini | A max library for musical notation and computer-aided composition[END_REF] allows to define temporal variations of parameters during the playing of a note by with the mechanism of slots. The processes controlled by such parameters are then available to use in the Max patch.

The Max for Live extension to Ableton Live allows to embed Max patches in the Ableton Live sequencer. Through the API provided, one can control the execution of various elements of the sequencer in Max; automations in Live can also be used to send data to Max patches at a given time. A method for dynamic patching of Max abstractions based on CommonLisp has been proposed by Thomas Hummel [START_REF] Hummel | A Common Lisp interface for dynamic patching with the IRCAM signal processing workstation[END_REF] to reduce resource usage by enabling and disabling subpatches at different points in the execution of a program. This has the advantage of saving computing power for the active elements of the score.

Dataflows and especially synchronous dataflows have seen tremendous usage in the music and signal processing community. A list of patterns commonly used when developing dataflow-based music software is presented in [START_REF] Pau Arumı | A dataflow pattern catalog for sound and music computing[END_REF]. Formal semantics are given in [START_REF] Benveniste | Data-flow synchronous languages[END_REF]. Specific implementation aspects of dataflow systems are discussed in the Handbook of Signal Processing Systems [START_REF]Handbook of Signal Processing Systems[END_REF].

Dynamicity in dataflows is generally separated in two independent aspects: dynamicity of the data, and of the topology. The first relates to the variability on the streams of tokens, while the second is about changes to the structure of the graph. Boolean parametric dataflows [START_REF] Bempelis | Boolean Parametric Data Flow Modeling-Analyses-Implementation[END_REF] have been proposed to solve dynamicity of topology, by introducing conditionals at the edges.

Temporal formalism

This work implicitly uses the OSSIA formalism [START_REF] Celerier | OSSIA: Towards a unified interface for scoring time and interaction[END_REF] in its examples to provide primitives relative to the evolution of time: time constraints (horizontal lines), time nodes (vertical lines). The elements of its syntax are presented in fig. 1.

It is important to note that any other system of temporal relationships between processes could be used instead. As can be seen in fig. 3, there are no relationships between f 1 and f 2 in the temporal graph.

Definitions

f 1 f 2 (a) f 1 f 2 (b) f 1 f 2 (c)
We call process an entity that consists in a function f , an associated state, any number of inputs and output ports, and an activation status. f has a single argument t ∈ R + . The execution of f may read any number of tokens from the inputs and write any number of tokens to the outputs.

The function associated to an inactive process may not be executed. We rely on two families of graphs for defining the execution of a program:

• Synchronous dataflow graphs between processes:

G d (V d , E d )
where V d is the set of processes and E d the set of data bindings between processes. • Temporal graphs, based on the OSSIA formalism:

G t (V t , E t ) where V t is the set of time nodes and E t is the set of time constraints in a score. For coherency, we call these graphs temporal graphs. In the following, we consider a program consisting in a dataflow, and a temporal graph. A program may consist in more than a single temporal graph: they are defined as processes themselves, which provides them with time information.

Each time constraint has an associated set of references to processes. A process may only be executed if it is referenced at least once in a time constraint, at the exception of a special "main" process that acts as an entrypoint.

The execution of a program is synchronous and driven by a scheduler. At each tick, the state of each temporal graph is updated with the following informations:

• Which processes are currently activated.

• For how long these processes have been activated. This is done according to the various events that occur and may change the order of activation of processes.

Processes are then sorted according to their dependencies and activation status, and finally executed.

Throughout this paper, we will use the execution traces in fig. 4a and fig. 4b as running example, as well as the relationships between f 1 and f 2 present in fig. 2.

f 1 f 2 Figure 3:
The example temporal graph we use: both f 1 and f 2 can start at any time. f 1 and f 2 both have a given, finite duration.

f 1 f 2 t 0 t 1 t 2 (a) A possible trace of execu- tion for f1 and f2 f 1 f 2 t 0 t 1 t 2 (b) Another trace of execution

Environment, implicit and explicit connections

In the data flow paradigm generally used in music software, nodes are linked together through connections in their respective input and output ports. This work extends the data flow approach with a permanent external environment, that contains a mapping of keyvalue pairs. Such a pair is called a variable.

Keys are specified with OSC-like [START_REF] Freed | Features and Future of Open Sound Control version 1.1 for NIME[END_REF] addresses: /foo/bar and values can be any kind of data: numbers, strings, etc. The values of the environment may vary independently of the execution of the program: for instance elements of the environment may be changed asynchronously through the network, graphical widgets or physical controls. We then have to provide a mean to use the values of this environment to the dataflow. Thus, we extend the input and output ports with the following explicitness semantic:

• An explicit port is a port that has been connected manually to another port. An input port may only read tokens from the output port it is connected to. This connection is static and will not change for the duration of the execution.2 • An implicit port is a port that has not been connected to another port. It may dynamically read and write to any number of addresses from the environment to perform its work. During a tick, ports have access to three sets of values, corresponding to scopes:

• Global scope: The values that were in the environment at the beginning of the tick. These values are accessible to every process. • Local scope: The values produced by previous implicit output ports in the dataflow. Section 4 presents the various policies that nodes can leverage to use these values. The local scope is cleared at the beginning of a tick. The values written to it are committed to the global environment at the end of the tick. • Connection scope: the explicit scope between two ports; the data flowing from one output port can only go to input ports it is connected to. This is the explicit case. For a given execution following fig. 2a, the evolution of such parameters would behave as in table 1.

Address Tick After f 1 After f 2 Tick Global /a a 0 a 0 a 0 f 2(f 1(a 0 )) Local /a ∅ f 1 (a 0 ) f 2(f 1(a 0 )) ∅

Relationships

We are interested in the relationships between nodes of the dataflow graph when they produce compatible tokens, whether the production is specified implicitly or explicitly, and when taking into account deactivated nodes. That is, given a node of the dataflow executing and producing tokens, we must define which following nodes, if any, will receive the tokens and when will they execute. We propose three relationships: strict, glutton, and delayed.

These relationships are expressed between ports of two nodes of the dataflow. Two nodes may not always be explicitly connected to each other through a cable. We have to provide an order between them since execution requires a total ordering of nodes.

For this, an additional set of directed edges between nodes of the dataflow is used to provide this order. Methods to set up these edges are discussed in section 5.

Strict relationship

In a given tick, an execution of a node engaged in a strict relationship with another node depends on the other node being active.

For instance, take the case in fig. 4a where f 1 and f 2 both read from a and write to a where a is an address. We use the dataflow given in fig. 2a.

Let commit(a, x) be the function that commits a value x to the address a in the local scope, and pull(x) the function that reads the value of the address x from the global scope. We assume that f 1 , f 2 always have access to this information. We will get the following behaviors during each slice:

• During t 0 : ∅.

• During t 1 : commit(a, (f 2 • f 1 )(pull(a))).

• During t 2 : ∅. A strict relationship between two nodes may only be defined through an explicit connection.

This relationship should be used when a computation does not make sense on its own.

Glutton relationship

An execution of a node will happen even if the nodes it is connected to are not active; instead, data will be read and written from the environment.

If we take the same case than previously, the behavior is:

• t 0 : commit(a, f 1 (pull(a))). • t 1 : commit(a, (f 2 • f 1 )(pull(a))). • t 2 : commit(a, f 2 (pull(a)
)). This relationship may be explicit or implicit. In the explicit case, the output of f 1 goes to the input of f 2 through a cable. If an address has been specified for each port in addition to the explicit connection:

• If f 1 is not active, f 2 reads from the local scope instead, or the global scope if the required address is not available. • If f 2 is not active, f 1 writes to the local scope instead. Such a behavior is conceptually similar to a guitarist's pedal board: not all pedals will always be active, but we want the signal to keep flowing even if a pedal is disabled.

Delayed relationship

A connection between an output and an input is delayed through bufferisation in a queue.

The delayed connection can behave in two ways:

• Readers of the buffer always start from the same point: the beginning of the previous function in the callback chain. The frame pointer would be located in each delayed connection, and would not be shared between processes. • Readers of the buffer continue from the latest read position. The frame pointer would be located in the source port, and would be shared across all processes reading from it. This behavior can be useful when multiple functions should apply successively to a single buffer, as in fig. 6. However, it would also create concurrent accesses problems if two nodes happened to read an output at the same time. Arumi presents in [START_REF] Pau Arumı | A dataflow pattern catalog for sound and music computing[END_REF] the advantages and drawbacks of storing tokens at the output or input ports.

This relationship has to be specified explicitly to allow for the tokens to be buffered.

If we have a delay connection from f 1 to f 2 , the first call to f 2 will use the first value that was produced by f 1 . We also define a strictness level for the delayed connection. In the strict case, a node will only be able to execute if the source has produced enough tokens.

That is, in fig. 5, f 2 would only execute during t 1 .

f 1 f 2 t 0 t t 2

Default behaviors for orders

We assess here the various mechanisms possible to specify the dependencies between nodes of the dataflow. Information provided in the temporal graph can be leveraged to connect the nodes at runtime in a fashion that would make sense to composers & authors. By default, any node without preceding nodes would strive to be scheduled at the earliest possible time.

Connections between ports imply a partial ordering between nodes, hence we only consider the ordering between implicitly connected nodes of the dataflow.

Manual ordering

In this case, the author explicitly specifies an order by setting up an edge between two nodes. This is the slowest process, but which gives the most precise specification.

Hierarchical ordering

We follow the hierarchical organization of the temporal graphs: each time constraint has an ordered list of processes, and each time constraint is itself ordered relative to others in a given temporal graph. This gives an order between processes, which does not require the composer to manipulate the dataflow unless a specific data connection has to be established.

Temporal ordering

In this case, the temporal order in which objects are executed becomes the order of chaining in the dataflow.

With the OSSIA semantics, this order could change at each run of a score, as showcased in fig. 7.

• t 0 : f 1 . • t 1 : f 2 • f 1 . • t 2 : f 2 .
(a) Glutton execution in the order of the fig. 4a •

t 0 : f 2 . • t 1 : f 1 • f 2 . • t 2 : f 1 . (b) Glutton execution in the case of fig. 4b

Implementation considerations

Multiple points discussed in this article can be left to the decision of designers of dataflow systems.

Compromises in dynamicity

A first choice that such a designer ought to make would be the level of dynamicity of the system. For instance: would nodes of the dataflow have statically, fixed input and output addresses, or would they be defined and routed dynamically at each tick. The first case allows for better performance: more functional dependencies could be checked and set-up statically. The second enables new behaviors: for instance, a node could write a value to a random parameter at each tick to create fuzzing effects. A second choice is the use of scopes and the behavior when a given scope does not have the required value. If an input port tries to read from an address /a, would the implementation allow it to read from the global scope if the value is not available in the local scope? It is up to the designer of the software to choose whether a port can work with any permutation of ports:

• When connected explicitly,

• With the local scope,

• With the global scope.

Pattern matching

More dynamic behaviors could also be achieved by allowing to use patterns instead of addresses in the port definitions. The functions we use in our example, as defined in Pure Data.

For instance, instead of accepting data from a single source, a port can specify an input pattern such as: /foo.*/bar/b[a-zA-Z], as proposed in the OSC specification.

Upon execution, the input stream of the port would contain the list of values corresponding to the matching addresses.

Given a global environment with the variables:

/foo/bar/ba 1.0 /foo .1/ bob/bu 2.0 /foo .2/ bar/be -1.0 /foo .42/ bar/bo -3.0 Such a pattern would yield the tokens -1.0 and -3.0 at the input of the port matching the pattern.

Default behaviors

Default behaviors can be encoded in any hierarchical unit; for instance, the global scope. Likewise, each temporal graph could also be set-up with a default connection type. We propose a default glutton behavior; however usability studies should be made to determine the most user-friendly default.

Reference implementation

An implementation is being developed as an extension to the OSSIA library 3 and i-score software 4 . This implementation uses PureData [START_REF] Miller Puckette | Pure Data: another integrated computer music environment[END_REF] through libpd [START_REF] Brinkmann | Embedding pure data with libpd[END_REF] to provide function execution with multiple ports with primitives useful for musical creation. As such, it allows to work with audio, midi, and messages.

The C++ implementation of the execution algorithm, provided in the OSSIA library, is not tied in any way to Pure-Data or any other environment: PureData is used as an example of implementation of a node to leverage an easy and well-known method to produce generators and filters with different kinds of inputs and outputs, which allows to cover the whole set of features. Other nodes can be implemented through inheritance of a set of C++ classes. As such, the processes currently available in i-score (automations, Javascript code, MIDI piano roll) and in i-score-audio (sound file reading, Faust and LV2 effects) are being ported to this new execution model. In terms of user interface, PureData patches appear as nodes with their inputs and outputs in i-score. There are two views: the main view, temporal and hierarchical, which allows to position the nodes in time, draw automations, etc., and the patching view which allows to connect nodes together and set the relationship types. The temporal view instead has easily accessible text fields that allow setting input and output addresses for each port.

f 1 f 2 f 1 f 3 f 4 f 5 f 5

Applied example: generative music

We present here an example that leverages patches built with Pure Data [START_REF] Miller Puckette | Pure Data: another integrated computer music environment[END_REF]. Figure 8 present the Pd patches used. Fig. 9 presents the data relationships between the Pd patches, with the mapping of inputs and outputs to addresses of the environment. The inlets and outlets are ordered so that audio ports come first and message ports come afterwards. Finally, fig. 10 presents the temporal score that orchestrates the execution of the Pd patches.

The execution happens as follows:

1. For a few milliseconds, nothing happens. 2. f 3 is started. However, there is a strict dependency between f 3 and f 4 : no sound is produced; f 3 is disabled. 3. f 1 is started. Since f 3 is disabled, it writes /note to the environment. 4. f 1 stops, and a few milliseconds afterwards, f 4 starts, which allows f 3 to execute. f 3 uses the last value of /note that was put in the global scope by f 1 . f 3 fetches the value of /vol in the environment and f 4 fetches the value of /filt there as well. Notice that f 3 's parent time constraint is dashed: it will execute until it is manually stopped.

The sound that can be heard is a single tone with some amount of high-pass filtering. 5. f 2 starts: random notes will be generated at a lower tempo and put at the /note input of f 3 directly, bypassing the environment. 6. f 5 starts: the low-pass filter adds itself after the highpass filter. 7. f 2 stops: the sound reverts to a continuous tone (the last that was written, again). 8. f 1 starts: tones are generated again, but with a faster tempo. 9. f 4 stops: there is no sound anymore due to the strict dependency. f 5 applies its low-pass filter to silence. 10. f 5 stops, and just afterwards f 5 starts. Since f 5 was in a delayed relationship with f 4 , the sound produced corresponds to the sound that was heard at the beginning of f 4 , with both f 4 's high pass filtering, and f 5's low-pass filtering.

Conclusion

Throughout this paper, the effects of adding macro-temporal semantics to dataflows were studied. The first step is to introduce an environment that allows execution of a program to continue if not all the nodes of a dataflow are currently being executed. Then, we study the new possibilities offered by the presence of the environment by the different ways to interpret the absence of execution of a node. This includes matching nodes together through pattern matching, and distinct policies of execution that can take into account the evolution of the program in time. Such global environments have been implicitly present in multiple dataflow-based software; however they are not given an explicit existence. For instance, Max externals generally handle their global state through static C variables. Making it explicit allows for better understanding of the execution of a program, and may enable further optimization opportunities.

After discussing the various choices left to the implementor, an example leveraging multiple PureData patches scheduled through an i-score score is explained.

A further goal for this work is to extend the definition not only to work with a single variable of time, but to any kind of activation mechanism: for instance, evolution of a position in a 3D space, etc.

The paper mostly centered around a single dataflow. A meaning has been proposed for multiple dataflows: they could be used as distinct variable scopes. If the temporal graph has hierarchical features, its use as a scoping mechanism should also be envisioned.

Figure 2 :

 2 Figure 2: Possible dataflows between f 1 and f 2 .As can be seen in fig.3, there are no relationships between f 1 and f 2 in the temporal graph.

Figure 4 :

 4 Figure 4: Process activation traces corresponding to the graph given in 3

Figure 5 : 1 f 2 f 3 f 4 Figure 6 :

 5146 Figure 5: Another execution trace, stemming from a different score than the one presented in fig. 3. f 2 's input corresponds to f 1 's output, delayed: this creates a causality problem.

Figure 7 :

 7 Figure 7: Executions with a temporal ordering

(a) f1, f 1 :

 1 note generator. (b) f2: note generator, at a lower tempo. (c) f3: synthesizes the input note, sets the volume. (d) f4: high-pass filter.(e) f5, f 5 : low-pass filter.

Figure 8 :

 8 Figure 8: The functions we use in our example, as defined in Pure Data.

Figure 9 :

 9 Figure 9: The dataflow relationships between instances of f 1,..5 in the program. The global environment contains variables for /vol and /filt when the execution starts. A PureData patch with similar semantics would use additionally throw~, catch~, send, receive, delwrite~, delread~, tabwrite~, tabread~between nodes, and UDP & OSC receivers and senders to read and write from the environment.

Figure 10 :

 10 Figure 10: The temporal relationships between instances of f 1,..5 in the program.

Table 1 :

 1 Evolution of a variable in the global and local scope during the execution of a tick, in the case of an implicit connection. Both f 1 and f 2 are active. "Tick" indicates the beginning of a new tick; the temporal progression is left-to-right.

This mechanism allows for new behaviors during the creation of a dataflow program.

Not to be mistaken with the Perl language commonly used for text processing

Reactive environments would of course be able to alter such connections at run-time; relevant mechanisms are outside of the scope of this paper.