Functional programming languages are informally classified into pure and impure languages. The precise meaning of this distinction has been a matter of controversy. We therefore investigate a formal definition of purity. We begin by showing that some proposed definitions which rely on confluence, soundness of the beta axiom, preservation of pure observational equivalences and independence of the order of evaluation, do not withstand close scrutiny. We propose instead a definition based on parameter-passing independence. Intuitively, the definition implies that functions are pure mappings from arguments to results; the operational decision of how to pass the arguments is irrelevant. In the context of Haskell, our definition is consistent with the fact that the traditional call-by-name denotational semantics coincides with the traditional call-by-need implementation. Furthermore, our definition is compatible with the stream-based, continuation-based and monad-based integration of computational effects in Haskell. Finally, we observe that call-by-name reasoning principles are unsound in compilers for monadic Haskell.

The LOLITA natural language processor is an example of one of the ever-increasing number of large-scale systems written entirely in a functional programming language. The system consists of over 47,000 lines of Haskell code (excluding comments) and is able to perform a wide range of tasks such as semantic and pragmatic analysis of text, information extraction and query analysis. The efficiency of such a system is critical; interactive tasks (such as query analysis) must ensure that the user is not inconvenienced by long pauses, and batch mode tasks (such as information extraction) must ensure that an adequate throughput can be achieved. For the past three years the profiling tools supplied with GHC and HBC have been used to analyse and reason about the complexity of the LOLITA system. There have been good results, however experience has shown that in a large system the profiling life-cycle is often too long to make detailed analysis possible, and the results are often misleading. In response to these problems a profiler has been developed which allows the complete set of program costs to be recorded in so-called cost-centre stacks. These program costs are then analysed using a post-processing tool to allow the developer to explore the costs of the program in ways that are either not possible with existing tools or would require repeated compilations and executions of the program. The modifications to the Glasgow Haskell compiler based on detailed cost semantics and an efficient implementation scheme are discussed. The results of using this new profiling tool in the analysis of a number of Haskell programs are also presented. The overheads of the scheme are discussed and the benefits of this new system are considered. An outline is also given of how this approach can be modified to assist with the tracing and debugging of programs.

In this article we explain two different operational interpretations of functional programs by two different logics. The programs are simply typed λ-terms with pairs, projections, if-then-else and least fixed point recursion. A logic for call-by-value evaluation and a logic for call-by-name evaluation are obtained as as extensions of a system which we call the basic logic of partial terms (BPT). This logic is suitable to prove properties of programs that are valid under both strict and non-strict evaluation. We use methods from denotational semantics to show that the two extensions of BPT are adequate for call-by-value and call-by-name evaluation. Neither the programs nor the logics contain the constant ‘undefined’.

One of the goals of this paper is to demonstrate that denotational semantics is useful for operational issues like implementation of functional languages by abstract machines. This is exemplified in a tutorial way by studying the case of extensional untyped call-by-name λ-calculus with Felleisen's control operator [Cscr ]. We derive the transition rules for an abstract machine from a continuation semantics which appears as a generalization of the ¬¬-translation known from logic. The resulting abstract machine appears as an extension of Krivine's machine implementing head reduction. Though the result, namely Krivine's machine, is well known our method of deriving it from continuation semantics is new and applicable to other languages (as e.g. call-by-value variants). Further new results are that Scott's D∞-models are all instances of continuation models. Moreover, we extend our continuation semantics to Parigot's λμ-calculus from which we derive an extension of Krivine's machine for λμ-calculus. The relation between continuation semantics and the abstract machines is made precise by proving computational adequacy results employing an elegant method introduced by Pitts.

Concurrent ML (CML) is an extension of Standard ML of New Jersey with concurrent features similar to those of process algebra. In this paper, we build upon John Reppy's reduction semantics for CML by constructing a compositional operational semantics for a fragment of CML, based on higher-order process algebra. Using the operational semantics we generalise the notion of weak bisimulation equivalence to build a semantic theory of CML. We give some small examples of proofs about CML expressions, and show that our semantics corresponds to Reppy's up to weak first-order bisimulation.

In the end, research on functional languages does little good unless they are used to write something other than compilers for functional languages. However, if one scans a typical functional programming conference or journal, one mainly sees papers on twists in language design, speed-ups in compiled code, clever new analyses, or refinements to semantic models. It much less common to see a paper that considers a functional language as a tool to some other practical end. We would like to see this change.

The Journal of Functional Programming carries, and will continue to carry, articles on all aspects of functional programming from lambda calculus theory to language design to implementation. But we have specially sought, and will continue to seek, papers on functional programming practice and experience.

Research and papers on practice and experience sometimes receive less attention because they are perceived as possessing less academic content. So we want to remind potential authors that we have published a number of papers on this topic in the past, and to spell out the criteria we apply to such papers.

We define a weak λ-calculus, λσw, as a subsystem of the full λ-calculus with explicit substitutions λσ[uArr ]. We claim that λσw could be the archetypal output language of functional compilers, just as the λ-calculus is their universal input language. Furthermore, λσ[uArr ] could be the adequate theory to establish the correctness of functional compilers. Here we illustrate these claims by proving the correctness of four simplified compilers and runtime systems modelled as abstract machines. The four machines we prove are the Krivine machine, the SECD, the FAM and the CAM. Thus, we give the first formal proofs of Cardelli's FAM and of its compiler.

The process of writing large parallel programs is complicated by the need to specify both the parallel behaviour of the program and the algorithm that is to be used to compute its result. This paper introduces evaluation strategies: lazy higher-order functions that control the parallel evaluation of non-strict functional languages. Using evaluation strategies, it is possible to achieve a clean separation between algorithmic and behavioural code. The result is enhanced clarity and shorter parallel programs. Evaluation strategies are a very general concept: this paper shows how they can be used to model a wide range of commonly used programming paradigms, including divide-and-conquer parallelism, pipeline parallelism, producer/consumer parallelism, and data-oriented parallelism. Because they are based on unrestricted higher-order functions, they can also capture irregular parallel structures. Evaluation strategies are not just of theoretical interest: they have evolved out of our experience in parallelising several large-scale parallel applications, where they have proved invaluable in helping to manage the complexities of parallel behaviour. Some of these applications are described in detail here. The largest application we have studied to date, Lolita, is a 40,000 line natural language engineering system. Initial results show that for these programs we can achieve acceptable parallel performance, for relatively little programming effort.

Many, perhaps even most, algorithms that involve data structures are traditionally expressed by incremental updates of the data structures. In functional languages, however, incremental updates are usually both clumsy and inefficient, especially when the data structure is an array.

In functional languages, we instead prefer to express such array algorithms using monolithic arrays – wholesale creation of the final answer – both for succinctness of expression, efficiency (only one array created) and (sometimes) implicit parallelism. The ease with which the solution can be reformulated of course depends on the problem, and varies from trivial (e.g. matrix multiplication), to challenging (e.g. solving linear equation systems using Gauss elimination, which in fact can be done by creating only two arrays, recursively defined, of which one is the answer). Other problems have been notoriously resistant to attack; these usually involve some unpredictable processing order of the elements. One such problem is graph marking, i.e. marking the nodes reachable from a set of roots. Hitherto, no functional method has been known except emulating the traditional imperative solution (King & Launchbury, 1995; Launchbury & Peyton Jones, 1995).

The contribution of this paper is to show how this problem, and some related ones, can be solved using a novel array creation primitive, lazier than previous ones.

We show the design principles of an automatic indentation GNU Emacs mode for Haskell and Miranda(tm), functional languages using the ‘layout rule’ instead of the usual parenthetic structures for indentifying dependent program parts.

An important issue faced by implementors of higher-order functional programming languages is the allocation and deallocation of storage for variables. The possibility of variables escaping their scope during runtime makes traditional stack allocation inadequate. We consider the problem of detecting when variables in such languages do not escape their scope, and thus can have their bindings allocated in an efficient manner. We use an annotated type system to infer information about the use of variables in a higher-order, strict functional language and combine this system with a translation to an annotated language which explicitly indicates which variables do not escape. The type system uses a notion of annotated types which extends the traditional simple type system with information about the extent of variables. To illustrate the use of this information we define an operational semantics for the annotated language which supports both stack and environment allocation of variable bindings. Only the stack allocated bindings need follow the protocol for stacks: their extent may not exceed their scope. Environment allocated bindings can have any extent, and their allocation has no impact on the stack allocated ones. We prove the analysis and translation correct with respect to this operational semantics by adapting a traditional type consistency proof to our setting. We have encoded the proof into the Elf programming language and typechecked it, providing a partially machine-checked proof.

We present an extension of the Hindley–Milner type system that supports a generous class of type constructors called functors, and provide a parametrically polymorphic algorithm for their mapping, i.e. for applying a function to each datum appearing in a value of constructed type. The algorithm comes from shape theory, which provides a uniform method for locating data within a shape. The resulting system is Church–Rosser and strongly normalizing, and supports type inference. Several different semantics are possible, which affects the choice of constants in the language, and are used to illustrate the relationship to polytypic programming.

We present a calculus that captures the operational semantics of call-by-need. The call-by-need lambda calculus is confluent, has a notion of standard reduction, and entails the same observational equivalence relation as the call-by-name calculus. The system can be formulated with or without explicit let bindings, admits useful notions of marking and developments, and has a straightforward operational interpretation.

In this paper we aim to give an introduction to fuzzy logic using the language Haskell to implement our solutions. We shall see how the high-level, declarative nature of a functional language allows us to implement easily and efficiently solutions to problems using fuzzy logic and, in particular, how the presence of functions as first-class values allows us to model the key concept of the fuzzy subset in a natural way.

In this paper we give a big-step Structured Operational Semantics (SOS), in the style of Plotkin, Kahn and Milner, of a significant fragment of the functional programming language Scheme, including quote, eval, quasiquote and unquote. The SOS formalism allows us to discuss incrementally the various features of the language and to keep a low mathematical overhead, thus producing a rigorous account of the semantics of a ‘real’ programming language, which nonetheless has a pedagogical value. More specifically, we formalize four strictly increasing fragments of Scheme, using a number of formal systems which express the evaluation of expressions, the display of output results, and the handling of errors.

Lazy functional languages seem to be unsuitable for programming embedded computers because their implementations require so much memory for program code and graph. In this paper we describe a new abstract machine for the implementation of lazy functional languages on embedded computers called the X-machine. The X-machine has been designed so that program code can be stored compactly as byte code, yet run quickly using dynamic compilation. Our first results are promising – programs typically require only 33% of the code space of an ordinary implementation, but run at 75% of the speed. Future work needs to concentrate on reducing the size of statically-allocated data and the run-time system, and on developing a more detailed understanding of throw-away compilation.

Moggi's computational lambda calculus is a metalanguage for denotational semantics which arose from the observation that many different notions of computation have the categorical structure of a strong monad on a cartesian closed category. In this paper we show that the computational lambda calculus also arises naturally as the term calculus corresponding (by the Curry–Howard correspondence) to a novel intuitionistic modal propositional logic. We give natural deduction, sequent calculus and Hilbert-style presentations of this logic and prove strong normalisation and confluence results.

A string-formatting function such as printf in C seemingly requires dependent types, because its control string determines the rest of its arguments. Examples:

formula here

We show how changing the representation of the control string makes it possible to program printf in ML (which does not allow dependent types). The result is well typed and perceptibly more efficient than the corresponding library functions in Standard ML of New Jersey and in Caml.

We describe a system that supports source-level integration of ML-like functional language code with ANSI C or Ada83 code. The system works by translating the functional code into type-correct, ‘vanilla’ C or Ada; it offers simple, efficient, type-safe inter-operation between new functional code components and ‘legacy’ third-generation-language components. Our translator represents a novel synthesis of techniques including user-parameterized specification of primitive types and operators; removal of polymorphism by code specialization; removal of higher-order functions using closure datatypes and interpretation; and aggressive optimization of the resulting first-order code, which can be viewed as encoding the result of a closure analysis. Programs remain fully typed at every stage of the translation process, using only simple, standard type systems. Target code runs at speeds comparable to the output of current optimizing ML compilers, even though handicapped by a conservative garbage collector.

Meertens number is a number with a very peculiar property. I had the idea in 1991, when I was invited to celebrate the occasion of Lambert Meertens' 25 years at the CWI, Amsterdam. Lambert has been a good friend and colleague for a number of years, and rather than bring the usual bottle of Glenlivet as a gift, I decided to give him a number.