Denis Bouhineau
email: denis.bouhineau@imag.fr

Hamid Chaachoua
email: hamid.chaachoua@imag.fr

Jean- François Nicaud

Jean-François Nicaud
email: jean-francois.nicaud@imag.fr

Helping Teachers Generate Exercises with random coefficients

Keywords: Design of TEL (Technology Enhanced Learning) environments, Pattern of exercises, Tools for Teachers, Training and Test activities, Pedagogical and Didactical Parameters

First, we propose two taxonomies concerning software designed for teaching mathematics, which we call TEL (Technology Enhanced Learning) environments, the first one concerns the teacher's place and role in TEL environments, the second one concerns the activities which are foreseen and provided by TEL environments. Second, we consider TEL environments which provide teachers with tools for building patterns of exercises used in the TEL environment to generate randomly and dynamically exercises or lists of exercises. Our approach is compared to classical approaches (based on standards like IMS-QTI or on Computer Algebra Systems).

Introduction

Since 2000, we are working on the TEL (Technology Enhanced Learning) environment Aplusix dedicated to the teaching and learning of formal algebra at secondary school level, see figure 1. Our main goals were to develop from scratch a high-quality TEL environment useful for research which would works also really at school : easy to use and efficient for learning/teaching. Principles worth following to achieve these goals and lessons learned from our experience have been published recently in .

During a first phase, from 2000 to 2003, most of our work has been devoted to the design of a microworld for learning-by-doing elementary algebra . Main principles used to develop this environment were, first, to let students freely and intuitively build and transform algebraic expressions, as they can do on paper, and second, to give permanent but not intrusive epistemic and fundamental feedbacks on the syntactic and semantic correction of the algebraic reasoning followed by the students. Experiments and usage in usual classes with this microworld have been successful, they have been reported in and Figure 1 Few steps of a student's reasoning in Aplusix to solve a quadratic equation. The first box contains an equation to be solved by the student. The other boxes have been built by the student thanks to the advanced editor of algebraic expressions of the system. The two first steps are correct: the modified equations have the same solutions as the previous one (1 and -3). The last step is not correct: a cross -red on computer screen-is draw over the double equivalent arrow.

The second phase, from 2003 to 2005, introduced a shift in the kind of TEL environment we were working on: we moved from the microworld paradigm to an exerciser paradigm. We worked specifically for math teachers, trying to provide them with tools for managing, improving and facilitating their work. One of our first works was to include an exercises generator for a wide range of algebraic exercises in all the domains available in Aplusix. Then, we introduced two modes for doing the activities in the software: one for training (with feedback, help and hint), one for tests (without feedbacks, help and hint, and with a limited amount of time). In parallel, we developed tools for editing richer exercises and for organizing scenarios of use. We also improved the feedback given to teachers for the analysis of the student's activities. And, finally, we facilitated the installation of the software on network. Thus, we added to Aplusix a map of algebraic exercises, see figure 2. This map of exercises is a set of about 40 families of exercises in formal algebra organized by type of exercise, domain and level of difficulty. The organisation is partly based on didactical variables, partly based on pedagogical reasons. In few words, behind the stage, each family contains about 10 patterns of exercises. More than 500 patterns of exercises have been produced for formal algebra exercises at secondary school level. Not all were used. Each pattern of exercises is defined with a general pattern having random coefficient. For each coefficient a domain of possible values is given. In the pattern, calculi are also described to be performed on the value and on the instantiated exercises. Few elements are also described: mean time to solve the exercise, exercise type, hints to describe the pattern, general family of pattern, pseudo-frequency to set the number of occurrences of the pattern. Finally, and this constitutes an original contribution of that work, the pattern contains constraints to be satisfied: theses constraints are to be tested out to validate an instantiated exercise. These constraints represent a natural way to express that the expected exercises are like the general pattern (with some defined properties given by the general pattern, the calculus and the domain of the coefficient) but not having other properties identified by the constraints. The introduction of such constraints has been decided to ease the work of math teachers and didacticians willing to participate to the definition of the patterns. As a consequence, the exercises are generated from patterns by non trivial random choices of the numbers and with verification of the constraints; see [BOU-05b] for more information.

The families of exercises and the patterns of exercises used in the map of exercises have been built by didacticians in mathematics and an important work has been made with them to define the language used for patterns. The introduction of the concept of 'constraint to be satisfied' is fruit of that effort and has been validated by the effective construction of the map of exercises. But each pattern remains a complex object with a dozen of attributes, see figure 3. The language used to described patterns has a strict syntax (as almost all the formal languages), and unfortunately no editor have been made available for the definition of the map of algebraic exercises. The definition and realization of an editor is time-consuming and were not in our priorities at that time. As a consequence, the process for the writing of the map of exercises was not straightforward: a first version of the patterns was written by didacticians in mathematics, some work was needed then, made by computer scientists to debug some patterns and assemble the patterns in the map of exercises. Then, tests were made by didacticians to validate the exercises and improve them when necessary. Improvements or additions were then possible, restarting the loop or the spiral of design. Our work for helping math teachers on the automatic generation of random exercises has been the opportunity to make short studies about the teacher's place and role in TEL environments and the activities which are foreseen and provided by TEL environments.

The first part of this paper concerns these two taxonomies. Main focus is on TEL environments in mathematics and activities performed in mathematics, but not only.

The second part of this paper is at the cross-road of the two taxonomies, and considers TEL environments which provide math teachers with tools for building patterns of exercises and generating randomly and dynamically lists of exercises. Our approach, and our last developments, will be compared to other typical and standard approaches.

Taxonomies

Teacher's place and role in TEL environments

The first short taxonomy considers teacher's place and role in TEL environments. The goal is to observe particularly if specific parts of TEL environments have been designed for the teacher, and if the answer is yes, what are theses parts. With these questions in mind, and after a short informal study on a set of 21 TEL environments, mostly in the domain of mathematics, four groups can be formed (from the less to the most important place and role offered to teachers):

• T1. TEL environments that simply ignore teachers. They are TEL environments in which no part of the environment has been designed for teacher's use specifically.

No functionality is devoted to the teacher. Teachers and students have the same environment. It does not necessarily mean that teacher has no role in the use of the TEL environment, because it does not necessarily mean that the TEL environment replace or acts as a teacher. Actually, two subgroups may be defined for group T1, the first one (T1.1) where the environment supposes the presence of a teacher who has to organise the activities (create documents on paper, or files to open, conduct and validate him/herself the result of the activity…). In this subgroup, we can place a lot of microworlds. We could also place pieces of software which are not TEL environments but are used in classroom (text editor, calculus sheet…). TEL environments of subgroup T1.1 can be viewed as tools for teachers. Compared to pieces of software which are not TEL environments, they intend to offer a pedagogical added value.

The second group (T1.2) collects the environments which incorporate some kind of electronic teacher to organise the activities (choice of the exercises, diagnosis of the answer…) Most of ITSs -Intelligent Tutoring Systems -belong to that subgroup. At the opposite of the TEL environments of subgroup T1.1, environments of subgroup T1.2 do not need teachers; teachers are just ignored by these environments. Student can use these environments at home, or autonomously in classroom (this could be interesting for teachers willing to work specifically with some other students, and can let the first one work alone).

• T2. TEL environments that give feedback to teachers. Some TEL environments from the previous subgroup T1.2 can give feedback, for example a user model, it consists essentially in showing externally the internal representation of the students, or an historic of the student's actions with simple and local diagnosis of the success or failure of the student. Such feedback can be of importance and interest for the teachers. Some TEL environments have rightly understood that and focus on it. These environments explicitly introduce the role of the teacher as the person for which these feedbacks are given. These TEL environments constitute the subgroup T2.1. Even more, some TEL environments have been specifically designed to give feedbacks to teachers (T2.2). An example is given by TEL environments which are dedicated to competencies diagnosis. These environments are used at the beginning of the year, or before inscription. Usually, TEL environments from that subgroup (T2.2) are not used in class during normal time and their use is very limited. So that subgroup is very small. However, in most of the case, when a TEL environment gives feedback to teachers, it does not belong to group T2, but belongs to one of the two last groups T3 or T4: the place and role of the teacher is larger, in that case, the teacher's role is not only to receive feedbacks.

• T3. TEL environments with teacher's interface to manage classes. The role and place given to teachers in these environments is limited to managing their classes, students and activities (among, most of the time, only predefined activities). Most of the time, teachers can also obtain feedbacks from the environment about the success and failure occurred in the passed activities. Sometimes, environments from group T3 let the teachers specify the behaviours of the TEL environments with pedagogically and didactically meaningful parameters (presence or not of feedback or hint, time to achieve the activity…).

The limitation occurs when the teacher wants to modify the activities predefined in the environment. The main difference between T3 and T4 is the possibility to add new exercises and to organise the scenario of his/her own activities.

• T4. TEL environments with teacher's interface to manage classes and edit activities. These environments propose teachers to manage their classes, students and activities, to specify the behaviours of the environments and to easily modify or enrich the environments with their own activities (lessons, exercises, tests). Two subgroups can be considered in group T4, according to the competencies needed by the teachers to perform all the roles devoted to him. Subgroup T4.1 is for TEL environments asking for no noticeable competencies in computer science. Subgroup T4.2 is for TEL environments asking for noticeable competencies in computer science.

In subgroup T4.1, TEL environments must include very specific parts and functionalities to permit the introduction or edition of one core part of the TEL environment. It does imply an important supplementary work for the designers.

In both cases, T4.1 and T4.2, an important supplementary work is asked to the teacher when s/he wants to add new exercises, and the learning curves to control the given tools are to be considered. Is it worth? Could teachers afford it? Clearly, the teacher has to learn how to use that specific part of the TEL environment. It is worth noting that this specific part is very often delicate and complex. Next, the teacher has to effectively introduce or change the activities. It could mean possibly that, compared to the paper and pencil environment, teacher's work for preparation may be greater than before.

From T1 to T4, the role and place offered to the teacher in the environments increase. Hopefully, it does not necessarily means that, from T1 to T4, the use of TEL environments is heavier for teachers. In a certain extent, TEL environments from T4 could be used as microworld like in T1 without a huge implication of the teacher. The questions arisen in paragraph about T4 about the importance of teacher's competencies are very important and could be reconsidered for all the categories about general teacher's technology competency and teacher's implication needed. The usability and the chance for TEL environments to be adopted and used are tied to the answers to theses questions.

If we consider taxonomies of teachers, from Canada [BIB-06] for example, there exists innovative pioneers, but also resistant to new technology, and in between those who are following the group with more or less scepticism and those who are only following the official directives when some are given by government. A mapping may be done from these categories onto our categories about TEL environments. Every teacher could have some TEL environment adapted to him. Hence, from that mapping one could imagine the number of teachers which would be interested by TEL environment from each category.

Finally, from the set of 21 TEL environments selected for a study in the research community [TEL-06], mostly in mathematics, and in the most advanced commercialised TEL environments in France, we have found out 5 environments belonging to T1, 4 environments belonging to T2, 5 environments belonging to T3 and 7 environments belonging to T4. This is not necessarily representative of all TEL environments designed and used. In fact, we think that our study privileged rich TEL environments. From our research point of view, these are the most interesting ones. From pedagogical point of view, the main interest could be for another group.

Activities foreseen and provided by TEL environments

The second short taxonomy is about the activities which are foreseen and provided by TEL environments. We point out technical and technological competencies needed for these activities and compare these activities done in TEL environments contexts with similar activities accomplished without computer in the regular work of the classes. Our goal is to find what could be the added value brought by computers.

From a global point of view three main activities are considered:

• Lessons. From our point of view (TEL environments designer and developer), the organisation, with a computer, of such learning activities is not the most difficult one. Moreover, in a large part, it is not specific to learning environment. Modern technologies and modern programming languages offer components which permit to easily display and edit multimedia documents with texts, mathematics, images, videos… Even organizing or assembling statically lessons for the construction of curricula is quite easy, or not so difficult. Difficulties and specificities appear when the organisation and the assembly are done automatically, like in . But this is a service which is rarely proposed, and, which still relies heavily on the availability of the content. Our opinion is that the most difficult part related to that activity does not concern designers and developers of TEL environment but people -teachers, didacticians or mathematicians for our concern -who define and create the content of such documents. Moreover, most of the work related to lessons and the way lessons are performed is not specific to TEL environments, it is analogous to the one done without computer.

• Discovery and Training activities. From our point of view, discovery activities and especially training activities introduce important works for designers and developers of TEL environments. When this is well done, it consequently allows added-values in comparison to classroom without computer activities. For example: feedback, hints, randomly generated exercises… One of the major difficulties in our domain (math education) in the design of TEL environments for discovery and training activities come from the necessity for the TEL environment to tackle the complexity of the domain (here mathematics.) We mean, complexity with the representations used, complexity with the semantics of the manipulated objects, complexity with the mathematical rules applied on these objects. One solution consists to link the TEL environment with a math expert: a CAS (Computer Algebra System) and to rely on the CAS for all the mathematical questions. That solution has drawbacks: Will the expert be understandable and understood? How the expert will be controlled? Can we give full freedom to the expert? It is not clear that this solution is the best one. We subscribe to the controversies about the ability of CAS to be the mathematical expert of a TEL environment [PRA-01]. Another solution is to reduce the training activities to multiple choice questions, or activities without any mathematical added-values, depending on the teacher for feedback, hints and creation of exercises.

If we focus on the feedback provided during training activities when students have to practice with exercises to acquire techniques, automatisms and autonomy, we can consider the example of our software Aplusix. We have already pointed out for Aplusix the two fundamental feedbacks, the first one is about semantics, it concerns the equivalence checking, the second one is at crossed-road of syntax and semantics, and it concerns the validation of the end of an exercise. About syntax and semantics considerations, see . The importance of syntactic and semantic feedbacks is essential. Here, the difficulty is that pedagogical and didactical elements may interfere with mathematical elements. Should the software accept mathematically correct answer when these answers are not pedagogically correct? And, how to express the didactical and pedagogical elements to be verified?

• Test activities. Test activities necessitate also important works for designers and developers of TEL environments but consequently allow added-values in comparison to classroom without computer activities, here, for example: automatic mark and diagnosis… About automatic marking, most of the difficulties share the same nature that those seen previously about the design of feedback in training and discovery activities: it is about the necessity for the TEL environment to tackle the complexity of the domain (for us mathematics) and it raises questions about the use of an expert (for us a CAS environment) to achieve that goal.

About diagnosis, difficulties and challenge do not concern mathematics but learning theories, didactics and pedagogy and cannot be solved by general didactical or pedagogical software solutions, because there is not any one available. The domain seems to be much more complex than all those seen previously. And it is not clear that a general diagnostic algorithm of human learning will be found even if some general theories tend toward that goal . Only few local solutions are available, and these local solutions have necessitated a lot of work, see for example systems based on ACT theory [AND-04].

On top of these activities, we must also notice the need for functionalities in TEL environments for managing students, classes, lessons, exercises and tests, and for sequencing the execution of such activities. Fortunately, there exists some general solutions for defining and playing scenarios composed of such activities, with selected students.

Considering usages, if we take into account what is working really in classes, from [BAL-05], out of the tree main activities seen above, the most important one, far ahead from the other is the discovery and training activity. In particular, activities where students have to work autonomously are pointed out in as what can make the difference for a successful integration of new technology at school.

Building patterns of exercises

The last part of this communication is at the cross-road of the two previous taxonomies. It considers TEL environments in mathematics which provide teachers with tools for building exercises (or patterns of exercises) in the TEL environment in order to produce personalized training activities (or to generate randomly and dynamically lists of exercises). Three solutions can be observed:

• Pedagogical Web Standard approach. In other words, we are thinking about standards like IMS-QTI . The advantage targeted by the use of such solutions is to gain compatibility and possible interoperability between different platforms and materials from different authors.

The first main problem is that pedagogical standard like IMS-QTI does not know a lot about mathematics. To some extent, this is not so important when the only training activities concern multiple choice questions. But for open exercises, or unsolved exercises this could appear to be a major inconvenient. Some tentative exists to introduce Mathematics in standard [MathQTI], but generalisation to other domains are not available, and even the MathQTI is not sure to become a success used by every software.

The second main problem is that this approach necessitates that the teacher willing to introduce new exercises, or pattern of exercises, must be familiar with the languages used like IMS-QTI, IMS-SS, IMS-LD, IMS-CP, LOM… Even for people aware of every new technology, this is a challenge. When user-friendly editors will be available, this solution could be practical, but it is not sure that in the next future user-friendly editors will appears. The languages IMS-* continue to evolve, for example in France for the LOM standard, evolution tends to add some specifics pedagogical elements or try to define the vocabulary used by index. One reason to understand why this approach is not 'naturally' suited for math teacher is to be found when we consider the goal of the IMS consortium: seems to be more oriented toward industries and institution than toward teachers.

• Specifically Math web approach with CAS. The most commonly used approach consists to integrate Computer Algebra Systems to open-source or proprietary web system, for ex. [Web+CAS]. In such systems, math teachers can write small algorithms to generate the mathematical part of the exercises. Of course it does necessitate knowing, using and mastering a programming language, usually the programming language of the CAS.

About the organization of exercises and pedagogical issues, web programming techniques are used (php, mysql…). Fortunately, these parts of the system can be and usually are hidden to math teachers, and the system behaves with default process. Last, but not least, about presentation and representations of the content and the math content, when editors are not available, math teachers have to know a little about web language (html, css…) but are then free to present their activities attractively, with animation, colours...

The major inconvenient of that approach is that it does necessitate that the teacher willing to introduce new exercises or pattern of exercises must be familiar with technologies and programming languages used by CAS and Web platforms. Even if CAS technologies and programming languages are more familiar to math teachers and technologies and programming languages of web platform are much more widespread in our society that approach still concern specialists up to date with new technologies.

• (Our) Teacher-friendly approach. Our approach tries to avoid the burden of technology by giving teacher, first, easy to use and efficient tools to design exercises and pattern of exercises, and second, by trying to help the teacher with intelligent functionalities which would give him feedback about what s/he has done, and what will be the result.

The first element of that approach is the design and realization of an editor for pattern of exercises and map of exercises. For exercises, the Aplusix environment already contains an exercise editor. It will not be described here. For pattern of exercises, our work relies on the work already done in Aplusix to give a definition and a structure to the global object 'pattern of exercises' . It leads to the previously described map of exercises with patterns of exercises. Until now, these patterns were hidden and unreachable. Teachers were asking for some control on it (visualize them, edit them), so we have worked on the design of a user friendly interface for teachers.

Two ideas have conducted our work. The first idea was to try to escape the use of formal language or programming language: whether responses are given in some natural language or responses are to be selected from predefined lists of items. The second idea is to provide the teacher with examples of instantiation of the pattern as soon as enough elements are defined (see right panel, figure 4). This is the major part of the second element of our approach. In fact, we try to give immediate non intrusive feedbacks. This follows the same ideas as in the main part of the Aplusix environment, the part devoted to students. Another feedback is also available: a rough evaluation of the number of different instantiated exercises produced with the current pattern. We also thought about an automatic calculation of the solution of the instantiated exercises, and of the complexity of the resolution (with the number of elementary steps to be performed to achieve a solution) but we did not achieve that part.

We also added the possibility to use Aplusix with the new pattern of exercises as soon as that pattern is 'correct', in the same condition as a student would do. And last, the teacher can organize his patterns in a tree-like manner, and reutilize patterns available in Aplusix.

Conclusion

On the occasion of the design of a prototype for a pattern editor in Aplusix, we have studied: first the role and place given to teachers in TEL environments, second, the activities foreseen in TEL environments, and at the cross-road, ways TEL environments propose to build exercises and patterns of exercises. From these studies, we have observed the influence of learning/teaching theories (behaviourism, constructivism, socio-constructivism…) According to us, such influence is due partly from the design of TEL environments and there are ways to liberated usages from it when TEL environments are been planned to cope with a lot of situations, and even permit free activities.

About the pattern editor, patterns of exercises were not new in Aplusix and generated exercises were appreciated by teachers, but patterns were unreachable and teachers asked for some control on them, so we have worked on a prototype of an editor. This is a first step toward an editor of pattern of exercises which could be integrated in the next version of Aplusix.

About generating exercises with random coefficients, two perspectives for the future can be imagined. The first one would be to try to extract the didactical variables used to define the hierarchy of patterns of exercises existing in the map of exercises of Aplusix in order to build a new generator of exercises whose input would not be patterns itself but didactical variables. The second one would be to find a way to introduce didactics in the pedagogical construction imagined in the IMS-like standards.

About usage, the new prototype permits the definition of two medium sized (fifteen families of exercises, more than fifty patterns), but fully usable, maps of exercises of arithmetic at elementary schools in few hours (less than 3h.) This is to be compared to the

Figure 2

 2 Figure 2 The map of exercises. When the student clicks on a dot, s/he gets a description of the family in the bottom part and a menu for launching the family in the training or test mode.

Figure 3

 3 Figure 3 Example of a pattern: x remains abstract variable, a and b are instantiated with products d.c and e.c where c and d are small strictly positive integers, e is a nonnull, c is non-unitary integer. For example, that pattern can produce the following expression 18x²+30x, 12x-9x and 14x²+7x. Factoring these expressions should reveal the c coefficient. With these examples, it should leads to 6x(x+5), 3x(4x-3) and 7x(2x+1).

Figure 4

 4 Figure 4 Editing patterns of exercises in Aplusix (prototype).

number of days, and even weeks, the first map (thirty eight families of exercises, more than three hundreds of patterns) necessitated.

The building of the editor introduces a shift in the way patterns of exercises and map of exercises are organized and taken into account in Aplusix, but this is another story.


Denis Bouhineau

Hamid Chaachoua

Camille Douine

Jean-Francois Nicaud

ICTMT8, Theme: Designing and using Dynamic Mathematics environments Helping Teachers Generate Exercises with random coefficients

Keywords: Design of TEL environments, Training and Test activities, Pedagogical and Didactical Parameters, Pattern of exercises

First, we propose two taxonomies concerning software designed for teaching mathematics, which we call TEL (Technology Enhanced Learning) environment, the first one is on teacher's place and role in TEL environments, the other one is on the activities which are foreseen and provided by TEL environments. Second, we consider TEL environments which provide teachers with tools for building patterns of exercises used in the TEL environment to generate randomly and dynamically exercises or list of exercises. Our approach is compared to classical approaches (based on standards like IMS-QTI or on Computer Algebra Systems).

Introduction

Since 2000, we are working on the TEL (Technology Enhanced Learning) environment Aplusix dedicated to the teaching and learning of formal algebra at secondary school level. During a first phase, from 2000 to 2003, most of our work has been devoted to the design of a microworld for learning by doing elementary algebra . Main principles used to develop this environment were, first, to let students freely and intuitively build and transform algebraic expressions, as they can do on paper, and second, to give permanent but not intrusive epistemic and fundamental feedbacks on the syntactic and semantic correction of the reasoning followed by the students. The second phase, from 2003 to 2005 introduced a shift in the kind of TEL environment we were working on: we moved from the microworld paradigm to an exerciser paradigm. We worked specifically for teachers, trying to provide them with tools for managing and improving or facilitating their work. In particular, we added to Aplusix a map of exercises which is a set of about 40 families of exercises based on didactical variables and organized by type of exercise and level of difficulty. Each family contains about 10 patterns of exercises having variables for the numbers and constraints to be satisfied. The exercises are generated from patterns by non trivial random choices of the numbers and verification of the constraints; see . The families of exercises and the patterns of exercises used in the map of exercises have been built by didacticians in mathematics and an important work has been made with them to define the language used for patterns. Each pattern is an object with a dozen of attributes (ex: the pattern itself with parameters, the domain for the value of parameters and constraint to be tested out to validate an instantiated exercise, mean time to solve the exercise, exercise type, hints to describe the pattern, general family of pattern, pseudo-frequency to set the number of apparition of the pattern).

Our work for helping teacher on the automatic generation of random exercises have been the occasion to make short studies about the teacher's place and role in TEL environments and the activities which are foreseen and provided by TEL environments. The first part of this communication will be about these two taxonomies. The second part of our communication will be at the cross point of the two taxonomies, and considers TEL environments which provide teachers with tools for building patterns of exercises and generating randomly and dynamically list of exercises. Our approach, and the last developments of our work, will be compared to other typical and standard approaches.

Taxonomies

Teacher's place and role in TEL environments

The first short taxonomy considers teacher's place and role in TEL environments. The goal is to observe particularly if specific parts of TEL environments have been designed for the teacher, and if the answer is yes, what are theses parts. With these questions in mind, four groups can be described (from less to most place and role):

• T1. TEL environments that simply ignore teachers. None part of the TEL environment has been designed for teacher's use specifically. None functionality is devoted to the teacher. It does not mean that teacher has no role in the use of the TEL environment, because it does not mean that the TEL environment acts as a teacher. Two subgroups may be defined for that group, the first one (T1.1) where the TEL environment supposes the presence of a teacher which has to organise the activities (a lot of microworlds belong to that subgroup), the second one (T1.2) where the TEL environment incorporates an electronic teacher (most of ITS -Intelligent Tutoring Systems-belong to that subgroup). • T2. TEL environments that give feedbacks to teachers. Some TEL environment from the previous subgroup T1.2 can give feedbacks to teachers, for example a user model, or a historic of the student's actions. In that case, the part of the TEL environment consists essentially in showing externally the internal representation of the students (T2.1). Some TEL environments have been specifically designed to give feedbacks to teachers (T2.2), for example some TEL environment are dedicated to competencies diagnosis. Frequently, TEL environments from that subgroup (T2.2) are not used in class during normal time and their use is very limited. So that subgroup is very small, in most of the case, when a TEL environment gives feedback to teachers, it belongs to one of the two last groups. • T3. TEL environments with teacher's interface to manage classes. The role and place given to teachers is limited to manage their classes, students and activities (among predefined activities) and, sometimes, to specify the behaviours of the TEL environments with pedagogically and didactically meaningful parameters. The limitation occurs when the teacher want to modify the activities predefined in the TEL environment. The main difference between T3 and T4 is the possibility to add new exercises. • T4. TEL environments teacher's interface to manage classes and edit activities. These are TEL environments that propose teachers to manage their classes, students and activities, to specify the behaviours of the TEL environments and to easily modify or enrich the TEL environments with their own activities (lessons, exercises, tests) without noticeable competencies in computer science. This means that the TEL environment must include very specific part and functionalities to permit the introduction or edition of one core part of the TEL environment. It does imply, first, an important supplementary work for the TEL environment's designers, second, an important supplementary work for teacher. Clearly, in that case, the teacher has to learn how to use that specific part of the TEL environment. It is worth noting that this specific part is very often delicate and complex. Next, the teacher has to effectively introduce or change the activities. It does mean that, compared to the paper and pencil environment, teacher's work for preparation may be greater than before.

From T1 to T4, teacher's role and place in the environments increase. Hopefully, it does not necessarily means that, from T1 to T4, the use of TEL environments is heavier for teachers. In a certain extent, TEL environments from T4 could be used as microworld like in T1 without a huge implication of the teacher. The questions arisen here about the importance of teacher's competencies and implication are important when we consider usability and the chance for TEL environments to be adopted and used From a set of 21 TEL environments selected for a study in the research community [TEL-06], and in the most advanced commercialised TEL environments, we have found out 5 TEL environments belonging to T1, 4 belonging to T2, 5 belonging to T3, 7 belonging to T4. This is not necessarily representative of all TEL environments designed and used. We think that our study privileged rich TEL environments.

Activities foreseen and provided by TEL environments

The second short taxonomy is about the activities which are foreseen and provided by TEL environments. We point out technical and technological competencies needed for these activities and compare these activities done in TEL environments contexts with similar activities accomplished without computer in the regular work of the classes.

From a global point of view three main activities are considered:

• Lessons. From our point of view (TEL environments design and development), the organisation of such activities is not the most difficult one. Modern programming languages offer components which permit to display multimedia documents with texts, mathematics, images, videos… The most difficult part related to that activity does not concern designers and developers of TEL environment but people -teachers, didacticians or mathematicians -who define and create the content of such documents. The work related to lessons and the way lessons are performed is not specific to TEL environments, it is analogous to the one done without computer.

• Training activities. From our point of view, training activities introduce important works for designer and developer of TEL environment but consequently allow added-values in comparison to classroom without computer activities, for example: feedbacks, hints, randomly generated exercises… Difficulties come from the necessity for the TEL environment to tackle the complexity of mathematics. One solution consists to link the TEL environment with CAS (Computer Algebra Systems) and to rely on CAS for all the mathematical questions, but it is not clear that this solution is the best one. We subscribe to the controversies about the ability of CAS to be the mathematical expert of a TEL environment [PRA-01]. Another solution is to reduce the training activities to multiple choice questions, or activities without any addedvalues, depending on the teacher for feedbacks, hints and creation of exercises.

If we focus on the feedbacks provided during training activities when students have to practice with exercises to acquire techniques and automatisms, we have already pointed out for Aplusix the two fundamental feedbacks, the first one concern the equivalence checking, the second one concern the validation of the end of an exercise. The difficulty is that minor pedagogical and didactical elements interfere with major and essential mathematical elements. • Test activities. Test activities necessitate also important works for designer and developer of TEL environment but consequently allow added-values in comparison to classroom without computer activities, here, for example: automatic mark and diagnostic… Difficulties do not concern mathematics but essentially didactics and pedagogy and cannot be solved by general didactical or pedagogical software solutions, because there does not exist any one.

On top of these activities, we must notice, also, the need for functionalities in TEL environments for managing and sequencing the execution of such activities; fortunately, there exists some general solution for defining and playing scenarios composed of such activities.

Building patterns of exercises

The second part of our communication is at the cross point of the two previous taxonomies, it considers TEL environments which provide teachers with tools for building exercises or patterns of exercises in the TEL environment to generate randomly and dynamically list of exercises for training activities. Three solutions can be observed:

• Pedagogical Web Standard approach. We have to look at the standards like IMS-QTI [IMS-04]. The advantage targeted by the use of such solution is to gain compatibility and possible interoperability. The first main problem is that pedagogical standard like IMS-QTI does not know a lot about mathematics. To some extent, this is not so important when the only training activities concern multiple choice questions. But for open exercises, this could appear to be a major inconvenient. Some tentative exists to introduce Mathematics in standard [MathQTI].

The second main problem is that this approach necessitates that the teacher willing to introduce new exercises, or pattern of exercises, must be familiar with the languages used like IMS-QTI, IMS-SS, IMS-LD, IMS-CP, LOM … • Specifically Math web approach with CAS. The most commonly used approach consists to integrate Computer Algebra Systems to proprietary web system so that the teacher can write and organize the execution of small algorithms to generate the mathematical part of the exercises, for ex. [Web+Cas]. In that circumstance, web techniques are used for pedagogical organisations and representations. The major inconvenient of that approach is that it does necessitate that the teacher willing to introduce new exercises or pattern of exercises must be familiar with programming languages used by CAS and Web platforms. • (Our) Teacher-friendly approach. Our approach tries to avoid the burden of technology by giving teacher easy to use, intelligent and efficient tools to design exercises and pattern of exercises. For exercises, the Aplusix environment already contains an exercise editor. It will not be described here. For pattern of exercises, our work relies on the work already done in Aplusix to give a definition and a structure to the global object 'pattern of exercises' .

It leads to the previously described map of exercises with patterns of exercises. But these patterns were hidden and unreachable, teachers were asking for some control on it, so we have worked on the design of a user friendly interface for teachers. Two ideas have conducted our work. The first idea was to try to escape the programming language barrier: whether responses are given in some natural language or responses are to be selected from predefined list of items.

The second idea is to provide the teacher with examples of instantiation of the pattern as soon as enough elements are defined (see right panel, figure 3). In fact, we try to give immediate non intrusive feedbacks and permit natural use, as in Aplusix for students.

Conclusion

At the occasion of the design of a prototype for a pattern editor in Aplusix, we have studied, first the role and place given to teachers in TEL environments, second, the activities foreseen in TEL environments, and at the cross point, ways TEL environments propose to build exercises and patterns of exercises. From these studies, we have observed the influence of learning/teaching theory (behaviourism, constructivism, socio-constructivism…) According to us, such influence are due partly from the design of TEL environments and there are ways to liberated usages from it when TEL environments are been planned to cope with a lot of situations, and even permit free activities.

About the pattern editor, patterns of exercises were not new in Aplusix and generated exercises were appreciated by teachers, but patterns were unreachable and teachers asked for some control on it, so we have worked on a prototype of an editor. This is a first step toward an editor of pattern of exercise which could be integrated in the next version of Aplusix.

About generating exercises with random coefficients, two perspectives for the future can be imagined. The first one would be to try to extract the didactical variables used to define the hierarchy of patterns of exercises existing in the map of exercises of Aplusix, in order to build a new generator of exercises whose input would not be patterns but didactical variables. The second one would be to find a way to introduce didactics in the pedagogical construction imagine in the IMS-like standards.

Figure 1 :

 1 Figure 1: First step of reasoning in Aplusix, further steps should follow to achieve a solution.

Figure 2 :

 2 Figure 2: The map of exercises. When the student clicks on a point, s/he gets a description of the family in the bottom part and a menu for launching the family in the training or test mode.

Figure 3 :

 3 Figure 3: Editing patterns of exercises in Aplusix (prototype)


Denis Bouhineau

Thomas Huguet

Jean-François Nicaud

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


Denis Bouhineau
email: bouhineau@irin.univ-nantes.fr

Jean-François Nicaud
email: nicaud@irin.univ-nantes.fr

Xavier Pavard
email: pavard@irin.univ-nantes.fr

Edix : A Software For Editing Algebraic Expressions

The paper presents a computer software, called Edix, devoted to the edition of algebraic expressions in their usual 2D representation. At present, many systems display fine algebraic expressions, but the edition of such expressions is weak. Systems like Word and FrameMaker place sub-expressions in too many boxes so that many editing actions are not simple, while usual CAS (computer algebra systems) just use a 1D representation for the edition. Furthermore, Edix allows the user to represent a reasoning as a sequence or a tree, and evaluates the equivalence indicating at each input whether the current step is equivalent to the previous one.

The edition facilities of Edix are very ergonomic and algebraically oriented. This has been obtained by using an external representation at the interface where parts of expressions sometimes are invisible boxes, sometimes are text, and an internal representation as a tree. A correspondence between these representations has been built, including the insertion point that can be placed with the mouse and moved with arrows. A selection with the mouse of well-formed subexpressions has been implemented including the selection of several parts. For example, it is possible to select x and 2y in x+3+2y-z. It is possible to apply some operators to a selected sub-expression, for example the go-to-denominator operator. In the previous example, it leads to ?/(x+2y)+3-z (where the question mark stands for something to complete; of course it is in the 2D representation and without parentheses).

Usual edition actions have been implemented on selected subexpressions: copy, cut, paste, and drag&drop. We have defined an algebraic-paste as a paste with an operator. We have limited the operators to the commutative and associative operators of the right type (+ and * for the algebraic type, 'and' and 'or' for the Boolean type). When a paste occurs, it is performed with one operator. The user may switch to the other by hitting the ctrl-A key. For example, when x+3 is pasted on the right of y in y+z, the result is y+x+3+z, hitting the ctrl-A key provides y(x+3)+z. We have also implemented a text-paste with the Alt key, e.g., x+3 text-pasted on the right of 4 in 4y provides 4x+3y. Drag&drop works like paste for the drop. The paper will present the main principles of the edition actions.

Expressions that are unachieved (with question marks), not wellformed (e.g., with unbalanced parentheses), or undefined (e.g., with 0 in a denominator) may be produced; the sub-expressions at the origin of the problem are displayed in blue or red to indicate the problem to the user.

A reasoning is represented at the interface with boxes linked with arrows, each box containing an expression, the link between two boxes meaning that the expressions are equivalent. A click on a special part of a box containing an expression E allows the user to produce a copy of this box if E is well-formed and, when E is the successor of U, if E is equivalent to U. If E is not equivalent to U, the link between U and E is destroyed, E becoming the starting point of a new reasoning. When an expression E which is the successor of U is modified, at each elementary modification, the information 'E is not well-formed' is indicated with a bleu cross on the link between U and E, and the information 'E is not equivalent to U' is indicated with a red cross. So, the user is always informed of the status of the edited expressions.

The semantics we use for the equivalence is the semantics of functions. At present, the domain used is the set R of real numbers (in the future, we will allow the user to choose between the real and the complex numbers). Two algebraic expressions A and B with variables x1, x2 … xn. are equivalent if and only if the associated functions from R^n to R are identical. Two logical expressions are equivalent if and only if the associated functions from R^n to {false, true} are identical. At present, we have implemented the calculation of the equivalence for polynomials with n variables, equations with one variable and degree less than 4 and systems of linear equations with n variables and p equations. We will extend a little these calculations and connect Edix to a CAS when more complex equivalences will have to be computed.

We consider several contexts for using the Edix software: (1) as a microworld for education, with parameters to adapt the system to the level of the student (2) as a general micoworld for people working on algebraic expressions, (3) as a component plugged inside systems (e.g., word processing, CAS) for the edition of algebraic expressions, If the paper is accepted, the presentation will include a demonstration.


Denis Bouhineau
email: denis.bouhineau@irin.univ-nantes.fr

Jean-François Nicaud
email: jean-francois.nicaud@irin.univ-nantes.fr

Implementation of the algebraic layer of the new APLUSIX with rewriting rules

The APLUSIX project undertook to carry out a certain number of evolutions these last years to reach the features of a product aiming at the teaching of formal algebra, usable throughout school course for pupils from secondary school to high school. This article relates to the modification and the choices on the lowest level concerning mathematics in the system, that is the first algebraic layer of the system used to define the processing of general expressions handled in the system. At this level, a set of rewriting rules is used to describe possible mathematical handling, which is associated with a rich mechanism with parameters for matching.

General Presentation

Since 1988, the APLUSIX project aims at the modelling of human knowledge in the field of mathematics, and mode precisely in the field of formal algebra, with as a general goal the realization of interactive human learning environment used in classroom for learning mathematics. Thus, and until 1998, several prototypes have been developed on Macintosh in Lisp and regularly tested by professors of mathematics, and by psychologists; since 1998, an innovative work is done to reach the feature of a product to replace these prototypes. The results obtained with the prototypes are positive under several aspects: the pupils appreciate the system, the tests and the analysis carried out from protocols after experiments shows progress, the teachers note that the system brings a structuring of the field for the pupils; for more information about the teaching capabilities of APLUSIX see [START_REF] Nguyen-Xuan | [END_REF].

The prototype and the future product are functioning in the same way: according to two modes of interactions. The first mode is a mode of observation, where the pupil is supposed to look at the system as the system is solving a problem, the pupil can ask explanation about the action of the system. The resolution is carried out step by step, by using a pedagogical engine of resolution based on an expert system using the mathematical knowledge acquired on the level of the pupil, using simple strategic knowledge and a teacher controller to check the relevance of the action. The second mode of interaction is a mode of action, where the pupil is confronted with a problem that has to be solved step by step. The steps are to be chosen among a list of usual algebraic manipulations (use of arithmetic reduction, use of development, use of factorisation, etc.)

Explicit calculations at the arithmetic level, like calculation of the result of an addition, or a product, etc., are performed by the system itself. It guarantees that the handled expressions are all well equivalent from an algebraic point of view, it prohibits the introduction of errors of 'calculation'. An analysis of the steps requested by the pupil is done by the system and possibly one step can be refused to the pupil if this step is erroneous from a mathematical point of view or awkward from a strategic point of view. In this mode, the pupil has the possibility to ask for help. The expert engine builds this help and take into account the resolution undertake by the pupil.

Figure 1: Layout for the prototypes of APLUSIX In order to obtain a maximum of significant results, the prototypes of the project had some limitations. First, concerning the school level, the prototypes relate essentially to the French pupils aged from 14' to 16' (from 'quatrième' to 'seconde'). Problems concerning rational fractions, and algebraic manipulations with discriminant are not considered.

Second, with regard to the class of algebraic problems dealt with, the major class of problems concerns factorisation of polynomials and solutions of polynomial equations. Systems of equation, and inequation are not carried out.

These limitations stated, now let us note the positive points that represent particular work in the APLUSIX project. First, APLUSIX is not only a model for interactive human learning environment, or a theoretical tool for the construction and the modelling of human knowledge in situation of learning. It is also an example of software which really works and which has been used for long periods in front of pupils. In particular, with regard to the achievement in the school area, these efforts represent an important work on the interface pupil-computer and on ergonomic as for the input of expressions and for the output of theses expressions. For example, expressions in shortened, natural, form like '3x+2y=5' are accepted, but expressions or sub-expressions which are not valid from a mathematical point of view cannot be selected. For example, a pupil cannot select (with mouse or keyboard) the expression 'x+2' as a sub-expression of the expression '3x+2y=5'. Second, for the display, algebraic expressions are drawn graphically in a two-dimensioned area. Third, at the strategic level, the development of calculations and search are done according to a tree with the possibility to backtrack, and to have several paths developed concurrently.

In term of Interactive Learning Environment, APLUSIX is halfway between the tutors and the micro-world. As a tutor, it is able to bring a pedagogical diagnosis with respect to a mathematical activity. It is able, also, to organize a sequence of exercises according to the progression of the competences of the pupil. That makes it possible to carry out a run with a professor. As a micro-world, it keeps the openness for new situations and unprepared exercises. The set of allowed algebraic manipulations is defined with parameters, the set of acceptable expressions in input is open, and solutions of one particular problem are not limited to one particular expression but mathematically defined. Efforts have been carried out to ensure a form of transparency in the design of APLUSIX, so that the users or possible analyst can have a rather precise idea of its behaviour. A model described at knowledge-level of the prototypes was published in [Nicaud-1994]. This model is available on Internet http://www.sciences.univ-nantes.fr/info/recherche/ia/projects/aplusix. In the future product, the set of rewriting rules used to describe the behaviour of the software is accessible to the user and is written in readable form. A modification of this set -at the risk of the usertransforms the behaviour of the software. The syntax of the mathematical expression in this set is flexible and natural, as it has been expressed earlier. Attention, however, this transparency aims at an informed public, and modification of the set of rule aims at an expert public.

We hope, so, that different versions of APLUSIX adapted to particular situations can be achieved in an independent way, for example for physicists or for precise corpus of mathematics in college.

The objective for the APLUSIX project is the production of an opened system largely diffused and able to bring help in the learning in the field of formal algebra during several years, this help consisting in mainly framing the pupils to solve open exercises.

Rewriting rules

In the architecture of APLUSIX, see figure 3, the first layer concerning mathematics includes the definition of the structures of the data to represent the current algebraic expression and the definition of possible algebraic manipulation. Expression are represented as trees, with, for the leaves, the symbols and numerical constants, and for the nodes, the operators: functions, minus and parenthesis are considered as unary operators, fractions and equalities are considered as binary operators and sum and product are considered as n-ary operators. The algebraic manipulations are human readably described in the form of rewriting rules in a file accessible from the user among configuration files of APLUSIX.

One will note two ruptures for the APLUSIX project, on the one hand the use of rewriting rules instead of internal function based on a complete programming language (LISP), on the other hand the transparency and the accessibility of these definition at a level of knowledge less specialized. These rules comprise three parts; the last part -Condition-is optional. The first two parts are sometimes called 'left part' and 'right part'. During the application of a rewriting rule, the left part can be called 'model'. If it matches with a particular expression that we will call 'Candidate', three results are obtained. The first result is that the rule applies to the candidate. The second result is a list of substitutions corresponding to the matching between the model and the candidate. The third result is the right part of the rewriting rule where the variables have been changed to respect the matching between the model and the candidate and the optional conditions. This second result, that is the list of substitutions, is not strictly equivalent to the third result because of the application of optional conditions.

Examples of rewriting rules are given figure 5. When a rewriting rule comprises a 'Condition', it is applicable only if this condition is verified. The conditions appearing in this grammar are of two different kinds, the conditions of 'type', and the conditions of ' calculus'. The conditions of 'type' require that a variable is of an algebraic particular type, like a sum, a square root, etc. This type is given ' by the example' as being the type of the expression between parentheses. It is the internal structure (that is the internal data structure) of the expression that determines it. As a tree whose nodes are typified represents each expression, the type of the root gives the type of the expression. Among the types, one finds the current types: sum, product, fraction, raise to a power, square root, constant, symbol, parenthesis, function (sine, cosine...). Minus being a unary operator, there is no type 'difference', but a type 'opposite'.

The conditions of 'calculus' impose that the expression given between parentheses is calculable and that the result of this calculation can be equal to a certain expression (identifier or constant). These conditions of 'calculus' make it possible to give values to new variables and to introduce them into the result of a rewriting (or right part of the rewriting rule) or to check numerical constraints.

Examples of application of rewriting rules are given figure 6.

Candidate

Applied rewriting rule Resultat The rewriting rules are grouped in classes, one rewriting rule can possibly appear in several classes. Among the classes, there is: the reductions (with the following subclasses: immediate reductions, usual reductions), factorisations (with the following subclasses: immediate factorisations, usual factorisations, factorisations according to a remarkable identity), developments, productions of squares, normal forms (for example in order to sort the monomials in a polynomial form). There will be, more or less, from ten to twenty classes or subclasses and about one hundred rewriting rules.

Examples of classes are given figure 7.

For each class of rewriting rules, several formal questions arise, as in any rewriting systems; see [Dershowitz & Jouannaud-1989] for a complete explanation if necessary. Is the rewriting system made of the rule of one or multiple classes confluent? That is, does the results of the application of different rules leads to completely different solutions? Does it terminate? That is, does the recursive application of all the possible rules finish after a finite number of steps without any rule to applies or can it be performed indefinitely? Is the system correct? That is, are the solutions given by the application of the system correct? Is the system complete? That is, can we obtain with the system all the existing solutions?

A more difficult set of questions arises when the theory of rewriting systems is confronted with educational issues. Is the rewriting systems made of the rules of one or multiple classes confluent, complete, correct and does it terminate in the context where are the pupils?

Classes

Rewriting rules For example, for the class of the reductions, it seems natural to ask that the rewriting system made of these rules terminates. However, this system does not have to be confluent (the expression 0+3x+5 can be reduced to 3x+5 if we reduce 0+3x as well as it can be reduced to 5+3x if we reduce 0+5) Proving that this system terminates is not straightforward. And, in fact, we do not have yet made any proof. Let us explain why. If one considers only the class of the immediate reductions, already a problem consists in proving formally that these rules form a system with termination. Usually, the proof of termination for reduction systems are simple, they take their argument on the fact that the length of the character string representing the expression decreases strictly after application of any rewriting rule. Here, the class suggested on figure 7 without the rule '(a*b)^n → a^n*b^n' answers this criteria, therefore it finishes. But when we add this rule, this simple proof is not valid any more. Does this mean that the rule '(a*b)^n → a^n*b^n' is not a reduction? Let us consider this rule '(a*b)^n → a^n*b^n': the linear form (linear opposed to the two-dimensioned form in figure 8) used for the expression of this rule answers to our preoccupation for readability and portability, but this linear form produces an important conceptual shift in comparison to the more natural way this reduction is expressed in twodimensioned form in figure 8. Note that in the linear representation of the rule '(a*b)^n → a^n*b^n', the number of characters on both sides of arrow is the same (and that could lead us to the conclusion that it is not a reduction), but do not correspond to the number of characters in the two-dimensioned form of figure 8. If we consider the two-dimensioned point of view the number of characters decreases, it is a reduction and so, the reduction system terminates. But in this two-dimensioned representation, it would have been more rigorous to say that the exponentiation introduces two pieces of information: the rise (compared to the base line) and the size reduction of the writing of the exponent. These two pieces of information are necessary to differentiate two possible interpretations for a^b^c: (a^b)^c and a^(b^c) as they appear on figure 9 and9'. If one takes into account the information described here, the rewriting rule '(a*b)^n → a^n*b^n' increases the number, and then it cannot be a reduction! Yet, for various reasons one wants that '(a*b)^n → a^n*b^n' is a reduction. Applied to polynomial: X n Y n is a product of monomials whereas (XY) n is a complex expression with a product of monomials and a rise to the power n. Applied to 'a' a constant, for example 3 and b a monomial X: 3 n X n can be reduce to obtain 9X n whereas (3X) n cannot be reduced. This explains the difficulty to prove formal properties on real systems used for teaching. Reality is quite complex. Other examples of formal property we would like to prove concerns classes of rule for the setting in normal form or the setting in canonical form this class must be confluent. The difficulty is the same. For the moment, we do not have given any formal proof for these properties, even if we are sure that our system owns these properties. One of our reasons is the difficulty of the proof; the second is that we do not want a syntactic (and quite technical) proof, but a semantic (and meaningful) proof because a syntactic proof would only be shared with specialists of rewriting systems and not with specialists of education, as could be a semantic proof.

Immediate reductions

(A*B) n --->>> A n * B n
In direct relationship with the rewriting rules presented here, the following section will relate to the mechanism of matching used to determine if a rule can be applied.

Mechanism for matching

The application of the rewriting rules requires the use of a mechanism of matching which, being given an expression candidate C, determines if a rule R is applicable and gives in this case a list of substitutions S for the variables of the left part of the rule (the model) corresponding to the matching between the candidate and the model.

The mechanism of matching used in APLUSIX is a form adapted to mathematics and formal algebra of the algorithms for unification which one finds in the logical or functional programming language. One can find another kind of matching algorithm in the Unix shell, and script language with joker and regular expressions that are adapted to file systems and to the processing of set of strings as in natural language data processing. See [Boizumault-1988] for unification in PROLOG and [Cousineau & Mauny-1995] for CAML. Precisely, the required matching is of the type discussed in [Borning & Bundy-1999]. Examples of the required matching are given figure 10.

Candidate

Model Substitution The required matching has to take into account the mathematical properties of the operators, (associative, commutative, existence of neutral elements). Matching must be able to be carried out on clean mathematical sub-expression of the candidate (that is quite classic in rewriting systems). The matching has to find substitution even if the candidate corresponds to the model multiplied by a numerical positive constant or differs only on the sign of the expression (in the following, we call this: matching with a factor). And, last, there are rewriting rules that rely on concepts or that introduce concepts, like the concept of square in the following rewriting rule 'a²-b² → (a-b)(a+b)', in that case the matching must be carried out with respect to these concepts. See examples figure 10.

The stake of a rich matching is to be able to write fewer rewriting rules, more concise ones, or more general, and more natural, closer to human matching and human rewriting rules. Let's take one example, with the natural rule of factorisation expressed with 'a*b+a*c → a(b+c)'. With a rich matching, the rewriting rule 'a*b+a*c → a(b+c)' corresponds to the natural rule and is sufficient. With a 'poor' matching, the rewriting rule 'a*b+a*c → a(b+c)' is not sufficient, and one must add the following set of rewriting rule; if he wants the same behaviour a human would have with 'a*b+a*c → a(b+c)':

• To manage that the multiplication is commutative • The fact that the addition is commutative, associative and the existence of a neutral element for addition do not require the introduction of additional rules for this example.

The risks of a too rich matching are multiple. At the data-processing level, they are expressed in terms of algorithmic complexity. As regards to educational issues, if the matching is a process independent of the mechanism of application of the rewriting rules, it is necessary to store all the information that the mechanisms of application of the rewriting rules would have allowed with respect to the didactic variables, if not there is a loss. Generally, these two mechanisms (matching and application of rewriting rule) are, more or less, equivalent from the point of view of algebraic manipulation, but this equivalence is not prolonged in the role allotted to each one of these processes in the information processing system. The rewriting mechanisms occupy a central place in APLUSIX, but the (rich) matching is 'only' a facility of expression intended to allow a certain abstraction and to follow the human reasoning more closely, and the integration of didactic information is not the same as in the application of the rewriting rules.

Consequently, there is a balance to find between richness of the matching and the size of the set of rewriting rule which one wants to handle. The more the matching is rich and the more the set of the rewriting rules will be reduced. On the other hand, the richer matching is, and the less there are catches on the didactic use of manipulations that are done, unless the matching itself relies on rewriting rules.

The technical implementation of each characteristic of the mathematical matching described previously represents considerable technical difficulties and strongly depends on the internal representations used for the expressions. The implementation also strongly depends on whether one seeks a matching starting from the candidate or from the model (it seems more efficient to carry out a common search). In all the cases, it seems necessary, on the one hand to be able to limit by program the execution of a too rich matching, on the other hand to know the mechanisms performed to get at a given matching (search for concept, use of associative, introduction of neutral elements, etc.)

Certain temporary choices were made to set up a matching of this kind in APLUSIX, with all the power we can get of it. For the removal of neutral elements, it is performed by a set of immediate reduction rewriting rules; for the moment, the commutability is carried out by duplicated rewriting rules; the associative aspect and the search for under-expressions are taken into account in the hard core of the algorithm of matching; the search for concepts (as the concept of square) is carried out in back chaining. There is nothing done for the introduction of neutral additive elements (i.e.0); the introduction of multiplicative neutral elements (i.e.1) is taken into account by the search for matching with a factor.

As for the search of matching with a factor, it is by far the most delicate mechanism to establish. It is performed with a two-pass algorithm. The first pass decorates the internal tree of the expression with possible factors appearing in the sub-expressions. The second pass tries a matching with one factor chosen among the possible ones. To limit the algorithmic complexity, the search for matching with a factor is done only for positive factors. Matching an expression with negative factor is not taken into account for the moment, but a model for matching with a factor (positive or negative) on a different internal structure has been studied and seems to work on both positive and negative factors. In fact, the matching is the same in the new structure, but we have to change the structure we use to reach it. Perhaps it will be done in the future.

Ending's Words

APLUSIX project will obtain a final product soon. We wait impatiently to gather all the pieces to carry out the first tests in real world. In particular, it will permit to observe how our wishes to leave the most open our environment makes it possible to widen the use of it. It will permit also to tune precisely the classes of rewriting rules and the matching algorithm. And at last, it will permit to see if the new APLUSIX works as well as the old APLUSIX.

Figure 2 :

 2 Figure 2: Layout for the new APLUSIX

Figure 3 :

 3 Figure 3: Architecture of APLUSIX

Figure 4 :

 4 Figure 4: grammar for rewriting rules

  *c --->>> a(b+c); (a-b)(a+b) --->>> a^2-b^2; a+b --->>> c | Type a (1) | Type b (1) | Calculus c (a+b); (-a)^n --->>> -a^n | Type n (1) | Calculus 1 (Modulo n 2); (a)+b --->>> a+b | Type a (1+1); a*b+a*c --->>> a*d | Type b (1) | Type c (1) | Calculus d (b+c);

Figure 5 :

 5 Figure 5: Example of rewriting rules

Figure 6 :

 6 Figure 6: Application of rewriting rules

Figure 7 :

 7 Figure 7: Classes of rewriting rules

Figure 8 :

 8 Figure 8: two-dimensioned form of the rule '(a*b)^n → a^n*b^n'

Figure 9 :

 9 Figure 9: (a^b)^c Figure 9': a^(b^c)

Figure 10 :

 10 Figure 10: Examples of matching

  o b*a+a*c → a(b+c) o a*b+c*a → a(b+c) o b*a+c*a → a(b+c) • To manage the introduction of neutral elements for the multiplication o a+a*b → a(1+b) o a*b+a → a(b+1) • To manage that the multiplication is associative o a*b*c+a*b*d → a*b(c+d) o a*b*c*d+a*b*c*d*e → a*b*c(d+e)


come

Verification of non-linear overconstraints in Euclidean

geometry with linear programming


R Allen

Denis Bouhineau

Laurent Trilling

Laurent Trilling Construction

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