916 papers · page 13 of 46
Abstract In this paper, we present a formalisation in a proof assistant, Isabelle/HOL, of a naive version of the Gauss-Jordan algorithm, with explicit proofs of some of its applications; and, additionally, a process to obtain versions of this algorithm in two different functional…
Abstract The study of programming with and reasoning about inductive datatypes such as lists and trees has benefited from the simple categorical principle of initial algebras. In initial algebra semantics, each inductive datatype is represented by an initial f -algebra for an app…
Abstract In this article, we present a new approach to the problem of calculating compilers. In particular, we develop a simple but general technique that allows us to derive correct compilers from high-level semantics by systematic calculation, with all details of the implementa…
Abstract We present a divide-and-conquer algorithm for parsing context-free languages efficiently. Our algorithm is an instance of Valiant's (1975; General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10 (2), 308–314), who reduced the problem of parsing…
The setting is a class on functional programming. There are four students: Anne, Jack, Mary and Theo.
Abstract We present a technique for automatically deriving test data generators from a given executable predicate representing the set of values we are interested in generating. The distribution of these generators is uniform over values of a given size. To make the generation ef…
Abstract The problem of finding a densest segment of a list is similar to the well-known maximum segment sum problem, but its solution is surprisingly challenging. We give a general specification of such problems, and formally develop a linear-time online solution, using a slidin…
The Commercial Users of Functional Programming workshop (CUFP) is an annual workshop held in association with the International Conference on Functional Programming (ICFP). The aim of the CUFP workshops is to publicize the use of functional programming in commercial ventures. Its…
Abstract We introduce a new formulation of pure type systems (PTSs) with explicit substitution and de Bruijn indices and formally prove some of its meta-theory. Using techniques based on Normalisation by Evaluation, we prove that untyped conversion can be typed for predicative PT…
With Thinking Functionally in Haskell Richard Bird steps up to continue a family of textbook classics.Bird and Wadler jointly started the series with two editions of Introduction to Functional Programming (in Haskell) in 1988 and 1998, respectively.Let me begin with the outright …
Abstract In a paper, entitled Binary lambda calculus and combinatory logic , John Tromp presents a simple way of encoding lambda calculus terms as binary sequences. In what follows, we study the numbers of binary strings of a given size that represent lambda terms and derive resu…
Many students complete PhDs in functional programming each year. As a service to the community, the Journal of Functional Programming publishes the abstracts from PhD dissertations completed during the previous year.
Many students complete PhDs in functional programming each year. As a service to the community, the Journal of Functional Programming publishes the abstracts from PhD dissertations completed during the previous year.
Many students complete PhDs in functional programming each year, but there is currently no common location in which to promote and advertise the resulting work. The Journal of Functional Programming would like to change that!
Abstract Representation theorems relate seemingly complex objects to concrete, more tractable ones. In this paper, we take advantage of the abstraction power of category theory and provide a datatype-generic representation theorem. More precisely, we prove a representation theore…
Abstract Pseudo-random number generation is a fundamental problem in computer programming. In the case of sequential processing the problem is very well researched, but parallel processing raises new problems whereof far too little is currently understood. Splittable pseudo-rando…
Abstract Teaching functional programming as a second programming paradigm is often difficult as students can have strong preconceptions about programming. When most of these preconceived ideas fail to be confirmed, functional programming may be seen as an unnecessarily difficult …
Abstract This article presents an overview of student difficulties in an introductory functional programming (FP) course taught in Haskell. The motivation for this study stems from our belief that many student difficulties can be alleviated by understanding the underlying causes …