Warning: if you're on the ICFP program committee and want to preserve
double-blind reviewing, please don't read this post.
Phew! The ICFP deadline is past, and two papers have been submitted.
The first paper covers the full story of stream fusion, greatly
extending work initially done for the ByteString library, in particular,
how to fuse zips, concatMaps and list comprehensions, and we've
implemented the entire list library to be stream fusible. The point:
faster Haskell code.
The second paper describes how, using Haskell, we can write
monte-carlo-based simulators that out perform optimised C
implementations, using a generative approach to simulator
specialisation. In particular, we generate multicore and cluster-based
simulators for polymer chemistry, outperforming the existing
(commercial) software in this area.
So here they are, for your functional programming satisfaction:
Stream Fusion:
From Lists to Streams to Nothing at All.
Duncan Coutts, Roman
Leshchinskiy and Don Stewart.
Abstract:
This paper presents an automatic fusion system, stream fusion,
based on equational transformations, that fuses a wider range of
functions than existing short-cut fusion systems. In particular, stream
fusion is able to fuse zips, left folds and functions over nested lists,
including list comprehensions. A distinguishing feature of the stream
fusion framework is its simplicity: by transforming list functions to
expose their structure, intermediate values are eliminated by general
purpose compiler optimisations.
We have reimplemented the entire Haskell standard list library on top of
our framework, providing stream fusion for Haskell lists. By allowing a
wider range of functions to fuse, we see an increase in the number of
occurrences of fusion in typical Haskell programs. We present benchmarks
documenting time and space improvements.
|
And the second paper:
Generative
Code Specialisation for High-Performance Monte-Carlo Simulations.
Don Stewart, Hugh Chaffey-Millar, Gabriele Keller, Manuel M. T.
Chakravarty and Christopher Barner-Kowollik.
Abstract:
We address the tension between software generality and performance in
the domain of scientific and financial simulations based on Monte-Carlo
methods. To this end, we present a novel software architecture, centred
around the concept of a specialising simulator generator, that combines
and extends methods from generative programming, partial evaluation,
runtime code generation, and dynamic code loading. The core tenet is
that, given a fixed simulator configuration, a generator in a
functional language can produce low-level code that is more highly
optimised than a manually implemented generic simulator. We also
introduce a skeleton, or template, capturing a wide range of
Monte-Carlo methods and use it to explain how to design specialising
simulator generators and how to generate parallelised simulators for
multi-core and distributed-memory multiprocessors.
We evaluated the practical benefits and limitations of our approach by
applying it to a highly relevant problem in computational chemistry.
More precisely, we used a Markov-chain Monte-Carlo method for the study
of advanced forms of polymerisation kinetics. The resulting
implementation executes faster than all competing software products,
while at the same time also being more general. The generative
architecture allows us to cover a wider range of chemical reactions and
to target a wider range of high-performance architectures (such as PC
clusters and SMP multiprocessors).
We show that it is possible to outperform low-level languages with
functional programming in domains with very stringent performance
requirements if the domain also demands generality.
|
/home ::
/haskell ::
permalink ::
rss