Refactoring Functional Programs
[back to project home page]
A small, but growing heap of potentially related work, in no
particular order. To be harvested, amended, summarised and sorted..
Functional refactoring people, potentially relevant Haskell
tools and projects..
- Mark Tullsen
(now at OGI). While a PhD student with Paul Hudak at Yale, wrote
a thesis onprogram transformation system for Haskell called PATH
(Programmer Assistant for Transforming Haskell).
- Ralf Lämmel and
Gibbons have been interested in (strategic) program transformation
and generic refactoring. There's a lot of work on functional
techniques for program transformation on Ralf's
publications page, but of special interest for us in the
context of functional refactoring are: A Framework for Datatype
Transformation (Kort/Lämmel), Reuse by program
de Moor and Ganesh
Sittampalam have been working on MAG
- a small transformation system for Haskell
- Martin Erwig
has been looking at program change on the basis of Programs
as abstract data types (instead of concretely
represented strings of characters). Together with Deling Ren,
he has been working on a Haskell
Update Language or update
- Eelco Visser
has been working on program
transformation and strategic rewriting
Marlow is working on an API for plugging GHC into Visual Studio.
- Haskell frontends (cf. Haskell Community Report sections on
2002). Ideally, we'd need both parsing/pretty-printing and type
checking/static analysis to get the syntax and static semantic
information to base our refactorings on.
-- A type Checking and Inference Tool for Haskell 98
- The Programatica
project at Pacsoft/OGI has been working on
a parsing/typing frontend for Haskell, but has not yet
released the tool (the parser-only component has been
available on request)
A full parser for Haskell 98 source, based on the Happy parser
generator (see section 5.4.1), is maintained in the GHC CVS
The project is currently active and the parser is kept up to date
with the Haskell 98 Language Report. The basic components of the
project are a lexer, a parser, a pretty printer and an abstract
syntax representation. The parser requires Happy.
- Typing Haskell
Haskell benefits from a sophisticated type system, but implementors,
programmers, and researchers suffer because it has no formal
description. To remedy this shortcoming, we present a Haskell
program that implements a Haskell typechecker, thus providing a
mathematically rigorous specification in a notation that is familiar
to Haskell users. We expect this program to fill a serious gap in
current descriptions of Haskell, both as a starting point for
discussions about existing features of the type system, and as a
platform from which to explore new proposals
- Haddock is a
documentation generator that supposedly understands Haskell syntax -
we might want to check whether its parsing component is reusable and
any good for us (Chris says it supports GHC extensions, and
has an AST format close, but not the same as the hssource
one, so even using that ones pretty-printer would require
some adaption? and of course, no type info..).
- Haskell meta-programming, generic programming, toolsets and
transformation frameworks. Once we've got the semantic
information for our refactorings, the real work begins (program
analysis and transformation).
-- Specification of Program Transformation Systems, see
Stratego is a modular language for the specification of fully
automatic program transformation systems based on the paradigm of
The HSX framework is a prototype for experimentation with the
application of rewriting strategies using the transformation
language Stratego to program optimization. Although the syntax is
for complete Haskell (without layout), the transformations are done
on a core-like subset only. The framework was used to implement the
Warm Fusion transformation for deforestation that turns recursive
function definitions into build/cata form. This form makes
deforestation, the fusion of a composition of data structure
producing and consuming functions, a piece of cake. Extension of the
work to full Haskell was not continued by lack of a reusable Haskell
HsOpt is a transformation framework for Helium, a proper (light)
subset of Haskell developed at Utrecht University. We reuse the
parser, prettyprinter, and typechecker from the Helium project. The
first target is the specification of a GHC style simplifier in
Stratego. The Haskell ATerm library is used to interface Haskell
components and Stratego components.
... is a Haskell-based bundle for generic programming. It
provides programming support for generic traversal as useful in the
implementation of program transformations. It is being developed by
Ralf Lämmel and Joost Visser at CWI and VU in Amsterdam since August
The basic concept underlying Strafunski are functional strategies:
generic functions that not only can be applied to terms of any type,
but which also allow generic traversal into a subterm while mixing
type-specific and uniform behaviour. Strafunski offers both a
strategy combinator library, including generic traversal
combinators, and a precompiler that supports using the library on
large systems of data types (via an extension of DrIFT).
is a type sensitive preprocessor for Haskell. It
extracts type declarations and directives from modules. The
directives cause rules to be fired on the parsed type declarations,
generating new code which is then appended to the bottom of the
input file. The rules are expressed as Haskell code, and it is
intended that the user can add new rules as required.
DrIFT automates instance derivation for classes that aren't
supported by the standard compilers. In addition, instances can be
produced in seperate modules to that containing the type
declaration. This allows instances to be derived for a type after
the original module has been compiled. As a bonus, simple utility
functions can also be produced from a type.
type classes, Ralf Hinze and Simon Peyton Jones. See
metaprogramming for Haskell, Tim Sheard and Simon Peyton
Jones: "We propose a new extension to the purely functional
programming language Haskell that supports compile-time
meta-programming. The purpose of the system is to support the
algorithmic construction of programs at compile-time.
The ability to generate code at compile time allows the programmer
to implement such features as polytypic programs, macro-like
expansion, user directed optimization (such as inlining), and the
generation of supporting data structures and functions from existing
data structures and functions.
Our design is being implemented in the Glasgow Haskell Compiler,
your boilerplate: a practical approach to generic programming,
Ralf Laemmel and Simon Peyton Jones:
"We describe a design pattern that for writing programs that traverse
data structures built from rich mutually-recursive data types. Such
programs often have a great deal of "boilerplate" code that simply
walks the structure, hiding a small amount of "real" code that
constitutes the reason for the traversal.
Our technique allows most of this boilerplate to be written once and
for all (perhaps even mechanically generated), leaving the
programmer free to concentrate on the important part of the
algorithm. These generic programs are much more robust to data
structure evolution because they contain many fewer lines of
Our approach is simple to understand, reasonably efficient, and it
handles all the data types found in conventional functional
programming languages. It makes essential use of rank-2
polymorphism, an extension found in some implementations of Haskell."
- The goal of the Generic
Haskell project is to develop: a generic programming language
extension of Haskell; practical examples such as a database
connection and XML tools; programming methods for the language
(Ulm Transformation System) is an interactive program transformation
system to transform Haskell programs. The system itself is written
in the functional language Gofer and uses TkGofer to implement its
user interface. An extended
abstract describes the system.
is a small transformation system for a subset of Haskell. It
was originally written as a teaching tool for the 3rd
International Summer School on Advanced Functional
Programming. One of its most innovative features is the use of
novel matching algorithms for lambda expressions, the one-step
and two-step matching algorithms. MAG is also of interest
because it makes use of the language implementation tools (for
parsing, pretty-printing and semantic analysis) now under
development at Utrecht University.
(Combining Verification Methods in Software Development) at
The goal of this programme is to develop methods for improving
software quality. The approach is to integrate a variety of
verification methods into a framework which permits a smooth
progression from hacking code to fully formal proofs of correctness.
By a pragmatic integration of different techniques in a
next-generation program development tool, we hope to handle systems
on a much larger scale than hitherto.
This project builds on and combines our extensive and
internationally well-known research in interactive theorem provers,
formal methods, program analysis and transformation, and automatic
testing. Our long experience with functional languages, which we use
both as implementation tools and a test-bed, improves our chances of
success in tackling these difficult problems.
[yes, this is about Haskell;-]
- Not quite Haskell, but closely related: SYNTH,
A Transformation System for Lazy Functional Logic Programs.
It's a refactoring tool for lazy functional logic programs (like
Curry, a conservative extension of Haskell in order to include
logic variables) based on some well-known transformations:
folding, abstraction, and definition introduction/elimination.
Synth is currently maintained by Gines
A predecessor to Strafunski - no longer maintained.
- Haskell IDEs, program development and maintenance tools,
editor modes, ..
Haskell. Extending GHC to provide an API for plugging it into
-- a programming IDE for Haskell.
development tools section at haskell.org: tag file
generators, program manipulators, editor modes for Vim, Emacs,
.., documentation and typesetting tools, testing tools,
debugging support, ..
- WinHugs -- a thin IDE-style layer on top of Hugs (Windows only,
included in standard release)
with Haskell support -- An IDE for both Haskell and Java
(see also jHaskell/Helium)
If you are aware of other relevant pointers, please send us an email, and we'll
eventually get round to updating this page.