916 papers · page 18 of 46
Abstract Functional logic programming and probabilistic programming have demonstrated the broad benefits of combining laziness (nonstrict evaluation with sharing of the results) with nondeterminism. Yet these benefits are seldom enjoyed in functional programming because the exist…
Suppose you are given a number of points in a plane and want to have those lines that each contain a large number of the given points. The Hough transform is a computerized procedure for that task. It was invented by Paul Hough (1962), originally to find the trajectories of subat…
Abstract Discrete Interval Encoding Trees are data structures for the representation of fat, i.e. densely populated sets over a discrete linear order. In this paper, we introduce algorithms for set-theoretic operations like intersection, union, etc. on sets represented as balance…
Abstract The worker/wrapper transformation is a general way of changing the type of a recursive definition, usually applied with an eye to increasing algorithmic efficiency. This note identifies an infelicity in the program transformations presented by Gill & Hutton (The worker/w…
Language Implementation Patterns: Create your own Domain-Specific and General Programming Languages, by Terence Parr, Pragmatic Bookshelf, http://www.pragprog.com, ISBN 9781934356456 - Volume 21 Issue 2
Haskell (Peyton Jones, 2003) is often used as a host language for embedding other languages. Typically, the abstract syntax of the guest language is defined by a collection of datatype declarations; parsers and pretty-printers convert between the concrete syntax and its abstract …
Abstract A weight-balanced tree (WBT) is a binary search tree, whose balance is based on the sizes of the subtrees in each node. Although purely functional implementations on a variant WBT algorithm are widely used in functional programming languages, many existing implementation…
Abstract It is often hard to write programs that are efficient yet reusable. For example, an efficient implementation of Gaussian elimination should be specialized to the structure and known static properties of the input matrix. The most profitable optimizations, such as choosin…
Abstract Arrows are a popular form of abstract computation. Being more general than monads, they are more broadly applicable, and, in particular, are a good abstraction for signal processing and dataflow computations. Most notably, arrows form the basis for a domain-specific lang…
Abstract Type abstraction and intensional type analysis are features seemingly at odds—type abstraction is intended to guarantee parametricity and representation independence, while type analysis is inherently non-parametric. Recently, however, several researchers have proposed a…
Abstract O'Neill (The genuine Sieve of Eratosthenes. J. Funct. Program . 19 (1), 2009, 95–106) has previously considered a functional implementation for the genuine Sieve of Eratosthenes, based on the well-known heap data structure. Here, we develop it further by adapting this da…
Abstract In efforts to overcome the complexity of the syntax and the lack of formal semantics of conventional hardware description languages, a number of functional hardware description languages have been developed. Like conventional hardware description languages, however, func…
Abstract This paper introduces a new recursion principle for inductively defined data modulo α-equivalence of bound names that makes use of Odersky-style local names when recursing over bound names. It is formulated in simply typed λ-calculus extended with names that can be restr…
Abstract Using an embedded, interpreted language to control a complicated application can have significant software-engineering benefits. But existing interpreters are designed for embedding into C code. To embed an interpreter into a different language requires an API suited to …
Abstract A parallel prefix network of width n takes n inputs, a 1 , a 2 , . . ., a n , and computes each y i = a 1 ○ a 2 ○ ⋅ ⋅ ⋅ ○ a i for 1 ≤ i ≤ n , for an associative operator ○. This is one of the fundamental problems in computer science, because it gives insight into how par…
Abstract In the design of railway track layouts, there are only a small number of geometric configurations that are used in practice, and a number of constraints as to how those configurations can be fitted together to create a whole layout. In order to solve these problems, we c…
The problem of the Dutch national flag was formulated by Dijkstra (1976) as follows: There is a row of buckets numbered from 1 to n. It is given that : P1 : each bucket contains one pebble P2 : each pebble is either red, white, or blue . A minicomputer is placed in front of this …
The 14th ACM SIGPLAN International Conference on Functional Programming (ICFP) took place on August 31–September 2, 2009 in Edinburgh, Scotland; Andrew Tolmach chaired the program committee. Following the conference, the authors of selected papers were invited to submit extended …