Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 24 Octobre 2000

Calcul des adjoints et programmation fonctionnelle

par Jerzy Karczmarczuk (GREYC)

Souvent dans la programmation dite "scientifique" on a besoin de calculer les dérivées (Jacobiens, Hessiens, gradients, etc.) des fonctions définies par le programme. On veut des algorithmes *exacts* (précision machine), et sans engager le calcul formel. On utilise donc les techniques de "Différentiation Algorithmique", dont l'implantation fonctionnelle standard dite "forward" (avancée?) a été présentée par moi il y a deux ans. Cette fois il s'agit de l'algorithme dit "innverse" ou "retardé", ou adjoint.

Il arrive parfois qu'une valeur finale, la seule qui nous intéresse, par exemple la température d'un réacteur, dépend de plusieurs paramètres de construction, et des conditions initiales. On a inventé ici une technique particulière de DA, où à chaque entité (variable, sous-expression) on ajoute son *adjoint* : la dérivée de la valeur finale p.rap. à cette entité. L'implantation impérative de cette technique est très non-naturelle et lourde.

Je montre comment implanter la technique de différentiation inverse en utilisant la programmation fonctionnelle paresseuse, et l'approche monadique à la construction des programmes fonctionnels qui *transforment l'ETAT du système*. Cet état c'est la (ou les) valeur de l'adjoint, et la particularité de cette stratégie est que l'état se propage du futur vers le passé, ce qui est très bizarre, mais des courants antithétiques de ce genre sont connus ailleurs, p.ex. dans la compilation : les attributs hérités descendent de la racine vers les feuilles, tandis qu'un parseur ascendant construit l'arbre à partir des feuilles.

Ma solution n'est pas (encore) très efficace, mais elle est utilisable, *très simple pour l'utilisateur*, et assez drôle à cause de cette "machine à voyager dans le temps" réalisé en Haskell.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr