LSM 2003 - Thema Free Software and Research

directed by Michel Lavaud - CNRS et Univ. Orléans

1 Time-table and Abstracts of the Conferences
2 TeXmacs
Bibliographie
3 Yacas
Bibliographie
4 Giac/Xcas

Last update on 5 juillet 2003, at 17h 23, by Michel Lavaud

To download the document LSM 2003 - Thema Free Software and Research (427Kb), click here.

Chapitre 1 Time-table and Abstracts of the Conferences 

1.1 Location of the conferences 

Fig. 1.1 Location of the conferences of thema FS and Research: campus du Saulcy, building UFR SHA, amphithéâtre Daubrée)

1.2 Time-table of the conferences of the thema Free Software and Research 

1.3 Conferences of Wednesday 9 july 2003 

1.3.1 Time-table 

1.3.2 Introduction to thema FS and Research and to Rosetta CDs for computer algebra 

Michel Lavaud (CNRS & Orléans Univ., France).
The aim of the Rosetta CDs is to allow the comparaison of the existing various free programs of computer algebra, by launching them directly from the CD, without having to install them beforehand on the hard disk. There exists one version for Linux and one for Windows, downloadable from the net in compressed iso form. The Windows version is an application of the project Experimental Computer Science, which consists in studying the behavior of software (free or not) in an experimental manner, with reproducible conditions. This approach was developed in order to study scientifically the << diseases>> (instabilities) of Windows and Linux, try to understand their origins and propose remedies. It aims to extend to useful software the studies (taxonomic, prophylactic etc.) that were done up to now only for harmful software (viruses).

1.3.3 Axiom - The next 30 years 

Tim Daly (CUNY, New York, USA).
Axiom started in the late 60s as the Scratchpad project at IBM Research. Over the next 30 years it evolved into a commercial platform for symbolic algebra. Recently Axiom has become open source software. We briefly describe Axiom's development followed by an overview of the algebra. Next we cover it's current state, review its strengths and weaknesses, and suggest research and development priorities for the next 30 years.

1.3.4 GNU TeXmacs - A scientific editing platform 

Joris van der Hoeven (Univ. Orsay, France).
GNU TEX [vdH01,vdH02,Gro01] is a free software, which can both be used as a scientific text editor and as a front-end for computer algebra systems. The editor allows you to write structured documents via a wysiwyg (what-you-see-is-what-you-get) and user friendly interface. New styles may be created by the user. The program implements high-quality typesetting algorithms and TeX fonts, which allow the user to produce professionally looking documents.

The high typesetting quality still goes through for automatically generated formulas, which makes TEX suitable as an interface for computer algebra systems, or other types of "plugins". Currently, there are interfaces with Axiom, Giac, GNUplot, Graphviz, Gtybalt, Macaulay2, Maxima, Mupad, GNU Octave, Pari, Qcl, GNU R, Reduce, Scilab and Yacas. TEX also supports the Guile/Scheme extension language, so that you may customize the interface and write your own extensions to the editor.

In our demonstration, we plan to show briefly how to edit mathematical texts with TEX, how to use computer algebra systems, and how to add interfaces with new systems in a very efficient way.

1.3.5 The Maxima Project - Working towards a world-class free computer algebra system 

James Amundson (The Maxima Project, Chicago, USA).
Maxima is a free software project with an uncommonly long history. In its present state, Maxima is a rich and powerful program. I describe how the current project grew out of an MIT research program dating to the 1960's. I also describe the current project itself, including examples of the Maxima's current capabilities, the progress we have made and the challenges that face the project itself. Looking to the future, I discuss what it will take to turn Maxima into a "world-class" system. Finally, I propose ways in which various free software mathematical projects might cooperate in order to advance the field of free mathematical software as a whole.

1.3.6 The Roxane Project 

Bernard Mourrain (INRIA Sophia Antipolis, France).
The issues addressed by the Roxane Project are reusability, efficiency, integration and evolutions of algebraic software. The objectives are to mutualise the efforts of implementation that are done in different groups; to organize the developments in a coherent environment; to furnish tools to build dedicated and efficient components for solving real problems in Computer Algebra; to take into account the evolution of the components, the adjunction of new components; to serve as a publication support for software developments, with an evaluation process; to distribute the software publication (ftp, cdrom, ...).

1.3.7 Yacas - A Do-it-yourself Symbolic Algebra Environment 

Ayal Pinkus (Netherlands).
We describe the design and implementation of Yacas a free computer algebra system currently under development. The system consists of a core interpreter and a library of scripts that implement symbolic algebra functionality. The interpreter provides a high-level weakly typed functional language designed for quick prototyping of computer algebra algorithms, but the language is suitable for all kinds of symbolic manipulation. It supports conditional term rewriting of symbolic expression trees, closures (pure functions) and delayed evaluation, dynamic creation of transformation rules, arbitrary-precision numerical calculations, and flexible user-defined syntax using infix notation. The library of scripts currently provides basic numerical and symbolic algebra functionality, such as polynomials and elementary functions, limits, derivatives and (limited) integration, solution of (simple) equations. The main advantages of Y are: free (GPL) software; a flexible and easy-to-use programming language with a comfortable and adjustable syntax; cross-platform portability and small resource requirements; and extensibility.

1.4 Conferences of Thursday 10 july 2003 

1.4.1 Time-table 

1.4.2 Introduction D2 and free archives scientific articles and programs 

Michel Lavaud (CNRS & Univ. Orléans, France).
The method of archiving in a cvs repository, used nowadays to develop the various computer algebra systems, allows collaboration between developers of a given program but not between developers of different programs. We propose, in collaboration with the CCSD of CNRS, to extend the principle of arXiv (free archive of scientific articles) to archiving of self-documented programs (written according to the principles of literate programming of Knuth), in the domain of computer algebra. The goal is to ease collaboration between developers and users of different programs, by providing them constantly an exhaustive and up-to-date report of procedures implemented in each language, and by allowing to use programs that can translate procedures from one language to another (for ex. Formconv by Z. Kovacs et al.). Furthermore, any user of any language could deposit his procedure in the archive with the same ease as for an ordinary article in arXiv, thus avoiding the cumbersome cvs procedures,that limit in practice contributions to a small number of users.

1.4.3 Literate programming - Developing maintainable software 

Tim Daly (CUNY, New York, USA).
Traditional commercial programming involved small groups of people who were trained on the code they maintain. Open source software involves groups of people spread over time and space who may never meet the original developers. In the long term software development requires better methods of documenting the software at the design, development, and detailed coding levels. Literate Programming offers the technology to support these goals.

1.4.4 Scilab Consortium and future of Scilab, a free scientific software 

Claude Gomez (INRIA Rocquencourt, France) (slides of the talk).
Scilab is a free interactive software package dedicated to numerical computation. Developed by INRIA and ENPC, it provides a powerful open computing environment for engineering and scientific applications. It is currently being used in industrial and academic laboratories around the world. A Consortium by the same name is now taking charge of it. Its purpose is to turn Scilab into worldwide reference software in academia and industry that relies on a large community of contributors. Contributors are welcome and we describe the various ways to contribute to Scilab.

1.4.5 Mpfr - A new concept for floating-point computations 

Paul Zimmermann (INRIA Lorraine, France).
MPFR is an arbitrary precision floating-point library, distributed under LGPL. Based on the famous GNU MP library, which brings both portability and efficiency, MPFR differs from other floating-point software by the fact it implements "correct rounding", following the philosophy of the IEEE 754 standard. Thus, the result of each operation is uniquely defined, which enables one to write programs whose behaviour is perfectly identical, independently from the machine word-size (32 or 64 bits). The talk will present the main concepts underlying the MPFR library, will give some examples of use of the library, and will discuss its future.

1.4.6 Giac/Xcas - A free and compatible computer algebra system 

Bernard Parisse (Univ. Grenoble, France).
Giac is a C++ library for computer algebra system distributed under the GPL license, Xcas groups in the same graphical user interface the CAS functionnalities of giac, a small spreadsheet and interactive geometry. Both are under active development, the implemented math functionnalities can today be used at undergraduate level. Programmation can be done using the interpreted language available in several flavours compatible with popular CAS (Maple, Mupad, TI89), or directly in C++ (either as a standalone program using the giac library or as dynamically linked libraries to be loaded at runtime in an xcas session).

1.4.7 Active-DVI - A DVI-previewer and a programmable presenter for slides written in LaTeX 

Pierre Weis (INRIA Rocquencourt, France).
To preview DVI files, Active-DVI features color anti-aliasing; inclusion of images (via the Camlimages package) with alpha channel and blending; encapsulated Postscript File inclusion (using graphics macros package); Gpic specials to display pictures; correct treatment of many (but not all) inlined-Postscript specials; page background settings; Japanese pTeX DVI extension support.

To present your DVI files, Active-DVI features basic effects for presentation (pause, delay, dynamic text color change); annotations displayed on demand (similar to pop-up balloons); hyper links from slide to slide or to other files (including DVI files); replay of previously recorded parts of the display; text movements; page transitions; embedded applications (launched and killed on demand from within the presentation text source), with precise security policy; scratching on slide to interactively modify the text on screen; Active-DVI special effects are set and launched from within your LaTeX source file via the macros of the advi.sty LaTeX package provided by the distribution.

1.4.8 Formats and tools for ensuring permanence of scientific archives 

Michel Lavaud (CNRS & Univ. Orléans, France).
Many scientific articles are now distributed in pdf format, by means of programs Pdftex, Pdflatex, Open Office, Word etc. Unfortunately, the pdf format being proprietary, nothing ensures its permanence. We will explain why the dvi format guarantees, o the contrary the permanence of scientific documents, and how it is possible to use this format without losing anything brought by the pdf format. The solution proposed goes through the adoption of a multi-platform dvi viewer (Active-DVI ?) as standard display program and through integration of functionalities of other existing dvi viewers that it might miss. This viewer ought in addition to be able to create and reread tar.gz or zip archives contaning the dvi file and all the resources (fonts, images etc.) necessary to display the dvi and perform some other tasks.

1.4.9 Mathemagix - Towards a modern free computer algebra system 

Joris van der Hoeven (Orsay Univ., France).
The Mathemagix project aims at developing a modern free computer algebra system. Mathemagix consists of a strongly typed language and a mechanism to easily incorporate existing free libraries like Gmp, Synaps, Linbox, etc. We also aim to provide a user friendly working environment using GNU TeXmacs. At the moment, the project is still in an early stage, but we are already able to show a glimpse of the system.

1.4.10 Demonstrations of software 

Demonstrations of the programs presented during the conferences (Maxima, Rosetta etc.) will be done in small groups, around laptops.

1.5 Conferences of Friday 11 july 2003 

1.5.1 Time-table 

1.5.2 Le projet Alchem.org - Anthology of Liberty for Chemistry 

Jérôme Pansanel (Univ. Strasbourg, France).
L'un des buts du projet Alchem.org est la publication d'informations sur les logiciels libres en chimie. La publication est importante dans la reconnaissance scientifique, et donc la survie (souvenez-vous du vieil adage : publish or perish). Il en est de même pour le logiciel libre.

1.5.3 LSD - Automatic structural analysis of organic molecules 

Jean-Marc Nuzillard (Univ. Reims, France).
The talk will first provide an overview of the analytical methods that are specific to the structural analysis of organic molecules. It will then focus on the impact of nuclear magnetic resonance (NMR) on the analytical process. A real-life example that uses the LSD (Logic for Structure Determination) software for automated 1D and 2D NMR data analysis will be then presented. The talk will end up with some information about the used algorithm and with perspectives on future developments.

1.5.4 Polyxmass - A free scientific software program for polymer mass spectrometry 

Filippo Rusconi (Museum Nat. Hist. Nat., Paris, France).
Mass spectrometry data acquisition on polymers is most often preceded by mass data simulation and followed by mass data analysis. The polyxmass mass spectrometry software suite provides an integrated free software framework to perform these tasks easily for any polymer type. Indeed, polyxmass provides a module to define brand new polymer chemistries. Once a polymer chemistry is defined, any polymer sequence complying with its specifications can be handled by the two other modules: polyxcalc is a mass calculator and polyxedit is the module where any chemical reaction is simulated with real time molecular mass recalculation.

1.5.5 Round-table - - Proposals to encourage the creation of free software by researchers 

A round-table is organized to inventory the problems that prevent or restrain the realization of free software by researchers, and to propose solutions to these problems.  

Chapitre 2 TeXmacs 

Résumé GNU TEX [vdH01,vdH02,Gro01] is a free software, which can both be used as a scientific text editor and as a front-end for computer algebra systems. The editor allows you to write structured documents via a wysiwyg (what-you-see-is-what-you-get) and user friendly interface. New styles may be created by the user. The program implements high-quality typesetting algorithms and TeX fonts, which allow the user to produce professionally looking documents. The high typesetting quality still goes through for automatically generated formulas, which makes TEX suitable as an interface for computer algebra systems, or other types of "plugins". Currently, there are interfaces with Axiom, Giac, GNUplot, Graphviz, Gtybalt, Macaulay2, Maxima, Mupad, GNU Octave, Pari, Qcl, GNU R, Reduce, Scilab and Yacas. TEX also supports the Guile/Scheme extension language, so that you may customize the interface and write your own extensions to the editor. In our demonstration, we plan to show briefly how to edit mathematical texts with TEX, how to use computer algebra systems, and how to add interfaces with new systems in a very efficient way.

2.1 Description 

1.  The need for a general purpose and user friendly scientific text editor.
2.  The need for high quality front-ends for computer algebra systems.
3.  The need for free (in the sense of freedom) scientific software.

From the editing point of view, TEX has the advantage of being wysiwyg (what-you-see-is-what-you-get). This does not withstand the facts that TEX is also a structured editor [vdH01] and that its typesetting quality is comparable to TeX. In fact, the user may control the degree of desired wysiwygness and the user may "feel" the structure of a document in other ways than through the explicit display of "source code". From the typesetting point of view, many algorithms were taken from TeX (hyphenation, line-breaking, spacing, etc.), as well as the fonts. At certain points, improvements were made, especially with regard to typesetting automatically generated formulas.

GNU TEX can currently be used as an interface for many computer algebra systems and other scientific software: Axiom, Giac, GNUplot, Graphviz, Gtybalt, Macaulay2, Maxima, Mupad, GNU Octave, Pari, Qcl, GNU R, Reduce, Scilab and Yacas. Communication takes place using pipes or dynamic libraries and existing pretty printers for LaTeX can be reused in order to build an interface with a new system in a few hours. At a second stage, a working interface can be extended to allow for two-dimensional mathematical input, tab-completion, contextual menus, customized keyboard modes, and much more.

Being part of the GNU project, one of the main aims of TEX is to encourage the development of free computer algebra systems, by removing the burden of writing good user interfaces from the programmers. We believe that free programs in the sense of

http://www.gnu.org/philosophy/free-sw.html

are particularly important in science: which mathematician would accept a proof of a theorem contained in a black box, for which you do not have the legal right to open it? What is the scientific interest of a theorem which cannot be used in proofs of other theorems?

The TEX program is currently well suited for writing scientific articles and as an interface to the computer algebra systems mentioned above. Currently, we are working on better conversions with TeX/LaTeX and input/output filters for HTML/MathML. In the future, we plan to include a "universal spreadsheet", a technical drawing editor, and more structured editing facilities. This will provide end-users with an office suite for structured documents with a high degree of interaction with scientific applications. It also provides developers with a scientific editing platform.

Bibliographie 

[Gro01]	Andrey Grozin. TEX interfaces to Maxima, Mupad and Reduce. Tech. rep., Arxiv, 2001. http://arxiv.org/abs/cs.SC/0107036.
[vdH01]	Joris van der Hoeven. GNU TEX: A free, structured, wysiwyg and technical text editor. In Daniel Flipo, editor, Le document au XXI-ième siècle, volume 39-40, pages 39-50, Metz, 14-17 mai 2001. Actes du congrès GUTenberg.
[vdH02]	Joris van der Hoeven. GNU TEX. http://www.texmacs.org, 1998-2002.

Chapitre 3 Yacas 

Ayal Zwi Pinkus 3e Oosterparkstraat 109-III, Amsterdam, The Netherlands apinkus@xs4all.nl Serge Winitzki Tufts Institute of Cosmology, Department of Physics and Astronomy, Tufts University, Medford, MA 02155, USA serge@cosmos.phy.tufts.edu

Résumé We describe the design and implementation of Y, a free computer algebra system currently under development. The system consists of a core interpreter and a library of scripts that implement symbolic algebra functionality. The interpreter provides a high-level weakly typed functional language designed for quick prototyping of computer algebra algorithms, but the language is suitable for all kinds of symbolic manipulation. It supports conditional term rewriting of symbolic expression trees, closures (pure functions) and delayed evaluation, dynamic creation of transformation rules, arbitrary-precision numerical calculations, and flexible user-defined syntax using infix notation. The library of scripts currently provides basic numerical and symbolic algebra functionality, such as polynomials and elementary functions, limits, derivatives and (limited) integration, solution of (simple) equations. The main advantages of Y are: free (GPL) software; a flexible and easy-to-use programming language with a comfortable and adjustable syntax; cross-platform portability and small resource requirements; and extensibility.

3.1 Introduction 

Y is primarily intended to be a research tool for easy exploration and prototyping of algorithms of symbolic computation. The main advantage of Y is its rich and flexible scripting language. The language is closely related to LISP WH89 but has a recursive descent infix grammar parser ASU86 which supports defining infix operators at run time similarly to Prolog B86, and includes expression transformation (term rewriting) as a basic feature of the language.

The Y language interpreter comes with a library of scripts that implement a set of computer algebra features. The Y script library is in active development and at the present stage does not offer the rich functionality of industrial-strength systems such as Mathematica or Maple. Extensive implementation of algorithms of symbolic computation is one of the future development goals.

Y handles input and output in plain ASCII, either interactively or in batch mode. (A graphical interface is under development.) There is also an optional plugin mechanism whereby external libraries can be linked into the system to provide extra functionality. Basic facilities are in place to compile Yacas scripts to C++ so they can be compiled into plugins.

3.2 Basic design 

The Y engine has been implemented in a subset of C++ which is supported by almost all C++ compilers. The design goals for Y core engine are: portability, self-containment (no dependence on extra libraries or packages), ease of implementing algorithms, code transparency, and flexibility. The Y system as a whole falls into the "prototype/hacker" rather than into the "axiom/algebraic" category, according to the terminology of Fateman F90. There are relatively few specific design decisions related to mathematics, but instead the emphasis is made on extensibility.

The kernel offers sufficiently rich but basic functionality through a limited number of core functions. This core functionality includes substitutions and rewriting of symbolic expression trees, an infix syntax parser, and arbitrary precision numerics. The kernel does not contain any definitions of symbolic mathematical operations and tries to be as general and free as possible of predefined notions or policies in the domain of symbolic computation.

The plugin inter-operability mechanism allows extension of the Y kernel and the use of external libraries, e.g. GUI toolkits or implementations of special-purpose algorithms. A simple C++ API is provided for writing "stubs" that make external functions appear in Y as new core functions. Plugins are on the same footing as the Y kernel and can in principle manipulate all Y internal structures. Plugins can be compiled either statically or dynamically as shared libraries to be loaded at runtime from Y scripts. In addition, Y scripts can be compiled to C++ code for further compilation into a plugin. Systems that don't support plugins can then link these modules in statically. The system can also be run without the plugins, for debugging and development purposes. The scripts will be interpreted in that case.

The script library contains declarations of transformation rules and of function syntax (prefix, infix etc.). The intention is that all symbolic manipulation algorithms, definitions of mathematical functions etc. should be held in the script library and not in the kernel. The only exception so far is for a very small number of mathematical or utility functions that are frequently used; they are compiled into the core for speed.

3.2.1 Portability 

Y is designed to be as platform-independent as possible. All platform-specific parts have been clearly separated to facilitate porting. Even the standard C++ library is considered to be platform-specific, as there exist platforms without support for the standard C++ library (e.g. the EPOC32 platform).

The primary development platform is GNU/Linux. Currently Y runs under various Unix variants, Windows environments, Psion organizers (EPOC32), Ipaq PDAs, BeOS, and Apple iMacs. Creating an executable for another platform (including embedded platforms) should not be difficult.

3.2.2 A self-contained system 

Y should work as a standalone package, requiring minimum support from other operating system components. Y takes input and output in plain ASCII, either interactively or in batch mode. (An optional graphical interface is under development.) The system comes with its own (unoptimized) arbitrary precision arithmetic module but could be compiled to use another arbitrary precision arithmetic library; currently linking to gmp is experimentally supported. There is also an optional plugin mechanism whereby external libraries can be linked into the system to provide extra functionality.

Self-containment is a requirement if the program is to be easy to port. A dependency on libraries that might not be available on other platforms would reduce portability. On the other hand, Y can be compiled with a complement of external libraries on "production" platforms.

3.2.3 Ease of use 

Y is used mainly by executing programs written in the Y script language. A design goal is to create a high-level language that allows the user to conveniently express symbolic algorithms. A few lines of user code should go a long way.

One major advantage of Y is the flexibility of its syntax. Although Y works internally as a LISP-style interpreter, all user interaction is through the Y script language which has a flexible infix grammar. Infix operators are defined by the user and may contain non-alphabetic characters such as "=" or "#". This means that the user interacts with Y using a comfortable and adjustable infix syntax, rather than a LISP-style syntax. The user can introduce such syntactic conventions as are most convenient for a given problem.

For example, the Y script library defines infix operators "+", "*" and so on with conventional precedence, so that an algebraic expression can be entered in the familiar infix form such as

 (x+1)^2 - (y-2*z)/(y+3) + Sin(x*Pi/2)

Suppose the user needs to reorder expressions containing non-commutative creation and annihilation operators of quantum field theory. It takes about 20 lines of Y script code to define an infix operation "**" to express non-commutative multiplication with the appropriate commutation relations and to automatically normal-order all expressions involving these symbols and other (commutative) factors. Once the operator ** is defined (with precedence 40),

 Infix("**", 40);

 15 # (_x + _y) ** _z <-- x ** z + y ** z;
 15 # _z ** (_x + _y) <-- z ** x + z ** y;

Rule-based programming is not the only method that can be used in Y scripts; there are alternatives that may be more useful in some situations. For example, the familiar if / else constructs, For, ForEach loops are defined in the script library for the convenience of users.

Standard patterns of procedural programming, such as subroutines that return values, with code blocks and temporary local variables, are also available. (A "subroutine" is implemented as a new "ground term" with a single rule defined for it.) Users may freely combine rules with C-like procedures or LISP-like list processing primitives such as Head(), Tail().

3.2.4 Code clarity vs. speed 

Speed is obviously an important factor. For Y, where a choice had to be made between speed and clarity of code, clarity was chosen. Y is mainly a prototyping system and its future maintainability is more important.

This means that special-purpose systems designed for specific types of calculations, as well as heavily optimized industrial-strength computer algebra systems, will outperform Y. However, special-purpose or optimized external libraries can be dynamically linked into Y using the plugin mechanism.

3.2.5 Flexible, policy-free engine 

The core engine of the Y system interprets the Yacas script language. The reason to implement yet another LISP-based custom language interpreter instead of taking an already existing one was to have full control over the design of the system and to make it self-contained. While most of the features of the Y script language are "syntactic sugar" on top of a LISP interpreter, some features not commonly found in LISP systems were added.

The script library contains declarations of transformation rules and of function syntax (prefix, infix etc.). The intention is that all symbolic manipulation algorithms, definitions of mathematical functions and so on should be held in the script library and not in the kernel. The only exception so far is for a very small number of mathematical or utility functions that are frequently used; they are compiled into the core for speed.

For example, the mathematical operator "+" is an infix operator defined in the library scripts. To the kernel, this operator is on the same footing as any other function defined by the user and can be redefined. The Y kernel itself does not store any properties for this operator. Instead it relies entirely on the script library to provide transformation rules for manipulating expressions involving the operator "+". In this way, the kernel does not need to anticipate all possible meanings of the operator "+" that users might need in their calculations.

This policy-free scheme means that Y is highly configurable through its scripting language. It is possible to create an entirely different symbolic manipulation engine based on the same C++ kernel, with different syntax and different naming conventions, by simply using another script library instead of the current library scripts. An example of the flexibility of the Y system is a sample script wordproblems.ys that comes with the distribution. It contains a set of rule definitions that make Y recognize simple English sentences, such as "Tom has 3 apples" or "Jane gave an apple to Tom", as valid Y expressions. Y can then "evaluate" these sentences to True or False according to the semantics of the current situation described in them.

The "policy-free" concept extends to typing: strong typing is not required by the kernel, but can be easily enforced by the scripts if needed for a particular problem. The language offers features, but does not enforce their use. Here is an example of a policy implemented in the script library:

 61 # x_IsPositiveNumber ^ y_IsPositiveNumber
       <-- MathPower(x,y);

3.3 The Yacas kernel functionality 

The kernel provides three basic data types: numbers, strings, and atoms, and two container types: list and static array (for speed). Atoms are implemented as strings that can be assigned values and evaluated. Boolean values are simply atoms True and False. Numbers are represented by objects on which arithmetic can be performed immediately. Expression trees, association (hash) tables, stacks, and closures (pure functions) are all implemented using nested lists. In addition, more data types can be provided by plugins. Kernel primitives are available for arbitrary-precision arithmetic, string manipulation, array and list access and manipulation, for basic control flow, for assigning variables (atoms) and for defining rules for functions (atoms with a function syntax).

The interpreter engine recursively evaluates expression trees according to user-defined transformation rules from the script library. Evaluation proceeds bottom-up, that is, for each function term, the arguments are evaluated first and then the function is applied to these values.

A HoldArg() primitive is provided to not evaluate certain arguments of certain functions before passing them on as parameters to these functions. The Hold() and Eval() primitives, similarly to LISP's QUOTE and EVAL, can be used to stop the recursive application of rules at a certain point and obtain an unevaluated expression, or to initiate evaluation of an expression which was previously held unevaluated.

When an expression can not be transformed any further, that is, when no more rules apply to it, the expression is returned unevaluated. For instance, a variable that is not assigned a value will return unevaluated. This is a desired behavior in a symbolic manipulation system. Evaluation is treated as a form of "simplification", in that evaluating an expression returns a simplified form of the input expression.

Rules are matched by a pattern expression which can contain pattern variables, i.e. atoms marked by the "_" operator. During matching, each pattern variable atom becomes a local variable and is tentatively assigned the subexpression being matched. For example, the pattern _x + _y can match an expression a*x+b and then the pattern variable x will be assigned the value a*x (unevaluated) and the variable y will have the value b.

This type of semantic matching has been frequently implemented before in various term rewriting systems (see, e.g., [C86]). However, the Y language offers its users an ability to create a much more flexible and powerful term rewriting system than one based on a fixed set of rules. Here are some of the features:

First, transformation rules in Y have predicates that control whether a rule should be applied to an expression. Predicates can be any Y expressions that evaluate to the atoms True or False and are typically functions of pattern variables. A predicate could check the types or values of certain subexpressions of the matching context (see the _x ^_y example in the previous subsection).

Second, rules are assigned a precedence value (a positive integer) that controls the order of rules to be attempted. Thus Y provides somewhat better control over the automatic recursion than the pattern-matching system of Mathematica which does not allow for rule precedence. The interpreter will first apply the rule that matches the argument pattern, for which the predicate returns True, and which has the least precedence.

Third, new rules can be defined dynamically as a side-effect of evaluation. This means that there is no predefined "ranking alphabet" of "ground terms" (in the terminology of [TATA99]), in other words, no fixed set of functions with predefined arities. It is also possible to define a "rule closure" that defines rules depending on its arguments, or to erase rules. Thus, a Y script library (although it is read-only) does not represent a fixed tree rewriting automaton. An implementation of machine learning is possible in Y (among other things). For example, when the module wordproblems.ys (mentioned in the previous subsection) "learns" from the user input that apple is a countable object, it defines a new postfix operator apples and a rule for its evaluation, so the expression 3 apples is later parsed as a function apples(3) and evaluated according to the rule.

Fourth, Y expressions can be "tagged" (assigned a "property object" a la LISP) and tags can be checked by predicates in rules or used in the evaluation.

Fifth, the scope of variables can be controlled. In addition to having its own local variables, a function can be allowed to access local variables of its calling environment (the UnFence() primitive). It is also possible to encapsulate a group of variables and functions into a "module", making some of them inaccessible from the outside (the LocalSymbols() primitive). The scoping of variables is a "policy decision", to be enforced by the script which defines the function. This flexibility is by design and allows to easily modify the behavior of the interpreter, effectively changing the language as needed.

3.4 The Yacas scripting language 

Y supports "function overloading": it allows a user to declare functions f(x) and f(x,y), each having their own set of transformation rules. Of course, different rules can be defined for the same function name with the same number of arguments (arity) but with different argument patterns or different predicates.

Simple transformations on expressions can be performed using rules. For instance, if we need to expand the natural logarithm in an expression, we could use the following rules:

 log(_x * _y) <-- log(x) + log(y);
 log(_x ^ _n) <-- n * log(x);

After entering these two rules, the following interactive session is possible:

 In> log(a*x^2)
 
 log( a ) + 2 * log( x )

 AntiDeriv(_x,log(_x)) <-- x*log(x)-x;

 In> Integrate(x)log(a*x^n)
 
 log( a ) * x + n * ( x * log( x ) - x ) + C18
 
 In> Integrate(x,B,C)log(a*x^n)
 
 log( a ) * C + n * ( C * log( C ) - C ) -
 
 ( log( a ) * B + n * ( B * log( B ) - B ) )

 10 # Factorial(_n) _ (n=0) <-- 1;
 20 # Factorial(n_IsInteger) _ (n>0) <--
   n*Factorial(n-1);

Rule-based programming can be freely combined with procedural programming when the latter is a more appropriate method. For example, here is a function that computes (xⁿ mod m) efficiently:

 powermod(x_IsPositiveInteger,
    n_IsPositiveInteger,
    m_IsPositiveInteger) <--
                                                                  
                                                                  
 [
   Local(result);
   result:=1;
   x:=Mod(x,m);
   While(n != 0)
   [
     if ((n&1) = 1)
 [
       result := Mod(result*x,m);
     ];
     x := Mod(x*x,m);
     n := n>>1;
   ];
   result;
 ];

 In> powermod(2,10,100)
 Out> 24;
 In> Mod(2^10,100)
 Out> 24;
 In> powermod(23234234,2342424234,232423424)
 Out> 210599936;

3.5 Currently supported CAS features 

A base of mathematical capabilities has already been implemented in the script library (the primary sources of inspiration were the books [K98], [GG99] and [B86]). The script library is currently under active development. The following section demonstrates a few facilities already offered in the current system.

Basic operations of elementary calculus have been implemented:

 In> Limit(n,Infinity)(1+(1/n))^n
 
 Exp( 1 )
 
 In> Limit(h,0) (Sin(x+h)-Sin(x))/h
 
 Cos( x )
 
 In> Taylor(x,0,5)ArcSin(x)
 
      3        5
     x    3 * x
 x + -- + ------
     6      40
 
 In> InverseTaylor(x,0,5)Sin(x)
 
      5    3
 3 * x    x
 ------ + -- + x
   40     6
 
 In> Integrate(x,a,b)Ln(x)+x
 
                    2   /                    2 \
                   b    |                   a  |
 b * Ln( b ) - b + -- - | a * Ln( a ) - a + -- |
                   2    \                   2  /
 
 In> Integrate(x)1/(x^2-1)
 
 Ln( 2 * ( x - 1 ) )   Ln( 2 * ( x + 1 ) )
 ------------------- - ------------------- + C38
          2                     2
 
 In> Integrate(x)Sin(a*x)^2*Cos(b*x)
 
 Sin( b * x )   Sin( -2 * x * a + b * x )
                                                                  
                                                                  
 ------------ - ------------------------- -
    2 * b          4 * ( -2 * a + b )
 
 Sin( -2 * x * a - b * x )
 ------------------------- + C39
    4 * ( -2 * a - b )
 
 In> OdeSolve(y''==4*y)
 
 C193 * Exp( -2 * x ) + C195 * Exp( 2 * x )

 In> Solve( {x+y+z==6, 2*x+y+2*z==10, \
 In> x+3*y+z==10}, \
 In>      {x,y,z} ) [1]
 Out> {4-z,2,z};

A small theorem prover [B86] using a resolution principle is offered:

 In> CanProve(P Or (Not P And Not Q))
 
 Not( Q ) Or P

 In> CanProve(a > 3 And a < 2)
 
 False

 In> N(1/7,40);    // evaluate to 40 digits
 Out> 0.1428571428571428571428571428571428571428;
 In> Decimal(1/7);    // obtain decimal period
 Out> {0,{1,4,2,8,5,7}};
 In> N(LnGamma(1.234+2.345*I)); // gamma-function
 Out> Complex(-2.13255691127918,0.70978922847121);

 In> RadSimp(Sqrt(9+4*Sqrt(2)))
 
 Sqrt( 8 ) + 1
 
 In> TrigSimpCombine(Sin(x)^2+Cos(x)^2)
                                                                  
                                                                  
 
 1
 
 In> TrigSimpCombine(Cos(x/2)^2-Sin(x/2)^2)
 
 Cos( x )
 
 In> GcdReduce((x^2+2*x+1)/(x^2-1),x)
 
 x + 1
 -----
 x - 1

 In> Factor(x^6+9*x^5+21*x^4-5*x^3-54*x^2-12*x+40)
 
          3            2
 ( x + 2 )  * ( x - 1 )  * ( x + 5 )
 
 In> Apart(1/(x^2-x-2))
 
       1               1
 ------------- - -------------
 3 * ( x - 2 )   3 * ( x + 1 )
 
 In> Together(%)
 
          9
 -------------------
      2
 9 * x  - 9 * x - 18
 
 In> Simplify(%)
 
      1
 ----------
  2
                                                                  
                                                                  
 x  - x - 2
 

 In> Ln(x*y) /: { Ln(_a*_b) <- Ln(a) + Ln(b) }
 
 Ln( x ) + Ln( y )
 
 In> Add(x^(1 .. 5))
 
      2    3    4    5
 x + x  + x  + x  + x
 
 In> Select("IsPrime", 1 .. 15)
 Out> {2,3,5,7,11,13};
 

 In> Groebner({x*(y-1),y*(x-1)})
 
 /           \
 | x * y - x |
 |           |
 | x * y - y |
 |           |
 | y - x     |
 |           |
                                                                  
                                                                  
 |  2        |
 | y  - y    |
 \           /

Symbolic inverses of matrices:

 In> Inverse({{a,b},{c,d}})
 
 /                                      \
 | /       d       \ /    -( b )     \  |
 | | ------------- | | ------------- |  |
 | \ a * d - b * c / \ a * d - b * c /  |
 |                                      |
 | /    -( c )     \ /       a       \  |
 | | ------------- | | ------------- |  |
 | \ a * d - b * c / \ a * d - b * c /  |
 \                                      /

3.6 Interface 

Debugging facilities are implemented, allowing to trace execution of a function, trace application of a given rule pattern, examine the stack when recursion did not terminate, or an online debugger from the command line. An experimental debug version of the Y executable that provides more detailed information can be compiled.

3.7 Documentation 

Y currently comes with its own document formatting module that allows maintenance of documentation in a special plain text format with a minimal markup. This text format is automatically converted to HTML, LaTeX, PostScript and PDF formats. The HTML version of the documentation is hyperlinked and is used as online help available from the Y prompt.

3.8 Future plans 

The plugin facility will be extended in the future, so that a rich set of extra additional libraries (especially free software libraries), system-specific as well as mathematics-oriented, should be loadable from the Y system. The issue of speed is also continuously being addressed.

Bibliographie 

Chapitre 4 Giac/Xcas 

www-fourier.ujf-grenoble.fr/parisse/giac.html

Giac/xcas, logiciel de calcul formel libre compatible

4.1 Contributors 

• BP (most of the code, some documentation),
• Renée de Graeve (some code and most of the French documentation),
• J. Manrique Lopez de la Fuente (Spanish localization),
• J.P. Branchard (mathml code and giac on-line),
• R. Kreckel (GNUification)
• lexer/parser derived originally from GiNaC, 2-d ps output from Eukleides
• several testers (C. Serret, ...)

4.2 Motivations, design choices 

• Motivation: a free CAS for education (background: I'm the main author of the HP49/40G calculator CAS) that can also be used in research (for all kind of researchers).
• Compatibility is essential for the users wrt to their favorite CAS hence I'm working on Maple and TI89 compatibility.
• Should be usable as a DLL library, third-party apps should not have to discuss with a CAS by feeding text to a readline interface. Choice of C++, a popular language with arithmetic facilities (operator overload), so that giac can be used by several C++ programmers outside the CAS community, while other can use their favorite syntax in xcas/giac readline.
• 2000: start of the project, 2002: first GUI, 2003/06: 82500 lines of code (GUI 14000 lines) in additions to several libraries (GMP/MPFR, GSL, PARI-GP, NTL, FLTK, FLVW, FL_Editor, readline, intl, ...).
• Available on Linux (rpm/deb), Windows (autoextract archive), Mac OS X (experimental). Around 100 downloads per month, slowly increasing.
• BTW I didn't know that maxima was GPL in 2000, but it does not fulfill some of my requirements anyway.

4.3 Mathematical functionnalities overview. 

4.3.1 Algebra 

1.  Multi-precision arithmetic (integers, floats) over GMP/MPFR, polynomial library (dense 1-dim, sparse distributed n-dim)
2.  Integer arithmetic (primality, gcd, B´ezout, chinese remainder, etc., link with PARI-GP for factorization)
3.  Polynomial arithmetic (gcd, B´ezout, resultant, ..., factorization over or over an extension, link to NTL for 1-d polynomial factorization, orthogonal polynomials, Lagrange interpolation...)
4.  Linear algebra and matrix arithmetic, row reduction/inverse/ determinant, eigenvalues/eigenvectors computation, numeric matrix factorization (using the GSL)
5.  Bilinear forms
6.  (currently inefficient) Groebner basis

4.3.2 Calculus 

1.  , (Risch algorithm for pure transcendental extension in test stage)
2.  Ordinary differential equations (1st order or with constant coefficients using Laplace transform)
3.  Limits, series expansion (Taylor, asymptotic, using the mrv algorithm)
4.  Polynomial-like exact solver, numerical rootfinder
5.  Several rewriting rules

4.3.3 Other 

1.  Probability and statistics (including usual distributions and reverse functions)
2.  Permutations
3.  Special functions
4.  (xcas) 2-d plotter, 3-d interface to gnuplot

4.3.4 Some examples 

• ifactor(2^128+1) (using PARI)
• factor(x^100+x^50+1)
• inv(hilbert(30))
• [P,J]:=jordan([[-2,-2,1],[-2,1,-2],[1,-2,-2]]) (using on-line help) check with P*J*inv(P)
• int(x*sin(x)^2*exp(x),x), derive, rewrite as the original expression
• int((2*x^2+1)*exp(x^2),x) (Risch algorithm)
• int(1/(x^4+1),x,0,+infinity) (bounds) + call to simplify
• desolve() (on-line help example)
• series(sin(x)/(exp(x)-1),x=0,6)
• The check subdirectory of giac contains several other examples.

4.4 Xcas user interface 

• Several "screens": history, 2-d graphics (including gemoetry) spreadsheet/matrixwriter, on-line help (English, French or Spanish);, program editor, debugger. The window can be split to show 2 or 3 screens simultaneously.
• Menus (computer-like and calculator-like), you don't need to learn command names (also available in texmacs giac interface).
• Virtual keyboard (makes xcas usable on a PDA)
• Full help inside your favorite browser (currently only French available)
• Import/export filters (examples: Maple worksheet, TI89 group archive)

Examples of interactions between 2 modules :

• Geometry and CAS (Napoleon's theorem)
• Spreadsheet and CAS tableseq(cos(x),x,0.0)

4.5 Examples of programs 

4.5.1 User language 

Find the matrix of a quadratic form, return 0 if expression is not a quadratic form. Maple syntax :

quad:=proc(q,x)    local fonc,fonc2,fonc3,mat,_i,j,k;    n:=nops(x);    mat:=matrix(n,n,0);    fonc:=q;    for _i from 1 to n do     fonc:=subs((x[_i])=0,fonc)    od;;    if fonc<>0 then RETURN(0) fi;;    for _i from 1 to n do      fonc:=q;      fonc:=diff(fonc,x[_i]);      for j from 1 to n do        fonc:=subs((x[j])=0,fonc)      od;;      if fonc<>0 then RETURN(0) fi;    od;;    for _i from 1 to n do      fonc:=diff(q,x[_i]);      for j from 1 to n do        fonc1:=diff(fonc,x[j]);        for k from 1 to n do          fonc2:=diff(fonc1,x[k]);          if fonc2<>0 then RETURN(0) fi;        od;      od;    od;;    for _i from 1 to n do      for j from 1 to _i do        fonc:=diff(q,x[_i]);        fonc:=diff(fonc,x[j]);        mat[_i,j]:=fonc/2;        mat[j,_i]:=fonc/2     od;    od;;    RETURN(mat);  end;

Test with q=x^2+2*y^2+2*x*y and q+1 and q*x. Show the translation in mupad, TI89, xcas syntax.

4.5.2 Standalone program using the library 

// -*- compile-command: "g++ -g essai.cc -lgiac -lgmp" -*-  #include<giac/giac.h>  using namespace std;  using namespace giac;    int main(){    gen g;    cout << "Enter an expression: ";    cin >> g;    g=eval(g);    cout << "Factorization of " << g << " is " << factor(g) << endl;  }

Once compiled (see commandline above), run it with ./a.out.

Debugging is easy with gdb and the following macro to print giac objects (in .gdbinit) :

echo Defining v as print command for giac types\n  define v  print ($arg0).dbgprint()  end  ; $ suppress this line (emacs latex colorization bug)

The main C++ type of giac is the gen class for generic object storage. It consists mainly of a short int, the type of the object, another short int the "subtype" (e.g. lists, sets or sequences have the same type but different subtypes), and an anonymous union that is either the object itself if fixed-size (16 bits integers or double) or a pointer to a referenced-counted object. More info on types are in the headers dispatch.h and gen.h. Typically a code slice could be :

if (g.type==_VECT){    vecteur & v = *g._VECTptr;    int s=v.size();    for (int i=0;i<s;++i)      cout << i << ":" << factor(v[i]) << endl;  }

Many types covered by gen are derived from the STL (Standard Template Library), e.g. vecteur is a typedef for std::vector<gen>, they should therefore be straightforward to use. User functions C++-equivalent have most of the time the same name preceded by _ (for non-unary functions, arguments are grouped in a vecteur before the function call, it appears always as a unary gen'gen function).

4.5.3 Dynamic modules 

Writing a dynamic module requires in addition the declaration of user functions, so that they can be called inside an xcas session after an insmod call. For example, a module to have French names for the user language control words, is in the directory src, file progfr.cc.

4.6 Future plans 

• Math library improvements,
• Compatibility improvement,
• Finish the source cleanup so that global variables are used only for the user langage, parallelization of some algorithms using threads (e.g. the modular factorization step when factoring a polynomial over ).
• User english full documentation.
• Programmer documentation.
• CVS/bugzilla for the code, so that other people can contribute.
• Equationwriter full rewrite
• Script compiler
• Improved Giac online interface (giac on the web)