books

  • Real World Haskell, Bryan O’Sullivan, John Goerzen, Don Stewart. Published by O’Reilly, 2008, 710 pages. ISBN 0596514980, 9780596514983
    This easy-to-use, fast-moving tutorial introduces you to functional programming with Haskell. You’ll learn how to use Haskell in a variety of practical ways, from short scripts to large and demanding applications. Real World Haskell takes you through the basics of functional programming at a brisk pace, and then helps you increase your understanding of Haskell in real-world issues like I/O, performance, dealing with data, concurrency, and more as you move through each chapter.
  • Dynamic Extension of Typed Functional Languages (PDF), Don Stewart. PhD Thesis, University of New South Wales, Sydney, Australia. 2010.

interviews

videos

talks

papers

Stream Fusion: From Lists to Streams to Nothing at All. Duncan Coutts, Roman Leshchinskiy and Don Stewart. Proceedings of the International Conference on Functional Programming (ICFP 2007), Freiburg, Germany. Oct 2007.
[.bib, .ps.gz, .pdf, .mov(video of ICFP talk) ]

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.

Specialising Simulator Generators for High-Performance Monte-Carlo Methods. Gabriele Keller, Hugh Chaffey-Millar, Manuel M. T. Chakravarty, Don Stewart, and Christopher Barner-Kowollik. Accepted for PADL, 2007. (This is a thoroughly revised and updated version of “Generative Code Specialisation for High-Performance Monte-Carlo Simulations” below.)
[ .pdf]

We address the tension between software generality and performance in the domain of simulations based on Monte-Carlo methods. We simultaneously achieve generality and high performance by a novel development methodology and software architecture centred around the concept of a specialising simulator generator. Our approach combines and extends methods from functional programming, generative programming, partial evaluation, and runtime code generation. We also show how to generate parallelised simulators.

We evaluated our approach by implementing a simulator for advanced forms of polymerisation kinetics. We achieved unprecedented performance, making Monte-Carlo methods practically useful in an area that was previously dominated by deterministic PDE solvers. This is of high practical relevance, as Monte-Carlo simulations can provide detailed microscopic information that cannot be obtained with deterministic solvers.

A Parallelised High Performance Monte Carlo Simulation Approach for Complex Polymerisation Kinetics. Hugh Chaffey-Millar, Don Stewart, Manuel M. T. Chakravarty, Gabriele Keller, and Christopher Barner-Kowollik. Macromolecular Theory and Simulation 16(6), pp 575-592, 2007.
[ .pdf (published version from WILEY-VCH Verlag) , .pdf (preprint), Supplementary data]

A novel, parallelised approach to Monte Carlo simulations for the computation of full molecular weight distributions arising from complex polymerisation reactions is presented. The methods developed enable rapid simulation of the outcomes of reactions that previously required many hours or even days. Some systems (e.g. those arising in the authors’ own research into star-polymer formation processes) which once required circa 8 hours of simulation time (using the commercial program package PREDICI) can now be simulated in a few minutes on a parallel computer.

In addition to this significant speed improvement, new insights have been developed with regard to the Monte Carlo process in at least four key areas: (1) an insufficient system size has been shown to create inaccuracies via poor representation of the most improbable events and least numerous species; (2) from a speed point of view, the method has been found to under-perform for some simple systems when compared to PREDICI but is vastly superior when applied to complex systems; (3) advanced algorithmic principles and compiler technology known to computer scientists have been used to provide speed improvements and (4) the parallelisability of the algorithm has been explored and excellent scalability been demonstrated.

For the first time, specific implementation strategies and their suitabilities are discussed. Further, the code is available, allowing other researchers to use or examine in detail the methods put forward.

Generative Code Specialisation for High-Performance Monte-Carlo Simulations. Don Stewart, Hugh Chaffey-Millar, Gabriele Keller, Manuel M. T. Chakravarty, Christopher Barner-Kowollik. Technical Report UNSW-CSE-TR-0710, 2007.[.bib, .ps.gz, .pdf]

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.

Rewriting Haskell Strings. Duncan Coutts, Don Stewart and Roman Leshchinskiy. In Proceedings of Practical Aspects of Declarative Languages 8th International Symposium, PADL 2007, Jan 2007, pp. 50–64, Springer-Verlag. Awarded “Most Practical Paper” at PADL.[.bib, .ps.gz, .pdf]

The Haskell String type is notoriously inefficient. We introduce a new data type, ByteString, based on lazy lists of byte arrays, combining the speed benefits of strict arrays with lazy evaluation. Equational transformations based on term rewriting are used to deforest intermediate ByteStrings automatically. We describe novel fusion combinators with improved expressivity and performance over previous functional array fusion strategies. A library for ByteStrings is implemented, providing a purely functional interface, and approaches the speed of low-level mutable arrays in C.

Dynamic Applications From the Ground Up. Don Stewart and Manuel M. T. Chakravarty. In Proceedings of the ACM SIGPLAN Workshop on Haskell, pages 27-38. ACM Press, 2005.[.bib, .ps.gz, .pdf]

Some Lisp programs, such as Emacs, but also the Linux kernel (when fully modularised) are mostly dynamic; i.e., apart from a small static core, the significant functionality is dynamically loaded. In this paper, we explore fully dynamic applications in Haskell where the static core is minimal and code is hot swappable. We demonstrate the feasibility of this architecture by two applications: Yi, an extensible editor, and Lambdabot, a plugin-based IRC robot. Benefits of the approach include hot swappable code and sophisticated application configuration and extension via embedded DSLs. We discuss both benefits in detail at the example of a novel embedded DSL for editor interfaces.

Plugging Haskell In. André Pang, Don Stewart, Sean Seefried, and Manuel M. T. Chakravarty. In Proceedings of the ACM SIGPLAN Workshop on Haskell, pages 10-21. ACM Press, 2004
[.bib, .ps.gz, .pdf]

Extension languages enable users to expand the functionality of an application without touching its source code. Commonly, these languages are dynamically typed languages, such as Lisp, Python, or domain-specific languages, which support runtime plugins via dynamic loading of components. We show that Haskell can be comfortably used as a statically typed extension language, and that it can support type-safe dynamic loading of plugins using dynamic types. Moreover, we discuss how plugin support is especially useful to applications where Haskell is used as an embedded domain-specific language (EDSL). We explain how to realise type-safe plugins using dynamic types, runtime compilation, and dynamic linking, exploiting infrastructure provided by the Glasgow Haskell Compiler. We demonstrate the practicability of our approach with several applications that serve as running examples.

demonstrations and position papers

Domain Specific Languages for Domain Specific Problems (position paper), Don Stewart, LACSS Workshop on Non-Traditional Programming Models October 2009

As the complexity of large-scale computing architecture increases, the effort needed to program these machines efficiently has grown dramatically. The challenge is how to bridge this “programmability gap”, making the hardware more accessible to domain experts. We argue for an approach based on
executable embedded domain specific languages (EDSLs)—small languages with focused expressive power hosted directly in existing high-level programming languages such as Haskell. We provide examples of EDSLs in use in industry today, and describe the advantages EDSLs have over general purpose languages in productivity, performance, correctness and cost. Read more…

Autonomous Verification and Validation (position paper). Lee Pike, Don Stewart and John Van Enk. CPS Week 2009 Workshop on Mixed Criticality

We outline a new approach to the verification and validation (V&V) of safety-critical avionics based on the use of executable \emph{lightweight domain specific languages} (LwDSLs)—domain-specific languages hosted directly in an existing high-level programming language.  We provide examples of LwDSLs used in industry today, and then we describe the advantages of LwDSLs in V&V.  We argue the approach promises substantial automation and cost-reduction in V&V.

Haskell: Batteries Included. Duncan Coutts, Isaac Potoczny-Jones and Don Stewart and Spencer Janssen. To Appear at HW 2008.[.bib, .ps.gz, .pdf]

The quality of a programming language itself is only one component in the ability of application writers to get the job done. Programming languages can succeed or fail based on the breadth and quality of their library collection. Over the last few years, the Haskell community has risen to the task of building the library infrastructure necessary for Haskell to succeed as a programming language suitable for writing real-world applications. This on-going work, the Cabal and Hackage effort, is built on the open source model of distributed development, and have resulted in a flowering of development in the language with more code produced and reused now than at any point in the community’s history. It is easier to obtain and use Haskell code, in a wider range of environments, than ever before. This demonstration describes the infrastructure and process of Haskell development inside the Cabal/Hackage framework, including the build system, library dependency resolution, centralised publication, documentation and distribution, and how the code escapes outward into the wider software community. We survey the benefits and trade-offs in a distributed, collaborative development ecosystem and look at a proposed Haskell Platform that envisages a complete Haskell development environment, batteries included.

XMonad: A Tiling Window Manager. Don Stewart and Spencer Janssen. To Appear at HW 2007.[.bib, .ps.gz, .pdf]

xmonad is a tiling window manager for the X Window system, implemented, configured and dynamically extensible in Haskell. This demonstration presents the case that software dominated by side effects can be developed with the precision and efficiency we expect from Haskell by utilising purely functional data structures, an expressive type system, extended static checking and property-based testing. In addition, we describe the use of Haskell as an application configuration and extension language.