Alexandre Bergel
email: bergel@iam.unibe.ch

Stéphane Ducasse
email: ducasse@iam.unibe.ch

Roel Wuyts
email: wuyts@iam.unibe.ch

Classboxes: A Minimal Module Model Supporting Local Rebinding Published in JMLC'03 Best Award Paper

Keywords: Language Design, Method Lookup, Modules, Smalltalk, Class Extension, Selector Namespace

Classical module systems support well the modular development of applications but do not offer the ability to add or replace a method in a class that is not defined in that module. On the other hand, languages that support method addition and replacement do not provide a modular view of applications, and their changes have a global impact. The result is a gap between module systems for object-oriented languages on one hand, and the very desirable feature of method addition and replacement on the other hand. To solve these problems we present classboxes, a module system for object-oriented languages that provides method addition and replacement. Moreover, the changes made by a classbox are only visible to that classbox (or classboxes that import it), a feature we call local rebinding. To validate the model, we have implemented it in the Squeak Smalltalk environment, and performed experiments modularising code.

Modules in the Presence of Extensibility

The term module is overloaded. We follow the definitions of Modular Smalltalk [START_REF] Wirfs-Brock | An overview of modular Smalltalk[END_REF] and Szyperski [START_REF] Szyperski | Import is not inheritance -why we need both: Modules and classes[END_REF].

Modules are program units that manage the visibility and accessibility of names. A module defines a set of constant bindings between names and objects [START_REF] Wirfs-Brock | An overview of modular Smalltalk[END_REF]. A module is a capsule containing (definitions of ) items. The module draws a strong boundary between items defined inside it and items defined outside other modules [START_REF] Szyperski | Import is not inheritance -why we need both: Modules and classes[END_REF].

A class extension is a method that is defined in another source packaging entity (for example, a Java package or an Envy application [START_REF] Pelrine | Mastering ENVY/Developer[END_REF]) than the class it is defined for. There exist two kinds of class extension: a method addition adds a new method, while a method replacement replaces an existing method.

Classical module systems, like those of Modula-2 [START_REF] Wirth | Programming in Modula-2[END_REF], Modula-3 [START_REF] Cardelli | Modula-3 language definition[END_REF], Oberon-2 [START_REF] Mössenböck | Object-Oriented Programming in Oberon-2[END_REF], Ada [START_REF] Taft | Ada 9x: From abstraction-oriented to object-oriented[END_REF], or MzScheme's [START_REF] Findler | Modular object-oriented programming with units and mixins[END_REF] do not support class extensions. Numerous object-oriented programming languages, such as Java, C++, and Eiffel [START_REF] Meyer | Eiffel: The Language[END_REF] lack this facility. However, it is widely used in those languages that support it, such as Smalltalk [START_REF] Wirfs-Brock | An overview of modular Smalltalk[END_REF] and GBeta [START_REF] Ernst | Propagating class and method combination[END_REF]. In "Capsules and Types in Fresco" A. Wills reports that in the goody library1 goodies-lib@cs.man.ac.uk 73% of the files modify existing classes, and 44% define no new classes at all [START_REF] Wills | Capsules and types in fresco[END_REF]. Even if these figures should be tempered due to the fact that goodies are not industrial applications, these numbers reflect that class extensions are not an anecdotical mechanism. There is some ongoing research that explores the introduction of class extensions to Java (for example OpenClasses [START_REF] Clifton | MultiJava: Modular open classes and symmetric multiple dispatch for Java[END_REF], Keris [START_REF] Zenger | Evolving software with extensible modules[END_REF] or MixJuice [START_REF] Ichisugi | Difference-based modules: A class independent module mechanism[END_REF]), which is another indication that this is quite an important concept.

Languages supporting class extensions such as Smalltalk or Flavors do not offer the notion of modules. In these languages the changes are globally visible and impact the whole system. Even in module systems that support class extensions (Modular Smalltalk [START_REF] Wirfs-Brock | An overview of modular Smalltalk[END_REF]), changes are visible to everyone after they have been applied.

To summarise, module systems exist for languages that do not support class extensions on the one hand, and languages exist that support class extensions but not modules on the other hand. The Classbox model provides modules that fully support class extensions, and these extensions are only visible to the classbox that defined them. Outside the classbox the system runs unchanged. This is accomplished by redefining the method lookup mechanism to take classboxes into account, so that the desired method is executed.

For validation we implemented this system in Squeak, an open-source Smalltalk environment, and implemented some small applications. Section 3 describes one of these examples, an application to check dead links on a web page. Classboxes are used to extend an existing system with a visitor and to replace existing system code.

The rest of the paper is structured as follows. Section 2 presents an overview of the Classbox model. In Section 3 we illustrate the model by showing the implementation of an application to check for dead links on web pages. Section 6 concludes the paper.

Overview of the Classbox Model

This section describes the semantics of the Classbox model. The next section illustrates the semantics and usage on a concrete case-study highlighting its unique features.

Classbox contents. A classbox consists of imports and definitions:

-An import is either a class import (stating explicitly from which classbox the class is imported, called the parentbox ) or a classbox import (i.e., that imports every class from the imported classbox).

-A definition can be a class definition or a method definition. A method definition declares the class that a method belongs to, the name of the method, and the implementation of the method.

Static completeness. Methods can only be defined on classes that are known within the classbox (e.g., defined or imported). Furthermore, the implementation of a method can only refer to classes known in the classbox.

Extension. Extending a class C with one method m has the following semantics: if the class C has a method with the same signature as m, m replaces that method, otherwise m is added to C. Note that this implies that for the method lookup, importing takes precedence over inheritance (first the import chain is used, and then the inheritance chain). This is explained in Section 4.

Flattened classbox. A flattened classbox consists of the flattened definitions of all the classes (defined or imported) of that classbox.

Class name uniqueness. When defining or importing a class C in a classbox cb1, the name of C has to be uniquely defined in flattened C. This guarantees that class import cycles are not possible.

Method addition. Method m is a method addition for class C if m is a method defined for C, and the flattened definition of C in its parentbox does not define a method with the same signature as m.

Method replacement. Method m is a method replacement for class C if m is a method defined for C, and the flattened definition of C in its parentbox contains a method with the same signature as m. Following the definition of flattening, the method replacement takes precedence in the flattened version of C.

These rules ensure the following property, which we call local rebinding. Suppose a classbox cb1 defines a class C with two methods, m calling n, and classbox cb2 imports C from cb1 and replaces n. We say that cb2 locally rebinds n in cb1 to represent the fact that calling m in the context of cb2 invokes the method n as defined in cb2 while calling m in the context of cb1 invokes the method n as it is defined in cb1. The runtime semantics are illustrated in the next section and explained in Section 4.

The Running Example

To illustrate the key properties of the Classbox model we develop an application that allows one to check dead links on a web page. We use Squeak [START_REF] Ingalls | Back to the future: The story of Squeak, A practical Smalltalk written in itself[END_REF], an open source Smalltalk, to implement the Classbox model. The user specifies the web page to be checked and the application returns the list of URLs that cannot be reached within a given time-out.

Out of the box, the Squeak environment comes with a sophisticated development environment and a rich class library. All this code is contained in a single "image" within a single global namespace and consists of about 1800 classes. Squeak contains a HTML parser, a hierarchy of HTML nodes that are built by the HTMLParser and several network protocols.

To write our application we use the existing HTML parser to create a HTML tree of the web page for which we want to check the dead links. Then we walk this tree, checking whether each link can be reached. While these checks can be hardcoded as methods in the HTML parse tree itself, it is a common practice to write a visitor for the HTML parse tree which can be reused by other applications. Then we only need to write a specialised visitor that checks for dead links. Therefore, the implementation of our application consists of the definitions of two classboxes: one extending Squeak with a visitor for the HTML parse tree and one customising that generic visitor with one that checks for dead links. The resulting system is shown in Figure 2, and is explained in the next sections.

Class Import and Class Extensions

As shown in Figure 1, extending the HTML parse tree with a visitor consists in adding a new HTMLVisitor class, and adding one method to each existing HTML parse tree node to call the visitor. Since the visitor methods and the visitor class itself logically belong together, we group them in the same classbox called HTMLVisitor. with a single method to visit them (called acceptVisitor:). It also contains the HTMLVisitor class, that implements the abstract visitor class.

Illustrated Model Properties: Method Additions. The example shows that classboxes can be used not only to define whole classes (like the HTMLVisitor class); they can also define methods on classes that are imported (all the acceptVisitor: methods), i.e., classboxes support method additions [START_REF] Wirfs-Brock | An overview of modular Smalltalk[END_REF] [START_REF] Clifton | MultiJava: Modular open classes and symmetric multiple dispatch for Java[END_REF].

Without this feature it is very difficult to factor out the visitor in a separate classbox from the tree it operates on. In languages that do not support method additions, the solution would be to create visitable subclasses for every HTML node and add the visiting methods there. However this has two undesirable effects: first of all, the existing code that used the classes has to be changed to use the new subclasses, and second, other applications that need to make similar extensions would have to independently add the same subclasses. Class extensions do not exhibit either problem.

Illustrated Model Properties: Local Rebinding. The addition of the method acceptVisitor: to the HTML tree classes is only visible for code executed in the context of the HTMLVisitor classbox. Code running in the Squeak classbox cannot see this method addition. The next sections elaborate on this point.

Classbox Import and Method Replacement

With the HTMLVisitor classbox defined it becomes easy to implement the Link Checker application. It basically boils down to adding a subclass of HTMLVisitor that overrides the visitAnchor: method to implement the checking of dead links. Checking a link means opening a connection to the specified URL within a certain amount of time.

In practice it turns out that the class that actually builds the connection (the class Socket) does not throw exceptions when links are not reachable. Instead it directly opens a dialogue box explaining the error that was encountered! This makes it suddenly quite hard to implement the Link Checker. The solution would be to change the method that opens a dialogue box and let it throw exceptions instead. However, this also means that all the applications that use this method and rely on dialogue boxes to be opened have to be changed as well. While this may be a worthwhile endeavour that would result in a cleaner Squeak system, it is too much work when just writing a Link Checker. The solution is to change this method in such a way that it will throw exceptions only in the places where it is needed. All other places should still use the unchanged method. This is what is done by the LinkChecker classbox. How this works is explained in detail in Section 4.

Figure 2 shows the classbox LinkChecker. It imports the classbox HTMLVisitor, i.e., all classes defined in HTMLVisitor are imported and it imports class Socket from the Squeak classbox. The classbox LinkChecker defines a class LinkChecker, a subclass of HTMLVisitor, and a method visitAnchor: that implements the actual checking of the links contained in a HTML document. It also defines a method ping: on Socket that replaces the existing implementation that opens dialogue boxes with an implementation that throws exceptions. Illustrated Model Properties: Local rebinding. This example shows that a classbox allows one to replace methods for existing classes. Moreover, these changes are again local to LinkChecker: it is only in the LinkChecker classbox that exceptions are raised when network locations are not reachable. The rest of the system is unaffected by this change, and still gets dialogue boxes when time-outs occur.

Local rebinding and Flattening

This section elaborates how local rebinding in the presence of the flattening property allows a classbox to change the behaviour of methods in the system in such a way that these changes are local to the classbox.

To illustrate this we execute some expressions in the example described in previous sections. We execute an expression that creates an HTML parse tree for a certain url in two different contexts: first in the Squeak classbox then in the LinkChecker classbox.

HtmlParser parse: ('http://www.iam.unibe.ch/˜scg/' asUrl contents)

In the Squeak classbox, the result of this expression is a parse tree consisting of instances of HTMLEntity that cannot be visited. This is exactly the intended behaviour, as the expression is performed in the context of the Squeak classbox, and that classbox does not know anything about visitors for its parse tree.

In the LinkChecker classbox the same expression the result is a HTML parse tree that can be visited. Again, this is exactly what is intended since we imported the HTML parse tree nodes from HTMLVisitor (indicating that we want those classes to be used).

Runtime Semantics of the Model

Depending on the classbox an expression is executed in, objects can understand different messages or have methods with different behaviour. For this to work, a classbox-aware lookup mechanism for methods and a change in the structure of method dictionaries are needed. We focus on Smalltalk method dictionaries here, but the same approach holds for other object-oriented languages.

Normally, method dictionaries are used to lookup a key consisting of the signature of the method (in Smalltalk this is only the name, as there are no static types), and return a value corresponding to the method body. To support classboxes we encode the classbox where the method is defined in the method signature (i.e., the key). For example the method dictionary for HTMLEntity has entries prefixed with "#Squeak." for the methods defined in Squeak, and entries with "#HTMLVisitor." for the method additions defined in that classbox. The method dictionary for class Socket now has two entries for the ping: method: one for the Squeak classbox and one for the LinkChecker classbox. Class LinkChecker has only a single entry for the visitAnchor method.

Encoding the classbox with the method signature makes it possible to let different implementations for a method live alongside each other. However, to take advantage of this, the method lookup mechanism has to be changed as well. The algorithm first checks whether the class in the current classbox implements the selector we are looking for (lines 5 to 9). If it is found, the lookup is successful and we return the found method (line 9). If it is not found, we recurse. The algorithm favours imports over inheritance, meaning that first the import chain is traversed (in lines 12 to 18) before considering the inheritance chain (in lines 19 to 30). This last part is the difficult part of the algorithm, since we need to find the classbox where the superclass is defined that is closest to the classbox we started the lookup from. Therefore the algorithm remembers the path while traversing the import chain (line 12), and uses this when determining the classbox for the superclass (line 21).

Runtime Performance

As can be expected, introducing the classbox aware method lookup mechanism introduces some runtime overhead, especially since our current implementation is currently not optimised. Table 1 shows the results for some benchmarks that we performed to compare the regular method lookup performance vs. the classboxaware lookup performance:

1. sending a message defined in the class of the instance (10 millions times), and sending a message defined in a super class hierarchy (10 millions times). 2. measuring launching and closing of two applications implemented in Squeak (a web browser and an e-mail client) within the same classbox (average over 10 times). 3. performing a method call through a chain formed by classboxes extending a class.

The table shows that the penalty for the new lookup scheme by itself is roughly 25 percent, where the real-world applications run about 60 percent slower. We think that this difference is due to the fact that we did not adapt the method cache in the virtual machine.

Note that our current implementation is straightforward and does not incorporate any optimisations yet. For example we are thinking of changing the structure of the method cache in order to take classboxes into account.

Related Work

No existing mainstream language supports class extensions, modules, and local rebinding. Classical module systems, like those of Modula-2 [START_REF] Wirth | Programming in Modula-2[END_REF], Modula-3 [START_REF] Cardelli | Modula-3 language definition[END_REF], Oberon-2 [START_REF] Mössenböck | Object-Oriented Programming in Oberon-2[END_REF], Ada [START_REF] Taft | Ada 9x: From abstraction-oriented to object-oriented[END_REF] or Java, do not support class extensions.

Keris introduces extensible modules which are composed hierarchically and linked implicitly. Keris does not support class extension [START_REF] Zenger | Evolving software with extensible modules[END_REF]. MzScheme's units are modules system with external connection facilities [START_REF] Findler | Modular object-oriented programming with units and mixins[END_REF], and act as components that can be instantiated and linked together. They do not support class extensions. Classboxes on the other hand, are source code management abstractions.

OpenClasses [START_REF] Clifton | MultiJava: Modular open classes and symmetric multiple dispatch for Java[END_REF] supports a modular definition of class extensions but only supports method addition and not method replacement. MixJuice [START_REF] Ichisugi | Difference-based modules: A class independent module mechanism[END_REF] offers modules based on a form of inheritance which combines module members and class extensions but not local rebinding.

Modular Smalltalk only supports method additions that are globally visible [START_REF] Wirfs-Brock | An overview of modular Smalltalk[END_REF]. In the Subsystems proposal [START_REF] Wirfs-Brock | Subsystems -proposal[END_REF], modules (subsystems) support selector namespaces, as in SmallScript [START_REF] Simmons | Smallscript[END_REF]. A selector namespace contains method definitions (of possibly different classes). Selector namespaces are nested and this structure is used for the method lookup.A local selector takes precedence over the same selector defined in a surrounding namespace. With selector namespaces, class extensions can be defined as layers where methods defined in a nested namespace may redefine methods defined in their enclosing namespaces. Selector namespaces, however, do not support local rebinding.

Us, a subject-oriented programming extension of Self [START_REF] Smith | A simple and unifying approach to subjective objects[END_REF], provides for object extensions and method invocations in the context of perspectives, but Us does not provide modules.

Conclusion

This paper introduces the Classbox Model, a module model for object-oriented systems that supports local rebinding. Hence it provides method additions and replacements that are only visible in the module that defines them. Classboxes enhance both existing object-oriented languages that support method addition and replacement, and those that provide module systems. For the former it localises method additions and replacements. It extends the latter with a mechanism that supports unanticipated evolution. To apply local rebinding to an object-oriented language efficiently, the method lookup mechanism has to be changed, and a slightly different method dictionary has to be introduced.

We have implemented the model in the Squeak Smalltalk environment, and performed experiments using classboxes. In the paper we describe an example of how classboxes allow one to extend an existing parse tree with a visitor (making use of class extensions), and replacing a badly implemented method in a system class without affecting the whole system (using method replacement). As far as we know, no other module system is able to achieve this separation.

Flattened

  class. A flattened class describes what methods a class in a certain classbox contains, taking imports into account: -The flattened definition of a class C defined in a classbox cb1 consists of C and all the method definitions for C in cb1. -The flattened definition of a class C imported in a classbox cb1 is the flattened definition of C in its parentbox extended by the method definitions for C in cb1.

Fig. 1 .

 1 Fig. 1. The Squeak Classbox and the HTMLVisitor Classbox that extends Squeak with an HTML Visitor.

Fig. 2 .

 2 Fig.2. The LinkChecker classbox, that defines a HTMLVisitor subclass that checks for dead links and that replaces the method ping: in the class Socket to throw exceptions instead of opening dialogue boxes.

1 4 |

 4 lookup: selector class: cls 2 startBox: startbox currentBox: currentbox classboxPath: path 3

10 parentBox:

 10 = currentbox providerOf: cls name.

  path addLast: parentBox.

  theSuper := cls superclass. 20 theSuper ifNil: [^cls method: selector notFoundIn: cls].

  21 togoBox := path detect: [:box | box scopeContains: theSuper].

  22 newPath := togoBox = startbox 23 ifTrue: [OrderedCollection with: startbox] 24 ifFalse: [path].

Fig. 3 .

 3 Fig. 3. The lookup algorithm that provides local rebinding.

Figure 3

 3 Figure3describes the lookup algorithm we implemented that ensures the local rebinding property.The algorithm first checks whether the class in the current classbox implements the selector we are looking for (lines 5 to 9). If it is found, the lookup is successful and we return the found method (line 9). If it is not found, we recurse. The algorithm favours imports over inheritance, meaning that first the import chain is traversed (in lines 12 to 18) before considering the inheritance chain (in lines 19 to 30). This last part is the difficult part of the algorithm, since we need to find the classbox where the superclass is defined that is closest to the classbox we started the lookup from. Therefore the algorithm remembers the path while traversing the import chain (line 12), and uses this when determining the classbox for the superclass (line 21).

Table 1 .

 1 Benchmarks results from Squeak comparing the regular method lookup mechanism with the classbox-aware lookup mechanism (units are in milliseconds).

	Benchmark	Regular lookup Classbox lookup Overhead
	direct call	5439	6824	25%
	looked up call	5453	6940	27%
	opening and closing a web browser	332	548	65%
	opening and closing a mailreader	536	760	41%
	call through 3 classboxes	-	10554	-
	call through 6 classboxes	-	10654	-

A goody is a small application provided without warranty or support.

Acknowledgments

We gratefully acknowledge the financial support of the Swiss National Science Foundation for the projects "Tools and Techniques for Decomposing and Composing Software" (SNF Project No. 2000-067855.02) and Recast: Evolution of Object-Oriented Applications (SNF 2000-061655.00/1).


D Benmerzouk

J-P Barbot

Chaotic behavior analysis based on sliding bifurcations

Keywords: Dynamic bifurcations (74H60), Chaotic behavior (74H65), Bifurcation of limits cycles and periodic orbits (37G15), Bifurcations

In this paper, a mathematical analysis of a possible way to chaos for bounded piecewise smooth systems of dimension 3 submitted to one of it's specific bifurcations, namely the sliding ones, is proposed. This study is based on period doubling method applied to the relied Poincaré maps.

Introduction

Piecewise smooth systems (p.w.s) considered in this paper are those defined by at least two sets of ordinary differential equations and switch from a smooth phase space to another one when some dynamic switching conditions occur, the sets that separate those phase spaces are smooth and of codimension one. Many special phenomena are relied to those systems (in addition to the classic ones) particularly the sliding ones; recall that those phenomena are well-known and studied since at least the famous Filippov book [START_REF] Filipov | Differential equations with discontinuous right and sides[END_REF]. Moreover, the Russian school has also proposed pioneer works in piecewise smooth bifurcations [START_REF] Feigin | Forced oscillations in systems with discontinuous nonlinearity[END_REF][START_REF] Feigin | On the structure of C-bifurcation boundaries of piecewise continuous systems[END_REF]. More recently, Mario di Bernardo and coauthors gave a bifurcation's classifications for piecewise smooth systems [START_REF] Bernardo | Normal form maps for grazing bifurcations in n-dimensional piecewise-smooth dynamical systems[END_REF][START_REF] Bernardo | Bifurcations of dynamic systems with sliding: Derivation of normal forms[END_REF][START_REF] Bernardo | Unified framework for the analysis of grazing and border-collisions in piecewise smooth systems[END_REF] using the relied Poincaré maps. On the basis of this special classifications, we analyze the possibility of generating chaos for bounded p.w.s systems via these kinds of bifurcations; we have already presented some results in [START_REF] Benmerzouk | Grazing analysis for synchronization of chaotic hybrid systems[END_REF][START_REF] Benmerzouk | Chaotic behavior analysis based on corner bifurcations[END_REF] concerning respectively the grazing bifurcation's and the corner bifurcation's cases. Hereafter, we investigate the possibility of generating chaos for bounded p.w.s systems of dimension 3 submitted to sliding bifurcations. Obviously, this kind of piecewise smooth systems and corresponding bifurcation's analysis already exists [START_REF] Jaguste | A class of discontinuous dynamic systems, an industrial slurry high density polyethylene reactor[END_REF][START_REF] Nuss | Border-collision bifurcations for piecewise smooth one dimensional map[END_REF], nevertheless, at our knowledge, a general mathematical study of a way to chaos via this type of bifurcations has never been proposed. Consequently, in this paper, following the analysis given in [START_REF] Benmerzouk | Observability analysis using Lyapunov-Schmidt method[END_REF][START_REF] Benmerzouk | Lyapunov-Schmidt method dedicated to observer Analysis and Design[END_REF] and based on Lyapounov-Schmidt method, a solution analysis is proposed for generating chaotic behavior, this will be done using period doubling method.

The paper is organized as follows: In section II, the problem statement is established; In section III , the problem analysis is developed, a way to chaos is proposed in section IV and an academic example based on this approach with simulations results are presented in section V.

Recalls and Problem statement

Let us consider the following piecewise smooth system:

ẋ = { F 1 (x) if H(x) ≥ 0 F 2 (x) if H(x) < 0 (1)
where

x : I -→ D, D is an open bounded domain of R 3 , I ⊂ R + , generally I is the time interval . F 1 , F 2 : C 1 (I, D) -→ C k (I, D),
for k ≥ 4 where C k (I, D) is the set of C k functions defined on I and having values in R 3 , the norm for C k (I, D) is defined as follows:

x ∈ C k (I, D) : ∥x∥ = sup t∈I ∥x(t)∥ e + sup t∈I ∥ ẋ(t)∥ e + ... + sup t∈I x (k) (t) e
where x (k) (.) denotes the k th derivative of x(.) and ||.|| e is a norm defined on R 3 .

According to [START_REF] Bresis | Analyse fonctionnelle, Théorie et Applications[END_REF], (C k (I, D), ∥.∥) is a Banach space. Thus, both vector fields F 1 and F 2 are sufficiently regular on their domains of definitions such that the flows Φ i , i = 1, 2 generated by each vector field F i are defined as the operators that satisfy:

∂Φ i (x,t) ∂t = F i (Φ i (x, t)) and Φ i (x, 0) = x, i = 1, 2. H : D -→ R is a C 1 application
, it is a phase space boundary between both regions of smooth dynamics, H defines the set:

S = {x(t) ∈ D : H(x(t)) = 0}
and S is the switching manifold and divides the phase space into two regions:

S + = {x(t) ∈ D : H(x(t)) > 0} S -= {x(t) ∈ D : H(x(t)) < 0}
Moreover for being in the context of sliding phenomena, it is assumed that there exists a subset of switching manifold S ⊂ S denoted as sliding region which is simultaneously attracting from S + and S -, so, considering any neighborhood v S of S, the existence of S is characterized by the following hypothesis:

H 1 ) < ∇H(x(t)), F 2 (x(t)) -F 1 (x(t)) >∈ R * + , for all x(t) ∈ v S .
where < ., . > is a usual scalar product on R 3 .

Thus, under H 1 ), if the system trajectory crosses S, the sliding motion evolves in S until it eventually reaches its boundary, this motion can also be described by considering an appropriate vector F S witch lies within the convex hull of F 1 and F 2 and is tangent to S for each x(t) ∈ v S , F S is given by:

F S (x(t)) = F 1 (x(t))+F 2 (x(t)) 2 + H u (x(t)) F 1 (x(t))-F 2 (x(t)) 2 ,
where H u : D -→ R is deduced from the equivalent vector method [START_REF] Filipov | Differential equations with discontinuous right and sides[END_REF][START_REF] Utkin | Sliding modes in control optimization[END_REF], in fact H u is given using the tangential condition of F S on the switching manifold i.e. < ∇H, F S >= 0 which implies that :

H u (x(t)) := - < ∇H(x(t)), F 1 (x(t)) + F 2 (x(t)) > < ∇H(x(t)), F 1 (x(t)) -F 2 (x(t)) > (2)
and

-1 ≤ H u (x(t)) ≤ 1, for x(t) ∈ v S (3)
So, the sliding region is redefined as :

S v = {x(t) ∈ v S : -1 ≤ H u (x) ≤ 1} (4)
It's follows from H 1 ) and ( 4) that sliding phenomena is characterized by:

< ∇H(x(t)), F 2 (x(t)) > > 0 > < ∇H(x(t)), F 1 (x(t)) > for x(t) ∈ v S (5)
and the boundary of the sliding region is defined as:

∂S + v = {x(t)ϵS v : H u (x(t) = 1} and ∂S - v = {x(t)ϵS v : H u (x(t) = -1} .
The system (1) characterizes the behavior of an increasing number of dynamic systems particularly in Applied Sciences and Engineering, those piecewise smooth systems can present a specific switching bifurcations particularly when depending on some parameters, thus in order to present a complete sliding bifurcation analysis, it is assumed that the system (1) is bounded and depends smoothly on a parameter ε such that at ε = 0, there exists a periodic orbit x(t) that slides at the point x corresponding to t (where t is defined modulo the periodicity of (1)) and there is no other sliding point along this orbit other than the point x and this for a sufficiently small neighborhood of ε.

Consequently, the system (1) is rewrite as follows:

ẋ = { F 1 (x, ε) if H(x) ≥ 0 F 2 (x, ε) if H(x) < 0 ( 6
)
and it is assumed that there exist a neighborhood v ε of ε = 0, a neighborhood v x of x = x such that the following hypotheses are verified at this bifurcation point (x, t):

H 2 ) H(x) = 0 and ∇H(x) ̸ = 0. H 3 ) H u (x) = -1 ⇔< ∇H(x), F 1 (x) >= 0
The assumption H 2 ) means that the bifurcation point belongs to the switching manifold and its neighborhood is correctly defined (x is isolated) and the assumption H 3 ) means that x is located on the boundary of the sliding region.

Without loss of generality (thanks to a coordinate change), the bifurcation point is assumed to be located at (x, t) = (0, 0).

According to [START_REF] Bernardo | Bifurcations of dynamic systems with sliding: Derivation of normal forms[END_REF], four possible cases of bifurcations involving sliding are possible:

Case 1: Sliding bifurcation of type 1: here, the sliding flow is assumed to move locally towards the boundary of the sliding region when it is perturbed from bifurcation point (see fig 1): This yields the following assumption:

A 1 ) ∂ 2 H(ϕ 1 (0,0)) ∂t 2 = ⟨ ∇H(0), ∂F 1 (0,0) ∂x F 1 (0, 0) ⟩ > 0.
The determination of the Poincaré map is based on the determination of the Zero Discontinuity Map (noted ZDM) , this map captures all the informations concerning the switching trajectories and is given by:

ZDM 1 (x, ε) = { εx if < ∇H, x > ≤ 0 εx + ε 2 v 1 (x) + o(ε 3 ) if < ∇H, x > > 0 (7)
where:

v 1 (x) = 1 2 < ∇H, ∂F 1 ∂x x > 2 < ∇H, F 2 >< ∇H, ∂F 1 ∂x F 1 > (F 2 -F 1 ) (8)
o(ε α ) -→ 0 when ε -→ 0, α ∈ R + and for the sake of compactness,the values of functions F 1 , F 2 , ∂F 1 ∂x and ∇H, defined in v 1 , stand (and also for the values of the functions given in the coefficients v 2 ,v 3 ,v 4 of the next cases) respectively for F 1 (0, 0), F 2 (0, 0), ∂F 1 ∂x (0, 0) and ∇H (0). Moreover, the projection of x on the Poincaré map is also noted by x.

Case 2: Grazing sliding bifurcation: here, the sliding flow moves towards the edge of the sliding strip and the sliding trajectory tends to leave S (see fig 2).

A 2 ) ∂ 2 H(ϕ 2 (0,0)) ∂t 2 = ⟨ ∇H(0), ∂F 2 (0,0) ∂x F 2 (0, 0) ⟩ > 0.
and the corresponding ZDM is given by:

ZDM 2 (x, ε) = { εx if < ∇H, x >≥ 0 εx + εv 2 (x) + o(ε 3 2 ) if < ∇H, x >< 0 (9)
where:

v 2 (x) = - < ∇H, x > < ∇H, F 2 > (F 2 -F 1 ) (10)
Case 3: Sliding bifurcation of type 2 (or switching-sliding bifurcation): here, contrary to the conditions requested for the two previous cases, the vector field F S must point away from the boundary of the sliding region at the bifurcation point and after a sliding occurs (see fig 3):

A 3 ) ∂ 2 H(ϕ 1 (0,0)) ∂t 2 = ⟨ ∇H(0), ∂F 1 (0,0) ∂x F 1 (0, 0) ⟩ < 0.
and the corresponding ZDM is given by:

ZDM 3 (x, ε) = { εx if < ∇H, x > ≤ 0 εx + ε 3 v 3 (x) + o(ε 4 ) if < ∇H, x > > 0 ( 11
)
where :

v 3 (x) = 2 3 < ∇H, ∂F 1 ∂x x > 3 < ∇H, F 2 >< ∇H, ∂F 1 ∂x F 1 > 2 (12) ( ∂F 1 ∂x + I d < ∇H, F 2 > (< ∇H, ∂F 1 ∂x F 1 - ∂F 1 ∂x F 2 >) ) (F 2 -F 1 )
and I d denotes the identity matrix of appropriate dimension.

A 4 ) ∂ 3 H(ϕ 1 (0,0)) ∂t 3 = ⟨ ∇H(0), ( ∂F 1 (0,0) ∂x ) 2 F 1 (0, 0) ⟩ < 0.
and the corresponding ZDM is given by:

ZDM 4 (x, ε) = { εx if < ∇H, x >≥ 0 εx + ε 2 v 4 (x) + o(ε 5 2 ) if < ∇H, x >< 0 (13)
where:

v 4 (x) = - 9 2 < ∇H, ∂F 1 ∂x x > 2 < ∇H, F 2 >< ∇H, ( ∂F 1 ∂x ) 2 x > ( ∂F 1 ∂x - < ∇H, ∂F 1 ∂x F 2 > < ∇H, F 2 > I d )(F 2 -F 1 ) (14)
For each type of sliding, the corresponding Poincaré map (noted P i ) is obtained by composing the corresponding ZDM with the time T-flow periodic map associated to the system and given by:

Π per : x → P x + Qε + o(∥x∥ , ε) ( 15
)
where P is a nonsingular matrix and Q is a non null vector of appropriate dimensions.

Problem analysis

In this section, the existence and uniqueness of periodic solution for the system (6) may be discussed for the four cases of slidings . First, recall that a fixed point of P i (., ε) represents an mT periodic orbit, where m is a natural number and T is the period, therefore searching a periodic solution of ( 6) is equivalent to resolve for each case of sliding i = 1, 2, 3, 4, the following equations:

P i (x, ε) = x (16)
So, two possibilities appear:crossing and non crossing cases, First possibility: there is no crossing i.e. (<∇H, x > ∈ R -for case 1 and 3) or (< ∇H, x > ∈ R + for case 2 and 4). Thus, one only considers the first equation of the systems (7), ( 9), [START_REF] Feigin | Forced oscillations in systems with discontinuous nonlinearity[END_REF], [START_REF] Filipov | Differential equations with discontinuous right and sides[END_REF] composed with the periodic map [START_REF] Nuss | Border-collision bifurcations for piecewise smooth one dimensional map[END_REF] and the problem becomes to analyze the same equation for the four cases given by: γ(x, ε)

:= P (εx) + Qε -x = 0 (17)
Thus, for sufficiently small ε in the neighborhood v ε of 0, the Implicit Functions theorem gives:

Lemma 1 Under conditions H j ), j = 1, 2, 3, and assumptions A i ) specific to each case i = 1, 2, 3, 4, there exists a neighborhood υ ε=0 ⊂ v ε in R, a neighborhood ν x=0 on the Poincaré section's (defined in R 2 ) and an unique application

x * : υ ε=0 -→ ν x=0 solution of γ(x * (ε), ε) = 0 such that x * (0) = 0.
Furthermore, the periodic solution of ( 6), x * depends continuously on ε.

Second possibility: a crossing occurs i.e. (< ∇H, x > ∈ R * + for case 1 and 3) or (< ∇H, x > ∈ R * -for case 2 and 4): Thus the problem of finding a periodic solution of ( 6) is equivalent to analyze for each case i = 1, 2, 3, 4 the following corresponding equations:

P i (x, ε) -x = 0 (18)
where :

• For case 1:

P 1 (x, ε) = P (εx + ε 2 v 1 (x)) + Qε + o(ε 3 ) (19)
where v 1 (x) is given in [START_REF] Bernardo | Normal form maps for grazing bifurcations in n-dimensional piecewise-smooth dynamical systems[END_REF] and ε ∈ v ε .

• For case 2:

P 2 (x, ε) = P (εx + εv 2 (x)) + Qε + o(ε 3 2 ) ( 20
)
where v 2 (x) is given in [START_REF] Djemai | New type of data transmission using a synchronization of chaotic systems[END_REF] and ε ∈ v ε .

• For case 3:

P 3 (x, ε) = P (εx + ε 3 v 3 (x)) + Qε + o(ε 4 ) ( 21
)
where v 3 (x) is given in [START_REF] Feigin | On the structure of C-bifurcation boundaries of piecewise continuous systems[END_REF] and ε ∈ v ε .

• For case 4:

P 4 (x, ε) = P (εx + ε 2 v 4 (x)) + Qε + o(ε 5 2 ) ( 22
)
where v 4 (x) is given in ( 14) and ε ∈ v ε .

The analysis of equations ( 18) is equivalent to analyze the following ones:

β i (x, ε) := P i (x, ε) -x = 0, i = 1, 2, 3, 4 (23)
and the Implicit Functions theorem gives:

Lemma 2 Under conditions H j ), j = 1, 2, 3, and assumptions A i ) specific to each case of sliding bifurcations i = 1, 2, 3, 4, there exists a neighborhood υ i ε=0 ⊂ v ε in R, a neighborhood ν i x=0 on the Poincaré section's (defined in R 2 ) and an unique application x * * i :

υ i ε=0 -→ ν i x=0 solution of β i (x * * i (ε), ε) = 0 such that x * * i (0) = 0.
Furthermore, the periodic solution of ( 6), x * * depends continuously on ε.

Way to Chaos

It is well known that a deterministic chaotic system is characterized by a great sensitivity to the initial conditions, a bounded behavior and "the strange"structure of its attractor. Moreover, according to [START_REF] Glendinning | Stability, instability and chaos: An introduction to the theory of nonlinear differential equations[END_REF] or [START_REF] Wiggins | Introduction to applied nonlinear dynamic systems and Chaos[END_REF], one way to generate chaotic behavior for one dimensional discrete systems is those based on period doubling method. In this section, we propose a mathematical analysis for bounded p.w.s systems of dimension 3, the associated Poincaré map is thus of dimension 2 , thus at this step, the famous result of Lie and Yorke [START_REF] Wiggins | Introduction to applied nonlinear dynamic systems and Chaos[END_REF] : "Period three implies chaos" is not available but here the most important mathematical tool used is the Implicit Function Theorem, this enables us to construct not an "ordinary" solution but a "branch" of solutions depending continuously on the parameter ε and as the Poincaré map is chosen to be orthogonal to the sliding surface, at ε = 0 the considered system will be defined in dimension 1 and this enables us to invoke this result. More precisely, the problem becomes to determine for each map P i , i = 1, 2, 3, 4, three distinct points x i , y i and z i such that: P i (x i , ε) = y i , P i (y i , ε) = z i and P i (z i , ε) = x i . This well be done naturally in three steps as follows: First step: analysis of the equation:

P i (x i , ε) = y i = x i + η i (24)
where for a sake of simplicity, η i stands for a vector defined in R 2 , having only one component equal to some fixed value (noted also η i ) and the other component is zero. Thus, the equation ( 24) is equivalent to:

Ψ i (x i , ε, η i ) := P i (x i , ε) -x i -η i = 0 (25)
and the next lemma is obtained with the same arguments than the previous one, note that the assumption needed at this step is that ε must be very small relatively to 1 which is obvious and thus:

Lemma 3 Under conditions H j ), j = 1, 2, 3 and A i ) specific to each case i = 1, 2, 3, 4, there exists a neighborhood ϑ i ε=0 in R, a neighborhood υ η i =0 in R, a neighborhood υ x i =0 on the Poincaré section's (defined in R 2 ) and an unique application x * i : ϑ i ε=0 × υ η i=0 -→ υ x i =0 solution of Ψ i (x * i (ε, η i ), ε, η i ) = 0 such that x * i (0, 0) = 0. Furthermore, x * i depends continuously on ε and η i .
Second step: analysis of the equation:

P i (P i (x i , ε), ε) = z i = y i + µ i = x * i (ε, η i ) + η i + µ i ( 26
)
where µ i stands for a vector defined on R 2 , having only one component equal to some fixed value(noted also µ i ) and the other is null. Thus, equation ( 26) is equivalent to:

Γ i (ε, η i , µ i ) := P i (x * i (ε, η i ) + η i , ε) -x * i (ε, η i ) -η i -µ i =
0 and in order to continue the process, the following hypothesis according to each case is necessary:

H i 1 )' ∂Γ i ∂η i (0, 0, 0) ̸ = 0.

It comes:

Lemma 4 Under conditions H j ), j = 1, 2, 3, A i ) specific to each case i = 1, 2, 3, 4 and H i 1 )', i = 1, 2, 3, 4 specific to each case, there exists a neighborhood

υ i ε=0 ⊂ ϑ i ε=0 , a neighborhood ν η i=0 ⊂ υ η i=0 , a neighborhood ν µ i =0 in R and an unique application η * i :υ i ε=0 × ν µ i =0 -→ ν η i=0 solution of Γ i (ε, η * i (ε, µ i ), µ i ) = 0 such that η * i (0, 0) = 0.
Furthermore, η * i depends continuously on ε and µ i .

Third step: analysis of the equation:

P i (P i (P i (x i , ε), ε), ε) = x i (27)
The equation ( 27) is equivalent to:

Π i (ε, µ i ) := P i (x * (ε, η * i (ε, µ i )) + η * i (ε, µ i ) + µ i , ε) -x * i (ε, η * i (ε, µ i )) = 0
(28) So the following hypothesis is required for each case i = 1, 2, 3, 4 :

H i 2 )' ∂Π i ∂µ i (0, 0) ̸ = 0
and one obtains:

Lemma 5 Under conditions H j ), j = 1, 2, 3, A i ), i = 1, 2, 3, 4 specific to each case and H i 1 )',H i 2 )' , i = 1, 2, 3
, 4 specific to each case, there exists a neighborhood ω i ε=0 ⊂ υ i ε=0 , a neighborhood θ µ i=0 in ν µ i=0 and an unique application µ * i :

ω i ε=0 -→ θ µ i=0 solution of Π i (ε, µ * i (ε)) = 0 such that µ * i (0) = 0. Furthermore, µ * i depends continuously on ε .
Remark 1 Assumptions noted H j ) are relied to the sliding phenomena and are so all necessary but the assumptions noted A i ) are relied to each of the four types of sliding bifurcations and assumption noted H i k )', k = 1, 2 are relied to chaotification processus corresponding to each case of slidings i = 1, 2, 3, 4.

The next corollary sums up the previous results:

Corollary [START_REF] Bernardo | Bifurcations of dynamic systems with sliding: Derivation of normal forms[END_REF] Under conditions H j ), j = 1, 2, 3, A i ), i = 1, 2, 3, 4 specific to each case and H i 1 )',H i 2 )',i = 1, 2, 3, 4 specific to each case, the bounded system (6), of dimension 3, admits a chaotic behavior.

Remark 2 A chaotic behavior in the sense of Lie and Yorke is not generally guarantied for systems of dimension greater than 3 because the period doubling as a way to chaos, at the best of our knowledge, is only proved for one dimensional discrete systems. Nevertheless, a period doubling is an indication for an eventual chaotic behavior. Moreover, the constraint1 n -d = 2 is not so restrictive: for switched system [START_REF] Bernardo | Bifurcations of dynamic systems with sliding: Derivation of normal forms[END_REF] with sliding manifold separating the state space in two parts,condition n -d = 2 is verified. Thus the period doubling is also valid in this case and the previous corollary may be rewritten with condition n-d = 2 instead of system dimension equal to 3.

Comparing this result to the previous one given in [START_REF] Benmerzouk | Grazing analysis for synchronization of chaotic hybrid systems[END_REF][START_REF] Benmerzouk | Chaotic behavior analysis based on corner bifurcations[END_REF] corresponding respectively to the grazing bifurcation and corner bifurcation highlights that sliding bifurcations need less restrictive conditions, consequently, sliding bifurcations seem better choice for many applications as chaotic emitter design.

An illustrative example

In this section, one illustrates the proposed approach using an academic example submitted to sliding bifurcation of type 2, nevertheless, the other types of sliding bifurcations can also be treated in the same way. So, let us consider the following piecewise smooth system:

ẋ1 = f 11 (x 1 , x 2 , x 3 ) ẋ2 = f 12 (x 1 , x 2 , x 3 ) for x 2 ≤ 0 ẋ3 = f 13 (x 1 , x 2 , x 3 ) and ẋ1 = f 21 (x 1 , x 2 , x 3 ) ẋ2 = f 22 (x 1 , x 2 , x 3 ) for x 2 > 0 ẋ3 = f 23 (x 1 , x 2 , x 3 )
where:

f 11 (x 1 , x 2 , x 3 ) = x1 √ x1 2 +x2 2 (√ x 1 2 + x 2 2 -r ) ( ν-ε √ r 2 +x1 2 +x2 2 +x3 2 -2r √ x1 2 +x2 2 -1 ) -x 1 x 3 α √ x1 2 +x2 2 -ψ(x 3 )x 2 f 12 (x 1 , x 2 , x 3 ) = ψ(x 3 )x 1 -x 2 x 3 α √ x1 2 +x2 2 - x2 √ x1 2 +x2 2 (√ x 1 2 + x 2 2 -r ) + x 2 ν-ε √ x1 2 +x2 2 √ x1 2 +x2 2 -r √ r 2 +x1 2 +x2 2 +x3 2 -2r √ x1 2 +x2 2 f 13 (x 1 , x 2 , x 3 ) = α (√ x 1 2 + x 2 2 -r ) -x 3 + x 3 ν-ε √ r 2 +x1 2 +x2 2 +x3 2 -2r √ x1 2 +x2 2 and f 21 (x 1 , x 2 , x 3 ) = x1 √ x 2 1 +x2 2 ( √ x 2 1 + x 2 2 -r ) ( ν √ r 2 +x 2 1 +x2 2 +x3 2 -2r √ x 2 1 +x2 2 -1 ) -x 1 x 3 α √ x 2 1 +x2 2 -x 2 γ f 22 (x 1 , x 2 , x 3 ) = x 1 γ -x 2 x 3 α √ x1 2 +x2 2 - x2 √ x1 2 +x2 2 (√ x 1 2 + x 2 2 -r ) + x 2 ν √ x1 2 +x2 2 √ x1 2 +x2 2 -r √ r 2 +x1 2 +x2 2 +x3 2 -2r √ x1 2 +x2 2 f 23 (x 1 , x 2 , x 3 ) = α (√ x 1 2 + x 2 2 -r ) -x 3 + x 3 ν √ r 2 +x1 2 +x2 2 +x3 2 -2r √ x1 2 +x2 2 with ψ(x 3 ) =    γ if x 3 > 0 -γ if x 3 < 0 [-γ, γ ] if x 3 = 0
α, γ and ν are fixed positives non nulls real numbers such that α < γ and ε is a positive real value, ε is small relatively to γ.

Conditions H i ) i = 1, 2, 3, A 2 ) and H 1 2 )', H 2
2 )' are satisfied in the neighborhood of a fixed point x = (x 1 , 0, 0), and x1 is a non null real value , then a sliding bifurcation of type 2 occurs. Thus simple calculus, based on the results of the previous sections and by considering also a special Poincaré section that is orthogonal to the sliding surface, gives the corresponding Poincaré map:

P 2 (x, ε) = { P (εx) if x ≥ 0 P (εx + εv 2 (x)) + Qε + o(ε 3 2 ) if x < 0 (29)
for any x ∈ R and v 2 (x) = -xε x1 γ . For all simulations, one considers the following parameters: α = 20π, γ = 20π + 0.001, ν = 0.5 and R = 5. So, for the first case ε = 0, the system behavior is a limit cycle (see fig 5). In all the next simulations, in order to show that the system behavior converges to the limit cycle (respectively a strange attractor), one chooses the initial state (x 1 = 5, x 2 = 0, x 3 = 1) outside the limit cycle (respectively a strange attractor). According to the proposed analysis, moving the parameter ε (the parameter variation can be reduced simply by a scale change), a period doubling occurs and a way to chaos is highlighted. In the figure 6, the system behavior is given for ε = 4.5. In the figure 7, the system behavior is given for ε = 9.5. In figure 8, a strange attractor appears for ε = 14.5.

Conclusion

In this paper, we have proposed a way to chaos analysis for bounded piecewise smooth systems of dimension 3 submitted to sliding bifurcations. Using the period doubling method, it is proved that chaos occurs for specific parameter variations. The obtained results can be generalized to hybrid systems such that the difference between the state dimension and the dimension of the sliding manifold is equal to two. The well-founded of this approach is highlighted by simulations results where way to chaos is explicitly shown. Their are many possible extensions of this paper in mathematical fields, for example by considering the other types of nonsmooth bifurcations or hybrid systems defined by more than two dynamics. On the other hand, some applications can be done particularly for observer design or controlling chaos, see for example [START_REF] Bernardo | Grazing, skipping and sliding: analysis of non-smooth dynamics of the DC/DC Buck converter[END_REF] in power

Figure 1 :

 1 Figure 1: Sliding bifurcation of type 1

Figure 2 :

 2 Figure 2: Grazing Sliding bifurcation

Figure 3 :

 3 Figure 3: Sliding bifurcation of type 2

Case 4 :

 4 Multisliding bifurcation: here the sliding flow is tangential to the boundary of the sliding strip at the bifurcation point and for further variation of the bifurcation parameter the trajectory may leave completely the manifold S going to S + (see fig4):

Figure 4 :

 4 Figure 4: Multisliding bifurcation

Figure 5 :

 5 Figure 5: Limit cycle

Figure 6 :

 6 Figure 6: first steps to chaos

Figure 7 :

 7 Figure 7: second steps to chaos

n -1 is the dimension of the relied Poincaré map (in our case n -1 =

2) and d is the bifurcation codimension.

electronic context and [10] in private communications applications.


Géraldine Abrami
email: geraldine.abrami@cemagref.fr

Didier Bazile
email: didier.bazile@cirad.fr

Harouna Coulibaly
email: hscoulibaly@yahoo.fr

François Bousquet
email: francois.bousquet@cirad.fr

Coulibaly H And

AN ABSTRACT ROLE-PLAYING GAME FOR DISCUSSING COLLECTIVE MANAGEMENT OF AGROBIODIVERSITY

Keywords: Mali, Sorghum, agrobiodiversity, seeds system, companion modelling, role-playing game Mali, Sorgho, agrobiodiversité, système semencier, modélisation d'accompagnement, jeu de rôle

This research aims at accompanying farmers in building a collective management of their subsidence cereals varietal diversity. Seed management and its impact on biodiversity dynamics are driven by farmers' individual choices and strategies on the one hand, and by the seed system functioning on the other hand. We think that the mutual understanding of the interactions arising in this complex system is a prerequisite to work together on the construction of new collective management rules to participe to agriculture sustainaibility coping with a large choice of varieties. Participatory conceptual modelling and Role-Playing Games were used in several workshops gathering researchers, NGOs, farmers' organisations and farmers. A result of this series of workshops is an ABM of an archetypal Malian village that represents the current situation where varietal diversity is managed individually but is freely available for the community. In this model, agents are farmers that make varietal choices and provoke seed exchanges depending on their individual strategies and external factors. All descriptive parameters hold qualitative abstract value so that the model can become the support of generic discussions between farmers from different regions. Through the workshops, this model was built and validated with the active input of local stakeholders and scenarios of collective management were constructed. Then the model will be used as a prospective tool for simulating these scenarios of various forms of collective action.

INTRODUCTION

The originality of our general approach is to focus on the biodiversity in agriculture, or agrobiodiversity [START_REF] Wood | Agrobiodiversity : Characterization, utilization and Management[END_REF]. During this study, we only consider the cultivated part of agrobiodiversity to evaluate the impact of farmers' practices in the dynamics of biodiversity at the local or regional scale. The global idea of the research process was to consider the farmers' informal seeds system as a complex and dynamic system where individual decisions interact through evolving networks of relations and result in emerging dynamic patterns of varieties at the scale of the communities. Considering less developed countries as Mali and Niger in west Africa, we ask the next question that positions sociocultural and agrotechnic factors on the two side of a same complex system [START_REF] Brookfield | Exploring agrodiversity[END_REF][START_REF] Brookfield | Cultivating biodiversity[END_REF][START_REF] Brush | Genes in the Field: On-farm conservation of crop diversity[END_REF]Jarvis & al., 2007) : "How the farmers' livelihoods are dependent on the varietal diversity and what are the drivers that impact the maintenance of the varietal diversity in the system? This posture define the general context of our research where the Farmer Seed System is considered as complex and dynamic system [START_REF] Almekinders | Farmers' seed production: New approaches and practices[END_REF][START_REF] Mcguire | Targeted Seed Aid and Seed System Interventions: Supporting farmers' seed systems in East and Central Africa[END_REF][START_REF] Mcguire | Securing access to seed: Social relations and sorghum seed exchange in eastern Ethiopia[END_REF] focusing on farmers' practices of seeds selection and exchange. Besides other packages focusing on description, characterization or improvement of local varieties and functioning and potential of formal nationwide seeds systems, this research was oriented towards farmers' practices regarding the dynamics of the diversity of varieties within seed selection and exchange.

The result that we present here is a Role Playing Game (RPG) called SEED-Div. It's the final product from a research project on farmers management of agrobiodiversity in Mali (West Africa) during the period 2005-2007. The paper only presents the final product of this participative research project (Bazile&Weltzein, 2008), without all the steps of its development, tackling farmers' individual and collective management of the varietal diversity of subsistence cereals in Mali and Niger (Pearl millet and Sorghum).

The various RPG developed in this research have allowed to show many scientific and social interests of this kind of methodology that we can summarize within theses shorts sentences:

-to increase the understanding of farmers practices; -to consider the sustainability of seed system for in situ conservation of agrobiodiversity -to support the dialogue of many stakeholders for prospective and new scenarios within contradictory point of views Outside the research line, we can explore other ways where the RPG could be used that comfort the participatory methods for teaching environment:

-learning during practise with students and professionals; -exchanges between various actors who can explore with this tool; -co-construction of scenarios.

MATERIAL AND METHOD

General Methodological context and material

Context and Tools : the companion modelling approach

This research was based on a companion modelling process where successive models of the system hold the trace of the perspectives and knowledge gathered, shared and discussed all along the process, iteratively with complementary field studies based on SEED-Div ABRAMI G., BAZILE D., COULIBALY H. And F. BOUSQUET observation and interviews [START_REF] Barreteau | Our Companion Modelling Approach[END_REF][START_REF] Bousquet | An environnemental modelling approach : the use of multi-agent simulations[END_REF]. While conceptual specification of the models were formalized through UML diagrams and implemented in an Agent-Based Model, several Role-Playing Games were designed to share and discuss different aspects of the models. These Role-Playing Games were used in 4 workshops gathering researchers, NGOs, farmers' organisations and farmers. [START_REF] Bazile | Des modèles pour analyser ensemble les dynamiques variétales du sorgho dans un village malien[END_REF][START_REF] Abrami | Accompanying farmers in the building of collective rules for agrobiodiversity management[END_REF] 1.1.2. Material: previous results of the project that did support SEED-Div conception Many on-farm experiments have been conducted during 2001 to 2004 in 12 villages of Mali. They depended on direct field observations, participatory appraisals and farmers' interviews on their crops. They resulted in a large amount of data on the biophysical and socio-economic determinants of farming systems diversity towards sorghum. These data have been structured and spatialised into a database and a GIS. A realistic "expert" ABM was developed on this basis. From an archetypal landscape, this model generates a spatial distribution of farms (with their fields, crops and varieties) embedded in a social structure. However the agents' behaviour was not relying on actual strategies, but on statistical values and the model structure was too complex to be shared with farmers. This model is an integration framework of various disciplinary submodels and data. It has been used to define and validate a reference initial state with our Malian research partners. The modeling process led to the identification of knowledge gaps on farmers' strategies. As a result the objectives of the next step were drawn: simplifying the model by converging to essential descriptive parameters and eliciting missing information about farmers' strategy. In order to break the complexity of the model, we have identified 4 modules that can describe the system. Our idea was to work separately with the farmers on the specific questions addressed by each module before going back to the whole system. Each of these modules corresponds to a decision context of the farmers. The 2 first modules (crops rotation strategy and varieties association strategy) fix the "static" state of the system. The 2 other modules (varieties changing, supplier selection and seed exchange) fix the dynamics of the system. Three of those modules were addressed within specific RPG workshops, and the last one (varieties adoption and abandonment) was addressed through fieldwork and during the workshops debriefing sessions. The RPG1 is dealing with varieties association strategies. Farmers have to specify their crops and varieties and their sowing dates in response to climatic variations in order to ensure their food security. Computerized abacus gives farmers a feedback on their harvest. The RPG1 session resulted in identifying archetypal varieties association and varieties changing strategies. It also showed knowledge gaps on crop systems and rotation influence and seeds supplying modalities. The RPG2 is dealing with crop rotations. Farmers have to specify the spatial organization of their crops in response to climatic variations, and perform group evaluation of their decisions. The RPG2 session resulted in simplifying the representation of farms agroclimatic constraints. The RPG3 is dealing with seeds suppliers and exchange networks. Farmers have to get appropriate seeds in response to climatic variations and disaster events. Some of them are attributed a special social status and social and spatial proximity relationships are reconstructed through grouping people in different phases of the time step. The RPG3 game session resulted in identifying which specific suppliers' types correspond to which specific rational of seeds research. The workshops occurred between April and December 2005. They resulted in a rearrangement of our hypotheses and results in a consistent frame built together with the farmers during the collective debriefings. However, each RPG was only be played one time, and the 3 workshops concerned different villages. The objectives of the next step were then to develop a "generic" ABM and design simulations that can be used for supporting collective prospecting on management scenarios.

RPG design context

1.2.1. Specific constraints on the RPG design SEED-Div was designed to be used in the last workshop of the research project, where Niger and Mali farmers from 9 different regions were to meet and share insights and outputs of the project in their respective communities. Then, this specific RPG activity had a double objective of being a media of exchange between these farmers and bring them on questioning institutional aspects of seeds management. The idea was then to wrap up our model in an tool that was as simple and abstract as possible as agro-ecological constraints of the different farmers where very different and half of them did not participate in the preceding companion modelling workshops. We thus decided to design an activity that could structure the 2 days workshop, starting with a very simple and abstract game and having the participants modifying it to make it more suitable to their questions and finally testing a seeds diversity management institution.

Mains elements for the design

The previous workshops activities were aimed at informing and discussing our ABM : there was little room for interaction among the players. Here the main objective of the activity was to have farmers from different regions interacting and discussing institutional aspects of varietal diversity management. Hence the RPG had to be : 1. simple enough to be played quickly and leave space for interactions 2. abstract enough to be illustrative for all the participants and hinder discussions on a generic level 3. able to allow upscaling from individual decision level on varieties choice and seeds supply to collective decision level on institution crafting [START_REF] Ferrand | WAT-A-GAME: sharing International Simulation And Gaming water and policies in your own basin[END_REF]. For the quality of its simplicity and its exemplarity, we took inspiration from the Chering / ReHab1 game which is used regularly as an introductory activity in training sessions of our fellow researchers of the companion modelling group. The principle of Chering is to ask each player to choose a cell to harvest in a grid and to provide his the result of its harvest as a feedback depending on a the level of resource in the cell and the number of player who chose this cell. Then the idea is to have quick sessions where player first play individually and then try to coordinate their action in groups of different size. From Chering we wanted to keep the principle of :

having players interacting on an abstract grid of square cells qualified by a single abstract and simple indicator having all players making a single very simple choice at every time step on the use of an abstract resource which dynamic is hidden being able to play several time steps in successive sessions where players act individually and then collectively However our wish was to be able to go a step further and have participants designing a local management institution for the resource represented in the game as an objective of the workshop. This is also a fairly classical approach used in companion modelling where a series of workshop session, and if possible a workshop of several day, is used to have 1) participants interacting around a simple RPG 2) participants modifying the RPG to make it more adequate to their constraints 3) participants designing and playing scenarios or institutions within the RPG (d'Aquino et al, 2003;[START_REF] Castella | Participatory simulation of landuse changes in the northern mountains of Vietnam: The combined use of an agent-based model, a role-playing game, and a geographic information system[END_REF]Gurung et al, 2006).

Our issue being agrobiodiversity, the principle of the game would be managing a resource diversity instead of managing a resource quantity and then having players choosing and renewing color tokens representing the different varieties of a resource. More specifically, the game should be able to tackle the essential aspects of the design of a local seeds management institution: -are there some underlying collective management institutions that help in maintaining the varietal diversity at the scale of a local community? -Would a formal institution be helpful and how should it be crafted : what should be -its status (conservation or supplying) : what should be the production objectives of the institution ? -its resources : financial (which money), land, human (who is making the work) -its governance : which procedural and institutional rules -REF A OSTROM ?? -the scale it should function

Workshops organisation

The organisation of the workshop(s) is a crucial point of any participative work and it is also the case of RPG where the questions of who are the participants, how they are selected, and which is their status in their community has a string impact on potential insight that will be raised within the workshop and also on the diffusion of the process.

As the workshop was the final event of a 3 years farmers driven process, we choose to invite many farmers from a variety of agricultural conditions in Mali and Niger. Ten (10) farmers came from Mali with the charge to represent this diversity of agrarian situations, cereals, varieties and cropping system en general. Five (5) members of ONG were accompanying theses farmers, one from each region, and participated to the choice of them within two principal criterions: capacity to debate the local conditions of its region and knowledge of the diversity of cropping system that generate. The same distribution was adapted for the Nigerian case with eigth (8) farmers but only two persons from ONG.

All the charges were assumed from the project.

The research staff was composed with 4 researchers from France (1 geographer, 2 modellers and 1 agronomist), 3 researchers from Mali (1 geographer, 1 agronomist and 1 sociologist) and 1 researcher from Niger (a genetist). All of them came with a specific charge in the organisation, animation, debating and modelling.

RESULTS

Description of SEED-Div

General description

In the RPG SEED-Div each player owns a field on which there are 4 plots. All fields are identical in size and represented as squares within a grid that represents the village fields. Each plot may be on 1 of 2 different types of soils (deep / shallow). All players cultivate the same cereal on their field but 8 varieties of this cereal are available. Each variety is represented by a different colour and has specific typical characteristics (optimal yield, sensitivity to water stress, length and plasticity of the cycle, photoperiodism, size and colour). Each player is initially given seeds from randomly chosen varieties for his 4 plots (seeds for 1 plot is represented by a disc of the colour of the variety). Then at each round (representing a year), the player must plant cereal on its plots by sticking its seeds disc on a card. He can choose among the 8 varieties as long as he is able to get a disc of the proper colour. New seeds can be obtained through harvesting (0, 1 or 2 discs depending on how the variety was appropriate to the climate), through exchange with other players or through external sources such as markets or NGOs. The game can be played with different levels of institutions. In a first step, players can be grouped in "families" where the elder is designed as the chief of the family. Then it is possible to craft a seeds management institution at the scale of the village and play it in the game.

Game description and rules

o The roles :

All players are farmers who owns 1 field in the same village. All fields are identical: 4 plots on 2 type of soils.

Players can be grouped in groups or family where they have to coordinate themselves Specific roles : it is possible to name 1 player per group as the chief of the group. Special roles may also appear when players design the management institution.

o The space and the environment :

The village is represented as a grid of fields. The spatial arrangement and ownership of fields and soils is visible on a board representing the territory.

(FIG 2)

There is a yearly climate characterized by a rain arrival date (early, mean, late) and a rain quantity (low, mean, big).

o The resources and the objects :

The varieties: there are 8 varieties in the village. Each variety has a different yield response to agro climatic conditions (soil and climate) and can be characterized by: its resistance to striga, its photoperiodicity (early, mean, late) and its origin (improved or local).

The production: depending on the variety chosen, the soil and the climate, a plot may produce 0, 1, 2 or 3 units. A farmer needs 4 units a year to survive The seeds : 1 seed unit is necessary to sow a plot with a variety. A seed unit is represented by a disk of the color of the variety. Farmer sow seeds by sticking the disk on their sheet (FIG 1). Depending on plot production, a farmer may get back 0, 1 or 2 unit of seeds.

o The rules A farmer cannot keep seeds that he does not use the following year. Farmers can ask and give seeds to each other at their own will Farmers can get "white" seeds from the market : the variety is unknown a priori and will be discovered only at harvest Special events can bring seeds from outside o The organisation : a time step represents a year Initialisation : each farmer is attributed a field and a set of seeds corresponding to the varieties he owns initially. Phase 1 -variety choosing : A rain arrival date is announced. Farmers can try to get seeds if they are not happy with what they have, either from other players or from the market, unless a special event arrives.

SEED-Div ABRAMI G., BAZILE D., COULIBALY H. And F. BOUSQUET

Phase 2 -sowing : farmers stick 1 seeds disk for each of their plot. When he is over he gives back to the assistant his playing sheet and the seeds he did not use. (FIG 4) Phase 3 -harvest : the rain quantity is announced, as well as the occurrence of striga and farmers get their playing sheets back with their production and their new seeds. The production level of each plot is displayed on the board. Farmer can start exchanging seeds for the next step.

Game settings

o Participants : the game needs quite a big number of participants (15 -30) so that diversity dynamics can be interesting.

o Facilitation team : however there is a bottleneck in the capture of player choices and the allocation and distribution of harvested seeds where a minimal facilitation and assistance team is needed : 1 facilitator, 1 or 2 observers, 1 assistant for the capture, 2 assistants for distributing the seeds and displaying the outputs in case there is no retro projector.

o Material (FIG 1 & 2) : sticking color disks for representing the seeds; playing sheets where players stick the seeds and get results; a lot of cups or glasses to make the color disks easily accessible to the assistant, to put seeds for the market, and possibly to use as a recipient to distribute the seeds to the players; a black or white board and a set of post-its to display outputs, or a retroprojector o Room and space settings (FIG 3) : there are no big constraint on space and room setting. The essential point is that participants should be able to get up and circulate easily, so it is better not to have tables. Then there is the possibility to arrange spatially the players to reflect their land disposition on the grid, as we did in Bamako, but it is not necessary. It can be useful to use spatial arrangement to design several groups where collective management can be asked.

o Preparation : cutting and sorting the seeds disks, printing the players sheets, arranging the room, briefing the facilitation and assistance team being clear about everybody's role, and if no retroprojector drawing the grid and preparing post-its

Results from Bamako's Workshops

Elements of improvement

SeedDiv such as it is described in this paper is the result of the improvements proposed by the farmers during the workshop. Three groups spent a few hours working on specific improvements that should be brought to the game : individual constraints, coordination in the village, local management institution. More specifically, the elements improved by the farmers were :

each farmer owns 4 plots (instead of 1) -each farmer has 2 plots on 1 type of soil, 2 plots on the other 1 -color and resistance to striga added as characteristic of local varieties number of seeds harvested for each level of production market and external input of seeds

The institutions played

After playing individually or within family groups, the farmers were asked to work in groups to craft institutions that could manage the seeds of the game. Three examples of institutions practices were designed with rules by the farmers during one day. The implementation of one of them was experimented during the workshop by all of the participants with fairly elaborated rules. The institution that was tested was a cooperative such as one of the village is working on designing. The rules used for simulating the cooperative were the following :

the cooperative starts with 1 seed of each kind and is able to store seeds for 3 years. Its objective is to have always at least 1 seed of each kind -4 multipliers are needed. A multiplier must use one of its plots for multiplication and gets the seed from the cooperative for this plot. A multiplier can get up to 10 seeds on its multiplying plot if its successful and must give 8 of them back to the cooperative -The seeds produced by the cooperative are of high quality : they give 4 seeds instead of 2 if the plot is successful -Everybody can ask seeds at the cooperative but it has to give it back. If a farmer borrows seeds produced by the cooperative, it has to give 3 seeds back -Cooperative members can access cooperative seeds for only 2 seeds back. The cotisation is 1 seed a year. (FIG 5 & 6) Farmers could test and adapt the rules they just crafted and check how it affected the performance of the institution in maintaining the diversity of variety over time and providing seeds for crops. The result was quite spectacular as the stock of varieties of the cooperative vanished within years! This was mainly due to the failures of multipliers and the fact that farmers were not interested in getting seeds from the cooperative they would have to give back.

General elements of feedback

More generally, the participants of the workshop were happy with the possibility of exchanges opened by this evolutive game, and in particular the exchanges they had around the test of a cooperative. The workshop did close on the engagement of partners NGO to keep on supporting farmers with the creation of cooperatives. The main drawback of the workshop was that it was held in Bamako for logistics simplicity reasons and then was far from any case study site where a field visit could have been organised.

DISCUSSION

Insights from Bamako workshop

The SEED-Div's RPG is actually the result of a long process (3 years) where representative abstractions and key descriptive structural and dynamic elements of local seeds systems were discussed with different groups of farmers during workshops. Despite its very abstract aspects, it actually contains many elements and constraints of the real world and was very easily appropriated and discussed by all the farmers in the workshop.

How do Seed-Div as a methodology

A more general output of the project is that 3 institutions created during the time of the project have beneficed of the support of this process and are still functional.

-Some critical reflections on the ABM in particular on the way the stochasticity of yields is managed how do they fit in a wider context / link with current project IMAS how does Seed-Div as a methodology fits in a wider RPG research context : o an abstract tool to bring participants in stepping back and exchanging ideas on a higher level of abstraction

Decontextualised description

A resource exists in several varieties. At every time step, Producers can transform this resource, reproduce it and exchange it. In the game, the producers try to meet some production objectives. The idea is to check how the diversity of the resource variety evolves in the system and how it may impact on the producers.

Resource transformation

Different kinds of conditions may affect the yield of the resource / product transformation. These conditions may be:

-Changing at every time step but identical for the producers (such as climatic conditions or global external events) -Stable over the time steps but dependant on spatial settings (such as soil types) -Stable over the time but dependant on producer (such as skill or level or equipment) -The different varieties may react differently to an identical set of conditions -An additional random variability might be introduced to represent other kinds of conditions that are not taken in account -The product of the resource is an important economic or subsistence asset for the producers, and the quality of this product and its potential uses may be different depending on the variety of the resource.

Resource reproduction : Unless its production is null, a Producer is always able to reproduce 1 or 2 unity of the resource.

Resource exchange :

-Producers are free to exchange resource units, although a cost (economic or social) may be attached to those exchanges -Under special conditions, some producers might get resources from outside the system. SEED-Div was used successfully during a training session in France and demonstrated its ability for being used as a generic tool for fostering discussions diversity management institutions

Strengths, limits and potential improvements of the tool o limits (drawn from decontextualized description and table ) :

the RPG is valid only for species where there is no genetical drift (autogamous species). This means in particular that it is not possible to use Seed-Div for millet which has an important genetic mixing the RPG as it is is valid only for species where it is possible to master on field seeds selection practices and seeds conservation practices individually on an agronomic point of view, the RPG as it is is valid only for rainfed crops where agronomic conditions are the main drivers of yield response. the RPG such as it is is valid for species where the community is the right scale for local seeds management. However it could be easily adapted to represent a wider territory and other kinds of stakeholders if the focus is on institution crafting it might be interesting and necessary to include more differentiation between the players. Not all members of a community may be able to play the same role in the crafting and functioning of a new institution,n o Potential improvements : Introducing "events" • Justifying stochasticity • Introducing varieties from outside Valuing fallows on bad soils Some contextual rules may need to be specified when the game is played outside its context : farmers did use implicit social and cultural rules when they played Seed-Div that equilibrate the game play. For instance they were not so keen on asking seeds to others as they attach a social cost to it. An affective link to varieties could be recreated by giving qualitative description of the varieties to the players Running simulations over a simplified version where

• agents type 1 try to minimize the risk : after 3 years, they start to look for the variety with the best worst result among their neighbours • agents type 2 try to get the best variety every year : they look for the variety with the best result for the announced climate among their neighbours and go to market if they cannot find it

Try it with • same conditions lead to same results

• fixed individual variability over the different varieties

CONCLUSION

The RPG focuses on the institutional aspects of varietal diversity management. Its specific question was what are the drivers of the diversity at the scale of the village? How to maintain it with a sustainable level of constraint for the community and the individuals? Its aim was to foster discussions between researchers, NGOs, farmers' organisations and farmers on possible management options of the seeds system at the local scale. Then the idea was to have a tool that could allow easily simulating the consequences of individual actions at the collective level and then discussing implicit collective rules, but also implementing explicit collective rules and testing them. In this way it could be used to facilitate and accompany institution's emergence. An additional constraint was that this tool had to be generic enough to have farmers from different regions and contrasted agro-ecological constraints being able to play together and exchange ideas.

The result is that SEED-Div has proven able to simulate seeds exchanges and varietal dynamics within a village. Its abstraction has proven efficient in bringing players to confront contrasted situations even though language barriers. Finally it has proven flexible enough to have players designing and implementing an elaborated local management institution.

The outputs of the overall process was that local actors are engaged in local seeds conservation actions reflecting new approaches of management, sharing and redistribution of agrobiodiversity benefits via a decentralised multiplication coordinated with the local actors.

The perspective is to get farmers organisation performing durably in situ managing local genetic material in seeds banks and cooperatives. After a low period, the work is continuing with the recent start of a new ANR project.

FIG 1 :

 1 FIG 1 : Assitants table with reserves of seeds at the back and at the front players sheets with their choices for several years and players cups with seeds inside ready for being distributed back

http://www.commod.org/pdf/ficheCherIng.pdf

SEED-Div

 ABRAMI G., BAZILE D., COULIBALY H. And F. BOUSQUET SEED-Div ABRAMI G., BAZILE D., COULIBALY H. And F. BOUSQUET