Shuo Zheng

Marc Antonini

Marco Cagnazzo

Lorenzo Guerrieri

Michel Kieffer

Irina Delia Nemoianu

Roger Samy

Bo Zhang

Softcast with per-carrier power-constrained channels

Keywords: Joint source-channel coding, Softcast, Precoding matrices, PLT channels

la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

A huge research effort has been devoted to design video coding and transmission systems to get the best received video quality for a given amount of channel resources. This is of paramount importance for cellular broadcasting, where channel conditions may be varying with time and among receivers, or for multimedia transmission in mobile ad-hoc networks, but also for communication over wired channels, such as DSL or powerline telecommunication (PLT) channels. Traditional solutions for these use-cases consist in hybrid video coding (H.264/AVC or HEVC [START_REF] Wiegand | Overview of the H.264/AVC video coding standard[END_REF][START_REF] Sullivan | Overview of the high efficiency video coding (HEVC) standard[END_REF]) or scalable video coding [START_REF] Schwarz | Overview of the scalable video coding extension of the H.264/AVC standard[END_REF] over a suitable network protocol. However, in the first case the source encoding is performed without knowing the actual channel characteristics, causing channel underuse or digital cliff; in the second, even if the transmission rate can be adapted, each additional coding layer significantly reduces the performance of the system.

Joint source-channel video coding (JSCVC) has the potential for dramatically improve the quality of the received video in such challenging conditions, as demonstrated recently by breaking-through systems such as Softcast and its variants [START_REF] Jakubczak | Softcast: one-size-fits-all wireless video[END_REF][START_REF] Zhihai | Layered image/video softcast with hybrid digital-analog transmission for robust wireless visual communication[END_REF][START_REF] Xiong | Power-distortion optimization for wireless image/video softcast by transform coefficients energy modeling with adaptive chunk division[END_REF]. Reminiscent of hybrid digital-analog video coding ideas proposed by [START_REF] Polley | Hybrid channel coding for multiresolution hdtv terrestrial broadcasting[END_REF][START_REF] Schreiber | Advanced television systems for terrestrial broadcasting: Some problems and some proposed solutions[END_REF], Softcast is a JSCVC scheme that encodes the video content with linear-only operators (such as a full-frame DCT and scaling). The original pixel luminance is transformed into numerical values that are sent on the channel with an extremely dense modulation. This can be done in such a way that high-quality channels only perturb the least significant bits of the numerical values, while low-quality channels still preserve the most significant bits. In Softcast, compression involves a full-GoP 3D-DCT transform and transformed coefficient selection, error protection is obtained by power allocation and resilience to packet loss is obtained by giving up temporal prediction and on the contrary ensuring that all packets contribute equally to the quality of the decoded video. The physical layer uses a classical OFDM framework. Detailed comparisons with H.264/AVC or SVC over 802.11 wireless networks show very clearly the advantages of Softcast [START_REF] Jakubczak | Softcast: one-size-fits-all wireless video[END_REF]. Many efforts have been done to adapt the data generated by Softcast and by linear coders in general to various channel conditions, such as wideband AWGN channels [START_REF] Jakubczak | Performance regimes of uncoded linear communications over awgn channels[END_REF], fading channels [START_REF] Zhang | Ecast: An enhanced video transmission design for wireless multicast systems over fading channels[END_REF][START_REF] Zhang | Channel-aware video softcast scheme[END_REF], MIMO channels [START_REF] Liu | Compressive image broadcasting in MIMO systems with receiver antenna heterogeneity[END_REF]. Nevertheless, all of these works consider a single constraint on the total transmission power when evaluating the optimal scaling factors for the blocks of transform coefficients (these blocks are called chunks). For some channels, such as DSL or PLT [START_REF] Yonge | An overview of the homeplug AV2 technology[END_REF], OFDM is employed and the power constraint depends on the index of the subchannel. Similarly, for multi-antenna transmission, each antenna has its own power amplifier and power constraint. In such situations, the simple approach of using a single total power constraint may give suboptimal scaling factors and individual power constraints may not be satisfied. An adaptation of Softcast when noise characteristics depend on the considered subchannel but with total power constraint can be found in [START_REF] Zhang | Channel-aware video softcast scheme[END_REF]. The chunks with the most energy are transmitted over the best channels after a proper scaling. This solution, however does not consider different power constraints on each subchannel. This paper deals with the adaptation of Softcast-based video transmission scheme considering parallel subchannels with different power constraints. To minimize the receiver MSE, one has to find a precoding matrix that transforms the chunk coefficients, modeled as independent Gaussian sources with different variances, so that they match the per-carrier power constraints. After recalling the main principles of Softcast in Section 2, we will describe this optimization problem in Section 3, recall the solution proposed in [START_REF] Lee | Optimal linear coding for vector channels[END_REF] and rediscovered later in the context of MIMO communication by [START_REF] Palomar | Optimum linear joint transmit-receive processing for MIMO channels with qos constraints[END_REF][START_REF] Palomar | 3 of Foundations and trends in communications and information theory[END_REF]. The main contributions of this paper consist in adapting the precoding problem to the Softcast scheme (allowing to find optimal power allocation solution) and in proposing suboptimal but simpler alternative solutions. A final contribution is a simulation-based validation of the various precoding schemes, considering the transmission of several HD videos over a realistic PLT channel model (Section 4).

SOFTCAST

The general architecture of Softcast transmitter and receiver is shown in Fig. 1. The input digital video signal undergoes a linear 3D-DCT transform, consisting of a full-frame 2D-DCT followed by a temporal 1D-DCT on a Group of Pictures (GoP) of nP frames.

Softcast works independently GoP by GoP. After a GoP has been transformed the resulting coefficients are grouped into chunks. A chunk is a set of nr × nc spatial coefficients belonging to the same temporal subband. The nC chunks are sorted according to their variance and only the first nS of them can be sent, according to the bandwidth limitations of the channel (see also the next section). The map of the selected chunk is robustly transmitted (using, e.g., a strong FEC code) on the channel: since the number of chunks is relatively small, the rate overhead needed to robustly transmit the map can be neglected.

The selected chunks are scaled in order to minimize the reconstruction error at the decoder. In [START_REF] Jakubczak | Softcast: one-size-fits-all wireless video[END_REF], a simple power-constrained AWGN channel is considered. These results are extended to several parallel channels with different gains in [START_REF] Zhang | Channel-aware video softcast scheme[END_REF]. The next section considers an extension of this result to parallel subchannels with individual power constraints and different noise characteristics.

SUBCHANNELS WITH DIFFERENT POWER CONSTRAINTS

The j-th coefficient of each of the nC chunks are assumed generated by a source vector x ∈ R n C such that E (x) = 0 and E xx T = Λ = diag (λ1, . . . , λn C ) . This vector has to be transmitted over a wideband channel split into nSB parallel subchannels. The power constraint for the i-th subchannel is Pi. The noise vector v corrupting the data on the subchannels is assumed to be zero-mean Gaussian process v with E vv T = N = diag σ 2 1 , . . . , σ 2 n SB . One has thus to determine an efficient way to transmit the selected chunks over the subchannels.

For that purpose, one will use the results introduced in [START_REF] Lee | Optimal linear coding for vector channels[END_REF][START_REF] Palomar | Optimum linear joint transmit-receive processing for MIMO channels with qos constraints[END_REF], which studied the problem of determining 1) an optimal precoding matrix G ∈ R n SB ×n C to transform the source vector x before transmission to get y = Gx; and 2) a decoding matrix H ∈ R n C ×n SB at receiver side to retrieve

x = H (Gx + v) such that G and H minimize ε = tr E (x -x) (x -x) T (1)
and satisfy the subchannel power constraints

GΛG T i,i = Pi, i = 1, . . . , nSB. (2)
The Lagrangian of this constrained optimization problem is

L (G, H, γ1, . . . , γSB) = tr Λ -HGΛ -ΛG T H T + H GΛG T + N H T + n SB i=1 γi GΛG T i,i -Pi .
Fixing the precoding matrix, [START_REF] Lee | Optimal linear coding for vector channels[END_REF][START_REF] Palomar | Optimum linear joint transmit-receive processing for MIMO channels with qos constraints[END_REF] obtained the optimum decoding matrix

H = ΛG T GΛG T + N -1 . (3)
Moreover, a necessary condition for optimality is H T H + Γ G = H T with Γ = diag (γ1, . . . , γSB), the matrix of Lagrange multipliers.

Using the previous results and introducing (1) may be rewritten as

G = N -1/2 G, (4)
ε = tr Λ -ΛG T G ΛG T + I -1 G Λ (5)
which has to be minimized with the constraints

N 1/2 G ΛG T N 1/2 i,i = Pi, i = 1, . . . , nSB (6)
leading to

G ΛG T =      P1/σ 2 1 * * * * P2/σ 2 2 * * * * . . . * * * * Pn SB /σ 2 n SB      = P . (7)
When some G minimizing (5) with the constraint (7) has been found, then G = N 1/2 G and the corresponding H minimize (1) with the constraint (2). For this reason, one considers first the problem of finding the optimal precoding matrix G with signal-to-noise constraints (7) that minimizes [START_REF] Jakubczak | Softcast: one-size-fits-all wireless video[END_REF]. One can thus define an equivalent channel with subchannel power constraints corresponding to the signal-to-noise ratios of the original subchannels and uncorrelated unit-variance noise components. Once a precoding matrix G has been found for the equivalent channel, the matrix G for the original channel may be deduced from [START_REF] Schwarz | Overview of the scalable video coding extension of the H.264/AVC standard[END_REF].

In what follows, one assumes without loss of generality that λ1

• • • λn C and that σ 2 1 • • • σ 2 n SB .

Optimal solution

To minimize [START_REF] Jakubczak | Softcast: one-size-fits-all wireless video[END_REF] with the constraint [START_REF] Xiong | Power-distortion optimization for wireless image/video softcast by transform coefficients energy modeling with adaptive chunk division[END_REF], [START_REF] Lee | Optimal linear coding for vector channels[END_REF] first consider the solution with the total power constraint of the equivalent channel

Peq = n SB i=1 Pi/σ 2 i ( 8
)
for which the optimal encoding matrix has the form

G = diag(g11, . . . , gn S n S ) 0 0 0 (9)
where nS min (nSB, nC) is the largest integer satisfying ¸1/2 P Fig. 2: Simple chunk scaling, assuming unit channel noise variance When the noise components are uncorrelated and of equal characteristics, as is the case for the equivalent channel, [START_REF] Lee | Optimal linear coding for vector channels[END_REF] shows that any orthogonal transform matrix does not change optimality. Then, considering the diagonal matrix D with the giis as diagonal elements and introducing the matrix M = DΛD T , one has to find an orthogonal transformation matrix Z such that ZM Z

λn S γ, √ γ = n S i=1 √ λi
T = P . If such Z exists, G = ZD. (11)
Finding Z requires to solve an inverse eigenvalue problem, since one has to determine the off-diagonal elements of P that has prescribed eigenvalues given by the diagonal matrix M . A constructive solution based on majorization theory is proposed in [START_REF] Lee | Optimal linear coding for vector channels[END_REF][START_REF] Palomar | Optimum linear joint transmit-receive processing for MIMO channels with qos constraints[END_REF][START_REF] Viswanath | Optimal sequences and sum capacity of synchronous CDMA systems[END_REF], provided that the l largest diagonal elements of M are larger than the sum of the l corresponding diagonal elements of P and trM = trP . When the previous necessary condition is not satisfied, one considers a matrix of Lagrange multipliers of the form

Γ = γ1I1 0 0 γ2I2
where I1 and I2 are p × p and (nSB -p) × (nSB -p) identity matrices. The optimal matrix G has then the form

G = Z1D1 0 0 Z2D2
where D1, D2 and Z1, Z2 are obtained solving two total power constraint optimization problems and using two numerical inverse Jacobi methods, see [START_REF] Palomar | Optimum linear joint transmit-receive processing for MIMO channels with qos constraints[END_REF] for more details. Nevertheless, the computed matrix G (or G) has to be transmitted to the receiver to allow decoding. As can be seen in [START_REF] Lee | Optimal linear coding for vector channels[END_REF][START_REF] Palomar | Optimum linear joint transmit-receive processing for MIMO channels with qos constraints[END_REF], G is a scaled product of rotation matrices (due to the inverse Jacobi method), which may be efficiently encoded. Nevertheless, for large nSB, the evaluation complexity for G may become significant.

Alternative solutions

Two suboptimal solutions are now proposed, in which the transform matrix G still satisfies (2), but may be obtained in a much easier way. In what follows, one assumes without loss of generality that the chunks and the subchannels are ordered with decreasing variance and with decreasing signal-to-noise ratios (SNR). Moreover, one considers only the equivalent channel.

In the first solution, called Simple Chunk Scaling (SCS), the chunk of largest variance is transmitted over the subchannel with the best SNR. The chunk with the second largest variance is sent over the subchannel with the second best SNR, etc., see Fig. 2. To fit the power constraint, the coefficients of the i-th chunk are multiplied by gSCS,i = Pi/ (λi).

The second solution, called Simple Chunk Scaling with Hadamard Transform (SCSHT), considers the optimal chunk scaling (10) obtained considering the total power constraint [START_REF] Polley | Hybrid channel coding for multiresolution hdtv terrestrial broadcasting[END_REF]. The scaled chunks are then Hadamard-transformed to get transformed chunks of similar power Peq/nSB, see Fig. 3

SCSHT,i = gii, i = 1 . . . ns, g

SCSHT,i = 0, i = ns+1 . . . nSB and g

(2)
SCSHT,i = nSBPi/Peq, where gii is given by [START_REF] Jakubczak | Performance regimes of uncoded linear communications over awgn channels[END_REF]. This solution is close to the original Softcast scheme proposed in [START_REF] Jakubczak | Softcast: one-size-fits-all wireless video[END_REF], where a total power constraint is considered.

EXPERIMENTAL RESULTS

In order to perform simulations, we first used the luminance of the Kimonol video sequence from the HEVC test set. It is a HD video sequence (resolution: 1920 × 1080), with 24 frames per second. Chuncks of 30 × 40 coefficients are used.

An in-home power line channel is considered for transmission. The considered frequency range is from 1.8 MHz to 86.13 MHz, which is the same range considered by the HomePlug Alliance in the last generation specification HomePlug AV2 [START_REF] Yonge | An overview of the homeplug AV2 technology[END_REF]. The spacing between subcarriers is 24.414 kHz. In OFDM-based PLT systems like AV2, typically SNRs per subchannel are available. Each subchannel is assumed to be modeled accurately by an AWGN channel. An example of the individual subchannel SNR constraints are represented in Fig. 4, which relates to a bad SISO link from ETSI STF 477 database [1].

Considering a Homeplug AV2-type physical layer adapted to Softcast, in which root-raised-cosine Nyquist filters with 30% rolloff are used, one obtains a per-subchannel transmission rate of 37.56 × 10 3 real-valued symbols per second. Remember that Softcast employs very high-density or analog constellations.

The various chunk scaling schemes are compared considering the average received video Peak Signal-to-Noise (PSNR) between the original video and the reconstructed video. In what follows, one considers noise with equal unit variance for each subcarrier.

Several transmission configurations are considered, according to the GoP size, the number of transmitted chunks and the number of subchannels used. The latter determines the maximum transmission rate and the maximum number of chunks that may be transmitted per GoP.

Results are provided in Table 1. Besides the scenario index, the first column is the GoP size; the second is the number of transmitted chunks; the third is the number of subchannels used; the fourth and fifth are the corresponding rates. Columns 6 to 8 report the resulting PSNRs for the three considered power allocation strategies. We first remark that the optimum precoding matrix provides always better results than the other ones. In particular, for a GoP size equal to 2, if we transmit more chunks, the optimal strategy has increasing gains, up to 3 dB with respect to SCS and 4.3 dB with respect to the SCSHT (plain Softcast). Considering the two last rows for GoP size 2, if we separate the transmission in two time slots and we always use the best 1024 subchannels, we obtain even better performance compared with using all subchannels and transmitting them in one time slot.

If we increase the GoP size but keep the number of chunks and number of subchannels unchanged, the PSNR will be worse because there are not enough chunks to represent the images. On the other hand, if we increase the number of chunks, the PSNR is increased accordingly. In any case, the proposed strategy gains several dBs with respect to the plain Softcast, see also Fig. 5.

We consider also a reduced complexity version of the proposed strategy, whose results are shown in the last row of Table 1. The reduced-complexity variant consists in gathering the chunks in groups of s chunks. Then, the variance of the group is used in the optimization problem. This divides the dimensionality of the problem by the number of groups, but the resulting precoding matrix is suboptimal.

In Scenario 13 and 14, GoPs of 8 frames are considered. A total of 13824 chunks per GoP has to be transmitted. In Scenario 13, these chunks are transmitted in 8 time slots. For each time slot, 1728 Table 2: Average PSNRs (in dB) over all frames for HD videos chunks are sent over the best 1728 subchannels. In Scenario 14, the sub-optimal strategy is used and in each time slot, the 1728 chunks are split in two parts of 864 chunks each, and the same is done for the subchannels. Two optimal predocing matrices are then designed for the first and the last 864 chunks and first and last 864 channels. Scenario 14 shows that this strategy results in a PSNR decrease of 1.2 dB compared to Scenario 13, but on the other hand the precoding matrix design algorithm takes only 57 % of the time of the original one. We observe that the reduced-complexity strategy provides an alternative trade-off, and that it is still better than references. In a second set of simulations, three additional HD video sequences are considered: DuckTakeOff, ParkJoy, and Life. Table 2 presents the resulting PSNRs averaged over all frames of the video sequences for Scenario 7 and 8. Fig. 6 shows the evolution with time of the PSNRs obtained with the various solutions. The highest benefits provided by the optimal precoding matrix are for the parts of all video sequences which have the best quality.

CONCLUSIONS

In this paper we consider a Softcast video coding and transmission scheme with a power allocation when multiple channels with different power constraints and noise characteristics have to be considered. An equivalent channel where the different power constraints are translated into signal-to-noise constraints is considered. The problem is then formulated as an inverse eigenvalues problem. Using an existing iterative algorithm for the inverse eigenvalues problem, we provide an optimal power allocation strategy that has better performance than alternative strategies that can be found in the stateof-the-art. Future work may address the complexity reduction of the proposed strategy.

Fig. 1 :

 1 Fig. 1: Softcast transmitter and receiver

Fig. 4 :Fig. 5 :

 45 Fig. 4: SNR as a function of the subcarrier index for the considered PLT channel

Fig. 6 :

 6 Fig. 6: PSNR as a function of time for Scenario 8.

Table 1 :

 1 . The scaled chunks Simulation results for Komono1, average PSNRs are in dB are then rescaled to fit the individual channel power constraints. The two scaling factors are then g

				¸1	g SCSHT,1 (1)		g SCSHT,1 (2)	P 1
				¸2	g SCSHT,2 (1)		g SCSHT,2 (2)	P 2
		Chunk selection	¸i	g SCSHT,i (1)	Hadamard transform	g SCSHT,i (2)	P i	Channel
				¸nSB	g SCSHT, (1)	nSB		(2) g SCSHT, nSB	P nSB
	Fig. 3: Simple chunk scaling with Hadamard transform, assuming
	unit channel noise variance
	Scenario	Gop	# transmit.	# used sub-	Rate	Max Rate	Optimal	SCSHT	SCS
		size		chunks	channels	(Msymb/s)	(Msymb/s)	PSNR	PSNR	PSNR
	1	2		16		16	0.23	0.6	29.6	29.6	29.5
	2	2		64		64	0.92	2.4	33.9	33.9	33.7
	3	2		128	128	1.84	4.8	36.7	36.6	36.2
	4	2		256	256	3.68	9.6	39.0	38.7	38.1
	5	2		512	512	7.36	19.2	40.9	39.9	39.5
	6	2		1024	1024	14.7	38.5	42.2	38.5	40.4
	7	2		2048	2048	29.5	76.9	42.7	36.9	40.8
	8	2		2048	1024 (×2)	29.5	38.5	44.9	40.7	41.9
	9	3		2048	1024 (×2)	19.7	38.5	43.4	39.6	41.1
	10	3		3072	1024 (×3)	29.5	38.5	45.1	40.9	41.9
	11	4		4096	1024 (×4)	29.5	38.5	45.2	41.1	41.9
	12	5		6144	1024 (×6)	35.4	38.5	46.4	41.8	42.5
	13	8		13824	1728 (×8)	49.8	64.9	46.7	44.1
	14	8		13824	1728 (×8)	49.8	64.9	45.5	44


Thomas Degueule
email: thomas.degueule@inria.fr

Benoit Combemale
email: benoit.combemale@irisa.fr

Jean-Marc Jézéquel
email: jezequel@irisa.fr

On Language Interfaces

Complex systems are developed by teams of experts from multiple domains, who can be liberated from becoming programming experts through domainspecific languages (DSLs). The implementation of the different concerns of DSLs (including syntaxes and semantics) is now well-established and supported by various languages workbenches. However, the various services associated to a DSL (e.g., editors, model checker, debugger or composition operators) are still directly based on its implementation. Moreover, while most of the services crosscut the different DSL concerns, they only require specific information on each. Consequently, this prevents the reuse of services among related DSLs, and increases the complexity of service implementation. Leveraging the time-honored concept of interface in software engineering, we discuss the benefits of language interfaces in the context of software language engineering. In particular, we elaborate on particular usages that address current challenges in language development.

Introduction

As far back as 1972, Edsger W. Dijkstra said in his ACM Turing Lecture:

Another lesson we should have learned from the recent past is that the development of 'richer' or 'more powerful' programming languages was a mistake in the sense that these baroque monstrosities, these conglomerations of idiosyncrasies, are really unmanageable, both mechanically and mentally.

I see a great future for very systematic and very modest programming languages.

This quote is often cited by proponents of Domain Specific Languages (DSL), which are indeed modest languages specifically designed for a single purpose.

Until now however, the vision of building large systems with the help of a set of DSLs, each caring for a specific aspect of the system, did not really turn into reality. Two main reasons why it has always been hard to work with DSLs, are:

1. Weaving together the various aspects of a system expressed in different DSLs is still mostly ad hoc and artisanal [START_REF] Jézéquel | Model Driven Design and Aspect Weaving[END_REF]. However recent approaches such as the GEMOC initiative [START_REF] Combemale | Globalizing modeling languages[END_REF] have made significant progresses towards that goal. 2. A DSL needs specific tool support: editors, parsers, checkers, interpreters, compilers, analysers, refactoring tools, etc. All of this software is subject to standard software engineering issues: successive versions, simultaneous variants, quality control (with e.g. tests). While general purpose languages used by millions of people can justify a high level of investment on building these supporting tools, the return on investment is more problematic for DSL used by definition by a much smaller number of people.

Regarding the second issue, the implementation of the different concerns of DSLs (including syntaxes and semantics) is now well-established and supported by various languages workbenches. However, the implementation of the services associated to a DSL (e.g., editors, model checker, debugger and composition operators) are still directly based on its implementation. Consequently, as the implementation of a DSL evolves, all services must be updated to target the new implementation. It is also not possible to reuse services for different, yet similar DSLs that target the same domain of application (e.g. two variants of state machine DSLs developed by different companies, or two versions of the same DSL). Moreover, most services require information that is scattered in the different concerns that compose a DSL, expressed in various and usually complex formalisms. Overall, the lack of abstraction mechanisms on top of DSL implementations complexifies the definition of services and hampers their reuse.

In this paper, we reflect on the uses and benefits of interfaces in programming and software engineering (Section 2). We then study how the concept of interface can be adapted to software language engineering to improve the current practice of language development. Specifically, we show how the concept of language interface can help to address various challenges that arise from current language development practices (Section 3). Finally, we conclude in Section 4.

Interfaces in Programming and Software Engineering

The time-honored concept of interface has been studied since the early days of computer science in many areas of programming and software engineering. Despite variability in their exact realization, interfaces invariably rely on common fundamental concepts and provide similar benefits. Historically, the notion of interface is intrinsically linked to the need for abstraction, one of the fundamental concepts of computer science. As stated by Parnas et al, "an abstraction is a concept that can have more than one possible realization" and "by solving a problem in terms of the abstraction one can solve many problems at once" [START_REF] Parnas | Abstract types defined as classes of variables[END_REF]. One can refer to an abstraction, leaving out the details of a concrete realization and the details that differ from one realization to another [START_REF] Kell | In search of types[END_REF]. Originally, in programming, the key idea was to encapsulate the parts of a program that are more prone to change into so-called modules, and to design a more stable interface around these change-prone parts. This concept, known as information hiding, eliminates hard-wired dependencies between change-prone regions, thereby protecting other modules of the program from unexpected evolution [START_REF] Parnas | On the criteria to be used in decomposing systems into modules[END_REF].

As different realizations may be used in place of the same abstraction, interfaces also foster reuse: one module can substitute another one in a given context provided that they realize the same interface, as expected by a client. The choice of a concrete module is transparent from the point of view of the client of the interface. Because interfaces expose only a portion or an aspect of a realization, leaving out some details, the nature of an interface is highly dependent on the nature of the concrete realization it abstracts. Following the evolution of programming paradigms, authors have thus defined various kind of interfaces for various concrete realizations: modules (module interfaces in Modula-2 [START_REF] Wirth | Modula: A language for modular multiprogramming[END_REF]), packages (package specifications in Ada [START_REF] Ichbiah | Reference manual for the Ada programming language[END_REF]), objects (protocols in Smalltalk [START_REF] Goldberg | Smalltalk-80: the language and its implementation[END_REF]), or components in Component-Based Software Engineering (CBSE) [START_REF] Heineman | Component-based software engineering[END_REF], to name a few.

The expressiveness in which one can specify an interface for a given kind of realization also varies: interfaces over classes in standard Java merely consists of a set of method signatures, while languages supporting design-by-contract enable the expression of behavioral specifications, e.g. in the form of pre-and post-conditions on those signatures [START_REF] Meyer | Applying'design by contract[END_REF]. The expressiveness of contracts themselves range from purely syntactical levels to extra-functional (e.g. quality of service) levels [START_REF] Beugnard | Making components contract aware[END_REF]. Interfaces are also closely linked to the notion of data type in programming languages [START_REF] Canning | Interfaces for stronglytyped object-oriented programming[END_REF]. Types abstract over the concrete values or objects manipulated by a program along its execution. Type systems use these types to check their compatibility, reduce the possibilities of bugs, and foster reuse and genericity through polymorphism and substitutability [START_REF] Cardelli | On understanding types, data abstraction, and polymorphism[END_REF].

While in programming languages the realizations hidden behind a given kind of interface are most often homogeneous, this is usually not the case in CBSE. As an illustration, component models enable communication between components written in different programming languages and deployed on heterogeneous platforms [START_REF] Siegel | CORBA 3 fundamentals and programming[END_REF]. In such a case, interfaces abstract away from implementation technologies to enable interoperability between heterogeneous environments. The associated runtime model is most of the time unaware of the functional aspect of components and uses generic interfaces to manage their life cycle (e.g. deploying or reloading a component). Most component models also provide the notion of required interface as a means to make explicit the dependencies between components and to reason about how different components interact together and must be composed.

In summary, interfaces are used in many ways and vary according to the purpose they serve. While "interfaces as types" mainly target the safe reuse and substitutability of modules and objects in different contexts and focus on functional aspects, the interfaces used in CBSE allow components to be independently developed and validated, and focus on extra-functional aspects. From these observations, we explore in the next section possible applications of the concept of interfaces at the language level, to improve the current practice of software language development.

3 Language Interfaces for Software Language Engineering "Software languages are software too" [START_REF] Favre | Languages evolve too! changing the software time scale[END_REF] and, consequently, they inherit all the complexity of software development in terms of maintenance, evolution, user experience, etc. Not only do languages require traditional software development skills, but they also require specialized knowledge for conducting the development of complex artifacts such as grammars, metamodels, interpreters, or type systems. The need for proper tools and methods in the development of software languages recently led to the emergence of the Software Language Engineering (SLE) research field which is defined as "the application of systematic, disciplined, and measurable approaches to the development, use, deployment, and maintenance of software languages" [START_REF] Kleppe | Software language engineering: creating domain-specific languages using metamodels[END_REF]. While the notions presented in this paper are applicable to both general-purpose and domain-specific languages (DSLs), we put a particular emphasis on the specificities of DSLs, which are small languages targeted to a particular domain of application.

In the SLE community, new DSLs are usually developed using a language workbench, a "one-stop shop" for the definition of languages and their environments [START_REF] Visser | A language designer's workbench: A one-stop-shop for implementation and verification of language designs[END_REF]. The notion of language workbench originates from the seminal work of Martin Fowler [START_REF] Fowler | Language workbenches: The killer-app for domain specific languages[END_REF]. The main intent of language workbenches is to provide a unified environment to assist both language designers and users in, respectively, creating new DSLs and using them. Modern language workbenches typically offer a set of meta-languages that language designers use to express each of the implementation concerns of a DSL, along with tools and methods for manipulating their specifications. Examples of modern language workbenches are manifold: Xtext [START_REF] Eysholdt | Xtext: implement your language faster than the quick and dirty way[END_REF], Monticore [START_REF] Krahn | Monticore: a framework for compositional development of domain specific languages[END_REF], Spoofax [START_REF] Kats | The spoofax language workbench: rules for declarative specification of languages and IDEs[END_REF] to name just a few.

One of the current trend in SLE is to consider more and more languages as first-class entities that can be extended, composed, and manipulated as a whole. However, to the best of our knowledge, there exists no previous work dealing with the explicitation of language interfaces, that is, interfaces at the language level, explicitly separated from language implementations, that provide the appropriate abstraction to ease the manipulation of languages as first-class entities. To motivate the need for language interfaces, we explore in this section some of the current challenges faced in SLE and highlight how they match the challenges that have been addressed with the use of interfaces in programming and software engineering.

Ingredients a Domain-Specific Language

To clarify what language interfaces abstract over, we must first understand what languages are made of. Domain-specific languages are typically defined by their abstract syntax, concrete syntax(es) and semantics. Various approaches may be employed to specify each of those, usually using dedicated meta-languages provided by language workbenches [START_REF] Visser | A language designer's workbench: A one-stop-shop for implementation and verification of language designs[END_REF]. The abstract syntax specifies the domain concepts and their relations defined by a metamodel or a grammar -the latter also defining the concrete syntax. This choice often depends on the language designer's background and culture. Examples of meta-languages for specifying the abstract syntax of a DSL include MOF [START_REF]MOF, 2.0 core final adopted specification[END_REF] and SDF [START_REF] Heering | The syntax definition formalism sdf-reference manual[END_REF]. The semantics of a DSL can be defined using various approaches including axiomatic semantics, denotational semantics, operational semantics, and their variants [START_REF] Mosses | The varieties of programming language semantics and their uses[END_REF]. Concrete syntaxes are usually specified as a mapping from the abstract syntax to textual or graphical representations, e.g. through the definition of a projectional editor [START_REF] Voelter | Projecting a modular future[END_REF]. DSLs usually benefit from dedicated environments that assist language users in the creation, analysis, and management of models and programs throughout their lifetime. Typically, these environments embed dedicated services such as code and documentation generators, checkers, editors, or debuggers.

Overall, the ingredients composing a language are manifold and usually complex to manipulate. Because there is no universally accepted way of implementing a language, it is difficult to directly relate languages created using different language workbenches. Moreover, the slightest variation in the syntax or semantics of a language leads to a conceptually new implementation, and all the artifacts referring to it (e.g. services) must be updated. Leveraging the concept of information hiding, the definition of explicit language interfaces on top of language implementations can help to abstract away from the change-prone implementation and switch the focus on a more stable and purpose-oriented view of languages. As we shall see in the next sections, such interfaces would ease the definition and reuse of services, the composition of languages, and the engineering of language families.

Easing the Definition and Reuse of Services

The development of services (e.g. code and documentation generators, static analyses) is an essential part of the development of software languages. Defining a new service requires to gather the appropriate information, which is often scattered in the various constituents of given language (abstract syntax, concrete syntax, semantics), in different formalisms. Naturally, the information to be extracted varies according to the purpose of the service. Some services, such as simple static analyses, only require access to a subset of the syntax specification of a language. More complex services may require to aggregate information from different sources. Additionally, services may be defined both at the language specification level (e.g. analysis of the completeness of a formal semantics specification), and at the instance level (e.g. dead code elimination for programs written in a particular language).

Rather than searching for the right information in the various constituents of a language, one can first design a language interface that aggregates the appropriate information in an easily manipulable form for a specific purpose. Using the appropriate interfaces eases the cognitive effort and abbreviates the definition of services. Moreover, since different languages can match the same interface, the services written on an interface can be applied to all matching languages.

One recent illustration in the programming community is the work of Brown et al, who use micro-grammars to ease the definition of static analysis tools for different programming languages [START_REF] Brown | How to build static checking systems using orders of magnitude less code[END_REF]. Micro-grammars are partial grammars that abstract over the full-blown specification of a language using wildcards. Wildcards are nonterminals used to ignore parts of a language implementation. The authors show that various languages (C++, Java, JavaScript, etc.) can match the same micro-grammars and that static analysis tools written on micro-grammars are easier to develop and can be reused or adapted to new languages with little effort.

The modeling community has also shown interest in such interfaces, as illustrated by the notions of model types [START_REF] Steel | On model typing[END_REF] and concepts [START_REF] Cuadrado | Generic model transformations: write once, reuse everywhere[END_REF]. Model types and concepts are both structural interfaces that specify a set of requirements over a metamodel -the standard way to define the abstract syntax of a language in the modeling community. A service, e.g. implemented as a model transformation, can be made generic by expressing its parameter in terms of a model type or concept, and any metamodel matching the model type or concept can benefit from this service. The duality of model types and concepts highlight the fact that there exist many ways to realize a given kind of interface. Model types are akin to subtype polymorphism while concepts are closer to parametric polymorphism but, overall, they are complementary and provide similar benefits. In addition, model types have also been used as unified interfaces that aggregate information from both the abstract syntax (the metamodel concepts) and the semantics (the transition steps of the operational semantics) of a language [START_REF] Degueule | Melange: A meta-language for modular and reusable development of dsls[END_REF]. Some generic services do not even require any information on the syntax or semantics of a language. A generic debugger, for instance, only requires the ability to start, pause, or inspect the execution of a model or program [START_REF] Bousse | Supporting efficient and advanced omniscient debugging for xdsmls[END_REF]. This common set of operations can be captured in a generic interface, and any language implementing it can benefit from debugging facilities.

Facing the Multiplication of DSLs

In the last decade, the development of Model-Driven Engineering (MDE) and the advances in language workbenches have strengthen the proliferation of domainspecific languages (DSLs). MDE advocates the use of DSLs to address each concern separately in the development of complex systems with appropriate abstractions and tools [START_REF] France | Model-driven development of complex software: A research roadmap[END_REF]. As a result, the development of modern software-intensive systems often involves the of multiple models expressed in different DSLs to capture different system aspects [START_REF] Combemale | Globalizing modeling languages[END_REF]. This trend is very similar to what was proposed by Ward in his early work on language-oriented programming [START_REF] Ward | Language-oriented programming[END_REF]. Even in traditional software development, multiple languages are often used to describe different aspects of the system of interest. Java projects, for instance, typically consist of Java source files, XML files describing the structure of modules and the deployment scenarios, Gradle build files expressed in Groovy, scripts, etc.

When multiple languages are used, the need for relating "sentences" that describe the same underlying system in different languages arises. In this context, models are seldom manipulated independently: checking a given property on a system, for instance, requires to gather information that is scattered in various models written by various stakeholders in various languages. In addition, the set of languages used to describe a given system is likely to change over time. A new, more expressive language can replace an existing one. New languages may be added, merged or split. While language workbenches support for engineering isolated languages is becoming more and more mature, there is still little support for relating concepts expressed in different DSLs together. The necessity of coordinated use of languages used in the development of a given system has recently been recognized [START_REF] Combemale | Globalizing modeling languages[END_REF][START_REF] Cheng | On the globalization of domain-specific languages[END_REF]. One promising approach is to leverage language interfaces to expose the appropriate information that allows to relate concepts from one language to the other [START_REF] Clark | Conceptual Model of the Globalization for Domain-Specific Languages[END_REF]. The type systems of two languages, for instance, may be related through the appropriate interface that would expose their respective type definitions to allow their integration. Overall, the challenges that must be tackled are very similar to the ones that were faced a few decades ago with the use of modules in software development.

The coordinated use of DSLs engineered with different language workbenches is even more challenging. Indeed, there is no abstraction mechanisms, at the language level, that allows to abstract from the concrete implementation techniques of a language workbench, e.g. a particular meta-language for defining the abstract syntax or a particular implementation technique for the semantics. The use of interfaces and connectors has been thoroughly studied in the context of component-based software engineering to alleviate the problem of technological space compatibility. Explicitly separating the implementation of a language from its interface can help to break the barriers between language workbenches if a common agreement on technology-agnostic interfaces is found.

Enabling Language Composition

Good practices from the component-based software engineering community can also be relevant in the context of software language engineering. The idea of building reusable and independently-validated language components to ease the definition of new languages has already been studied by several authors. A language component, such as a simple action language or a for-loop construct, can be defined and thoroughly validated independently and then reused as such in other languages that encompass the expression of actions or for-loops. In the same way languages are defined, the definition of such component encompasses both the definition of its abstract syntax, concrete syntax, and semantics. This leads to what is known as compositional language engineering: the ability to design new languages as assemblies of existing language components, thus lowering the development costs [START_REF] Krahn | Monticore: a framework for compositional development of domain specific languages[END_REF]. The actual realization of the composition may be done statically, i.e. the different modules are merged together to produce a new language specification with its associated implementation, or dynamically, i.e. the modules are kept separated but communicate to provide the composed behavior.

In this context, language interfaces serve as a support for the definition of provided and required interfaces of each component that are later used to reason about the composition of several language components and the correctness of the assembly. Interfaces are used to detect whether the constructs of different language components are in conflict, without having to dive into their intrinsic implementation. Language interfaces are also the concrete mean for several language components to communicate with each other at runtime. For instance, when two executable languages are composed together, their interpreter must also be coordinated. Language interfaces provide the appropriate information for relating together the two interpreters, for example through a delegation pattern.

Engineering Language Families

A language family is a set of languages that share meaningful commonalities but differ on some aspects. Finite-state machine languages, for instance, are all used to model some form of computation but expose syntactic variation points (e.g. nested states, orthogonal regions) and semantic variation points (e.g. inner or outer transition priority) [START_REF] Crane | Uml vs. classical vs. rhapsody statecharts: Not all models are created equal[END_REF]. Altogether, these different variants form a family of finite-state machine languages. Similarly, when a language evolves, the subsequent versions form a set of variants, which raises the question of backward and forward compatibility between them. Recently, different approaches have been proposed for automating the generation of such language variants based on earlier work from the software product line engineering community [START_REF] Cazzola | Choosy and picky: configuration of language product lines[END_REF][START_REF] Vacchi | Variability support in domain-specific language development[END_REF].

In the presence of a language family, language designers must be given the possibility to reuse as much as possible the environment and services (e.g. editors, generators, checkers) from one variant to the other. Naturally, the opportunities of reuse must be framed, as not all services are compatible with all variants. Language interfaces can be employed to reason about the commonalities of various language variants and the applicability of a given service or environment. Model types [START_REF] Steel | On model typing[END_REF], for instance, can be used to assign a type to a language and specify the safe substitutions between different artifacts based on typing relations. The definition of those types is precisely an example of language interface. Types abstract over the details of the implementation of different variants and are used to reason about substitutability between them. In this context, language interfaces can support the definition of common abstractions are shared by all or a subset of the members of a family, abstracting from the details that vary from one member of the family to the other.

Conclusion

The lack of abstraction in the manipulation of DSL implementations complexifies the definition of services (e.g. debuggers, generators, composition operators) and hampers their reuse. In this paper, we have reflected on the use of interfaces in programming and software engineering, and advocated the definition of interfaces at the language level for software language engineering. We have shown that various challenges of today's language development can be addressed through the use of language interfaces. The concept of language interface presented here is purposely abstract. We leave to future work the definition of concrete interfaces for specific purposes.


Medical discharge letters

The data are provided from the GHICL in the scope of the ClinMine ANR project. The goal is to cluster patient stays according to the evolution of the status of their discharge letters over the time. Clustering such type of data could help to improve the patient management by detecting some atypical clusters.

Definition of the states

The discharge could pass by 8 different states:

1. the doctor is dictating the letter. 2. the letter is "waiting" to be type-writing by an assistant 3. the letter is type-writing by the assistant 4. the letter is "waiting" for doctor validation 5. the letter is in validation process by the doctor 6. the letter is "waiting" to be affected to an assistant 7. the letter is treated by the assistant 8. the letter is sent to the patient (end).

Data description

Categorical functional data

The data

• n sample paths : x = {x 1 , x 2 , . . . x n }.

• The ith path:

x i = (s i0 , t i0 , s i1 , t i1 . . . , t i(d i -1) , s id i )
m the number of states d i = the number of jumps of the path i, t ij = the length of time spent in the j visited state of path i s ij = (s ijh , . . . , s ijm ) the binary coding of the j th state from the path i • It is supposed that the paths are uncensured, i.e. the paths are observed until they have reached the absorbing state.

Mixture of Markov processes

Likelihood: general form

• The n paths come from K different processes characterized by parameters θ k (k ∈ {1, . . . , K}).

• The likelihood function for the path i coming from cluster k is:

p(x i ; θ k ) = p(s i0 ; θ k )p(t i0 , s i1 |s i0 ; θ k ) d i -1 j=1 p(t ij , s i(j+1) |s ij , t i(j-1) , . . . , s i1 , t i0 , s i0 ; θ k )
Markovian assumptions H1: The distribution of (t ij , s i(j+1) ) is independent of the past given s ij p(t ij , s i(j+1) |s ij , t i(j-1) , . . . , s i1 , t i0 ,

s i0 ; θ k ) = p(t ij , s i(j+1) |s ij ; θ k ) H2:
The distributions of t ij and s i(j+1) are independent given

s ij p(t ij , s i(j+1) |s ij ; θ k ) = p(t ij |s ij ; θ k )p(s i(j+1) |s ij ; θ k )
H3: The distribution of s ij given e ij is an exponential distribution H4: The distribution of the initial state does not depends on the cluster

p(s i0 ; θ k ) = p(s i0 ) Then p(x i ; θ k ) = p(s i0 ) d i -1 j=0 p(t ij |s ij ; θ k ) time p(s i(j+1) |s ij ; θ k ) transition
Parameters of cluster k:

θ k = (α k , λ k ) Transition probability matrix α k • α khh ′ : the probability to move from state h to state h ′ , • α k = (α khh ′ ) 1≤h≤m-1,1≤h ′ ≤m Time distribution λ k • λ kh : parameter of the time distribution in state h, • λ k = (λ k1 , . . . , λ k(m-1) )
Parameters estimation and model choice

Parameters

The parameters to be estimated are the cluster specific parameters θ 1 , . . . , θ K and the prior weights π 1 , . . . , π K . θ = (π 1 , θ 1 , π 2 , θ 2 , . . . , π K , θ K )

Likelihood

The likelihood for the path i is modeled as a mixture

p(x i ; θ) = K k=1 π k p(x i ; θ k ).
The log-likelihood of the data x for the parameter θ is

ℓ(θ; x) = n i=1 log K k=1 π k p(x i ; θ k ) .

EM algorithm

The parameters are estimated by maximum likelihood using the EM algorithm.

The completed log-likelihood is:

ℓ(θ; x, z) = n i=1 K k=1 z ik log (π k p(x i ; θ k ))
where z ik equals 1 if the path i comes from the k th Markov process.

• E step:

t (r+1) ik = E[Z ik |x i ; θ (r) ] = P (Z ik = 1|x i ; θ (r) ) = π (r) k p(x i ; θ (r) k ) K k ′ =1 π (r) k ′ p(x i ; θ (r) k ′ ) . • M step: Let n (r+1) khh ′ = n i=1 d i -1 j=0 t (r+1) ik s ijh s i(j+1)h ′ n (r+1) kh = n i=1 d i -1 j=0 t (r+1) ik s ijh n (r+1) k = n i=1 t (r+1) ik
The update formulas are

π (r+1) k = n (r+1) k n α (r+1) khh ′ = n (r+1) khh ′ n (r+1) kh λ (r+1) kh = n (r+1) k n i=1 d i j=1 t (r+1) ik s ijh t ij .

Model choice

Since in practice the number of cluster is unknown the choice of the number of cluster can be simply performed by the BIC criterion

BIC(K) = ℓ( θ; x, K) - ν K 2 log(n).
where ν K is the number of free parameter of the model with K clusters.

Clustering of discharge letters

Results of the clustering in 2 clusters • The main difference between the clusters is the sojourn time distribution. The second cluster is characterized by long sojourn times. • The transition probabilities are roughly the same except for transition from state 1 to state 8.

Discussion

• Due to the very large number of data (n = 443 325), the model choice issue is difficult to solve since standard model choice criteria leading to large number of clusters making the interpretation difficult. • The large number of direct transitions from state 1 to state 8 in the data make the interpretation difficult from the practical point of view, further investigations on the data are in progress.

Conclusion and perspectives Conclusion

• Transition probabilities and sojourn times naturally taken into account • Model parameters easy to interpret

Perspectives

• A package R will be available soon including parsimonious models on transition probabilities and time distribution parameters • Adapt the model when the number of states is large (estimation of the transition matrix difficult) • Apply the model on other clinical data such as data on diabetes

  Clustering categorical functional data Application to medical discharge letters Vincent Vandewalle a,c & Cristian Preda b,c a Équipe d'Accueil 2694 (Université Lille 2) b Laboratoire Paul Painlevé (Université Lille 1 -CNRS) c Équipe MODAL (Inria Lille Nord Europe) Work conducted under the ClinMine ANR project

  Clustering {x 1 , x 2 , . . . x n }.

Acknowledgements

We would like to thank Doctor Arnaud Hansske from the GHICL, Julie Jacques, Julien Taillard and David Delerue from the alicante society for providing us the data.