LogoLogo

Malakhovski, Ian. Sur le pouvoir expressif des structures applicatives et monadiques indexées

Malakhovski, Ian (2019). Sur le pouvoir expressif des structures applicatives et monadiques indexées.

[img]PDF - nécessite un logiciel de visualisation PDF comme GSview, Xpdf or Adobe Acrobat Reader
999Kb

Résumé en francais

Il est bien connu que des constructions théoriques très simples telles que les structures Either (équivalent type théorique de l'opérateur logique "ou"), State (représentant des transformateurs d'état composables), Applicative (application des fonctions généralisée) et Monad (composition de programmes séquentielles généralisée), nommés structures en Haskell, couvrent une grande partie de ce qui est habituellement nécessaire pour exprimer avec élégance la plupart des idiomes informatiques utilisés dans les programmes classiques. Cependant, il est usuellement admis qu'il existe plusieurs classes d'idiomes couramment utilisés qui ne s'intègrent pas bien à ces structures, les exemples les plus remarquables étant les transformations entre arbres (types de données, dont l'utilisation doit s'appuyer soit sur les motifs généralisés soit sur une infrastructure de méta programmation lourde) et traitement des exceptions (qui sont d'habitude supposés nécessiter un langage spécial et une prise en charge de l'exécution). Ce travail a pour but de montrer que beaucoup de ces idiomes peuvent, en fait, être exprimés en réutilisant ces structures bien connues avec des modifications mineures (le cas échéant). En d'autres termes, le but de ce travail est d'appliquer les principes du rasoir KISS (Keep It Stupid Simple) et/ou d'Occam aux structures algébriques utilisées pour résoudre des problèmes de programmation courants. Techniquement parlant, ce travail a pour but de montrer que les généralisations naturelles de classes de types Applicative et Monad de Haskell, associées à la possibilité d'en faire des produits cartésiens, en produisent un cadre commun très simple pour exprimer de nombreuses choses pratiques, dont certaines sont des nouvelles méthodes très commodes pour exprimer des idées de programmation communes, tandis que les autres peuvent être vues comme systèmes d'effets. Sur ce dernier point, si l'on veut généraliser des exemples présentés dans une approche de la conception de systèmes d'effets en général, on peut alors considérer la structure globale de cette approche comme un cadre quasi syntaxique qui permet d'ériger une structure générale du cadre "mariage" au dessus de différents systèmes d'effets adhérant aux principes de base. (Bien que ce travail ne soit pas trop approfondi dans la dernière, car il est principalement motivé par des exemples qui peuvent être immédiatement appliqués à la pratique de Haskell.) Il convient toutefois de noter qu'en fait, ces observations techniques n'ont rien d'étonnant: Applicative et Monad sont respectivement des généralisations de composition fonctionnelle et linéaire des programmes; ainsi, naturellement, les produits cartésiens de ces deux structures doivent couvrir en grande partie ce que les programmes font habituellement.

Sous la direction du :
Directeur de thèse
Soloviev, Sergei
Vasilyev, Nikolay
Ecole doctorale:Mathématiques, informatique, télécommunications de Toulouse (MITT)
laboratoire/Unité de recherche :Institut de Recherche en Informatique de Toulouse (IRIT), UMR 5505
Mots-clés libres :Foncteurs applicatifs - Monades - Monades indexées - Type algébrique de données - Métaprogrammation - Processeur basé sur la pile - Combinateurs d'analyseurs syntaxiques - Logique - Théorie des catégories
Sujets :Informatique
Déposé le :17 Jan 2020 16:49