Jean-Louis Giavitto
email: giavitto@lri.fr

Dominique De Vito

Olivier Michel

Semantics and Compilation of Recursive Sequential Streams in 81/2

Keywords: stream, clock, compilation of dataflow graphs

Recursive definition of streams (infinite lists of values) have been proposed as a fundamental programming structure in various fields. A problem is to turn such expressive recursive definitions into an efficient imperative code for their evaluation. One of the main approach is to restrict the stream expressions to interpret them as a temporal sequence of values. Such sequential stream rely on a clock analysis to decide at what time a new stream value must be produced. In this paper we present a denotational semantics of recursively defined sequential streams. We show how an efficient implementation can be derived as guarded statements wrapped into a single imperative loop.

Introduction

To simplify the formal treatment of a program, Tesler and Enea [START_REF] Tesler | A language design for concurrent processes[END_REF] have considered single assignment languages. To accommodate loop constructs, they extend the concept of variable to an infinite sequence of values rather than a single value. This approach takes advantage of representing iterations in a "mathematically respectable way" [START_REF] Wadge | Lucid, the Data flow programming language[END_REF] and to quote [START_REF] Waters | Automatic transformation of series expressions into loops[END_REF]: "series expressions are to loops as structured control constructs are to gotos". Such infinite sequences are called streams and are manipulated as a whole, using filters, transductors, etc.

This approach has led to the development of the stream data structure and the dataflow paradigm, according to a large variety of circumstances and needs. Since the declarative programming language Lucid [START_REF] Wadge | Lucid -A formal system for writing and proving programs[END_REF], more and more declarative stream languages have been proposed: Lustre [START_REF] Caspi | LUSTRE: A declarative language for programming synchronous systems[END_REF] and Signal [START_REF] Le Guernic | Signal, a dataflow oriented language for signal processing[END_REF] in the field of real-time programming, Crystal [START_REF] Chen | A parallel language and its compilation to multiprocessor machines or VLSI[END_REF] for systolic algorithms, Palasm [START_REF] Schmitz | Software aids in PAL circuit design, simulation and verification[END_REF] for the programming of PLD, Daisy [START_REF] Johnson | Synthesis of Digital Designs from Recursion Equations[END_REF] for VLSI design, 81/2 [START_REF] Giavitto | A synchronous data-flow language for massively parallel computer[END_REF] for parallel simulation, Unity [START_REF] Chandy | Parallel Program Design -a Foundation[END_REF] for the design of parallel programs, etc. Moreover, declarative definitions of streams can be a by-product of the data-dependence analysis of more conventional languages like Fortran. In this case, a stream corresponds to the successive values taken by a variable, e.g. in a loop.

Synchronous Streams

Synchronous streams in Lustre or Signal have been proposed as a tool for programming reactive systems. In these two languages, the succession of elements in a stream is tightly coupled with the concept of time: the evaluation order of the elements in a stream is the same as the order of occurrence of the elements in the stream [START_REF] Plaice | From abstract time to real time[END_REF]. This is not true in Lucid, where the computation of element i in a stream A may require the computation of an element j > i in A. In addition, synchronization between occurrences of events in different streams is a main concern in Lustre and Signal. Lustre and Signal rely on a clock analysis to ensure that synchronous expressions receive their arguments at the same time (see [START_REF] Benveniste | Special section: Another look at real-time programming[END_REF] and [START_REF] Halbwachs | Synchronous programming of reactive systems[END_REF] for a general introduction to synchronous programming). For example, the expression A + B where A and B are streams, is allowed in Lustre or Signal only if the production of the elements in A and B takes place at the same instants (and so does the computation of the elements of A + B). This requires that the streams A, B and A + B share a common reference in time: a clock. Timed flow, synchrony, together with a restriction on stream expressions to ensure bounded memory evaluation [START_REF] Caspi | Clocks in dataflow languages[END_REF], make Lustre and Signal especially suitable tools to face real-time applications.

Sequential Streams

Sequential streams in 81/2 share with the previous approach the idea of comparing the order of occurrence of events in different streams. But, in contrast with the previous approach, the expression A + B is always allowed in 81/2 emphasizing on a single common global time. The instants of this time are called ticks. The 81/2 clock of the stream is specified by the sequence of ticks where a computation must occurs to ensure that, at each instant of the global clock, the relationship between the instantaneous values of the streams A, B, and A + B is satisfied. Given streams A and B, it suffices to recompute the value of A + B whenever a change happen to A or to B. The value of a stream can be observed at any time and this value is the value computed at the last change.

The idea of a clock in 81/2 corresponds more closely to the time where values are computed rather than to the time when they must be consumed. In addition, a stream value can be accessed at any time. This makes 81/2 unable to express realtime synchronization constraints (for example, asserting that two streams must have the same clock, like the synchro primitive in Signal), but makes more easy arbitrary combinations of trajectories in the simulation of dynamical systems [START_REF] Michel | A data-parallel declarative language for the simulation of large dynamical systems and its compilation[END_REF]. We call 81/2 streams sequential streams to stress that they have a strict temporal interpretation of the succession of the elements in the stream (like Lustre and Signal and unlike Lucid) without constraining to synchronous expressions.

Compiling Recursive Stream Equations into a Loop

The clock of a synchronous stream is a temporal predicate which asserts that the current value of the stream is changing. The inference, at compile time, of the clock of a stream makes the compiler able to check for consistencies (for example no temporal shortcuts between stream definitions) and to generate straight code for the computation of the stream values instead of using a more expensive demand-driven evaluation strategy.

Compiling a set of recursive stream equations consists in generating the code that enumerates the stream values in a strict ascending order. The idea is just to wrap a loop, that enumerates the ticks, around the guarded expression that computes the stream values at a given tick. This is possible because we only admit operators on streams satisfying a preorder restriction. The problem is to derive a static scheduling of the computations and to generate an efficient code for the guards corresponding to the clocks of the stream expressions.

Structure of the paper. In the following section, we sketch L a declarative language on sequential streams. In section 3 we give a denotational semantics of L based on an extension of Kahn's original semantics for dataflow networks [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF]. The main difference between our semantics and that of Plaice [START_REF] Plaice | Sémantique et compilation de LUSTRE un langage déclaratif synchrone[END_REF] or Jensen [START_REF] Jensen | Clock analysis of synchronous dataflow programs[END_REF] relies in a simpler presentation of clocks. Moreover, our proposition satisfies a property of consistency between clock and stream values: if the clock ticks, the corresponding stream value is defined. Section 4 presents the translation of the clock definitions from the denotational semantics to a boolean expression using C as the target language. The process involves the resolution of a system of boolean expressions. Section 5 presents a benchmarks corresponding to the performances of a 81/2 program compiled using the previous tools compared to an equivalent hand-coded C program: it compares quite well. Finally, section 6 examines related works.

Recursively Defined Sequential Streams

Conventions. We adopt the following notations. The value of a stream is a function from a set of instants called ticks, to values called scalar values. We restrict ourself in this paper to totally ordered unbounded countable set of ticks and therefore we use N to represent this set ( [START_REF] Andersen | An asynchronous process algebra with multiple clocks[END_REF] and [START_REF] Nguyen | Représentation et construction d'un temps asynchrone pour le langage 81/2[END_REF] show possible uses of a partially ordered set of instants). The current value of a stream A refers to the scalar value at some tick t and is denoted by A(t). The current value of a stream may be undefined, which is denoted by nil. A sequential stream is more than a function from ticks to scalar values: we have to represent the instants where a computation takes place to maintain the relationship asserted by the definition of the stream. The set of ticks characterizing the activity of the stream A is called its clock and written cl(A). For t ̸ = 0, if t ̸ ∈ cl(A), then A(t) = A(t -1) because no change of value occurs and therefore the current value is equal to the previous value. If 0 ̸ ∈ cl(A), then A(0) = nil. So, a stream A described by > ; ; 1; ; 2; ; 3; . . . > means that A(0) = nil, A(1) = nil, A(2) = 1, A(3) = 1, A(4) = 2, A(5) = 2, A(6) = 3, etc. The clock of A is the set cl(A) = { 2, 4, 6 . . . }. With this notation, ticks are separated by ";" and a value is given only if the corresponding tick is in the clock of the stream.

A Sequential Stream Algebra

The language L represents the core of 81/2 w.r.t the definition of streams. The set of expressions in L is given by the grammar:

e ::= c | Clock n | x | e1 op e2 | $e | e1 when e2
where c ranges over integer and boolean constants (interpreted as constant streams), n ranges over N, x over the set of variables Id and op over integer and boolean operations such as +, ∧, ==, < etc.

Constant streams. Scalar constants, like 0 or true, are overloaded to denote also a constant stream with clock reduced to the singleton {0} and current value always equal to the scalar c: c(t) = c. A construct like Clock n represents a predefined boolean stream with current value always equal to true and with an unbounded clock (the precise clock is left unspecified).

Arithmetic expressions. An expression like e1 bop e2 extends the scalar operator bop to act in a point-wise fashion on the elements of the stream: ∀t, (A bop B)(t) = A(t) bop B(t). The clock of A bop B is the set of ticks t necessary to maintain this assertion (in a first approximation, it is the union of the clocks of A and B, Cf. section 3).

Delay. The delay operator $, is used to shift "in time" the values of an entire stream.

It gives access to the previous stream value. This operator is the only one that does not act in a point-wise fashion. Consequently, only past values can be used to compute a current stream value, and references to past values are relative to the current one. So, only the last p values of a stream have to be recorded where p is a constant computable at compile time. This restriction enables a finite memory assumption and enforces a temporal interpretation of the sequence of elements in a stream.

Sampling. The when operator is a trigger, corresponding to the temporal version of the if then else construct. It appears also in Lustre and Signal. The values of the stream A when B are those of A sampled at the ticks where B takes the value true (Cf. Tab. 1).

Recursively Defined Sequential Streams

A stream definition in L is given through an equation x = e where x is a variable and e a stream expression. This definition can be read as an equation being satisfied between x and the stream arguments of e.

A definition can be guarded to indicate that it is valid only for some ticks:

A@0 = 33, A = ($A + 1) when Clock 0 .

The first equation is guarded by @0 which indicates that this equation is only valid for the first tick in the clock of A (that is, the first tick of A is also the first tick of the constant stream 33, which is the tick t = 0). The second equation is "universally" quantified and defines the stream when no guarded equation applies. In this paper, the only language we consider for temporal guards is @n where n is an integer which denotes the nth tick in a clock. A L program is a set of such definitions (i.e. guarded or non-guarded equations). For a given identifier x, there can only be a single universally quantified equation and at most one equation quantified by n.

An example of a reactive system using sequential streams. A "wlumf" is a "creature" whose behavior (mainly eating) is triggered by the level of some internal state (see [START_REF] Maes | A bottom-up mechanism for behavior selection in an artificial creature[END_REF] for such model in ethological simulation) More precisely, a wlumf is hungry when its glycaemia subsides under the level value 3. It can eat when there is some food in its environment. Its metabolism is such that when it eats, the glycaemia goes up to the level 10 and then decreases to zero at a rate of one unit per time step. Essentially, a wlumf is made of counters and flip-flop triggered and reset at different rates. The operator {. . .} is used to group sets of logically related stream definitions but we shall not be concerned with this aspect of the language for the rest of the paper .

System wlumf = { hungry@0 = f alse hungry = glycemia < 3 glycemia@0 = 6 glycemia = if eat then 10 else max(0, $glycemia-1)when(Clock 0) fi

eat@0 = f alse eat = $hungry && environment.f ood } System environment = { t@0 = 0 t = $t + 1 when Clock -4 f ood = (0 == (t%2)) } Fig. 1.
The dynamical behaviour of an artificial creature, the "wlumf". The operator % is for modulo and == for testing equality. So f ood is true or f alse depending on the parity of the counter t which progresses randomly at an average rate of 1/4. The operator && is the logical and.

A Denotational Semantics for L

For the sake of simplicity, we assume that guarded equations are only of the form x@0 = e. Therefore, we replace a definition x@0 = e1, x = e2 by a single equation x = e1 fby e2 where fby is a new operator waiting for the first tick in the clock of e1 and then switching to the stream e2. The denotational semantics of L is based on an extension of Kahn's original semantics for dataflow networks [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF]. The notations are slightly adapted from [START_REF] Mosses | Handbook of Theoretical Computer Science, volume 2, chapter Denotational Semantics[END_REF].

Stream Values and Clocks

The basic domain consists of finite and infinite sequences over the sets of integer and boolean values extended with the value nil to represent the absence of a value: ScValue = Bool ∪ Int ∪ {nil} and Value = ScValue * ∪ ScValue ∞ . The operation "." denotes the concatenation of finite or infinite sequences. In Value, u approximates v, written u ≼ v if v = u.w. This order is chosen against the more general Scott order (e.g. used for defining domains of functions [START_REF] Mosses | Handbook of Theoretical Computer Science, volume 2, chapter Denotational Semantics[END_REF]) in accordance with our interpretation of the succession of elements in the stream as the progression in time of the evaluation process.

A first idea to describe timed stream is to associate to the sequence of values, a sequence of boolean flags telling if an element is in the clock of the stream (flag true: ⊤) or not (flag false: ⊥). In other words, a sequence of booleans {⊥, ⊤} is used to represent cl(). For example, the sequence representing the clock of Clock 2 is: ⊤ ⊥ ⊤ ⊥ ⊤ . . . Thus: ScClock = {⊥, ⊤} and Clock = ScClock * ∪ ScClock ∞ . We choose to completely order ScClock by ⊥ < ⊤. The motivation to completely order the domain ScClock is the following: there is no particular reason for a stream definition evaluating into a sequence of undefined values, not to have a defined clock (with no true values). Moreover, if we cannot evaluate the current value of a clock, we obviously cannot evaluate the current value of the corresponding stream and this is observationally equivalent to the value ⊥ in the clock sequence.

By convention, if s is a Clock, then t ∈ s means s(t) = ⊤ and t ̸ ∈ s means s(t) = ⊥. We extend the logical or ∨ by ∨ and the logical and ∧ by ∧ to operate point-wise on Clock: that is, (s

∧ s ′ )(t) = s(t) ∧ s ′ (t) and (s ∨ s ′ )(t) = s(t) ∨ s ′ (t)).
The ordering of clocks is also the prefix ordering.

In the work of Plaice [START_REF] Plaice | Sémantique et compilation de LUSTRE un langage déclaratif synchrone[END_REF] or Jensen [START_REF] Jensen | Clock analysis of synchronous dataflow programs[END_REF], the definition of the clock of a stream is loosely coupled with the value of the stream, in the following sense: a tick can be in the clock of a stream while the current value of the stream is undefined. The simplest example is the expression $e which has the same clock of e but with an undefined value for the first tick in cl(e). On the contrary, we ask for a denotational semantics that ensures that:

t ∈ cl(e) ⇒ e(t) ̸ = nil (1)
A property like ( 1) is natural and certainly desirable but cannot be directly achieved. This is best shown on the following example. Consider the stream defined by:

A = 1 fby (($A + 1) when (Clock 0)) (2)
which is supposed to define a counter increasing every ticks. But, if we assume property (1), then cl(A) can be proved to be {0}. As a matter of fact, 0 ∈ cl(A) because 0 ∈ cl [START_REF] Tesler | A language design for concurrent processes[END_REF] and obviously the first tick in cl(e) is also in cl(e fby e ′ ). Furthermore, a delayed stream $e cannot have a defined value the first time e has a defined value. So, using property (1), it comes that 0 ̸ ∈ cl($A). Furthermore, the value of e when clock0 is defined only when e has a defined value. So, again using property (1), we infer that

cl(A) = ⊤.Ok(cl($A + 1)) = ⊤.Ok(cl($A)) (3)
where the predicate Ok tells if the clock has already ticked: Ok(⊥.s) = ⊥.Ok(s) and Ok(⊤.s) = T rue (the sequence T rue is the solution of the equation T rue = ⊤.T rue).

The clock of $A depends of the clock of A and more precisely, except for the first tick in cl(A), we have cl($A) = cl(A). So, for t ̸ = 0, equation (3) rewrites in:

t ̸ = 0, cl(A)(t) = Ok(cl(A))(t) (4)
Equation ( 4) is a recursive equation with solutions in Clock. This equation admits several solutions but the least solution, with respect to the structure of Clock, is cl(A) = ⊤.F alse (where F alse = ⊥.F alse). This is a problem because we expect the solution T rue.

The collapse of the clock is due to the confusion of two predicates : "having a definite value at tick t" and "changing possibly of value at tick t". Then, to develop a denotational semantics exhibiting a property similar to (1), our idea is to split the clock of a stream A in two sequences D(A) and C(A) with the following intuitive interpretation: D(A) indicates when the first non nil value of A becomes available for further computations and C(A) indicates that some computations are necessary to maintain the relationship asserted by the stream definition.

Semantics of Expressions

We call environment a mapping from variables to Clock or Value. An element ρ of Env is a mapping Id → Clock × Clock × Value. Such an element really represents three environments linking a variable to the two sequences representing its clock and the sequence representing its value.

The semantics of L expressions is defined by the three functions:

D[[ ]], C[[ ]], V[[ ]] : Exp → Env → Value .
The reason of using an element of Env instead of an environment, is the value of an expression involving variable may depend of the clocks

D[[ ]] and C[[ ]] of this variable.
By convention, if ρ ∈ Env, then ρ d , ρc and ρv represents the components of ρ, that is:

ρ(x) = (ρ d (x), ρc(x), ρv(x)).
In addition, we omit the necessary injections between the basic syntactic and semantic domains when they can be recovered from the context. A constant c denotes the following three sequences:

D[[c]]ρ = T rue, C[[c]]ρ = ⊤.F alse, V[[c]]ρ = c ∞ ,
where c ∞ denotes an infinite sequence of c's, i.e. c ∞ = c.c ∞ . The intuitive meaning is that the current values of a constant stream are available from the beginning of time, a computation being needed only at the first instant to build the initial value of the constant stream and the current values being all the same. Some other constants are needed if we want to have streams with more than singleton clocks. This is the purpose of the constant stream Clock n which has an unbounded clock:

D[[Clock n]]ρ = T rue, C[[Clock n]]ρ = dev(n), V[[Clock n]]ρ = T rue,
where dev(n) is some device computing a boolean sequence depending on n, beginning by ⊤ and with an unbounded number of ⊤ values. Variables are looked up in the corresponding environment:

D[[x]]ρ = ρ d (x), C[[x]]ρ = ρc(x), V[[x]]ρ = ρv(x) .
The predefined arithmetic and logical operators are all strict:

D[[e1 bop e2]]ρ = D[[e1]]ρ ∧ D[[e2]]ρ C[[e1 bop e2]]ρ = D[[e1 bop e2]]ρ ∧ (C[[e1]]ρ ∨ C[[e2]]ρ) V[[e1 bop e2]]ρ = V[[e1]]ρ bop V[[e2]]ρ
that is, the value of e1 bop e2 can be computed only when both e1 and e2 have a value. This value changes as soon as e1 or e2 changes its value, when both are defined.

Notice that the definition of C[[e]]ρ takes the form D[[e]

]ρ ∧ (. . .) in order to ensure the property:

∀t, C[[e]]ρ(t) ⇒ D[[e]]ρ(t) (5)
(Cf. section 3.3). For a delayed stream, the equations are:

D[[$e]]ρ = delD(D[[e]]ρ), C[[$e]]ρ = D[[$e]]ρ ∧ C[[e]]ρ V[[$e]]ρ = delV (nil, nil; V[[e]]ρ, C[[e]]ρ)
where delD and delV are auxiliary functions defined by (s, s ′′ are sequences and p, p ′ are scalar values ̸ = nil):

delD(⊥.s) = ⊥.delD(s) delD(⊤.s) = ⊥.s delV (nil, nil; v.s, ⊥.s ′ ) = nil.delV (nil, nil; s, s ′ ) delV (nil, nil; v.s, ⊤.s ′ ) = nil.delV (v, v; s, s ′ ) delV (p, p ′ ; v.s, ⊥.s ′ ) = p.delV (p, p ′ ; s, s ′ ) delV (p, p ′ ; v.s, ⊤.s ′ ) = p ′ .delV (p ′ , v; s, s ′ )
In other words, if t is the first tick for which A has a defined value, then the value of $A becomes available at t + 1. The computation needed for $A takes place at the same instants, as for A, except the first instant, and the values are shifted in time accordingly.

The sampling operator is specified by:

D[[e1 when e2]]ρ = D[[e1]]ρ ∧ D[[e2]]ρ C[[e1 when e2]]ρ = D[[e1 when e2]]ρ ∧ (C[[e2]]ρ ∧ V[[e2]]ρ) V[[e1 when e2]]ρ = trigger(nil; V[[e1]]ρ, C[[e1 when e2]]ρ)
where trigger is defined as:

trigger(p; v.s, ⊥.s ′ ) = p.trigger(p; s, s ′ ) trigger(p; v.s, ⊤.s ′ ) = v.trigger(v; s, s ′ )
The value of the sampling operator can be defined only when both operands are defined. The clock is defined by the (sub)clock of e2 when e2 takes the value ⊤.

Finally, the fby construct takes the first defined element in its first argument and then "switches" to its second argument:

D[[e1 fby e2]]ρ = D[[e1]]ρ C[[e1 fby e2]]ρ = D[[e1]]ρ ∧ f byC(C[[e1]]ρ, C[[e2]]ρ) V[[e1 fby e2]]ρ = f byV (C[[e1]]ρ, V[[e1]]ρ, V[[e2]]ρ)
where:

f byC(⊥.s, b.s ′ ) = ⊥.f byC(s, s ′ ) f byC(⊤.s, b.s ′ ) = ⊤.s ′ f byV (⊥.w, v.s, v ′ .s ′ ) = v.f byV (w, s, s ′ ) f byV (⊤.w, v.s, v ′ .s ′ ) = v.s ′

Semantics of Programs

The semantics of a set of recursive equations {. . . , xi = ei, . . .} is composed of an element ρ ∈ Env assigning domain, clock and values to each stream variables xi in the program. It can be computed as the least fixed point of the function

F (ρ) = [. . . , xi → (D[[ei]]ρ, C[[ei]]ρ, V[[ei]]ρ), . . .]
where [. . . , x → v, . . .] stands for an environment which maps x to v. All auxiliary functions involved are monotone and continuous. Then, the fixed point can be calculated in the standard way as the least upper bound of a sequence of iterations F n starting from the empty environments. We write (D(x), C(x), V(x)) for the value associated to x in the meaning of a program. The simple form of the semantics may accommodate several variations to specify other stream algebra. The affirmation (5) holds for any environment ρ, and then it holds also for the fixpoint: ∀t, C(e)(t) ⇒ D(e)(t)

A proof by induction on the structure of an expression shows that a property similar to [START_REF] Tesler | A language design for concurrent processes[END_REF]

holds between C[[e]] and V[[e]] for any expression e in a program: ∀t, C(e)(t) ⇒

V(e)(t) ̸ = nil. Another result will be extremely useful for the implementation. Once defined, the current value of a stream may change on tick t only if the clock of the stream takes the value ⊤ at t:

∀t, D(e)(t -1) ∧ V(e)(t -1) ̸ = V(e)(t) ⇒ C(e)(t) (7)
the proof is by induction on terms in L.

Example of a counter. As an example, we consider the semantics of the clock of the program (2). We assume that dev(0) = T rue. The semantics of the counter A is defined by the following equations:

D(A) = D(

Compiling Recursive Streams into a Loop

We implement a sequence s as the successive values of one memory location associated with (the current value of) s. We emphasize that successive means here successive in time. The idea is to translate a set of equations {. . . , x = e, . . .} into the imperative program (in a C like syntax): for(;;) { ...; xd = ed; xc = ec; xv = ev; ...; } where xd is associated to the current value of D(x), etc. This implementation is far from the representation needed for Lucid (or for the lazy lists of Haskell) where several elements of a sequence can be present at the same time in the memory so that a garbage collector is involved to remove useless elements from the memory.

With the denotational semantics defined above, this representation implies the update of the three memory locations at each tick (i.e. for each element in the sequence). However, property [START_REF] Le Guernic | Signal, a dataflow oriented language for signal processing[END_REF] implies that it is sufficient to update the memory location representing C(e) only when D(e)(t) evaluates to true. And property [START_REF] Chen | A parallel language and its compilation to multiprocessor machines or VLSI[END_REF] implies that is is sufficient to evaluate V(e)(t) when C(e)(t) evaluates to true. These two conditions are sufficient but not necessary (e.g. Clock 0 has an unbounded clock but its current value is always ⊤). So, a L program can be translated into the following C skeleton: for(;;) { ...; if(xd = ed) { if(xc = ec) { xv = ev; }} ...; } However, translating a set of definitions into imperative assignments is not straightforward because of the recursive definitions: how to evaluate fixed points of sequences expressions without 1) handling explicitly infinite sequences and 2) iterations. In the rest of the section, we will build the tools that are necessary for this translation.

LR(1) Functions

We say that a function f :

ScValue × Value n → Value is LR(1) if: f (m; v1.s1, . . . , vn.sn) = f ′ (m, . . . , vn) . f (f ′′ (m, v1, . . . , vn); s1, . . . , sn)
where f ′ and f ′′ are functions from scalar values to scalar values: f ′ , f ′′ : ScValue n+1 → ScValue. Being LR(1) means that computing f on sequences can be a left to right process involving only computation on scalars, with only one memory location, assuming that the arguments are also provided from left to right.

Suppose F is LR(1); to solve the equation v.s = F (m; v.s) on sequences (v and s are unknown, m is a parameter) it is then sufficient to solve the equation

v = F ′ (m; v) ( 8
)
on scalars and then to proceed with the resolution of s = F (F ′′ (m, v); s). Thus we have to consider the two sequences:

vi = F ′ (mi; vi), mi = F ′′ (mi-1, vi-1), i ≥ 1
obtained by enumerating the successive solutions of (8) starting from an initial value m0. The sequence of vi's is obviously a solution of s = F (s) and moreover, it is the least solution for ≼. The equation ( 8) is called the I-equation associated with the equation s = F (s) (I stands for "instantaneous"). It is easy to show that all the functions involved in the semantics of an expression given in section 3 are LR [START_REF] Tesler | A language design for concurrent processes[END_REF]. This provides the basis for the implementation of declarative sequential streams into an imperative code.

Guarded LR(1) Semantic Equations

It is easy to rephrase the semantic definition of each L construct given in section 3 to make explicit properties ( 6), [START_REF] Chen | A parallel language and its compilation to multiprocessor machines or VLSI[END_REF] and LR [START_REF] Tesler | A language design for concurrent processes[END_REF]. The semantic equations are rephrased in Fig. 2 but due to the lack of place, we omit to rephrase some auxilliary functions. We have explicitly stated the values for a tick t in order to give directly the expressions ed, ec and ev corresponding to C skeleton. The notation s(t) refers to the tth element in sequence s, where element numbering starts 0. Semantics of systems remains the same. We will omit the tedious but straightforward proof by induction on terms to check that the two semantic definitions compute the same thing.

for commodity, let D[[e]]ρ(-1) = ⊥, C[[e]]ρ(-1) = ⊥, V[[e]]ρ(-1) = nil

for any expression e and environment ρ, and assume t > -1 below:

D[[c]]ρ(t) = ⊤ C[[c]]ρ(t) = (t == 0) V[[c]]ρ(t) = c D[[Clock n]]ρ(t) = ⊤ C[[Clock n]]ρ(t) = dev(n, t) V[[Clock n]]ρ(t) = ⊤ D[[x]]ρ(t) = ρ(x)(t) C[[x]]ρ(t) = ρ(x)(t) V[[x]]ρ(t) = ρ(x)(t) D[[e1 bop e2]]ρ(t) = D[[e1]]ρ(t) ∧ D[[e2]]ρ(t) C[[e1 bop e2]]ρ(t) = if D[[e1 bop e2]]ρ(t) then C[[e1]]ρ(t) ∨ C[[e2]]ρ(t) else ⊥ V[[e1 bop e2]]ρ(t) = if C[[e1 bop e2]]ρ(t) then V[[e1]]ρ(t) bop V[[e2]]ρ(t) else V[[e1 bop e2]]ρ(t -1)

D[[$e]]ρ(t) = D[[e]]ρ(t -1) C[[$e]]ρ(t) = if D[[$e]]ρ(t) then C[[e]]ρ else C[[$e]]ρ(t -1) V[[$e]]ρ(t) = if C[[$e]]ρ(t) then delV (nil, nil; V[[e]]ρ, C[[e]]ρ)(t) else V[[$e]]ρ(t -1)

D[[e1 when e2]]ρ(t) = D[[e1]]ρ(t) ∧ D[[e2]]ρ(t) C[[e1 when e2]]ρ(t) = if D[[e1 when e2]]ρ(t) then C[[e2]]ρ(t) ∧ V[[e2]]ρ(t) else ⊥ V[[e1 when e2]]ρ(t) = if C[[e1 when e2]]ρ(t) then V[[e1]]ρ(t) else V[[e1 when e2]]ρ(t -1) D[[e1 fby e2]]ρ(t) = D[[e1]]ρ(t) C[[e1 fby e2]]ρ(t) = if D[[e1 fby e2]]ρ(t) then f byC(C[[e1]]ρ, C[[e2]]ρ)(t) else ⊥ V[[e1 fby e2]]ρ(t) = if C[[e1 fby e2]]ρ(t) then f byV (C[[e1]]ρ, V[[e1]]ρ, V[[e2]]ρ)(t) else V[[e1 fby e2]]ρ(t -1)
Fig. 2. Semantics of L in an explicit LR(1) form.

I-system Associated with a Program

x d = F ′ d [x](x md ; . . .), xc = F ′ c [x](xmc; . . .), xv = F ′ v [x](xmv; . . .) .
For each variable in the program there is one equation defining

Solving Efficiently an I-system

The problem of computing the least fixed point of a set of equations on sequences has now be turned into the simpler problem of computing the least solution of the I-system, a set of equations between scalar values. A straightforward solution is to compute it by fixed point iterations. If l is the number of expressions in the program, the iterations must become stationary after at most l steps, because the scalar domains are all flat. The problem is that this method may require l steps (l can be large) and that each step may require the computation of all the l expressions in the program.

Consider the dependence graph of an I-system: vertices correspond to variables and an edge from x to y corresponds to the use of x in the definition of y. This graph may be cyclic if the given definitions are recursive. For instance in a@0 = b, a = $a or b which defines a signal a always true after the first true value in b, C

[[a]] depends of C[[a]] (and also of C[[b]] which imposes its clock).

Without recursive equations, solving the I-system is easily done by simple substitutions: a topological sort can be used to order the equations at compile time. Non strict operators, like the conditional expression if...then...else..., can rise a problem because they induce a dependence graph depending on the value of the argument, value which is known only at evaluation time. Most of the time, it is possible to consider the union of the dependence graphs without introducing a cycle (which enables a static ordering of the equations). For the remaining rare cases, more sophisticated techniques, like conditional dependence graphs [START_REF] Benveniste | Synchronous programming with events and relations: the SIGNAL language and its semantics[END_REF], can be used to infer a static scheduling. Solving the sorted system reduces to compute, in the order given by the topological sort, each right hand side and update the variables in the left hand side. In addition, the environment is implicitly implemented in the x d , xc, xv, . . . variables.

For cyclic dependence graphs, the vertices can be grouped by maximal strongly connected components. The maximal strongly components form an acyclic graph corresponding to a partition of the initial I-system into several sub-systems. We call this graph the c-graph of the system (c stands for "component"). A root in the c-graph is a minimal element, that is, a node without predecessor (because c-graphs are acyclic, at least a root must exist). Each root of the c-graph represents a valid sub-system of the I-system, that is, a system where all variables present are defined (this is because roots are minimal elements). The solution of the entire I-system can be obtained by solving the sub-systems corresponding to the roots, propagating the results and then iterating the process. The processing order of the components can be determined by a topological sort on the c-graph.

So, we have turned the problem of solving an I-system into the problem of solving a root, that is: solving a subsystem of the initial system that corresponds to a maximal strongly connected component without a predecessor. In a root, we make a distinction between two kinds of nodes: the V -nodes corresponding to expressions computing the current value of some stream and the B-nodes generated by the computation of the current boolean value for the clock of some stream. It can be seen that if there is a cycle between V -nodes, there is also a corresponding cycle involving only B-nodes (because the computation of D [[e]] and C [[e]] involves the same arguments as the computation of V[[e]] for any expression e).

First, we turn our attention on cycles involving only B-nodes: they correspond to λx.x, ∧, ∨ and if then else operations between ScClock. We assume that the root is reduced, that is, each argument of a B-node is an output of another B-node in the root (e.g., expressions like ⊤ ∧ x are reduced to x before consideration). Then, the output of any node in the root reduces to ⊥. This is because a B-node op is strict (i.e. op(. . . , ⊥, . . .) = ⊥). Consequently, the fixed point is reached after one iteration. Now, we turn our attention on cycles involving only V -nodes. Circular equations between values result also in circular equations between domains and clocks. The associated clock then evaluates to f alse so there is no need to compute the associated value (which therefore remains nil).

A cycle involving both V -nodes and B-nodes is not possible inside a reduced root because there is no operator that promotes a clock into a value (clocks are hidden objects to the programmer, appearing at the semantical and implementation levels only).

Evaluation

The approach described in this paper has been fully implemented in the experimental environment of the 81/2 language [START_REF] Michel | Design and implementation of 81/2, a declarative data-parallel language[END_REF][START_REF] Michel | 81/2 : data-parallelism and data-flow[END_REF][START_REF] Vito | Effective SIMD code generation for the high-level declarative data-parallel language 81/2[END_REF] (available at ftp://ftp.lri.fr/LRI/ soft/archi/Softwares/8,5). The current compiler is written in C and in CAML. It generates either a target code for a virtual machine implemented on a UNIX workstation or directly a straight C code (no run-time memory management is necessary).

To evaluate the efficiency of our compilation scheme, we have performed some tests. We have chosen to compare the sequential generated C code from the 81/2 equations with the hand-coded corresponding C implementation (because the application domain of 81/2 is the simulation of dynamical systems, tests include a standard example of the numerical resolution of a partial differential equation through an explicit scheme and an implementation of the Turing's equations of diffusion-reaction). We details the results of the benchmark for the numerical resolution of a parabolic partial differential equation governing the heat diffusion in a thin uniform rod (Cf. Tab. 2).

The mean execution time corresponding to the compiler generated code without optimization is about 2.9 times slower than the hand-written one. The slight variation of the ratio with the number of iterations (which is the tick at which the program stops) are explained by a cache effect [START_REF] Vito | Semantics and compilation of sequential streams into a static SIMD code for the declarative data-parallel language 81/2[END_REF].

Four optimizations can be made on the generated C code to improve the performances. The first two concern the management of arrays (array shifting instead of gather/scatter and array sharing instead of copying for the concatenation) and does not interfere with the stream compilation scheme.

The last two optimizations have to do with the management of streams. For each delay $F appearing in the 81/2 code, a copy has to be performed. The current value of a stream F is copied as many times as F is referenced by the delay operator. So, the sharing of delay expressions removes the useless copies. Moreover, the copy of expressions referenced by a delay operator (x d into x md , etc.) can be time-consuming, Table 2. The heat diffusion resolution. Each element represents the ratio of the generated code execution time by the hand-written one. They both have been compiled using the GNU C compiler with the optimization option set -O. The evaluation has been performed on a HP 9000/705 Series under the HP-UX 9.01 operating system. The first number represents the ratio without high-level optimizations, the second with the four optimizations sketched. The ratio does not depend of the number of iterations, i.e. the number of stream elements that are computed, which shows the strict temporal nature of the stream evaluation scheme. especially when large arrays are manipulated. However, the copy of the value of a stream F is not required, under some conditions (a similar optimization is described in Lustre [START_REF] Halbwachs | Generating efficient code from dataflow programs[END_REF]). If these conditions are not met, it is however possible to discard the delay copy. But it is necessary to have a temporary variable associated with the stream $F . This kind of delay optimization consists in the definition of a single variable for each of the streams F and $F and to alternatively let it play the role of F or $F (a similar optimization is proposed in Sisal [START_REF] Cann | Advanced array optimizations for high performance functional languages[END_REF]). The second number in Tab. 2 underlines the impact of these improvements: the mean ratio decreases to 1.5. Actually, it goes as far as 1.1 if we do not take into account the tests for which the rod has less than 100 elements, that is a size such that control structures are not negligible. However, it must be noted that there is a large room for further optimizations. More benchmarks can be found in [START_REF] Vito | Semantics and compilation of sequential streams into a static SIMD code for the declarative data-parallel language 81/2[END_REF].

Number of iterations

Conclusion

Denotational semantics of recursive streams goes back to [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF]. Equivalence between the denotational semantics and the operational behavior of a dataflow networks is studied in the work of [START_REF] Faustini | An operational semantics of pure dataflow[END_REF]. Denotational semantics of timed flow begins in the framework of Lustre with [START_REF] Bergerand | LUSTRE: un langage déclaratif pour le temps réel[END_REF][START_REF] Plaice | Sémantique et compilation de LUSTRE un langage déclaratif synchrone[END_REF]. A very general framework has been formulated in [START_REF] Benveniste | A denotational theory of synchronous reactive systems[END_REF] but its sophistication makes its use uneasy. The work of Jensen [START_REF] Jensen | Clock analysis of synchronous dataflow programs[END_REF] formalizes clock analysis in terms of abstract interpretation and extends the works of Plaice and Bergerand. We should mention the work of Caspi and Pouzet [START_REF] Caspi | Synchronous Kahn networks[END_REF]: the clock calculus there is different than most other in not using fixpoints. Our proposal fills a gap left open in these approaches by providing a denotational semantics of clock tightly coupled with the denotational semantics of values. Notice that there is a great difference between our handling of time and the synchronous concept of time in reactive systems: our clocks indicates when the value of a stream has to be recalculated as a result of other changes in the system, while clocks in reactive systems tells when the value of a signal is present.

If D(x) or C(x) reduces to F alse, there is no value produced in the sequence V(x). This situation is a kind of deadlock. Deadlocks detection in declarative stream definitions are studied in [START_REF] Wadge | An extensional treatment of dataflow deadlock[END_REF][START_REF] Lee | Synchronous dataflow[END_REF] and for lazy lists in [START_REF] Sijtsma | On the productivity of recursive list definitions[END_REF]. Thanks to the ROBDD [START_REF] Bryant | Graph based algorithms for boolean function manipulation[END_REF] representation of clocks, it is possible to detect at compile-time some cases of such definitions. Clock reducing to T rue can also be detected and their implementation optimized. Signal has developed a sophisticated clock calculus to solve clock equations (dynamical system over Z/3Z and Grobner bases). This approach is powerful but computation consuming. Its extension to our own stream algebra is not obvious and must be carefully studied.

The transformation of stream expressions into loops is extensively studied in [START_REF] Waters | Automatic transformation of series expressions into loops[END_REF]. The expressions considered do not allow recursive definitions of streams. Our proposition handles this important extension as well as "off-line cycle" expressions and is based upon the formal semantics of the expressions. We share the preorder restriction, i.e.: the succession of stream elements must be processed in time ascending order (this is not the case in Lucid). We focus also on unbounded streams and therefore we do not consider operations like concatenation of bounded streams. The work in [START_REF] Parhi | Static rate-optimal scheduling of iterative data-flow programs via optimum unfolding[END_REF] considers the static scheduling of a class of dataflow graphs used in digital signal processing. The translation of a (recursive) stream definition into a (cyclic) dataflow graph is straightforward. Their propositions apply but are limited to the subset of "on-line" programs [START_REF] Aho | The design and analysis of computer algorithms[END_REF]. This restriction excludes the sampling operator and requires the presence of, at least, one delay on each cycle of the dataflow graph.

The benchmarks performed validate the approach used in the compilation of the clock expressions although all the needed optimizations are not currently implemented. When made by hand, the ratio between the C version and the 81/2 version lies between 1.1 and 2.3 (in favor of C) for the benchmark programs. As an indication, the handwritten C program for the Turing example of diffusion-reaction has 60 lines of code whereas the 81/2 program is only 15 lines long (which are the straight transcription of the mathematical equations governing the process). Thus the price to pay for high expressivity (declarative definition of high-level objects) is not always synonym of low efficiency provided that some carefully tuned optimization techniques are used. Nevertheless, the cost of the control structures cannot be neglected and several optimizations must be performed [START_REF] Vito | Effective SIMD code generation for the high-level declarative data-parallel language 81/2[END_REF].

1

 1 fby (($A + 1) when Clock 0)) = D(1) = T rue C(A) = C(1 fby (($A + 1) when Clock 0)) = f byC(C(1), C(($A + 1) when Clock 0)) = f byC(⊤.F alse, D(($A + 1 when Clock 0) ∧ (C(Clock 0) ∧ T rue)) . We have D(($A + 1) when Clock 0) = D($A + 1) ∧ D(Clock 0) = D($A + 1) = D($A) ∧ T rue = D($A) = ⊥.T rue because D(A) = T rue. So, as expected: C(A) = T rue ∧ f byC(⊤.F alse, ⊥.T rue ∧ (C(Clock 0) ∧ T rue)) = f byC(⊤.F alse, ⊥.T rue) = T rue .

  Each equation x = F (x) in a L program is directly interpreted through the semantics of an expression, as three equations defining D[[x]], C[[x]] and V[[x]], the images of x by the program meaning. Each right hand-side, written respectively F d [x], Fc[x] and Fv[x], corresponds to a LR(1) function and therefore can be decomposed into the F ′ and F ′′ forms. In order to implement the various environments simply as a set of memory locations, we write x d , xc and xv for the current value of D[[x]], C[[x]] and V[[x]] and x md , xmc and xmv for the first argument in F ′ . The three I-equations associated with x = F (. . .) can then be rephrased as:

Fig. 3 .

 3 Fig. 3. Sketch of the code implementing the computation of a L program.

Table 1 .

 1 Some examples of streams expression.

	1 : >	1;	;	;	;	; . . . >
	true : > true;	;	;	;	; . . . >
	Clock 2 : > true;	; true;	; true; . . . >
	1 when Clock 2 : >	1;	;	1;	;	1; . . . >
	$1 : >	;	;	;	;	; . . . >
	$(1 when Clock 2) : >	;	;	1;	;	1; . . . >

Acknowledgments. The authors wish to thank Jean-Paul Sansonnet, the members of the Parallel Architectures team in LRI and the anonymous reviewers for their constructive comments.