This paper main goal is to introduce the basic language and programming styles of the mathematical software Mathematica (5.2), and applies it to solve problems in algebra, calculus, linear algebra, probability and statistics. We hope readers can enhance the interest of learning mathematics by the aid of software, verify the common theorem using the software, and solving mathematical problems.

The intricate concepts of ad-hoc polymorphism and overloading permeate the field of programming languages despite their somewhat nebulous definitions. With the perspective afforded by the state of the art, object-oriented Fortress programming language, this thesis presents a contemporary account of ad-hoc polymorphism and overloading in theory and in practice. Common language constructs are reinterpreted with a new emphasis on overloading as a key facility. Furthermore, concrete problems with overloading in Fortress, encountered during the author's experience in the development of the language, are presented with an emphasis on the ad hoc nature of their solutions. / text

In Artificial Intelligence, especially in area of constraint programming, it's popular to design various modeling languages which allow solving problems on domain level and by using domain specific abstractions. Techniques known from research on Domain-Specific Languages are often useful in this effort. Functional programming languages offer new tools for designing such languages, particularly Domain-Specific Embedded Languages. This work investigates the advantages and disadvantages of using functional programming for designing and implementing a Domain-Specific Embedded Language for state space search problems.

S'assurer qu'un programme informatique se comporte bien, surtout dans des applications critiques (santé, transport, énergie, communications, etc.) est de plus en plus important car les ordinateurs et programmes informatiques sont de plus en plus omniprésents, voir essentiel au bon fonctionnement de la société. Mais comment vérifier qu'un programme se comporte comme prévu, quand les informations qu'il prend en entrée sont de très grande taille, voire de taille non bornée a priori ? Pour exprimer avec exactitude ce qu'est le comportement d'un programme, il est d'abord nécessaire d'utiliser un langage logique formel. Cependant, comme l'a montré Gödel dans, dans tout système formel suffisamment riche pour faire de l'arithmétique, il y a des formules valides qui ne peuvent pas être prouvées. Donc il n'y a pas de programme qui puisse décider si toute propriété est vraie ou fausse. Cependant, il est possible d'écrire un programme qui puisse vérifier la correction d'une preuve. Ce travail utilisera justement un tel programme, Coq, pour formellement vérifier la correction d'un certain programme. Dans cette thèse, nous expliquons le développement d'une nouvelle version de Rainbow, plus rapide et plus sûre, basée sur le mécanisme d'extraction de Coq. La version précédente de Rainbow vérifiait un certificat en deux étapes. Premièrement, elle utilisait un programme OCaml non certifié pour traduire un fichier CPF en un script Coq, en utilisant la bibliothèque Coq sur la théorie de la réécriture et la terminaison appelée CoLoR. Deuxièmement, elle appelait Coq pour vérifier la correction du script ainsi généré. Cette approche est intéressante car elle fournit un moyen de réutiliser dans Coq des preuves de terminaison générée par des outils extérieurs à Coq. C'est également l'approche suivie par CiME3. Mais cette approche a aussi plusieurs désavantages. Premièrement, comme dans Coq les fonctions sont interprétées, les calculs sont beaucoup plus lents qu'avec un langage où les programmes sont compilés vers du code binaire exécutable. Deuxièmement, la traduction de CPF dans Coq peut être erronée et conduire au rejet de certificats valides ou à l'acceptation de certificats invalides. Pour résoudre ce deuxième problème, il est nécessaire de définir et prouver formellement la correction de la fonction vérifiant si un certificat est valide ou non. Et pour résoudre le premier problème, il est nécessaire de compiler cette fonction vers du code binaire exécutable. Cette thèse montre comment résoudre ces deux problèmes en utilisant l'assistant à la preuve Coq et son mécanisme d'extraction vers le langage de programmation OCaml. En effet, les structures de données et fonctions définies dans Coq peuvent être traduits dans OCaml et compilées en code binaire exécutable par le compilateur OCaml. Une approche similaire est suivie par CeTA en utilisant l'assistant à la preuve Isabelle et le langage Haskell. / Making sure that a computer program behaves as expected, especially in critical applications (health, transport, energy, communications, etc.), is more and more important, all the more so since computer programs become more and more ubiquitous and essential to the functioning of modern societies. But how to check that a program behaves as expected, in particular when the range of its inputs is very large or potentially infinite? In this work, we explain the development of a new, faster and formally proved version of Rainbow based on the extraction mechanism of Coq. The previous version of Rainbow verified a CPF le in two steps. First, it used a non-certified OCaml program to translate a CPF file into a Coq script, using the Coq libraries on rewriting theory and termination CoLoR and Coccinelle. Second, it called Coq to check the correctness of the script. This approach is interesting for it provides a way to reuse in Coq termination proofs generated by external tools. This is also the approach followed by CiME3. However, it suffers from a number of deficiencies. First, because in Coq functions are interpreted, computation is much slower than with programs written in a standard programming language and compiled into binary code. Second, because the translation from CPF to Coq is not certified, it may contain errors and either lead to the rejection of valid certificates, or to the acceptance of wrong certificates. To solve the latter problem, one needs to define and formally prove the correctness of a function checking whether a certificate is valid or not. To solve the former problem, one needs to compile this function to binary code. The present work shows how to solve these two problems by using the proof assistant Coq and its extraction mechanism to the programming language OCaml. Indeed, data structures and functions de fined in Coq can be translated to OCaml and then compiled to binary code by using the OCaml compiler. A similar approach was first initiated in CeTA using the Isabelle proof assistant.

Gameplay programming is vital for video game development and benefits from good tools and techniques. However, techniques are still used in the industry that involves describing how the computer operates. Reactive programming is a way to describe eventful and stateful computer programs declaratively, focusing on what the program should accomplish. This thesis uses the reactive library UniRx with the game engine Unity 5 to create an FPS with reactive techniques, and discusses the advantages and disadvantages of these. Object-oriented reactive programming is used to combine reactive objects with Unity’s component-based framework without using wrappers for non-reactive objects. The results include static methods for observable user input, patterns when defining game components with reactive content, and communication between game objects through interface components. It can be concluded that reactive programming for game programming enables the programmer to describe and understand game logic in a declarative manner. However, combining UniRx and Unity 5 led to complex patterns. Suggestion for future work is using reactive programming with game engines that allows to design game objects that are fully reactive. / Gameplay-programmering är avgörande för utveckling av videospel och har nytta av bra verktyg och tekniker. Dock används tekniker i spelbranschen som kräver att programmeraren beskriver hur datorn utför uppgifter. Reaktiv programmering är ett sätt att beskriva händelserika och föränderliga datorprogram med fokus på vad programmet ska utföra. Denna avhandling använder det reaktiva biblioteket UniRx med spelmotorn Unity 5 för att skapa en FPS med reaktiva tekniker, samt diskuterar fördelarna och nackdelarna med dessa. Objektorienterad reaktiv programmering används för att kombinera reaktiva objekt med Unity’s komponentbaserade ramverk utan att använda wrappers för icke-reaktiva objekt. Resultaten inkluderar statiska metoder för observerbar användarinput, programmeringsmönster för definition av spelkomponenter med reaktivt innehåll och kommunikation mellan spelobjekt via gränssnittskomponenter. Man kan dra slutsatsen att reaktiv programmering för spelprogrammering gör det möjligt för programmeraren att beskriva och förstå spellogik på ett deklarativt sätt. Kombinationen av UniRx och Unity 5 ledde emellertid till komplexa mönster. Förslag till framtida arbete är att använda reaktiv programmering med spelmotorer som gör det möjligt att designa spelobjekt som är helt reaktiva.

Bugs in software is a very common problem, code reviews can help to catch bugs early on and detect which code is the most complex and may introduce bugs but when the code base is very large it can be costly to review all the code. Cyclomatic complexity can be used to give an indication of how complex the system source code is and help the developers to select which code they should review. But when measuring cyclomatic complexity on code written according to the functional paradigm, McCabe’s formula will not be sufficient since it is a formula most suitable for imperative code. Therefore we are making adaptations to a formula suited for pure functional languages in order to fit functional JavaScript. We are using an inductive empirical quantitative measurement method to calculate cyclomatic complexity on a directed graph implementation in order to define adaptations for functional JavaScript. Our results show a working adapted version of the formula. We have measured on a graph implemented in Haskell and on a corresponding functional JavaScript version which results in a cyclomatic complexity difference at only 0.375.

Ce manuscrit présente une méthode de conception au niveau système reposant sur la programmation fonctionnelle typée et visant à atténuer certains des problèmes complexifiant le développement des systèmes numériques modernes, tels que leurs tailles importantes ou la grande variété des blocs les constituant. Nous proposons un ensemble de mécanismes permettant de mélanger au sein d'un même design plusieurs formalismes de description distincts («modèles de calcul») se situant potentiellement à des niveaux d'abstraction différents. De plus, nous offrons au concepteur la possibilité d'expliciter directement les paramètres explorables de chaque sous-partie du design, puis d'en déterminer des valeurs acceptables via une étape d'exploration partiellement ou totalement automatisée réalisée à l'échelle du système. Les gains qu'apportent ces stratégies nouvelles sont illustrés sur plusieurs exemples. / This work presents a novel system-level design method based on typed functional programming and aiming at mitigating some of the issues making the development of modern digital systems complex, such as their increasing sizes and the variety of their subcomponents. We propose a range of mechanisms allowing to mix within a single design several description formalisms (``models of computation''), possibly at different abstraction levels. Moreover, the designer is provided with means to directly express the explorable parameters of each part of their design, and to find acceptable values for them through a partially or totally automatic system-wide architectural exploration step. The advantages brought by those new strategies are illustrated on several examples.

Com o avanço tecnológico dos últimos anos passou a ser normal vermos microprocessadores com múltiplos núcleos (cores). A expectativa é de que o crescimento da quantidade de núcleos passe a ser maior do que o crescimento da velocidade desses núcleos. Assim, além de se preocuparem em otimizar algoritmos sequenciais, os programadores começaram a dar mais atenção às possibilidades de aproveitamento de toda a capacidade oferecida pelos diversos cores. Existem alguns modelos de programação que permitem uma abordagem concorrente. O modelo de programação concorrente mais adotado atualmente é o baseado em threads, que utiliza memória compartilhada e é adotado em Java. Um outro modelo é o baseado em troca de mensagens, no qual as entidades computacionais ativas são denominadas atores. Nesse trabalho, estudamos a linguagem Scala e seu modelo de atores. Além disso, implementamos em Scala uma versão paralela de um algoritmo de classicação que simula o sistema imunológico dos animais, o AIRS paralelo, e comparamos seu desempenho com a versão em Java. / With the technological advance of the last years it has been normal to see microprocessors with multiple cores. The expectation is that the growth of number of cores becomes greater than the growth of the speed of these cores. This way, besides worrying about optimizing sequential algorithms, developers started to give more attention to the possibilities of proting from all capacity offered by the cores. There exists a few programming models that allow a concurrent approach. In these days, the most adopted concurrent programming model is the one based on threads, which uses shared memory and is adopted in Java. Other model is based on message passing, on which the active computational entities are called actors. In this project, we studied Scala language and its model based on actors. Besides that, we implemented in Scala a parallel version of a classification algorithm that simules the immune system of the animals, parallel AIRS, and compared its performance with the Java version.

Ce mémoire décrit et évalue un système de module qui améliore la migration de code dans le langage de programmation distribuée Termite Scheme. Ce système de module a la possibilité d’être utilisé dans les applications qu’elles soient distribuées ou pas. Il a pour but de faciliter la conception des programmes dans une structure modulaire et faciliter la migration de code entre les nœuds d’un système distribué. Le système de module est conçu pour le système Gambit Scheme, un compilateur et interprète du langage Scheme utilisé pour implanter Termite. Le système Termite Scheme est utilisé pour implémenter les systèmes distribués. Le problème qui est résolu est la diffusion de code compilé entre les nœuds d’un système distribué quand le nœud destination n’a aucune connaissance préalable du code qu’il reçoit. Ce problème est difficile car les nœuds sont hétérogènes, ils ont différentes architectures (x86, ARM). Notre approche permet d’identifier les modules de façon unique dans un contexte dis- tribué. La facilité d’utilisation et la portabilité ont été des facteurs importants dans la conception du système de module. Le mémoire décrit la structure des modules, leur implémentation dans Gambit et leur application. Les qualités du système de module sont démontrées par des exemples et la performance est évaluée expérimentallement. / This thesis presents a module system for Termite Scheme that supports distributed computing. This module system facilitates application modularity and eases code migration between the nodes of a distributed system. This module system also works for developing non-distributed applications. The Gambit Scheme system is used to implement the distributed Termite and the Module system. The problem that is solved is the migration of compiled code between nodes of a distributed system when the receiving node has no prior knowledge of the code. This is a challenging problem because the nodes are not homogenous, they have different architectures (ARM, x86). Our approach uses a naming model for the modules that uniquely identifies them in a distributed context. Both ease of use and portability were important factors in the design of the module system. The thesis describes a module system and how it was integrated into Gambit. The system allows developing distributed modular systems. The features of this system are shown through application examples and the performance is evaluated experimentally.

Cette thèse traite de la conception et implémentationd’un langage de programmation pour les systèmes detraitement de flux en temps réel, comme l’encodagevidéo. Le modèle des réseaux de Kahn est bien adaptéà ce domaine et y est couramment utilisé. Dans cemodèle, un programme consiste en un ensemble deprocessus parallèles communicant à travers des filesmono-producteur, mono-consommateur. La force dumodèle réside en son déterminisme.Les langages synchrones fonctionnels comme Lustresont dédiés aux systèmes embarqués critiques. Un programmeLustre définit un réseau de Kahn synchronequi peut être exécuté avec des files bornées et sans blocage.Cette propriété est garantie par un système detypes dédié, le calcul d’horloge, qui établit une échellede temps globale à un programme. Cette échelle detemps globale est utilisée pour définir les horloges, sé-quences booléennes indiquant pour chaque file, et àchaque pas de temps, si un processus produit ou consommeune donnée. Cette information sert non seulementà assurer la synchronie mais également à générerdu logiciel ou matériel à état fini.Nous proposons et étudions les horloges entières, unegénéralisation des horloges booléennes autorisant desentiers naturels arbitrairement grands. Les horlogesentières décrivent la production ou consommation deplusieurs valeurs depuis une même file au cours d’uninstant. Nous les utilisons pour définir la constructiond’échelle de temps locale, qui peut masquer despas de temps cachés par un sous-programme au contexteenglobant.Ces principes sont intégrés à un calcul d’horloge pourun langage fonctionnel d’ordre supérieur. Nous étudionsses propriétés et prouvons en particulier que lesprogrammes bien typés ne bloquent pas. Nous compilonsles programmes typés vers des circuits numériquessynchrones en adaptant le schéma de générationde code dirigé par les horloges de Lustre. L’informationde typage contrôle certains compromis entre temps etespace dans les circuits générés. / This thesis addresses the design and implementationof a programming language for real-time streaming applications,such as video decoding. The model of Kahnprocess networks is a natural fit for this area and hasbeen used extensively. In this model, a program consistsin a set of parallel processes communicating via singlereader, single writer queues. The strength of the modellies in its determinism.Synchronous functional languages such as Lustre arededicated to critical embedded systems. A Lustre programdefines a synchronous Kahn process network, thatis, which can be executed using finite queues and withoutdeadlocks. This is enforced by a dedicated type system,the clock calculus, which establishes a global timescale throughout a program. The global time scale isused to define clocks: per-queue boolean sequences indicating,for each time step, whether a process producesor consumes a token in the queue. This information isused both for enforcing synchrony and for generatingfinite-state software or hardware.We propose and study integer clocks, a generalizationof boolean clocks featuring arbitrarily big natural numbers.Integer clocks model the production or consumptionof several values from the same queue in the courseof a time step. We then rely on integer clocks to definethe local time scale construction, which may hide timesteps performed by a sub-program from the surroundingcontext.These principles are integrated into a clock calculus fora higher-order functional language. We study its properties,proving among other results that well-typed programsdo not deadlock. We adjust the clock-directedcode generation scheme of Lustre to generate finite-statedigital synchronous circuits from typed programs. Thetyping information controls certain trade-offs betweentime and space in the generated circuits.