Date : 2019
Type : Livre / Book
Type : Thèse / ThesisLangue / Language : français / French
Langages de programmation fonctionnelle -- Simulation, Méthodes de
Accès en ligne / online access
Accès en ligne / online access
Accès en ligne / online access
Résumé / Abstract : La première partie de la thèse a pour sujet les effets de bord dans les programmes fonctionnels, et leur simulation par les monades. Les propositions ont une portée générale : elles peuvent s’appliquer peu importe le thème du programme. Cependant, elles ont été inspirées par un contexte de programmation de simulateur d’économies. Ce type de programme utilise intensément les effets de bord et les répétitions de fonctions. Les propositions de la thèse sont plus pertinentes pour les programmes qui présentent ces caractéristiques.Comme bien d’autres, elles sont pensées dans un objectif d’organisation stricte du programme.Elles ne sont pas adaptées pour réaliser un programme "vite fait bien fait", mais plutôt un programme dans lequel des parties critiques ont été sécurisées et n’ont plus besoin d’attention.Le chapitre 1 introduit la programmation fonctionnelle, et des schémas d’exécution reflétant la consommation mémoire lors de l’exécution. Il introduit les monades, et les transformateurs de monades, en tant que mécanismes permettant d’automatiser la simulation des aspects mutables dans un contexte immutable. Le chapitre 2 aborde la gestion des effets de bord : la simulation d’une variable mutable par la monade State, et l’encadrement de sa valeur par un prédicat. Le chapitre commence par définir précisément cerque signifie le respect du prédicat, notamment par la solution bien connue du type abstrait. Ensuite, nous faisons observer que le prédicat est plus expressif lorsqu’il concerne un type fonctionnel (A ! A) plutôt que simplement A. La monade State fournit un support adéquat pour implanter le prédicat dans le programme, puisqu’elle exprime une variable mutable par des compositions de fonctions. Dans une simulation,la monade State abstraite avec prédicat permet d’exprimer des mécanismes auxiliaires mais ubiquitaires, tels la génération de nombre pseudo-aléatoire, ou la gestion de comptes bancaires. Ce sont deux concepts, la simulation d’effets de bord, et la garantie de prédicat, qui se résolvent par une même structure : la monade State abstraite.Le chapitre 3 concerne un autre aspect de la sécurité du programme : la consommation mémoire. Celle-ci est bornée par les composants physiques de l’ordinateur qui exécute le programme. Si l’exécution du programme nécessite trop d’espace mémoire, elle est simplement arrêtée. Le chapitre présente les deux types d’erreurs mémoire rencontrés en programmation fonctionnelle : Stack_Overflow et Out_Of_Memory. L’erreur Stack_Overflow est causée par les fonctions récursives. Le remède est l’optimisation de l’appel terminal.Cependant il est plus difficilement applicable en présence de monades, qui remplacent l’application standard par l’application bind, sur laquelle le programmeur a moins de contrôle. L’exemple emblématique est la monade State, qui crée des compositions de fonctions dont l’évaluation n’est pas optimisée. De plus,les compositions de fonctions doivent être stockées et risquent de générer une erreur Out_Of_Memory.Le chapitre présente ensuite les solutions existantes, dont la meilleure définit une fonction de récursion spécialisée à chaque monade. Les solutions existantes ne résolvent pas la situation où la récursion n’est pas"contrôlée", c’est à dire où le programmeur fournit seulement la fonction à répéter. Dans ce contexte, les solutions provoquent un risque d’erreur Out_Of_Memory, car elles stockent des opérations en suspension. [....]
Résumé / Abstract : The first part of the phd concerns side effects in functional programs, and their simulation by monads. The proposed solutions have a general goal : they are useful no matter the subject of the program. However, they have been inspired by the context of programming economics simulators. Indeed this kind of program use intensively side effects and repetition of functions calls. The proposed solutions are more usefulfor program with these characteristics. Like many others, they are suited for a strict organization of the program. They are not meant to build a "quick and well done" program, rather a program whose critical parts have been made safe and does not need any more attention.The chapter 1 introduces functional programming, with execution schemes representing memory consumption.It introduce monads, and monads transformers, as mechanisms allowing to automatize the simulation of mutable aspect in an immutable context.Chapter 2 address handling of side effects : the simulation of a mutable variable by the State monad, the framing of its value by a predicate. The chapter starts by defining precisely what means the respect of apredicate, in particular by the well known solution of abstract type. Then, we observe that the predicateis more expressive when it concerns a functional type (A ! A) rather than simply A. The State monad gives a adequate structure to implant the predicate in the program, since it simulates a mutable variable byf unction composition. In an economics simulator, the abstract State monad with a predicate can expresssimilar but ibiquitous mechanisms, as pseudo-random generation, or handling of bank accounts. These aretwo concepts, simulation of side effects and respect of a predicate, that are resolved by the abstract State monad.Chapter 3 address another aspect of program safety : memory consumption. It is boundered by physical components of the computer. If the execution of the program necessits too much memory space, the program is simply stopped. The chapter presents the two type of memory error in functional programing :Stack_Overflow and Out_Of_Memory. The error Stack_Overflow is caused by recursive functions. The solution is tail-call optimization. However it is more difficult to apply in the presence of monads, which replace the standard application by application bind, on which the oprogrammer has less control. The emblematic example is the State monad, which creates composition of functions non-optimized by tail-call.Moreover, composition of functions has to be stored and can generate an error Out_Of_Memory.The chapter then introduces the existing solutions, and the best one defines a function of recursion specialized for each monad. However none of the solution resolve the case where the recursion is "not controlled",ie when the programmer just gives a function to be repeted. In this context, the existing solutions present arisk of Out_Of_Memory, because they store functions in suspension.We present our solution : "monadic concretes". The idea is to create a context inside of which all the informations are known, for example theauxiliary variable of State. It is then possible to perform recursive uncontrolled recursion without suspendingoperations. The context is responsible for waiting the informations.The chapter ends by presenting the context of Read Eval Print Loop (REPL). It consists in extracting(reading) the monadic value between every bind. This present a problem with existing solutions, since every tome they have to recompute the suspensions. Monadic concretes then shows themselves adequate,since they do not use suspensions.Chapter 4 gather a set of observations resulting from the writing of a small functional economis simulator.They concerns the monads library realized from the previous chapter, the problem of lift, the use of mutability in isolated and time critical places. The chapter ends by an attempt of comparing programing with mutability versus immutability. [....]