Functional logic languages provide a powerful programming paradigm combining the features of functional languages and logic languages. However, current implementations of functional logic languages are complex, slow, or both. This thesis presents a scheme, called the Basic Scheme, for compiling and executing functional logic languages based on non-deterministic graph rewriting. This thesis also describes the implementation and optimization of a prototype of the Basic Scheme. The prototype is simple and performs well compared to other current implementations.

This thesis presents a critical analysis of normalisation by evaluation as a technique for speeding up compilation of typed functional programming languages. Our investigation focuses on the SML.NET compiler and its typed intermediate language MIL. We implement and measure the performance of normalisation by evaluation for MIL across a range of benchmarks. Taking a different approach, we also implement and measure the performance of a graph-based shrinking reductions algorithm for SML.NET. MIL is based on Moggi’s computational metalanguage. As a stepping stone to normalisation by evaluation, we investigate strong normalisation of the computational metalanguage by introducing an extension of Girard-Tait reducibility. Inspired by previous work on local state and parametric polymorphism, we define reducibility for continuations and more generally reducibility for frame stacks. First we prove strong normalistion for the computational metalanguage. Then we extend that proof to include features of MIL such as sums and exceptions. Taking an incremental approach, we construct a collection of increasingly sophisticated normalisation by evaluation algorithms, culminating in a range of normalisation algorithms for MIL. Congruence rules and alpha-rules are captured by a compositional parameterised semantics. Defunctionalisation is used to eliminate eta-rules. Normalisation by evaluation for the computational metalanguage is introduced using a monadic semantics. Variants in which the monadic effects are made explicit, using either state or control operators, are also considered. Previous implementations of normalisation by evaluation with sums have relied on continuation-passing-syle or control operators. We present a new algorithm which instead uses a single reference cell and a zipper structure. This suggests a possible alternative way of implementing Filinski’s monadic reflection operations. In order to obtain benchmark results without having to take into account all of the features of MIL, we implement two different techniques for eliding language constructs. The first is not semantics-preserving, but is effective for assessing the efficiency of normalisation by evaluation algorithms. The second is semantics-preserving, but less flexible. In common with many intermediate languages, but unlike the computational metalanguage, MIL requires all non-atomic values to be named. We use either control operators or state to ensure each non-atomic value is named. We assess our normalisation by evaluation algorithms by comparing them with a spectrum of progressively more optimised, rewriting-based normalisation algorithms. The SML.NET front-end is used to generate MIL code from ML programs, including the SML.NET compiler itself. Each algorithm is then applied to the generated MIL code. Normalisation by evaluation always performs faster than the most naıve algorithms— often by orders of magnitude. Some of the algorithms are slightly faster than normalisation by evaluation. Closer inspection reveals that these algorithms are in fact defunctionalised versions of normalisation by evaluation algorithms. Our normalisation by evaluation algorithms perform unrestricted inlining of functions. Unrestricted inlining can lead to a super-exponential blow-up in the size of target code with respect to the source. Furthermore, the worst-case complexity of compilation with unrestricted inlining is non-elementary in the size of the source code. SML.NET alleviates both problems by using a restricted form of normalisation based on Appel and Jim’s shrinking reductions. The original algorithm is quadratic in the worst case. Using a graph-based representation for terms we implement a compositional linear algorithm. This speeds up the time taken to perform shrinking reductions by up to a factor of fourteen, which leads to an improvement of up to forty percent in total compile time.

Java has recently become a multi paradigm language, with the functional paradigmnow made available alongside the traditional, imperative, one. Programming in thefunctional paradigm may be considered complicated or hard to read, and there maybe concerns that the code it produces may become hard to maintain because ofcomplexity or readability issues. On the other hand, proponents of the functionalparadigm promises smaller amounts of less complex code, as the framework takeson a larger responsibility. This Bachelor’s thesis closely examines the differences be-tween effectively equal code written in functional and imperative Java, respectively,from the aspects of readability, complexity and verbosity, and shows that while codewritten in the functional paradigm is smaller and less complex, it is not harder to read.

Event sourcing has caught the interest of many developers due to desirable features such as an implicit audit log and a simplified database design. This thesis presents a case study with a focus on managing the challenges of versioning and correcting incorrect states. The techniques upcasting and support multiple versions are investigated for handling versioning within event sourcing. Partial and full reversal techniques are applied to investigate the correction of incorrect states. The techniques will be implemented within an event sourcing prototype written in F# to demonstrate how the techniques behave in practice, which can be of use for developers that want to endeavor into event sourcing projects. The results of the study show that all investigated techniques can handle the associated challenges. The comparison of techniques shows the advantages and disadvantages associated with the techniques when implemented in the prototype.

by Chi-keung Luk. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1993. / Includes bibliographical references (leaves 169-174). / Preface --- p.xi / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Programming Languages --- p.2 / Chapter 1.2 --- Programming Paradigms --- p.2 / Chapter 1.2.1 --- What is a programming paradigm --- p.2 / Chapter 1.2.2 --- Which came first? Languages or paradigms? --- p.2 / Chapter 1.2.3 --- Overview of some paradigms --- p.4 / Chapter 1.2.4 --- A spectrum of paradigms --- p.6 / Chapter 1.2.5 --- Mulitparadigm systems --- p.7 / Chapter 1.3 --- The Objectives of this research --- p.8 / Chapter 2 --- "Studies of the object-oriented, the logic and the functional paradigms" --- p.10 / Chapter 2.1 --- The Object-Oriented Paradigm --- p.10 / Chapter 2.1.1 --- Basic components --- p.10 / Chapter 2.1.2 --- Motivations --- p.11 / Chapter 2.1.3 --- Some related issues --- p.12 / Chapter 2.1.4 --- Computational models for object-oriented programming --- p.16 / Chapter 2.2 --- The Functional Paradigm --- p.18 / Chapter 2.2.1 --- Basic concepts --- p.18 / Chapter 2.2.2 --- Lambda calculus --- p.20 / Chapter 2.2.3 --- The characteristics of functional programs --- p.21 / Chapter 2.2.4 --- Practicality of functional programming --- p.25 / Chapter 2.3 --- The Logic Paradigm --- p.28 / Chapter 2.3.1 --- Relations --- p.28 / Chapter 2.3.2 --- Logic programs --- p.29 / Chapter 2.3.3 --- The opportunity for parallelism --- p.30 / Chapter 2.4 --- Summary --- p.31 / Chapter 3 --- A survey of some existing multiparadigm languages --- p.32 / Chapter 3.1 --- Logic + Object-Oriented --- p.33 / Chapter 3.1.1 --- LogiC++ --- p.33 / Chapter 3.1.2 --- Intermission --- p.34 / Chapter 3.1.3 --- Object-Oriented Programming in Prolog (OOPP) --- p.36 / Chapter 3.1.4 --- Communication Prolog Unit (CPU) --- p.37 / Chapter 3.1.5 --- DLP --- p.37 / Chapter 3.1.6 --- Representing Objects in a Logic Programming Language with Scoping Constructs (OLPSC) --- p.39 / Chapter 3.1.7 --- KSL/Logic --- p.40 / Chapter 3.1.8 --- Orient84/K --- p.41 / Chapter 3.1.9 --- Vulcan --- p.42 / Chapter 3.1.10 --- The Bridge approach --- p.43 / Chapter 3.1.11 --- Discussion --- p.44 / Chapter 3.2 --- Functional + Object-Oriented --- p.46 / Chapter 3.2.1 --- PROOF --- p.46 / Chapter 3.2.2 --- A Functional Language with Classes (FLC) --- p.47 / Chapter 3.2.3 --- Common Lisp Object System (CLOS) --- p.49 / Chapter 3.2.4 --- FOOPS --- p.50 / Chapter 3.2.5 --- Discussion --- p.51 / Chapter 3.3 --- Logic + Functional --- p.52 / Chapter 3.3.1 --- HOPE --- p.52 / Chapter 3.3.2 --- FUNLOG --- p.54 / Chapter 3.3.3 --- F* --- p.55 / Chapter 3.3.4 --- LEAF --- p.56 / Chapter 3.3.5 --- Applog --- p.57 / Chapter 3.3.6 --- Discussion --- p.58 / Chapter 3.4 --- Logic + Functional + Object-Oriented --- p.61 / Chapter 3.4.1 --- Paradise --- p.61 / Chapter 3.4.2 --- LIFE --- p.62 / Chapter 3.4.3 --- UNIFORM --- p.63 / Chapter 3.4.4 --- G --- p.64 / Chapter 3.4.5 --- FOOPlog --- p.66 / Chapter 3.4.6 --- Logic and Objects (L&O) --- p.66 / Chapter 3.4.7 --- Discussion --- p.67 / Chapter 4 --- The design of a multiparadigm language I --- p.70 / Chapter 4.1 --- An Object-Oriented Framework --- p.71 / Chapter 4.1.1 --- A hierarchy of classes --- p.71 / Chapter 4.1.2 --- Program structure --- p.71 / Chapter 4.1.3 --- Parametric classes --- p.72 / Chapter 4.1.4 --- Inheritance --- p.73 / Chapter 4.1.5 --- The meanings of classes and methods --- p.75 / Chapter 4.1.6 --- Objects and messages --- p.75 / Chapter 4.2 --- The logic Subclasses --- p.76 / Chapter 4.2.1 --- Syntax --- p.76 / Chapter 4.2.2 --- Distributed inference --- p.76 / Chapter 4.2.3 --- Adding functions and expressions to logic programs --- p.77 / Chapter 4.2.4 --- State modelling --- p.79 / Chapter 4.3 --- The functional Subclasses --- p.80 / Chapter 4.3.1 --- The syntax of functions --- p.80 / Chapter 4.3.2 --- Abstract data types --- p.81 / Chapter 4.3.3 --- Augmented list comprehensions --- p.82 / Chapter 4.4 --- The Semantic Foundation of I Programs --- p.84 / Chapter 4.4.1 --- T1* : Transform functions into Horn clauses --- p.84 / Chapter 4.4.2 --- T2*: Transform object-oriented features into pure logic --- p.85 / Chapter 4.5 --- Exploiting Parallelism in I Programs --- p.89 / Chapter 4.5.1 --- Inter-object parallelism --- p.89 / Chapter 4.5.2 --- Intra-object parallelism --- p.92 / Chapter 4.6 --- Discussion --- p.96 / Chapter 5 --- An implementation of a prototype of I --- p.99 / Chapter 5.1 --- System Overview --- p.99 / Chapter 5.2 --- I-to-Prolog Translation --- p.101 / Chapter 5.2.1 --- Pass 1 - lexical and syntax analysis --- p.101 / Chapter 5.2.2 --- Pass 2 - Class Table Construction and Semantic Checking --- p.101 / Chapter 5.2.3 --- Pass 3 - Determination of Multiple Inheritance Precedence --- p.105 / Chapter 5.2.4 --- Pass 4 - Translation of the directive part --- p.110 / Chapter 5.2.5 --- Pass 5 - Creation of Prolog source code for an I object --- p.110 / Chapter 5.2.6 --- Using expressions in logic methods --- p.112 / Chapter 5.3 --- I-to-LML Translation --- p.114 / Chapter 5.4 --- The Run-time Handler --- p.117 / Chapter 5.4.1 --- Object Management --- p.118 / Chapter 5.4.2 --- Process Management and Message Passing --- p.121 / Chapter 6 --- Some applications written in I --- p.125 / Chapter 6.1 --- Modeling of a State Space Search --- p.125 / Chapter 6.2 --- A Solution to the N-queen Problem --- p.129 / Chapter 6.3 --- Object-Oriented Modeling of a Database --- p.131 / Chapter 6.4 --- A Simple Expert System --- p.133 / Chapter 6.5 --- Summary --- p.138 / Chapter 7 --- Conclusion and future work --- p.139 / Chapter 7.1 --- Conclusion --- p.139 / Chapter 7.2 --- Future Work --- p.141 / Chapter A --- Language manual --- p.146 / Chapter A.1 --- Introduction --- p.146 / Chapter A.2 --- Syntax --- p.146 / Chapter A.2.1 --- The lexical specification --- p.146 / Chapter A.2.2 --- The syntax specification --- p.149 / Chapter A3 --- Classes --- p.152 / Chapter A.4 --- Object Creation and Method Invocation --- p.153 / Chapter A.5 --- The logic Subclasses --- p.155 / Chapter A.6 --- The functional Subclasses --- p.156 / Chapter A.7 --- Types --- p.158 / Chapter A.8 --- Mutable States --- p.158 / Chapter B --- User's guide --- p.160 / Chapter B.1 --- System Calls --- p.160 / Chapter B.2 --- Configuration Parameters --- p.162 / Chapter B.3 --- Errors --- p.163 / Chapter B.4 --- Implementation Limits --- p.164 / Chapter B.5 --- How to install the system --- p.164 / Chapter B.6 --- How to use the system --- p.164 / Chapter B.7 --- How to recompile the system --- p.166 / Chapter B.8 --- Directory arrangement --- p.167 / Chapter C --- List of publications --- p.168 / Bibliography --- p.169

This thesis addresses the problem of automated graphical user interface generation for functional programs. First an analysis of current state in the field of automated GUI generation is performed. Based on the analysis the concept of Functionally Structured User Interface (FSUI) is introduced. Meta-data system for code annotation is then specified for the Clojure programming language and a transformation from this system to FSUI data model is implemented. Finally a graphical layer for displaying the actual interface is implemented in Clojure. Benefits of this approach are demonstrated by proof-of-concept case study.

This dissertation provides the motivation for and evidence in favour of an approach to language extension via dynamic loading of plug-ins. There is a growing realisation that language features are often a superior choice to software libraries for implementing applications. Among the benefits are increased usability, safety and efficiency. Unfortunately, designing and implementing new languages is difficult and time consuming. Thus, reuse of language infrastructure is an attractive implementation avenue. The central question then becomes, what is the best method to extend languages? Much research has focussed on methods of extension based on using features of the language itself such as macros or reflection. This dissertation focuses on a complementary solution: plug-in compilers. In this approach languages are extended at run-time via dynamic extensions to compilers, called plug-ins. Plug-ins can be used to extend the expressiveness, safety and efficiency of languages. However, a plug-in compiler provides other benefits. Plug-in compilers encourage modularity, lower the barrier of entry to development, and facilitate the distribution and use of experimental language extensions. This dissertation describes how plug-in support is added, to both the front and back-end of a compiler, and demonstrates their application through a pair of case studies.

This thesis establishes formal equational properties of multi-stage calculi and related proof techniques that support analyses of staged programs. A key promise of staging is to make programs efficient without destroying clarity, thereby reducing the likelihood of bugs. However, few publications rigorously verify that their staged programs indeed behave as intended. In fact, little is known about how staged programs can be verified, or what correctness issues staging introduces. To solve this problem, I show a reduction of the correctness of a staged program to that of an unstaged program. This reduction not only clarifies the effects of staging on program behavior but also eases verification, as unstaged programs are more susceptible to existing reasoning techniques. I also demonstrate that important single-stage reasoning techniques apply to staged programs. These techniques are useful for establishing side conditions for the reduction and for discovering or validating further reasoning principles. / NSF grant CCF-0747431

Establishing the termination of programs is a fundamental problem in the field of software verification. For transformational programs, termination is used to extend partial correctness to total correctness. For reactive systems, termination reasoning is used to establish liveness properties. In the context of theorem proving, termination is used to establish the consistency of definitional axioms and to automate proofs by induction. Of course, termination is an undecidable problem, as Turing himself proved. However, the question remains: how automatic can a general termination analysis be in practice? In this dissertation, we develop two new general frameworks for reasoning about termination and demonstrate their effectiveness in automating the task of proving termination in the domain of applicative first-order functional languages. The foundation of the first framework is the development of the first known complete set of algorithms for ordinal arithmetic over an ordinal notation. We provide algorithms for ordinal ordering ($<$), addition, subtraction, multiplication, and exponentiation on the ordinals up to epsilon-naught. We prove correctness and complexity results for each algorithm. We also create a library for automating arithmetic reasoning over epsilon-naught in the ACL2 theorem proving system. This ordinal library enables new termination proofs that were previously not possible in previous versions of ACL2. The foundation of the second framework is an algorithm for fully automating termination reasoning with no user assistance. This algorithm uses a combination of theorem proving and static analysis to create a Calling Context Graph (CCG), a novel abstraction that captures the looping behavior of the program. Calling Context Measures (CCMs) are then used to prove that no infinite path through the CCG can be an actual computation of the program. We implement this algorithm in the ACL2, and empirically evaluate its effectiveness on the regression suite, a collection of over 11,000 user-defined functions from a wide variety of applications.

Thesis (Ph.D.)--University of Melbourne, Dept. of Information Systems and Faculty of Architecture, Building and Planning 2006. / Typescript. Includes bibliographical references (leaves 261-275).