Raouf Khalil
email: raouf.khalil-ayad@lip6.fr

Andrii Dudka

Dimitri Galayko

Ramy Iskander

Philippe Basset
email: p.basset@esiee.fr

Design and Modeling of a Successive Approximation ADC for the Electrostatic Harvester of Vibration Energy

Keywords: Energy harvesting, successive approximation ADC, VHDL-AMS, calibration, MEMS

This paper presents a functional design and modeling of a successive approximation analog-to-digital converter (ADC) and its application in the conditioning circuit of the vibration energy harvester. The paper published on BMAS'09 highlighted the necessity of a smart digital control to calibrate the system, which requires in turn an ultra low power supplied ADC. The harvester and the ADC are designed using a CMOS 0.35µm High Voltage technology and modeled in a mixed VHDL-AMS/ELDO environment. The supply voltage of the ADC is 2.5V. The whole system was simulated using a mixed signal AdvanceMS simulator.

INTRODUCTION

Modern self-powered autonomous electronic micro-systems, such as wireless micro-sensor network, embedded monitoring systems, biomedical implants, tend to incorporate more functions into smaller surfaces of devices and also are required to operate for a relatively long time without human intervention. On the other hand, the evolution in power source development is not following the same trend: the power supply sources still occupy an important part of size and weight of the system. The energy capacity, as well as lifetime of the existing sources is limited, and alternative energy sources are needed to overcome these bottlenecks. The autonomy of the devices can be extended by extracting power from ambient energy sources such as light, temperature gradients, mechanical vibration and others. Longlasting, self-renewable, chip-compatible energy harvesting sources are therefore a subject of research for a growing number of scientists and engineers. This study is focused on conversion of the energy of external mechanical vibrations into electrical energy with a use of an electrostatic transducer, which operates as a variable capacitor implemented in a MEMS technology. Harvesting the vibration energy with the capacitive transducer requires complex conditioning electronics for managing the transducer operation and for interfacing the transducer with the load. Harvester, operating under conditions of variable vibration parameters, claims a "smart" power management and adaptive control of the system operation. Our previously published work in BMAS'09 [START_REF] Dudka | Vhdl-ams modeling of adaptive electrostatic harvester of vibration energy with dual-output dc-dc converter[END_REF] addressed the system adaptation to the variable amplitude of vibrations and, consequently, proposed an adaptive operation algorithm which was implemented in a power management control block and modeled in VHDL-AMS.

The need of measurements of the voltages of the conditioning circuit used for the "smart" control electronics managing the operation of conditioning circuit and the interface with the load requires an analog-to-digital converter with ultra low power consumption. Power saving can be achieved in ADC through the selection of a suitable low-power ADC. The successive approximation ADC is known as one of the best candidates in terms of low-power [START_REF] Michael | An ultra low-energy adc for smart dust[END_REF]. This paper presents the design of a successive approximation ADC, and its modeling in the context of the conditioning circuit presented in [START_REF] Dudka | Vhdl-ams modeling of adaptive electrostatic harvester of vibration energy with dual-output dc-dc converter[END_REF]. The most critical blocks for the power consumption of the ADC are described at the electrical netlist level (the comparator and the digital-toanalog converter, DAC), and the control unit is described behaviourally in VHDL-AMS language. The main goal of the mixed modeling of the whole system (ADC+conditioning circuit) is an estimation of the power losses associated with the electromechanical power conversion and with the measures of the electrical state of the conditioning circuit needed for the calibration. This estimation doesn't take into account the consumption related with purely digital blocks.

In section 2, we summarize the basic architecture and the operation of the harvester as well as the calibration technique allowing the adaptation of the system to the vibration parameters. In section 3, we present the architecture of the successive approximation ADC and we explain the implementation and modeling approach for each block. In section 4, the connection of harvester system with the ADC, calibration technique is discussed and simulation results of the whole system are shown.

HARVESTER OPERATION

An electrostatic energy harvester consists of a mechanical resonator, an electromechanical transducer (based on MEMS technology) [START_REF] Basset | A batch-fabricated and electret-free silicon electrostatic vibration energy harvester[END_REF] and an electrical conditioning circuit managing the operation of the transducer and providing an interface with the load [START_REF] Dudka | Vhdl-ams modeling of adaptive electrostatic harvester of vibration energy with dual-output dc-dc converter[END_REF]. One of the possible architecture of conditioning circuit, initially proposed by Yen [START_REF] Yen | A variable-capacitance vibration-to-electric energy harvester[END_REF], is composed of two main parts: a charge pump and a flyback circuit controlled by a switch SW (Fig. 1). The charge pump circuit transfers electrical charges from a large initially pre-charged capacitor Cres toward a small temporary storage Cstore with the use of variable transducer capacitor Cvar. The energy for this charge pumping comes from the mechanical domain through the variations of the transducer capacitor. During the pumping, the converted energy is stored in the Cstore capacitor, the Cstore voltage Ustore increases and Cres voltage Ures decreases very slightly (since Cres >> Cstore). It has been shown that the energy conversion is maximal for a particular range (U1, U2) of Ustore [START_REF] Dudka | Vhdl-ams modeling of adaptive electrostatic harvester of vibration energy with dual-output dc-dc converter[END_REF], and when Ustore reaches the upper border of this range U2, a part of the charges of Cstore must be returned to Cres, so to put Ustore at the low limit U1 of this range. This is performed by the inductive flyback circuit. Topologically, the flyback circuit is similar to a Buck DC/DC converter, but with an output voltage Ures needed to be pulled up as efficiently as possible using the energy of Cstore. As soon as Ustore reaches U2, the Ustore is reduced to U1, the switch becomes of f and the inductor discharges on Cres through the diode D3. After this, a new charge pump operation cycle starts. From theoretical investigation [START_REF] Galayko | Mechanical/electrical power-aware impedance matching for design of capacitive vibration energy harvester[END_REF] U1 and U2 parameters are calculated as:

U1 = Ures + 0.1(Ustore max -Ures), U2 = Ures + 0.6(Ustore max -Ures). (1)
Here, Ustore max is the saturation voltage of the charge pump given by [START_REF] Yen | A variable-capacitance vibration-to-electric energy harvester[END_REF]:

Ustore max = Cmax Cmin Ures, (2)
where Cmax and Cmin are the maximal and minimal values which takes the transducer capacitance. From eq. ( 2), Ustore max depends on the ratio between Cmax and Cmin that are, in turn, related to the resonator vibration parameters such as frequency and amplitude, which usually vary in the time. Consequently, Ustore max voltage is not a fixed value and moreover can not be measured directly since during charge pumping Ustore never reaches the saturation [START_REF] Dudka | Vhdl-ams modeling of adaptive electrostatic harvester of vibration energy with dual-output dc-dc converter[END_REF].

In the paper presented on BMAS'09 we showed, however, that Ustore max can be measured in an ad-hoc calibration cycle, which repeats periodically (much more rarely then a charge pump+flyback cycle).

During the calibration cycle, the flyback is deactivated and the charge pump runs freely up to the saturation. At the saturation, the Ustore value can be measured and used as Ustore max in U1 and U2 calculation. The operation of the calibration cycle can be summarized as follow [START_REF] Dudka | Vhdl-ams modeling of adaptive electrostatic harvester of vibration energy with dual-output dc-dc converter[END_REF]: firstly, the charge pump is initialized (Ustore resets to Ures), secondly, periodic measurements of Ustore during the charge pumping are provided. At each measurement, Ustore is compared with the previously measured value. As soon as the difference ∆U between two neighboring measured values of Ustore becomes lower than a predefined minimal value ∆Umin, it is concluded that Ustore is saturated and the last measured value is considered as Ustore max. The calibration cycle ends by the updating of U1 and U2. Hence, between two calibration cycles, the system operates with optimized U1 and U2 switching parameters, which are likely to improve the energy yield of the harvester regarding to the variation of ambient conditions.

In order to calculate U1 and U2 during the system calibration, we need to measure Ustore max and Ures. Consequently, to interface analog voltages with the digital electric circuit we need to use an analog-to-digital converter.

Vibration energy harvesters provide low values of powers (tens microwatts), hence, the conditioning electronics, including ADC, should consume as few as possible. In this work, we demonstrate the design of the very low power consumption successive approximation ADC.

SUCCESSIVE APPROXIMATION ADC ARCHITECTURE

In Fig. 2, we can see how different parts of the successive approximation ADC are connected. In our topology, the signal is sampled in the first clock cycle and is converted in the next N clock cycles, where N is the number of bits. The sample and hold operation is achieved with the use of the DAC, when it is set in "sampling" mode. The DAC, allowing to achieve the successive approximation of the input voltage value, contains an array of binary weighted capacitors whose topology can be reconfigured by switches. The DAC output is connected to the negative input terminal of the comparator as it is shown in Fig. 3, while the common mode voltage Ucm is connected to the positive input terminal and the comparator output is connected to the control unit. The control unit represents the successive approximation register (SAR) that controls the DAC switches allowing to switch capacitors terminals to the three reference voltages: the supply voltage U dd , the common mode voltage Ucm = U dd /2 and the ground gnd. It generates the output digital word representing the digitally approximated input voltage. This architecture was described in details in [START_REF] Allam | Systematic design of a successive approximation analog-to-digital converter[END_REF].

Successive approximation ADC stages

This section describes stages of successive approximation ADC conversion, achieved in different modes. In the first half cycle of the first clock cycle, the DAC capacitors bottom plates in the capacitor array are connected to the input signal Uin, while the top plates are connected to U dd /2: this is the "sampling" mode and it corresponds to the configuration shown in Fig. 3. In the second half of the clock cycle, all bottom plates are connected to U dd /2: this is the inversion mode. After the first cycle, the control unit checks the comparator output (comp out). If it is high, it connects the largest capacitor bottom plate to U dd , if it is low, the control unit connects the largest capacitor bottom plate to gnd. This mode is called charge redistribution mode.

The same is repeated with all capacitors in the array, in N clock cycles. At i th clock cycle, the output of the comparator correspond to i th bit of the output ADC word. This bit value is saved by the control unit and after the end of the charge redistribution mode, the digital output of the control unit is equal to the digitally approximated input voltage. In Fig. 4, we can see how the voltage of the DAC top plates changes in every mode on the example of 8-bit successive approximation ADC.

Comparator Circuit

The comparator in Fig. 5 is designed in CMOS 0.35 µm technology. This is a semi-dynamic clocked architecture and it compares the output of the DAC UDACT op that is connected to the negative terminal and Ucm that is connected to the positive terminal. Transistors M1 and M2 are used to amplify the input signal. Transistors M3, M4, M9 and M10 implement a couple of inverters connected so to be a flip-flop (back to back inverters). Transistors sizes are chosen with a low aspect ratio so as to reduce the power consumption and with a large area to reduce the offset mismatch. The comparator uses an internal clock equal to 2.5KHz. Thus, using the resolution of the ADC N = 8 bit, the sampling fre-

Digital to Analog Converter Circuit

The DAC is designed in CMOS 0.35 µm technology and it contains 8 binary weighted capacitors in the array, the top plates are connected together. At each bottom plate, there are ideal switches to connect the bottom plate with the input signal and the three references as shown in Fig. 7. The choice of the unit capacitance value (Cu) depends on the input capacitance of the comparator, the needed resolution and the sampling frequency.

Control Unit VHDL-AMS Model

The output of the comparator is connected to the SAR control unit. At the sampling mode, the SAR control unit commands the switches so that the upper plates of the array are connected to U dd /2 and the bottom plates are connected to Uin. Then, at inversion mode, it commands switches so that the bottom plates are connected to U dd /2. In each clock cycle of the charge redistribution mode, depending on the comparator output, the control unit decides either to connect the corresponding weighted capacitor bottom plate to U dd or to gnd. In this way, the control unit raises or reduces voltages on the top plates of the capacitors array by binary weighed level voltages (U dd /4, U dd /8,...,U dd /256), so achieving the successive approximation of the input voltage. This block was described in VHDL-AMS language as it is shown in the code below. e nti ty c o n t r o l 4 i s generic ( n : i n t e g e r := 8 ) ; port ( --i n t e r n a l c l o c k : s i g n a l c l o c k : in s t d l o g i c ; --s a m p l i n g c l o c k : s i g n a l s t a r t : in s t d l o g i c ; --comparator o u t p u t t e r m i n a l : t e r m i n a l t o u t p : e l e c t r i c a l ; --t o c o n t r o l Uref s w i t c h e s t e r m i n a l t i n 0 1 b r , t i n 0 2 b r , t i n 0 3 b r , t i n 0 4 b r , t i n 0 5 b r , t i n 0 6 b r , t i n 0 7 b r : e l e c t r i c a l ; --t o c o n t r o l ground s w i t c h e s t e r m i n a l t i n 0 1 b g , t i n 0 2 b g , t i n 0 3 b g , t i n 0 4 b g , t i n 0 5 b g , t i n 0 6 b g , t i n 0 7 b g : e l e c t r i c a l ; --t o c o n t r o l Ucm s w i t c h e s : t e r m i n a l tin01bcm , tin02bcm , tin03bcm , tin04bcm , tin05bcm , tin06bcm , tin07bcm , tin08bcmx : e l e c t r i c a l ; t e r m i n a l tgnd : e l e c t r i c a l ; --o u t p u t b i t s : s i g n a l dout : out u n s i g n e d ( 7 downto 0 ) ) ; begin end e nti ty c o n t r o l 4 ; archi te cture f c t of c o n t r o l 4 i s --q u a n t i t y d e c l a r a t i o n --s i g n a l d e c l a r a t i o n begin p1 : process vari abl e i : i n t e g e r :=n ; vari abl e word : u n s i g n e d ( ( n-1)downto 0 ) ; begin --d

APPLICATION OF SAR ADC INTO THE HARVESTER CONDITIONING CIRCUIT

In this section, we present the use of the designed successive approximation ADC in the conditioning circuit of harvester, whose model architecture is shown in Fig. 8. The ADC measures only the Ustore voltage, whereas the value of Ures can be found from the determined value of the Ustore converted voltage as we will explain later in this section. For optimal operation, the harvester requires the high voltage on Cstore section, firstly, we discuss the divider architecture and its operation, then the use of ADC during the calibration cycle and, at last, the whole system simulation results.

Voltage Divider Circuit

In present work the division factor of divider is 20, since the maximal value for Ustore is limited by 50V and the voltage supplied by the ADC is 2.5V. The proposed divider consists of 2 resistors connecting in series, 2 switches and an output capacitor as shown in Fig. 9. At every sample, resistors divide Ustore by 20, and the divided voltage is stored in the capacitor C div , so that the successive approximation ADC can sample this value. The clock used in the divider (CLK DIV) has the same sampling frequency but with the smaller pulse width to decrease the power consumption.

The relation between Ustore and the divider output U out div can be calculated based on equation:

Ustore U out div = R1 + R2 R2 = 20 (3)
τ = R1 R2 • C div , (4)
The presented voltage divider circuit is designed in CMOS 0.35µm high voltage technology of Austrian Microsystem (AMS035HV), and modeled using the ELDO simulator.

Calibration Using Successive Approximation ADC

The calibration cycle starts with putting U1 to a very low value (zero), so that Cstore voltage becomes equal to Cres voltage. During 20 ms Ustore remains at the Ures value, which gives to the ADC enough time to measure it. After that, the flyback switch control orders the charge pumping to start, and Ustore starts to increase, up to the saturation. During this charge pumping, the voltage Ustore is measured with 3.6 ms sampling step. The goal of this measurement is to detect the Ustore max value. This is done as described in the section 2; the digital values corresponding to the neighboring samples of Ustore are compared, and when there are 2 consecutive steps have the same value, their value is considered as measured Ustore max (it means that ∆Umin mentioned in section 2 equals to the ADC resolution). At the end of the calibration cycle the flyback switch control block turns of f the ADC and U1 as well as U2 are calculated. Then, the normal mode (periodic charge pump+flyback cycles) starts till the next calibration cycle as it is shown in the Fig. 10.

Modeling Results

In order to validate our study we created and simulated models of the divider and of the successive approximation ADC and connected them to the conditioning circuit model as it is shown in the Fig. 8. In this paper, we present simulation results which demonstrate the harvester operation with ADC during almost 11 seconds. Here, calibration cycles repeat every 900ms, such a low interval is chosen in order to reduce the modeling time, in reality the calibration phase should be less frequent (tens of seconds) to reduce the power consumed.

In the top part of the Fig. 11, Ustore is plotted together with the measured Ustore voltage. We can see that during the calibration cycle there is a good matching between them because of the good resolution of the ADC. In the bottom part of the Fig. 11, the real Ures is plotted with the measured Ures voltage. The increase in the real Ures value is explained by the accumulation of the energy of the system (i.e., a normal harvester operation). As we see, Ures is measured only once during the calibration cycle. In the normal operation mode between calibration cycles ADC is deactivated by the signal of f1. The measured Ustore max value is reset to 0 and the equivalent Ures is saved until the next calibration cycle.

CONCLUSIONS

In this paper, we presented the architecture design and modeling of the electrostatic vibration energy harvester with a successive approximation ADC. The use of such ADC in energy harvester application is suitable for a low power consumption. The whole system of the harvester including the SAR ADC is simulated with VHDL-AMS/ELDO mixed model using the cadence environment. Simulation results of the harvester with the use of 8-bit SAR ADC demonstrate a good matching between Ustore and the measured from ADC Ustore mes during the calibration cycle. The estimated power consumption of the ADC is around 1.25µW for one step conversion. The comparator is the dominating block in power consumption of ADC with the used sampling frequency and 8-bit resolution, whereas the DAC has much less contribution. The modeling approach consisting in mixing the description levels and the disciplines is very efficient;

the VHDL-AMS/ELDO mixed modeling appears as the best solution for low-level design of electrical interfaces for energy conversion.

Figure 1 :

 1 Figure 1: Conditioning circuit architecture of the vibration energy harvester switch SW is set on by external control blocks and Cstore starts to discharge on Cres through the inductor. When Ustore is reduced to U1, the switch becomes of f and the inductor discharges on Cres through the diode D3. After this, a new charge pump operation cycle starts. From theoretical investigation [5] U1 and U2 parameters are calculated as:

Figure 2 :Figure 3 :

 23 Figure 2: Successive approximation ADC architecture

Figure 4 :

 4 Figure 4: 8-bit successive approximation ADC modes

Figure 6 :

 6 Figure 6: Comparator Resolution

Figure 7 :

 7 Figure 7: Differential DAC of a 8-bit successive approximation ADC with unit capacitance Cu

  i s a b l e a l l c o n t r o l s i g n a l s LOOP wait on c l o c k ; --f i r s t c y c l e i n c h a r g e r e d i s t r i b u t i o n mode i f c l o c k ' e v e n t and c l o c k = '1 ' and s t a r t = '0 ' and ( i=n ) then i :=n-1; --c o n n e c t t h e c a p a c i t o r s --bottom p l a t e s t o Ucm in02bcm <=2.5; in03bcm <=2.5; in04bcm <=2.5; in05bcm <=2.5; in06bcm <=2.5; in07bcm <=2.5; in08bcmx <=2.5; i f ( comp out >1) then word ( i ):= ' 1 ' ;--msb=1 i n 0 1 b r<= 2 . 5 ;--c o n n e c t t h e msb cap t o Uref e l s e word ( i ):= ' 0 ' ;--msb=0 in01bg<= 2 . 5 ;--c o n n e c t t h e msb cap t o gnd end i f ; e l s e --s e c o n d c y c l e i n c h a r g e d i s t r i b u t i o n mode i f c l o c k ' e v e n t and c l o c k = '1 ' and s t a r t = ' 0 ' and ( i=n-1) then --c o n n e c t t h e c a p a c i t o r s bottom p l a t e s t o Ucm i := i -1; in02bcm <=0.0; in03bcm <=2.5; in04bcm <=2.5; in05bcm <=2.5; in06bcm <=2.5; in07bcm <=2.5; in08bcmx <=2.5; i f ( comp out >1) then word ( i ):= ' 1 ' ;--2nd b i t =1 i n 0 2 b r<= 2 . 5 ;--c o n n e c t t h e 2nd cap t o Uref e l s e word ( i ):= ' 0 ' ;--2nd b i t =0 in02bg<= 2 . 5 ;--c o n n e c t t h e 2nd cap t o gnd end i f ; e l s e --t h i s a l g o r i t h m i s r e p e a t e d --t o i=n-7 --l a s t c y c l e i n c h a r g e d i s t r i b u t i o n mode i f c l o c k ' e v e n t and c l o c k = '1 ' and s t a r t ' e v e n t and s t a r t = '1 ' and ( i=n-7) then --c o n n e c t t h e c a p a c i t o r s --bottom p l a t e s t o Ucm i := i -1; in08bcmx <=2.5; i f ( comp out >1) then word ( i ):= ' 1 ' ;--l s b b i t =1 e l s e word ( i ):= ' 0 ' ;--l s b b i t =0 end i f ; --we g e t t h e new o u t p u t b i t s --a t t h e end o f t h e c o n v e r s i o n dout<=word ; i :=n ; --d i s a b l e a l l c o n t r o l s i g n a l s end loop ; end process ; end archi te cture f c t ;

[ 1 ]Figure 8 :

 18 Figure 8: Functional schema of harvester system

Figure 9 :

 9 Figure 9: Voltage divider circuit interfacing the harvester with the ADC

Figure 10 :

 10 Figure 10: Calibration cycle of the harvester

Figure 11 :

 11 Figure 11: Simulation results of harvester operation using the SAR ADC model

ACKNOWLEDGEMENTS

This work is funded by the French National Research Agency (ANR).


Olivier Beaudoux
email: olivier.beaudoux@eseo.fr

Arnaud Blouin
email: arnaud.blouin@inria.fr

Olivier Barais
email: barais@irisa.fr

Jean-Marc Jezequel
email: jezequel@irisa.fr

Specifying and implementing UI Data Bindings with Active Operations

Keywords: ACM Classification D.2.2 Software Engineering: Design Tools and Techniques-Computer-aided software engineering (CASE), User interfaces Algorithms, Design, Languages Data binding, active operation, GUI

Modern GUI toolkits propose the use of declarative data bindings to link the domain data to their presentations. These approaches work fine for defining simple bindings, but require an increasing programming effort as soon as the bindings become more complex. In this paper, we propose the use of active operations for specifying and implementing UI data bindings to tackle this issue. We demonstrate that the proposed approach goes beyond the usual declarative data bindings by combining the simplicity of the declarative approaches with the expressiveness of active operations.

INTRODUCTION

The problem of linking domain data to their presentations has appeared very early in computer science. The Model-View-Controller (MVC) design pattern has been introduced with the SmallTalk-80 language to formalize and implement such a linking [START_REF] Krasner | A description of the model-view-controller user interface paradigm in smalltalk80 system[END_REF]. The main drawback of this pattern is that the view is bound to a specific model: the view has to observe the model and refresh its state on model changes. Consequently, applications must adapt their domain data to the specific models bound to their possible views. The Java Swing API applies such a schema; for example, displaying a collection of elements within a JTable requires adapting the collection by implementing interface TableModel [START_REF] Eckstein | Java Swing[END_REF].

The concept of data binding can be seen as an evolution of MVC that avoids such a drawback. A data binding is a "controller" that binds the model and the view: it observes the model and updates the view whenever the model changes; conversely, it observes the view and updates the model whenever the view changes. The concept of data binding is very close to the controller of the PAC model where the Controller binds the Abstraction and the Presentation [START_REF] Coutaz | PAC, on object oriented model for dialog design[END_REF]. Recent GUI toolkits propose the data binding as the first-class object for linking models and views. However, as this paper will illustrate, they all suffer from two main limitations: 1) they offer a limited expressiveness so that hand-programming is often required when the complexity of the bindings grows; 2) they are platform-dependent implying that a data binding written within a given GUI toolkit must be entirely rewritten to be used within another one.

In this paper, we propose the use of active operations for specifying and implementing UI data bindings. The concept of active operation extends the usual concept of operation by allowing the result of an operation to be re-evaluated afterward. For example, usual operation b := a.select(f ) constructs collection b containing each element of collection a that satisfies predicate f [START_REF] Warmer | The object constraint language: getting your models ready for MDA[END_REF]; the active version of this operation does more: it adds into b (respectively removes from b) any element newly added into a (respectively removed from a) that satisfies f. Active operations formalize and generalize our initial work on active transformations in the context of GUI [START_REF] Beaudoux | Linking data and presentations: from mapping to active transformations[END_REF][START_REF] Beaudoux | XML active transformation (eXAcT): Transforming documents within interactive systems[END_REF]; the mathematical definition of action operations is provided in [START_REF] Beaudoux | Active operations on collections[END_REF].

Our proposal aims at combining the simplicity of the declarative approaches with the expressiveness of active operations, which is achieved through: a unified and platform-independent language for specifying data bindings; the use of simplified class diagrams (Ecore documents) for representing both the models and the views; a formalism for implementing the specification of bindings independently from the final implementation language; a compatibility schema with GUI toolkits.

The remainder of this paper is structured as follows. Section 2 presents, through three concrete examples, our language used to specify data bindings with active operations. Section 3 explains why and how the speci-fication of active operations must be translated before being implemented. Section 4 focuses on the implementation and execution of active operations on GUI platforms. Section 5 introduces works related to data binding. Section 6 complements section 5 by comparing our proposal with the declarative data bindings of three representative Rich Internet Application (RIA) toolkits. Section 7 finally concludes on our work and its perspective.

SPECIFYING ACTIVE OPERATIONS

This section introduces active operations through three complementary examples. These examples have been carefully designed to illustrate the expressiveness of active operations for specifying various UI data bindings. They have also been motivated to illustrate the limitation of usual binding mechanisms (see section 6).

The following specifications of active operations are expressed using our own domain specific language (DSL) that is close to the OCL language [START_REF] Warmer | The object constraint language: getting your models ready for MDA[END_REF]. Expression c.map(f ) applies function f to each element e of collection c, and maintains a link (called a trace) between e and the element returned by f(e). In the example, the root element of document d is bound to the root item of tree t through binding E2I defined as follows:

Example 1 -A Simple XML Editor

1 i . text := "<" + e.name + ">" The text of tree item i displays the name of element e surrounded by angle brackets. Children of item i result from concatenating attributes of element e sorted by their name and mapped to tree items (line 3), with children of element e recursively mapped to tree items (line 4). Finally, binding A2I displays the name and value of attribute a into tree item i : i . text := "@" + a.name + "=" + a.value All the previous bindings are unidirectional. The next example illustrates how active operations can be used to define bidirectional bindings.

Example 2 -A Directory Editor

Figure 2 gives the model of a directory editor. The left part represents a directory d of contacts; the right part represents the model of a list widget l ; three textfields ff, lf, and pf, are used to respectively edit the first-name, last-name and phone number of the contact selected from the list widget l ; finally, a fourth text-field tf is used to filter the content of the list so that a user can quickly find a contact within a large directory.

5

.

map(C2I)

The list of contacts is first sorted (line 2); a simple string concatenation is here used to specify a sort on the last-Name and then on the firstName of the contacts. The resulting list is then filtered through the select operation (lines 3-4): if text-field tf is empty, all the contacts are selected; otherwise, only contacts whose last-name starts with the text-field content are selected. Each resulting contact c is then mapped to a list item i by calling binding C2I (line 5), which is defined as follows: Binding L2PF binds text-field pf used to edit the phone number to the selected item of the list l, as follows:

pf . text := l . selection . contact .phone.toString () l . selection . contact .phone := pf. text . toInteger ()

The phone number of the selected contact is converted into a string displayed into text-field pf (line 1); conversely, the text of text-field pf is converted into an integer that represents the phone number of the selected contact (line 2). Text-field pf must be designed to restrict the editing to integers; this must be achieved at the GUI platform level, but not by the binding itself. Binding L2PF is bidirectional : if the user changes the selection, the text-field is automatically updated; conversely, if the user changes the text-field content, the phone number of the selected contact is automatically updated. Infinite loop on such a bidirectional binding is avoided by only notifying changes on new values: if the new value does not differ from the previous one, no notification is performed by the property setter method.

Only path assignments, along with an optional conversion, can be used in a bidirectional way [START_REF] Beaudoux | Active operations on collections[END_REF]. If no conversion is required between two properties, the double use of operator := defines a bidirectional assignment that can be shortened with the operator =, such as binding L2FF illustrates:

ff . text = l. selection . contact .firstName Contrary to the previous binding, no conversion is required here. Binding L2LF is similar to L2FF for property lastName.

These bindings illustrate the bidirectionality feature of active operations; however, as within example 1, these bindings remain quite simple. The next example uses intensively active operations to achieve a complex binding. The collection (i a , i b ) is computed by mapping courses d.courses through binding C2I x. The collection of free time-slots (0, 2, 3) is computed by subtracting d.courses.timeslot 1 equals to (1, 4) y, from collection ts representing all defined time-slots (0..4) z. The collection of empty grid-items (i Ø , i Ø , i Ø ) is computed by mapping collection of free time-slots with function GridItem.new {. The two collections of grid-items are then concatenated to form the collection of all griditems (i a , i b , i Ø , i Ø , i Ø ) |. Such a collection is however not ordered accordingly to time-slots. Since timeslot numbers represent positions, the "order collection" (1, 4, 0, 2, 3), resulting from the concatenation of a and b time-slots and the free time-slots }, is used to sort the grid-items ~: operation sortedBy sorts collection (i a , i b , i Ø , i Ø , i Ø ) with order (1, 4, 0, 2, 3) that gives the position of each item after sorting. The previous principle is quite complex due to the calendar model that does not divide a day into time-slots. However, this proposed model is a simplification of a calendar model that allows a time-slot to contain multiple courses and a course to span multiple time-slots. This simplified model has been designed to illustrate that active operations allow the definition of bindings between "something missing" (a time-slot without any course) to a UI object (an empty grid-item).

Example 3 -An Academic Calendar

Binding D2R is specified with our DSL as follows, and illustrates the expressiveness of our DSL: Binding C2I finally binds the text of the not-empty grid-item i to the description of its corresponding course c, as follows:

i . text := c. description

TRANSLATING ACTIVE OPERATIONS

The previous section focuses on the specifications of bindings. However, as this section will illustrate, these specifications cannot be executed on a target platform as is: they must be translated into an active implementation. Such a translation uses again our own DSL by introducing new specific operations, thus making the translation process independent from the final implementation language and platform (see section 4). Moreover, some of the new operations motivated by the translation might be useful at the specification level, such as example 3 illustrates through its use of operation sortedBy (see section 2.3).

Paths

Paths extend the dotted notation of OOP so that the dot symbol can be applied more than once on collections [START_REF] Warmer | The object constraint language: getting your models ready for MDA[END_REF]. For example, expression d.contacts.firstName represents a path that returns a flattened collection, as the OCL operation collect does [START_REF] Warmer | The object constraint language: getting your models ready for MDA[END_REF], containing the firstname of all contacts of directory d. The dedicated operation path must be used for implementing path on collections on top of an OOP language; in binding L2FF of example 2, expression:

ff . text = l. selection . contact .firstName must be translated into:

ff . text = l. selection .path(s | s . contact ). path(c | c.firstName)

Observability

Usual loops can be used to implement usual operations on collections. For example, expression b := a.collect(f ) computes collection b by converting each element e of collection a into element f(e) within collection b; operation collect is easy to implement using a loop, as follows:

a.each(e, i | b.add(f(e ), i ) )

The previous code states that each element e at position i within collection a must be converted to the corresponding element f(e) at the same position i within b.

Making an operation active, such as operation collect, requires the observability of collections: an observable collection is a collection from which additions and removals can be observed [START_REF] Akehurst | Model Translation: A UML-based specification technique and active implementation approach[END_REF][START_REF]JFace data binding[END_REF]. We have proposed in [START_REF] Beaudoux | Active operations on collections[END_REF] to extend usual loops with active loops that manage collection observability and allow implementing active operations as usual loops do for implementing the usual operations. For example, the previous usual loop that implements operation collect can be easily translated to the following active loop: Such a translation process from usual loops to active loops works fine for operations collect, map and path. However, it must be augmented for operations select and sortedBy, as explained in the next section.

Selection and sort

The following expression: The same problem arises with operation sortedBy. For example, binding E2I of example 1 sorts attributes of element e by their name: e. attributes .sortedBy(a | a.name)

minors := persons.
If an attribute a is added or removed from e.attributes, the active loop updates correctly the resulting collection. However, any change to a.name is not captured by the active loop. We thus propose to reify the order function f involved in expression c.sortedBy(f ) into an order collection represented as a sequence of integers. In the previous example, the order collection is defined by the following expression: e. attributes .path(a | a.name).ascendingOrder()

If element e defines three attributes named "first", "second" and "last", the previous expression returns order collection {0, 2, 1} that gives the position of names after the sort. By overriding operation sortedBy, the previous example should be translated into:

name).ascendingOrder() )

Order collections are also useful for solving various ordering problems, independently from the translation phase. For example, they have been used in the specification of binding D2R to bind courses and free timeslots with grid-items (see section 2.3).

Tuples

Anonymous functions f involved in active operations, such as b := a.select(f ), may require more than one argument. For example, binding D2L includes a selection based on two arguments tf and c: The reified version of this select operation uses a tuple from which a predicate operation is performed, as follows: By doing so, the predicate collection is updated whenever d.contacts.lastName or tf.text changes. Tuples can thus be used for extending the initial scope of operation select to multiple arguments; a similar extension can be applied to other active operations, such as operation collect2 .

d.

IMPLEMENTING ACTIVE OPERATIONS

The previous section explains the translation of binding specifications to their active implementation, independently from the target GUI platform. This section explains how to make the final implementation compatible with a given GUI platform so that its widgets can be reused. It gives theoretical and experimental results regarding performances of the final implementation.

Implementing Active Operations on a GUI Toolkit

In order to evaluate the use of active operations for UI data binding, we have implemented active operations on top of the Flex GUI platform [START_REF] Kazoun | Programming Flex 2[END_REF]. Flex has been chosen for its own internal binding mechanism, its rich set of widgets, and its ability to pass anonymous functions as function arguments. All the three examples presented in this paper have been implemented with the resulting ActiveFlex project; more details about the Flex implementation can be found within the project. 3 . Figure 5 gives an overview of our ActiveFlex model that extends Flex classes with active operation capabilities. Any class derived from the Flex class Object can mark any of its attribute as bindable: by doing so, the bindable attribute can be bound to Flex widgets displaying simple values, such as a text-field or a check-box. Our class ActiveObject thus defines its content through attribute value that is marked as bindable so that any active object can be bound to such Flex widgets.

The following MXML code 4 illustrates how simple the binding of the TreeItem of example 1 to a Flex mx:Tree widget is: <mx:Tree dataProvider="{tree.root}" ... /> Object tree is an instance of our class Tree. The mx:Tree is bound to the tree.root, which is an instance of our TreeItem class; the mx:Tree then uses internally: the children property to recursively construct the tree content, and the bindable property label to display the content of each tree item. Any Flex widget can be bound to an instance of our classes ActiveArray or ActiveObject similarly.

Such a scheme can be applied to any RIA toolkit that proposes a declarative data binding mechanism, such as with WPF/Silverlight [START_REF] Sells | Programming Windows Presentation Foundation[END_REF] or JavaFX [START_REF] Field | JavaFX language reference (chapter 7 -Data binding)[END_REF]. Toolkits without data binding capabilities require more coding effort. For example, the use of active operations on top of the Swing toolkit requires implementing Java interfaces such as TableModel, TreeModel or Document within active collection and/or object classes.

Theoretical Complexities

Table 1 summarizes the best-case (C min ), average-case (C av ) and worst-case (C max ) complexities of active operations (see [START_REF] Beaudoux | Active operations on collections[END_REF] for more details on computation of these complexities). Columns labeled "I" give complexities for the initial construction of the operation result; columns labeled "+"

C min C av C max Operation I + - I + -I + - collect n 1 n path n 1 n select n 1 n predicate n 1 n not,
(respectively "-") give complexities for updating the result when an addition (respectively a removal) occurs on the source collection. Initial constructions mainly cost a linear time since they globally use elementary operation add in the best-case (i.e. append); subsequent mutations also cost a linear time due the required shifting. These results only vary for sorting that requires two loops, and for difference/intersection that must check the presence with operation contains which costs a linear time.

The previous complexities are asymptotic. However, the translation cost representing the amount of time and memory used by the intermediate operations that appear during the translation (see section 3) should be also taken into account. For example, expression: The previous complexities of individual operations can be used to compute complexities of an overall binding. Let us consider the binding defined by example 1 (the XML editor) for a source XML document with a depth d, a number of child elements per element n e , and a number of attributes per element n a , both common to all elements. For simplification purpose, we consider that n e = n a = n. Document thus counts N e = n d -1 n-1 elements, and N a = n × N e attributes; the tree widgets counts N i = N a + N e items. By considering that N = n The ratio N between these two complexities well illustrates the interest in making active binding operations, rather than recomputing all the resulting tree widget content. The next section illustrates that our experimental results match these theoretical ones.

c. select (e |

Experimental results

Our experimental measurements focus on two objectives: verifying that our theoretical complexities match the measured performance; comparing the cost of active operations with the cost of widget rendering. They have been performed on a PC running Windows XP on top of an Intel Pentium 1.8 GHz + 1 GB RAM and an ATI FireGL 128 MB. Figure 6 gives the performance of initial construction of the tree widget for the XML document defined in the previous section with depth 3 (N = n 3 ). Axis x represents number n, and axis y gives time performance in ms.Construction The five curves represent respectively: the XML document construction (curve "Doc.") that includes the creation of instances of classes Document, Element and Attribute, and the establishment of their relation; the "passive" data binding (curve "Passive") that represents the usual operations that can be used (only) for the initial construction; the tree construction (curve "Tree (naive)") that represents the binding uses to build the target instances of class Tree and TreeItem with active operations; the tree construction that uses a quicksortbased algorithm (curve "Tree (quicksort)") instead of a naive one (previous curve); finally, the tree widget rendering (curve "mx:Tree") performed by the Flex engine to display the graphical content of the widget. Curve "Doc" tends to 0, 25 × N , thus illustrating that the document construction is linear. Curve "Tree (naive)" gives the performance of the bindings in the worst-case since it uses a naive implementation of the sort that costs O(n 2 ); it tends to 0, 052 × N × n, thus matching the expected theoretical result. Curve "Tree (quicksort)" tends to 0, 18 × N × log 2 n; the expected logarithmic dimming effect appears for a significant value of n (here around 14). Curve "Passive" tends to 0, 028 × N × n, which is around half the curve "Tree (naive)": this illustrates that the translation cost is around 1, as expected (one intermediate order collection is here required). Finally, curve "mx:Tree" tends to 0, 6 × N × n 2 , which probably results from the traversing required for computing location y of each treeitem i. This location may be recursively computed by summing heights h of the previous-sibling items of i : y(i) = j h(i.sibling[j]); in turn, computing the height of a node consists of summing the height of its children:

h(i) = j h(i.children[j]
). The overall layout includes N computation of y, so that the complexity tends to N × n 2 .

This experimentation illustrates that complexity of data bindings can often be neglected regarding the complexity of rendering complex graphics, such as a tree. Simpler widgets, such as a list widget, can however require complexity comparable to the one of the associated binding. Experiments performed on example 2 with a large list of contacts confirms this point: because the binding performs a sort, displaying the list can become faster than performing the binding, but for a large number of list items (around 10.000 in our experimentation).

Figure 7 gives the performance of the addition of an attribute; performance of its removal is very close to this curve, and is thus not shown in the figure. In both cases, updating the document (curve "Doc.") takes a constant and negligible time; data binding takes a linear time t(ms) = 0, 015 × n, as expected (curve "Tree"); the Flex tree widget does not have to compute new y locations: this rather consists of applying a vertical offset in the display buffer, which requires a constant time around 150 ms (curve "mx:Tree"). These performances illustrate that the time required to refresh a drawing is often bigger than the time for computing a binding. In the previous example, the update time for the Flex tree and the active operations become equal when n reaches 150/0, 015 = 10.000, which represents a really huge XML document (10 12 nodes for a depth of 3).

RELATED WORKS

Constraint systems have been widely used for defining data bindings in the context of GUI. The Garnet toolbox proposes the use of "formula", expressed in Lisp, to bind an object value to other object values: the for-mula is reevaluated whenever the values within the formula change, like in spreadsheets [START_REF] Myers | Garnet: comprehensive support for graphical, highly interactive user interfaces[END_REF]. The Rendezvous architecture defines the concept of "active value": an active value is a variable used as en entry point to constraint definitions (also expressed in Lisp); when the value changes, the constraint is reevaluated to reflect the change [START_REF] Hill | The Rendezvous constraint maintenance system[END_REF]. Similarly, but within a C++ infrastructure, the Amulet environment allows the definition of constraint through "formula" that bind object values [START_REF] Myers | The Amulet environment: new models for effective user interface software development[END_REF]. However, all these constraint-based systems are limited to the binding of object values: they do not address the binding of collections, and are thus limited to simple widgets such as text-field or combo-box.

The JFace toolkit defines interfaces IObservableValue and IObservableCollection that respectively allow the observation of values and collections [START_REF]JFace data binding[END_REF]. These interfaces are implemented in classes that can be used for representing "bindable" data in both the model and the view. This approach defines the required foundation classes for data binding; however, it is a pure programmatic approach where bindings must be implemented rather than being declared. The ObjectEditor toolkit uses a more subtle approach that consists of extending the JavaBean syntax so that data bindings appear in a more declarative way [START_REF] Dewan | Increasing the automation of a toolkit without reducing its abstraction and user-interface flexibility[END_REF]. Moreover, this toolkit extends the scope of data binding to action binding that allows user actions to be bound to "do", "undo" and "redo" methods. However, ObjectEditor offers a low expressiveness regarding data binding capabilities.

RIA toolkits, such as WPF [START_REF] Sells | Programming Windows Presentation Foundation[END_REF], Flex [START_REF] Kazoun | Programming Flex 2[END_REF], and JavaFX [START_REF] Field | JavaFX language reference (chapter 7 -Data binding)[END_REF], have adopted a declarative approach to data binding. The aim of these approaches is to simplify the process of writing bindings: rather than being implemented, bindings are declared. These approaches work fine for simple bindings where the view does not differ much from the model; they however lose their simplicity as soon as the complexity of the model is increased, which often results in requiring some low level programming that contradicts the initial aim of the declarative approach. Section 6 focuses on proving these limitations.

Using rule-based incremental transformation languages solves the previous limitations of declarative data bindings. The incremental XSLT processor incXSLT allows the incremental execution of XSLT transformations [START_REF] Villard | An incremental XSLT transformation processor for XML document manipulation[END_REF]. However, XSLT concerns source XML documents and target text documents, which makes it difficult to use on various GUI platforms. Moreover, XSLT is a complex language that does not match well the required simplicity of data binding. Using a mapping language, such as Malan [START_REF] Blouin | Malan: A mapping language for the data manipulation[END_REF], combines the benefits of the simplicity of data bindings and the expressiveness of transformation languages. However, this higher level approach postpones the problem of executing the mappings: for example, active operations can be generated from a mapping so that the mapping can be executed on a target platform.

COMPARISON WITH BINDINGS OF RIA TOOLKITS

From our knowledge, recent RIA toolkits offer the best data binding mechanisms. This section compares our approach with three representative RIA toolkits: Flex [START_REF] Kazoun | Programming Flex 2[END_REF], WPF [START_REF] Sells | Programming Windows Presentation Foundation[END_REF], and JavaFX [START_REF] Field | JavaFX language reference (chapter 7 -Data binding)[END_REF]. It illustrates why the three examples presented in this paper cannot be fully implemented by using their data binding capabilities. Category "Math" includes the usual mathematical set operations, and the definition of tuples; tuples are useful in operations such as select(f ) and collect(f ) with more than one parameter in f. Category "View" (in the database sense) includes operations select and sort; it also defines the ability for an active collection or object to be treated more than once by an active operation (such as select and sort), thus allowing multiple views on a common model. Category "Transformation" concerns operations collect, path and map, that allow a progressive transformation from the source to the target. Finally, category "Bidir." defines the bidirectional assignment used to perform two-way bindings on active objects; this functionality is supplemented by a reversible conversion.

Active Operation Capabilities

All these capabilities have been illustrated in the 3 examples of section 2. The next section discusses if and how these capabilities are present within the data binding mechanisms of the three RIA toolkits Flex, WPF and JavaFX. WPF offers richer binding capabilities than Flex [START_REF] Sells | Programming Windows Presentation Foundation[END_REF].

Comparison with RIA Toolkits

Operations select and sort return new bindable collections, and thus allow the definition of multiple views; bidirectional conversion is also possible. However, math operations and transform operations collect and path remain undefined for collections.

JavaFX has adopted a radically different strategy for defining bindings: rather that proposing a bunch of binding artifacts, such as with Flex or WPF, JavaFX introduces new language keywords dedicated to the definition of bindings [START_REF] Field | JavaFX language reference (chapter 7 -Data binding)[END_REF]. Consequently, JavaFX bindings are clearer than that of Flex or WPF since they are based on very few constructs, while Flex and WPF bindings use many different artifacts that often require low level ad hoc programming. However, as table 4 illustrates, important features are unavailable in JavaFX thus making it not as expressive as expected.

Implementing the Examples using RIA Toolkits

Regarding example 1, Flex data binding cannot be used to bind XML documents to the tree widget since this requires union operations. The example could be built by coding a specific data provider that implements Flex interface ITreeDataDescriptor. This practice is similar to the implementation of Swing models, and thus does not respect the initial philosophy of binding. Filtering contacts in example 2 is impossible with Flex binding: this requires the programming of an ad hoc code that recomputes the filtering whenever the user changes the filtering text. Moreover, sorting and filtering the contacts must be specified by altering the code of the model: the design of the GUI thus impacts the source model, which contradicts the fact that binding clearly separates the model and its GUIs. Finally, example 3 cannot be implemented by using Flex binding. This is due to the free-time slots objects that are not present in the source model, and thus cannot be bound to griditems.

As with Flex, example 1 cannot be implemented using WPF binding due to the lack of operation union.

Example 2 is easier to implement than with Flex due to WPF view capabilities; however, the active filtering of contacts again requires the development of ad hoc code. But most of all, implementing example 2 with WPF requires a bunch of data binding artifacts: "bidirectional converters" must be programmed by implementing interface IValueConverter ; "data templates" must be defined with the XAML document5 for implementing functions that define the text of the tree items; and "observable collection" must specify the filtering and sorting of contacts in a programmatic way. The developer thus needs to juggle with multiple artifacts, and with both programmatic and declarative paradigms. Example 3 cannot reap benefit from WPF binding and must be implemented from scratch.

Due to the lack of view capabilities, examples 1 and 2 cannot be implemented using JavaFX binding. As with Flex and WPF binding, example 3 is not feasible with JavaFX.

Discussion

Data binding of RIA toolkits are simple to use for simple bindings. Their binding mechanisms remain sufficient as long as the source models do not differ much from the target models. Moreover, these mechanisms allow binding to existing relational databases and/or XML documents directly, thus making them attractive in an enterprise context. In counter part, the offered binding capabilities become insufficient to address various and/or complex problems. These toolkits often require multiple artifact juggling that alter the initial simplicity of the declarative approach. Moreover, each RIA toolkit proposes its own data binding mechanism. Consequently, a binding written in WPF cannot always be translated to a Flex or JavaFX binding: they are all platform dependent and do not share a common model.

The use of active operations for specifying and implementing data binding removes such limitations. A single DSL is used for specifying the bindings, and translating them before being implemented; it is thus platform-independent. The resulting implementation performances are good for the initial construction of operation results, and very good for updating these results. In counter part, active operations have to be implemented through a dedicated compiler; however, RIA toolkits also require some hidden code generation (for example, to implement paths between two bound properties). Active operations currently do not provide mechanisms for binding UI directly with databases or XML documents. However, such an issue is not specific to the domain of active operations: it concerns the serialization and deserialization of models on different data platforms.

CONCLUSION

This paper presents how to reap benefits from active operation expressiveness and easiness for specifying and implementing UI data bindings. Active operations offer the ability to reevaluate the result of the operations in real-time while the user interacts with the system. The proposed approach overcomes the limitations of data binding mechanisms provided by modern UI toolkits. These limitations are: GUI bindings are platformdependent and lack at defining complex bindings. It is based on a single DSL, mainly inspired by OCL, that allows both the specification and the platformindependent implementation of data bindings. Active operations have been implemented on top of the Flex RIA toolkit; the resulting ActiveFlex API offers good performance for the initial construction of active operation results, and very good ones regarding their updates.

The next step of our work is to implement a compiler that will generate active implementations from any active operation specification. Such a compiler would generate the implementations on various GUI platforms. Since our approach offers a great expressiveness, we will use and evaluate it in the context of "Information Visualization" in order to confront its performance to large models.

Figure 1

 1 Figure 1 gives the model of a simple XML editor. The left part represents a simplified XML document model; the right part represents the model of a tree widget; the middle part represents bindings between these two models.

Figure 1 .

 1 Figure 1. A Simple XML Editor

2 i

 2 . children := 3 e. attributes .sortedBy(a | a.name).map(A2I) + 4 e. children .map(E2I)

Figure 2 . 3 .

 23 Figure 2. A Directory Editor

Figure 3 .

 3 Figure 3. An academic calendar

Figure 3

 3 Figure 3 gives the model of an academic calendar. The left part represents a simplified model of a weekly academic calendar; the right part represents the model of an HTML-like table widget; the middle part represents bindings between these two models. Binding W2G binds week w, instance of class Week, to grid widget g, instance of class Grid. It maps days of week w to rows of grid g by calling binding D2R: g.rows := w.days.map(D2R)

Figure 4 .

 4 Figure 4. Principle of binding D2R

  ts := seq(0 to 4) courseTS := d.courses . timeslot freeTS := ts -courseTS items := d. courses .map(C2I) + freeTS.map(n | GridItem.new) r . items := items.sortedBy(courseTS + freeTS)

1

  a.eachAdded(e, i | b.add(f(e ), i ) ) 2 a.eachRemoved(e, i | b.remove(i) ) This code states that: each element e newly added into a results in adding the converted element f(e) into b (line 1); each element e newly removed from position i within collection a results in removing the corresponding element from b (line 2).

  e. attributes .sortedBy( e. attributes .path(a | a.

  d. contacts . select (c | tf . text .isEmpty() or c.lastName.startsWith( tf . text ) )

Figure 5 .

 5 Figure 5. ActiveFlex model

d 1 ,

 1 we have: N e n d-1 = N/n and N a N i n d = N . Number N = n d thus represents the overall and approximate number of both document nodes and tree items, while n represents the cardinality of each relation. The worst-case complexity of the associated binding is given by the complexity of the sort that binding D2R performs, and thus costs O(n 2 ). The initial construction of the tree widget requires N e sort operations, and thus costs C init = N e × O(n 2 ), i.e. C init = O(N × n). Mutations cost a linear time for all operations within the binding, i.e. C update = O(n).

Figure 6 .

 6 Figure 6. Construction performance

Figure 7 .

 7 Figure 7. Addition performance

  If persons contains three people with ages 16, 42 and 12, this expression returns predicate collection true, f alse, true. By overriding operation select, the previous example should be translated into:

	minors := persons. select (
	persons .path(a | a.age). predicate (a | a < 18)
	)
	select (p | p.age < 18)
	computes collection minors that contains persons p un-
	der 18. The active loop of such a select operation can be
	easily translated from a usual loop. This loop works fine
	whenever a person is added or removed from collection
	persons; however, it fails whenever the age of a person
	goes above 18: this last change is not captured by the
	active loop. We thus propose to reify predicate func-

tion f involved in expression c.select(f ) into a predicate collection represented as a sequence of booleans. The predicate collection related to the previous example is defined by the following expression: persons .path(a | a.age). predicate (a | a < 18)

Table 1 .

 1 Complexities of active operations

	and, or n	1		n
	sortedBy	n	1		n
	asc.Order	n	1	n.log 2 n	n	n 2	n
	and	n	1		n
	union	n	1		n
	difference	n	1	n 2	n	n 2	n
	intersection n	1	n 2	n	n 2	n

Table 2 .

 2 Translation cost

	f1(e.p1) and f2(e.p2))
	must be translated into expression:
	c. select (c.path(e|e.p1). predicate (f1) and
	c.path(e|e.p2). predicate (f2 ))
	This last expression includes 2 paths (n pa = 2), 2 predi-
	cates (n Operation	Translation cost
	union, diff., inter. 0
	collect	0
	path	1
	select	n

pr = 2), plus 1 boolean expression (n pr -1), and thus costs 5 intermediate active collections and operations. A similar principle can be applied to operation sortedBy that can be based on multiple criteria (n cr ). Table

2

synthesizes such a cost. pa + 2 × n pr -1 sortedBy n pa + 2 × n cr -1

Table 3

 3

		summarizes the capabilities of active operations
	presented throughout this paper. The capabilities be-
	long either to active collections, active objects, or both.
	Bidir.	path map bidir. assignment + conversion	√ √ n/a n/a	√ √ √ √

Table 3 .

 3 Active operation capabilities

Table 4

 4 summarizes the data binding capabilities of the three RIA toolkits Flex, WPF and JavaFX. As mentioned in section 4.1, instances of the Flex class ArrayCollection can be bound to collection widgets, and bindable properties defined within instances of class Object can be bound to simple widgets[START_REF] Kazoun | Programming Flex 2[END_REF]. These two capabilities are equivalent to operation map on collections

	Flex	WPF	JavaFX
	Coll. Obj. Coll. Obj. Coll. Obj.
	Math op. select sort n/a assign. ( √ ) ( √ ) n/a √ + conv. n/a	√ n/a n/a	√ √	n/a n/a	√

Table 4 .

 4 binding capabilities of RIA toolkits and on objects. Bidirectional assignment is possible through property binding, but without conversion. A path can be specified when binding two properties; however, paths cannot be defined on collections. It is also possible to define a "transformation function" within a property binding, which is analogous to operation collect for a single object. All the other capabilities are not available with Flex. Operations select and sort exist on class ArrayCollection, but they do not return new collections: they rather modify the source model directly; this does not separate well the model from the GUI.

Moreover, these operations cannot use "active" parameters (for example, through tuples).

Expression d.courses.timeslot is a path, which is a specific operation detailed in section 3.1.

Such an extension is however out of the scope of this paper.

ActiveFlex is available under GPL license at http: // gri. eseo. fr/ software/ activeflex. html .

MXML is the Flex XML dialect used to specify user interfaces.

XAML is the XML dialect used by WPF to specified user interfaces.