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.

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.

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.

<p>This thesis gives a partial answer to the question: “Can type systems detect modeling errors in scientific computing, particularly for inverse problems derived from physical models?” by considering, in detail, the major aspects of inverse problems in Magnetic Resonance Imaging (MRI). We define a type-system that can capture all correctness properties for MRI inverse problems, including many properties that are not captured with current type-systems, e.g., frames of reference. We implemented a type-system in the Haskell language that can capture the errors arising in translating a mathe- matical model into a linear or nonlinear system, or alternatively into an objective function. Most models are (or can be approximated by) linear transformations, and we demonstrate the feasibility of capturing their correctness at the type level using what is arguably the most difficult case, the (discrete) Fourier transformation (DFT). By this, we mean that we are able to catch, at compile time, all known errors in ap- plying the DFT. The first part of this thesis describes the Haskell implementation of vector size, physical units, frame of reference, and so on required in the mathemat- ical modelling of inverse problems without regularization. To practically solve most inverse problems, especially those including noisy data or ill-conditioned systems, one must use regularization. The second part of this thesis addresses the question of defining new regularizers and identifying existing regularizers the correctness of which (in our estimation) can be formally verified at the type level. We describe such Bayesian regularization schemes based on probability theory, and describe a novel simple regularizer of this type. We leave as future work the formalization of such regularizers.</p> / Master of Science (MSc)

Le comportement non-linéaire des sols observé lors des mouvements sismiques forts est maintenant bien établi et le déploiement des puits accélérométriques a permis des analyses détaillés de la propagation des ondes ainsi qu'une évaluation quantitative des paramètres physiques tels que la vitesse de cisaillement et de compression des ondes et les facteurs d'amortissements en fonction de la déformation. En dépit du nombre grandissant d'´etudes sur ce phénomène, sa connaissance est encore récente et les recherches sur les données de puits accélérométriques restent une étape importante vers la compréhension du comportement complexe in-situ des sédiments soumis à des mouvements sismiques forts. L'objectif de ces travaux est triple. Premièrement, un code d'inversion par algorithme génétique est développé afin d'inverser des données de puits accélérométriques via la théorie des matrices de propagation de Thomson- Haskell. Cette technique nous permet dans un premier temps de valider la structure en une dimension (1D) (e.g., vitesse des ondes de cisaillement, facteurs d' amortissements) d'un puits accélérométrique dans le domaine linéaire et dans un second temps de mettre en évidence de manière quantitative le comportement non-linéaire des sédiments lors du séisme de Fukuoka, 2005, Japon. Deuxièmement, les résultats de l'inversion sont utilisés pour tester des lois de comportement simples et avancées en utilisant la Méthode des Eléments Finis. Les résultats montrent clairement que l'hypothèse bilinéaire de la loi de comportement simple produit des séries temporelles non réalistes en vitesse et en accélération. L'utilisation d'une loi de comportement avancée mène à de meilleurs résultats, cependant, le nombre de paramètres ajustables pour obtenir des résultats consistants avec l'observation est un obstacle inévitable. Troisièmement, afin d'étendre l'étude des effets de site à des dimensions supérieures, des codes 2D et 3D de la Méthode en Eléments Spectraux sont développés et validés en comparant leurs résultats dans le domaine linéaire avec ceux obtenus théoriquement ou via d'autres méthodes numériques.

The aim of this thesis is to research how the functional paradigm can be used for hardware acceleration with an emphasis on data-parallel tasks. The level of abstraction of the traditional hardware description languages, such as VHDL or Verilog, is becoming to low. High-level languages from the domains of software development and modeling, such as C/C++, SystemC or MATLAB, are experiencing a boom for hardware description on the algorithmic or behavioral level. Functional Languages are not so commonly used, but they outperform imperative languages in verification, the ability to capture inherent paralellism and the compactness of code. Data-parallel task are often accelerated on FPGAs, GPUs and multicore processors. In this thesis, we use a library for general-purpose GPU programs called Accelerate and extend it to produce VHDL. Accelerate is a domain-specific language embedded into Haskell with a backend for the NVIDIA CUDA platform. We use the language and its frontend, and create a new backend for high-level synthesis of circuits in VHDL.

The purpose of this thesis is to show a method, that would transform given Turing machine into propagating scattered context grammar, which language contains all valid computational histories of that particular Turing machine. Afterwards this thesis deals with questions arising from existence of such algorithm, especially in regards to the current knowledge about power of propagating scattered context grammars. Practical examples and implementation of proposed algorithm is also part of this thesis.

In this thesis we see two new approaches to compose tree transducers and more general to fuse functional programs. The first abroach is based on initial algebras. We prove a new variant of the acid rain theorem for mutually recursive functions where the build function is substituted by a concrete functor. Moreover, we give a symmetric form (i.e. consumer and producer have the same syntactic form) of our new acid rain theorem where fusion is composition in a category and thus in particular associative. Applying this to compose top-down tree transducers yields the same result (on a syntactic level) as the classical top-down tree transducer composition. The second approach is based on free monads and monad transformers. In the same way as monoids are used in the theory of character string automata, we use monads in the theory of tree transducers. We generalize the notion of a tree transducer defining the monadic transducer, and we prove an according fusion theorem. Moreover, we prove that homomorphic monadic transducers are semantically equivalent. The latter makes it possible to compose syntactic classes of tree transducers (or particular functional programs) by simply composing endofunctors.

In this thesis we see two new approaches to compose tree transducers and more general to fuse functional programs. The first abroach is based on initial algebras. We prove a new variant of the acid rain theorem for mutually recursive functions where the build function is substituted by a concrete functor. Moreover, we give a symmetric form (i.e. consumer and producer have the same syntactic form) of our new acid rain theorem where fusion is composition in a category and thus in particular associative. Applying this to compose top-down tree transducers yields the same result (on a syntactic level) as the classical top-down tree transducer composition. The second approach is based on free monads and monad transformers. In the same way as monoids are used in the theory of character string automata, we use monads in the theory of tree transducers. We generalize the notion of a tree transducer defining the monadic transducer, and we prove an according fusion theorem. Moreover, we prove that homomorphic monadic transducers are semantically equivalent. The latter makes it possible to compose syntactic classes of tree transducers (or particular functional programs) by simply composing endofunctors.