Papers for

functional programming developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Symbolic execution in Haskell sped up with configurable embeddings

SymFC: Configurable Semantics for All Paths Symbolic Execution in Haskell via Embeddings

Abstract: Lightweight methods like QuickCheck have proven to be successful in functional languages and beyond, as they let users specify properties as Boolean functions directly in code. We can replicate some of their benefits for (bounded) proofs via symbolic execution. If we can execute arbitrary functions symbolically, we can specify properties just as easily. Unfortunately, existing symbolic execution tools for Haskell are restricted to a subset of the language that excludes many real-world applications like IO; they also have a hard time scaling to larger programs, making them a poor fit for general purpose lightweight verification. One reason behind these limitations is that existing techniques only offer fixed symbolic semantics for SMT base types. This makes it hard to cover more programming constructs and libraries; it also makes it difficult to fine-tune symbolic representations for better performance. We present SymFC, a new symbolic execution method for Haskell that offers configurable semantics via embeddings. An embedding of a function in SymFC is just another Haskell function that can use arbitrary code, as well as SMT primitives. Embeddings make it easy to support new programming constructs and fine-tune symbolic representations for speed. To integrate embeddings into Haskell's type system, we make use of Haskell's coercions, which let us transparently convert between a Haskell type and the type of its embedding. We realize embeddings in SymFC, an all-paths symbolic execution engine for Haskell, which lets us symbolically represent arbitrary types and values in GHC core. We implement SymFC as a GHC plugin, and evaluate it by checking properties of Haskell's container library, and the iproute library. We build embeddings for IORef, Haskell's Ptr/ForeignPtr interface, and the hardware library Clash, and our evaluation reports a 6.25x speedup on G2's own benchmarks.

Thu 5 NovProgramming Languages
The gist
Checking programs automatically for bugs or errors can be slow and limited in Haskell because existing tools struggle with many language features and real-world code. The authors created SymFC, which lets symbolic execution be customized using ordinary Haskell functions called embeddings. These embeddings improve speed and flexibility by allowing more kinds of code, including input/output operations, to be analyzed symbolically. SymFC runs inside the Haskell compiler and showed faster performance on real libraries than previous tools.
Open → 2611.07916v1

Symmetric list objects enable free commutative monoid constructions

Symmetric List Objects

Abstract: Cons-lists are fundamental to functional programming, and are well-understood as initial algebras, and as a concrete construction of free monoids. In category theory, such list objects can be axiomatised internal to any monoidal category, with nil and cons maps, and a recursion mechanism. When strengthened to support parametrised recursion, they can be shown to give the free monoid construction. We study a small variant on parametrised list objects called parametrised symmetric list objects, in a symmetric monoidal category, where the two frontmost elements are allowed to be permuted. We show that this gives a construction of free commutative monoids, and develop some related theory.

Tue 27 OctLogic in Computer Science
The gist
Lists are basic structures in programming that can be put together in order, like words in a sentence. The researchers looked at a special kind of list where the first two items can be swapped, not just kept in order. They found this lets you build something called a free commutative monoid, which is a way to combine things where order does not matter. This helps in understanding how certain mathematical and computational objects can be formed.
Open → 2610.37944v1

Gentzen-style monadic translation extends Gödel's System T with new tools

The Gentzen-style monadic translation of Gödel's System T revisited

Abstract: We revisit the Gentzen-style monadic translation of Gödel's System T. The translation is parametrized by a nucleus, a monad-like structure that need not satisfy the monad laws. A fundamental theorem of logical relations provides a uniform correctness argument for its instances. By choosing suitable nuclei, we obtain majorants, moduli of pointwise and uniform continuity, internal dialogue trees, and functionals of general bar recursion, all represented by terms of T. The internal dialogue-tree application gives a simpler construction, with correctness established directly using Church-encoded terms. We also extend the translation and its fundamental theorem to sums and finite lists. Finally, we develop the Kuroda-style translation and its continuity instance, comparing the moduli obtained with those of the Gentzen-style translation.

Sun 4 OctLogic in Computer Science
The gist
Gödel’s System T is a foundational system in mathematical logic used to represent computations. This paper revisits a way to translate System T terms using a structure called a nucleus that acts like a monad but doesn’t have to follow all monad rules. By picking different nuclei, the authors show how to represent various mathematical concepts such as measures of function size, continuity, and recursion inside System T. They also improve and expand the translation for more data types and provide comparisons with another translation style. This work helps understand and manipulate computational properties within a unified logical framework.
Open → 2610.05187v1