Marcelo M Morato

Amir Naspolini

Julio E Normey-Rico

Olivier Sename

NMPC via qLPV models and Taylor-based Scheduling Parameter Extrapolation: A Cartesian Robot Case Study

In this brief paper, we present an overview of recent advances on Model Predictive Control (MPC) synthesis for nonlinear systems using quasi-Linear Parameter Varying (qLPV) embeddings. For such, we consider a highly nonlinear Cartesian robot benchmark as a case study. Specifically, we advocate on the use of recursive Taylor-based extrapolation maps to generate accurate estimates for the future trajectories of the qLPV scheduling parameters, as shown in recent findings. We show how these estimates can be used to enhance and fasten the corresponding MPC algorithms, offering comparable performances to state-of-the-art techniques, while maintaining relieved numerical burden during the implementation. Through realistic simulations of the Cartesian robot, we demonstrate the effectiveness and the real-time capabilities of the discussed method, which is tested against widely acknowledged techniques (the SQP qLPV MPC framework, and the CasADi NMPC solver).

I. INTRODUCTION

Model Predictive Control (MPC) is a very wide-spread method for the regulation of constrained processes [START_REF] Camacho | Model predictive control[END_REF]. Over the last decades, it has had considerable research interest, with extensions developed for a wide variety of systems and settings. The theoretical establishment of MPC corresponds to the formal guarantees of recursive feasibility of the optimisation and closed-loop stability [START_REF] Mayne | Constrained model predictive control: Stability and optimality[END_REF].

Many works have studied the application of MPC for nonlinear systems (NMPC), e.g. [START_REF] Köehler | A nonlinear model predictive control framework using reference generic terminal ingredients[END_REF], [START_REF] Cunha | Robust nonlinear model predictive control with bounded disturbances based on zonotopic constraint tightening[END_REF]. Nevertheless, such algorithms are usually not trivial and their corresponding online implementation comes at the cost of increases numerical burden due to the inherent nonlinear predictions, which complicates real-time applications. Until the late 10s, even the most efficient NMPC algorithms displayed exponential complexity growth w.r.t. system size. Recent tools have shown how these algorithms can be fastened [START_REF] Andersson | CasADi: a software framework for nonlinear optimization and optimal control[END_REF], [START_REF] Gros | From Linear to Nonlinear MPC: Bridging the Gap via the Real-time Iteration[END_REF], yet through approximations of the nonlinear optimisation.

Anyhow, recent advances have shown how exact NMPC solutions with real-time capabilities can be generated through quasi-Linear Parameter Varying (qLPV) embeddings, see [START_REF] Cisneros | Nonlinear model predictive control for models in quasi-linear parameter varying form[END_REF], [START_REF] Morato | Robust nonlinear predictive control through qLPV embedding and zonotope uncertainty propagation[END_REF]; compare also to the survey [START_REF] Morato | Model predictive control design for linear parameter varying systems: A survey[END_REF] and references therein. LPV models are able to describe nonlinear and time-varying behaviours under linear dynamics structures [START_REF] Mohammadpour | Control of linear parameter varying systems with applications[END_REF], which depend on known, bounded scheduling parameters ρ. *This work has been supported by Campus France (Eiffel Scholarship), by CNRS ("Investissements d'Avenir", ANR-15-IDEX-02), and by CNPq (304032/2019 -0 researcher grant and PIBIC scientific initiation scholarship). The Authors thank J.P. Jordanou for his helpful insights on CasADi.

1 Dept. de Automac ¸ão e Sis., Univ. Fed. de Santa Catarina, Brazil.

marcelomnzm@gmail.com 2 Univ. Grenoble Alpes, CNRS, Grenoble INP , GIPSA-lab, 38000 Grenoble, France. Institute of Engineering Univ. Grenoble Alpes.

The elegance of qLPV-embedding MPC design resides on the fact that the "full-blown" nonlinear predictions are replaced by linear ones [START_REF] Morato | Model predictive control design for linear parameter varying systems: A survey[END_REF], thus enabling fast operation of the corresponding optimisation. The majority of these algorithms (first proposed in [START_REF] Cisneros | Efficient nonlinear model predictive control via quasi-LPV representation[END_REF] being established and generalised there since) are based on an iterative mechanism to estimate the future scheduling trajectories, applying the qLPV scheduling function over the previewed state trajectory and re-evaluating the optimisation until a certain convergence criteria is reached. Thereby, the resulting control algorithm has the numerical burden of a Sequential Quadratic Program (SQP).

Recent works have developed an alternative approach to the prior, where the future scheduling trajectories are estimated through linear recursive Taylor-based extrapolation laws [START_REF] Morato | NMPC through qLPV embedding: A tutorial review of different approaches[END_REF], [START_REF] Morato | A fast dissipative robust nonlinear model predictive control procedure via quasi-linear parameter varying embedding and parameter extrapolation[END_REF]. The novelty of this alternative is that the resulting MPC algorithm does not require to evaluate many QPs per sample, but rather just a single one. Moreover, convergence of the estimates to the true scheduling trajectories are obtained within a few samples, enabled by easy-to-verify sufficient conditions [START_REF]Sufficient conditions for convergent recursive extrapolation of qLPV scheduling parameters along a prediction horizon[END_REF]. The concept of NMPC using the qLPV-embedding approach is recent, and the advances on linear Taylor-based scheduling trajectory estimates are even more recent. Therefore, in this brief paper, we recall this concept, detailing all necessary implementation steps. Moreover, we use a (highly nonlinear) Cartesian robot system, as illustrated in Fig. 1, as a benchmark to demonstrate the effectiveness of these algorithms. Specifically, we compare the Taylor-based technique, as proposed by the Authors in [START_REF]Sufficient conditions for convergent recursive extrapolation of qLPV scheduling parameters along a prediction horizon[END_REF], to the stateof-the-art SQP qLPV MPC approach from [START_REF] Cisneros | Nonlinear model predictive control for models in quasi-linear parameter varying form[END_REF], as well as to a benchmark NMPC solution generated through CasADi [START_REF] Andersson | CasADi: a software framework for nonlinear optimization and optimal control[END_REF]. Our intent is to advocate the use of qLPV-embedding with Taylor-based parameter extrapolation as a benchmark approach to NMPC. Paper organisation. In Sec. II, we we present the Cartesian robot benchmark system and the required setup for the corresponding qLPV embedding. In Sec. III, we provide the general qLPV NMPC problem setup, as well as the underlying assumptions required for correct implementation; we also give simple solutions to generate terminal ingredients that ensure stability and recursive feasibility properties. In Sec. IV, we detail the Taylor-based scheduling parameter trajectory extrapolation mechanism, also providing a brief convergence proof. In Sec. V, simulation results are presented, comparing the qLPV MPC approach to state-of-theart NMPC. Concluding remarks are drawn in Sec. VI.

Notation. The index set N [a,b] represents {i ∈ N | a ≤ i ≤ b}, with 0 ≤ a ≤ b.
The identity matrix of size j is denoted as I j ; I j,{i} denotes the i-th row of I j . col{•} denotes the vectorisation of the entries and diag{v} denotes the diagonal matrix generated with the line vector v. The predicted value of a given variable v(k) at time instant k + i, computed based on the information available at instant k, is denoted as v(k + i|k). K refers to the class of positive and strictly increasing scalar functions that pass through the origin. • denotes the 2-norm. In matrix inequalities, ( ) denotes the corresponding symmetrical transpose.

II. PRELIMINARIES: CASE STUDY AND QLPV

EMBEDDING

In this Section, we present the basic requirements for qLPV embeddings and then apply them to considered case study. For such, consider the following generic discrete-time nonlinear system:

G := x(k + 1) = f (x(k), u(k)) , y(k) = f y (x(k), u(k)) , (1)
being k ∈ N the sampling instant, x ∈ R nx the vector of states, u ∈ R nu the vector of control inputs, and y ∈ R ny the vector of measured outputs. Without loss of generality, we assume that the origin is an admissible equilibrium point of G, i.e. there exists some ū s.t. f (0, ū) = 0. We assume that the states x are measured, thus we use the state-feedback u(k) := κ(k)x(k) to ensure that the dynamics of G adhere to desired specifications. We consider two possible objectives: (a) Regulation (steering x to the origin), and (b) Tracking (steering y to a steady-state target y r , which conversely means steering (x, u) to a steady-state target pair (x r , u r )).

The system in Eq. ( 1) is subject to state and input constraints, which define an admissible operation:

x ∈ X := {x ∈ R nx : x j ≤ x j , ∀j ∈ N [1,nx] } and u ∈ U := {u ∈ R nu : u i ≤ u i , ∀i ∈ N [1,nu] }. The nonlinear function f (x, u) is assumed of class C 1 over Z := X × U, i.e.
differentiable with first continuous derivatives.

A. qLPV Embedding

Assume that the nonlinear system G satisfies an exact differential inclusion property [START_REF] Morato | Model predictive control design for linear parameter varying systems: A survey[END_REF], which means that it can be embedded to a qLPV model. Therefore, suppose that there exists a map H(x, u) ⊆ R (nx+ny)×(nx+nu) such that [f (x, u) f y (x, u)] := H(x, u) x u T , ∀(x, u) ∈ Z. In this case, it is implied that Eq. ( 1) is equivalent to:

G :=    x(k + 1) = A(ρ(k))x(k) + B(ρ(k))u(k) , y(k) = C(ρ(k))x(k) + D(ρ(k))u(k) , ρ(k) = f ρ (x(k)) ∈ P .
(

The model in Eq. ( 2) is qLPV, with an endogenous nonlinear function f ρ (•) that results in the scheduling parameters ρ(k), which are bounded and known at each instant k. These variables are unknown for any future instant k + j , ∀j ∈ N [1,∞] . Through the sequel, we use P :=

ρ j ∈ R | ρ j ≤ ρ j ≤ ρ j , ∀j ∈ Z [1,nρ] .
In order to relieve conservativeness of the considered MPC algorithm, we assume that the scheduling variables exhibit bounded rates of variation:

Assumption 1: The scheduling variables ρ(k) evolve along the horizon with bounded rates of variation. This is:

δρ(k + 1) = (ρ(k + 1) -ρ(k)) ∈ δP := {δρ j ∈ R : δρ j ≤ δρ j ≤ δρ j , ∀j ∈ N [1,np] }.
Remark 1: For simplicity, we present qLPV embedding in Eq. ( 2) for a realisation of the nonlinear dynamics with a scheduling proxy that is only dependent on the state variables, i.e. f ρ (•) is only a function of x(k). We stress some cases this function is state-and input-dependent, i.e. ρ = f ρ (x, u). The detailed procedures are applicable to such cases without loss of generality.

B. A Nonlinear Benchmark: Cartesian Robot

As previously stated, a highly nonlinear case study is used as a benchmark to demonstrate the effectiveness of the qLPVembedding approach to MPC. Specifically, we consider the Cartesian robot system, which basically consists of a winch (vertical movement, z-axis), and is capable of performing movements along rails (longitudinal movement, x-axis. This robot is a benchmark nonlinear system in the likes of [START_REF] Cheng | Controller design for an overhead crane system with uncertainty[END_REF]; a graphical scheme is given in Fig. 1.

In order to model the dynamics of this Cartesian robot, the following baseline hypotheses are taken into account:

1) The beam translation force along the tracks F (t),

with corresponding mass M , can be imposed by an operator; 2) The winch cables are rigid, of negligible mass, and of constant length l; 3) The load mass m is concentrated at one point, that is, the geometry of the load is negligible compared to the dimensions of the bridge; 4) The pendulum motion of the load is subjected to a viscous frictional torque given by b θ(t), with b > 0; 5) The translational motion of the beam along the rail undergoes a viscous friction d ẋv (t), with d > 0; 6) The acceleration of gravity is denoted g.

Thence, using Lagrangian mechanics and the Euler-Lagrange equation, the following set of ODEs is obtained:

ẍv (t) = F (t) M + m sin 2 (θ(t)) - b θ(t) cos(θ(t)) l(M + m sin 2 (θ(t))) - ml θ(t) 2 sin(θ(t)) M + m sin 2 (θ(t)) - mg sin(θ(t)) cos(θ(t)) M + m sin 2 (θ(t)) - d ẋv (t) M + m sin 2 (θ(t))
,

θ(t) = F (t) cos(θ(t)) l(M + m sin 2 (θ(t))) - d ẋv (t) cos(θ(t)) l(M + m sin 2 (θ(t))) - g sin(θ(t))(M + m) l(M + m sin 2 (θ(t))) - b θ(t)(M + m) ml 2 (M + m sin 2 (θ(t))) - m θ(t) 2 sin(θ(t)) cos(θ(t)) M + m sin 2 (θ(t)) .
We consider that the output of this system is the load position (which is to be controlled), given by:

y(t) = x c (t) = x v (t) -l sin(θ(t)) ,
where the control input is u(t) = F (t) and the vector of state variables is given by This system operates under a sampling period of T s = 1 s, which gives a corresponding qLPV-embedding realisation as in Eq. (2), with system matrices given in Eqs. ( 5)-( 6). This qLPV realisation is generated with:

x(t) = θ(t) θ(t) x v (t) ẋv (t)
ρ(k) = f ρ (x(k), u(k)) =       cos(x 1 (k)) 1 M +m sin 2 (x1(k)) sinc(x 1 (k)) x 1 (k + 1) 2 x 1 (k) 2       . ( 3
)
We note that both x(k) and u(k) are known and measured variables at instant k, and thus ρ(k) can be generated explicitly through the nonlinear proxy f ρ (•). As previously explained, the future behaviour of the scheduling parameters, i.e. ρ(k + j), ∀j ≥ 0 is unknown, but estimated.

III. THE MPC SETUP

Taking into account the presented case study and the corresponding qLPV embedding realisation, we now detail the closed-loop paradigm with MPC.

Consider the robot system G is regulated through an MPC algorithm, which generates a state-feedback control law u(k) = κx(k), where κ is the corresponding feedback gain. This policy must be such that the state trajectories are steered to a given steady-state target, in an admissible manner (in the regulation case, this steady-state is the origin). Thus, in order to generate the MPC law, the qLPV model from Eq. ( 2) is spanned along a prediction horizon of N p steps. For such the future scheduling trajectory P k = col{ρ(k + j|k)}, ∀j ∈ N [0,Np-1] , from which only ρ(k) is a priori known. P k is generated through the Taylor-based extrapolation procedure, detailed in Sec. IV.

A. MPC Design

Consider the following cost function:

J(x(k), P k ) = Np i=1 (x(k + i|k), u(k + i -1|k)) + V (x(k + N p |k)) ,
where the stage cost, which weights the performance along the horizon, is quadratic, as follows:

(x, u) = x Q + u R .
We name V (x) as the terminal cost, used to penalise the state at the end of the prediction horizon. We consider Q and R as positive definite weighting matrices, used to imply the envisioned trade-off between control effort and state regulation. In the sense of the case study, this trade-off is set between driving the load to a certain position (regulation) while minimising the beam translation force (control effort).

Definition 1: Positive Invariant Set Assume that there exists a terminal set X f . X f is a positively invariant set for G iff, for any x(k) ∈ X f and ρ(k) ∈ P, it follows that x(k + 1) ∈ X f , where x(k + 1) := (A(ρ(k)) + B(ρ(k))κ) x(k).

Consider that there exists a terminal set X f which is positive invariant for G. Then, the MPC is implemented as follows: at each sampling instant k, the states x(k) are measured, the scheduling trajectory P k is computed, and the following optimisation problem is solved, embedding performance objectives and constraints:

min U k J(x(k), P k ) , (4)
s.t. X k = A(P k )x(k) + B(P k )U k , Y k = C(P k )x(k) + D(P k )U k , x(k + j|k) ∈ X , ∀j ∈ N [1,Np] , u(k + j -1|k) ∈ U , ∀j ∈ N [1,Np] ,
x(k

+ N p |k) ∈ X f ,
where

X k = col{x(k + j|k)} , ∀j ∈ N [1,Np] denotes the predicted sequence of states, Y k = col{y(k + j|k)} , ∀j ∈ N [0,Np-1]
gives the predicted sequence of outputs, and

U k = col{u(k + j|k)}, ∀j ∈ N [0,Np-1]
gives the sequence of control actions along the prediction horizon. The prediction matrices A(•), . . . , D(•) are given in Eqs. ( 7)-( 9), maintaining the same form for all discrete-time samples k ≥ 0. Let J (x(k), P k ) be the optimal solution of the optimisation in Eq. ( 4) at instant k, from which U k is the optimal sequence of control inputs. Then, the MPC law

A(ρ) =     0 1 0 0 -Tsg(M +m)ρ 3 ρ 2 l -mρ 1 ρ 2 ρ 3 (ρ 4 + ρ 5 ) + b(M +m)ρ 2 l 2 m 1 + 2mρ 1 ρ 2 ρ 3 ρ 5 - b(M +m)ρ 2 l 2 m dρ 1 ρ 2 l -dρ 1 ρ 2 l 0 0 0 1 -Tsmgρ 1 ρ 2 ρ 3 + bρ 1 ρ 2 l -mlρ 2 ρ 3 (ρ 4 + ρ 5 ) -bρ 1 ρ 2 l + 2mlρ 2 ρ 3 ρ 5 dρ 2 1 -dρ 2     .
(5)

B(ρ) = 0 Tsρ 1 ρ 2 l 0 Tsρ 2 T . C(ρ) = -lρ 2 0 1 0 . ( 6
)
A(P k ) =      A(ρ(k)) A(ρ(k + 1))A(ρ(k))
. . .

A(ρ(k + Np -1))A(ρ(k + Np -2)) . . . A(ρ(k))      , C(P k ) =      C(ρ(k)) C(ρ(k + 1))A(ρ(k))
. . .

C(ρ(k + Np -1))A(ρ(k + Np -2)) . . . A(ρ(k))      . ( 7
)
B(P k ) =      B(ρ(k)) 0 . . . A(ρ(k + 1))B(ρ(k)) B(ρ(k + 1)) . . . . . . A(ρ(k + Np -1)) . . . A(ρ(k + 1))B(ρ(k) A(ρ(k + Np -1)) . . . A(ρ(k + 2))B(ρ(k + 1)) . . .      . ( 8
)
D(P k ) =      D(ρ(k)) 0 . . . C(ρ(k + 1))B(ρ(k)) D(ρ(k + 1)) . . . . . . C(ρ(k + Np -1))A(ρ(k + Np -2)) . . . A(ρ(k + 1))B(ρ(k) C(ρ(k + Np -1)) . . . C(ρ(k + 2))B(ρ(k + 1)) . . .      . ( 9
)
at instant k is given by the application the first entry of

U k = col{u (k + j|k)}, ∀j ∈ N [0,Np-1] ,
i.e. u (k|k), to the process. In order for the MPC to render closedloop stability and a recursively feasible optimisation, the terminal ingredients (cost V (•) and set X f ) should verify some conditions, further detailed in Sec. III-C.

B. Tracking

Consider that a tracking objective is envisioned, as in the considered case study application, for which the controlled output is the load position, which must steered to a given setpoint. Then, the stage cost (x, u) must be set in order to minimise the variations of (x, u) from the desired set-point target (x r , u r ), which implies in an output target goal y r . Following the lines of [START_REF] Limon | Nonlinear MPC for tracking piece-wise constant reference signals[END_REF], the target goal can be generated using an offline reference optimisation selector, as follows.

Proposition 1: Assume there exists a linear (parameter varying) combination of the states x and inputs u that ensures y(k) → y r , considering the qLPV dynamics in Eq. ( 2). Then, the target goal z r = x r u r can be determined through the solution of:

min zr C(f ρ (z r )) D(f ρ (z r )) z r -y r 2 , (10)
s.t. (A(f ρ (z r )) -I nx ) B(f ρ (z r )) z r = 0 nx , f ρ (z r ) ∈ P , z r ∈ (X f × U)
. Proof: This optimisation finds an admissible steadystate target z r that imposes the output tracking objective. Full details of the proof are given in [START_REF] Limon | Nonlinear MPC for tracking piece-wise constant reference signals[END_REF]. Note that this target selection problem can be solved online, at each sampling instant, if the output reference goal y r is time-varying, which adds computational complexity.

C. Terminal Ingredients

We proceed by further detailing the how the terminal ingredients should be generated in order to render an asymptotically stable closed-loop, as well as a recursively feasible optimisation.

Assumption 2:

The scheduling parameters assume a constant value in steady-state, i.e. ρ = ρ r .

Assumption 3: The stage cost function is positive definite and uniformly continuous such that (e, δ) ≥ α ( e ) and | (e 1 , δ 1 )-(e 2 , δ 2 )| ≤ λ e ( e 1 -e 2 )+λ δ ( δ 1 -δ 2 ), where α , λ e and λ δ are K-functions. It is implied that (0, 0) = 0. Assumption 4: 1) There exists an admissible terminal feedback law κ t (x) ∈ U, ∀x ∈ X . 2) The terminal set X f is closed, contains the origin, and represents an admissible positive invariant set.

3) The terminal cost V (•) is continuous and positive for all x ∈ X . Moreover V (•) represents a control Lyapunov function for the unconstrained qLPV system in Eq. ( 2), meaning that there exist constants b > 0 and σ > 1 such that V (x) ≤ b|x| σ . It is implied, thus, that

V (A(f ρ (x))x + B(ρ)κ t (x)) -V (x) ≤ (x, κ t (x)), for V (x 1 ) -V (x 2 ) ≤ α r (|x 1 -x 2 |) (i.e. V (•) is a K function)
. The previous assumptions are standard. Accordingly, the following theorems ensure an admissible MPC operation.

Theorem 1: Stability and Recursive Feasibility [2] Suppose the there exists a terminal control law u = k t (x). Consider that the qLPV system in Eq. ( 2) is controlled by the MPC, as rendered through Eq. ( 4). Then, input-to-state stability is ensured if the following conditions hold: (C1) The origin x = 0 lies in the interior of X f ; (C2) X f is positively invariant under the terminal feedback controller κ t (•). (C3) The discrete Lyapunov equation is verified ∀ x ∈ X f and ∀ ρ ∈ P: V (x + ) -V (x, ) ≤ -(x, κ t (x)). (C4) The image of the terminal control is admissible, i.e. κ t (•) ∈ U , ∀ρ ∈ P. (C5) The terminal set X f is a subset of X .

Assuming that the initial solution of the MPC problem U k is feasible, then, the MPC is recursively feasible.

Proof: This proof is standard; refer to [START_REF] Mayne | Constrained model predictive control: Stability and optimality[END_REF].

In order to satisfy the conditions required by Theorem 1, we choose the following quadratic terminal cost function V (x) = x T T x, where T = T T is a positive definite weight. Accordingly, the terminal set X f is taken as a sub-level set of the terminal cost, i.e. X f := {x ∈ R nx | x T T x ≤ 1}. By construction, X f is an ellipsoidal set constraint, which should be positively invariant for the terminal feedback κ t (•). Thus, the following theorem gives a numerically solvable sufficient solution that generates these terminal ingredients.

Theorem 2: Terminal Ingredients [8] Conditions (C1)-(C5) from Theorem 1 are satisfied if there exist a symmetric positive definite matrix T ∈ R nx×nx and a rectangular matrix W ∈ R nu×nx such that Y = T -1 > 0, W = KY and that LMIs ( 11)-( 13) hold under the minimisation of log det{Y } for all ρ ∈ P. The terminal feedback is then given by κ t (•) = Kx.

    Y (A(ρ)Y + B(ρ)W ) Y Y 0 Q -1 W 0 0 R -1     ≥ 0 , ( 11
)
x 2 j I {j} Y I {j} Y T Y ≥ 0, j ∈ N [1,nx] , ( 12
)
u 2 i I {i} W Y ≥ 0, i ∈ N [1,nu] . ( 13
)
Proof: Consider P k is known (via the extrapolation procedure detailed in Sec. IV). Since ρ(k) = f ρ (x(k)), it follows that ρ(k) = ρ r in steady-state, iff lim k→+∞ x(k) = x r . Then, by applying a Schur complement to LMI [START_REF] Cisneros | Efficient nonlinear model predictive control via quasi-LPV representation[END_REF], we obtain condition (C3), which suffices for (C2). By definition, an ellipsoid ensures (C1). (C4) and (C5) are respectively satisfied by applying Schur complements to LMI [START_REF] Morato | NMPC through qLPV embedding: A tutorial review of different approaches[END_REF] and [START_REF] Morato | A fast dissipative robust nonlinear model predictive control procedure via quasi-linear parameter varying embedding and parameter extrapolation[END_REF]. In turn, the terminal feedback κ t (x) = Kx ensures that the qLPV system is asymptotically stable. This concludes the proof.

Remark 2: The terminal ingredients provided through Theorem 2 ensure recursive feasibility and asymptotic stability of the state trajectories. We note that LMI ( 11) is infinite-dimensional; in practice, its solution can be found by enforcing the inequalities over a sufficiently dense grid of points ρ ∈ P. Then, the solution can be verified over a denser grid. If quadratic terminal ingredients are excessively conservative, a parameter-dependent alternative can be sought, if necessary, refer to [START_REF] Morato | Robust nonlinear predictive control through qLPV embedding and zonotope uncertainty propagation[END_REF].

IV. SCHEDULING PARAMETER EXTRAPOLATION

The concept of MPC is based on spanning a prediction of the process variables along a future horizon window. For such, we use the full state and output predictions

X k = A(P k )x(k) + B(P k )U k , Y k = C(P k )x(k) + B(P k )D k ,
with prediction matrices given in Eqs. ( 7)- [START_REF] Morato | Model predictive control design for linear parameter varying systems: A survey[END_REF]. For such, the future scheduling sequence P k is required.

Accordingly, we detail, in this Section, the recent framework from [START_REF] Morato | A fast dissipative robust nonlinear model predictive control procedure via quasi-linear parameter varying embedding and parameter extrapolation[END_REF], [START_REF]Sufficient conditions for convergent recursive extrapolation of qLPV scheduling parameters along a prediction horizon[END_REF], which uses a first-order Taylor expansion of the scheduling proxy f ρ (x(k)) to construct the future scheduling sequence. First and foremost, we stress that the main advantage of this extrapolation is that predicted sequence P k is generated through a single recursive linear law, numerically much cheaper than the state-of-the-art procedure from [START_REF] Cisneros | Nonlinear model predictive control for models in quasi-linear parameter varying form[END_REF], which requires the iterative re-evaluation of

P l k = f ρ (X l-1 k )
, where the super-index l indicates the l-th iteration of the MPC optimisation.

Denote δx(k + j) = x(k + j + 1) -x(k + j) as the incremental state deviation. By definition, δx is bounded 1 to a compact and convex box-type set

∆X := δx ∈ R nx : |δx j | ≤ δx j , ∀j ∈ N [1,nx] .
The method is as follows: re-write the static scheduling map f ρ (x) through the following Taylor expansion: approximated by:

f ρ (x) = f ρ (x)| x + ∂f ρ (x) ∂x x (x -x) + ξ ρ , (14)
being x the expansion point and ξ ρ a residual which inherits the discrepancy between the real static map and its approximate. Since f ρ (x) is assumed class C 1 , it is direct that the partial derivatives ∂fρ(x) ∂x

x are ultimately bounded for all x ∈ X .

From this development, we obtain:

ρ(k + 1) = ρ(k) + f ∂ ρ (k)δx(k) + ξ ρ (k) , . . . ρ(k + N p -1) = ρ(k + N p -2) + f ∂ ρ (k + N p -2)δx(k + N p -2) + ξ ρ (k + N p -2) ,
where the derivative terms are given by f

∂ ρ (k + j) = ∂fρ(x) ∂x x (k+j)
. Note that ρ(k) and δx(k) are known variables at each instant k, whereas f ∂ ρ (k) can be numerically evaluated. In practice,

f ∂ ρ (k + j) is unknown for j ∈ N [1,N -2] but it can be replaced by f ∂ ρ (k + j) = f ∂ ρ , ∀ j ∈ N [1,N -2]
, where f ∂ ρ denotes the partial derivative evaluated at instant k, see the discussion in [START_REF]Sufficient conditions for convergent recursive extrapolation of qLPV scheduling parameters along a prediction horizon[END_REF]. By doing so, it is implied that ρ(k + j) ≈ ρ(k + j -1) + f ∂ ρ δx(k + j -1|k). Therefore, the estimate for the future scheduling variables can be written as the sum of the estimate from the previous sample corrected with an adjustment term f ∂ ρ δx(k + j -1). Through the sequel, we neglect the bias term ξ ρ , since it is bounded and small, as argued in [START_REF]Sufficient conditions for convergent recursive extrapolation of qLPV scheduling parameters along a prediction horizon[END_REF]. In any case, robustified MPC schemes with respect to such estimation error are discussed in [START_REF] Morato | Robust nonlinear predictive control through qLPV embedding and zonotope uncertainty propagation[END_REF], [START_REF] Morato | A fast dissipative robust nonlinear model predictive control procedure via quasi-linear parameter varying embedding and parameter extrapolation[END_REF]. Accordingly, we can write the vectorwise extrapolation in a recursive fashion:

P k = P k-1 + f ∂ ρ δX k , (15)
where the sequence of state increments is given by

δX k = col{δx(k + j)} T , ∀j ∈ N [0,Np-2] .
Lemma 1: Assume that f ρ (•) is class C 1 and that f ∂ ρ is ultimately bounded. Assume that the system (2) is stable in closed-loop with u(k) = κx(k). Then, the recursive extrapolation algorithm in Eq. ( 15) converges.

Proof: This proof is reduced for brevity, full details are given in [START_REF]Sufficient conditions for convergent recursive extrapolation of qLPV scheduling parameters along a prediction horizon[END_REF], which presents five (simple-toverify) sufficient conditions for convergence. Consider that the residual term ξ ρ (k + j) should turn null. Thus, use lim k→∞ x(k) = x r holds (stability) and take ξ ρ (k) = f ρ (x(k + 1)) -f ρ (x(k)) -f ∂ ρ δx(k). Due to the stabilisation, it directly follows that lim k→∞ f ρ (x(k)) = lim k→∞ f ρ (x r ) and lim k→∞ δx(k) = 0, which implies in lim k→∞ ξ ρ (k) = -lim k→∞ f ∂ ρ δx(k) → 0. This concludes the proof. We recall the major advantages of this Taylor-based extrapolation method: (i) the resulting online operation is recursive, only residing in linear operations (i.e. Eq. ( 15)), thus being numerically-cheap; (ii) the estimated scheduling parameter trajectories P k converge to the true values within a finite number of discrete-time samples (as gives Lemma 1), which means that precise information on the future behaviour can be passed to the MPC); (iii) the estimation error is small and bounded (refer to [START_REF]Sufficient conditions for convergent recursive extrapolation of qLPV scheduling parameters along a prediction horizon[END_REF]Lemma 3]).

V. NONLINEAR SIMULATION RESULTS

In this Section, we show the simulation results of the nonlinear case study. Specifically, in order to illustrate the effectiveness of the qLPV-embedding approach to NMPC design, three distinct strategies are used to control the Cartesian robot:

• The benchmark approximation-based NMPC solution CasADi, from [START_REF] Andersson | CasADi: a software framework for nonlinear optimization and optimal control[END_REF].

• The state-of-the-art SQP-based qLPV MPC from [START_REF] Cisneros | Nonlinear model predictive control for models in quasi-linear parameter varying form[END_REF], previously shown as a comparable method to approximation-based NMPC solutions (such as ACADO, GRAMPC, and CasADi), e.g. [START_REF] Cisneros | Plenary at the 3 rd IFAC workshop on linear parameter varying systems: Fast Nonlinear MPC via quasi-LPV Models[END_REF]. In this approach, the QP in Eq. ( 4) is solved l times per sample, with the scheduling parameter trajectory estimate being given by P l k = f ρ (X l k ). • The highlighted Taylor-based extrapolation single QP qLPV MPC from [START_REF] Morato | A fast dissipative robust nonlinear model predictive control procedure via quasi-linear parameter varying embedding and parameter extrapolation[END_REF], [START_REF]Sufficient conditions for convergent recursive extrapolation of qLPV scheduling parameters along a prediction horizon[END_REF], where the scheduling trajectory is estimated by the means of Eq. ( 15). For simplicity, we denote these methods henceforth as "CasADi NMPC", "SQP qLPV MPC", and "Taylor qLPV MPC", respectively. The following results were obtained in a 2.1 GHz, 8 RAM PC, using Matlab, Yalmip, and Gurobi (qLPV MPCs), and Python (CasADi).

As previously stated, the control objective is to steer the load position y(k) according to a piece-wise constant reference signal r(k), which must be tracked. Thereof, we use the corresponding tracking stage cost (x, u) = yy r Q + u R , which can be rewritten as x -x r Qx + u -u r Rx using suitable coordinate changes. The tracking objective given through (x r , u r ) is obtained via Proposition 1. For the synthesis of the MPCs, we use a prediction horizon of N p = 10 samples, together with the following weighting matrices Q = 1, and R = 0.02 (thus prioritising output tracking over control effort minimisation). The initial conditions are: x(0) = [0 -1 4000 3 1 100 ] T and u(0) = 0. Remark 3: The CasADi solution is implemented with minor changes to the control input constraints (a stricter slew rate is used) and to the stage cost (•) (used as x -x r Q + u R ). These adjustments are done in order to bypass the strong nonlinearities of the MPC optimisation at some samples, which are softened and thus infeasibility is avoided.

First of all, we show the accurateness of the scheduling parameter trajectory estimated generated by the Taylor-based recursive argument, detailed in Sec. IV. This is illustrated in Fig. 2, which gives the full behaviour of ρ 5 plotted against sampled trajectories of the fifth entry of P k . Evidently, the recursive extrapolation law generates very precise estimations, with negligible residual (also true for the remaining scheduling variables, not shown due to lack of space). This further emphasises the applicability of the Taylor-based extrapolation scheme, which is reliable and passes precise information to the MPC regarding the future behaviour of ρ. A significant advantage is that each P k is generated linearly at sample k, which is numerically very cheap (in contrast to the SQP method, which requires a nonlinear vector map P l k = f ρ (X l k ) and multiple QPs). Next, Figs. 3 and4 show the output and input trajectories, respectively, obtained with each control method. The results from CasADi are slightly deviated due to the issues mentioned in Remark 3. We stress that both qLPV MPC methods yield very similar results in terms of reference tracking, which is obtained with offset-free error in steady state. For the considered system, the SQP MPC approach took, in average, two iterations of its internal loop to achieve a solution, meaning that it held a computational complexity of roughly two QPs per sample.

Finally, Table I presents corresponding performance indexes 2 , given w.r.t. those from the CasADi NMPC solution (benchmark). We highlight the key findings:

1) In terms of real-time capabilities, the qLPV MPC approaches are shown to be very fast solutions to 2 We use IAE as k r(k) -y(k) , being r(k) the reference signal. NMPC. The average computational burden with these approaches (t c ) is even smaller than what is required by CasADi (more than 20 times smaller), which is quite impressive. 2) Despite the SQP qLPV MPC solution being widely applied in recent works, e.g. [START_REF] Cisneros | Nonlinear model predictive control for models in quasi-linear parameter varying form[END_REF], [START_REF] Cisneros | Plenary at the 3 rd IFAC workshop on linear parameter varying systems: Fast Nonlinear MPC via quasi-LPV Models[END_REF], we advocate for the use of the Taylor-based approach from [START_REF]Sufficient conditions for convergent recursive extrapolation of qLPV scheduling parameters along a prediction horizon[END_REF]. By using a linear recursive estimate to estimate P k , the total numerical burden of the controller is reduced in over 30 %, since only one QP is required to be solved per sample (and not multiple ones as in [START_REF] Cisneros | Nonlinear model predictive control for models in quasi-linear parameter varying form[END_REF]). As shown in [14, Lemma 3]), we note that the estimation residual can be easily verified to be bounded, small, and null in steady-state.

3) The use of qLPV-embeddings is an elegant and efficient way to encapsulate nonlinearities of system that satisfy differential inclusion. The corresponding MPCs do not have to resort to any nonlinear optimisation, but rather quadratic ones. Furthermore, less conservative control is allowed, since recursive feasibility is ensured and the artifices to circumvent feasibility losses due to local minima (i.e. Remark 3) do not have to be used.

VI. CONCLUDING REMARKS

In this paper, we advocate for the qLPV-embedding framework as a standard approach for the development of NMPC algorithms with exact solution. Specifically, we highlight and exemplify recent findings on use of recursive Taylor-based extrapolation maps to generate accurate estimates for the future trajectories of the process qLPV scheduling parameters. Using a highly nonlinear Cartesian robot system, we demonstrate the effectiveness of the qLPV approach using these Taylor-based extrapolation estimates. For such, the method is compared in terms of numerical burden and achieved performances to a state-of-the-art qLPV MPC technique and a benchmark NMPC solution (CasADi). We show how the analysed framework is able to achieve comparable results to state-of-the-art NMPC algorithms with much reduced numerical burden; the method enables real-time NMPC applications using only one quadratic program and one linear recursive law per sample during the implementation, which is a significant advance.

Fig. 1 .

 1 Fig. 1. Case study: Cartesian robot benchmark.

  parameters are used: the cable length l is of 7 m. The mass of the beam M and the mass of the load m are, respectively, 5000 Kg and 20000 Kg. The viscous friction constant d in the beam is of 2000 Kg/s and the viscous friction torque constant b in the load is of 0.00172 Kg m 2 /s. This system must be regulated such that the following constraints are respected: θ ∈ [-π, π] rad (angle between the load and the beam); θ ∈ -1 7 , 1 7 rad/s (load angular speed); x v ∈ [-50, 50] m (beam position on the rail); ẋv ∈ [-1, 1] m/s (beam speed); u ∈ [-100, 100] N (force on the beam); y ∈ [-50, 50] m (load position).

Fig. 2 .

 2 Fig. 2. Scheduling trajectory and Taylor-based extrapolation estimates (at different samples). Coloured lines represent the trajectory estimates of Np-samples, while the blue curve stands for the real scheduling parameter trajectory.

Fig. 3 .

 3 Fig. 3. Cartesian robot: Reference tracking results.

Fig. 4 .

 4 Fig. 4. Cartesian robot: Control inputs.

Bounds can be generated directly from Eq. (2), using x ∈ X .


Bruno Paoli

Meters and Formulas : The Case of Ancient Arabic Poetry

Introduction Introduction Introduction

The phrase "Ancient Arabic poetry" stands here for poetry attributed to poets who probably lived between the end of the fifth century A. D. and the end of the seventh, whose poems were brought down to us through written recensions established by Arabic scholars between the eighth and tenth centuries. Although their genuineness remains under question, most specialists now acknowledge that the poems at hand, despite the fact that they were obviously more or less distorted during transmission and collection, can be considered, on the whole, as representative of the poetic tradition of this period. 1The use of writing, as it seems, had for long been known among the Arabs and other people of the area, as shown by Nabatean and Palmyrenian writings, by those of Qaryat al-Faw or, later on, by the stele of al-Namāra2 .

But it was probably restricted to specific usages -dedications, commemorative and funeral stelae, contracts or pacts, diplomatic correspondence, etc. -, whereas literary works were not written down except under extraordinary occasions: as far as the Arabian Peninsula is concerned, the famous versified hymn of Qāniya (first century A.D.) constitutes the only exception to this rule 3 . Similar situations can be found elsewhere: let us just mention the well-known cases of Touareg in North Africa and of Irish in the time of the Ogham tradition. There is no doubt, thus, that poetic practice among the Arabs before the rise of Islam was purely oral. To the historical and transhistorical proofs, we can add some formal features -a finite repository of traditional themes, conventional similes, and formulas, common to all poets -which are usually held to be characteristic of oral poetry. Ancient Arabic poetry is versified, ruled by quantitative meter and monorhyme, without any further constraint on verse order or grouping. In a way, each poem is an open form, the completion of which is left in the poet's hands; all lines share a same verse-pattern and a same rhyme and they are not grouped into stanzas, so that their number is theoretically unlimited. But this simplicity is balanced, in a way, by the great number and the extreme variety of the available verse-patterns. The scanning of more than 38,000 lines attributed to a hundred poets of the period under examination has enabled me to give a quite complete picture of verse-patterns in use, as can be seen in Tables 1 and2 (Paoli 1997: 401-402). All these verse-patterns share common structural constraints 4 . Leaving verse-ending aside, we can observe that they all rely on a binary alternation between free metrical positions and fixed metrical units, which are both in very limited number. There are two types of free positions: x (-or ∪) and X (or ∪∪). Two successive such positions are forbidden, except at the beginning of a hemistich, where a few verse-patterns (basīṭ-2 (a and b), sarīʿ and munsariḥ) exhibit two interdependent free positions (x^x), which cannot be simultaneously associated with short syllables. In other words, x^x can only be realized as two long syllables (--), one long and one short (-∪) or vice versa (∪ -). As for the fixed units, if we except the end of lines and hemistichs, they are three in number : [∪ -], [∪ --] et [-∪ -]. In the great majority of verse-patterns, the alternation between free positions and fixed units is strictly binary. As mentioned above, the succession of two free units only occurs at the beginning of a hemistich (x^x); and the succession of two or three fixed units only occurs at the end of both hemistichs of a few versepatterns. This is the reason why I call "foot" any association of one fixed unit and one free position. As can be seen, this analysis of verse-patterns, which is intended to match poetic practice as closely as possible, leads us quite far from the "official representation" of verse-patterns, that of the classical theory of 'ilm al-'arūḍ attributed to al-Ḫalīl (second half of the eighth century A. D.).

Table 1. Verse-patterns of ancient Arabic poetry (part 1)

H1 H2 P1 P2 P3 P4 P1 P2 P3 P4 (1) T-1 [∪ -] x [∪ -] x [-∪ -] x [∪ -∪ -] [∪ -] x [∪ -] x [-∪ -] x [∪ ---] (2) T-2 [∪ -] x [∪ -] x [-∪ -] x [∪ -∪ -] [∪ -] x [∪ -] x [-∪ -] x [∪ -∪ -]
(3) T-3

[∪ -] x [∪ -] x [-∪ -] x [∪ -∪ -] [∪ -] x [∪ -] x [-∪ -] x [∪ --] (4) Md-1a x [∪ --] x [∪ -] x [∪ --] ///// x [∪ --] x [∪ -] x [∪ --] ///// (5) Md-1b x [∪ --] x [∪ -] x [∪ -] ///// x [∪ --] x [∪ -] x [∪ -] ///// (6) Md-2a x [∪ -] x [-∪ -] [∪ ∪ -] ///// x [∪ -] x [-∪ -] [∪ ∪ -] ///// (7) Md-2b x [∪ -] x [-∪ -] [∪ ∪ -] ///// x [∪ -] x [-∪ -] [--] ///// (8) B-1a x [-∪ -] x [∪ -] x [-∪ -] [∪ ∪ -] x [-∪ -] x [∪ -] x [-∪ -] [∪ ∪ -] (9) B-1b x [-∪ -] x [∪ -] x [-∪ -] [∪ ∪ -] x [-∪ -] x [∪ -] x [-∪ -] [--] (10) B-2a x^x [∪ -] x [∪ --] [-∪ -] [∪ ∪ -] x^x [∪ -] x [∪ --] [-∪ -] [∪ ∪ -] (11) B-2b x^x [∪ -] x [∪ --] [-∪ -] [∪ ∪ -] x^x [∪ -] x [∪ --] [-∪ -] [--] (12) Bm-1 x x [∪ -] x [∪ -] x^x [∪ -] ///// x x [∪ -] x[∪ -] x^x[∪ -] ///// (13) Bm-2 x^x [∪ -] x[∪ -] x^x [∪ -] ///// x^x [∪ -] x[∪ -] x^x [∪ -] ///// (14) Bm-3 x^x [∪ -] x[∪ -] x [-(∪) -] ///// x^x [∪ -] x[∪ -] x [--] ///// (15) W [∪ -] X [-∪ -] X [-∪ --] ///// [∪ -] X [-∪ -] X [-∪ --] ///// (16) Wm [∪ -] X [-∪ -] X [-] ///// [∪ -] X [-∪ -] X [-] ///// (17) K-1 X [-∪ -]
Table 2. Verse-patterns of ancient Arabic poetry (part 2) These numerous verse-patterns are unequally employed. More than three quarters of the lines were composed according to verse-patterns of ṭawīl, which is by far the most common one (38,69 %), wāfir (14,03 %), kāmil (12,2 %) and basīṭ (11,89 %). Then come mutaqārib (6,5 %), ḫafīf (4,39 %), rağaz (3,55 %), ramal (2,23 %), kāmil mağzū' (1,86 %), sarī' (1,8 %), munsariḥ (1,47 %), hazağ (0,48 %) and basīṭ mağzū' (0,31 %). The remaining verse-patterns are very rare and some of them are used in a few lines only, as is the case for wāfir mağzū' (Wm), kāmil-2b (K-2b), simple kāmil (Ks), ramal mağzū'-2 (Rm-2), simple ḫafīf (Xs) and mutaqārib-2 (Mt-2). What will be said in the following pages mostly concerns the four main meters and their derived long versepatterns : ṭawīl (T-1, T-2 et T-3), basīṭ (B-1a, B-1b, B-2a et B-2b), wāfir (W) and kāmil (K-1, K-2 et K-3). In particular, the short patterns of basīṭ (Bm) and kāmil (Km), which undergo specific processes, will be left aside. Up to now, the formulaic style of ancient Arabic poetry has received but little attention. The contributions of [START_REF] Monroe | Oral Composition in Preislamic Arabic Poetry[END_REF] and [START_REF] Zwettler | The Oral Tradition of Classical Arabic Poetry, Colombus[END_REF], who deserve credit for having brought it to light, undertook to prove that the Arabic poetic tradition was an oral one. Applying a statistical approach to a sample of well-known lines, they were able to estimate the ratio of formulaic units with a fantastic precision: Monroe, for example, concludes that the four samples he has analysed contain 87,54 % of formulaic expressions. However, these authors did not try to proceed to a systematic and detailed analysis of formulaic style; in particular, they did not pay attention to the interaction between formulas and verse-patterns, which plays, in my view, a main role in the creative process of verse composition.

H1 H2 F1 F2 F3 F4 F1 F2 F3 F4 (24) H [∪ --] x [∪ --] x ///// ///// [∪ --] x [∪ ---] ///// ///// (25) Rj-1 x x [∪ -] x x [∪ -] x x [∪ -] ////
x [∪ -] x x [∪ -] x x [∪ -] ///// x x [∪ -] x x [∪ -] x x [∪ -] ///// (30) R-1a x [∪ --] x [∪ --] x [∪ -] ///// x [∪ --] x [∪ --] x [∪ --] ///// (31) R-1b x [∪ --] x [∪ --] x [∪ -] ///// x [∪ --] x [∪ --] x [∪ ] ///// (32) R-2 x [∪ --] x [∪ --] x [∪ -(-)] ///// x [∪ --] x [∪ --] x [∪ -] ///// (33) Rm-1 x [∪ --] x [∪ --] ///// ///// x [∪ --] x [∪ --] ///// ///// (34) Rm-2 x [∪ --] x [∪ ] ///// ///// x [∪ --] x [∪ ] ///// ///// (35) S-1 x^x [∪ --] x [∪ -] [-∪ -] ///// x^x [∪ --] x [∪ -] [-∪ ] ///// (36) S-2 x^x [∪ --] x [∪ -] [-∪ -] ///// x^x [∪ --] x [∪ -] [-∪ -] ///// (37) S-3 x^x [∪ --] x [∪ -] [-∪ -] ///// x^x [∪ --] x [∪ -] [--] ///// (38) S-4a x^x [∪ --] x [∪ -] X [-] ///// x^x [∪ --] x [∪ -] X [-] ///// (39) S-4b x^x [∪ -] x [-∪ -] X [-] ///// x^x [∪ -] x [∪ -] X [-] ///// (40) Mn x^x [∪ --] x [-∪ -] [∪ ∪ -] ///// x^x [∪ --] x [-∪ -] [∪ ∪ -] ///// (41) X-1 x [∪ --] x [-∪ -] x[∪ --] or [---] ///// x [∪ --] x [-∪ -] x[∪ --] or [---] ///// (42) X-2 x [∪ --] x [-∪ -] x[∪ --] ///// x [∪ --] x [-∪ -] x [∪ --] ////
The only author to be aware of this phenomenon is Bauer (1993aBauer ( , 1993b)), who devoted two papers to the initial formulas used in the traditional introduction to the nasīb (erotic prelude) of the qaṣīda, viz. ḏikr al-aṭlāl, the evocation of the deserted encampment of the beloved's tribe5 . In my own exhaustive inventory of initial ḏikr al-aṭlāl formulas, which basically corresponds to that of Bauer (Paoli 1997: 629), I have classified the formulas according to the verse-patterns they match with. This classification is reproduced in table 3, where N is a common noun, NP a proper noun, and where N [ --], for example, means that the noun begins with two long syllables. Finally, a noun is [+def] if it is preceded by the definite article (ddāra) ; otherwise, it is [-def] (dāran) 6 . Table 3. Introductory formulas of the ḏikr al-aṭlāl

ṭawīl wāfir mutaqārib kāmil basīṭ sarī' ḫafīf li-man + N [-def] li-man + N [-def] li-man + N [-def] li-man +N [+def] li-man +N [+def] 'afā / 'afat +NP or min 'afā / 'afat + min+NP 'afati d-diyāru 'a-min + N [-∪] 'a-min + N [--] 'a-min + N [-∪] 'a-min + N [∪ -] 'a-min + N [∪ -] 'araftu li- 'arafta + N [-def] 'arafta + N [+def] 'a-ta'rifu + N [-def] 'a-ta'rifu + N [-def] 'a-'arafta min hal ta'rifu + N [+def] hal ta'rifu + N [+def] hal 'arafta + N [+def] li + NP [-] li + NP [-]
'a-lā yā dāra yā dāra

+ NP[-∪∪] yā dāra + NP [-] yā dāra + NP [--] bāna + N [+def] bānat + NP [∪ -] dārun li + NP [-]
6 Here are some complete formulas built according to the structural patterns which appear in table 3 : li-man ṭalalun 'To whom do the vestiges belong... ?'; li-mani d-diyāru 'To whom do the abode(s) belong... ?'; li-mani d-dāru 'To whom do the abode belong... ?'; 'afati d-diyāru 'The abodes have become erased' ; 'afā min Sulaymā 'Sulaymā has left [a place]...'; 'a-min Laylā, 'amin Nawāra, 'a-min Rayḥānata, 'a-min 'Ummi 'Awfā 'Do, of Laylā, of Nawāra, of Rayḥāna, of Umm 'Awfā...) ; 'a-min 'āli Laylā (Do, of Laylā's tribe...?'; 'a-min rasmi dārin 'Do, of the traces of an abode...?'; yā dāra (Hindin) 'O abode of (Hind)'; li-Salmā, li-Hindin 'Of Salmā', 'Of Hind'; 'araftu ddiyāra 'I recognized the abodes'; 'araftu d-dāra 'I recognized the abode'; 'araftu li-Salmā 'I recognized, to Salmā'; 'a-'arafta dāran 'Did you recognize an abode ?'; 'a-ta'rifu rasma-d-dāri 'Do you recognize the traces of the abode?'; hal ta'rifu-d-dāra 'Do you recognize the abode'; hal 'arafta l-ġadāta 'Did you recognize, at dawn, ...?'; bānat Su'ādu 'Su'ād has disappeared'; bāna lḫalīṭu 'The company has disappeared'. The case of interrogative formulas built with the verb 'arafa is a perfect example of the kind of alternations that can be found. The combination of the interrogative pronouns 'aand hal with a verb in the perfect or imperfect tense gives four different formulas and, thus, four different metrical patterns, each used with one or two verse-patterns, as can be seen in Table 4.

Table 4. Interrogative formulas with the verb 'arafa formula metrical pattern meters

'a-'arafta + N [-def, Cvx+] ∪∪ -∪ - kāmil 'a-ta'rifu + N [-def, Cvx+] ∪ -∪∪ - ṭawīl, wāfir hal ta'rifu + N [+ def] --∪ - basīṭ, sarī' hal 'arafta + N [+ def] -∪ -- ḫafīf
The second column of Table 4 displays the metrical quantitative pattern of each of these four formulas. In the formulas built with particle hal, the noun following the verb is preceded by the definite article (l-), which does not happen in the formulas beginning with 'a-. The four metrical patterns define four different 'rhythms', each of which begins with a different two-syllable sequence : one short and one long for wāfir and ṭawīl (i.e. an iambic pattern [∪ -]) ; for kāmil, two short syllables constituting an anapaestic pattern with a fixed following long syllable [∪∪ -]) ; two long syllables (i.e. a spondaic pattern [--]) for basīṭ and sarī' ; a long syllable followed by a short one (a trochaic pattern [-∪]) for ḫafīf. There is absolutely no ambiguity between these four formulas. But it must also be noted that each of the two formulas with an imperfect verb can be used with two different verse-patterns: that of wāfīr and ṭawīl for the first one ('a-ta'rifu) ; that of basīṭ and sarī' for the other (hal ta'rifu). In the case of ʾa-taʿrifu, this ambiguity disappears with the next noun phrase, the choice of which depends on what verse-pattern has been chosen. This analysis is illustrated by lines (1) and ( 2), which follow versepatterns of ṭawīl-2 and wāfir, respectively 7 :

(1) 'a-ta'-ri-fu ras-man bay-na Duh-mā-na fa-r-Ra-qam

[∪ -] ∪ [∪ -] - [- ∪ -] - [∪ - ∪ -] [∪ -] - [∪ -] - [- ∪ -] - [∪ - ∪ -] 'i- lā Ḏī Ma-rā-ḥī-ṭin ka-mā ḫuṭ-ṭa bi-l-qa-lam
(2) 'a-ta'-ri-fu min Hu-nay-da-ta ras-ma dā-rin

[∪ -] ∪∪ [- ∪ -] ∪ ∪ [- ∪ - -] [∪ -] - [- ∪ -] ∪ ∪ [- ∪ - -]
bi-ḫar-ğay Ḏar-wa-tin fa-'i-lā li-wā-hā

In the case of hal ta'rifu, the following noun remains the same (d-dār 'the abode'), whatever the verse-pattern , basīṭ or sarī'; it is only the second part of the hemistich that enables us to identify the correct verse-pattern without any ambiguity. Examples (3) and ( 4) seem to support the idea that sarī' (line 4) can be considered, in a way, as a shortened form of basīṭ (line 3) 8 :

(3) hal ta' -ri-fu-d-dā-ra qaf-ran lā 'a-nī-sa-bi -hī

- [- ∪ -] - [∪ -] - [- ∪ -] [∪∪ -] - [- ∪ -] - [∪ -] - [- ∪ -] [- -]
'il-la-l-ma-ġā-nī wa-'il-lā maw-qi-da-n-nā-ri

(4) hal ta'-ri-fu-d-dā-ra 'a-fā ras-mu-hā

- - [∪ - -] ∪ [∪ - - ∪ -] - - [∪ - -] ∪ [∪ - - ∪ -]
'il-la-l-'a-ṯā-fiy--ya wa-mab-na-l-ḫi-yam Though the alternations found for other kinds of formulas are not as systematic as the one presented above, they all define a clear-cut opposition between verse-patterns starting with an initial fixed metrical unit (ṭawīl, wāfir, mutaqārib et hazağ) and those beginning with a free position or two interdependent free positions (kāmil, basīṭ, sarī', ḫafīf and ramal). The case of formulas beginning with li-man is of utmost significance: if the following noun is not preceded by the definite article, the verse-pattern belongs to the first class; otherwise, that is if the noun is preceded by the definite article, it belongs to the second class. Likewise, the noun following 'a-min can begin with a long syllable or with a short one. In the first case, the verse-pattern starts with a stable metrical unit (wāfir, ṭawīl or mutaqārib). In the other case, it is one of the basīṭ or sarī' verse-patterns.

7 (1)
Another formula regularly employed in ḏikr al-aṭlāl, usually to introduce the nasīb proper, that is the remembrance of the beloved, will help us deepen the study of formulaic paradigms. The poet, after a short presentation of the deserted encampment of the beloved's tribe, ponctuates his discourse and says: 'I stopped there', waqaftu fī-hā, waqaftu bi-hā or wuqūfan bi-hā, as in the fifth verse of Imru' al-Qays's Mu'allaqa, which appears under (5) below: 9(5) wu-qū-fan bi-hā ṣaḥ-bī 'a-lay-ya ma-ṭiy-ya-hum

[∪ -] - [∪ -] - [- ∪ -] ∪ [∪ - ∪ -] [∪ -] - [∪ -] - [- ∪ -] ∪ [∪ - ∪ -]
ya-qū-lū-na lā tah-lik 'a-san wa-ta-ğam-ma-li

The formula waqaftu bi-hā is metrically and semantically similar to the previous one, as can be seen in line (6): 10 (6) wa-qaf-tu bi-hā min ba'-di 'iš-rī-na ḥiğ-ğa-tan

[∪ -] ∪ [∪ -] - [- ∪ -] - [∪ - ∪ -] [∪ -] - [∪ -] - [- ∪ -] ∪ [∪ - ∪ -]
fa-la'-yan 'a-raf-tu d-dā-ra ba'-da ta-wah-hu-mi The quantitative structure of this second formula (∪-∪∪ -) is metrically ambiguous, so that it can be used not only in a line of ṭawīl, as shown in ( 6), but also at the beginning of lines of wāfir and mutaqārib. This possibility is illustrated by lines ( 7) and (8): 11

(7) wa-qaf-tu bi-hā l-qa-lū-ṣa-ʿa la-k-ti-'ā-bin

[∪ -] ∪ ∪ [- ∪ -] ∪∪ [- ∪ - -] [∪ -] ∪ ∪ [- ∪ -] -[- ∪ - -]
wa-ḏā-ka ta-fā-ru-ṭu š-šaw-qi-l-mu 'an-nī (8) wa-qaf-tu bi-hā 'u-ṣu-lan mā tu-bī-nu

[∪ -] ∪ [∪ -] ∪ [∪ - - ∪ - -] [∪ -] ∪ [∪ -] - [∪ - - ∪ - -] li-sā- 'i-lu-hā-l-qaw-la 'il- lā si-rā-rā
Moreover, by means of a slight modification, the same formula can fit other verse-patterns, that of kāmil for example, where an initial conjunction (fa-) should be added and the preposition bichanged to fī. The resulting formula is fa-waqaftu fīhā, as in line (9): 12

(9) fa-wa-qaf-tu fī-hā kay 'u-sā-'i-lu-hā

∪∪ [-∪ -] -[- ∪ -] [∪∪ -] - [- ∪ -] ∪∪ [- ∪ -] [- -]
ġaw-ğa l-la-bā-ni ka-miṭ-ra-qi-n-nab-'i

The formula of line (9) can also be employed, after conjunction -fa has been deleted, with verse-patterns of basīṭ, as in the second line of al-Nābiġa al-Ḏubyānī's Mu'allaqa which is reproduced under (10): 13 (10) wa-qaf-tu fī-hā 'u-ṣay-lā-nan 'u-sā-'i-lu-hā

- [- ∪ -] - [∪ -] - [- ∪ - ∪ ∪ -] - [- ∪ -] - [∪ -] - [- ∪ - ∪ ∪ -]
'ay-yat ğa-wā-ban wa-mā bi-r-rab-'i min 'a-ḥa-di 11 In order to fit a formula to various verse-patterns, poets resort to a very simple process, which consists in adding such words as the conjunctions waand fa-, the particule qad and its variants laqad, wa-qad, fa-qad, wa-laqad. Particles such as 'inna, 'innī 'as for myself', fa-'inna 'and as for...' and 'ammā 'as for...' should probably be added to this first list. I will call them "stop-gaps", because they do not modify the meaning of the line fundamentally, except for its modal aspect, as happens with negation and interrogative pronouns. Such a typical introductory formula as bāna l-ḫalīṭu 'the company has disappeared', which is usually employed with basīṭ verse-patterns, can also appear with wafīr, by adding 'a-lā, i.e. vocative and negation, as shown by lines ( 11) and ( 12), both composed by the same poet:14 (11) bā-na-l-ḫa-lī-ṭu wa-lam yū-fū bi-mā 'a-hi-dū

- [- ∪ -] ∪ [∪ -] - [- ∪ -] [∪ ∪ -] - [- ∪ -] ∪ [∪ -] - [- ∪ -] [∪ ∪ -]
wa-zaw-wa-dū-ka-š-ti-yā-qan 'ay-ya-tan 'a-ma-dū

(12) 'a-lā bā-na-l-ḫa-lī- ṭu wa-lam yu-zā-rū [∪ -] - [- ∪ -] ∪ ∪ [- ∪ - -] [∪ -] ∪∪ [- ∪ -] ∪ ∪ [- ∪ - -]
wa-qal-bu-ka fī-ẓ-ẓa-'ā-'i-ni mus-ta-'ā-ru

While drawing up the inventory of formulas, we will have to deal with these particles, which [START_REF] Zwettler | The Oral Tradition of Classical Arabic Poetry, Colombus[END_REF], in his analysis of Imru' al-Qays's Mu'allaqa, deals with just as if they were ordinary formulaic components, neglecting therefore their very crucial metrical function. The case of laqad or wa-laqad followed by a perfect verb is obviously different from that of particles such as ka-'anna 'as if', which possess an important thematic function, that of bringing in a comparison. Of course, shades of meaning should be carefully examined, so that only particles that do not noticeably modify the meaning of the line be called "stopgaps". Although Parry (1928) originally defined the formula in a very restrictive way, the range of this notion was progressively widened, so as to include more or less closely related "formulaic expressions". According to Zumthor (1982: 117), "rather than to the lexical items themselves, we now attach importance to structuring factors such as prosody, syntax or distribution of key-words". For [START_REF] Nagler | Spontaneity and Tradition: A Study in the Oral Art of Homer[END_REF], a formula is a "Gestalt" which constitutes, in the poet's mind, the underlying model of a set of formulaic expressions related by rhythmical, phonetic, syntactic, lexical or semantic correspondences. Since formulaic style has much to do with meter and rhythm, it can be considered a part of "inner metrics", as opposed to "outer metrics". According to O'Neill (1942: 105, footnote 2), "the outer metrics establishes the syllabic framework within which the poet composes words into lines"; as far as Arabic metrics is concerned, the results of the analysis of "outer metrics" have been summed up in Tables 1 and2. By contrast, "inner metrics" can be defined as the analysis of the rhythmic structure of words inside verse-patterns: that is to say, it has to do with the interaction between the metrical structure and the linguistic structure of lines, including all levels of linguistic organization (phonology, including stress patterns, morphology, syntax, lexicon and semantics). In sum, "inner metrics" is the rhythm of verse-instances  what Sauvanet (1992) defines as a "moving periodic structure" marked out by quantitative meter and rhyme. The verse-pattern (meter), a more or less fixed sequence of short and long syllables, defines the metrical structure of the line, whereas rhyme marks out the end of a period and the beginning of the following one, as cadence does for Western classical music. This periodic structure, common to all the lines of a poem, is "moved" by the changing linguistic rhythm of words and groups of words, which varies from line to line. In a way, each line can be considered as a "variation" (in its musical meaning) of the periodic structure; and the understanding of poetic rhythm implies a detailed analysis of all variations of a given versepattern. As I try to show below, formulas play an important part in these rhythmical variations, so that we have to pay attention to paradigmatic variants of proper formulas, but also to the enlarged field of the formulaic techniques and to what we may call "rhythmical formulas", i.e. combined metrical and linguistic patterns that underlie a significant number of "formulaic expressions".

In what follows, I will mainly focus on the combination of versepatterns and word-stress patterns, in order to characterize a set of recurrent rhythmical formulas and to show how they combine with each other in a small number of prototypical verse-instances. I will just outline here the main features of this analysis, which should of course be developed into a large-scale analysis if we want to determine to what extent the prototypes defined play a significant role in poetic practice.

Under its phonetic aspect, stress relies on the prominence of one accented unit (syllable) within a sequence of syllables grouped into an accentual unit (word). At the production level, it involves one or more of prosodic parameters, intensity, frequency and duration; in Arabic, accent is usually marked by a peak of frequency, which may be reinforced by a peak of intensity. In any case, stress does not induce lengthening, and this can easily be explained by the fact that vowel length is an important distinctive feature of Arabic phonology and morphology. Finally, in a sentence or in a line, "the succession of prominent and non-prominent syllables creates a rhythm which is determined by the temporal distance between two stressed syllables" (Boulakia 1995: 341). Stress therefore contributes to organizing discourse into rhythmic units.

Modern standard Arabic and a great majority of contemporary Arabic dialects share the following word-stress assignment basic principles (the examples chosen belong to modern standard Arabic)15 : Although we do not have any direct evidence on stress assignment in ancient and classical Arabic, I will assume here that it followed the same rules. 16As far as verse is concerned, we first notice, at the end of lines and hemistichs, systematic regularities due to the conjunction of stressassignment principles, quantitative stability of verse-endings and rarity of enjambment. Consequently, the rhythmical patterns of verse-endings are few in number: [x -* -] for ṭawīl-1, ṭawīl-3, wāfir and kāmil-2 ; [(∪) -* ∪ -] for ṭawīl-2 and kāmil-1 ; and [X* -] for the four basīṭ verse-patterns, kāmil-3 and kāmil-2b, that is to say three different patterns for all long verse-patterns of the four main meters.

Let us consider here the case of ṭawīl-2 : the last word-stress of both hemistichs is almost always associated with the antepenult metrical position. The only exception, which is rather rare, concerns the case where the last word has two syllables only. In such a case, the first syllable of the word, which corresponds to the penult position of the hemistich, bears stress. The association of the ninth position of the hemistich with a stressed syllable can also be considered very frequent. Therefore, the percentage of hemistichs having the final metrical and accentual patterns given in (13) seems to be very high:

* * (13) [∪ -] ∪ [∪ -] - [- ∪ -] - [∪ - ∪ -]
The predominance of this pattern is correlated to the use of characteristic formulas, as is the case of these prepositional groups where the preposition ignored syllable, or that they considered ḥarf a more convenient notion for their purpose. But it can't serve as an argument to demonstrate that there are no syllables in classical Arabic. Although we don't know anything about stress assignment in ancient and classical Arabic, I believe that the rules presented above also applied. Contrary to other Semitic languages, and contrary to contemporary Arabic dialects, where accent causes processes of vowel reduction and vowel deletion, literary Arabic seems to be much more conservative: all vowels are perfectly preserved, so that syllabic structure does not change. According to [START_REF] Diakonoff | Yaziki drevney peredney Azii [Languages of Ancient Near East[END_REF], it is the absence of stress that accounts for the absence of vowel reduction in Classical Arabic, whereas vowel reduction in Hebrew, Aramaic, Ethiopian and modern arabic dialects occurs under the influence of stress. But the nature and use of the Arabic literary language can be opposed to this argument: the use of this koinè is restricted to literary compositions, which is a guarantee of stability. As for vowel deletion, examples can be found in the ancient Eastern Arabic dialects. In a good number of nominal forms, an unstressed short vowel is usually erased: watdun for watidun (stick), 'aḍdun for 'aḍudun (harm). Finally, it must be noticed that in Modern Literary Arabic, vowel reduction also remains exceptional, though the existence of word stress can't be denied. For all these reasons, I believe that Arabic always had word stress, though its nature and function might have changed through the ages. It seems that Semitic stress was a strong expiratory stress, marked by a prominence of intensity, and it might have been the case, also, in Arabic, where this strong stress might afterwards have progressively been « weakened » and changed into a prominence of frequency, losing its metrical function throughout this process. In what follows, stressed syllables will be marked with an asterisk (*).

governs two nouns linked by coordination or annexion, or a noun followed by an adjective. Line ( 14) illustrates the first and the last cases, in the second and first hemistich, respectively17 .

(

) * * * * * [∪ -] ∪ [∪ -] - [- ∪ -] - [∪ - ∪ -] 14
li-man ṭa-la-lun miṯ-lu-l-ki-tā-bi-l-mu-nam -ma -qi

* * * * * [∪ -] ∪ [∪ -] - [- ∪ -] - [∪ - ∪ -]
ḫa-lā 'ah-du-hū bay-na-ṣ-Ṣu-lay-bi fa-Muṭ -ri -qi

In these two examples, the preposition (bayna, miṯlu) is disyllabic and the complete formula has nine syllables. Such a structural formula is quite frequent, though a little bit less than formulas having seven or eight syllables, depending on the type of preposition (monosyllabic or disyllabic) and the morphological structure of nouns and adjectives employed. Let us line (15):18

* * * * * [∪ -] ∪ [∪ -] - [- ∪ -] - [∪ - ∪ -] (15)
'a-raf-tu li-Lay-lä bay-na Waq-ṭin fa-Øal-fa-'i

* * * * * [∪ -] ∪ [∪ -] - [- ∪ -] - [∪ - ∪ -]
ma-nā-zi-la 'aq-wat min ma-ṣī-fin wa-mar-ba-'i

The underlined formulas each have eight syllables and, though the preposition is either disyllabic (bayna) or monosyllabic (min), they both have the same stress pattern. And such is the case of the noun phrases listed in ( 16): Although the morphological structure and syntactical function of these examples are different, they all share the same metrical structure (the last eight positions of a hemistich of ṭawīl-2) and the same stress pattern. Moreover, they are all composed of two four-syllable units, the second one having one stress, and the first one having one (dawāfi'u) or two stresses (bayna Waqṭin), so that the complete formula has two or three stresses which always fall in the same metrical positions. The rhythmical shape of these formulas is shown in figure (17), where metrical positions which coincide with the formula are the last eight of the hemistich and where the facultative initial stress is put between brackets.

(*) * *

(17

) [∪ -] x [∪ -] x [-∪ -] x [∪ - ∪ -]
A certain number of formulas allow us to determine another paradigm, with seven syllables, where word-stresses fall in the same metrical positions as in the octosyllabic formulas above. All these heptasyllabic formulas have two stresses, corresponding to a three-syllable word and a four-syllable word, or vice versa, as in the two types of formulas listed in ( 18) and ( 19): (24

) [∪ -] -[∪ -] ∪ [-∪ -] -[∪ - ∪ -]
ka-rağ-'i-l-wu-šū-mi fī ẓu-hū-ri-l-'a-nā-mi-li

It appears these initial six-syllable formulas are constructed under the model of introductory formulas of the type 'araftu d-diyāra 'You recognized the abodes' or 'araftu li-Laylā 'You recognized, from Laylā...'. These few formulaic paradigms enable us to define three types of prototypical verse-instances of ṭawīl-2, with a break ($) after the fifth, the sixth and the seventh metrical position, respectively. A break after the fifth position is often reinforced by another break after the seventh, as in line ( 21) above. These three prototypical verse-instances are represented in ( 25), ( 26) and ( 27

): * * * * * (25) [∪ -] x [∪ -]$ x [-($) ∪ -] x [∪ - ∪ -] * * (*) * * (26) [∪ -] x [∪ -] x $ [-∪ -] x [∪ - ∪ -] * * * * (27) [∪ -] x [∪ -] x [-$ ∪ -] x [∪ - ∪ -]
The frequency of these prototypes and of all the types of formulas that were quoted up to now have to be further determined, through a statistical analysis of a large number of poems. First, a hemistich with a break after the sixth or the seventh metrical position does not necessarily imply the use of formulas such as those listed above. Secondly, a certain number of lines, the proportion of which also has to be determined, do not allow a medial break, as in examples ( 28), ( 29) and (30), which exhibit similar structural formulas in medial position:

21 * * * * (28) [∪ -] -[∪ -] -[-∪ -] ∪ [∪ --] li-Hin-din bi-ḥiz-zā-ni-š-Ša-rī- fi ṭu-lū-lu 20 (
) [∪ -] -[∪ -] -[-∪ -] ∪ [∪ --] li-Hin-din bi-'a'-lā-mi-l-'A-ġar-ri ru-sū-mu * * * * (30) [∪ -] -[∪ -] -[-∪ -] ∪ [∪ - ∪ li-Sal-mā bi-šar-qiy-yi-l-Qa-nā-ni ma-nā-zi- lu 29
It is also worth noting that lines with an initial five-syllable formula often conform to a ternary rhythmical pattern which recalls the case of Greek dactylic verses with no (masculine or feminine) caesura, in that they are composed of three progressive rhythmical groups. Examples ( 31) and ( 32) illustrate this kind of ternary rhythm:

22 * * * * (31) [∪ -] -[∪ -] -[-∪ -] ∪ [∪ - ∪ -]
'a-fā Taw-'a-mun min 'ah-li-hī fa-Ğu-lā-ği luh

* * * * (32) [∪ -] -[∪ -] -[-∪ -] ∪ [∪ - ∪ -]
'a-fā Miğ-da-lun min 'ah-li-h¬ fa-Mu-tā-li-'u

The three rhythmic units of these lines respectively have five, four and five syllables. Another case of ternary hemistich is shown in examples (33) to (35), where the underlined formula is a variant of ḏikr al-aṭlāl introductory formulas with the verb 'arafa: 23

* * * * * (33) [∪ -] ∪ [∪ -] -[-∪ -] -[∪ - ∪ -]
fa-la'-yan 'a-raf-tu-d-dā-ra ba'-da ta-wah-hu-mi

* * * * * (34) [∪ -] ∪ [∪ -] -[-∪ -] -[∪ - ∪ -] fa-lam-mā 'a-raf-tu-d-dā-ra qul-tu li-rab-'i- hā 22 (
(35) [∪ -] ∪ [∪ -] -[-∪ -] -[∪ - ∪ -]
fa-lam-mā wa-rad-na-l-mā-'a zur-qan ği-mā-mu-hū

The same rhythmical formula is also currently employed at the beginning lines of wāfir, as shown by example (36):

24 * * * * (36) [∪ -] -[-∪ -] ∪ ∪ [-∪ --]
fa-lam-mā 'an ra-'ay-tu ba-nū lu-'ay-yin

* * * * [∪ -] - [- ∪ -] ∪ ∪ [- ∪ - -]
'a-raf-tu-l-wud-da wa-n-na-sa-ba-l-qu-rā-bā

* * * * [∪ -] - [- ∪ -] - [- ∪ - -]
ra-fa'-tu-r-rum-ḥa 'iḏ qā-lū qu-ray-šun

These occurrences perfectly illustrate the versatility of certain structural formulas. Indeed, the same formula is used in lines of kāmil, as is the case in wa-la-qad qa-ṭa'-tu-l-waṣ-la yaw-ma ḥi-lā-ği-hī

* * * * * ∪ ∪ [- ∪ -] ∪ ∪ [- ∪ -] - [- ∪ -]
wa-'a-ḫu-ṣ-ṣa-rī-ma-ti fī-l-'u-mū-ri-l-muz-mi-'u

In these two hemistichs, the formula is preceded by the particle laqad, itself preceded by the conjunction wa-. This pattern is extremely frequent: for an example, it appears eight times within the forty-five lines of this poem. Followed by a verb in the perfect, laqad only underlines the fact that the action is definitely completed, and therefore does not modify the meaning substantially.

4 4 4 4. . .

. Conclusion Conclusion Conclusion Conclusion

The combination of verse-patterns and formulas appears to play a main role in the oral-formulaic composition of ancient Arabic poetry. In that respect, the formulaic density of the opening lines of a poem is extremely significant.

In the course of an oral performance, the poet comes into contact with his audience by producing certain signals which belong to a common code. Among these, the choice and identification of a particular rhythm, through the use of specific formulas matching a particular verse-pattern, seem to fulfil a very important constructive function. The formula, subject to variations such as those presented in the first part of this paper, certainly helps the poet to establish a rhythm and helps the audience to identify it. This is the reason why I have paid special attention to the first lines of poems and, as a particular but exemplary case, that of ḏikr al-aṭlāl. But this constructive function should be further examined, through a large-scale analysis of the corpora. First of all, a complete database containing all lines of ancient poetry that have been brought down to us should be constituted. All lines should then be tagged, so that specific linguistic and stylistic features could be automatically identified. As far as proper formulas are concerned, their recognition does not raise any problem. As for rhythmical formulas, I propose to equal them to combined metrical and accentual patterns which may include word boundaries, as well as some morphological and syntactical features, such as the structure of the phrase, the form or tense of verbs, the use of such specific particle, etc. As for an example, formulas like 'araftu d-dāra and qaṭa'tu l-waṣla could be both represented as: (38) [∪ -* -+ -* ∪; V, +Pf, 1sg] + [N, +def] All formulas could therefore be progressively grouped into paradigms, from the most abstract, a combination of metrical and accentual patterns, to the most concrete, proper formulas, where lexical items should themselves be specified. Syllabification and identification of verse-patterns can now be easily processed, as shown by [START_REF] Bohas | Towards a systematic corpus analysis of Arabic poetry[END_REF]. As for stress, it relies on a quite simple quantitative principle, and it should therefore be possible to assign correct word-stress patterns automatically, provided that word boundaries have been marked previously.

To conclude, let us say that the detailed analysis of poetic techniques (meter, formulaic style, lexicon, etc.) should not only help us to better understand the process of poetic creation, but also to throw a new light on the history of literary forms and techniques in ancient Arabia.

  ancient Arabic poetry patterns of ancient Arabic poetry patterns of ancient Arabic poetry patterns of ancient Arabic poetry

  style of ancient Arabic poetry The formulaic style of ancient Arabic poetry The formulaic style of ancient Arabic poetry The formulaic style of ancient Arabic poetry

9 ( 5 )

 5 Ibn al-Anbārī (1964: 25) : 'And my comrades, stopping their mounts close to me and telling me : Don't let sadness overwhelm you ; get over your pain !' This line also appears in Ṭarafa's Mu'allaqa with a different rhyme, so that the last word (tağammali) is replaced by another one (tağalladi) which has the same meaning. 10 (6) Zuhayr b. Abī Sulmā (1992: 35, line 4) : 'I stopped there, after twenty pilgrimages [years], and I could hardly recognize the abode, unless in imagination.' The poem to which this line belongs is one of the famous Mu'allaqāt.

  7) Nābiġa al-Ḏubyānī (al-) (1985: 125, line 3) : 'I stopped there, [mounting] my young shecamel, and I was plunged into affliction ; this is how one is seized by the pain of passion.' ; (8) Mufaḍḍal al-Ḍabbī (al-) (1976: 412, line 4) : 'I stopped there, at daybreak, and [the abandoned abodes] didn't give me any answer, only lines [drawn as can be on a backhand].' 12 (9) 'Abd al-Ğalīl (1977: 220, line 6, kāmil-3 : 'I stopped there, in order to question them, [mounting a horse] with a large breast, as [skinny] as a stick of nab' [wood].' 13 (10) Nābiġa al-Ḏubyānī (al-) (1985: 14, line 2): 'I stopped there, at daybreak, to question [the abodes]; they tried to answer, but there was nobody left.'

  (a) Stress assignment is fixed by word boundaries, i.e. stress-bearing units are words possibly augmented with one or more clitics. (b) The domain of stress assignment is limited to the last three syllables of the word. (c) The last syllable of the word bears stress if it is superheavy (Cvxc): muslimūn 'muslims', kitāb 'book', banāt 'girls'. (d) If (c) does not apply, the penult syllable bears stress if it is heavy (long, Cvx) or superheavy (extra-long, Cvxc), or if the word contains two syllables only : katabtu 'I wrote', yaqūlu 'he says', bādartu 'I undertook', mahāmmun 'missions', kamā 'as', kātib 'writer'. (e) If neither (c) nor (d) apply, the antepenult syllable bears stress : 'al-kutubu 'the books', kutubu-hu 'his books', kitābu-hum 'their book', kitābu-humā 'their book' (dual).

  fī ẓuhūri l-'anāmili 'On the fingers' back' (Ğabbūrī (al-) 1982: 212, line 1) (b) fa-r-Rusaysu fa-'Āqiluh 'And al-Rusays and 'Āqil' (Zuhayr b. Abī Sulmā 1992: 114, line 5) (c) Raḥraḥāni fa-Rākisā 'Raḥraḥān and Rākis' ('Abbās b. Mirdās (al-) 1968: 68, line 1) (d) fa-ṭ-ṭilā'u d-dawāfi'u 'And the torrent running down the valley' (Nābiġa al-Ḏubyānī (al-) 1985: 30, line 1) (e) Ḏū kulāfin fa-Munkifu 'Ḏū Kulāf and Munkif' (Ibn Muqbil 1962: 189, line 1)

  bi-Ḏāti s-Salāsili 'At Ḏāt al-Salāsil' (Ğabbūrī (al-) 1982: 212, line 1) (b) wa-rasmu manāzilin 'And the traces of the abodes' (Šammāḫ b. Ḍirār (al-) 1968: 211, line 1) (c) wa-nu'yan muhaddamā 'And a destroyed channel' (Ḥātim al-Ṭā'ī 1990: 220, line 1a) (d) kitāban munamnamā 'An adorned book' (Ḥātim al-Ṭā'ī 1990: 220, line 1b) (19) (a) bi-burqati Ṯahmadi 'On the hard and rocky ground of Ṯahmad' (Ṭarafa b. al-'Abd 1975: 6, line 1) (b) bi-ḥarrati Darġadi 'In the gloomy plain of Darġad' ('Abīd b. al-Abraṣ 1913: 78, line 1)To all these formulas correspond formulas matching the beginning of the hemistich, which count five, six or seven syllables. The first type has two words, one disyllabic word and one three-syllable word, as in the introductive formula li-man ṭalalun. The examples listed in (20) are takenCombined with eight-syllable final formulas, they constitute a complete halfverse, as can be seen in line (24):

  16) Ğabbūrī (al-)(1982: 212, line 1b) : 'Which resemble the lines of a tattoo on the backhand.' 21 (28) Ṭarafa b. al-'Abd (1975: 81, line 1, ṭawīl-3): 'To Hind [are] the abodes which twinkle on the barren ground of al-Šarīf'; (29) Labīd b. Rabī'a (1970: 95, line 1, ṭawīl-3) : 'Of Hind, on the heights of al-Aġarr, traces [remain]'; (30) Zuhayr b. Abī Sulmā (1992: 213, line 1, ṭawīl-2): 'To Salmā, East of al-Qanān, do belong abodes and traces'.

  a) Ḥuṭay'a (al-) (1958: 131, line 1a): 'Taw'am has been abandoned by its inhabitants, and so for Ğulāğil' (b) 'Abbās b. Mirdās (al-) (1968: 80, line 1a): 'Miğdal has been abandoned by its inhabitants, and so for Mutāli''. 23 Zuhayr b. Abī Sulmā (1992: 35, line 4b): 'I hardly recognized the abode, after I had [so often] imagined it'; Zuhayr b. Abī Sulmā (1992: 36, line 6a) : 'And when you recognized the [place of the] encampment, you addressed yourself to its abodes and said: [...]' ; Zuhayr b. Abī Sulmā (1992: 39, line 15a) : 'And when we reached the waterplace, [we discovered] its blue surface'.

  ∪ ∪ [-∪ -] -[-∪ -] ∪ ∪ [-∪ -]

The genuineness of ancient Arabic poetry was radically contested by[START_REF] Margoliouth | The Origins of Arabic Poetry[END_REF] and ṬahaḤusayn (1926, 1927), who relied on historical and contextual arguments mainly, and thus neglected the analysis of the poems themselves. On the contrary,Blachère (1952Blachère ( - 1966)), taking the linguistic, metrical and stylistic detailed analysis of the poems as a startingpoint, and submitting them to a drastic critical examination, tends to consider what was brought down to us as representative, on the whole, of the ancient poetic tradition. This point of view does not rule out the existence of forgeries and distortions. But specialists now consider that the problem of genuineness can only be resolved step by step, through a careful analysis of each line and each poem, and after the whole corpus has been submitted to a detailed textual criticism

. 2 Between the I st century B.C. and the III rd century A.D., Palmyrenians and Nabateans used local variants of imperial Aramean, whereas their native tongue was probably Arabic. For what concerns the inscriptions of Qaryat al-Faw and al-Namāra, see especially Robin (1991). Before the inscriptions of Qaryat al-Faw (Saoudi Arabia) written in Sabean script (II nd century B.C.) were discovered, the inscription (in Nabatean script) of al-Namāra (Syria), a funeral

stela dedicated to a certain Imruʾ al-Qays, 'king of all the Arabs', dated 328 A.D., had long been considered the oldest written record ofArabic. 3 This inscription, discovered in Yemen (1973), was written down at the end of the first century A. D. Its twenty-seven lines are rather short and almost equal in length, and they all end with the same two rhyming letters (ḥ-k). The precise meaning of this hymn dedicated to the sun (šams) is rather uncertain. A lot of textual problems remain, due to the fact that the language in use, neither Arabic nor South Arabian, has not yet been attested elsewhere. For a reproduction and short presentation, seeRobin (1991:122-125). 4 The only exception concerns rağaz verse-patterns (Rj), which constitute a specific metrical class, as well as the rare basīṭ mağzū' (Bm).

X [-∪ -] X [-∪ -] ///// X [-∪ -] X [-∪ -] X [-∪ -] ///// (18) K-2 X [-∪ -] X [-∪ -] X [-∪ -] ///// X [-∪ -] X [-∪ -] X [--] ///// (19) K-2b X [-∪ -] X [-∪ -] [∪ ∪ -] ///// X [-∪ -] X [-∪ -] X [--] ///// (20) K-3 X [-∪ -] X [-∪ -] X [-∪ -] or [∪ ∪ -] ///// X [-∪ -] X [-∪ -] [--] ///// (21) Km-1 X [-∪ -] X [-∪ -] ///// ///// X [-∪ -] X [-∪ --] ///// ///// (22) Km-2 X [-∪ -] X [-∪ -] ///// ///// X [-∪ -] X [-∪ -] ///// ///// (23) Ks X [-∪ -] X [-∪ -] ///// ///// ///// ///// ///// /////

The poet is facing the deserted encampment of his beloved's tribe and the evocation of the encampment logically leads to the description of the beloved herself. Whether ḏikr al-aṭlāl must be considered as a part of the nasīb or not remains under question, since in some ancient poems, it is immediately followed by raḥīl or ḥikma. For further discussion, see R.[START_REF] Jacobi | The Origins of the Qasida Form[END_REF] for example.

(11) Bišr b. AbīḪāzim (1960: 54, line 1): 'The company has disappeared, not respecting her word, sharpening your burning desire wherever they headed for.' ; (12) Mufaḍḍal al-Ḍabbī (al-) (1976: 338, line 1) : 'Alas ! The company disappeared, before they were visited, and your heart has gone away with the palanquins.'

See, for example,Kouloughli (1976: 124-125). I agree with[START_REF] Bohas | Processus accentuels en arabe[END_REF], who reject the rules presented byWright (1981: 27-28) and taken for granted by most contemporary English and American linguists. These rules wrongly assign stress to the first syllable of the word if the penult and the antepenult are short.

The fact that Arab grammarians did not say a word about stress cannot be considered a valid argument to show that there was no word stress at all in classical Arabic. Arab grammarians didn't care about prosodic phenomena as a whole. And they also ignored syllable. But can one say that there is no syllable in Arabic or in English just because the Arab grammarians or the authors of Sound Pattern of English did not say a word about it? The traditional phonetic and metrical analysis of the Arab grammarians relies on a minimal unit, the ḥarf, which is smaller than the syllable. This theoretical choice does only mean that they

(13) Salāma b. Ğandal (1968: 153, line 1) : 'To whom do the abodes belong, resembling an adorned book, whose time has past, between al-Ṣulayb and Muṭriqi?'

(14) Ṭufayl al-Ġanawī (al-) (1968: 103, line 1): 'I recognized, between Waqṭ and Ḍalfa', the abodes of Laylā, deserted encampments of springtime and summertime.'

(15) Ğabbūrī (al-)(1982: 212, line 1a): 'To whom are the vanishing traces at Ḏāt al-Salāsil ?'

Mufaḍḍal al-Ḍabbī (al-) (1976: 315, lines 14 and 15a): '(14) And when I looked at the sons of Lu'ayy, I suffered passion because of close ties of kinship; (15a) I raised [my] spear when they said "Qurayš" [...]'.

Mufaḍḍal al-Ḍabbī (al-) (1976: 49, line 4): 'I broke off [our] liaison the day when discord [became stronger]; he who is being prompt in his decisions is a man of strength and perseverance."

Such formulas can ideally be with nine-syllable final formulas, as in the two hemistichs of line ( 14) above: li-man ṭalalun + miṯlu l-kitābi lmunammaqi # ḫalā 'ahduhū + bayna ṣ-Ṣulaybi fa-muṭriqi.

In other, more frequent cases, the final formula has seven syllables, as in the examples mentioned above, and a disyllabic word occupies the sixth and seventh positions. In many of the lines starting with li-man ṭalalun, the initial formula is followed by the verbs 'aqwā 'to be deserted' or 'afā 'to erase' or, as in line ( 21), by the active participle of ʿafā, viz. ʿāfin:

li-man ṭa-la-lun ʿā-fin bi-ḏā-ti-s-Sa-lā-si-li

A second type of formula has six syllables, generally divided into two threesyllable words which bear stress on the penult, as shown in figure (22).

The following examples are taken from the same two poems of Zuhayr b. Abī Sulmā (1992).