Vladimir A Goy

Uri Vool

Maxim N Chernodub

Preturbulence in momentum-relaxing Navier-Stokes hydrodynamics

In a hydrodynamic regime of electronic fluids, the electron scattering on impurities and phonons inhibits the development of oscillating preturbulent phenomena (such as the Kármán vortex shedding) and enforces a laminar flow. Working in a local generalization of the Navier-Stokes hydrodynamics of incompressible two-dimensional fluids, we show that the critical relaxation time separating these two regimes is described by a surprisingly simple fractional power function of the Reynolds number. The critical exponent, α 4/3, sets particular experimental conditions for the observation of preturbulent effects in electronic fluids.

Introduction. In certain solid-state systems, electronic transport exhibits collective hydrodynamic behavior, which appears to be in sharp contrast with the expected diffusive drift of a Fermi liquid [START_REF] Polini | Viscous electron fluids[END_REF]. Instead, the electron flow resembles a fluid when the momentumconserving electron-electron scatterings events occur much faster than the timescale of the momentumrelaxing interactions of electrons with phonons, impurities, and the boundaries of the system [START_REF] Lucas | Hydrodynamics of electrons in graphene[END_REF][START_REF] Narozhny | Hydrodynamic approach to twodimensional electron systems[END_REF].

The hydrodynamic behavior of electrons reveals itself via various transport properties in conductors of finite geometries. For example, the Gurzhi effect, which emerges in clean conducting channels, discriminates between ballistic transport restrained by the scattering of electrons with the boundaries of the channel and laminar flow of electronic fluid, dominated by the momentum-conserving electron-electron scattering events [START_REF] Gurzhi | Minimum of resistance in impurity-free conductors[END_REF]. The robust signatures of the electron hydrodynamic flow have been found in various compounds via its imprints on the thermal and electric transport [START_REF] Jong | Hydrodynamic electron flow in high-mobility wires[END_REF][START_REF] Moll | Evidence for hydrodynamic electron flow in PdCoO2[END_REF][START_REF] Gooth | Thermal and electrical signatures of a hydrodynamic electron fluid in tungsten diphosphide[END_REF][START_REF] Vool | Imaging phonon-mediated hydrodynamic flow in WTe2[END_REF].

The exceptional mobility of electrons in ultraclean graphene offers another exciting possibility to investigate their hydrodynamics [START_REF] Müller | Graphene: A nearly perfect fluid[END_REF]. Due to the viscosity of the electronic flow [START_REF] Govorov | Hydrodynamic effects in interacting Fermi electron jets[END_REF][START_REF] Torre | Nonlocal transport and the hydrodynamic shear viscosity in graphene[END_REF][START_REF] Pellegrino | Electron hydrodynamics dilemma: whirlpools or no whirlpools[END_REF][START_REF] Bandurin | Fluidity onset in graphene[END_REF] a localized injection of the electronic current can create whirlpools in the electron flow near the contacts. The emerging electronic vortices were predicted to generate a viscous backflow [START_REF] Levitov | Electron viscosity, current vortices and negative nonlocal resistance in graphene[END_REF][START_REF] Lucas | Hydrodynamics of electrons in graphene[END_REF] which leads to experimentally observable negative resistance [START_REF] Bandurin | Negative local resistance caused by viscous electron backflow in graphene[END_REF] as well as a strong violation of the Wiedemann-Franz law [START_REF] Crossno | Observation of the Dirac fluid and the breakdown of the Wiedemann-Franz law in graphene[END_REF]. The viscosity of electronic flow reveals itself in hydrodynamic conductance in narrow constrictions [START_REF] Kumar | Superballistic flow of viscous electron fluid through graphene constrictions[END_REF], which allows for the visual discrimination [19] of the high-temperature diffusive Ohmic current from the low-temperature laminar Poiseuille flow via spatial imagining of the electronic current profiles [START_REF] Sulpizio | Visualizing poiseuille flow of hydrodynamic electrons[END_REF][START_REF] Ku | Imaging viscous flow of the Dirac fluid in graphene[END_REF][START_REF] Jenkins | Imaging the breakdown of Ohmic transport in graphene[END_REF].

The experimental efforts are mostly concentrated in the laminar hydrodynamical regime characterized by low values (Re 1) of the Reynolds number:

Re = U L ν , (1)
set by the characteristic linear dimension L of the hydrodynamic problem, the flow velocity U , and its kinematic (shear) viscosity ν. At higher Reynolds numbers, typically Re 10 . . . 10 3 , electronic transport may exhibit "preturbulent" phenomena [START_REF] Müller | Graphene: A nearly perfect fluid[END_REF], which may experimentally be observed via fluctuations of the electronic current past constrictions and localized impurities in the flow channel [START_REF] Mendoza | Preturbulent regimes in graphene flow[END_REF][START_REF] Gabbana | Prospects for the detection of electronic preturbulence in graphene[END_REF]. In ordinary fluid dynamics, the preturbulent regime is manifested via a periodic detachment of hydrodynamic vortices, which form the so-called Kármán vortex street [START_REF] Karman | Aerodynamics, Dover Books on Aeronautical Engineering[END_REF][START_REF] Falkovich | Fluid Mechanics[END_REF]. In condensed matter context, the formation of the Kármán vortices has been theoretically predicted [START_REF] Sasaki | Bénard-von Kármán vortex street in a Bose-Einstein condensate[END_REF] and experimentally observed [START_REF] Kwon | Observation of von Kármán vortex street in an atomic superfluid gas[END_REF] in the Bose-Einstein condensates of cold atoms.

Contrary to the flow of ordinary fluids, which experience momentum-relaxing interactions only with the channel boundaries and macroscopic obstacles in the flow, the electronic fluids can also lose their momentum at a microscopic level via inelastic scattering of electrons on thermal phonons and impurities of a crystal lattice. These momentum-relaxing events can substantially inhibit the development of the preturbulence regime.

The aim of our paper is to investigate the preturbulent regime in two-dimensional incompressible fluids in the presence of a uniform background of momentum-relaxing events. We consider Navier-Stokes (NS) fluids extended with a simple momentum-relaxing term and study its effect in the realm of electronic flows in graphene. Due to the minimal and model-independent nature of the extension, this simple model can serve as a universal benchmark case of NS fluids with dissipation to be compared with more elaborate models [START_REF] Mendoza | Preturbulent regimes in graphene flow[END_REF][START_REF] Gabbana | Prospects for the detection of electronic preturbulence in graphene[END_REF].

Navier-Stokes hydrodynamics with relaxation.

A one-component electronic fluid is characterized by the electronic density n of the charge carriers with the mass m, the particle current density j = nu and the local velocity u = u(r). We consider a fluid propagating slower than plasmonic velocities which possesses incompressible flow, ∇ • u = 0 [START_REF] Bandurin | Fluidity onset in graphene[END_REF][START_REF] Levitov | Electron viscosity, current vortices and negative nonlocal resistance in graphene[END_REF]. Its hydrodynamic regime is described by the extended Navier-Stokes equation:

∂ ∂t + u • ∇ u -ν∆u = - 1 mn ∇P - e m E - 1 τ mr u , (2)
which incorporates forces experienced by an element of the fluid including (i) internal shear stress due to velocity gradients with the magnitude set by the kinematic shear viscosity ν, (ii) the pressure-gradient ∇P , (iii) the background electrostatic field E, and (iv) friction due to electron scattering on phonons and crystal defects. The parameterization of the friction term by the single quantity, the scattering time τ mr , turns out to be remarkably successful in explaining experimental results in the linear-response regime [START_REF] Bandurin | Fluidity onset in graphene[END_REF][START_REF] Bandurin | Negative local resistance caused by viscous electron backflow in graphene[END_REF][START_REF] Kumar | Superballistic flow of viscous electron fluid through graphene constrictions[END_REF][START_REF] Braem | Scanning gate microscopy in a viscous electron fluid[END_REF].

A steady laminar flow can be described by the simplified time-independent NS equation ( 2), with the material derivative and pressure-gradient terms neglected [START_REF] Bandurin | Negative local resistance caused by viscous electron backflow in graphene[END_REF]:

σ 0 E(r) -eL 2
Gu ∆j(r) + ej(r) = 0. The spatial hydrodynamic length scale is set by the (diffusive) Gurzhi length

L Gu = √ ντ mr . (3)
which, for example, determines the spatial size of the electronic whirlpools in graphene [START_REF] Levitov | Electron viscosity, current vortices and negative nonlocal resistance in graphene[END_REF]. At vanishing viscosity, ν → 0, or at high momentum-relaxing collision rate, τ mr → 0, the hydrodynamic length vanishes, L Gu → 0, and the NS equation reduces to the usual Ohmic drift of electric current, J ≡ -ej = σ 0 E, set by the Drude-like conductivity σ 0 = n 0 e 2 τ mr /m. Scales. The vortex shedding occurs in the non-linear regime of the NS equation (2) which can be conveniently rewritten in the following dimensionless form:

Re ∂ ∂t 0 + u 0 • ∇ 0 u 0 -∆ 0 u 0 = -Rl u 0 + f 0 , (4)
where dimensionless quantities carry the subscript "0":

x = Lx 0 , t = T L t 0 , u = U u 0 , including the dimen- sionless force f 0 = -T L (∇ 0 P )/(mnν) -eLT L E/(mν).
The hydrodynamics of fluid ( 4) is characterized by two dimensionful time scales: the kinematic time T L = L/U , which sets, for example, the scale for the shedding frequency of the Kármán vortices [see Eq. ( 11)], and the kinematic relaxation time scale τ L = L 2 /ν, which determines their attenuation. In Eq. ( 4), we also introduced the dimensionless momentum-relaxation number,

Rl = τ L τ mr = L 2 ντ mr = L 2 L 2 Gu . (5)
given by the ratio of kinematic, τ L , and actual, τ mr , momentum-relaxation times. This parameter separates regimes of fast (τ L τ mr or Rl 1) and slow (τ L τ L or Rl 1) momentum relaxation. Thus, the hydrodynamics can be fully described by only two dimensionless numbers: The Reynolds number Re (1) and the momentum-relaxation number Rl [START_REF] Jong | Hydrodynamic electron flow in high-mobility wires[END_REF].

The critical line of preturbulence. We extensively simulated the NS fluid (4) to elucidate the effects of the momentum relaxation term on the onset of preturbulence. We consider a circular impurity of the diameter L placed in the center of a wide straight channel of the large width W = 10L and use no-slip boundary conditions with vanishing velocity at the boundaries.

In the absence of momentum relaxation, τ mr → ∞, the flow becomes unstable at high Reynolds numbers (1), Re > Re c , where the critical value Re c depends on the geometry of the hydrodynamic system. For a disk-shaped two-dimensional obstacle in a channel of infinite width, the Kármán vortices start to form if the Reynolds number exceeds the critical value Re (∞) c 47 [START_REF] Jackson | A finite-element study of the onset of vortex shedding in flow past variously shaped bodies[END_REF]. In our geometry with a finite-size channel, the critical Reynolds number in the relaxation-free (τ mr = ∞) regime is:

Re c = 52.4(5) , (at τ mr → ∞) . (6)
We found numerically that a finite momentum relaxation time τ mr drastically affects the value of the critical Reynolds number by inhibiting the formation of the Kármán vortices in agreement with Ref. [START_REF] Gabbana | Prospects for the detection of electronic preturbulence in graphene[END_REF]. The phase diagram of the preturbulence in the (Re, Rl) plane is shown in Fig. 1 (the amplitude of the flow velocity is explored in more detail in Supplementary Figure S1).

The phase diagram possesses a laminar phase (at τ mr < τ mr,c ) and the pre-turbulent Kármán phase (at τ mr > τ mr,c ). We established that the critical line that separates these phases is described by the fascinatingly simple fractional power law:

Rl Rl 0 = Re Re c α -1, Re Re c , (7)
where the best-fit parameters are as follows:

Rl 0 = 3.63(7) , α = 1.348(2) 4/3 , (8)
and the critical Reynolds number is given in Eq. ( 6). The excellence of the fit of the numerical data by the phenomenological scaling [START_REF] Gooth | Thermal and electrical signatures of a hydrodynamic electron fluid in tungsten diphosphide[END_REF] is demonstrated in Fig. S2.

The relative amplitude of the velocity oscillations, δU/U , created by the vortices produced past the impurity, takes its weakest values near the critical line [START_REF] Gooth | Thermal and electrical signatures of a hydrodynamic electron fluid in tungsten diphosphide[END_REF]. The amplitude gets substantially enhanced as either the Reynolds number Re or the relaxation time τ mr increases.

In a nondissipative limit, when the relaxation time is long, τ mr τ L (Rl 1), the vortices start to form closer to the lowest critical Reynolds number [START_REF] Moll | Evidence for hydrodynamic electron flow in PdCoO2[END_REF]. At higher Reynolds values, the preturbulent vortex regime sets in at a shorter momentum-relaxation time (for example, according to Fig. 1, the critical relaxation time is τ mr,c τ L /60 or Rl c 60 at Re = 400).

Equations ( 1), ( 5) and [START_REF] Gooth | Thermal and electrical signatures of a hydrodynamic electron fluid in tungsten diphosphide[END_REF] imply that the Kármán vortex phase is realized at the initial flow velocities higher than the critical value u > u c : In the absence of momentum relaxation, τ mr → ∞, the critical line ( 9) is reduced to u c (τ mr ) = Re c ν L which defines the critical point (6) Re = Re c , as expected. In the opposite, fast-relaxation limit, τ mr τ L (at Rl 1), one gets the following asymptotic scaling regime:

u c (τ mr ) = Re c ν L 1 Rl 0 L 2 ντ mr + 1 1/α . ( 9
)
u c (τ mr ) = u 0 ν α-1 α L 2-α α τ -1 α mr for τ mr L 2 /ν, (10)
with the dimensionless u 0 = Re c Rl -1/α 0 = 20.1(2). Shedding frequency and momentum relaxation. The vortex production is characterized by a periodic pattern of the unsteady flow of the vortex shedding. In ordinary fluids, the main vortex shedding frequency,

f = St U L ≡ St T L , (11)
is expressed via the dimensionless Strouhal number "St" [START_REF] Falkovich | Fluid Mechanics[END_REF]. The Strouhal number, which can be computed numerically, depends on the geometry of the obstacle. The typical frequency of the vortex shedding ( 11) is set by the kinematic timescale T L which depends on the velocity of the fluid and the size of the obstacle. For a disk-shaped impurity in the absence of the momentum relaxation, τ mr = ∞, the Strouhal number takes values around St 0.2 in a wide range of values of the Reynolds number [START_REF] Chen | Flow-Induced Vibration of Circular Cylindrical Structures[END_REF]. In a momentum-nonconserving fluid, the finite relaxation time scale τ mr implicitly affects the vortex shedding frequency [START_REF] Torre | Nonlocal transport and the hydrodynamic shear viscosity in graphene[END_REF]. Contrary to the soft equation of state [START_REF] Gabbana | Prospects for the detection of electronic preturbulence in graphene[END_REF], the fluid oscillations in our model ( 4) feature a single production frequency [START_REF] Torre | Nonlocal transport and the hydrodynamic shear viscosity in graphene[END_REF].

Figure 2 2), appears to be qualitatively similar to the ordinary laminar phase below the critical Reynolds number (Re < Re c at τ mr = ∞, point B). The only difference between these phases appears, expectedly, in a faster dissolution of the long-distance laminar tail at τ mr = 0 (well pronounced at point F at a smaller τ mr ).

In the preturbulent phase, the momentum relaxation produces a visible qualitative effect on the structure of the vortex shedding. For example, at Re = 100, the vortices become individually non-distinguishable as they form a single oscillating trail which we dub the "Kármán tadpole", which is well-visible in point C. As the relaxation time τ mr increases, the tadpole breaks into individual vortices (point D), which become more pronounced as τ mr reaches the non-dissipative limit (point E). Thus, at Re > Re c , an increasing relaxation time τ mr turns a laminar flow (B) into a Kármán tadpole (C), which then gets gradually transformed into the usual Kármán vortex street (D). The effect of the momentum relaxation on the vortex attenuation is also seen in the series of points F -H and I-K at higher Reynolds numbers.

Large holes. A non-zero momentum relaxation also produces an attenuating effect for large holes, which may have important consequences relevant to the experimental observation of preturbulence. In Fig. 3, we show the velocity flow around a large disk-shaped impurity for several momentum-relaxation times τ mr . An impurity of diameter L in a channel of slightly larger width W = 4/3L separates the fluid flow into two narrow constrictions. The constrictions inject the fluid with an enhanced velocity past the obstacle close to the walls of the channel, leading to the formation of the Kármán vortex street.

At a distance r (5 -6)L from the obstacle, the flow becomes laminar. A decreasing relaxation time inhibits the preturbulence effect, leading to a pure lami- nar flow of two joining sub-flows above the critical value Rl 15. Our results, illustrated in Fig. 3, imply that the most favorable point for the observation of vortices is r (2 -3)L past the impurity. The relevant frequencies/amplitudes are of the same order as for small holes with important geometry-dependent corrections that are explored in more detail in Supplementary Fig. S4.

Realistic experimental parameters and measurement techniques. With this quantitative understanding of the threshold for Kármán vortices, let us now examine if realistic parameters can be chosen that cross this threshold in an experimental system, focusing on high quality low carrier-density conductors such as graphene sheets and GaAs quantum wells. Initially, a large flow velocity U is required, and velocities of U ≈ (1 -5) × 10 5 m/s have been previously achieved in GaAs [START_REF] Smith | Electron velocity in Si and GaAs at very high electric fields[END_REF][START_REF] Mokerov | Drift velocity of electrons in quantum wells in high electric fields[END_REF] and graphene [START_REF] Meric | Current saturation in zero-bandgap, top-gated graphene field-effect transistors[END_REF][START_REF] Dorgan | Mobility and sat-uration velocity in graphene on SiO2[END_REF][START_REF] Andersen | Electron-phonon instability in graphene revealed by global and local noise probes[END_REF]. The Reynolds number can be increased by constrictions of larger diameter L, but this also increases the relaxation timescale τ L , thus placing a larger constraint on the relaxation time τ mr . This trade-off is explored in detail in Supplementary Figure S3, which shows the required velocity U and viscosity ν to cross the vortex-shedding threshold for various constriction diameters L and momentum relaxation times τ mr . As τ mr is currently experimentally limited to 1-10 ps [START_REF] Jong | Hydrodynamic electron flow in high-mobility wires[END_REF][START_REF] Bandurin | Negative local resistance caused by viscous electron backflow in graphene[END_REF], a diameter length scale of L ≈ 1 µm seems optimal. This experimentally favorable condition is achieved in the asymptotic scaling regime [START_REF] Govorov | Hydrodynamic effects in interacting Fermi electron jets[END_REF] which gives u c ∝ ν 1/4 L 1/2 τ -4/3 mr due to the relatively large [START_REF] Vool | Imaging phonon-mediated hydrodynamic flow in WTe2[END_REF] scaling exponent α > 1. The observation of preturbulence requires then viscosity ν ≈ 10 -4 m 2 /s. Such a value could be possible [START_REF] Bandurin | Negative local resistance caused by viscous electron backflow in graphene[END_REF], but is currently the most significant deviation of needed parameters from existing measured values, consistent with a previous analysis of preturbulence [START_REF] Gabbana | Prospects for the detection of electronic preturbulence in graphene[END_REF]. Improvements in relaxation time can allow for larger constriction sizes, thus reducing the viscosity constraint.

As the effect of Kármán vortices is local to the area past the impurity, the strong effects will be difficult to measure in regular transport measurements but will require local probes such as electric potential [START_REF] Sulpizio | Visualizing poiseuille flow of hydrodynamic electrons[END_REF], scanning SQUID magnetometry [START_REF] Aharon-Steinberg | Direct observation of vortices in an electron fluid[END_REF], or magnetometry with nitrogen-vacancy (NV) centers [START_REF] Vool | Imaging phonon-mediated hydrodynamic flow in WTe2[END_REF][START_REF] Ku | Imaging viscous flow of the Dirac fluid in graphene[END_REF][START_REF] Jenkins | Imaging the breakdown of Ohmic transport in graphene[END_REF]. The latter is particularly advantageous due to the high sensitivity of the NV to microwave radiation at frequencies corresponding to its spin transitions for a given applied magnetic field. Thus, in addition to the measurement of the DC current shape, the oscillations themselves can be locally observed, with the ability to tune their frequency in-situ by varying the applied current and thus the velocity U . The oscillation frequency [START_REF] Torre | Nonlocal transport and the hydrodynamic shear viscosity in graphene[END_REF] of the vortices for this typical geometry is f ≈ 10 GHz, which is conveniently obtainable for NV centers with the applied field. The observation of a local microwave signal (when only a DC signal is applied) that is tunable with the applied current will be a smoking-gun signature of preturbulent electron hydrodynamics.

Conclusions. Our paper explored the turbulentdissipative regime in two-dimensional incompressible electronic fluids by taking the most straightforward local extension of the NS equation with the local momentumrelaxation term (4) arising from electron scattering on impurities and phonons. We suggested characterizing the relaxation rate in terms of the new momentum relaxation number Rl [START_REF] Jong | Hydrodynamic electron flow in high-mobility wires[END_REF]. We found the critical relaxation number Rl that discriminates the laminar flow from the pre-turbulent regime, is described by a surprisingly simple fractional power law [START_REF] Gooth | Thermal and electrical signatures of a hydrodynamic electron fluid in tungsten diphosphide[END_REF] of the Reynolds number Re with the exponent α 4/3 which intriguingly matches the Yaglom turbulence exponent for dissipation rates of conserved quantities [START_REF] Yaglom | On the local structure of a temperature field in a turbulent flow[END_REF][START_REF] Monin | Statistical fluid mechanics[END_REF].

Close to the critical transition line, the street of shredded Kármán vortices collapses to a new dynamical structure, a single vibrating Kármán tadpole. In the local relaxation model (4), the oscillations are characterized by a single global frequency that does not depend on the distance to the impurity.

The novel preturbulent-dissipative regime accessible with electron hydrodynamics shows rich behavior that can be effectively modeled by two dimensionless parameters. This simple model will serve as a benchmark for the exploration of this regime and a useful tool to motivate, guide, and interpret future experimental studies. . . , 100 µm as derived from the fractional power law [START_REF] Gooth | Thermal and electrical signatures of a hydrodynamic electron fluid in tungsten diphosphide[END_REF] which is assumed to be valid in the whole range of parameters used. The straight segments mark the validity of the asymptotic fractional-power-low [START_REF] Govorov | Hydrodynamic effects in interacting Fermi electron jets[END_REF] which is realized at short relaxation times τmr and characterized by the scaling uc(τmr) ∝ ν

FIG. 1 .

 1 FIG. 1. Phase diagram of the vortex formation in the plane of the Reynolds number Re, Eq. (1), and the momentumrelaxation number Rl, Eq. (5), past a circular impurity of a diameter L in the channel of the width W = 10L. The critical line, described by the phenomenological fractional power law (7) with parameters (8), separates the laminar flow (the white region above the transition line at low τmr, high Rl) and the preturbulent region with higher τmr (lower Rl), where the flow produces the Kármán vortices. The examples of the laminar flow and the oscillatory Kármán flow are shown in the insets (a) and (b), respectively. The color displays the magnitude of velocity oscillations at the point r = L in the middle of the channel past the obstacle.

  shows the Strouhal number calculated numerically across the whole phase diagram. In the low-Re corner of the diagram, corresponding to slow relaxation with high τ mr , the Strouhal number takes the lowest value around St 0.15. In contrast, in the opposite high-Re and low-τ mr corner, the oscillations of the vortex flow are characterized by a twice higher Strouhal number, St 0.3. Finally, in the rest of the phase diagram, the oscillations are close to the standard value St 0.2. Kármán vortices and Kármán tadpoles. Figure 2 also illustrates qualitative features of the fluid flow in various points A-K of the phase diagram. The momentum-relaxing laminar flow above the critical line (at Re > Re c and τ mr = 0 with τ mr < τ mr,c , point A in Fig.

FIG. 2 .

 2 FIG. 2. The Strouhal number St, which determines the frequency of the vortex oscillations (11), is shown in the (Re, Rl) plane of the phase diagram of Fig. 1 along with the examples of the Kármán vortex streets and Kármán tadpoles at the points A, B, . . . , K (the color marks the absolute value of the velocity flow). The inset shows a low-Re corner of the diagram.

FIG. 3 .

 3 FIG. 3. Absolute value of the flow velocity around a large circular impurity of the diameter L in a channel of the width W = 4/3L for various momentum-relaxation numbers Rl. Re = 100, determined formally via the hole size (1), is fixed for all maps, and we observe preturbulence with the critical value Rlc ≈ 15. The velocity color map follows Fig. 2.

B

  FIG.S2. The best fit of the transition line which separates, in the plane of the Reynolds parameter Re and the relaxation parameter Rl, the regions of the preturbulent and laminar phases in Fig.1and Fig.2. The fit is performed by the fractional power function[START_REF] Gooth | Thermal and electrical signatures of a hydrodynamic electron fluid in tungsten diphosphide[END_REF] with the best-fit parameters given in Eq. (8).

=

  ν γ with the fixed exponent γ ≡ 0.258(1) 1/4. The electronic fluid enters the preturbulence regime at u > uc.

S3D. 8 FIG

 8 FIG. S4. The Strouhal number (11) of flow oscillations at Re = 100 (a) in the dissipationless limit, τmr = ∞, as function of the ratio L/W of the hole L and the width of the channel W ; (b) as a function of the relaxation number Rl for various ratios L/W . (c) and (d): The same as in (a) and (b), but for the magnitude velocity at the point at a distance 3L past the hole (cf. Fig. 3 in the main text). The frequency does depend on the geometry (a) but is largely independent of the relaxation time τmr (b). The oscillations of the flow velocity exhibit substantial dependence on both parameters. The insets show examples of the fluid flow at particular geometries and also the limits at a vanishing diameter of the hole.

Acknowledgments. The work of VAG was supported by Grant No. 0657-2020-0015 of the Ministry of Science and Higher Education of Russia.

Supplementary Information


FRT = identification system

The three kinds of FRT

• Verification or authentication is often referred to as one-to-one matching.

• Identification means that the template of a person's facial image is compared to many other templates stored in a database to find out if his or her image is stored there.

• Automated Facial Recognition (AFR)

• Live Facial Recognition Technology (LFRT)

• Categorisation deals with deducing whether an individual belongs to a specific group based on his or her biometric characteristicsfor example, sex, age, or race.

Needs for a CE label

The RFT in the AI Act

•

  it authorizes real-time facial identification for the prosecution of thirty-two criminal offenses (Framework Decision 2002/584 JHA) • require a previous authorization by "a judicial authority or an independent administrative authority" of the member state (with exceptions) • distinction between "real-time" biometric surveillance and " ex-post" biometric surveillance • Sandbox possibility Thank you for your attention…

WHAT IS FACIAL RECOGNITION? Old (and malfunctioning) FRT Actual Facial Recognition (in progress) §1 FACIAL IMAGES AS A UNIQUE BIOMETRIC IDENTIFIER

	1ST CHAPTER:
	• What is facial
	recognition?
	• What are the potential
	harms for human rights
	of facial recognition?
	• What is the position of
	the European regulation
	on facial recognition?

Privacy issues

• ECHR Olsson v. Sweden. Is FRT part of a pressing social need ? • CJUE Tele2: generalized storage and administrative access to connection data of all users of telecommunications services did not comply with Articles 7 and 8 of the CFREU (generalized surveillance of citizens) • case-by-case perspective:

• the list of offenses justifying the use of technology • restricting the use of these devices in time and space • duration of retention and access to data.

Other fundamental principles

• Proportionality

• restricted to prevention or resolution of the most serious crimes.

• Transparent and clear provision of information • Freedom of expression and freedom of assembly and of association

The need for european legal regulation

No domestic regulation : Italian memorandum (31 December 2021). Why should international regulation be "better" or "more effective" than national regulation?

• globalization of the digital economy • context of international competition §1 The Council of Europe's approach The Council of Europe approach

• Right to transparency (art. 8)

• Right not to be subject to a unilateral decision (art. 9,1a). • Right to obtain knowledge of the reasoning (art. 9,1c).

Teaty on Artificial Intelligence


Rémi Douence

Xavier Lorca

Nicolas Loriant

Lazy Composition of Representations in Java

The separation of concerns has been a core idiom of software engineering for decades. In general, software can be decomposed properly only according to a single concern, other concerns crosscut the prevailing one. This problem is well known as "the tyranny of the dominant decomposition". Similarly, at the programming level, the choice of a representation drives the implementation of the algorithms. This article explores an alternative approach with no dominant representation. Instead, each algorithm is developed in its "natural" representation and a representation is converted into another one only when it is required. To support this approach, we designed a laziness framework for Java, that performs partial conversions and dynamic optimizations while preserving the execution soundness. Performance evaluations over graph theory examples demonstrates this approach provides a practicable alternative to a naive one.

Introduction

The separation of concerns is a basis of software engineering. In general, each concern imposes its own decomposition to the whole software: once a primary concern has been chosen, the others become hard to modularize. This problem is well known as "the tyranny of the dominant decomposition". Similarly, at the programming level, the choice of a representation drives the implementation of algorithms. For instance, consider the case of the Cartesian or polar representations of a point. The first one fits with translations while the second with rotations, but neither efficiently implements the two operations simultaneously.

In this case, one possibility is to maintain several representations at the same time. This promotes reusability of algorithms specialized for a given representation. However, the synchronization of multiple representations has drawbacks:

(1) a significant amount of computation can be required to maintain all representations up to date; (2) the space complexity increases with the number of co-existing representations; (3) the benefit in terms of expressiveness are annihilated by the complexity of the data structure manager. Another possibility is to maintain only one representation at a time and to convert the current representation into another one when an operation is simpler to program or more efficient in the other representation. This limits memory waste and avoids consistency problems. However it can be quite inefficient because of frequent conversions of the whole data structure.

In this article, we explore the last approach and we make it practical. Precisely, each algorithm is programmed in its "natural" representation. A wrapper is responsible to delegate incoming calls only to the "natural" representation and to convert a representation into another one. For the sake of efficiency, conversions are performed lazily and sequences of delayed conversions are dynamically simplified when possible. This article presents the following contributions. First, we show how to make practical the collaboration of several representations of the same data structure. Second, we provide a general framework for laziness and dynamic optimization in Java. It lets the programmer declaratively specify dependencies between computations and it makes safer the programming of subtle algorithms. These specifications can be used to automatically generate tedious infrastructure code.

The article is structured as follows. Section 2 details the motivations of the paper, through an example based on directed graph representations, and introduces the contributions of our solution. Section 3 presents an optimized scheme to implement collaborative representations. Section 4 introduces a new way to support laziness in an imperative language like Java. Laziness makes collaborative representations efficient in practice. Section 5 proposes an evaluation of the framework on a graph based example. Then, we review related work (Section 6) and conclude (Section 7).

Motivation and Contribution

The choice of a data structure is mainly driven by the complexity of its most frequent operations. Unfortunately, when a new operation has to be developed, such a representation may not fit with it, both theoretically (time and space complexity) and practically (architecture design). Then, an option is to maintain several appropriate representations. Nevertheless, such duplication is expensive to store and to maintain. In the following, Section 2.1 illustrates our purpose with an example based on directed graph representation, even if our work goes beyond the scope of graph representations. Next, Section 2.2 discusses the contribution.

Example: Direct Graph Based Representation

Most of the practical applications using graph based representations require various properties like connected components, path existence between two nodes, cost of a minimum spanning tree, etc. However, the time and space complexity to compute these properties differ from one graph representation to another, and no best one exists when several operations are used. The authors of [START_REF] Mehlhorn | Algorithms and Data Structures[END_REF] explain on pages 172 to 173 that several representations of graph "are suitable for different sets of operations on graphs, and can be tuned further for maximum performance in any particular application. The edge sequence representation is good only in specialized situations. Adjacency matrices are good for rather dense graphs. Adjacency lists are good if the graph changes frequently." Futhermore, they also observe that "no graph representation is best for all purposes. How can on cope with the zoo of graph representation?". This observation is highlighted in applications that require graph representations to systematically compute several graph properties. This is the case for the implementation of global constraints [START_REF] Beldiceanu | Combining tree partitioning, precedence, and incomparability constraints[END_REF]. However, the complexity of this application lead us to introduce a simpler example with only two properties and two representations.

Consider the representation of a n-nodes m-arcs directed graph as a set of adjacency lists over the successors of each node. This representation allows to easily express a search over the descendants of a given node by using the well-known breadth first search algorithm. Such an algorithm is depicted by Figure 1, its time complexity is related to the complexity of the next(G, x) operation (line 10) which provide the successors of node x in G. In the case of a representation of the directed graph by an adjacency lists over the successors, next(G, x) can be done in O(1), and the desc(G, s) operation is achieved in O(n + m) time. But, if the ancestors of a node have to be computed then, the pred(G, x) operation is achieved in O(n) time and the ance(G, s) requires O(n 2 ) time. The problem is similar when the directed graph is represented by an adjacency lists over the predecessors of each node. Then, the next(G, x) operation complexity increases to O(n) time, and consequently desc(G, s) has an amortized complexity of O(n 2 ).

Thus, the complexity of a given operation differs from one representation to another, and the representation choice affects the efficiency of the operations. However, practical applications are based on several operations (e.g., compute both descendants and ancestors of nodes). For instance, our application uses several graph properties then, the procedures implementing the properties have to coexist. Precisely, if the graph representations support the reachable procedure both for the descendants and the ancestors of node s then, each of the two implementations are efficient for one of the two procedures, but not for both.

Contributions

The duplication of the data structures must be avoided because of the related memory waste and the time complexity enhancement due to the data structure management. Thus, a collaborative representation framework has to address the following aspects: (1) the data structures related to the representations should not be duplicated (to avoid memory waste), (2) systematic total conversion from one representation to another should be avoided when the required procedure is in the wrong representation (to limit time complexity waste). In this context, providing such a solution is a tedious task. However, we propose a Java framework to conciliate these two points.

Our solution proposes a declarative language to specify the dependencies between the representations and the procedures. The dependencies are used by a general scheme that inserts the conversions when and where they are required. In order to avoid useless conversions from one representation to another, our framework introduces a lazy approach to implement a partial conversion strategy. Thus, each time a procedure is executed, only the required information is converted according to its specifications.

Most often in practical applications, the execution of some procedures can be delayed until another one requires its effective execution. Our framework addresses this point by managing lazy execution of the procedures. Thus, during the execution, a call to a "delayable" procedure results in only recording its corresponding closure in a generic trace. On the other hand, a "strict" procedure may require the execution of some delayed procedures in the trace to be safely executed. Finally, dynamic optimizations allow to limit the trace size during the execution. We provide an optimization that can detect outstanding patterns among the closures (e.g., invertibility between closures, complementarity of a closure set), and operates simplifications (e.g., closure removals, closure substitutions). In the following, we detail and evaluate these features of our framework.

Collaborative Representations

In this section we present our approach. It enables us to compose pieces of software (i.e., several data representations and their corresponding algorithms) without modifying them. For the sake of simplicity, we use a toy running example but in Section 5 we evaluate a realistic example. Section 3.1 presents a simple (and inefficient) collaborative scheme. Section 3.2 and 3.3 introduce two optimizations of this scheme. Finally, Section 3.4 offers a language to define how several representations collaborate thanks to these optimizations.

Automatic Conversions

Let us consider a point in a two dimensional space. The coordinate of such a Point can be represented either using Cartesian coordinates or using polar coordinates. Some operations, for instance translations, are simpler to program and more efficient to execute in the Cartesian representation. On the other hand, other operations, for instance rotations, are simpler to program and more efficient to execute in the polar representation. We propose to use both representations. Each operation is programmed only in the more appropriate representation (e.g., translation is implemented for Cartesian coordinates, and rotation is implemented for polar coordinates) and two conversions functions (from Cartesian to polar and from polar to Cartesian) are written once for all operations.

A wrapper is generated in order to make both representations collaborative. We arbitrarily choose the Cartesian representation to be the initial representation. When an operation implemented in Cartesian representation is called, the wrapper delegates the call to the Cartesian representation. When an operation implemented in the polar representation is called, the wrapper first converts the Cartesian coordinates into polar coordinates, then delegates the call to the polar representation, and finally converts back the polar coordinates into Cartesian coordinates. Figure 2 illustrates this behavior. In this figure, a box is a Java object and a line is a reference from an instance to another: a wrapper hides the two representations, pc (a PointCart) and pp (a PointPol). At each point in time, the representation colored gray is valid. Initially, the point is in its Cartesian representation. Upon a call to be performed in the second representation (e.g., rot(a) at time k), the wrapper first converts pc into the polar representation by calling toPointPol, performs the operation in pp (time k + 1) and finally converts pp back into pc by calling toPointCart.

                  Fig. 2. Automatic conversion

Invertible Conversions

The scheme described in the previous section systematically introduces conversions when an operation in the non default representation is called. This ensures that when an operation is executed the corresponding representation is up to date. However, when we consider a sequence of operations, some conversions could be suppressed. For instance, to perform two successive rotations, there is no need to convert the coordinates (from polar to Cartesian and then from Cartesian to polar) between the two rotations. Such a scenario is depicted by Figure 3. A call to the rot(a) method leads to convert pc into pp. Then, the automatic conversion directly restores pc. When a new call to rot(a) is immediately performed, pc must be converted back into pp. So the sequence of inverse conversions pp.toPointCart(pc); pc.toPointPol(pp) can be suppressed. Our goal is to get a general scheme that can be applied to any representation and conversion algorithm. To avoid these useless conversions, we propose the following scheme. First, we delay the conversions as late as possible. Second, we dynamically detect and suppress sequences of two inverse conversions when they occur. This technique is not as simple at it may appears. First, to delay the conversions, we have to detect when a delayed conversion must be forced (otherwise the computation would be incorrect). Second, calls to conversions can be interleaved with any other code in the program. This must be taken into account to detect sequences of two inverse conversions.

Incremental Conversions

If a representation is huge, its conversion into another one could be expensive. When a complete conversion is not required, then an optimization consists in a partial conversion of the representation. For instance, let us now consider colored points. A color can be represented either in the RGB model or in the HSB model. We assume a colored point is represented either by a PointCartRgb or by a PointPolHsb. We can apply our collaborative technique to wrap these representations. However, note that the coordinate representation and the color representation are coupled: when a colored point coordinates are represented by Cartesian coordinates, then its color is represented by a RGB value. On the other hand, when a colored point coordinates are represented by polar coordinates, then its color is represented by a HSB value. 4 In the case of PointCartRgb and PointPolHsb, the coupling can introduce useless conversions. For instance, the sequence rot(a1); setRed(r) in Figure 4 requires converting a RGB color to a HSB color when rot is called (although rot does not use the color). If the coordinate representation and the color representation were decoupled, only the required conversions would be performed. For instance, in Figure 5, when a rotation is performed, the coordinates are converted to the polar representation but the color remains a RGB value. Then, when setRed is called the color does not have to be converted. This method calls toPointPol to convert the coordinates to the polar representation, then it calls toColorHsb to convert the color to its HSB value. In order to decouple representations, we only have to make lazy and invertible the conversion submethods (i.e., toPointPol and toColorHsb). This way, coordinates and color conversion becomes independent.

Our general scheme for representations collaboration relies on laziness and dynamic detection and suppression (i.e., simplification) of sequences of inverse conversions. This requires developers to declare the dependencies between representations (and their associated methods). In the next section, we show how such dependencies can be specified by the user.

Collaboration Specification

We have defined a language to declare collaborative representations. This language provides what is required to generate the boilerplate code that implements a collaborative representation. Figure 6 presents the grammar of our language. This language enables to specify a collaborative representation as follows. The keyword wrapper specifies the class identifier of the wrapper to be generated. The keyword representation lists the two (or more) representations to be wrapped. The keyword conversion lists the corresponding conversions. Note that, these are the top level conversion methods to be called by the wrapper (e.g., toPointPolHsb and toPointCartRgb but not toColorHsb in the previous example). The keyword inverse lists pairs of inverse methods. The keyword partition introduces a set of atoms that represent a partition of the representations. Each atom represents a part of a representation (e.g., a cartesian colored point can be decomposed into an atom for the coordinate and an atom for the color, or a single atom can represent both). The finer the decomposition is, the more precise the closure dependencies are. The keyword lazy specifies that a method is lazy. The next two arguments specifies which atoms are read and written when the lazy method is finally forced (i.e., executed). The keyword strict specifies that a method is strict. The next two arguments specifies which atoms are read and written when the strict method is executed. These atoms are used to compute dependencies between lazy and strict methods and to force evaluation of a delayed lazy method before a strict one reads or write the same part of the memory. Methods annotated as strict start by checking for delayed computation to be forced. Methods without strict or lazy annotation are plain Java (strict) methods that do not interfere with delayed computation.

The Figure 7 shows a specification of collaborative representations for colored points. We choose to partition the state in two atoms : a1 (which represents x, y, r, g and b) and a2 (which represents rad, teta, h, s and b). This makes the coordinates and the color representation coupled. Indeed, the accessor getR reads the memory part corresponding to a2, and the conversion method toPointPolHsb writes the memory part corresponding to a2. So, these two methods are dependent, and when the red component of the color is accessed, it first forces delayed calls to toPointPolHsb (that convert colors and coordinates). In order to decouple the coordinate representation and the color representation we only have to define a different specification based on a more precise partition. This specification would have four atoms: a1_1 corresponding to the Cartesian coordinates, a1_2 corresponding to the polar coordinates, a1_2 corresponding to the RGB colors, and a2_2 corresponding to the HSB colors. This enables to specify, for instance, setR() modifies only the RGB representation (i.e., a1_2) but not the Cartesian coordinates a1_1.

The finer the decomposition is, the more precise the closure dependencies are. However, the finer the decomposition is, the more expansive the closure dependencies computation are and the more memory they require. The choice of a decomposition in atoms should be guided by a tradeoff between precision and efficiency (in particular it is not worth spending more time to decide a closure evaluation can be delayed than evaluating it).

Here we summarize the steps required by our collaborative representations:

1. Programmers provides different implementations of a data structure.

2. The collaborative representations programmer implements conversion functions from a representation to another and specifies these methods are lazy as well as their side effects. He also specifies the strict methods (e.g., accessors). 3. The wrapper class and the closures classes are automatically generated. They rely on our framework for safe laziness in Java. 4. Users transparently calls the resulting library. The execution of lazy methods is delayed. When a strict method is called, our framework forces the evaluation of delayed methods required to compute the result of the strict one. As the application progresses the data get scattered in the different representations.

A Framework for Safe Laziness in Java

In order to support our specification language introduced in the previous section, we offer a framework that deals with the most difficult and error-prone tasks of collaborative representations: laziness in an imperative language. Hence, users can focus on writing those representations. Our framework features both lazy evaluation for the Java programming language and dynamic optimizations.

Laziness in Imperative Language

While laziness is a natural feature of functional programming languages, the implementation of lazy evaluation in imperative languages such as Java is complex:

-In order to delay a method call, the method, its receiver and its arguments must be stored in data structure (i.e., a closure) so that the method can actually be called later. -The execution of a lazy method can be delayed until its result is required by a strict computation. A lazy framework is able to detect when a delayed method result is required in order to force its evaluation. In an imperative language, a method can have side effects and modify variables (e.g., assign

x with 0). When a strict method has to read the value of the variable x, the closure of the delayed computation (that assigns x with 0) must be forced.

Our framework provides means to specify the side effects of methods and to automatically decide when a delayed computation must be forced.

-In an imperative language, two method calls are not in general commutative (e.g., "increment x, then square it" is not equivalent to "square x, then increment it"). So, our framework uses a trace in order to maintain the order of the closures. Dependencies between them also take into account the trace: sometimes, evaluating a closure requires to evaluate another before. -When two computations are inverse one of another (e.g., "increment x" and "decrement x") and both are delayed, the two closures can be suppressed without being evaluated and without changing the result of the program.

Our framework requires the user to specify closure side effects. These specifications could be automatically generated by abstract interpretation. This would still require the user to specify a partition of the representation (i.e., the corresponding abstract domain). However, such an analysis can be quite expansive in general. The side effect specifications can be used to compute closures dependencies. Next, we describe this aspect of our framework.

Closure Dependencies

In our framework, delayed computations are represented by subclasses of the class Closure. Closure classes can be automatically generated from their side effect specifications shown in the previous section. Closures must provide an evaluation method eval that actually calls the delayed method. Each closure must also provide two methods reads and writes. These methods are used to compute the dependencies between closures. They return a set of atoms implemented, in our experiment, by a BitSet. Let us considers two closures c1 and c2, with c1 is older than c2. When c2 is to be evaluated, c1 must be evaluated first if either the evaluation of c2 reads memory written by the evaluation of c1, or the evaluation of c2 writes memory read by the evaluation of c1, or the evaluation of c2 writes memory written by the evaluation of c1.

When a method call is delayed, the corresponding closure is created and pushed on a stack trace. (When a closure is pushed, if the inverse of the closure is already in the stack, both closures are removed. Due to space constraints, we do not detail here this dynamic simplification phase). When a strict method is called, the method force in Figure 8 is called to compute dependencies and force evaluation of some closures in the trace before the strict method is evaluated.

The method force visits the trace from the most recent closures to the oldest ones. In order to keep track of its position in the trace this method uses a second stack ecart and transfers closures from one stack to another, one at a time. If the current closure is required to be evaluated (line 5) it is tagged (line 6) but it is not evaluated immediately because older closures may require to be evaluated before, so the sides effects of the current closure are taken into account (lines 7-8). The memory written by this closure c is added to the memory written by all the closures to be evaluated s.writes. The memory read by this closure c is added to the memory read by all the closures to be evaluated s.reads and the memory written by c is removed from s.reads. Then, the visit continues. When the beginning of the trace is reached, the second half of the method force (lines 12-15) visits the closures from the oldest one to the most recent one. If a closure is tagged then it is evaluated, otherwise it is pushed back in the trace.

Evaluations

We now evaluate our approach over a realistic example related to the graph theory in the context of global constraints implementation. Global constraints represent invaluable modeling tools for Constraint Programming (CP). They heavily rely on graph theory through properties like the connected components, the strongly connected components or the transitive closure [START_REF] Beldiceanu | Combining tree partitioning, precedence, and incomparability constraints[END_REF]. Nevertheless, a global constraint has to combine efficiently several properties at a time. Our framework offers a promising way to efficiently and safely combines several procedures related to the graph properties.

As explained in Section 2.1 when a graph is represented by adjacency lists over the successors of each node (i.e., GraphSucc), it is easy and efficient to express a search over the descendants of a given node. On the other hand, when the graph is represented by adjacency lists over the predecessors of each node (i.e., GraphPred), the same search over the descendants becomes more complex. Symmetrically, it is easy and efficient to express a search over the ancestors in GraphPred, but it is more complex for searching the descendants. In this case, we can apply our collaborative representations scheme.

Conversion

Conversions between GraphSucc and GraphPred are based on two methods toNodePred(n) and toNodeSucc(n) which behave as depicted in Figure 9. The toNodePred method converts a column of the GraphSucc into a row of GraphPred. The notion of column is a logical view in GraphSucc (a list of lists of successor nodes) which has no corresponding direct accessor, does not exist in GraphSucc, so the method iterates for each node s, if the list of successors of s in GraphSucc contains n, it removes it from that list (which frees its memory so that nodes only exist in one representation at a time) and it adds s to the ancestors of n in GraphPred. The reverse conversion (from GraphPred to GraphSucc) is symmetric, hence invertible, that is, the back and forth conversions of a given node leaves both representations unchanged). In order to convert all the nodes of a graph, the method toGraphSucc (resp. toGraphPred) calls toNodeSucc (resp. toNodePred) for each node of the graph.

                              

Fig. 9. Partial conversion between lines and columns

This can be specified as in Figure 10. A class Graph can be automatically generated to wrap an instance of GraphSucc and an instance of GraphPred (line 1 and 2). A representation is transformed into the other one by calling either toGraphPred or toGraphSucc (line 3). We partition the toGraphSucc representation into its columns c i (this is a conceptual notion that is not implemented by the structure) and the toGraphSucc representation into its lines j . The methods toNodePred and toNodeSucc are inverse one of another (line 5). Both are lazy, and we specify their side effect. For instance, toNodePred(n) reads c n , the n th column in the successor representation, it erases (i.e., writes) it, and writes n , the n th line in the predecessor representation. The accessors are strict. We also specify their side effects. For instance, getNodeSucc reads a line (i.e., all columns) in the successor representation (line 8 and 9).

Conversion Strategies

Let us consider a graph with n nodes. The conversion method toGrapPred calls toNodePred for each node of the graph. If toGrapPred is defined as a for loop, its execution creates n closures (one for each call to toNodePred). Closure instantiation, simplification (e.g., with inverse rules) and dependencies computation can be expensive. We describe two alternative definitions of toGraphPred.

A first alternative is for the user of our framework to define a recursive and lazy version of toGraphPred. In this case, a call toGraphPred(i) would create only two closures corresponding to toNodePred(i) and toGraphPred(i+1). This recursive scheme can be much more efficient when nodes with low index are converted: the strict accessor call getNodePred(m) will require m closures of toGraphPred to be evaluated until the right closure toNodePred(m) is created. Unfortunately, when the last node of a graph is converted, a closure is still created for each node.

A better alternative is for the user of the framework to define a dichotomic recursive and lazy version of toGraphPred. When toGraphPred(start,end) is called it creates two closures corresponding to toGraphPred(start,mid) and toGraphPred(mid+1,end), where start is the first node to convert, end is the last node to convert, and mid is the middle of start and end. This recursive scheme builds at most 2log(n) closures when a node has to be converted. This is the conversion scheme we use in the evaluation below.

Benchmarks

We have evaluated our approach with a scenario related to graph theory (a short example is provided by Section 2.1). We compare the execution time, on 43 200 randomly generated graphs, of the standard single representation approach (either list of successors GraphSucc or list of predecessors GraphPred) and of our dichotomic lazy conversion approach. Each graph instance is benchmarked on 8 kinds of scenarios depicted in Figure 11. It depicts the patterns used for these experiments: (ance{3}desc){6} means the method ance is called three times successively, then the method desc is called once, this is repeated 6 times with randomly picked arguments. All patterns contains 24 method calls, but they vary in the frequency of the alternations between ance and desc calls. In this experiment, our graphs are structured as lattices and each scenario is evaluated on 5 kinds of arguments grouped by "zones": zone 1 means the arguments are chosen among all the nodes of the lattice, zone 2 means the arguments are chosen inside the bottom half of the lattice and so on. The bigger the zone, the more nodes will be converted to perform the ance or desc computation. In each case, we measured the execution time for the lists of successors representation, the lists of predecessors representation and of our approach. For scenarios with the same number of calls of each operation (e.g., (ance; desc){12}), successor and predecessor representations exhibit comparable execution time, but for non symmetric pattern (e.g., ance{24}) one representation may be up to 150 times slower than the other. Figure 11 compares our approach with the best of the two standard representations on each scenario. It shows that for all of the patterns, our approach is less efficient than the best of the two standard representations. However, note that when fewer nodes must be converted (zones 2 to 5), our approach gets close to the best representation. Moreover, measures shows that compared to the worst of the two standard representations for each scenario, our lazy approach has comparable performance but is at best up to 90 times faster. Because the number of conversions is more likely to be higher when zone equals one, the difference of behavior of partial conversions observed, around that point may be explained by the high number of closures corresponding to delayed conversion. This makes it harder for the framework to simplify invertible conversions.

A dedicated solution to this graph scenario would outperform our approach. However, our proposal does not impose a higher space complexity and is generally more efficient than both naive approaches. Moreover, it offers a general solution: it is less error prone (i.e., as long as side effects specifications are correct, no closure evaluation is forgotten), it reuses "natural" representations and it could be extended to manage more than two representations. Thus, our approach provides a good software engineering/performance trade-off, demonstrating the applicability of collaborative representations.

Related Work

The definition of aspect in the ASOD.Net wiki glossary [3] is based on the notion of tyranny of the dominant decomposition attributed to IBM's T. J. Watson Research center's research on Morphogenic Software. Multi-dimensional Separation of Concerns [START_REF] Tarr | N degrees of separation: multidimensional separation of concerns[END_REF] shows how the software artifacts corresponding to different concerns (a.k.a. hyperslices) can be merged to generate a full application. This general and abstract model is instantiated by Subject-Oriented Programming [START_REF] Harrison | Subject-oriented programming: a critique of pure objects[END_REF] where hyperslices are pieces of code (e.g., partial class hierarchies). Aspect-Oriented Programming [START_REF] Kiczales | Aspect-oriented programming[END_REF] is quite similar but it is asymmetric: it considers the structure of a base program and it provides pointcut languages to specify where another code crosscuts the base program and the corresponding pieces (i.e., advices) should be woven. All these static approaches enable to compose several pieces of code (i.e., a base program and several advices). However, they focus on the code structure, and the woven program executes the base code and the advices "at the same time". This do not help to compose different data representations (and their corresponding algorithms) and to dynamically change the representation at run-time.

Early work of Don Batory on data structure compilers and data structure tailoring and optimization provide languages to describe and compose data structure representation and their corresponding algorithms. In particular, Section 3.2 of [START_REF] Batory | The design and implementation of hierarchical software systems with reusable components[END_REF] introduces the notion of robust (i.e., interchangeable) algorithms versus non robust algorithms. It should be further studied if and how our technique could be used in this context in order to interchange non robust algorithms.

Our work shares similarities with views in database management systems (DBMS) [START_REF] Chamberlin | Structured query language[END_REF]. A view defines a table that is computed rather than stored. An updatable view requires the DBMS to infer a reverse mapping. However, in our framework, partial conversions dynamically scatter the data in the collaborative representations, while views duplicate the data of the underlying tables. Views have also be proposed for specification languages such as Z, but their collaboration is defined by an invariant, which is declarative but does not help to build a concrete solution [START_REF] Jackson | Structuring Z specifications with views[END_REF]. Wadler [START_REF] Wadler | Views: a way for pattern matching to cohabit with data abstraction[END_REF] has studied how to have views and pattern matching at the same time. This work is one of the main source of inspiration of our approach although it is restricted to functional languages and it focuses on pattern matching. Our dynamic simplifications of inverse closures is also inspired by a short cut to deforestation [START_REF] Gill | A short cut to deforestation[END_REF] that proposes such a dynamic scheme, to complement the static one, to simplify the functions fold and build.

Hughes [START_REF] Hughes | Why Functional Programming Matters[END_REF] argues laziness is a powerful tool to compose programs (i.e., functions). Laziness has an intuitive semantics in pure functional languages but it is tricky when sides-effects are introduced. So, lazy extensions of imperative languages are limited. For instance, LazyJ [START_REF] Warth | LazyJ: Seamless lazy evaluation in Java[END_REF] extends Java's type system with lazy types. The programmer is responsible for introducing coercions that force delayed evaluations, but there are no specification or propagation of dependencies. Recent work have introduced dependencies into imperative languages. They have been used to automatically incrementalize an invariant checks when a data structure is modified [START_REF] Shankar | DITTO: automatic incrementalization of data structure invariant checks (in Java)[END_REF] or to update a self-adjusting computation [START_REF] Acar | Imperative self-adjusting computation[END_REF]. In both cases, laziness is not involved and caching prevents from re-evaluating a computation. It should be studied how these techniques could complement ours.

Conclusion and Future Work

This article proposes a new approach to compose data structure representations and their corresponding algorithms. It introduces a general scheme to replace the dominant representation by multiple collaborative representations. Each algorithm is programmed in the best representation (i.e., that fits), so that the corresponding code is simpler or more efficient than in the other representations. The conversions from one representation to another are automatically inserted by a wrapper (so the original code does not have to be modified). A representation is partially converted by need: only the subparts of the representation required by a computation are converted. This technique relies on lazy evaluation and dynamic optimizations. We provide a framework to support it in Java. It let the user declaratively specify dependencies and simplification rules. The framework supports safer development (most of the code can be automatically generated and the dependencies are systematically propagated). We have validated our approach with actual experiments for different graph representations. Our evaluations shows that our approach is practical. It provides a good tradeoff between software engineering issues and performances.

Our proposal offers many opportunities for future work. We list here a few of them. First, our approach already requires the user to specify the memory read and written by methods. Such a piece of information could be used to dynamically check when a method call can be skipped (i.e., when the memory m reads and writes has not been written since the previous call to m). Second, our approach relies currently on dynamic analysis only, but it could benefit from static analyses too. For instance, the automatic derivation of reads and writes from the source code could be studied. It could also be interesting to statically decide when two closures never interacts in order to have independent traces instead of a single one (in our running example we could have a trace by graph instance). This shorter traces would make the dependencies propagation less expensive. In some cases the user could specify a conversion function and its inverse could be automatically generated [START_REF] Matsuda | Bidirectionalization transformation based on automatic derivation of view complement functions[END_REF][START_REF] Foster | Combinators for bi-directional tree transformations: a linguistic approach to the view update problem[END_REF]. Finally, other applications of our framework for safe laziness in Java should be explored.

Fig. 1 .

 1 Fig. 1. Detecting the descendants (desc(G, s)) or the ancestors (ance(G, s)) of node s in a directed graph G independently of the graph representation.

Fig. 3 .

 3 Fig. 3. Invertible conversion

Fig. 4 .

 4 Fig. 4. Coupled representations

Fig. 5 .

 5 Fig. 5. Decoupled representations for incremental conversions

4}

1 wrapper class { 2 representationFig. 6 .

 26 Fig.6. Specification language for automatic conversions

Fig. 7 .

 7 Fig. 7. Collaborative (coupled) representations of colored points (excerpt)

1v 6 c 7 s 8 s 9 }Fig. 8 .

 67898 Fig. 8. Compute closure dependencies and force their evaluation

10}Fig. 10 .

 10 Fig. 10. Collaborative Representations GraphSucc and GraphPred (excerpt)

Fig. 11 .

 11 Fig. 11. Best of GraphSucc and GraphPred versus Collaborative Representations

This coupling can be easily avoided: a colored point could aggregate a coordinate and a color. In general, it is not possible to avoid such a coupling (see Section

5).