Simon Archipoff
email: simon.archipoff@u-bordeaux.fr

An Efficient Implementation of Tiled Polymorphic Temporal Media

Tiled Polymorphic Temporal Media (TPTM) are a convenient way to describe, compose and encode multimedia streams. This paper presents a TPTM encoding that allows simple and efficient implementation of both composition and rendering. In particular, an on-the-fly rendering procedure is provided in order to handle infinite (lazy) TPTM.

Introduction

In the context of computerized music, but also in the context of systems producing temporal media, the purpose of computation not only concerns what values are to be computed as in classical programming, but also when these values are to be produced or rendered.

In these fields, temporal media (sequences of media values that evolve with time, such as audio or video) play a prominent role. In [START_REF] Hudak | An algebraic theory of polymorphic temporal media[END_REF], a polymorphic temporal media algebra is defined, allowing to combine them either in sequence or in parallel. Presumably, these operators are sufficient. However, the analysis of common functions, such as temporal media synchronization, suggests that temporal media may be abstracted further.

In order to compose of two audio sequences m 1 and m 2 , we have to take into account the content of m 1 and m 2 in order to make a consistent audio * Partially funded by INEDIT, ANR-12-CORD-009. alignment. A silence d may have to be added to the composition in order to synchronize m 1 and m 2 . More precisely, such a composition would be (d :+: m 1 ) :=: m 2 or m 1 :=: (d :+: m 2 ), where :+: denotes the sequential composition and :=: denotes the parallel composition. Of course, an abstraction of the form λm 1 m 2 → (d :+: m 1 ) :=: m 2 would be meaningless since the value d depends on both m 1 and m 2 . Instead, the correct abstraction of the composition of two audio sequences m 1 and m 2 can be defined by: where the function alignOffset performs a possibly complex analysis of the underlying musical structure induced by m 1 and m 2 .

The synchronization data of two temporal media m 1 and m 2 can be independent one with the other, for instance for musical bars. This suggests that the underlying abstract structure that may relevantly describes these audio sequences should not only consists in the ordered audio frames themselves, that form the basis of the audio sequences, but also in a number of synchronization marks al-lowing to adequately align these audio sequences one with each other.

As a matter of fact, most audio toolboxes that are available nowadays propose mechanisms to enrich audio or musical sequences with such a kind of synchronization markers. Yet, while these markers are defined (in a quite ad hoc way) at the interface level, their definition, manipulation and transformation at the programmatic level is far from being clearly understood.

Despite an apparent simplicity, defining and handling adequate synchronization marks over temporal media is not easy: how many synchronization marks should we allow? This immediately raises the question of representing the (possibly many and heterogeneous) time scales the temporal media are to be defined on. Such a time scale can be for instance: seconds, bars, beats, events. . . Even more, as soon as interaction appears, this poses the problem of building systems that are globally asynchronous (event driven) and locally synchronous (almost continuous).

The tiled modeling and tiled programming approach that is recalled and implemented in this paper is an attempt to formalize, not only at the programmatic level but also at the modeling level, the interplay between temporal media values: what they are, and their synchronization marks: how they should be used. In particular, it aims at providing sufficiently rich abstract description of temporal media types so that as we shall see, one can easily define a meaningful abstract composition process:

λm 1 m 2 → m 1 % m 2
where % is the tiled composition operator. The resulting domain specific language is both versatile and efficient.

In a first part of this paper we will recall some of the work done in this field. Then we will present our main contribution: a new implementation of Tiled Polymorphic Temporal Media. Last, we will study how this implementation compare to other ones considering algorithmic complexity, performances, and finally expressiveness. As an illustra-tion of expressiveness, we present a set of primitives to convert Polymorphic temporal media to Tiled Polymorphic Temporal Media using our implementation.

From PTM to TPTM

In this section we give a brief survey of the existing approaches, from Hudak's Polymorphic Temporal Media (PTM) to the more recently proposed Tiled Polymorphic Temporal Media (TPTM).

An important concept with PTM and therefore TPTM is the notion of observational equivalence between two temporal media. The observational equivalence of m 1 and m 2 , denoted by m 1 ≡ m 2 , means that m 1 and m 2 can not be distinguished during the rendering, no matter how they are combined with other temporal media.

Polymorphic Temporal Media (PTM)

A Hudak's Polymorphic Temporal Media [START_REF] Hudak | An algebraic theory of polymorphic temporal media[END_REF] can be either a temporal media value lasting for some duration d, a sequential composition :+: or a parallel composition :=: of any two simpler media. Such operators are depicted in Figure 1 where, as in most figures, the horizontal axis represents the flow of time from left to right. Despite its simplicity, this model is used in computer music library such as Haskore [START_REF] Hudak | Haskore music notation -an algebra of music[END_REF] and Eu-terpea [START_REF] Hudak | The Haskell School of Music : From signals to Symphonies[END_REF] (both written in Haskell). It has nice algebraic properties [START_REF] Hudak | An algebraic theory of polymorphic temporal media[END_REF].

This model handles infinite temporal media thanks to laziness. For instance in m = m 1 :+: m, m is a valid and playable temporal media when m 1 is finite. About the implementation, the "on demand" semantics of Haskell spares the programmer a lot of work and makes the code very simple.

With the simplicity of this approach come two slight drawbacks. The first one concerns the semantics of the parallel composition, we have many ways to synchronize two temporal media in parallel (at their beginning, at their end, truncating the end of the longest. . . ). We have to make an arbitrary choice: in Euterpea, the parallel composition synchronizes the two operands at their beginning, and the duration of the resulting media is the one of the longest operand. The second drawback is the lack of modularity mentioned in the introduction.

Tiled Polymorphic Temporal Media (TPTM)

Tiled Polymorphic Temporal Media proposed by Hudak and Janin [START_REF] Hudak | Tiled polymorphic temporal media[END_REF] offers a simpler approach with a single tiled composition operator (denoted %).

With TPTM, the information about the synchronization is embedded in the media and is used in the tiled composition. It follows that both sequential and parallel compositions appear as particular cases of tiled composition. Tiled PTM allows the decorrelation of the beginning and the end of the temporal media from their synchronization points. More precisely, a tile is a stream enriched with two particular points called pre ( ) and post ( ), as depicted in Figure 2. Then, given two tiles t 1 and t 2 encapsulating streams s 1 and s 2 respectively, we compute the composition t 1 % t 2 by synchronizing the post marker of t 1 with the pre marker of t 2 , and mixing their underlying streams. The synchronization points of the resulting tile are the pre marker of t 1 and the post marker of t 2 , as depicted in Figure 3

Derived Operators

The model is rich enough so that we can easily define derived functions to compose tiles. The reset of a tile re t is a tile of duration 0 with the post marker at the same place as the pre marker in t. It can be used to make parallel composition of tiles by synchronizing them at their pre marker. The coreset function co places the pre marker of a tile at the position of the post marker, making a tile of duration 0. It is useful to synchronize two parallel tiles on their post marker. And the inv function swaps the pre and the post marker. These functions are depicted in Figure 4.

The inv function have a very interesting algebraic property. Under a few hypothesis on the underlying media, the set of tiles equipped with product % and the empty tile unit (of duration 0) forms an inverse monoid with regard to observational equiva-

t re t co t inv t
Figure 4: A tile t, and its reset, co-reset, and inverse lence [START_REF] Hudak | Tiled polymorphic temporal media[END_REF]. More precisely the product % is associative, unit is neutral and for every tile x there is a unique tile inv x verifying:

x % inv x % x ≡ x inv x % x % inv x ≡ inv x

Parallel Operators

Using those operators, we can define fork and join binary operators, two parallel compositions synchronizing tiles at their pre and post marker, respectively. The fork operator behaves somehow like the :=: compositor of PTM. The semantics of these functions are depicted in Figure 5.

fork t 1 t 2 = re t 1 % t 2 join t 1 t 2 = t 1 % co t 2

Modeling Examples

Tiled Polymorphic Temporal Media are convenient to handle media according to their underlying structures beginning or ending, which can be distinct from their literal beginning or ending. Possible applications of this property are detailed below.

Adding a Pickup

In music, an anacrusis, or pickup, is a brief introduction to a measure. Using TPTM, it is simple to add a pickup to a tile. Given a tile t with a positive duration and nothing before the pre marker, it In this example, we can see a case where TPTM are more modular than PTM. In a % t % b, if one wants to add something in t, as long as the markers of t are placed in a consistent way, neither a nor b will be impacted by this modification.

Uniform Handling of Language and Rhythmical Units

As a more concrete application instance, tiles are convenient to modelize the relation between the lyrics and the music. Those two objects do not have the same logical structure. One is decomposed in verses, grammatical units, words,. . . the other in phrases, bars,. . . Nevertheless, they are both entangled in a song and TPTM can formalize these relations.

Here, we consider the Bob Dylan's song "Blowing in the wind". We can encode the lyrics by a list of tiles where the text embedded by each tile is determined by grammar, and the markers of those tiles by musical criteria. In Figure 7 the lyrics are split using grammatical criteria, the pre and post markers are placed according to the musical bars location.

How many roads must a man walk down This illustrates the potential of TPTM to represent music at various time scales, and according to the different structures involved (natural language, measure, melody,. . . ).

Existing Implementations

Implementing TPTM is not a trivial task. We have to satisfy the constraint of polymorphism, this implies to make minimal hypothesis on the tiled media. We also want to handle infinite data structure, and we want our tiles to be playable in real time.

Tiles in Euterpea

Hudak and Janin made a first implementation on top of Euterpea [START_REF] Hudak | Tiled polymorphic temporal media[END_REF] Simple and elegant, this implementation already allows to study the notion of tiled programming. However, it suffers from a lack of polymorphism, as primitives on tiles are implemented with primitives of Music type.

The Syntactic Approach

Other standalone implementations proposed by Bazin, Hudak and Janin [START_REF] Bazin | Flux média tuilés polymorphes: une sémantique opérationnelle en Haskell[END_REF][START_REF] Hudak | From out-of-time design to in-time production of temporal media[END_REF] separate clearly the out-of-time tile construction induced by tiled modeling and the in-time on-the-fly rendering. To this end, they encode tiles in a syntactic way.

This settles a set of primitives that allows both composition and rendering of tiles.

Creation Primitives

First, the out-of-time primitives used to produce tiles: delay :: Duration → Tile a event :: a → Tile a (%) :: Tile a → Tile a → Tile a dur :: Tile a → Duration This syntax describes the two atomic tiles. The expression delay d is an empty tile of duration d which can be positive as well as negative, and event e is a tile of null duration with a single event e. The Figure 9 shows two atomic tiles. In most figures the horizontal axis represent the time and the scale is respected. The dur function returns the duration of the tile, defined as the time distance between the pre and post markers. We observe that dur (a % b) ≡ dur a + dur b. The % operator allows the composition of those two base tiles. As delays can be negative, the temporality of the media does not have to be reflected in the description of the tile. For instance, in event a % delay (-1) % event b, the event b will occur before the event a. Then, we can describe every tile by its sequence of events separated by back and forth delays, hence the resulting tiles are "zigzag" through time. An example of such a tile is depicted in With those construction primitives, we can implement the reset, co-reset, and inverse functions described earlier. These functions are depicted in Figure 4.

inv t = let d = dur t in delay (-d) % t % delay (-d) re t = t % delay (-(dur t)) co t = delay (-(dur t)) % t

Rendering Primitives

Obviously, zigzag tiles can not be rendered as they are. The first event to occur can be deep in the syntactic structure. For each tile, there is a normal form where there is no consecutive delays, and no negative delay between two events. Such a normal form is depicted in Figure 11.

e b f a,c d -2 2 1 1 1 -2
Figure 11: The tile t normalized One way to compute such a normal form is to define some primitives to extract the first events and the time distance to them: firstE :: Tile a → MultiSet a firstD :: Tile a → Maybe Duration The firstE function returns the list (encoding a multiset) of all the first events (all the other are strictly later). And the firstD function returns the delay between the pre marker and the first events. Such a delay will not be defined if the tile have no event. That is the reason why firstD returns a value of type Maybe Duration. It can be either Just d, returned when the tile have events, or Nothing when there is no such event.

In order to play a tile, we need to compute the first events to occur, when they will occur, but also what comes afterward. We define the primitives headT and tailT to compute these. The headT function returns the tile composed of the first delay and the first simultaneous events, and tailT returns the remainder of the tile, as depicted in Figure 12. For any tile, we have the property:

t ≡ headT t % tailT t
Those functions are named after the head and tail functions defined over lists because of the semantic similarity between them. Over any non empty list l the following property is verified.

l == head l : tail l

The headT function can be defined in term of firstD and firstE:

headT t = case firstD t of Nothing → delay 0 Just d → delay d % fold (λt e → t % event e) (delay 0) (firstE t)
As event only takes a single event, the multiset returned by firstE is reduced in a tile using tiled product and the standard Haskell function fold. This function takes as parameter an accumulation function (here of type Tile e → e → Tile e) and a starting accumulator value (here delay 0, a neutral).

Observational Equivalence

The simplest observational equivalence is the following: two tiles are considered equivalent when they have the same duration and describe the same marked sequence of timed events. Such a definition does not takes into account the properties of the events type, relevant from the observation. It is recursively implemented by:

(≡) :: Eq e ⇒ Tile e → Tile e → Bool (≡)

t 1 t 2 = case (firstE t 1 , firstE t 2 ) of ([ ], [ ]) → dur t 1 == dur t 2 (le1, le2) → firstE t 1 == firstE t 2 ∧ firstD t 1 == firstD t 2 ∧ tailT t 1 ≡ tailT t 2
The base case is when both tiles have no event, then it checks if they are equal in duration. The recursive case checks if the two tiles have the same first events, at the same time, and if their remainders (their tails) are equivalent.

Heaped Tiles

Here, we present a new approach using balanced data structure and making the duration of the tile independent of the delays used to build it. For this, we define a tile as a duration (of type Duration) and a set of timed events. Such a set is implemented by a mergeable heap, here Sleator and Tarjan's skew heap [START_REF] Sleator | Self adjusting heaps[END_REF].

The implementation of the tile is given by:

data Tile e = Tile Duration (SHeap e)

with Duration the duration of the tile and SHeap e a set of timed events. The skew heap of events is a binary tree where node are labeled by a delay and embed some events.

data SHeap e = Empty | SHeap Duration (MultiSet e) (SHeap e) (SHeap e)

The events are stored in a multiset MultiSet, the Duration member is the time distance that separates the events in the node from his father, or the implicit pre marker of the tile for the root. In Figure 13 are depicted the same tiles as in Figure 9. The duration is represented by a dotted line between the two synchronization points, and the event is attached to the implicit pre marker of the tile (at time 0). In Figure 14, we can see the correspondence between zigzag and heaped representations (same position on the horizontal axis means same time). In the later case, the syntactic composition of the tile is lost but the events are partially ordered.

High Level Implementation of the Primitives

The primitives introduced in 3.3 are implemented as follows:

delay d = Tile d Empty event e = Tile 0 (SHeap 0 (singleton e) Empty Empty) --singleton e is a multiset containing only e (%) (Tile

d 1 s 1 ) (Tile d 2 s 2 ) = Tile (d 1 + d 2 ) (mergeSH s 1 (shiftSH d 1 s 2 )) dur (Tile d ) = d
The delay d function returns a tile of duration d with no events, the event e function returns a tile of duration 0 and a single event at time distance 0 of the pre marker of the tile. The mergeSH function is a binary operator that merges two heaps by preserving time distances, every event of each operand will be at the same time distance in the resulting tree. And the shiftSH function takes as parameter a duration and a heap, and shift all the timed events of the heap by the duration. The implementation of composition is based on the property:

t 1 % t 2 ≡ re t 1 % delay (dur t 1 ) % t 2
The sole SHeap of the tile delay (dur t 1 ) % t 2 , is computed by shiftSH d 1 s 2 (every events of t 2 are preceded by a delay of (dur t 1 )). Then, the events of t 2 shifted are merged by the ones of t 1 , and the duration of the resulting tile is the sum of the durations of t 1 and t 2 . The tiled product is depicted in Figure 15.

Additional Primitives

The rendering primitive are simple as well, all of the relative complexity of the implementation is hidden in the heap's primitives. Here the implementation of a few more primitives:

firstD (Tile (SHeap d )) = Just d firstD = Nothing a 1 b 1 d 1 2 2 c 1 2 1 -2 a 2 b 2 d 2 1 2 c 2 3 -1 (a)
The synchronization points are aligned (the heap of the second operand is shifted)

2 a 1 a 2 , c 1 b 2 d 2 1 2 c 2 3 2 b 1 d 1 2 2 1 (b)
The heaps and the synchronization data are merged The tailT function removes the first events, and then computes a new heap containing all the remaining events.

A very important improvement with this tile representation is that the reset of a tile is defined even when the duration of this tile is undefined, as we can implement it by: re (Tile h) = Tile 0 h

Low Level Implementation

A skew heap [START_REF] Sleator | Self adjusting heaps[END_REF] is a very simple data structure that can be implemented in Haskell with less than 10 lines of code, it have nice algorithmic properties, and as it is a good base for an implementation of a priority queue, we can use it to implement TPTM as well. It is a binary tree where the nodes are labeled by elements of an ordered set (times for instance). It allows a quick access to the smallest element of the heap, and a quick merge of two heaps. Here, to store the events we uses a slightly modified skew heaps, the difference with the usual ones is that the nodes carry delays and not absolutes times.

The set of timed event is coded by a binary tree. In an expression of the form n = SHeap d mse lchild rchild where d is the time distance between the events in the multiset mse and the event embedded by the father of n, or the implicit pre synchronization of the tile when n is the root.

The invariant of the heap is:

• the duration carried by every node except the root is strictly positive,

• a node carry at least one event,

• the total delay to an event is the sum of all delays from the root to the node carrying this event.

The implementation of shiftSH is pretty straightforward. It is an O(1) operation: as the labels on the nodes are relatives, shifting a node shifts all its subtree. With absolutes labels we would have an O(n) operation. Finally, the implementation of mergeSH is given by: mergeSH :: Ord e ⇒ SHeap e → SHeap e → SHeap e mergeSH l Empty = l mergeSH Empty r = r mergeSH heap 1 @(SHeap d 1 e 1 l 1 r 1 )

heap 2 @(SHeap d 2 e 2 l 2 r 2 ) = case compare d 1 d 2 of EQ → SHeap d 1 (union e 1 e 2 ) (mergeSH l 1 r 1 ) (mergeSH l 2 r 2 ) LT → SHeap d 1 e 1 (mergeSH r 1 (shiftSH (-d 1 ) heap 2 )) l 1 GT → SHeap d 2 e 2 (mergeSH r 2 (shiftSH (-d 2 ) heap 1 )) l 2
We merge the trees following their rightmost paths, and swap the right and the left child in the resulting tree. This case is depicted in Figure 16. By this mean, the tree tends to grow "from the inside" rather than the rightmost path.

If the roots of the two tree we want to merge have the same delay, we do not increase the resulting tree size and we merges their events instead , otherwise we would have a 0 delay and violate our invariant. This case is depicted in Figure 17. The fact that we forbid null delay is reducing the tree size, but we could as well allow it and then treating this special case in the headT function rather than in the merge function. We can use mergeSH over infinite heaps because it is lazy on the childs of its parameters.

Complexity Analysis

In this section we will study space and time complexity of a syntactic implementation and the heaped implementation. We define the size of a tile merge

e 1 l 1 r 1 d 1 e 2 l 2 r 2 d 2 ⇒ merge e 1 l 1 d 1 e 2 l 2 r 2 d 2 -d 1 r 1
Figure 16: Heaps merge: case

d 1 < d 2 by n = n e + n d
where n e is the number of events and n d is the number of delays in it.

Syntactic Complexity

A syntactic implementation suffer from two algorithmic problems, about time and space complexity. Firstly, there is no mechanism to balance the structure built. The complexity of the in-time rendering depends on the way the tile has been constructed. For instance, a call to firstE is linear on a tile that has been constructed starting "from the end", because the first events are in the bottom of the syntactic structure. In general, all operation are in O(n), where n is the size of the tile.

Secondly, given a tile t of any event type, there is no bound to the size of a tile t such that t ≡ t . We can have an arbitrary number of delays because of the property delay (a + b) ≡ delay a % delay b. With the implementation described in 3.1, the space complexity is O(n e + n d ).

Heaped Complexity

With the heaped implementation and assuming that Duration have O(1) space complexity (for instance when a bounded number of delay values are used), the space complexity of a tile with n e events and n d delays is O(n e ) since the invariant of the heap imply

n d = O(n e ).
It can be proven [START_REF] Sleator | Self adjusting heaps[END_REF] that mergeSH have an amortized complexity of O(log n). Hence, both % and tailT have a logarithmic time complexity and headT have a constant time complexity.

Performances

In this section, we will compare the Twisted implementation [START_REF] Hudak | From out-of-time design to in-time production of temporal media[END_REF], and the one introduced in this paper. In all the following measures, we simulate the rendering of a tile by recursively extracting all the first events of the tile. We use GHC 7.8.4 with no runtime tuning on an AMD Opteron 6174 (2.2 GHz). More specifically, we will benchmark the normalization of tiles defined as follow:

tileL 0 = delay 0 tileL n = (delay 1 % event ()) % tileL (pred n) tileR 0 = delay 0 tileR n = tileR (pred n) % (delay 1 % event ()) parallelTile t n = foldl (%) (delay 0) (replicate n (re t)) tileLeft = parallelTile (tileL 2000) 16 tileRight = parallelTile (tileR 2000) 16
The performance of the normalization of a tile is very sensitive to its expression with the syntactic representation. The tileR function generate a worst case for syntactic representation (parallelTile do not).

Due to the space complexity described in section 5.1, the extraction of the first events of a tile does not guaranty that the remainder is smaller than the original tile. The implementation described in [START_REF] Hudak | From out-of-time design to in-time production of temporal media[END_REF] suffer from this, the number of delays in tailT t increases. This is the reason why in Figure 18 the reduction time of firstE (tailT n t) is proportional to n. But the Twisted implementation stay very sensitive to the expression of the tile. In Figure 20 we see the normalization of the same tile but right parenthesized. The first events are the deepest leafs of an imbalanced syntactic tree, hence the reduction time of firstE is proportional to the size of the tile. The performance of the Heaped implementation performing the normalization of the same tile as in Figure 20 (a tile constructed "backward") is shown in Figure 21. The average call to firstE is less than 50 µs. The garbage collector periodically cause longer execution time. Because of the complicated complexity analysis of the skew heaps and the impact of the lazy semantics, a worst case for the Heaped implementation is yet to find. The normalization of a left parenthesized tile with the Heaped implementation is depicted in Figure 22. The first call to firtsE last 1400 µs, the average is 6 µs.

Infinite Tiles

As the lazy semantics of Haskell allows the programmer to write infinite data structures such as lists, we would like to be able to write infinite tiles.

In this section we study the possibility of representing and playing an infinite tile. Such a tile that may results from an equation of the form x = m % re x [START_REF] Hudak | Tiled polymorphic temporal media[END_REF]. Because we are interested in relevant tile from a musical point on view, we will consider only the tiles with a finite number of events at each time, and where all delay d i between consecutive set of events verify for all i: 0 < m d i M for some m and M. This mean in particular that we can not have an infinite number of events in a finite time interval.

Syntactic Implementation

With the syntactic representation, we observe that it is impossible to build such an infinite tile with a finite duration. Because the duration of the tile is the sum all the delays that composes it, and a infinite tile have an infinite number of positive delays, we would need to add an infinite number of negative delays to make the sum finite. We can write a function that compute an potentially infinite tile from a potentially infinite list for instance, but it will suffer from a memory leak because of the infinite number of negative delays accumulated needed to have a finite duration. The Figure 23 where all the durations in it are positives except maybe the first one and all multisets are non empty. Hence, we can build infinite tiles given an infinite list.

We define a function sToT as Stream To Tile, that takes a potentially infinite list and returns an infinite tile of finite duration that encode this list. Such a tile is depicted in Figure 24.

Encoding PTM into TPTM

As a consequence of the possibility to compute infinite Heaped tile, we can write conversion function from infinite PTM to TPTM. This implementation suffers from a memory leak when the PTM converted is have an infinite duration.

We use this simple definition for PTM, and a Event to encode temporal media in term of events: The constructors Prim d a represents a media a during a time d, Wait d is a delay, and the remaining constructors are pretty straightforward. In TPTM, we encode a media a for a duration d by two event separated by a time d marking the beginning and the end of a. The tiles involved here have the property:

(P) All the events embedded are between the two synchronization marks: There is no event before the pre marker, and no event after the post marker.

A TPTM encoding a PTM is a well parenthesized sequence of event On a and Off a. We define a function mToT as Media To Tile that computes such a tile:

: m 2 ) = parM (mToT m 1 ) (mToT m 2 ) mToT (m 1 :+: m 2 ) = seqM (mToT m 1 ) (mToT m 2 )
The seqM and parM functions are the tiled implementation of :+: and :=: respectively, in order to be able do deal with infinite tiles, these functions can not be implemented naively. The seqM function works under the hypothesis that both operands verify (P).

parM (Tile d 1 h1) (Tile d 2 h2) = Tile (max d 1 d 2 ) (mergeSH h1 h2) seqM (Tile d 1 h1) ∼(Tile d 2 h2) = Tile (d 1 + d 2 ) (lazyMergeSH h1 (shiftSH d 1 h2))
The implementation of parM is pretty straightforward, we notice that parM is lazy on durations, and mergeSH can handle infinite heaps, so such a function suit its purpose. However, the implementation of seqM is less obvious because it have to be lazy on its second parameter in order to be able to handle an infinite PTM such as m 1 :+: (m 2 :+: (m 3 :+: (m 4 .... The first unwanted strictness come from the fact that in Haskell, pattern matching in case expression are strict by default. Without the "lazy-pattern" tilde, when seqM a b is evaluated, it will trigger the evaluation of a and b, b can also be of the form seqM c d, hence, it will trigger an infinite computation. Such a pattern matching cannot fail because Tile e have a single constructor. We could as well made the program lazy on the second operand by other mean, but for the sake of simplicity, we use the ∼(pattern) syntax.

The second unwanted strictness comes from mergeSH because it needs to evaluate both its operand in order to see from which one the first event of the resulting tree comes from. We use the hypothesis (P) to implement a lazier merge. The lazyMergeSH function is lazy on the second parameter and works only under the hypothesis that the first event of the second heap is after the last event of the first heap. The algorithm is exactly the same as mergeSH, but by hypothesis we are always in the LT case.

The mToT function build a tile of the duration of the media, such a duration can be undefined in case of infinite PTM such as m in m = m 1 :+: m. It follows that one will prefer the use of the function mToReT which returns the reset of that tile, of duration 0.

mToReT :: Ord a ⇒ Media a → Tile (Event a) mToReT = re • mToT Such an implementation suffers from a memory leak if the PTM converted is infinite. Because the function mToT will compute without evaluating the duration of the resulting tile, which can be infinite.

Rendering

The firstE, firstD and tailT performs an abstract rendering. In order to make more concretes experiments around TPTM, two players have been written. The first one is a MIDI player, and the second one an audio player.

These two players relies on the sound server JACK that provides a real-time engine and primitive to send both MIDI and audio. The input of JACK is bufferized, this conveniently loosen the real-time constrains imposed to the Haskell runtime.

MIDI Player

The MIDI player takes as input a tile of MIDI messages and feed the JACK server by performing an on-the-fly normalization of the tile. The firstE function performs an agnostic accumulation of the MIDI events, the player relies on downstream components to compute the semantic of simultaneous events.

This player have been used to play standard MIDI files. Such a file can be seen as a list of parallel tracks (usually one per instrument), where a track is a sequence of delays and MIDI events. Hence, we encode a MIDI file by a tile of the form re t 1 % re t 2 % re t 3 %• • • where each t n is a positive tile encoding of the nth MIDI track.

Audio Player

We implemented a player that is capable of reading and playing audio tile as well. A digital audio stream is a continuous signal discretized at a constant framerate. For performance reasons, rendering a tile with one event per audio frame was not feasible. Thus, an audio tile is based on the granular synthesis technique. The audio events are "grain", some few milliseconds of audio stream. These grains overlap and are placed in an envelope in order to avoid artifacts.

Thanks to this technique, we can easily change the tempo without modifying the pitch, as it suffice to modify the delays in tile separating the grains. However, significant speed change generate a lot of artifacts.

A reduction have to be performed on the events returned by firstE, from a multiset of grains we compute a vector of audio frames.

These experiments open the way to musical experimentation. We are currently working on a player that can simultaneously read both MIDI and audio.

Conclusion

The implementation proposed in this paper have good algorithmic properties and can handle infinite temporal media, just as Tiled Euterpea could [START_REF] Hudak | Tiled polymorphic temporal media[END_REF].

In further research we would like to extend TPTM model in order to handle interactive temporal media. In particular, we are interested in being able to describe some synchronizations between the rendering of a tile and an external stream of events (the music played by a musician for instance). We are also interested in expressing complex interactive programs with conditional renderings.

The tree structure of our implementation seems to be adapted to this extension as it induces a partial order between the events that is compatible with the temporality of those events. This tree describes a non-determinism between the order of the events to be played that is resolved by the normalization. An arbitrary arity tree could express a nondeterminism between the order of external events that would be resolved by the monitoring of external events. Of course, this would imply exploring the possible links with other known approaches such as, in particular, Functional Reactive Programming approach.

λm 1 m 2 →

 2 let d = alignOffset m 1 m 2 in if d > 0 then (d :+: m 1 ) :=: m 2 else m 1 :=: ((-d) :+: m 2 )

m 1 m 2 m 1 and m 2 m 1 m 2 sequential composition m 1 :+: m 2 m 1 m 2 parallel composition m 1 :=: m 2 Figure 1 :

 2212121 Figure 1: PTM syntax and semantics

Figure 2 :

 2 Figure 2: A tile

Figure 3 :

 3 Figure 3: Tiles are enriched streams

Figure 6 :

 6 Figure 6: Adding a pickup with tiles

Figure 7 :Figure 8 :

 78 Figure 7: A song tiled by measures

  by encapsulating Euterpea's Music type into a type Tile: data Tile a = Tile {preT :: Duration; postT :: Duration; musT :: Music a} with Duration implementing the set of rational numbers.

2 (Figure 9 :

 29 Figure 9: Two simple tile

1 Figure 10 :

 110 Figure 10: A tile "zigzag" t

Figure 12 :

 12 Figure 12: Same tile as in Figure 10 with the first event extracted

2 (Figure 13 :

 213 Figure 13: Two simple heaped tiles

Figure 14 :

 14 Figure 14: Two representations of the tile delay 1 % event b % delay (-3) % event a % delay 2 % event c % delay (-2)

Figure 15 :

 15 Figure 15: Tile composition

  shiftSH :: Duration → Sheap e → SHeap e shiftSH d Empty = Empty shiftSH d (SHeap d e l r) = SHeap (d + d ) e l r

2 ⇒ e 1 ∪ e 2 d 1 merge l 1 r 1 merge l 2 r 2 Figure 17 :

 2111217 Figure 17: Heaps merge: case d 1 = d 2

Figure 18 :Figure 19 :

 1819 Figure 18: Normalization of tileLeft with the Twisted implementation

Figure 20 :

 20 Figure 20: Normalization of tileRight with the patched Twisted implementation

Figure 21 :

 21 Figure 21: Normalization of tileRight with the new Heaped implementation (some few points are between 500 and 5000 µs)

Figure 22 :

 22 Figure 22: Normalization of tileLeft with the new Heaped implementation (some few points are between 500 and 1500 µs)

1 Figure 23 : A potentially infinite zigzag tile 7 . 2

 12372 Figure 23: A potentially infinite zigzag tile

Figure 24 :

 24 Figure 24: An infinite heaped tile

data

  Media a = Prim Duration a | Wait Duration | Media a :+: Media a | Media a :=: Media a data Event a = On a | Off a deriving (Eq, Ord)

  mToT :: Ord a ⇒ Media a → Tile (Event a) mToT (Prim d a) = event (On a) % delay d % event (Off a) mToT (Wait d) = delay d mToT (m 1 :=

  lazyMergeSH :: SHeap e → SHeap e → SHeap e lazyMergeSH Empty h = h lazyMergeSH (SHeap d e l r) h = SHeap d e (lazyMergeSH r (shiftSH (-d) h)) l

  . Thus, tiles t 1 and t 2 describe how s 1 and s 2 are aligned.

	t 1	pre	s 1	t 2	pre	s 2
			post	post
	(a) Two stream descriptors enriched with pre and post
	synchronization points
			s 1
				s 2
	(b) When composing t 1 with t 2 , the post synchronization
	point of t 1 is aligned with the pre synchronization point
	of t 2
			s 1	s 2
	(c) The streams s 1 and s 2 are completed with silences and
	composed together to make a new tile


Lamiae Dounas

Raul Mazo
email: raul.mazo@univ-paris1.fr

Juan C Muñoz-Fernández

Camille Salinesi
email: camille.salinesi@univ-paris1.fr

Omar El Beqqali
email: omar.beqqali@usmba.ac.ma

Runtime Requirements Monitoring Framework for Adaptive e-Learning Systems

Keywords: Requirements monitoring, adaptive e-learning systems, constraint programming, dynamic software product lines, goal modelling

As academic learners and companies are turning to e-learning courses to achieve their personal and professional goals, it becomes more and more important to handle service quality in this sector. Despite scientific research conducted to personalize the learning process and meet learner's requirements under adaptive e-learning systems, however, the specification and management of quality attribute is particularly challenging due to problems arising from environmental variability. In our view, a detailed and high-level specification of requirements supported through the whole system lifecycle is needed for a comprehensive management of adaptive e-learning systems, especially in continuously changing environmental conditions. In this paper, we propose a runtime requirements monitoring to check the conformity of adaptive e-learning systems to their requirements and ensure that the activities offered by these learning environments can achieve the desired learning outcomes. As a result, when deviations (i.e., not satisfied requirements) occur, they are identified and then notified during system operation. With our approach, the requirements are supported during the whole system lifecycle. First, we specify system's requirements in the form of a dynamic software product line. This specification applies a novel requirements engineering language that combines goal-driven requirements with features and claims and avoid the enumeration of all desired adaptation strategies (i.e. when an adaptation should be applied) at the design time. Second, the specification is automatically transformed into a constraint satisfaction problem that reduces the requirements monitoring into a constraint program at runtime.

INTRODUCTION

E-learning, also known as online learning or technology-enhanced learning is expected to make a radical difference to education, specifically, the quality and effectiveness of learning experience [START_REF] Mulwa | Adaptive educational hypermedia systems in technology enhanced learning: a literature review[END_REF]. In recent years, elearning systems have gained in popularity among academic and companies; the global e-learning market is expected to reach USD 107 billion by 2015 as reported by the Global Industry Analysts, Inc. Therefore, it becomes more and more important to handle service quality of this sector.

Among the existing technologies enhanced learning, adaptive e-learning systems have arisen as an alternative to traditional "one size fits all" learning approach that provides the same content for all learners regardless of their cultural diversity or how they learn [START_REF] Brusilovsky | Adaptive and intelligent web-based educational systems[END_REF] [START_REF] Brown | Patterns in authoring of adaptive educational hypermedia: a taxonomy of learning styles[END_REF]. On the one hand, some studies have attempted to provide personalized contents and navigation support for each learner, based on several characteristics of learners including knowledge level, goals, learning style or personal preferences [START_REF] Weber | ELM-ART: An adaptive versatile system for Web-based instruction[END_REF][START_REF] Mitrovic | Constraint-based tutors: A success story[END_REF][START_REF] De Bra | AHA! The adaptive hypermedia architecture[END_REF][START_REF] Papanikolaou | Personalizing the Interaction in a Web-based Educational Hypermedia System: the case of INSPIRE[END_REF][START_REF] Tseng | Development of an adaptive learning system with two sources of personalization information[END_REF][START_REF] Hwang | A heuristic algorithm for planning personalized learning paths for context-aware ubiquitous learning[END_REF][START_REF] Wang | Application of context-aware and personalized recommendation to implement an adaptive ubiquitous learning system[END_REF][START_REF] Mampadi | Design of adaptive hypermedia learning systems: A cognitive style approach[END_REF][START_REF] Chen | A hybrid recommendation algorithm adapted in e-learning environments[END_REF]. On the other hand, others studies have stressed technical aspects including learning standards like AICC, IMS, SCORM, and LOM, to give flexibility to learning systems, in term of contents as well as in structure.

As we move into a new era of dynamic adaptation, more attention is needed to support the requirements of adaptive e-learning systems and allow their evolution at runtime. So far, the main used approach to model adaptation is the design time enumeration of all desired adaptation strategies, on every context. But, this is clearly a fastidious and cumbersome task due to the number of decisions needed, considering continuously changing environmental conditions (e.g., learner engagement, learner location, device status, and network connectivity). Moreover, some requirements or features of the environment may be unknown at design time which may limit the system self-awareness [START_REF] Dardenne | Goal-directed requirements acquisition[END_REF] and reduce guarantee that adaptation strategies will remain

BACKGROUND

The main objective of our requirements monitoring framework is to check the satisfaction of learning requirements at runtime. This implies to be able to specify the requirements of the adaptive e-learning systems and be aware of changes in their environments at the same time. Therefore, we are particularly interested in establishing relationships among three key elements:

 Learning materials  Learning requirements  Assumptions about the environment A simple way to do would be the design time enumeration of all possible instances of these elements and the relationship between them in a declarative statement. However, this statement can miss some unknown requirements of the operational environment, and it would also produce a tangled design. In contrast, we propose a much convenient way that uses a detailed and high-level requirements specification and supports the monitoring in the whole system lifecycle.

1 REFAS language

REFAS language is a novel requirements engineering language that seeks to manage uncertainty and to be sufficiently expressive for self-adaptive systems. It allows the representation of all relevant concepts in different views [START_REF] Munoz-Fernández | Towards a requirements specification multi-view framework for self-adaptive systems[END_REF]. From these views, we are interested in the following four views that conform with our requirements model:

 Variability view: represents system requirements (functional requirements) as goals. The top-level goal should state the overall objective of the system. This goal is decomposed then in several sub-goals (AND/OR-refinement) and the process of refinement ends when the leaf goals can be operationalized (i.e. solved by an operation or components). A goal may have several operationalization goals, which represents system's architectural variability. The decision about the satisfiability of selected configuration is reported at runtime to ensure acceptable behaviour under the current context.  Soft goals view: represents system's non-functional requirements as soft goals.  Context view: defines the context variables that impact the learning process and relation between these variables.  Soft goals satisficing view: represents assumptions about the context and their implication over the soft goals satisfaction. The view specifies soft-dependencies to express required levels of soft goal satisfaction for condition based on context values, and claims to indicate satisfaction level of soft goals expected from a combination of operationalization goals. Note that, the levels of satisfaction can be expressed from a set of values {0, 1, 2, 3, 4} ranging from complete denial (0) to complete satisfaction (4).

2 VariaMos Tool

VariaMos (Variability Models) is a Java-based tool for specification, automatic verification, analysis, configuration, integration and simulation of variability models [START_REF] Mazo | VariaMos: a Tool for Product Line Driven Systems Engineering with a Constraint Based Approach[END_REF].It offers an automatic transformation of requirements specifications of self-adaptive systems into a high-level constraint program [START_REF] Mazo | Abstract Constraints: A General Framework for Solver-Independent Reasoning on Product Line Models[END_REF], and then compiled into the language of the solver at hand to execute the resulting model. In this paper, it is used to implement REFAS requirements model, realize simulations about how the goals can be reached, and the soft goals can be satisfied, and transform the model into constraint program. More details about the tool can be found online1 .

MODELING APPROACH

Running example

To support discussion about the need for continuous requirements monitoring at runtime for adaptive elearning systems, we apply our approach to an adaptive e-learning system proposed by Franzoni et al. [START_REF] Franzoni | Student learning styles adaptation method based on teaching strategies and electronic media[END_REF]. The system aims to adapt the presentation of course materials (text, graphics, video, audio, forum, etc.) to each learner based on his learning style and encourage collaborative learning.

The learning style is defined using the Felder & Silverman model [START_REF] Felder | Learning and teaching styles in engineering education[END_REF] that classifies a learner under four dimensions: sensing/intuitive, visual/verbal, active/reflective and sequential/global. Then, the learning style and teaching strategies are matched based on the following taxonomy:

 Sensitive learners prefer facts, data and experimentation (laboratory exercises, problem-solving), they are patient with details but don't like complication. Whereas intuitive learners prefer theories and principles, they get bored with details and accept complication.  Visual learners remember the things they see. The information gathering must use visual representations (images, graphics, and text). Whereas verbal learners remember the things they have heard. The learning content must have a lot of oral representation (video, audio).  Active learners tend to apprehend and assimilate new information when they practice and work with others (discussion, chat, and forum). Whereas reflective learners think about information quietly, before go ahead and stop periodically to review what have been learned. The learning content must be related to with experience (question and answer methods, case study).  Sequential learners learn through small orderly steps (chapters, daily homework). Whereas, global learners learn through big steps and prefer to see everything as a whole (Project, case study). To extend our running example, we assume the system stimulates collaborative learning by managing two groups namely, an online group and a physical self-help group. Learners living in the same geographical space can use a physical self-help group. So they can have face-to-face meetings as well as online meetings with this group. Now, let us describe a scenario we expect the need for requirements monitoring at runtime: According to Felder & Silverman, the system knows what appropriate presentation of courses materials for a learner. However, there are some ignored driving characteristics to be considered when proposing course materials like network connection speed, bitrate and learner's preferences. For example, for a video lecture, the system need to consider bandwidth measurements and deliver the video file in different quality or when the bandwidth is too low, ask learners if they prefer textual presentation. In this scenario, the impact of the event of bandwidth was not anticipated at design time. Moreover, the system needs to work with learners, at runtime, to find relevant presentation of course materials in each context and avoid high waiting time.

Runtime requirements monitoring framework for adaptive e-learning systems

The requirements monitoring framework is performed in two stages:  At design time, as shown in Figure1, the administrator of the system elucidates the business goals and the requirements (non-functional requirements) to be monitored. The designer builds then the requirements model using REFAS language and specifies soft-dependencies and claims. Finally, the model is transformed into a constraint satisfaction problem where the goals, soft-goals, operationalization goals and context variables are mapped as variables and the claims and soft-dependencies as constraints.

At this stage, our approach aims to facilitate the requirements specification and verify the requirements model using simulations under a graphical tool, namely VariaMos.



At runtime: the requirements monitoring is reduced to a constraint program that verify the satisfaction of requirements and find optimal configurations that satisfy all constraints using the generated constraint satisfaction problem (CSP) from the design time stage.

As illustrated in Figure 2, our requirements monitoring is implemented as an autonomic computing MAPE (monitor-analyze-plan-execute) loop architecture [START_REF] Brun | Engineering self-adaptive systems through feedback loops[END_REF] under adaptive e-learning system:

In the upper part of Figure 2 shown, a typical architecture of adaptive e-learning that is organized in the form of three basic models: the student model represents information about learners. This information can be gathered from questionnaires or dynamically from log files which give a complete description of the current Changes Deviation Find alternative configurations that satisfy our CSP with free operationalization goals under the current context.

Plan

Execute alert function

Execute

Monitor context variables and system's configuration.

Monitor

Analyze CSP to check requirements satisfaction under the changes conditions. In the lower part of Figure 2 shown the MAPE loop control that continuously checks the satisfaction of learning requirements through four stages:

Analyze

Sensors

The first stage of the MAPE loop involves monitoring both: 1) System's context (or the external environment) by means of sensors. For example, the monitoring can use GPS to track learners and detect change in their geographical location.

2) Configuration (i.e. the whole operationalization goals used by the system) using log files from running instances of the system.

The current state information about managed elements is then stored in a data file and updated progressively to reason about. In this respect, when the monitoring identifies changes, the analysis stage is intended to verify the impact of the changes on learning requirements satisfaction by executing our constraint program using the values in the data file from the first stage. And if e-learning system is not providing the required satisfaction level, it triggers the next stage.

The planning stage is then employed to find optimal configurations of operationalization goals according to the values of the current context from the data file.

The executing stage alerts the system about deviations and presents a list of the available optimal configurations.

Note that, our monitoring framework may identify new requirements and verify some variables values from the system. For example, the monitoring may ask the system available representations of a typical course to enable/disable some multimedia options (operationalization goals).

APPLICATION AND SIMULATIONS

4.1 Applying our approach to the running example

Requirements analysis

In the running example, the aim is to promote the learning process by adapting the representation of learning materials to each learner based in learning style and supporting learner collaboration. Besides these functional requirements, the administrator of the system provides additional non-functional requirements. The focus herein is to list the overall requirements and describe the relation between these requirements and assumptions about the operational environment: R0 : Learners should have learning materials that fit their learning styles. In our view, monitoring this 'hard' requirement is not important and would be redundant, since our monitoring would likely not be able any more effective that the system itself. The remaining 'soft' requirements are then supported by the requirements model. R1 : Learners should not have to wait unduly long for loading learning materials. The monitoring framework shall consider network connectivity to identify relevant digital contents representations (video, graphics and audio, or text). For example, a learner can connect over a low bandwidth modem line, if the system presents a heavy video lecture, the learner may wait unduly long for the transmission of data. In this case, the monitoring should identify alternatives learning material based in their sizes to optimize the waiting time. R2 : The system should support collaborative learning and ensure a good match between collaborative groups. The monitoring framework shall track change in the geographical space and maintain the homogeneity of collaborative groups. And if changes occur, inform the system, so it can update their groups. R3 : The system should provide learners an accessible and available communication tools. The monitoring framework shall monitor learners' access to the e-learning platform and detect relevant communication tools for every learner depending of its frequency of access. For example, the system needs to use SMS or Email for learners with low frequency to keep learners aware of what happening in the platform, which might motivate them to connect and follow courses. R4 : The system needs to support the accessibility to learning materials in different contexts. The monitoring framework shall detect noisy environments and identify relevant auxiliary to multimedia like caption and subtitle.

Requirements model

The requirements model of the running example is supported by the four aforementioned views of REFAS language:

 Considering the variability view (see Figure 3), the root goal is PromoteLearningProcess which is AND-refined into two sub-goals IndividualizeCourseMaterial and ProvideCommunicationService. The former is AND-refined into two leaf goals OfferCommunicationTools and UpdateCollaborationGroup. And the latter is OR-refined into two leaf goals IndividualizeMultimediaDelivery and SupportAuxiliaryMultimedia. Each leaf goal has several operationalizations, for instance, OfferCommunicationTools goal can be operationalized using Forum, Chat, InternalMail, SMS, or ExternalMail. In addition, the use of some operationalization can be conditioned by constraints like require or exclude. This kind of constraints can considerably reduce the configuration space at runtime. In our example, UseSubtitle/UseCaption and Video are related by required relations, which means if subtitle or caption is activated, a video lecture must be selected.

 Considering the soft goals view (see Figure 4), the view supports five soft goals: WaitingTimeOptimization, GroupHomogeneity, RelevantCommunication, InteractiveCommunication and AccessibilityEnhancement. These soft goals represent the aforementioned 'soft' requirements {R1, R2, R3, R4}.

 Considering the context view (see Figure 5), the context variables that may affect the system include the NetworkSpeed, GeographicalChangeSpace {true, false}, IsLongStay {true, false}, VideoBitRate {high, low}, AudioBitRate {high, low}, FrequencyOfUse {high, low} to the system and NoisyEnvironment {true, false}.

Note, that to avoid overloading the system, the monitoring supports GeographicChangeSpace only for long stay (i.e., when duration of change exceeds 30 days). Thus, when a change in the geographical space of learner is detected, the monitor informs the system, this latter, ask the learner to verify if he will stay more than 30 days and send feedback to the monitoring.

 Considering the soft goals satisficing view (see Figure 6), the view supports 13 claims and 4 softdependencies. For instance, C8 indicates that using Text course fully satisfies WaitingTimeOptimization, and SD4 indicates that when NetworkSpeed is low, the soft-goal WaitingTimeOptimization should be fully satisfied (level 4).

Note that, the last view acts as a filter and permits the exclusion of non-relevant configurations by using the claims and soft-dependencies to reason about soft-goals. The combination of the five SD defines 16 scenarios of soft goal satisfaction. Within each scenario, the monitoring considers the variation of course materials and learner preferences. Without the proper constraints on the soft goal satisficing view, the configuration space grows exponentially. In our running example, each scenario has around 40 possible configurations.

Simulations

The primary objective of our requirements monitoring is the detection of deviations. In the following, we present two examples to illustrate how the requirements monitoring infrastructure dynamically detects a satisfaction problem using the generated constraint satisfaction problem and plans optimal configurations.

Verbal Learner Example

Let us suppose that we have a verbal learner, i.e. she understands information more effectively by listening to sounds and spoken words, according to Felder & Silverman [START_REF] Felder | Learning and teaching styles in engineering education[END_REF]. Consequently, the system prefers to deliver video lectures to this learner. Nevertheless, in this example video lectures are only available in high quality, i.e. they require high bitrate. This example also has text lectures available.

The soft goals satisficing view defines two claims; these claims affect the expected level of the soft goal WaitingTimeOptimization for the Video operationalization, as illustrated in Figure 6. The claims CL9 and CL13 require Video refined from the goal IndividualizeMultimediaDelivery. The soft goals satisficing view also expresses, with soft dependency SD4, the required level of the soft goal WaitingTimeOptimization. The claims and SD required in this example can be expressed in a simplified way as:

CL8_selected  Text_selected  Graphics_Selected CL8_selected  WaitingTimeOptimization_ExpectedLevel = 4 CL9_selected  Video_selected  VideoBitRate = low CL9_selected  WaitingTimeOptimization_ExpectedLevel = 1 CL13_selected  Video_selected  VideoBitRate = high CL13_selected  WaitingTimeOptimization_ExpectedLevel = 4 SD4_selected  NetworkSpeed=low SD4_selected  WaitingTimeOptimization_RequieredLevel = 4
Claim CL8 indicates the highly positive influence on the satisfaction of WaitingTimeOptimization (expected level = 4) when the system delivers text or graphics. Claim CL9 indicates the highly positive influence on over the satisfaction of WaitingTimeOptimization (expected level = 4) when the system delivers video, and the VideoBitRate is low. Claim CL13 indicates the expected denial in the satisfaction of WaitingTimeOptimization (expected level = 1) when the system delivers video, and the VideoBitRate is high.

Soft dependency SD1 specifies that if the NetworkSpeed connection is low then the waiting time optimization should be fully satisfied.

In this example we consider two context scenarios, the first NetworkSpeed variable is high and second NetworkSpeed variable is low. In both scenarios, we guaranty the VideoBitRate in high. In the former, no constraints exist over the soft goal WaitingTimeOptimization; i.e., the unique soft dependency, SD1, for this soft goal is not selected. Figure 8, on the left, presents this configuration in VariaMos.

On the contrary in the latter, the system needs to satisfice the soft goal WaitingTimeOptimization, regarding the network speed is low. The initial configuration uses text as CL8 also has a highly positive influence on WaitingTimeOptimization. Figure 8, on the right, presents this configuration in VariaMos. Nevertheless, the monitoring constantly takes the bandwidth measurement. If it sees that the bandwidth is getting better, it notifies the system to change to the Video operationalization as this is the preferred option for the learner´s learning style.

Frequency of Use Example

Let us suppose we have a learner that is not a frequent visitor of the system. In this case, the system should maintain relevant communications using external systems, such as ExternalEmail or SMS. Nevertheless, if the user becomes a frequent visitor, the system should encourage interactive communications.

The claims and SD required in this example can be expressed in a simplified way as:

Cl1_selected  SMS_selected ExternalMail_selected CL1_selected  RelevantCommunications_ExpectedLevel = 4 CL1_selected  InteractiveCommunications_ExpectedLevel = 1 Cl2_selected  Chat_selected InternalMail_selected Forum_selected CL2_selected  RelevantCommunications_ExpectedLevel = 1 CL2_selected  InteractiveCommunications_ExpectedLevel = 4 SD2_selected  (FrequencyOfUse= Low) SD2_selected  RelevantCommunicacions_RequieredLevel = 4 10 SD5_selected  (FrequencyOfUse= High) SD5_selected  InteractiveCommunicacions_RequieredLevel = 4
In this example we consider two context scenarios, the first FrequencyOfUse variable is low and the second FrequencyOfUse variable is high. In the former, the system needs to satisfice the soft goal RelevantCommunicacion when the frequency of use is low. Figure 9, on the left, presents this configuration in VariaMos. In the latter, the system needs to satisfice the soft goal InteractiveCommunicacion, regarding the frequency of use is high. The initial configuration uses ExternalMail or SMS as CL2 also has a highly positive influence on RelevantCommunicacion. Nevertheless, the monitoring constantly takes monitor the access logs to identify frequent users. Figure 9 presents the configuration in VariaMos on the right. If it sees that the user becomes a frequent user, it notifies the system to change to the Chat, InternalMail or Forum operationalization as this satisfice the soft goal InteractiveCommunication.

Configurations of a scenario

From the generated optimal configurations, the e-learning system can decide the adaptation strategy to follow when the requirements monitoring detects a satisfaction problem. For Instance, we chose a scenario with the following context variables: GeographicChangeSpace is true, IsLongStay is true, FrequencyOfUse is low, NoisyEnvironment is false and NetworkSpeed is low. For this scenario, we obtained 40 relevant configurations. They are relevant because they ignore the selection between operationalization goals without influence in the adaptation, for example, the selection of Chat, Forum or InternalMail have the same influence.

From the scenario, we are interested in the visual learner that prefers video for learning materials. Thus, Table 1 presents the aggregated configurations for video, from 40 configurations, only 8 remain relevant. To simplify the table, we do not display not selectable claims. The columns of Table 1 Finally, in the table, the first configuration is the only alternative that satisfice all the soft goals. As the scenario defines low NetworkSpeed, the alternative requires low VideoBitRate to satisfice the soft goal WaitingTimeOptimization. Other alternatives do not satisfy all soft goals but is also possible to select them.

L N Y N Y N Y --N Y Y N N Y Y Y Y Y N 4 4 4 4 1 Y Y Y Y Y L N Y N Y Y N --N Y N Y N Y Y Y Y Y N 4 4 4 4 1 N Y Y Y Y L Y N N Y N Y --Y N Y N N Y Y Y Y Y N 4 4 4 4 1 Y N Y Y Y L Y N N Y Y N --Y N N Y N Y Y Y Y Y N 4 4 4 4 1 N N Y Y Y H N Y N Y N Y --N Y Y N Y Y Y Y Y Y N 4 4 4 4 1 Y Y Y N Y H N Y N Y Y N --N Y N Y Y Y Y Y Y Y N 4 4 4 4 1 N Y Y N Y H Y N N Y N Y --Y N Y N Y Y Y Y Y Y N 4 4 4 4 1 Y N Y N Y H Y N N Y Y N --Y N N Y Y Y Y Y Y Y N 4 4 4 4 1 N N Y N Y

RELATED WORK

This research work is at the intersection of Dynamic Adaptive Systems (DASs) and adaptive e-learning systems.

While the literature widely addresses DAS development, we are interested by runtime monitoring techniques to detect deviations at runtime. The concept of requirements monitoring originates with Fickas and Feather [START_REF] Fickas | Requirements monitoring in dynamic environments[END_REF], which means gather information that can determine whether and to what degree a running system is meeting its requirements. Later in other paper [START_REF] Feather | Reconciling system requirements and runtime behavior[END_REF], they proposed a runtime event-monitoring system that combines KAOS goal driven specification and FLEA (Formal Language for Expressing Temporal Combinations of Events). FLEA translates KAOS assertions in temporal combinations of events. Whenever an event occurs, it is automatically stored in a database and its defined action is executed. Subsequently, Robinson [START_REF] Robinson | Monitoring web service requirements[END_REF] extended Feather's model to address the problem of web services monitoring. The KAOS model was used to define requirements model at design time while a database was used to support the runtime analysis. Goldsby et al. [START_REF] Goldsby | Goal-based modeling of dynamically adaptive system requirements[END_REF] used i* goal model for requirements specification, but they assume that they have no guarantee that such DAS could perform requirements engineering at runtime. Finally, despite the wide use of goal models like KAOS and i* to represent requirements specification, however, these models only help list different strategies that can be performed and they do not support system evolution. Consequently, the process of requirements monitoring using these approaches still depends on a static monitoring strategy that enumerate all possible alternative behaviour. To address this gap, Baresi et al. [START_REF] Baresi | Adaptive goals for self-adaptive service compositions[END_REF] have modified KAOS goal specification and extended it by adaptive goals. The idea consists of using a membership function to assess satisfaction requirements of goals at runtime and when some requirements reach a boundary trigger suitable adaptation actions (adding/removing goals). The system is then guided by a fuzzy logic operators, which were already used in RELAX [START_REF] Whittle | Relax: Incorporating uncertainty into the specification of self-adaptive systems[END_REF] a declarative approach for specifying requirements for DAS. In contrast to use declarative approaches accounting for more flexibility, Sawyer et al. [START_REF] Sawyer | Using constraint programming to manage configurations in self-adaptive systems[END_REF] proposed an approach to represent and transform an extended goal driven requirements model into a constraint program to manage the configuration of Self-adaptive systems. In the same line with this approach we propose to use REFAS language for requirements specification and automatically transform the model into a constraint satisfaction problem. Our approach has the advantage that is guided by the graphical tool VariaMos, which allows the designer a performance modelling and verification of the specification through simulations as presented in this paper.

In addition to goal-driven requirements, formalisms like probabilistic and real-time logics have been widely used for requirements specification whose formal verification can then be carried out using probabilistic model checker [START_REF] Calinescu | Dynamic QoS management and optimization in service-based systems[END_REF]. Nevertheless, the formalisation and inference using such techniques are always complex and resources consuming [START_REF] Lalanda | Autonomic Computing[END_REF]. In line with these approaches, Calinescu et al. [START_REF] Calinescu | Dynamic QoS management and optimization in service-based systems[END_REF], proposed a Dynamic QoS management and optimization in service-based systems. They adopt Markov model to determine quantitatively the reliability and performance quality metrics of service-based systems, which are then formally and automatically analyzed to identify and enforce optimal system configurations. Ghezzi et al. [START_REF] Ghezzi | Runtime monitoring of component changes with spy@ runtime[END_REF] presented SPY@RUNTIME approach that focus on verification of system behaviour at runtime. This latter is represented by finite state automata. The tool can detect change and notify system designer by continuously checking the executed program against a specification. In contrast to runtime verification that reacts just after anomalies are detected, our purpose is to predict the deviations.

On the other hand, significant research effort has been devoted to support the development of adaptive elearning systems including techniques for learning monitoring. To the best of our knowledge, this latter consist of just recording student interaction and analyzing log data to offer a visualization that help instructors become aware of what is happening in distance learning classes ([33][34] [START_REF] Romero-Zaldivar | Monitoring student progress using virtual appliances: A case study[END_REF]), but it remains to see if the instructors are willing to invest significant time and effort required for continuous monitoring. In contrast, to passive monitoring, our approach leads to detect deviations from desired learning requirements at runtime and notify the system with a list of alternative configurations. So it can adjust its strategies.

Figure 2 :

 2 Figure 2: Runtime Requirements monitoring framework of adaptive e-learning systems

Figure 1 :

 1 Figure 1: Requirements monitoring at design time

Figure 3 :Figure 4 :

 34 Figure 3: Variability view

Figure 6 : Context view 8 Figure 7 :

 687 Figure 6: Context view

Figure 8 :

 8 Figure 8: Configuration scenarios for Verbal Learner using VariaMos tool

Figure 9 :

 9 Figure 9: Configuration scenarios for Frequency of Use using VariaMos tool

  are then organized as follow: Column 1 presents the VideoBitRate variable with Low and High values. Columns 2-9 represent the selection (Y) or rejection (N) of one or more operationalizations, in the last two cases the selection is irrelevant (-). Columns 10-15 represent the activation (Y) or deactivation (N) of claims. Columns 16-20 represent the soft dependency activation (Y) or deactivation (N), columns 21-25 represent the soft goals required satisfaction levels and columns 26-30 represent satisfaction (Y) or denial (N) of the soft goals.

Table 1 :

 1 Configurations for verbal learner style in a particular scenario

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
	VideoBitRate	Chat OR Forum Or InternalMail	SMS OR ExternalMail	Audio XOR Graphics XOR Text	Video	Online Discussion Group	Physical Self-Help Gr	Use Captions	Use Subtitles	CL1	CL2	CL3	CL4	CL9	CL13	SD1	SD2	SD3	SD4	SD5	GroupHomogeneity -Required Level	RelevantCommunication -Required Level	AccesibilityEnhacement -Required Level	Level WaitingTimeOptimization -Required	Level InteractiveCommunication -Required	GroupHomogeneity -Satisfice	RelevantCommunication -Satisfice	AccesibilityEnhacement -satisfice	WaitingTimeOptimization -Satisfice	InteractiveCommunication -satisfice

http://variamos.com/

CONCLUSION

In this paper, an automated approach for requirements monitoring was introduced to explicitly support the lack of dynamic requirements monitoring in adaptive e-learning systems, which allow these systems to respond flexibly to dynamic learners needs and be aware of their environments. Our approach defines and implements the autonomic computing MAPE loop architecture. The loop control continuously checks the requirements satisfaction under changing context using a CSP solver. The strengths of our approach are that the requirements model is specified by means of a language that combines goal-driven requirements with features and claims, and it is fully automated. Thus, the requirements model is automatically transformed into a CSP, and the verification of the requirements model is carried out through simulations using VariaMos tool. With this automation, we have two advantages: first, this avoids loss of information and misinterpretation of the specification during the transformation. Secondly, it explores the power to reason about goals to represent complex constraints and expressiveness of constraint programming.

As the next step, we first aim to improve the generated constraint program and implement our monitoring framework and then study its impact on the learning process and learners' satisfaction using real world data.

While the focus of this paper was add "self-adaptability" to adaptive e-learning systems by allowing the evolution of these systems at runtime using constraint programming, future work will explore the proposed approach in the verification and the evaluation of adaptive e-learning systems.


Filippo Santambrogio

Xu-Jia Wang

Convexity of the support of the displacement interpolation: counterexamples

Given two smooth and positive densities ρ 0 , ρ 1 on two compact convex sets K 0 , K 1 , respectively, we consider the question whether the support of the measure ρ t obtained as the geodesic interpolant of ρ 0 and ρ 1 in the Wasserstein space W 2 (R d ) is necessarily convex or not. We prove that this is not the case, even when ρ 0 and ρ 1 are uniform measures.

Introduction

One of the main features of optimal transport theory (we refer to [START_REF] Villani | Optimal Transport. Old and New. Grundlehren der Mathematischen Wissenschaften[END_REF] and [START_REF] Santambrogio | Optimal Transport for Applied Mathematicians[END_REF] for a general presentation) is the fact that it provides an original and efficient way to define interpolations between probability measures.

Given a domain Ω ⊂ R d (that we take compact for simplicity and convex for the sake of the interpolation), we define the space W 2 (Ω) as the space of probabilities on Ω endowed with the distance W 2 , defined through

W 2 2 (µ, ν) = min Ω×Ω |x -y| 2 dγ : γ ∈ Π(µ, ν) ,
where Π(µ, ν) is the set of the so-called transport plans, i.e.

Π(µ, ν) = {γ ∈ P(Ω × Ω) : (π x ) # γ = µ, (π y ) # γ = ν, }, where π x (x, y) := x and π y (x, y) = y are the standard projections on the two factors of Ω × Ω. It is possible to prove that the above minimization problem has a solution, which is unique and of the form γ = (id, T ) # µ (i.e. it is concentrated on the graph of a map T : Ω → Ω, called optimal transport map) in many situations (in particular if µ ≪ L d ) and that W 2 , i.e. the square root of the minimal value above, is indeed a distance on P(Ω).

The space W 2 (Ω) can be checked to be a geodesic space, where for µ, ν ∈ P(Ω) the (unique) geodesic curve connecting them is obtained through

ρ t := ((1 -t) id +tT ) # µ, (1.1)
where T is the optimal transport map from µ to ν. This provides a useful interpolation between µ and ν which is very different from the linear interpolation (1 -t)µ + tν. In particular, it is useful in many applications, for instance in image processing: this is the case when doing histograms interpolations (roughly speaking, the average between a distribution of pixel colors which are almost white and another were they are almost black should be a a distribution with intermediate grey pixels, and not one with half pixels which are white and half which are black), or when artificially creating intermediate images between two pictures representing a same object which ahs moved (and the goal is to find the same object in the middle, instead of two half objects at the starting and arrival spots). But this very interpolation has also a lot of mathematical applications, as it was first pointed out by McCann in [START_REF] Mccann | A convexity principle for interacting gases[END_REF]. Indeed, McCann found a class of functionals F : P(Ω) → R which are convex along these geodesic lines (but not necessarily convex in the usual sense, think for instance at µ → |x -y| 2 dµ(x)dµ(y)), thus making possible to obtain uniqueness results or sufficient optimality conditions (see [START_REF] Blanchet | Existence and uniqueness of equilibrium for a spatial model of social interactions[END_REF], for instance) for variational problems involving them. Also, this notion of convexity, called displacement convexity (the above interpolation is also called displacement interpolation) is an important notion in the study of gradient flows of these functionals (see [START_REF] Ambrosio | Gradient Flows in Metric Spaces and in the Space of Probability Measures[END_REF]). We also recall that the interpolation ρ t can be found numerically via one of the most classical algorithm for optimal transport, the so-called Benamou-Brenier method [START_REF] Benamou | A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem[END_REF]. By solving the kinetic energy minimization problem min

1 0 Ω |v t | 2 dρ t dt : ∂ t ρ t + ∇ • (v t ρ t ) = 0 ,
among curves of measures with given initial and final data, one recovers the above interpolation, and the optimal velocity field v t allows to find T (as we have v t (x) = (T -id) • (T t ) -1 with T t := (1 -t) id +tT ). Finally, let us remark that the interpolated measures ρ t can also be considered as weighted barycenters between ρ 0 and ρ 1 , as they solve the minimization problem min (1 -t)W 2 2 (ρ, ρ 0 ) + tW 2 2 (ρ, ρ 1 ) : ρ ∈ P(Ω) , a minimization problem which has ρ t as unique solution (provided one of the measures ρ 0 , ρ 1 is absolutely continuous). This problem has also been considered when more than two measures are given, in order to find the weighted barycenter of many of them, solving (see [START_REF] Agueh | Barycenters in the Wasserstein space[END_REF])

min n i=1 λ i W 2 2 (ρ, ρ i ) : ρ ∈ P(Ω) (1.2)
(a minimization problem that can be also recast in the setting of multi-marginal problems, as in [START_REF] Gangbo | Optimal maps for the multidimensional Monge-Kantorovich problem[END_REF]). Note that when n ≥ 3 this variational definition of the barycenter is the only possible one, differentely from the case n = 2 where one can simply use the geodesic in W 2 .

In optimal transport theory, and in particular for regularity issues, the convexity of the support of a measure is an important fact, and some results are only available under this assumption. In particular, the optimal transport map between two smooth densities ρ 0 , ρ 1 is smooth itself, provided their supports are convex (this theory was first developed by Caffarelli, [START_REF] Caffarelli | A localization property of viscosity solutions to the Monge-Ampère equation and their strict convexity[END_REF][START_REF] Caffarelli | Some regularity properties of solutions of Monge Ampère equation[END_REF][START_REF] Caffarelli | Interior W 2,p estimates for solutions of the Monge-Ampère equation[END_REF], see [START_REF] De | The Monge-Ampère equation and its link to optimal transportation[END_REF] for a survey). Since it is possible to write optimality conditions for the minimizers of (1.2) in terms of the optimal maps T i sending the optimal ρ onto the various ρ i (which actually amounts to a system of Monge-Ampère equations), one could imagine some boothstrap strategy to study the regularity of ρ using that of the T i . Yet, this requires as a preliminary fact to check the convexity of spt(ρ)! Note that this is not needed for n = 2, since formula (1.1) allows to deduce the regularity of ρ t from that of T , which is the optimal map from ρ 0 to ρ 1 : in particular, only the convexity of the supports of these two measures is needed. Anyway, the question whether the support of the barycenter is guaranteed to be convex whenever the supports of the ρ i are so is a very natural question. The case n = 2 is the easiest to study and if the answer is no in such a case there is no hope to get yes in the case n ≥ 3.

Moreover, independently of the regularity motivation, this question is very natural from a geometric point of view, as a question on convex bodies. One can for instance insist on the case where ρ 0 and ρ 1 are uniform measures on convex sets and look at spt(ρ t ) as an interpolation between these sets. More generally, one could wonder if the interpolation between log-concave densities (of the form ρ = e -V for a convex function V : R d → R ∪ {+∞}) is still log-concave. This is true in dimension 1 (and, contrarily to the question on the supports, it is non-trivial1 ).

Unfortunately, the present paper shows that the answer to these questions is no. More precisely, we will see (Theorem 1) that on any smooth convex domain on R 2 we can find smooth and positive densities ρ 0 , ρ 1 such that the support of ρ 1/2 is not convex, and that this can also be done with uniform measures on (different, of course) convex sets.

The case of two segments or two curves

Consider two Lipschitz curves ω 0 , ω 1 : [a, b] → R d , and two measures ν 0 , ν 1 ∈ P([a, b]). We need to discuss the optimal transport between the measures ρ 0 and ρ 1 , defined through µ i := (ω i ) # ν i for i = 0, 1, in connection with the optimal transport between ν 0 and ν 1 . Note that, if d > 1, these measures fall out of the usual assumptions for the existence of an optimal transport map between them, as it is not true that µ 0 does not give mass to "small" (i.e. (d -1)-dimensional, or smaller) sets (see [START_REF] Brenier | Décomposition polaire et réarrangement monotone des champs de vecteurs[END_REF][START_REF] Mccann | Existence and uniqueness of monotone measure preserving maps[END_REF] and, more recently, [START_REF] Gigli | On the inverse implication of Brenier-McCann theorems and the structure of (P 2 (M ), W 2 )[END_REF], for the exact conditions for this existence result).

Yet, the fact that both measures are one-dimensional, allows to act differently (by the way, let us mention a recent preprint, [START_REF] Chiappori | Pass Multi-to one-dimensional transportation[END_REF], on the case where optimal transport between measures in different dimensions is considered). We will suppose that ω 0 and ω 1 are such that ω0 (t) • ω1 (s) > 0 for a.e. (t, s) ∈ [a, b] 2 . In this case what happens is that optimal transport plans γ ∈ Π(µ 0 , µ 1 ) for the quadratic cost |x -y| 2 are just obtained as the image of optimal transport plans in Π(ν 0 , ν 1 ) through the map (t, s) → (ω 0 (t), ω 1 (s)).

Indeed, it is well-known that transport plans γ are optimal for the quadratic cost if and only if their support is monotone, in the sense that (x, y),

(x ′ , y ′ ) ∈ spt(γ) implies (x -x ′ ) • (y -y ′ ) ≥ 0.
Yet, for (x, y) = (ω 0 (t), ω 1 (s)) and x ′ = (ω 0 (t ′ ), ω 1 (s ′ )), we have

(x -x ′ ) • (y -y ′ ) = t ′ t ω0 (τ )dτ • s ′ s ω1 (σ)dσ = t ′ t s ′ s ω0 (τ ) • ω1 (σ) dσdτ,
and, since the integrand in the last expression is positive, the sign of the integral is the same as the sign of (t ′ -t)(s ′ -s). This proves that, if we write γ = (ω 0 × ω 1 ) # γ, the monotonicity of the support of γ is equivalent to the 1D monotonicity of that of γ. In particular, when ν 0 ≪ L 1 , the optimal transport plan in Π(ν 0 , ν 1 ) is unique and easy to find, and it is induced by a map, the unique monotone increasing map T sending ν 0 onto ν 1 ; as a consequence, there is a unique optimal transport plan from µ 0 to µ 1 , and it is induced by the map ω 1 • T • ω -1 0 . We just point out that the situation is even simpler in case ω 0 and ω 1 are affine functions, i.e. their images are two segments S 0 and S 1 . Up to transations, we can that S 0 and S 1 are of the form S i = {tv i , t ∈ [0, 1]}, for some vectors v i ∈ R d (i = 0, 1). Translating the segments is not restrictive as we know that optimal transport and translations commute.

Then, we distinguish three cases: either

v 0 • v 1 = 0, or v 0 • v 1 > 0, or v 0 • v 1 < 0.
In the first case it is easy to check that, for every x ∈ S 0 and y ∈ S 1 , we have |x -y| 2 = |x| 2 + |y| 2 . This implies |x -y| 2 dγ = |x| 2 dµ 0 + |y| 2 dµ 1 for every γ ∈ Π(µ 0 , µ 1 ), and hence every transport plan between these two measures is optimal (in particular, there is no uniqueness). In the case v 0 • v 1 > 0, we have, for x = tv 0 , y = sv 1 and c

= v 0 • v 1 , |x -y| 2 = c|t -s| 2 + (|v 0 | 2 -c)t 2 + (|v 1 | 2 -c)s 2 ,
where the first term in the right hand side is a positive multiple of the quadratic cost in the variables (t, s) and the second term is separable. The case v 0 • v 1 < 0 can be reduced to the previous one up to replacing v 0 with -v 0 and translating again. This means that, whenever v 0 and v 1 are not orthogonal, the optimal transport between the two measures can be computed as if we were in dimension one, i.e. it is the monotone increasing map. The orientation of the segments (which is crucial to define the monotonicity of the map) has to be chosen so that the scalar product is positive.

With these considerations in mind, we consider the following esample. Let S 0 = {(t, at) : t ∈ [-1, 1]} and S 1 = {(t, -at) : t ∈ [-1, 1]} be two segments in R 2 with middle point at the origin, and connecting (-1, -a) to (1, a) and (-1, a) to (1, -a), respectively. We select a ∈]0, 1[ so that the correct orientation of the two segments is the one based on the abscissas. Then we consider a probability measure µ 0 on S 0 with linear density, proportional to 1 -t, and µ 1 a probability measure on S 1 with density proportional to t + 1. A simple calculation provides the formula for the optimal trasnport map

T (t, at) = (-1 + 4 -(1 -t) 2 , a(1 -4 -(1 -t) 2 ))
and the shape of the interpolated measure is represented in the following figure. The fact that this interplation is supported on a curve which is not a segment (it is actually part of the boundary of an ellipse) will be the key point for our counter-examples.

spt µ 0 = S 0 spt µ 1/2 spt µ 1 = S 1 • • • • • • • • • • • • Figure 1:
The support of µ 1/2 when µ 0 and µ 1 have linear densities on the segments S 0 and S 1 .

Figure 2: The supports of the interpolations µ t for t = k/6.

Counterexamples with convex bodies

In this section we use the previous considerations to provide a wide class of cases where two measures ρ 0 and ρ 1 have smooth and positive densities on their supports, their supports are convex sets, but the support of the interpolant ρ 1/2 cannot be convex.

Geometric setting

We consider now a convex set Ω ⊂ R 2 and two portions Γ 0 and Γ 1 of its boundary, and we suppose that, in suitable coordinates, we have Γ 0 = {(t, f (t)) : t ∈ I} and Γ 1 = {(t, g(t)) : t ∈ J} for some disjoint intervals I = [a, b] and J = [c, d] and f : I → R, g : J → R Lipschitz functions, with 0 < f ′ < λ and 0 > g ′ > -λ for a suitable constant λ ∈ (0, 1). We suppose f (b) = g(c) and f (a) = g(d). Let us call x = (a, f (a)) and x ′ = (b, f (b)) the endpoints of Γ 0 , and y = (c, g(c)) and y ′ = (d, g(d)) those of Γ 1 . We also take two points x ′′ ∈ Γ 0 and y ′′ ∈ Γ 1 , with the same ordinate, smaller than (f (a) + f (b))/2 = (g(c) + g(d))/2. We consider two measures µ 0 ∈ P(Γ 0 ) and µ 1 ∈ P(Γ 1 ) such that the optimal transport plan between them exists, is unique, and is induced by a map T with T (x) = y, T (x ′ ) = y ′ and T (x ′′ ) = y ′′ .

The situation is the one sketched in the picture below. We now consider two sequence of densities ρ n 0 and ρ n 1 weakly converging to µ 0 and µ 1 , respectively, and concentrated on Ω (we will see different examples later where their support can be, or not, the whole domain Ω). Let us call ρ n 1/2 the interpolated density between them at time t = 1/2. We will prove that, for n large enough, it is not possible that the support of ρ n 1/2 is convex. Lemma 1. Let Ω be a convex domain and µ 0 and µ 1 two measures on the segments S 0 and S 1 as in the geometric setting above. Let ρ n 0 and ρ n 1 be smooth densities weakly converging to ρ 0 and ρ 1 , respectively, and concentrated on Ω. Let ρ n 1/2 be the middle point of the geodesic in W 2 (Ω) between them. Then, for n large enough, the support of ρ n 1/2 is not convex.

Proof. Consider the optimal transport plan γ n ∈ Π(ρ n 0 , ρ n 1 ) for the quadratic cost. By uniqueness

• x • x ′ • y ′ • y • x ′′ • y ′′ I J Γ 0 Γ 1 Ω Figure 3: The configuration of Ω, Γ 0 , Γ 1 .
of the optimal plan γ from µ 0 to µ 1 , it is clear that γ n ⇀ γ. From the fact that the support of γ is included in the Hausdorff limit of the supports of γ n , we deduce the existence of points (x n , y n ), (x ′ n , y ′ n ), (x ′′ n , y ′′ n ) ∈ spt(γ n ) converging to (x, y), (x ′ , y ′ ) and (x ′′ , y ′′ ), respectively. Since ((x n + y n )/2, (x ′ n + y ′ n )/2) belong to the support of ρ n 1/2 , if this support were convex, it should also contain p n := (x n + y n + x ′ n + y ′ n )/4. For simplicity, and without loss of generality, we will suppose that (x + y + x ′ + y ′ )/4 = 0 (this is possible up to a translation). Now, suppose p n spt(ρ n 1/2 ). This means that there exist z n , w n ∈ Ω such that (z n + w n )/2 = p n and (z n , w n ) ∈ spt(γ n ). Note that the monotonicity of spt(γ n ) implies the inequality

(w n -y ′′ n ) • (z n -x ′′ n ) ≥ 0.
Up to subsequences, we can pass to the limit and obtain the existence of two points z, w ∈ Ω such that z + w = 0 and (w -y ′′ ) • (z -x ′′ ) ≥ 0. Using w = -z this translates into z ∈ Ω ∩ (-Ω) and

z - x ′′ -y ′′ 2 2 ≤ x ′′ + y ′′ 2 2 .
This means that z belongs to the intersection of Ω, -Ω, and a ball centered at q := (x ′′ -y ′′ )/2 with radius |(x ′′ + y ′′ )/2|. But it is possible to see that this intersection is empty, as one can observe from the next figures. Indeed, the closest point of Ω ∩ (-Ω) to q is the point q on the intersection of horizontal line through 0 with ∂Ω, yet it does not belong to the required ball, as the segment [x ′′ , -y ′′ ] is a diameter of this ball, and q sees both segments [x ′′ , q] and [q, -y ′′ ] under an angle smaller than 45 • because of the derivative condition on f and g.

We can now provide our main counter-examples.

Theorem 1. For every smooth convex body Ω ⊂ R 2 there exist two smooth probability densities ρ 0 and ρ 1 in P(Ω), strictly positive on Ω, such that the support of their interpolation ρ 1/2 is not convex.

• 0 = x+y+x ′ +y ′ 4 • x ′′ +y ′′ 2 • x • x ′ • y ′ • y • x ′′ • y ′′ • -y ′′ • q = x ′′ -y ′′ 2 Γ 0 Γ 1 Ω -Ω
Figure 4: Ω, -Ω, and the reflected points.

• q • x ′′ • -y ′′ • q Ω -Ω
Figure 5: A zoom around q and q.

Proof. It is enough to notice that it is always possible to find two portions of boundary Γ 0 , Γ 1 ⊂ ∂Ω such that the assumptions of Lemma 1 (i.e. those of the above geometrical setting) are satisfied (it is enough to choose Γ 0 and Γ 1 close enough to an extremal point of Ω, and orientate the coordinate system so that this point is the unique point of Ω with maximal ordinate and to choose suitable non-uniform probabilities µ 0 and µ 1 on Γ 0 and Γ 1 ). Then, we take any smooth and strictly positive approximations ρ n 0 and ρ n 1 and choose ρ 0 = ρ n 0 and ρ 1 = ρ n 1 , for n large enough.

Remark 1. The same procedure can be applied to any convex domain Ω, provided that there exist portions of its boundary sith tangent vectors forming angle strictly smaller than 90 • , which allows to choose a suitable coordinate system and fit the geometrical setting. The only convex domains in R 2 where this is not possible are the rectangles and the acute (or right) triangles.

Theorem 2. There exist convex sets A, B ⊂ R 2 such that, setting ρ 0 = |A| -1 L 2 A and ρ 1 = |B| -1 L 2 B, the support of the middle point interpolation ρ 1/2 is not convex.

Proof. 1 L 2 A n and ρ n 1 = 1 Figure 6 :

 12116 Figure 6: Counter-example with uniform measures.

This result has been proven by Young-Heon Kim via un-published computations, in the hope of generalizing to higher dimensions.