Olivier Huber
email: olivier.huber@inria.fr

Vincent Acary
email: vincent.acary@inria.fr

Bernard Brogliato
email: bernard.brogliato@inria.fr

Franck Plestan
email: franck.plestan@irccyn.ec-nantes.fr

Discrete-time twisting controller without numerical chattering: analysis and experimental results with an implicit method

Keywords: twisting controller, sampled-data system, implicit discretization, electropneumatic actuator

In this note, we present an implementation of the twisting controller on an electropneumatic plant for a tracking control problem. Implicit and explicit discrete-time twisting controllers are considered, and some implementation details are provided. Experimental results are provided and analyzed. They sustain the theoretical superiority of the implicitly discretized version, as shown in previous work. The main advantages of the implicit method are better tracking and drastic reduction in the input and output chattering. This is achieved without modifying the controller structure compared to its continuoustime version.

I. INTRODUCTION

Implementation of control laws is almost exclusively done using microcontrollers. This implies that the controller is in discrete-time rather than in continuous-time. In sliding mode control, this can induce a degradation of the performance by contributing to the chattering phenomenon. We call this the numerical chattering. An intense activity over the last 30 years was devoted to the reduction of this numerical chattering, mainly for equivalent control based sliding mode control (ECB-SMC). In the early 90's, second order sliding mode control concept was introduced in [START_REF] Levant | Sliding order and sliding accuracy in sliding mode control[END_REF] and sparked the development of a large wealth of literature. One of the first controller of this kind was the twisting controller which features a discontinuous control action w.r.t the sliding variables. However to the best of our knowledge, few discrete-time versions of the twisting controller have been proposed. The replacement of the signum function by a saturation, common trick to reduce the chattering for first order SMC, has no straightforward extension to the twisting algorithm. It is then fair to assume that the explicit discretization was used to get a discrete-time twisting controller, like in [START_REF] Taleb | Pneumatic actuator control: Solution based on adaptive twisting and experimentation[END_REF].

One of the two discretization methods we consider here is the implicit method. It has been used for a long time in the nonsmooth mechanics community, but it was not applied in control theory until very recently [START_REF] Acary | Implicit Euler numerical scheme and chattering-free implementation of sliding mode systems[END_REF]- [START_REF] Huber | Analysis of explicit and implicit discrete-time equivalent-control based sliding mode controllers[END_REF]. In particular the implicit discretization of the twisting controller was first studied in [START_REF] Acary | Chattering-free digital slidingmode control with state observer and disturbance rejection[END_REF]. Roughly speaking, the difference between the explicit and implicit methods in our context is the following: given a partition {t k } of a time interval, with the explicit discretization, at the time instant t k , the argument of the signum function is the value of the sliding variable at t k , whereas with the implicit discretization it is the value at t k+1 . Despite its name and formulation, the implicitly discretized twisting controller is non-anticipative and induces a well-defined behaviour, as we shall see in Section II. Its main features are the drastic reduction of the output chattering and the reduction of the control input chattering, that is the control input is no more of the "bangbang" type. In the discrete-time sliding regime, the control input is also insensitive to an increase of the gain. To simplify the nomenclature, we refer to the discrete-time twisting controller with an implicit (resp. explicit) discretization as the implicit (resp. explicit) twisting controller.

In this note, we present results from an implementation of both explicit and implicit twisting controllers on an electropneumatic plant. The control problem at hand is the tracking of a sinusoidal trajectory for the position of the end of the piston. The analysis of the gathered data supports the theoretical reduction of the chattering [START_REF] Acary | Chattering-free digital slidingmode control with state observer and disturbance rejection[END_REF] and also the claim that the numerical chattering can be the main source of chattering [START_REF] Huber | Analysis of explicit and implicit discrete-time equivalent-control based sliding mode controllers[END_REF]. This highlights the importance of the discretization process which is unfortunately often overlooked.

In the remainder of this section, we introduce the notations. In Section II we briefly recall the twisting controller in continuous-time as well as in discrete-time. The experimental setup is presented in Section III as well as the control scheme. Then the experimental results are analyzed in Section IV.

Notations: The sliding variable is denoted by σ and is supposed to be at least twice differentiable. Let Σ := σ, σ

T . The control value changes at time instants t k , defined as t k := t 0 + kh for all k ∈ N with t 0 , h ∈ R + . The scalar h > 0 is called the sampling period. Let σ k := σ(t k ) and σk := σ(t k ) for all k ∈ N. The tilded variants σ, σ and Σ are used for variables internal to the controller. Let sgn be the classical single-valued signum function: for all x > 0, sgn(x) = 1, sgn(-x) = -1 and sgn(0) = 0. Definition 1 (Multivalued signum function). Let x ∈ R. The multivalued signum function Sgn : R ⇒ R is defined as:

Sgn(x) =      1 x > 0 -1 x < 0 [-1, 1] x = 0. If x ∈ R n ,
then the multivalued signum function Sgn : R n ⇒ R n is defined as: Sgn(x) := (Sgn(x 1 ), . . . , Sgn(x n ))

T .

II. THE TWISTING CONTROLLER

A. Continuous-time version

The twisting algorithm was one of the first second-order sliding mode controllers presented in the literature [START_REF] Levant | Sliding order and sliding accuracy in sliding mode control[END_REF]. It requires the control input u to be of relative degree 2 with respect to the sliding variable σ, that is

σ(x, t) = a(x, t) + b(x, t)u, (1)
with the following bounds: for all (x, t) ∈ R n × R + ,

0 ≤ K m ≤ |b(x, t)| ≤ K M and |a(x, t)| ≤ K a .
The control law for the twisting controller is

u ∈ -r 1 Sgn(σ) -r 2 Sgn( σ), (2)
and with the conditions

(r 1 + r 2 )K m -K a > (r 1 -r 2 )K M + K a (r 1 -r 2 )K m > K a , (3)
the closed-loop system (1) and ( 2) converges to the origin in finite time. Lyapunov functions for this controller have been recently investigated, see [START_REF] Orlov | Finite time stability and robust control synthesis of uncertain switched systems[END_REF], [START_REF] Polyakov | Lyapunov function design for finitetime convergence analysis: "twisting" controller for second-order sliding mode realization[END_REF].

It is worth noting that the controller (2) is by definition multivalued and that the control input is a selection of the closed-loop differential inclusion formed by ( 1) and (2).

B. Discrete-time version

The control input computed by a microcontroller is usually a step function, with a value periodically updated. We model the control input function as ū = ūk for t ∈ [t k , t k+1 ). When implementing this controller, the task at hand at each time instant t k is to compute the control input value from all the possible values defined by a discretization of (1) and [START_REF] Taleb | Pneumatic actuator control: Solution based on adaptive twisting and experimentation[END_REF]. We want to keep the multivalued feature of the controller. This is achieved by using the implicit discretization, which applied on [START_REF] Taleb | Pneumatic actuator control: Solution based on adaptive twisting and experimentation[END_REF] gives

u k ∈ -r 1 Sgn(σ k+1 ) -r 2 Sgn( σk+1 ),
whereas the explicit discretization yields

u k = -r 1 sgn(σ k ) -r 2 sgn( σk ). (4)
Note that the relation in ( 4) is not an inclusion since the right-hand side is given at time t k . The event where either σ k or σk is zero is clearly pathological. Hence the signum function is single-valued, contrarily to the continuous-time case. The computation of the control input value is in this case straightforward from equation ( 4). With the implicit discretization, a discrete-time version of the dynamics (1) is required to perform this computation. In the following, the discrete-time dynamics of Σ := (σ, σ) T is supposed to be affine, that is

Σ k+1 = A d k Σ k + F d k + B d k Λ. with Λ := (λ 1 , λ 2 ) and u k = -(r 1 , r 2 ), Λ , the dependency of Λ on k being hidden. At each time instant t k , Σ k = Σ(t k ) but Σ k+1 is in general not equal to Σ(t k+1
). If the dynamics ( 1) is LTI and exact, the discrete-time dynamics obtained using a ZOH discretization is exact and therefore Σ k+1 = Σ(t k+1 ).

The control input value u k is computed with the solution Λ of the following generalized equation

Σ k+1 = A d k Σ k + F d k + B d k Λ Λ ∈ -Sgn( Σ k+1 ), (5)
with unknowns Λ and Σ k+1 . Let us analyze this system using tools from convex analysis and variational inequalities. The equivalence Λ ∈ -

Sgn( Σ k+1 ) ⇐⇒ Σ k+1 ∈ -N [-1,1] 2 (Λ), with N [-1,1] 2 (Λ) the normal cone to the square [-1, 1] 2 = [-1, 1] × [-1
, 1] at the point Λ, enables us to transform (5) into the generalized equation

0 ∈ A d k Σ k + F d k + B d k Λ + N [-1,1] 2 (Λ).
More precisely, this inclusion is an equivalent form of an Affine Variational Inequality (AVI) [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]. Solving this AVI consists in finding

Λ ∈ [-1, 1] 2 such that for all w ∈ [-1, 1] 2 , (w -Λ) T L k (Λ) ≥ 0, (6)
with

L k : Λ → A d k Σ k + F d k + B d k Λ an affine map.
Let us present some properties of the solution of AVI [START_REF] Orlov | Finite time stability and robust control synthesis of uncertain switched systems[END_REF]. We use SOL(L k ) to denote the set of all solutions to the AVI (6).

Lemma 1. The AVI (6) has always a solution.

Proof. Since the mapping L k is continuous and [-1, 1] 2 is a bounded convex set, Corollary 2.2.5, p. 148 in [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF] gives the result.

The proposed controller is non-anticipative: a solution to the AVI [START_REF] Orlov | Finite time stability and robust control synthesis of uncertain switched systems[END_REF], with a positive semi-definite matrix B d k , can be computed using the algorithm proposed in [START_REF] Cao | A pivotal method for affine variational inequalities[END_REF] which is implemented in the SICONOS software package [START_REF] Acary | An introduction to SICONOS[END_REF] 1 . Since the AVI (6) has dimension 2, it is also possible to find the solution by enumeration, that is test the 9 possible cases for λ 1 and λ 2 and pick one that is satisfactory.

III. EXPERIMENTAL SETUP

A. Plant dynamics

Let us now present the physical system, actuators and sensors. The electropneumatic system of the IRCCyN lab (École Centrale de Nantes, France), depicted on Fig. 1, has two actuators. On the left-hand side, there is a double acting electropneumatic actuator (the "main" one) controlled by two servodistributors and composed of two chambers denoted P and N . The piston diameter is 80 mm and the rod diameter is 25 mm. With a source pressure equal to 7 bar, the maximum force developed by the actuator is 2720 N. The air mass flow rates entering the chambers are modulated by two three-way servodistributors. The pneumatic jack horizontally moves a load carriage of mass M . This carriage is coupled with the second electropneumatic actuator, the "perturbation" one, on Fig. 1: Scheme of the electropneumatic system the right-hand side. The goal of the latter is to impress a dynamic load force on the main actuator. This actuator has the same mechanical characteristics as the main one, but the air mass flow rate is modulated by a single five-way servodistributor.

Under some assumptions detailed in [START_REF] Shtessel | A novel adaptive-gain supertwisting sliding mode controller: Methodology and application[END_REF], the plant dynamics can be written as a nonlinear system affine in the control input [u P u N ] T , with u P (resp. u N ) the control input of the servo distributor connected to the P (resp. N ) chamber. The model is divided in two parts: the first two equations describe the pressure dynamics in each chamber and the motion of the piston is given by the last two equations. There is a single control objective: make the load position track a reference trajectory. Therefore we set u := u P = -u N , and the dynamics of the electropneumatic experimental setup is

ṗP = κrT V P (y) [ϕ P + ψ P u - S rT p P v] ṗN = κrT V N (y) [ϕ N -ψ N u + S rT p N v] v = 1 M [S (p P -p N ) -b v v -F ] ẏ = v, (7)
with p P (resp. p N ) the pressure in the P (resp. N ) chamber, y and v being the position and velocity of the load. The constant κ is the polytropic index, r the ideal gas constant, T the temperature (supposed the same inside and outside the chambers) and b v the viscous friction coefficient. The volumes in each chamber are V P and V N , both depending on the actuator position y. The constant piston section is S. The external force applied by the perturbation actuator is denoted by F . Finally, ϕ X and ψ X (X being P or N ) are both 5 th order polynomial functions versus p X [START_REF] Sesmat | Static characteristics of a three way electropneumatic servovalve[END_REF], that characterize the mass flow rate q X in the chamber X in the following way

q X = ϕ X (p X ) + ψ X (p X , sgn(u X ))u X .
The sources of uncertainty can be the polytropic index κ, the mass flow, the temperature T , the mass M , the viscous friction coefficient b v and the disturbance force F . They can be modeled by additive bounded functions added to the nominal part of each parameter. As an example, the mass M can be viewed as the sum of a nominal part and an uncertain one: M =: M n + ∆M, where ∆M is a bounded uncertainty and M n the nominal value. The control variable u is constrained to take values between -10 and 10.

B. Control strategy

The presence of uncertainties motivates the use of a sliding mode control scheme, well-known for its robustness. A first study was already conducted for equivalent-based sliding mode controller, with a comparison between explicit, implicit and saturation methods [START_REF] Wang | Experimental comparisons between implicit and explicit implementations of discrete-time sliding mode controllers: Towards chattering suppression in output and input signals[END_REF]. The experiments we present here were carried on with the discrete-time twisting controller presented in Section II. Since we are interested in a tracking problem for the position, we choose y as the output. The desired position of the piston is y d and the position error in the tracking problem is e := yy d . The choice of output leads to a relative degree 3. Therefore, to bring the relative degree between the sliding variable and the control input to 2, we define the sliding variable as σ := αe + ė.

Its first and second derivatives are

σ = α ė + ë and σ = αë + ... y - ... y d , where ... y = v = 1 M [S ( ṗP -ṗN ) -b v v -Ḟ ].
Using the relation in [START_REF] Polyakov | Lyapunov function design for finitetime convergence analysis: "twisting" controller for second-order sliding mode realization[END_REF], we get ...

y = SκrT M ϕ P V P - ϕ N V N - S 2 κ M (p P -p N ) v + b v M 2 (S(p P -p N ) -b v v -F ) - Ḟ M + SκrT M ψ P V P - ψ N V N u. (8)
Let us define the following functions

Φ := SκrT M ϕ P V P - ϕ N V N - S 2 κ M (p P -p N ) v + b v M 2 (S(p P -p N ) -b v v) + αë - ... y d and
Ψ := SκrT M ψ P V P - ψ N V N ,
which are the nominal functions associated with the dynamics of the sliding variable

σ = Φ + ∆Φ + (Ψ + ∆Ψ)u.
The terms ∆Φ and ∆Ψ are here to take into account uncertainties, like those introduced by the perturbation actuator: F and Ḟ in [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]. The variables p P , p N and y are measured. The implicit controller is constructed in the following way: the control input is discretized using the implicit discretization, that is

u k ∈ -G(Sgn(σ k+1 ) + β Sgn( σk+1 )). (9)
The dynamics of the sliding variable is discretized as follows: expressing the sliding variable dynamics as a first-order ODE, we get

Σ = AΣ + F + Bu, (10)
with Σ = σ σ , A = 0 1 0 0 , B = 0 0 GΨ βGΨ and F = 0 Φ . We discretize Φ and Ψ using the explicit Euler scheme: we consider that

Φ(t) = Φ k := Φ(t k ) and Ψ(t) = Ψ k := Ψ(t k ) for t ∈ [t k , t k+1 ).
For the last step in the discretization of [START_REF] Acary | An introduction to SICONOS[END_REF], we use the ZOH method, which yields

Σ k+1 = A * Σ k + F * k + B * k Λ, (11)
with

A * := e Ah = 1 h 0 1 , B k := 0 0 GΨ k βGΨ k and B * k := t k+1 t k e Aτ B k dτ = h 2 GΨ k /2 βh 2 GΨ k /2 hGΨ k βhGΨ k , F k := 0 Φ k and F * k := t k+1 t k e Aτ F k dτ = h 2 Φ k /2 hΦ k
. We combine ( 9) and ( 11) to get

σ k+1 = σ k + h σk + h 2 2 Φ k + h 2 2 GΨ k [λ 1 + βλ 2 ] (12) σk+1 = σk + hΦ k + hGΨ k [λ 1 + βλ 2 ] λ 1 ∈ -Sgn( σ k+1 ) λ 2 ∈ -Sgn( σk+1 ).
The position y is available but both the speed v and acceleration are computed using a filtered differentiator of the form

D(s) = s 1 + τ s
in the frequency domain.

IV. EXPERIMENTAL RESULTS

This section is devoted to the analysis of the experimental results obtained on the electropneumatic setup. Recall that the control objective is to make the position of the piston track a sinusoidal trajectory. In the following, the desired trajectory is y d := A mpl sin(0.2πt).

The controller was implemented as a Simulink model and then transfered onto a DS1005 dSpace board. We were able to get results with the sampling period h in the range [START_REF] Acary | Implicit Euler numerical scheme and chattering-free implementation of sliding mode systems[END_REF]100]ms and with the gain G in the range [10 -2 , 10 7 ]. The sliding surface parameter α and the two filtered differentiator time constants require proper tuning for each sampling period. They can drastically alter the performances of the control. Since it appears that both have to be tuned together, preliminary values were obtained using simulations, with a selection based on the average error or precision, and were later tuned on the plant.

We now present results for two criteria: the tracking accuracy and the chattering magnitude on both the input and the output. In each case, we first compare the explicit and implicit methods, before analyzing in more depth the performances of the implicit method.

A. Tracking accuracy

The tracking error e = yy d is the quantity we minimize through the twisting controller. Due to the high relative degree of the system, the controller does not bring e to 0 in finite time, but rather σ = αe + ė. Once the sliding phase occurs, the convergence of e to 0 is then exponentially fast if α > 0. The latter parameter controls the speed of convergence: the bigger α is, the faster the error decreases.

To measure the accuracy of the tracking, we compute the average of the absolute value of the error over an interval of 60s. We call this quantity the precision and we denote it ē. Its analytical formula is

ē := N k=1 |e(t k )| N with t N -t 1 = 60s.
On Fig. 2, the precision with both the implicit and explicit controllers is displayed for different sampling periods. The implicitly discretized controller clearly yields a better performance than the explicit one, and this for each sampling period where the comparison is possible. Indeed it was not possible to get reliable data for large sampling periods with the explicit controller, since the plant was becoming unstable. The precision appears to increase linearly with h, or in other word it is in O(h). This is underscored by the linear regression plotted in Fig. 2. This may be of surprise since we use a second-order sliding mode controller and the order should be O(h 2 ). However, recall that σ = αe + ė, with the derivative being computed by a simple filtered differentiator. Hence in [START_REF] Sesmat | Static characteristics of a three way electropneumatic servovalve[END_REF], the term σ k is known with a precision only in O(h). This problem may be alleviated by the use of another differentiator, like the one proposed in [START_REF] Levant | Robust exact differentiation via sliding mode technique[END_REF].

Let us show more details for a specific sampling period: h = 10ms. On Fig. 3a and3b, the real and desired trajectories are depicted with, respectively, an implicit (or explicit) controller. On Fig. 3a, the tracking is very accurate: the two curves are undistinguishable. On the other hand, on Fig. 3b, the chattering of the real trajectory is visible in the Although the control is affected by the noise from the measurements, there is an underlining periodical signal, which is also witnessed on simulation results. The root cause is likely to be the approximations done to get the discrete-time model in [START_REF] Shtessel | A novel adaptive-gain supertwisting sliding mode controller: Methodology and application[END_REF]. It is difficult to analyze the data on Fig. 4b since the control input is switching at a very high frequency between the 2 extremal values -10 and 10, sign of a chattering input. It is pretty clear that the main source of chattering is the explicit discretization of the controller. We analyze further the chattering in the second part of this section.

Having exposed the superiority of the implicit discretization with respect to the explicit one, let us further present the good performances that it yields. Firstly it is possible to increase the sampling period while keeping a good tracking and a practically stable system. Fig. 5 illustrates this fact: even with a sampling period of 100ms, the tracking takes place, although with degraded performances compared to the one in Fig. 3a. However the precision is still better than with an explicit controller with a sampling period one order of magnitude smaller as shown in Fig. 2 and 3b. Another very nice feature of the implicit discretization is the fact that the control input value is computed as a selection, as mentioned earlier. One implication is that to be robust, the gain needs to be large enough with respect to the perturbation (see ( 3)) but a further increase in the gain does not harm the performances. This is illustrated by Fig. 6, where the precision ē is plotted versus the gain G for 3 sampling periods. For each value of the latter, we changed the gain from 10 -2 to 10 7 , each time multiplied by 10. In each case, the precision varies only by less than 5%, with is solely due to the noise in the plant. The random evolution, with respect to the gain, in Fig. 6 further supports this claim. The insensitivity of the discontinuous controller w.r.t. the gain variations, has also been verified for the ECB-SMC controller in [START_REF] Wang | Experimental comparisons between implicit and explicit implementations of discrete-time sliding mode controllers: Towards chattering suppression in output and input signals[END_REF]. Let us switch focus on the chattering in the rest of the section.

B. Input and output chattering

We propose to characterize the chattering of a variable by the variation of the associated signal. The variation of a real-valued function f (•) is defined as

Var T t0 (f ) := k |f (t k ) -f (t k-1 )|,
with k ∈ N * such that t k ∈ (t 0 , T ]. Though this quantity is not commonly used in Control Engineering, it provides a nice characterization of the chattering on either the control input or the sliding variable. We pay attention to both input and output chattering, since the first one contributes to the second and it can also induce rapid wear of actuators, especially if they are mechanical ones. Furthermore, it may also be linked to the energy consumption of the actuator. As before, we present the evolution of the control input chattering with respect to the sampling period for both implicit and explicit controllers. From Fig. 7, we can infer that the trend in both cases is a decrease of the variation with an increase in the sampling period. Again the implicit controller performs much better, having a control input variation 2 orders of magnitude smaller than the explicit one. This reduced chattering can also be assessed on site with a huge reduction of the noise made by the actuators2 . Moving on to the output chattering, the same conclusion follows: the implicit method performs better than the explicit one, this time by an order of magnitude (see Fig. 8). This means that the output chattering is notably reduced. Indeed a bang-bang type control input, like the one the explicit discretization yields, tends to change the sign of the sliding

Fig. 2 :

 2 Fig. 2: Evolution of the precision ē with respect to the sampling time for both implicit and explicit discretizations. The gain used in every capture was G = 10 5 .

  With an implicit discretization.

  With an explicit discretization.

Fig. 3 :

 3 Fig. 3: Real and desired position trajectories with h = 10ms and G = 10 5 .

  With an explicit discretization.

Fig. 4 :

 4 Fig. 4: Evolution of the control input u for both implicit and explicit discretization with h = 10ms and G = 10 5 .Fig.4aand 4b illustrate the evolution of this quantity in the implicit and explicit cases. In the first case, the control values are in the range [-3, 3.3], which is well inside the constraints u ∈ [-10, 10]. Although the control is affected by the noise from the measurements, there is an underlining periodical signal, which is also witnessed on simulation results. The root cause is likely to be the approximations done to get the discrete-time model in[START_REF] Shtessel | A novel adaptive-gain supertwisting sliding mode controller: Methodology and application[END_REF]. It is difficult to analyze the data on Fig.4bsince the control input is switching at a very high

Fig. 5 :

 5 Fig. 5: Real and desired positions with an implicit discretization, h = 100ms and G = 10 5 .

Fig. 6 :

 6 Fig. 6: Precision versus gain (G in (9)).

Fig. 7 :

 7 Fig. 7: Evolution of the control input variation with respect to the sampling time for both implicit and explicit discretizations. The gain used in every capture was G = 10 5 .

Fig. 8 :

 8 Fig.8: Evolution of the error variation with respect to the sampling time for both implicit and explicit discretizations. The gain used in every capture was G = 10 5 .

  10 -2 10 -1 10 0 10 1 10 2 10 3 10 4 10 5 10 6 10 7

		0.44
		0.42
		0.40
	Precision	0.32 0.34 0.36 0.38	h = 25ms h = 10ms h = 5ms
		0.30
		0.28
		0.26
		Gain

The reader is invited to watch the videos at http://bipop. inrialpes.fr/people/huber/ variable very frequently. This leads to a large variation of the error, with respect to the variation with an implicit controller. At the same time, this behaviour does not yield a better tracking, as illustrated by Fig.2.V. CONCLUSIONIn this note we present the results of an experimental study of two discrete-time twisting controllers: the implicit and the explicit one. Extensive experiments were conducted in the context of a position tracking problem. The analysis of the data reveals that on this electropneumatic setup, the implicit twisting controller outperforms the explicit one on

criteria: the tracking error and both the input and output chattering. Despite the complexity of the control loop arising from the high relative degree, meaningful illustrations of theoretical results are provided, like the insensitivity with respect to an increase in the gain, once the latter is large enough. The implicit discretization allows to drastically reduce both the output and the input chattering, without modifying the controller structure compared to its continuous-time version. Video recordings of the experiments can be found online 2 .

ANR grant CHASLIM (ANR-11-BS03-0007).


Stefan Marr
email: stefan.marr@inria.fr

Tobias Pape
email: tobias.pape@hpi.uni-potsdam.de

Wolfgang De Meuter

Are We There Yet? Simple Language-Implementation Techniques for the 21 st Century

Keywords: Language Implementation, Virtual Machines, Compilers, Interpreters. !

With the rise of domain-specific languages (DSLs), research in language implementation techniques regains importance. While DSLs can help to manage the domain's complexity, it is rarely affordable to build highly optimizing compilers or virtual machines, and thus, performance remains an issue. Ideally, one would implement a simple interpreter and still reach acceptable performance levels. RPython and Truffle are two approaches that promise to facilitate language implementation based on simple interpreters, while reaching performance of the same order of magnitude as highly optimizing virtual machines. In this case study, we compare the two approaches to identify commonalities, weaknesses, and areas for further research to improve their utility for language implementations.

INTRODUCTION

P ROGRAMMING language implementation has been a major field of research since the beginning of computer science. Over the years, many advances were made leading to highly optimizing compilers and dynamic just-in-time (JIT) compilation techniques [START_REF] Aycock | A Brief History of Just-In-Time[END_REF] allowing for efficient implementation of a wide range of programming languages. However, the implementation of compilers as well as JIT compiling virtual machines (VMs) require significant engineering effort, which often goes well beyond what is feasible for instance for domainspecific languages (DSLs). Thus, interpreters remain a simple alternative for the implementation of programming languages. Interpreters typically reflect directly the desired execution semantics and hence retain a close relation between the language and its execution. This makes them ideal for evolving languages, design experiments, and DSLs. The downside of interpreters however was so far that they are several orders of magnitude slower than highly optimizing VMs or compilers.

In this paper, we investigate language implementation techniques that enable the use of interpreters, while at the same time yielding performance that is supposed to reach the same order of magnitude as compilers and JIT compiling VMs. Specifically, we study RPython [START_REF] Bolz | Tracing the Meta-level: PyPy's Tracing JIT Compiler[END_REF], which is know as the implementation platform for PyPy, a fast Python implementation, as well as Truffle [START_REF] Würthinger | Self-Optimizing AST Interpreters[END_REF], which is a new language implementation framework for the JVM that also aims to enable efficient language implementations.

S O M: SIMPLE OBJECT MACHINE

As running example and case study for this paper, we use SOM (Simple Object Machine) [START_REF] Haupt | The SOM Family: Virtual Machines for Teaching and Research[END_REF], a simple Smalltalk [START_REF] Goldberg | Smalltalk-80: The Language and its Implementation[END_REF]. SOM is designed for teaching language implementation and VM techniques. Therefore, it is kept simple and includes only a small set of fundamental language concepts such as objects, classes, closures, primitives, and non-local returns. The following listing illustrates the SOM syntax: Here, the two classes Boolean and True are sketched. Line 1 defines the class Boolean as a subclass of Object. In Smalltalk, control structures such as if or while are defined as polymorphic methods on objects and rely on mechanisms such as closures and non-local returns. Thus, Boolean defines the method #ifTrue:ifFalse: on line 2, which takes two blocks, i. e., closures, as arguments. When this message is sent to a boolean, line 3 is executed and will evaluate the trueBlock parameter by sending the message #value. The caret (^) is Smalltalk's return symbol, and causes a non-local return in this case. This means, if the boolean is an instance of the class True, the trueBlock is evaluated and the result is returned to the caller of #ifTrue:ifFalse:. Without the notion of nonlocal returns, execution would not return from #ifTrue:ifFalse: and line 4 would be executed as well.

IMPLEMENTING INTERPRETERS

Interpreters are commonly implemented using one of two approaches. The simpler is based on abstract syntax trees (ASTs) generated by a parser. The other approach uses a linearized program representation, typically referred to as bytecodes. For illustration of the difference between the two approaches, the following SOM listing shows a recursive factorial function.

factorial: n = ( ^n = 0 ifTrue: [START_REF] Aycock | A Brief History of Just-In-Time[END_REF] ifFalse: [n * (self factorial: n -1)])

The comparison n = 0 results in a boolean object, which receives the message #ifTrue:ifFalse:. In case n is 0, the #factorial: method will return the value of the first block, i. e., 1. Otherwise, it evaluate the second block, which recursively computes the factorial for n.

AST Interpreters

The SOM parser compiles the example code to an AST similar to fig. 1, where each AST node is annotated with its type. An AST interpreter then implements for each node type the corresponding actions as sketched in the following listing: Note, we use Python pseudo-code to distinguish between the language implemented and its implementation language. The IntegerLiteral class illustrates how literals such as the integer 1 are handled. Since their value is known at compilation time, the execute method of IntegerLiteral just returns this stored value. In contrast, the BinaryMessageSend has two subexpressions, the receiver and the argument, that have to be evaluated first. Thus, execute first calls the execute methods on the subexpressions. Then, it retrieves the receiver's class and looks up the Smalltalk method that corresponds to the selector defined in the AST.

In the factorial example, the arithmetic operations, the comparison, as well as #factorial: itself are such binary message sends.

While it is straightforward to build interpreters this way, the overhead of the dynamic dispatch for methods such as execute and the memory access patterns of the tree traversal cause performance issues. As a consequence, bytecode interpreters are advocated as the favorable alternative. For example, Ruby as well as WebKit JavaScript switched in 2007/2008 from AST-based to bytecode-based interpreters and gained better performance.

Bytecode Interpreters

For bytecode interpreters, the AST is first linearized to represent the program as a sequence of instructions, typically called bytecode. This bytecode is executed by a stack-or register-based machine, which includes operations such as push, pop, move, invoke method, and jump. Often additional instructions for common program patterns are included to reduce the interpreter overhead. Examples include the VMs for Smalltalk-80 as well as Java.

For SOM, the bytecode set for a stack-based interpreter has 16 bytecodes. Compiling the factorial example from section 2 to this bytecode yields the following:

push_argument 1 push_constant Integer(0) send #= push_block Block([1]) push_block Block([n * self factorial...]) send #ifTrue:ifFalse: return_local
While the AST interpreter evaluates subexpressions of a node directly, the bytecode interpreter uses a stack to communicate intermediate values. Thus, to invoke the #= method, the interpreter first pushes the argument n and then the integer constant 0 on the stack. The #= method consumes these arguments and pushes a boolean as result onto the stack. Such an interpreter could look like this pseudo-code: Basic bytecode interpreters use simple dispatch loops like these switch/case statements to implement the bytecode dispatch. First, it fetches the next bytecode from the method that is currently executed, including a possible argument to the bytecode. Then, it jumps to the corresponding bytecode implementation, which either pushes an argument to the message send onto the stack, pushes a constant encoded in the method, or performs a send.

As mentioned earlier, bytecode interpreters are more complex than AST interpreters. One reason is the explicit execution stack that requires the implementer to carefully track the stack balance, e. g., for method calls. However, this complexity seems to be accepted to reap the performance benefits.

Research on optimizations ignored AST interpreters for a long time [START_REF] Hondt | Are Bytecodes an Atavism?[END_REF] and only recently, with Truffle [START_REF] Würthinger | Self-Optimizing AST Interpreters[END_REF] reconsidered them actively. However, for bytecode interpreters, a number of optimizations have been developed. Examples are threaded interpretation [START_REF] Bell | Threaded code[END_REF] to reduce the bytecode dispatch overhead as well as superinstructions [START_REF] Casey | Optimizing Indirect Branch Prediction Accuracy in Virtual Machine Interpreters[END_REF] and quickening [START_REF] Casey | Optimizing Indirect Branch Prediction Accuracy in Virtual Machine Interpreters[END_REF][START_REF] Brunthaler | Efficient Interpretation Using Quickening[END_REF] to optimize the bytecode sets for better performance. These are only few examples, however, even when applied consequently, interpreters exhibit much lower performance than optimizing VMs with JIT compilers. RPython as well as Truffle promise to provide such optimizing VMs when provided with bytecode or AST interpreters.

RPYTHON: META-TRACING JITS

In order to make language implementation simpler, the RPython toolchain [START_REF] Bolz | Tracing the Meta-level: PyPy's Tracing JIT Compiler[END_REF] takes simple interpreters implemented in a high-level language and generates efficient VMs for them. For performance, it builds upon the notion of tracing JIT compilers [START_REF] Gal | Hot-pathVM: An Effective JIT Compiler for Resource-constrained Devices[END_REF]. Specific to RPython's approach is the use of meta tracing, i. e., an implementation of SOM does not trace the execution of a SOM program directly but rather the execution of the SOM interpreter. In addition to meta tracing, the RPython toolchain provides low-level services such as memory management and object layout. These services are added to the interpreter in several transformation steps that eventually generate C code for the final VM. The RPython language is a restricted subset of Python with a type system that enables the analysis and transformation steps of the interpreter into a VM with a meta-tracing JIT.

RPySOM: A Tracing JIT for SOM

The RPython-based SOM implementation, named RPySOM, is the bytecode interpreter sketched in section 3.2. To enable the meta-tracing JIT compiler, the bytecode loop needs to be annotated, as the tracing JIT has to be able to recognize the loop based on interpreter state. Thus, the interpreter loop needs to be changed slightly:

def Interpreter.interpret(self, method, frame): bc_idx = 0 while True: bc, arg = method.get_bytecode(bc_idx) jit.jit_merge_point(bc_idx=bc_idx, interp=self, method=method) switch bc: case push_argument: #...

The jit_merge_point tells the VM that a loop occurred when the execution has reached a point where the bytecode index (bc_idx), method, and interpreter instance are the same objects as they have been at a previous point. When such a loop has been executed often enough, the VM starts to record a trace that is optimized subsequently to remove unnecessary operations such as temporary allocations and repeated side-effect-free function execution. Since the trace records all operations and disregards function boundaries, reordering of operations and removal of redundant operations should yield theoretically peak performance for a specific execution trace.

Since the optimizer has to make conservative assumptions even for such concrete traces, it is necessary to make certain properties explicit with annotations. For instance, functions can have sideeffects that are not essential for the execution, e. g., for caching values. With RPython's @elidable annotation, the optimizer can be told that it is safe to elide repeated executions from a trace, because it is guaranteed that the function produces for the same input always the same return values. RPySOM uses it, e. g., for the lookup for globals, which use a dictionary that is normally not guaranteed to remain unchanged. Another chance for optimization comes from values that remain constant within the context of a trace, but where the optimizer cannot proof it. In these cases the value can be marked with the promote function. In RPySOM, the stack pointer is such a value that is constant within the specific context of a trace. A more in-depth discussion of these optimizations is provided by Bolz and Tratt [START_REF] Bolz | The Impact of Meta-Tracing on VM Design and Implementation[END_REF].

Necessary Optimizations

To generate useful traces for JIT compilation. the tracer needs to be able to identify hot loops. This turned out to be a challenge for SOM. Smalltalk with its unified design and minimal set of concepts does not match very well with RPython's heuristics. One of the main issues is the way SOM implements loops. Originally, it used a primitive, i. e., a built-in function of the SOM interpreter, which resets the bytecode index of the loop frame to start over with the execution of the loop body. For the tracer, this approach makes it harder to detect loops.

Initially, the complete reification of the execution stack in the interpreter also puts extra burden on the optimizer because data dependencies become ambiguous.

To address the loop detection and to make data dependencies explicit, we made RPySOM a recursive interpreter. Originally, the interpret method of Interpreter was activated only once. In the recursive version, every SOM method invocation leads to an additional invocation of interpret. The relevant execution state like the frame object, the current method, and current bytecode index is thus kept in the interpret method. This makes data dependencies more explicit for the optimizer by decoupling logically independent copies of the variables.

Consequently, the implementation of non-local returns and loops changed. Non-local returns were implemented by walking the chain of frame objects and setting the corresponding fields in the interpreter object, which made it hard for the optimizer to determine independent changes. In the recursive interpreter, non-local returns use exceptions to walk the RPython stack of recursive interpret invocations. The SOM loop implementation changed from a primitive manipulating the bytecode index to explicit looping primitives for the #whileTrue: and #whileFalse: message. These two implement the loops by using RPython's while loop, which has the additional benefit that relevant trace merge points can be indicated to RPython using the jit_merge_point annotation.

TRUFFLE: SELF-OPTIMIZING AST INTER-

PRETERS

Truffle is a Java-based framework to implement efficient AST interpreters [START_REF] Würthinger | Self-Optimizing AST Interpreters[END_REF]. Based on the execution paths taken and the types observed, Truffle dynamically specializes the AST. In combination with a speculative optimizing compiler that uses partial evaluation, these ASTs are then JIT compiled to reach the performance of custom-built VMs [START_REF] Würthinger | One VM to Rule Them All[END_REF]. The framework builds on top of a standard JVM and therefore benefits from its services, e. g., garbage collectors, native code optimizers, support for threads, or memory model. In contrast to RPython's approach, the language implementer has to explicitly provide the AST specializations, and thus, the main mechanism for performance is in the hand of the developer instead of being a black-box provided by a toolchain.

TruffleSOM: A Self-Optimizing SOM

TruffleSOM is based on the AST interpreter outlined in section 3.1 using the Truffle framework. To reduce the execution overhead, we follow the general guideline for Truffle, i. e., to identify costly operations on the execution's fast path that can be performed optimistically only once as an initialization step. This allows later executions to rely on, e. g., a cached value and a guard that verifies the assumptions. In TruffleSOM, method lookup is one such optimization point, not only because of the avoided overhead of the lookup, but also because it enables later method inlining for context-specific specialization. The message send first evaluates its arguments. Thus, it determines the receiver as well as the operand. During the first execution of this AST node, the variable n contains an integer and, consequently, the variable read node can be specialized for reading integers. This is beneficial to avoid boxing [START_REF] Würthinger | Self-Optimizing AST Interpreters[END_REF]. The message send node can then be specialized based on the receiver's class, i. e., Integer in this case. Thus, the uninitialized message send node is replaced by a cached send node, which keeps the value of the lookup, i. e., the comparison method defined in Integer. As a guard, the cached send node has a special class check node as its child. This node is a specialized version of a class check and performs only a Java instanceof test on the receiver to determine whether the send can be performed. In the best case, this assumption holds and the cached comparison method can be invoked directly. In case the class check fails, execution is handed over to an uninitialized send node, which performs the method lookup and then specializes itself.

This caching strategy has a wide applicability for instance for the lookups of globals, which are a pair of key and value. The pair can be cached in a specialized node, which allows the optimizer to treat it as a constant. Compared to RPython, this technique is similar to the use of promote() and @elidable, but requires node specialization instead of being simple annotations.

Another example for specializations necessary to reach peak performance is the handling of non-local returns. In a naive implementation, each method handles non-local returns as follows: However, only few methods contain non-local returns, but the setup for handling them has a severe performance impact. Thus, TruffleSOM splits this handling into a CatchNonLocalReturn node and generates it only for methods that need it.

Building Specializations

While the optimization of a Truffle interpreter is left to the language implementer, Truffle's approach to it feels very natural. The tree structure facilitates optimizations such as special handling for Smalltalk loop message sends, or control structures, because it fits better with the semantics of these and other constructs than the linearized bytecode format in RPySOM. Taking the example of #ifTrue:ifFalse:, in TruffleSOM it is specialized when the receiver is a boolean and the arguments are blocks. The specialized node then performs a simple identity check on the receiver and evaluates the corresponding block. Compared to the library solution, this reduces the number of method and block activations significantly. In RPySOM, we had to introduce jump bytecodes, change the parser to generate them, and implement them in the interpreter. Thus, the changes were neither as localized nor as straightforward.

Another important part of the framework is TruffleDSL, a set of annotations, that facilitates the specification of node specializations. For instance, in dynamic languages such as Smalltalk, an addition operation has to account for the various possible combinations of input types to implement the desired semantics. Since Truffle requires that each of these specializations are node objects, the language implementer would need to implement for each case a separated class. However, with TruffleDSL such classes are generated automatically. So that the language implementer only needs to define one method for each specialization and annotate it with the conditions that need to hold to apply the specialization.

PERFORMANCE EVALUATION

To assess whether RPySOM and TruffleSOM reach performance of the same order of magnitude as optimizing JIT compiling VMs, we compare them to Oracle's HotSpot JVM and PyPy. We chose DeltaBlue and Richards as two object-oriented benchmarks, which are used to tune JVM's, JavaScript VMs, PyPy, and Smalltalk VMs, as well as Mandelbrot as a numerical benchmark. Note, as with all benchmarks, the results are only indicative, but not predictive for the performance of actual applications.

Table 1 lists the results, indicating the absolute runtime in milliseconds, as well as the standard deviation. Furthermore, it lists the result normalized to Java, which means higher factors are slower. The benchmarks measure stable-state performance. Each benchmark was executed 100 times. The used machine has two quad-core Intel Xeons E5520, 2.26 GHz with 8 GB of memory and runs Ubuntu Linux with kernel 3.11. A full overview of the results and notes on their reproduction are available online. 1 As a further reference point, we include the SOM++ interpreter, a SOM implemented in C++. It uses bytecodes and applies optimizations such as inline caching, threaded interpretation, and a generational garbage collector. However, it is 70 to 700× slower than Java. RPySOM and TruffleSOM on the other hand, reach more or less the same order of magnitude of performance. RPySOM reaches 1.7 to 10.6×, while TruffleSOM has more remaining optimization potential with being 1.4 to 16× slower. Nonetheless, both implementations manage to reach, depending on the benchmark, the same order of magnitude of performance as Java, without requiring custom VMs and hundreds of person years of engineering. Thus, we conclude, that RPython as well as Truffle live up to the expectations.

1. Appendix Performance Evaluation: http://stefan-marr.de/ papers/ieee-soft-marr-et-al-appendix-performance-evaluation For brevity, we omit a comparison based on microbenchmarks. However, TruffleSOM outperforms RPySOM on two out of three of the larger benchmarks and all but one of the microbenchmarks. Thus, we assume further specializations will allow TruffleSOM to reach the same performance level on the Richards benchmark as well.

CONSEQUENCES FOR LANGUAGE IMPLE-

MENTATIONS

RPython as well as Truffle overall deliver on their promise of providing a fast VM based on simple interpreter implementations, but with different tradeoffs. The initial performance gains provided by RPython's meta-tracing can be more compelling, especially when engineering resources are constraint. However, Truffle's approach might be more beneficial in long-run when the black-box approach of meta-tracing fails and the flexibility of custom specializations is required. Performance aside, the Truffle framework initially guides the interpreter implementation sufficiently to quickly prototype ideas with low engineering effort, and thus, is a suitable platform for experiments as well.

To gain performance, both approaches turn out to be similar. They both rely on complex compiler technology combined either with tracing or partial evaluation. As a consequence, performance benefits significantly in both cases when data dependencies are made explicit, which often leads to a programming style that avoids unnecessary side effects. To further make certain properties explicit for the optimizer, they also provide roughly the same set of annotations.

Furthermore, both approaches steer a language implementer to avoid exposing implementation decisions to the language level. In a dynamic language such as Smalltalk, both approaches encourage to expose the dynamisms in a controlled manner only. For instance, it is easier to provide access to information such as the class of an object via a primitive than to expose it via an object field that is treated differently than other object fields. In both cases, the framework needs to be notified that the class structure has changed to invalidate compiled code.

ARE WE THERE YET?

The general impression of RPython's meta-tracing approach and Truffle's self-optimizing interpreters is that both have the potential to change the way languages are implemented. They enable language implementations with low effort and good performance characteristics. Especially, in the field of DSL where the language implementations need to be maintainable and as flexible as the domain it requires, the engineering benefits of both approaches over classic compiler and VM implementations are significant. They free the language implementer from low-level concerns such as memory management, native code generation, and other typical VM services, and thus, require overall significantly less engineering than classic approaches.

Interestingly, neither of them provides advanced support for one of the main issues of today: concurrency and parallelism. Truffle allows the use of the JVM's capabilities, and RPython experiments with software transactional memory. Still, neither provides building blocks to language designers that can facilitate the implementation of DSLs for concurrent and parallel programming, even thought, programmers in this field could benefit from highly efficient DSL implementations to tackle the complexity of concurrency. Furthermore, both approaches could benefit from each other. The initial performance advantage of the meta-tracing approach can be a benefit, especially for DSLs developed for narrow use case. A combination with the self-optimizing approach of Truffle might then provide benefits for long-term project to expose more optimization potential and reach the maximum possible performance, without having to rely solely on the black-box meta tracing.

For the future of programming languages and their implementation, RPython and Truffle both make valuable contributions. Combined with language design and implementation environments such as language workbenches, they can dramatically change the way languages are implemented in the future. Moreover, their optimization potential might reduce the cost of language features such as metaprogramming, which can have a positive impact on programmer productivity. That way, they could also widen the set of acceptable programming techniques in performance sensitive fields.

1 Boolean = Object ( 2 ifTrue

 12 : trueBlock ifFalse: falseBlock = ( 3 self ifTrue: [ ^trueBlock value ].

4

  self ifFalse: [ ^falseBlock value ].

5

 5

8 9

 8 True = Boolean ( 10 ifTrue: block = ( ^block value ) 11 ifFalse: block = ( ^nil ) 12 "..." 13 )

Fig. 1 .

 1 Fig.1. Abstract syntax tree for the factorial function

Fig. 2 .Figure 2

 22 Fig. 2. Specialization of a Message SendFigure 2 depicts a possible specialization for the messages send n = 0 of the factorial function from fig. 1.The message send first evaluates its arguments. Thus, it determines the receiver as well as the operand. During the first execution of this AST node, the variable n contains an integer and, consequently, the variable read node can be specialized for reading integers. This is beneficial to avoid boxing[START_REF] Würthinger | Self-Optimizing AST Interpreters[END_REF]. The message send node can then be specialized based on the receiver's class, i. e., Integer in this case. Thus, the uninitialized message send node is replaced by a cached send node, which keeps the value of the lookup, i. e., the comparison method defined in Integer. As a guard, the cached send node has a special class check node as its child. This node is a specialized version of a class check and performs only a Java instanceof test on the receiver to determine whether the send can be performed. In the best case, this assumption holds and the cached comparison method can be invoked directly. In case the class check fails, execution is handed over to an uninitialized send node, which performs the method lookup and then specializes itself.This caching strategy has a wide applicability for instance for the lookups of globals, which are

1 def

 1 CatchNonLocalReturn.execute(self, frame):

TABLE 1

 1

			Performance Results
		DeltaBlue	Richards		Mandelbrot
		ms	norm.	ms	norm.	ms	norm.
	Java	118 ± 29.0	1.0	192 ± 10.9	1.0	146 ± 0.4	1.0
	PyPy	606 ± 9.9	5.1	646 ± 2.6	4.1	217 ± 0.8	1.5
	RPySOM	201 ± 0.5	1.7	1689 ± 2.9	10.6	786 ± 1.1	5.4
	TruffleSOM	171 ± 45.2	1.4	2557 ± 72.7	16.0	344 ± 3.0	2.3
	SOM++	8656 ± 12.8	73.0 87436 ± 170.2	547.4 104033 ± 184.2	710.4

ACKNOWLEDGMENTS

The authors would like to thank C. F. Bolz from the PyPy team as well as G. Duboscq, C. Humer, M. Haupt, C. Seaton, C. Wimmer, A. Wöß, T. Würthinger, and W. Zhang from the Truffle community for guidance and support. Their help was essential for enabling the SOM implementations to perform efficiently in the first place.