[PDF] Le clouage des sols. Application au soutènement de fouille. Étude

View - Download Le clouage des sols. Application au soutènement de fouille. Étude

Previous PDF

Next PDF

Preface

En 2019, les 30emes journees francophones des langages applicatifs (JFLA) se deroulent aux Rousses dans le Jura. Apres une edition mediterraneenne a Banyuls-sur-Mer, les JFLA retrou- vent donc une nouvelle fois la montagne. Chaque annee, les JFLA reunissent, dans un cadre convivial, des concepteurs, des developpeurs et des utilisateurs des langages fonctionnels, des assistants de preuve et des outils de verication de programmes en presentant des travaux varies, allant des aspects les plus theoriques aux applications industrielles. Cette annee, nous avons selectionne 11 articles de recherche et 4 articles courts. Les thematiques sont variees : preuve formelle, execution symbolique, verication de programmes, langages de programmation, mais aussi theorie des categories et programmation synchrone. La selection a ete faite par les membres du comite de programme a partir des articles recus apres les 18 soumissions de resumes. Ceux-ci ont ete aides dans leur travail par des rappor- teurs exterieurs que nous souhaitons remercier ici : Timothy Bourke, Adrien Guatto et Pascal Schreck. Cette annee, le format des papiers courts permet de faire conna^tre a la communaute des JFLA des travaux en cours ou bien recemment publies. Pour completer le programme, nous benecions de deux cours, l'un par Guillaume Melquiond

sur les liens entre l'arithmetique des ordinateurs et les preuves formelles; l'autre par Pierre-Marie

Pedrot sur la prise en compte des eets dans la theorie des types. Nous assisterons egalement a deux exposes invites, le premier par Ilaria Castellani sur les types de session qui peuvent ^etre vus comme une abstraction pour les protocoles de communication et le second par Pierre Courtieu sur l'etude formelle de protocoles de deplacement de robots. Enn cette 30eme edition des JFLA est l'occasion de se retrouver et d'observer le chemin parcouru depuis quelques annees. Nous avons selectionne les 3 orateurs les plus proliques des

10 dernieres editions (2009 a 2018). Tous les 3 ont, chacun en ce qui les concerne, presente au

moins 7 contributions aux JFLA en 10 ans. Il s'agit de Jean-Christophe Filli^atre qui nous fera une synthese de ses 25 annees d'experience(s) en programmation avec OCaml, de Louis Mandel qui fera un tour d'horizon de la programmation synchrone aux JFLA et d'Alan Schmitt qui nous parlera de semantiques formelles certiees. Nous remercions chaleureusement la cellule Congres de l'Universite de Strasbourg qui nous a accompagnee sur le chemin logistique et administratif des JFLA 2019: Christine Guibert, et surtout Marion Oswald, qui a ete presente de bout en bout pour gerer tous les aleas adminis- tratifs rencontres. Enn, nos sinceres remerciements a nos genereux sponsors. Cette annee encore, les etudiants orateurs ne paient pas les frais d'hebergement et d'inscription. Merci au laboratoire ICube de l'Universite de Strasbourg, au CEA LIST, au GDR GPL, a OcamlPro et a TrustInSoft.

Nicolas Magaud & Zaynah Dargaye

Universite de Strasbourg CEA List

i

Comité de programme

Nicolas Magaud ICube, Université de Strasbourg (président)

Zaynah Dargaye CEA List (vice-présidente)

Guillaume Burel École Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)

Evelyne Contejean CNRS, Université Paris-Sud

Claire Dross Adacore

Guillaume Dufay Prove & Run

Benjamin Grégoire Inria Sophia-Antipolis Méditerranée

Sébastien Hinderer Inria Paris

Marc Pouzet ENS

Yann Régis-Gianas IRIF

Bernard Serpette Inria Bordeaux Sud-Ouest

Mihaela Sighireanu IRIF

Julien Tesson LACL

Comité de pilotage

Pierre Castéran Université de Bordeaux

Catherine Dubois École Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)

Micaela Mayero LIPN, Université Paris 13

Alan Schmitt Inria Rennes - Bretagne Atlantique

Julien Signoles CEA LIST

Pierre Weis Inria Paris

iii

Table des matieres

Cours invites. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1

Arithmetique des Ordinateurs et Preuves Formelles. . . . . . . . . . . . . . . . . . . .3

Guillaume Melquiond

Des Theories des Types qui font de l'Eet. . . . . . . . . . . . . . . . . . . . . . . . . . . . .13

Pierre-Marie Pedrot

Exposes invites. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15

Types de Session : une Abstraction pour les Protocoles de Communication 17

Ilaria Castellani

Les Protocoles de Deplacement de Robots : l'Algorithmique Distribuee comme Terrain de Jeu pour la Preuve Formelle. . . . . . . . . . . . . . . . . . . . . . . .19

Pierre Courtieu

Session speciale : 30 ans de JFLA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21 Retour sur 25 ans de Programmation avec OCaml. . . . . . . . . . . . . . . . . . . . . .23

Jean-Christophe Filli^atre

Programmation Synchrone aux JFLA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25

Guillaume Baudart, Louis Mandel et Marc Pouzet

Semantiques Formelles et Certiees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41

Alan Schmitt

Articles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43

Suspension et Fonctorialite : Deux Operations Implicites Utiles en CaTT. .45

Thibaut Benjamin et Samuel Mimram

SQL a l'

Epreuve de Coq : Une semantique Formelle pour SQL. . . . . . . . . . .61

Veronique Benzaken et

Evelyne Contejean

SMTCoq: Automatisation Expressive et Extensible dans Coq. . . . . . . . . . . .77 Valentin Blot, Amina Bousalem, Quentin Garchery et Chantal Keller CAMLroot: Revisiting the OCaml FFI. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .93

Frederic Bour

Arguments Cadences dans un Compilateur Lustre Verie. . . . . . . . . . . . . . .109

Timothy Bourke et Marc Pouzet

Formalisation en Coq d'Algorithmes de Filtres Numeriques. . . . . . . . . . . . . .125

Diane Gallois-Wong

v Combinatoire Formelle avec Why3 et Coq. . . . . . . . . . . . . . . . . . . . . . . . . . . . .139 Alain Giorgetti, Catherine Dubois et Remi Lazarini

Axiomes de Continuite en Geometrie Neutre : une

Etude Mecanisee en Coq155

Charly Gries, Julien Narboux et Pierre Boutry

Unboxing Mutually Recursive Type Denitions in OCaml. . . . . . . . . . . . . . .173

Simon Colin, Rodolphe Lepigre et Gabriel Scherer

Typer: ML Boosted with Type Theory and Scheme. . . . . . . . . . . . . . . . . . . .193

Stefan Monnier

De l'Assembleur sur la Ligne ? Appelez TInA !. . . . . . . . . . . . . . . . . . . . . . . .209 Frederic Recoules, Sebastien Bardin, Richard Bonichon, Laurent Mounier et Marie-Laure Potet

Articles courts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .225

Learn-OCaml : un Assistant a l'Enseignement d'OCaml. . . . . . . . . . . . . . . . .227 Cagdas Bozman, Benjamin Canou, Roberto Di Cosmo, Pierrick Couderc, Louis Gesbert, Gregoire Henry, Fabrice Le Fessant, Michel Mauny,

Carine Morel, Loc Peyrot et Yann Regis-Gianas

Formally Veried Decomposition of Non-binary Constraints into Equiva-

lent Binary Constraints. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .237

Catherine Dubois

En Finir avec les Faux Positifs gr^ace a l'Execution Symbolique Robuste. . .245 Benjamin Farinier, Sebastien Bardin, Richard Bonichon et Marie-Laure Potet

Un Mecanisme de Preuve par Re

exion pour Why3 et son Application aux

Algorithmes de GMP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .253

Raphael Rieu-Helft

vi

Cours invités

1 Arithmétique des Ordinateurs et Preuves Formelles

Guillaume Melquiond

Inria, LRI, Univ. Paris-Saclay

guillaume.melquiond@inria.fr

Résumé

Cet article complète l'exposé du même nom et en reprend les grandes idées. L'exposé s'intéresse aux liens entre arithmétique des ordinateurs et vérication automatique, que ce soit pour de la preuve de programmes ou de théorèmes, le tout dans le cadre formel de l'assistant de preuve Coq. L'exposé est construit en deux parties.

La première s'intéresse à la preuve automatique de théorèmes mathématiques à l'aide

de méthodes venues de l'arithmétique des ordinateurs. Il s'agit d'abord d'implanter et de formaliser une arithmétique à virgule ottante simpliée mais ecace an d'approcher les

calculs réels. Puis une arithmétique d'intervalles peut être implantée au-dessus, orant un

moyen able de calculer des bornes sur des expressions à valeurs réelles. L'arithmétique d'intervalles dans sa version naïve est certes able mais rarement ecace à cause de l'eet de corrélation. L'étape suivante est donc de construire des approximations polynomiales ables pour réduire cet eet. En combinant tout cela avec de la preuve par réexion, il est alors possible de prouver automatiquement des bornes nes sur des expressions à valeurs

réelles. Le procédé peut être poussé jusqu'à des intégrales propres voire même impropres.

Tout cela a été intégré à la bibliothèque CoqInterval. La deuxième partie s'intéresse à la vérication formelle d'algorithmes qui mettent en

oeuvre de l'arithmétique à virgule ottante. C'était déjà le cas de certains des algorithmes

de la première partie, mais l'utilisation de l'arithmétique d'intervalles les rendait en grande

partie corrects par construction. Par contre, si l'on s'intéresse à des bibliothèques ecaces

d'approximation de fonctions mathématiques (les libm ), il n'y a plus rien de cela. Sans une vérication formelle, il est alors dicile de se convaincre que le code ne contient pas

de nombreux bogues subtils dus à l'arithmétique à virgule ottante. Il est alors nécessaire

d'eectuer une analyse ne des erreurs d'arrondi commises an de s'assurer que les valeurs calculées par le code approchent correctement la fonction mathématique souhaitée. Mais une telle analyse est longue et dicile, surtout dans un cadre formel. C'est pour cela que

l'outil Gappa a été conçu. Il permet de vérier automatiquement des propriétés sur des

algorithmes ottants, par une combinaison d'arithmétique d'intervalles, de réécriture et d'analyse de l'erreur directe. Il est aussi capable de générer des preuves formelles pour décharger des buts Coq.

1 Introduction

L'arithmétique à virgule ottante est une arithmétique bien adaptée au calcul en machine et

son utilisation très majoritaire consiste en l'approximation d'opérations sur les nombres réels.

Inspirée de la notation scientique, elle ore une plage étendue de valeurs tout en garantissant un

nombre conséquent de chires signicatifs. Ainsi, le formatbinary64est capable de représenter des nombres de10-308à10308avec au moins 15 chires décimaux signicatifs. La norme

internationale IEEE 754 décrit précisément les formats et les opérations arithmétiques [

8

Cette norme étant très suivie, il est possible d'eectuer des calculs ottants dans un très grand

nombre d'environnements. On pourrait donc croire que, pour ce qui est d'eectuer des calculs numériques en machine,

au moins d'un point de vue arithmétique, la question est réglée. Malheureusement, ce n'est pas

3 Arithmétique des Ordinateurs et Preuves Formelles Melquiond le cas. Tout d'abord, même si la plage de valeurs semble immense, nous ne sommes pas à l'abri d'un programme qui, lors de ses calculs, sortirait de cette plage, au moins temporairement.

Ainsi, si la norme d'un vecteur excède10154, la façon la plus naturelle de calculer cette norme

va provoquer un débordement de capacité. Dans ce cas, le calcul ottant va renvoyer+1, ce qui est assez loin de la valeur attendue. Un problème plus pernicieux est la question de la qualité numérique des calculs (accuracy en anglais, à ne pas confondre avecprecision). A priori, tout semblait parfait pourtant. Quinze chires décimaux sont en eet susants pour représenter précisément la plupart des valeurs

intéressantes en pratique (oublions les problématiques monétaires). Qui plus est, la norme IEEE-

754 garantit que, si le résultat d'une opération ottante n'est pas exactement représentable, le

nombre représentable le plus proche du résultat exact doit être renvoyé. Ce nombre le plus

proche sera représenté dans la suite par(). Malheureusement, ce n'est pas parce que chaque

opération intermédiaire est correcte avec quinze chires que le résultat nal l'est. Pour s'en

convaincre, il sut de considérer le calcul approché de(260+1)-260. La première somme260+1 est très bien approchée par(260+ 1) = 260. Par contre, la somme nale(260+ 1)-260= 1 est inniment mal approchée par((260+ 1)-260) =(260-260) = 0. Il existe de nombreux exemples de calcul ottant ayant eu des conséquences désastreuses. Le plus connu, car le plus dramatique, causa la mort de 28 personnes et de nombreux blessés en

1991. Durant la Première Guerre du Golfe, l'armée des États-Unis installa des systèmes Patriot

pour intercepter les missiles Scud visant ses bases. Mais la très grande vitesse des missiles Scud

rendait l'interception hasardeuse et la décision fut prise d'augmenter la précision de certains

calculs de trajectoire (mais pas tous). Cette modication provoqua une dérive des erreurs de calcul. Laisser tourner le système quelques jours sans le redémarrer fut susant pour que le missile intercepteur rate sa cible d'une fraction de seconde [ 12

Ce qui rend cet exemple particulièrement intéressant est que le système s'est eondré parce

que des personnes ont cherché à augmenter la qualité des calculs. Cela montre à quel point

les calculs numériques déent l'intuition [ 11 ]. Se pose alors naturellement la question de leur abilité. Comment s'assurer qu'un programme ne va provoquer aucun comportement exception- nel, par exemple un débordement? Comment s'assurer que le résultat calculé est susamment proche du résultat attendu pour être utilisable sans risque?

La section

2 donne quelques dénitions et propriétés pr éliminairessur l'arithmé tiqueà vir- gule ottante et l'arithmétique d'intervalles. La section 3 s'in téressee nsuiteà des algor ithmes arithmétiques simples qui permettent de prouver formellement et automatiquement des proprié- tés par le calcul numérique. Finalement, la section 4 mon trecommen tv érierdes algorithmes

bien plus subtils tels qu'on peut les trouver dans les bibliothèques de fonctions mathématiques.

2 Préliminaires

2.1 Arithmétique à virgule ottante

Pour un format donné, les nombres ottants représentent des nombres réels de la forme m·βe. Les entiersm,βetesont le signiant, la base et l'exposant du nombre. La base est

xée, généralement2ou10. Pour des raisons matérielles, les valeurs demetesont contraintes.

En règle générale, nous assimilerons un nombre ottant au nombre réel qu'il représente.

Pour simplier la formalisation, nous ne considérons que des formatsFpour lesquels il existe une fonction?2Z!Ztelle que

F=fx2Rjx·β-'(mag(x))2Zg

4 Arithmétique des Ordinateurs et Preuves Formelles Melquiond

Formatβ % e

minbinary322 24-149binary642 53-1074binary1282 113-16494decimal3210 7-101decimal6410 16-398decimal12810 34-6176Table1 Paramètres des formats décrits par la norme IEEE-754.

avecmag(x) =blogjxj+ 1c. Deux familles de formats nous intéressent plus particulièrement ici. Les formats FLX sont décrits par des fonctions?(e) =e-emintandis que les formats FLT sont décrits par?(e) = max(e-%;emin). Cette dernière famille de formats est susante pour représenter les formats

ottants classiques, si l'on fait abstraction des problèmes liés aux débordements de capacité. La

table 1 indique commen tc hoisirle sparamètres %etemin. Ceci étant dit, de nombreuses autres fonctions?sont possibles, donnant des formats plus ou moins exotiques [4, Ÿ3.1.3]. La norme IEEE-754 indique que chaque opération ottante doit se comporter comme si elle

calculait d'abord le résultat inniment précis puis elle l'arrondissait au format de destination.

Cela justie l'introduction d'un opérateur d'arrondi2(). Une somme ottante entre deux nombres ottantsuetvsera ainsi notée2(u+v). Les opérateurs d'arrondi qui nous intéressent ont la forme suivante :

2(x) =bx·β-'(mag(x))e ·β'(mag(x));

avecbeune fonction partie entière. Si l'on choisit la partie entière inférieure, on obtient l'arrondi vers-1, tandis que si l'on choisit la partie entière supérieure, on obtient l'arrondi vers+1:

5(x) =bx·β-'(mag(x))c ·β'(mag(x));

4(x) =dx·β-'(mag(x))e ·β'(mag(x)).

Enn, si l'on choisit l'entier le plus proche du réel (avec priorité à l'entier pair dans le cas

ambigu), on obtient l'arrondi au plus près, au sens de la norme IEEE-754.

2.2 Arithmétique d"intervalles

DénotonsIles sous-ensembles fermés et connectés deR. Il s'agit de;et des intervalles (-1;v],[u;+1)et[u;v]avecuvdes nombres réels. Dans ce qui suit, nous nous intéresserons principalement aux intervalles dont les deux bornes sont des nombres ottants. On dira d'une fonctionf2In!Iqu'elle est une extension par intervalles def2Rn!R si elle satisfait la propriété d'inclusion :

8x12I;...;xn2I;8x12R;...;xn2R;

x Une propriété intéressante des opérateurs d'arrondi vers1est5(x)x 4(x). Par conséquent, si l'on a deux encadrementsu2[u;u]etv2[v;v], on peut en déduire les encadre- 5 Arithmétique des Ordinateurs et Preuves Formelles Melquiond ments suivants par monotonie des opérateurs arithmétiques : u+v2[5(u+v);4(u+v)]; u-v2[5(u-v);4(u-v)]; Cela permet donc de programmer très facilement des extensions par intervalles des opéra-

teurs arithmétiques réels en quelques opérations ottantes. Et comme la propriété d'inclusion

est préservée par composition, il est donc facile de borner une expression réelle arbitrairement

compliquée. Cependant, la propriété d'inclusion garantit seulement que l'encadrementf(~x)2f(~x)est correct. Elle ne dit absolument rien de la nesse de l'intervallef(~x). En particulier, celui-ci peut

être trop large pour en déduire une propriété intéressante surf(~x). Par exemple, dex2[0;1], on

peut déduirex-x2[0;1]-[0;1] = [-1;1]par arithmétique d'intervalles. C'est un encadrement

correct mais assez médiocre puisquex-x= 0. C'est le phénomène de perte de corrélation dû

à la présence d'occurrences multiples dex.

3 Preuve par le calcul numérique

Comme indiqué dans la section précédente, l'arithmétique d'intervalles ore une façon simple

de borner des expressions à valeurs réelles. Voyons voir comment transposer cela dans le cadre formel d'un système comme Coq. L'objectif est d'arriver à prouver formellement et automati- quement une propriété comme Z +1 -1(0.5·log(2+ 2.25) + 4.1396 + log)20.25 +2d226.844.(1)

3.1 Arithmétiques

quotesdbs_dbs23.pdfusesText_29

[PDF] Géométrie dans l 'espace - Logamathsfr

[PDF] Droites du plan - Exo7 - Emathfr

[PDF] guide du port du havre - Grand Port Maritime du Havre

[PDF] DROITS DE SOLIDARITE EN DROIT INTERNATIONAL*

[PDF] la portée juridique des droits économiques, sociaux et culturels

[PDF] Règlement de la classe de CE1 - Académie de Nancy-Metz

[PDF] ou druses

[PDF] Buried Disc Drusen have hypo-reflective appearance on SD-OCT

[PDF] LA DEGENERESCENCE MACULAIRE LIEE A L 'AGE

[PDF] Drusen du nerf optique

[PDF] Drusen du nerf optique

[PDF] ds 4 caractéristiques techniques et équipements - Citroen

[PDF] 3ème - Arithmétique - Exercices

[PDF] Sujets et corrigés des DS de mathématiques BCPST1A Lycée

[PDF] Exercices de Khôlles de Mathématiques, premier - Normalesuporg