Personal tools

Research papers

From HaskellWiki

Revision as of 08:05, 7 April 2006 by DonStewart (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Research Papers

A lot of documentation exists about Haskell, and its foundations, in the form of research papers written by those investigating language design. And it is this enormous research effort that goes into making Haskell such a sane language. In general, if a feature is not well understood, it isn't going to become part of the language.

Here is a selection of those papers, with the goal of making the wealth of material published on Haskell more available to the casual user, and not just researchers.

Some of the papers are highly technical, others, not so. These papers are not suitable for those trying to learn the language from scratch, but more for those looking for a deeper understanding of the theoretical and practical aspects of Haskell.

If you know of Haskell (or related) papers that are missing, please add them. There's a lot out there.

Contents


1 Monads and state

Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell
In "Engineering theories of software construction", ed Tony Hoare, Manfred Broy, Ralf Steinbruggen, IOS Press, ISBN 1 58603 1724, 2001, pp47-96.
State in Haskell
SL Peyton Jones and J Launchbury, Lisp and Symbolic Computation 8(4), Dec 1995, pp293-341.
Lazy functional state threads
SL Peyton Jones and J Launchbury, SIGPLAN Symposium on Programming Language Design and Implementation (PLDI'94), Orlando, June 1994, pp24-35.
Imperative functional programming
SL Peyton Jones and PL Wadler, 20th ACM Symposium on Principles of Programming Languages (POPL'93), Charleston, Jan 1993, pp71-84.

2 Foreign language interfaces

H/Direct: A Binary Foreign Language Interface for Haskell
SO Finne, D Leijen, E Meijer, SL Peyton Jones, ICFP'98.
Scripting COM components in Haskell
SL Peyton Jones, E Meijer, and D Leijen, Software Reuse 1998.
Calling hell from heaven and heaven from hell
Sigbjorn Finne, Daan Leijen, Erik Meijer, and Simon Peyton Jones. ICFP '99.
Green Card: a foreign-language interface for Haskell
T Nordin and SL Peyton Jones, Proceedings of the Haskell Workshop, Amsterdam, June 1997.

2.1 Interface tools

C -> Haskell, or Yet Another Interfacing Tool
Manuel M. T. Chakravarty. In Pieter Koopman and Chris Clack, editors, Implementation of Functional Languages, 11th. International Workshop (IFL'99), Springer-Verlag, LNCS 1868, 2000.

3 Concurrency

Extending the Haskell Foreign Function Interface with Concurrency
Simon Marlow, Simon Peyton Jones, and Wolfgang Thaller, Proceedings of the Haskell Workshop, Snowbird, Sept 2004.
Concurrent Haskell
SL Peyton Jones, A Gordon, S Finne, 23rd ACM Symposium on Principles of Programming Languages, St Petersburg Beach, Florida, Jan 1996, pp295-308.
Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell
In "Engineering theories of software construction", ed Tony Hoare, Manfred Broy, Ralf Steinbruggen, IOS Press, ISBN 1 58603 1724, 2001, pp47-96.
Developing a high-performance web server in Concurrent Haskell
Simon Marlow. Journal of Functional Programming, 12(4+5):359--374, July 2002

3.1 Software Transactional Memory

Composable Memory Transactions
Tim Harris, Simon Marlow, Simon Peyton Jones, Maurice Herlihy. PPoPP'05: ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Chicago,

Illinois, June 2005

Lock Free Data Structures using STMs in Haskell
Anthony Discolo, Tim Harris, Simon Marlow, Simon Peyton Jones, Satnam Singh) FLOPS 2006: Eighth International Symposium on Functional and Logic Programming, Fuji Susono, JAPAN, April 2006

4 Parallel Haskell

Haskell on a Shared-Memory Multiprocessor
Tim Harris, Simon Marlow, Simon Peyton Jones) Haskell '05: Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, pages 49--61, Tallinn, Estonia, ACM Press, September 2005

5 Runtime Systems

Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine
SL Peyton Jones, Journal of Functional Programming 2(2), Apr 1992, pp127-202.
How to make a fast curry: push/enter vs eval/apply
Simon Marlow and Simon Peyton Jones, Proc International Conference on Functional Programming, Snowbird, Sept 2004, pp4-15.
[http://research.microsoft.com/~simonpj/Papers/optimistic/index.htm Optimistic Evaluation
an adaptive evaluation strategy for non-strict programs, Robert Ennals and

Simon Peyton Jones, Proc ACM International Conference on Functional Programming, Uppsala, Aug 2003 (ICFP'03).

[http://research.microsoft.com/~simonpj/Papers/new-rts.htm The New GHC/Hugs Runtime System, Simon Marlow and Simon Peyton Jones. (Unpublished.)
The interactive Lazy ML System
Lennart Augustsson, J. Funct. Program. 3(1): 77-92 (1993)

5.1 Profiling

Formally-based profiling for higher-order functional languages
PM Sansom and SL Peyton Jones, ACM Transactions on Programming Languages and Systems, 19(2), March 1997, pp 334-385.
Time and space profiling for non-strict functional languages
P Sansom and SL Peyton Jones, 22nd ACM Symposium on Principles of Programming Languages (POPL'95), San Francisco, Jan 1995, pp355-366.
Execution profiling for non-strict functional languages
P Sansom, PhD thesis, University of Glasgow, Nov 1994.

5.2 Garbage collection

Exploring the Barrier to Entry: Incremental Generational Garbage Collection for Haskell
Andy Cheadle, Tony Field, Simon Marlow, Simon Peyton Jones, and Lyndon While, International Symposium on Memory Management, Vancouver, 2004.
Non-stop Haskell, Andy Cheadle, Tony Field, Simon Marlow, Simon Peyton Jones, and Lyndon While
ICFP 2000.
Generational garbage collection for Haskell, P Sansom and SL Peyton Jones
Proc Functional Programming Languages and Computer Architecture (FPCA'93), Copenhagen, June 1993, pp106-116.
An Incremental Garbage Collector for Embedded Real-Time Systems,
Malcolm Wallace and Colin Runciman. Proceedings of Chalmers Winter Meeting, June 1993.

5.3 Dynamic linking

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
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.

6 Compiler technology

6.1 Analysis

Constructed Product Result Analysis for Haskell
Clem Baker-Finch, Kevin Glynn, and Simon Peyton Jones, Journal of Functional Programming 14(2), March 2004, pp 211-245.
Simple Polymorphic Usage Analysis
Keith Wansbrough (2002), PhD thesis, Computer Laboratory, University of Cambridge.
Secrets of the Glasgow Haskell Compiler inliner
Simon Peyton Jones and Simon Marlow. IDL'99; revised version Journal of Functional Programming 12(4), July 2002, pp393-434.
Simple Usage Polymorphism
Keith Wansbrough and Simon Peyton Jones; Workshop on Types In Compilation 2000.
Once Upon a Polymorphic Type Keith
Wansbrough and Simon Peyton Jones, POPL'99.
the effectiveness of a simple strictness analyser
SL Peyton Jones and WD Partain, Functional Programming, Glasgow 1993, ed Hammond and O'Donnell, Springer Verlag Workshops in Computing, 1993, pp201-220.

6.2 Compiler construction

The Glasgow Haskell compiler: a technical overview
SL Peyton Jones, CV Hall, K Hammond, WD Partain, PL Wadler, Proceedings of Joint Framework for Information Technology Technical Conference, Keele, March 1993, pp249-257.

6.3 Compilation by transformation

A transformation-based optimiser for Haskell
SL Peyton Jones and A Santos, Science of Computer Programming 32(1-3), pp3-47, September 1998.
Compiling Haskell by program transformation: a report from the trenches
SL Peyton Jones Proc European Symposium on Programming (ESOP'96), Linkping, Sweden, Springer Verlag LNCS 1058, Jan 1996.
Let-floating: moving bindings to give faster programs
(ICFP '96), SL Peyton Jones, WD Partain, A Santos, Proc International Conference on Functional Programming, Philadelphia (ICFP'96), May 1996.
Cheap deforestation for non-strict functional languages
A Gill, PhD thesis, University of Glasgow, Jan 1996.
Compilation by transformation in non-strict functional languages
A Santos, PhD thesis, University of Glasgow, Sept 1995.
A short cut to deforestation
A Gill, SL Peyton Jones, J Launchbury, Proc Functional Programming Languages and Computer Architecture (FPCA'93), Copenhagen, June 1993, pp223-232.
A modular fully-lazy lambda lifter in Haskell
SL Peyton Jones and D Lester, Software Practice and Experience 21(5), May 1991, pp479-506.
Pattern Guards and Transformational Patterns
Martin Erwig and Simon Peyton Jones; Haskell Workshop 2000.
Playing by the rules: rewriting as a practical optimisation technique in GHC
Simon Peyton Jones, Andrew Tolmach and Tony Hoare, Haskell Workshop 2001.

7 Language design

Unboxed values as first class citizens
SL Peyton Jones and J Launchbury, Functional Programming Languages and Computer Architecture (FPCA'91), Boston, LNCS 523, Springer Verlag, Sept 1991,

pp636-666.

A static semantics for Haskell, SL Peyton Jones and PL Wadler
unpublished draft, Department of Computing Science, University of Glasgow, 1992.
Wearing the hair shirt: a retrospective on Haskell
Slides of my invited talk at POPL'03.
Stretching the storage manager: weak pointers and stable names in Haskell
Simon Peyton Jones, Simon Marlow, and Conal Elliott. Proc Workshop on Implementing Functional Languages, 1999.

7.1 Pure type systems

Henk: a typed intermediate language
SL Peyton Jones and E Meijer, Proceedings of the Types in Compilation Workshop, Amsterdam, June 1997.

7.2 Intermediate languages

Henk: a typed intermediate language
SL Peyton Jones and E Meijer, Proceedings of the Types in Compilation Workshop, Amsterdam, June 1997.
Bridging the gulf: a common intermediate language for ML and Haskell
SL Peyton Jones, J Launchbury, MB Shields, and AP Tolmach, POPL98.

7.3 Functional dependencies

Sound and Decidable Type Inference for Functional Dependencies
Gregory J. Duck, Simon Peyton Jones, Peter J. Stuckey, and Martin Sulzmann, European Symposium on Programming 2004 (ESOP'04).

7.4 Generic programming

Scrap your boilerplate: a practical approach to generic programming
Ralf Laemmel and Simon Peyton Jones, Proc ACM SIGPLAN Workshop on Types in Language Design and Implementation (TLDI

2003), New Orleans, pp26-37, Jan 2003.

Scrap more boilerplate: reflection, zips, and generalised casts
Ralf Laemmel and Simon Peyton Jones. appeared in Proceedings of ICFP 2004, ACM Press
Scrap your boilerplate with class: extensible generic functions
Ralf Laemmel and Simon Peyton Jones. appeared in Proceedings of ICFP 2005, ACM Press

7.5 Modules

First class modules for Haskell
Mark Shields and Simon Peyton Jones; FOOL'02.
An exploration of modular programs
Electronic proceedings of the 1996 Glasgow Functional Programming Workshop, J Nicklisch and SL Peyton Jones, Ullapool, July 1996.

7.6 Exceptions

Imprecise Exceptions, Co-Inductively
Andy Moran, Soeren Lassen, and Simon Peyton Jones. HOOTS'99.
A semantics for imprecise exceptions
Simon Peyton Jones, Alastair Reid, Tony Hoare, Simon Marlow, Fergus Henderson. Proc Programming Language Design and Implementation (PLDI'99), Atlanta.
Asynchronous exceptions in Haskell
Simon Marlow, Simon Peyton Jones, Andy Moran and John Reppy, PLDI'01.

7.7 Records

Lightweight Extensible Records for Haskell
Mark Jones and Simon Peyton Jones, Haskell Workshop 1999.

7.8 Meta programming

Dynamic typing as staged type inference
MB Shields, T Sheard, and SL Peyton Jones, POPL98.
Template meta-programming for Haskell
Tim Sheard and Simon Peyton Jones, Proceedings of the Haskell Workshop, Pittsburgh, 2002
Optimising Embedded DSLs using Template Haskell
Sean Seefried, Manuel M. T. Chakravarty, and Gabriele Keller. In Gabor Karsai and Eelco Visser, editors, Third International Conference on Generative Programming and Component Engineering (GPCE'04), LNCS 3286, Springer-Verlag, pages 186-205, 2004. [An earlier draft was presented at the IFL 2003 - 15th International Workshop on the Implementation of Functional Languages, 2003.

7.9 Type classes

Type classes: exploring the design space
Simon Peyton Jones, Mark Jones, Erik Meijer, Haskell Workshop 1997.
Type classes in Haskell, CV Hall, K Hammond, SL Peyton Jones, and PL Wadler
European Symposium On Programming, LNCS 788, Springer Verlag, pp. 241-256, April 1994.
Bulk types with class
SL Peyton Jones, Electronic proceedings of the 1996 Glasgow Functional Programming Workshop, Ullapool, July 1996.
Derivable Type classes, Ralf Hinze and Simon Peyton Jones
Haskell Workshop 2000.
Implementing Haskell overloading
Lennart Augustsson, 1993. FPCA. 65-73

7.10 Object Oriented Haskell

Object-Oriented Style Overloading for Haskell
Mark Shields and Simon Peyton Jones; BABEL workshop '01.
Interfacing Haskell with Object-Oriented Languages
Andr T. H. Pang and Manuel M. T. Chakravarty. In Greg Michaelson and Phil Trinder, editors, Implementation of Functional Languages: 15th International Workshop, IFL 2003, Edinburgh, UK, September 8-11, 2003, Revised Papers, LNCS 3145, Springer-Verlag, pages 20-36, 2004.

7.11 Associated Types

Associated types with class
Manuel M. T. Chakravarty, Gabriele Keller, Simon Peyton Jones, Simon Marlow) POPL '05: Proceedings of the 32nd ACM SIGPLAN-SIGACT sysposium on Principles of programming languages, pages 1--13, Long Beach, California, USA, ACM Press, 2005
Associated Type Synonyms
Manuel M. T. Chakravarty, Gabriele Keller, and Simon Peyton Jones. In Proceedings of The Tenth ACM SIGPLAN International Conference on Functional Programming, ACM Press, pages 241-253, 2005.

8 Data Structures

8.1 Arrays

An Approach to Fast Arrays in Haskell
Manuel M. T. Chakravarty and Gabriele Keller. In Johan Jeuring and Simon Peyton Jones, editors, lecture notes for The Summer School and Workshop on Advanced Functional Programming 2002. LNCS 2638, Springer-Verlag, pages 27-58, 2003.
Functional Array Fusion
Manuel M. T. Chakravarty and Gabriele Keller. In Xavier Leroy, editor, Proceedings of the Sixth ACM SIGPLAN International Conference on Functional Programming, ACM Press, pp205-216, 2001.

8.2 Binary

Heap Compression and Binary I/O in Haskell
Malcolm Wallace and Colin Runciman, Proceedings of the 2nd ACM Haskell Workshop, Amsterdam, the

Netherlands, June 1997.

The Bits Between The Lambdas: Binary Data in a Lazy Functional Language
Malcolm Wallace and Colin Runciman. proceedings of the International Symposium on Memory Management, Vancouver, Canada, Oct 1998.

9 Program Development

9.1 Tracing

Freja, Hat and Hood - A Comparative Evaluation of Three Systems for Tracing and Debugging Lazy Functional Programs
Olaf Chitil, Colin Runciman, and Malcolm Wallace. Proceedings of the 12th International Workshop on Implementation of Functional Languages, Aachen, Germany, September 4th - 7th 2000, LNCS 2011, 2001, pp. 176--193
Multiple-View Tracing for Haskell - a New Hat
Malcolm Wallace, Olaf Chitil, Thorsten Brehm, and Colin Runciman. (draft)

9.2 Editors

Visual Haskell: A full-featured Haskell development environment
Krasimir Angelov, Simon Marlow. Haskell '05: Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, pages 5--16, Tallinn, Estonia, ACM Press, September 2005
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.

9.3 Documentation

Haddock, A Haskell Documentation Tool
Simon Marlow. Proceedings of the ACM SIGPLAN workshop on Haskell, Pittsburgh Pennsylvania, USA, ACM Press, October 2002

9.4 Lexers and Parsers

Lazy Lexing is Fast
Manuel M. T. Chakravarty. In A. Middeldorp and T. Sato, editors, Fourth Fuji International Symposium on Functional and Logic Programming, Springer-Verlag, LNCS 1722, pages 68-84, 1999.