Time filter

Source Type

Oliveira B.C.D.S.,National University of Singapore | Loh A.,Well Typed LLP
PEPM 2013 - Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, Co-located with POPL 2013 | Year: 2013

This paper presents a representation for embedded domain specific languages (EDSLs) using abstract syntax graphs (ASGs). The purpose of this representation is to deal with the important problem of defining operations that require observing or preserving sharing and recursion in EDSLs in an expressive, yet easy-to-use way. In contrast to more conventional representations based on abstract syntax trees, ASGs represent sharing and recursion explicitly as binder constructs. We use a functional representation of ASGs based on structured graphs, where binders are encoded with parametric higher-order abstract syntax. We show how adapt to this representation to well-typed ASGs. This is especially useful for EDSLs, which often reuse the type system of the host language. We also show an alternative class-based encoding of (well-typed) ASGs that enables extensible and modular well-typed EDSLs while allowing the manipulation of sharing and recursion. Copyright © 2013 ACM.

Swierstra W.,University Utrecht | Loh A.,Well Typed LLP
Onward! 2014 - Proceedings of the 2014 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software, Part of SPLASH 2014 | Year: 2014

As software becomes increasingly complex, software configuration management is becoming ever more important. This paper shows how logics for reasoning about mutable state, such as separation logic, can also be used to give semantics for version control systems. By applying these ideas from the programming language research community, developers may reason formally about the broader software development process.

Loh A.,Well Typed LLP | Magalhaes J.P.,University Utrecht
WGP'11 - Proceedings of the 2011 ACM SIGPLAN Workshop on Generic Programming | Year: 2011

Much has been said and done about generic programming approaches in strongly-typed functional languages such as Haskell and Agda. Different approaches use different techniques and are better or worse suited for certain uses, depending on design decisions such as generic view, universe size and complexity, etc. We present a simple and intuitive yet powerful approach to generic programming in Agda using indexed functors. We show a universe incorporating fixed points that supports composition, indexing, and isomorphisms, and generalizes a number of previous approaches to generic programming with fixed points. Our indexed functors come with a map operation which obeys the functor laws, and associated recursion morphisms. Albeit expressive, the universe remains simple enough to allow defining standard recursion schemes as well as decidable equality. As for type-indexed datatypes, we show how to compute the type of one-hole contexts and define the generic zipper. Copyright © 2011 ACM.

Magalhaes J.P.,University Utrecht | Loh A.,Well Typed LLP
Electronic Proceedings in Theoretical Computer Science, EPTCS | Year: 2012

Datatype-generic programming increases program abstraction and reuse by making functions operate uniformly across different types. Many approaches to generic programming have been proposed over the years, most of them for Haskell, but recently also for dependently typed languages such as Agda. Different approaches vary in expressiveness, ease of use, and implementation techniques. Some work has been done in comparing the different approaches informally. However, to our knowledge there have been no attempts to formally prove relations between different approaches. We thus present a formal comparison of generic programming libraries. We show how to formalize different approaches in Agda, including a coinductive representation, and then establish theorems that relate the approaches to each other. We provide constructive proofs of inclusion of one approach in another that can be used to convert between approaches, helping to reduce code duplication across different libraries. Our formalisation also helps in providing a clear picture of the potential of each approach, especially in relating different generic views and their expressiveness.

Magalhaes J.P.,University of Oxford | Loh A.,Well Typed LLP
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2015

Generic programming (GP) is a form of abstraction in programming languages that serves to reduce code duplication by exploiting the regular structure of algebraic datatypes. Several different approaches to GP in Haskell have surfaced, giving rise to the problem of code duplication across GP libraries. Given the original goals of GP, this is a rather unfortunate turn of events. Fortunately, we can convert between the different representations of each approach, which allows us to “borrow” generic functions from different approaches, avoiding the need to reimplement every generic function in every single GP library. In previous work we have shown how existing GP libraries relate to each other. In this paper we go one step further and advocate “hierarchical GP”: through proper design of different GP approaches, each library can fit neatly in a hierarchy, greatly minimizing the amount of supporting infrastructure necessary for each approach, and allowing each library to be specific and concise, while eliminating code duplication overall. We introduce a new library for GP in Haskell intended to sit at the top of the “GP hierarchy”. This library contains a lot of structural information, and is not intended to be used directly. Instead, it is a good starting point for generating generic representations for other libraries. This approach is also suitable for being the only library with native compiler support; all other approaches can be obtained from this one by simple conversion of representations in plain Haskell code. © Springer International Publishing Switzerland 2015

Magalhaes J.P.,University of Oxford | Loh A.,Well Typed LLP
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2014

Generic programming (GP) is a form of abstraction in programming languages that serves to reduce code duplication by exploiting the regular structure of algebraic datatypes. Over the years, several different approaches to GP in Haskell have surfaced. These approaches are often similar, but certain differences make them particularly well-suited for one specific domain or application. As such, there is a lot of code duplication across GP libraries, which is rather unfortunate, given the original goals of GP. To address this problem, we define conversions from one popular GP library representation to several others. Our work unifies many approaches to GP, and simplifies the life of both library writers and users. Library writers can define their approach as a conversion from our library, obviating the need for writing meta-programming code for generation of conversions to and from the generic representation. Users of GP, who often struggle to find "the right approach" to use, can now mix and match functionality from different libraries with ease, and need not worry about having multiple (potentially inefficient and large) code blocks for generic representations in different approaches. © 2014 Springer International Publishing.

Wang M.,Chalmers University of Technology | Gibbons J.,University of Oxford | Wu N.,Well Typed LLP
Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP | Year: 2011

A bidirectional transformation is a pair of mappings between source and view data objects, one in each direction. When the view is modified, the source is updated accordingly. The key to handling large data objects that are subject to relatively small modifications is to process the updates incrementally. Incrementality has been explored in the semi-structured settings of relational databases and graph transformations; this flexibility in structure makes it relatively easy to divide the data into separate parts that can be transformed and updated independently. The same is not true if the data is to be encoded with more general-purpose algebraic datatypes, with transformations defined as functions: dividing data into welltyped separate parts is tricky, and recursions typically create interdependencies. In this paper, we study transformations that support incremental updates, and devise a constructive process to achieve this incrementality. Copyright© 2011 ACM.

Coutts D.,Well Typed LLP | Loh A.,Well Typed LLP
Computing in Science and Engineering | Year: 2012

Haskell is a modern, functional programming language with an interesting story to tell about parallelism: rather than using concurrent threads and locks, Haskell offers a variety of libraries that enable concise, high-level parallel programs with results that are guaranteed to be deterministic (independent of the number of cores and the scheduling being used). This Web extra contains Haskell code, as discussed in the article. © 2011 IEEE.

De Vries E.,Well Typed LLP | Loh A.,Well Typed LLP
WGP 2014 - Proceedings of the 2014 ACM SIGPLAN Workshop on Generic Programming | Year: 2014

We introduce the sum-of-products (SOP) view for datatype-generic programming (in Haskell). While many of the libraries that are commonly in use today represent datatypes as arbitrary combinations of binary sums and products, SOP reflects the structure of datatypes more faithfully: each datatype is a single n-ary sum, where each component of the sum is a single n-ary product. This representation turns out to be expressible accurately in GHC with today's extensions. The resulting list-like structure of datatypes allows for the definition of powerful high-level traversal combinators, which in turn encourage the definition of generic functions in a compositional and concise style. A major plus of the SOP view is that it allows to separate function-specific metadata from the main structural representation and recombining this information later. © 2014 ACM.

De Vries E.,Well Typed LLP
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2013

Uniqueness typing and affine (or linear) typing are dual type systems. Uniqueness gives a guarantee that an term has not been shared, while affinity imposes a restriction that a term may not be shared. We show that we can unify both concepts through polymorphism. © 2013 Springer-Verlag Berlin Heidelberg.

Loading Well Typed LLP collaborators
Loading Well Typed LLP collaborators