Valérie Ménissier-Morain et Pierre Weis

An exact arithmetic package for ML

Résumé: Nous présentons la comception et l'implémentation d'une bibliothèque d'arithmétique rationnelle exacte pour le langage fonctionnel Caml, un dialecte de ML proche du LCF-ML d'origine.

Notre arithmétique, écrite presque entièrement en Caml, combine l'efficacité, la puissance d'expression et la flexibilité. Pour des raisons d'efficacité, la bibliothèque fournit plusieurs types de base différents pour représenter les nombres et pour augmenter la souplesse du système, de nombreuses fonctions opérant sur chacun de ces types sont implémentées.

Pour gèrer cette complexité et pour que cette bibliothèque reste simple à utiliser par l'utilisateur occasionnel, nous avons conçu un type fédérateur des nombres qui permet un accès facile à l'arithmétique exacte.

Cependant, l'intégration de cette bibliothèque à un compilateur ML existant pose plusieurs problèmes intéressants: les nombres rationnels introduisent un nouveau type de données qui ne correspond pas à une algèbre libre. Ceci nécessite de modifier l'algorithme de filtrage de ML. La prolifération des types de base nous a contraints à trouver une nouvelle façon de lire des nombres; les bibliothèques existantes n'ont pas été écrites pour tenir compte de ces nouveaux types numériques. Nous devons donc les adapter à la bibliothèque arithmétique pour éviter un nombre gigantesque de coercions ou d'erreurs de typage; finalement, puisqueles opérateurs de base manipulent différents types numériques (l'opération mathématique "+" possède neuf types incompatibles dans cette bibliothèque) il nous faut disposer d'un mécanisme pour les réconcilier. Nous voulons pouvoir utiliser les notations arithmétiques usuelles dans les expressions arithmétiques pour mréserver la lisibilité des programmes.

Dans cet article, nous décrivons birèvement l'implémentation de la bibliothèque en Caml et une partie des algorithmes utilisés. En particulier nous étudions l'opportunité de la normalisation des nombres rationnels. Nous présentons ensuite le type fédérateur des nombres et mettons en évidence ses propriétés.

Nous présentons les problèmes et proposons des solutions pour intégrer cette bibliothèque à un compilateur ML existant. Puis nous donnons des exemples intéressants de calcul numérique et symbolique utilisant cette bibliothèque, et finalement nous comparons les performances de cette arithmétique avec celle d'autres langages connus.

Version PostScript de cette publication

Référence BibTeX de cette publication

Page personnelle de Valérie Ménissier-Morain

Page personnelle de Pierre Weis