Cette thèse est consacrée aux algorithmes de morphologie mathématique qui peuvent considérer les pixels d'une image comme un flux de données. Nous allons démontrer qu'un grand nombre d'algorithmes de morphologie mathématique peuvent être décrits comme un flux de données traversant des unités d'exécution. Nous verrons que cette approche peut aussi fonctionner sur des processeurs génériques possédant un jeu d'instructions multimédia ou sur des cartes graphiques. Pour décrire les algorithmes en flux de données, nous proposons d'utiliser le langage fonctionnel Haskell, ce qui nous permettra de décrire les briques de base de la construction des algorithmes de morphologie mathématique. On applique ces briques dans la description des algorithmes les plus couramment utilisés (dilatation/érosion, opérations géodésiques, fonction distance et nivellements) ce qui facilitera le portage de ces algorithmes sur plusieurs plate-formes. Nous proposons pour la construction des algorithmes morphologiques un mode d'exécution original par macro blocs et nous étudions en profondeur la transposition de cette idée aux architectures SIMD. Nous montrons que l'utilisation des macro blocs est intéressante pour les architectures multimédia et nous montrons également que les algorithmes morphologiques proposés dans cette thèse atteignent de meilleures performances que les implémentations standard. Un nouveau champ s'ouvre ainsi aux algorithmes développés dans les applications de traitement d'images en temps réel. Cette thèse explore également les processeurs graphiques et démontre sur des résultats expérimentaux qu'ils sont, dès à présent, assez performants pour concurrencer les processeurs généraux.

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.

Submitted by Luiz Felipe Barbosa (luiz.fbabreu2@ufpe.br) on 2015-03-09T13:43:25Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO Francisco Miranda Soares da Silva Neto.pdf: 1968720 bytes, checksum: 60383d7751d95b545cae9a16a83f611c (MD5) / Made available in DSpace on 2015-03-09T13:43:26Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO Francisco Miranda Soares da Silva Neto.pdf: 1968720 bytes, checksum: 60383d7751d95b545cae9a16a83f611c (MD5) Previous issue date: 2014-02-27 / In recent years, the diminishing rate with which we can increase the amount of transistors in a processor core has slowed down the increase of computers’ power. Moore’s Law appears to be drawing to an end. With it, the assumption that software written today will be more efficiently executed in the future simply due to processors’ evolution is being challenged. On the other hand, parallel applications can still be made more efficient by distributing work among different processors to be executed at the same time, thus reducing overall execution time. To enable parallelization, we must have multiple processor cores. This has led to the popularization of multicore architectures. However, writing parallel applications is not trivial. A program must be either written from the start to be executed in parallel, or later adapted for parallel execution. The programmer has the error-prone task of parallelizing the application through use of concurrency and parallelism constructs. Locking, the most common concurrency option, presents risks for inexperienced programmers, such as the famous Deadlock and Livelock problems. As we move from single core architectures to multicore, our programming languages need to make it easier for the programmers to use concurrency. Many researchers have pointed at Software Transactional Memory (STM) as an answer to that issue, as it is a lock-free, abstract way to guarantee isolated access to shared resources. But adapting for STM a program that uses lock is not simple. Besides being an error-prone task, technical details of the language might require special attention to preserve the program’s behavior. In this dissertation, we propose a set of program transformations for concurrency constructs in Haskell, a purely functional programming language. They may be used to refactor a program’s existing locks into transactional constructs from Haskell’s STM implementation. This allows a programmer to gain the benefits of working on STM even for programs which were already developed using locks. Each transformation is accompanied by execution examples and a discussion on its ability to preserve program behavior. We also present a supporting study, in which a controlled experiment was used to evaluate the benefits of locks or STM for the development of Haskell programs. Although subjects’ opinions tended to favor lock-based concurrency, those which used STM overall committed significantly fewer mistakes and required on average 12% less time to finish their assignments. / Recentemente, a queda na taxa de crescimento da quantidade de transístores integráveis em processadores tem desacelerado o crescimento de poder computacional. A lei de Moore parece aproximar-se de seu fim. Com isso, é desafiada a premissa de que software escrito hoje terá melhor desempenho no futuro simplesmente devido à evolução dos processadores. Ainda assim, aplicações paralelas ainda podem se tornar mais eficientes ao se distribuir trabalho entre diferentes processadores para execução simultânea. Para permitir a paralelização, são necessários múltiplos núcleos de processamento, o que tem levado à popularização de arquiteturas multinúcleo. Entretanto, a escrita de aplicações paralelas não é trivial. Deve-se escrever um programa para execução paralela desde sua concepção, ou adaptá-lo posteriormente para execução paralela. O programador tem a difícil tarefa de paralelização da aplicação através do uso de construções de concorrência e paralelismo. Travas, a mais comum opção para concorrência, apresentam riscos para programadores inexperientes, tais quais os famosos problemas de Deadlock e Livelock. Ao adaptarem-se de arquiteturas de um único núcleo para as de multinúcleo, as linguagens de programação precisam facilitar o uso de concorrência para os programadores. Muitos pesquisadores têm indicado Memória Transacional em Software (STM, do inglês Software Transactional Memory) como a resposta para esse problema, por ser uma forma abstrata e não bloqueante para garantia de acesso isolado a recursos compartilhados. Mas adaptar para STM programas que usam travas não é simples. Além de ser uma atividade propensa a erros, detalhes técnicos da linguagem podem requerer cuidados para se preservar o comportamento do programa. Nesta dissertação, é proposto um conjunto de transformações de programas para construções de concorrência em Haskell, uma linguagem de programação puramente funcional. Elas podem ser usadas para refatorar travas de um programa para uso de construções transacionais da implementação de STM em Haskell. Isso permite ao programador aproveitar os benefícios do trabalho com STM mesmo para programas já desenvolvidos com uso de travas. Cada transformação é acompanhada de exemplos de execução e uma discussão sobre sua capacidade de preservar o comportamento do programa. Também é apresentado um estudo de apoio, no qual um experimento controlado foi usado para avaliar os benefícios do uso de travas ou STM no desenvolvimento de programas em Haskell. Apesar das opiniões dos participantes terem favorecido o uso de travas, aqueles que usaram STM cometeram em geral menos erros e em média precisaram de 12% a menos de tempo para terminar suas tarefas.

Functional Reactive Programming (FRP) offers a declarative way to express reactive systems such as animations, user interfaces and games. Various topics related to FRP like optimization, generalization and debugging were studied. However, the use of FRP in distributed systems has not been investigated extensively. Focused on the use of the Dunai FRP library implemented in the Haskell programming language, the aim of this thesis is to develop and evaluate a way to apply FRP to distributed systems. A library is implemented to extend Dunai with means to create distributed systems. There is support for the Client/Server network architectural model and algorithms to synchronize applications across a network. As the synchronization of distributed systems has been a topic of research for decades, this thesis explores whether developed ideas, such as Time Warp (Jefferson, 1985), can be expressed in FRP. Additionally, Client Side Prediction (Bernier, 2001) and Dead Reckoning (DIS Steering Committee, 1994) are used to predict server reactions on client-side. An exemplary application demonstrates the implementation. The application is then evaluated in a performance test and a user test. TimeWarp synchronization has a significant impact on performance. Despite this, the application is playable up to a latency of 100 ms. The result of Dead Reckoning is acceptable, whereas Client Side Prediction is not usable. The thesis shows that the developed way can be used to run FRP on distributed systems. Further work should focus the performance to enable more complex applications. Moreover, Dead Reckoning can be improved to a smoother result. Non-trivial changes are necessary to make Client Side Prediction usable.:1 Introduction ... 1 2 Functional Reactive Programming ... 4 2.1 The Arrow Type Class ... 5 2.2 The Dunai FRP Library ... 7 2.2.1 Monadic Stream Functions ... 7 2.2.2 Combining Monads ... 8 2.2.3 Monads in Monadic Stream Functions ... 9 2.3 The BearRiver FRP Library ... 10 2.4 Executing FRP ... 11 3 Synchronization of Distributed Systems ... 13 3.1 Distributed Systems ... 13 3.2 Consistency of Distributed Systems ... 14 3.3 Client/Server Architecture ... 15 3.4 Time Warp Synchronization ... 16 3.5 Dead Reckoning ... 17 3.6 Client Side Prediction ... 19 4 Cloud Haskell ... 21 4.1 Exchanging Messages ... 22 4.2 Fault Tolerance ... 23 4.3 The Cloud Haskell Platform ... 23 5 Concept ... 25 5.1 Concept of the Implemented Library ... 25 5.2 Concept of the Sample Application ... 27 5.3 Functional Requirements ... 28 5.4 Non-Functional Requirements ... 30 6 Implementation ... 32 6.1 Client/Server Architecture ... 33 6.1.1 Establishing Connections between Clients and Servers ... 33 6.1.2 Distributed Execution of FRP ... 35 6.1.3 Implementation of Servers ... 36 6.1.4 Implementation of Clients ... 38 6.2 Time Warp Synchronization ... 39 6.2.1 Rollbacks of Monadic Stream Functions ... 39 6.2.2 Executing FRP using Time Warp Synchronization ... 41 6.3 Dead Reckoning ... 45 6.4 Client Side Prediction ... 46 7 Evaluation ... 48 7.1 Evaluation of Functional Requirements ... 48 7.2 Concept of the Performance Test ... 52 7.3 Concept of the User Test ... 53 7.4 Results of the Performance Test ... 54 7.5 Results of the User Test ... 56 8 Summary ... 60 Bibliography ... A Listings ... M List of Figures ... O List of Tables ... P Glossary .. Q Abbreviations ... U

Mathematical optimization has many applications in operations research, image processing, and machine learning, demanding not only computational efficiency but also convenience and correctness in constructing complex models. In this work, we introduce HashedExpression, an open-source algebraic modeling lan- guage (AML) that allows users to express unconstrained, box-constrained, and scalar-expressions-constrained optimization problems, aimed at embeddability, type-safety, and high-performance through symbolic transformation and code generation. Written in Haskell, a statically-typed, purely functional program- ming language, HashedExpression places a great emphasis on modeling correct- ness by providing users with a type-safe, correct-by-construction interface that uses Haskell type-level programming to express constraints on correctness which the compiler uses to flag many modelling errors as type errors (at compile time). We show how type-safety can be added in steps, first matching expressions’ shape and then associated physical units. The library implements symbolic ex- pressions with a hashed indexing scheme to implement common subexpression elimination (CSE). It abstracts away details of the underlying lookup table via monadic type class instances. We explain how using symbolic expressions with CSE enables performance-enhance transformations and automatic computation of derivatives without the issue of “expression swelling”. For high-performance purposes, we generate low-level C/C++ code for symbolic expressions and pro- vide bindings to open-source optimization solvers such as Ipopt or L-BFGS-B. We explain how this architecture lays the groundwork for future work on par- allelization including SIMDization and targetting multi-core CPUs and GPUs, and other hardware acceleration. / Thesis / Master of Science (MSc)

The feeling of a narcotic cannot be put to words, just as the sensation one receives from her or his favorite artwork is impossible to record. Equally, both these delicacies of modern existence must be sought out. The user/viewer only gets a tiny taste and must therefore keep coming back for more. Utopia may be an unrealistic construction of culture, but I would posit the idea the both narcotics and art strive to give us just that – however tiny a taste. This paper addresses the intersections of visual art, drugs, anti-hero worship and contemporary representations of Romanticism throughout the American body politic.

La Programmation Orientée Langage est un paradigme de programmation qui tente, par la technique de méta-programmation, de changer les habitudes des développeurs de systèmes informatiques en leur permettant de "travailler en termes de concepts et notions du problème à résoudre, au lieu d'être toujours obligés de traduire leurs idées aux notions qu'un langage généraliste est capable de comprendre" (Ward et Sergey). Le développement de logiciels passe de ce fait par la conception de langages dédiés : on définit un ou plusieurs langages qui capturent les caractéristiques du domaine étudié, puis on écrit les applications visées en utilisant ces langages. Dans cette thèse, nous proposons une démarche méthodologique de développement logiciel reposant sur ce concept. Il s'agit de conduire la même démarche méthodologique au niveau des langages que ce qui est classiquement fait au niveau des composants logiciels. En l'occurrence, nous utilisons le formalisme des grammaires attribuées pour tenter de répondre à la question suivante : comment peut-on créer de nouveaux langages par composition de langages réutilisables existants ? Nous tirons profit de leur traduction en algèbres de combinateurs fonctionnels pour définir des spécifications exécutables de langages dédiés (vus comme composants logiciels), plongés dans le langage fonctionnel pur Haskell. \' partir d'exemples significatifs d'extension et de réutilisation de langages dédiés (par stratification de ceux-ci, ou par changement de monade), nous proposons un typage de langages dédiés en vue de leur assemblage et leur réutilisation. Pour illustrer cette démarche, nous décrivons un langage dédié (bibliothèque de combinateurs) pour l'édition de documents structurés. Un document y est représenté par un zipper attribué, une structure arborescente localisable, représentant un arbre et son contexte, et caractérisée par une grammaire attribuée. L'édition consiste alors à la modification interactive de cette structure ; ce qui entraîne une réévaluation totale ou partielle des attributs. L'édition peut aussi être réalisée à travers une vue abstraite obtenue par projection de la structure concrète. Ce qui pose le problème de \textit, un problème familier de la communauté des bases de données, auquel nous donnons une solution grâce à nos combinateurs d'éditeurs.

We discuss the development of a number of algorithms and techniques to allow object oriented virtual machines to support many of the features needed by functional and other higher level languages. These features include non-strict evaluation, partial function application, higher ranked and higher kinded types. To test the mechanisms that we have developed we have also produced a compiler to allow the functional language Haskell to be compiled to a native executable for the Common Language Runtime. This has allowed us to demonstrate that the techniques we have developed are practically viable.

Title: Functional Data Structures and Algorithms Author: Milan Straka Institute: Computer Science Institute of Charles University Supervisor of the doctoral thesis: doc. Mgr. Zdeněk Dvořák, Ph.D, Computer Science Institute of Charles University Abstract: Functional programming is a well established programming paradigm and is becoming increasingly popular, even in industrial and commercial appli- cations. Data structures used in functional languages are principally persistent, that is, they preserve previous versions of themselves when modified. The goal of this work is to broaden the theory of persistent data structures and devise efficient implementations of data structures to be used in functional languages. Arrays are without any question the most frequently used data structure. Despite being conceptually very simple, no persistent array with constant time access operation exists. We describe a simplified implementation of a fully per- sistent array with asymptotically optimal amortized complexity Θ(log log n) and especially a nearly optimal worst-case implementation. Additionally, we show how to effectively perform a garbage collection on a persistent array. The most efficient data structures are not necessarily based on asymptotically best structures. On that account, we also focus on data structure...

Prosoft é um grupo de pesquisa do Instituto de Informática da UFRGS, desenvolvido pelo grupo de pesquisa homônimo e coordenado pelo Professor Daltro José Nunes. O objetivo do projeto é desenvolver um ambiente de desenvolvimento de software completo, o Ambiente Prosoft, que é baseado nos conceitos de Modelos, Cálculo Lambda, Tipos Abstratos de Dados e Orientação a Objetos. Um dos componentes do Ambiente Prosoft é sua linguagem de especificação algébrica: o Prosoft Algébrico. Apesar de ser base e tema de diversos trabalhos no grupo de pesquisa Prosoft, o Prosoft Algébrico não tem sua semântica devidamente definida. Os trabalhos desenvolvidos até agora foram baseados em noções operacionais, e apresentam diferentes interpretações do Prosoft Algébrico. Esta dissertação apresenta uma especificação de semântica denotacional para o Prosoft Algébrico, compreendendo, entre outras características, sua primitiva de comunicação entre tipos de dados, chamada ICS, e sua notação gráfica para representação de instanciação de tipos abstratos de dados. Essa dissertação apresenta também um estudo sobre prototipação semântica usando a linguagem de programação Haskell. O conceito de Literate Programming e a proximidade entre Cálculo Lambda e Haskell foram cruciais no rápido desenvolvimento de uma implementação protótipo do Prosoft Algébrico, baseada na sua semântica especificada. As principais contribuições dessa dissertação incluem: uma interpretação precisa e sem ambiguidades do Prosoft Algébrico, através da especificação da sua semântica; a definição de semântica para a ICS, um conceito único (até o limite do nosso conhecimento) que fornece um mecanismo de passagem de mensagens entre tipos de dados algébricos; uma implementação protótipo do Prosoft Algébrico, que pode realmente ser utilizada para experimentar e testar a definição da linguagem e a especificação da semântica do Prosoft Algébrico; resultados sobre prototipação semântica de especificações tanto de semântica denotacional quanto de semântica operacional usando a linguagem de programação Haskell para desenvolvimento rápido de protótipos de linguagens baseados na sua semântica. Como grande parte do desenvolvimento do Ambiente Prosoft é realizado através de projetos de cooperação internacional e essa dissertação irá influenciar fortemente o seu desenvolvimento futuro, o texto foi escrito em inglês para facilitar a troca de informação entre o grupo Prosoft e seus parceiros estrangeiros. / Prosoft is a research project at Instituto de Informática da UFRGS, developed by the research group with the same name and coordinated by Professor Daltro José Nunes. The project’s goal is to develop a full software development environment, the Prosoft Environment, based on the concepts of Models, Lambda Calculus, Abstract Data Types and Object orientation. One of the components of the Prosoft Environment is its algebraic specification language: Algebraic Prosoft. Although being the basis and theme of several works in the Prosoft research group, Algebraic Prosoft doesn’t have its semantics properly defined. Works done up to now were based on operational notions and presented different interpretations of Algebraic Prosoft. This thesis presents a denotational semantics specification for Algebraic Prosoft, comprising, among other features, its “inter-data type” communication primitive, called ICS, and its graphical notation for representing instantiations of abstract data types. This thesis also presents a study of semantic prototyping using the Haskell programming language. The concept of Literate Programing and the proximity between lambda calculus and Haskell were crucial to the rapid development of a prototype implementation of Algebraic Prosoft, based on its specified semantics. This thesis’ main contributions include: a precise and unambiguous interpretation of Algebraic Prosoft, through a semantics specification; the definition of semantics to the ICS, a unique (to the best of our knowledge) concept that provides a messagepassing mechanism between algebraic data types; a prototype implementation of Algebraic Prosoft, which can actually be used to experiment and test the Algebraic Prosoft language definition and semantics specification; results regarding semantics prototyping of both denotational and operational semantics specifications using the Haskell programming language for rapid development of semantics-based prototypes of languages. Since a large portion of Prosoft Environment’s development is done through international cooperation projects and this thesis will strongly influence its future development, the text was written in English in order to facilitate the information exchange between the Prosoft research group and its foreign partners.