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

People

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 Jeremy 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 transformation (Lämmel)

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

Eelco Visser has been working on program transformation and strategic rewriting

Simon Marlow is working on an API for plugging GHC into Visual Studio.

Haskell frontends (cf. Haskell Community Report sections on this: November 2001, May 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.

• Hatchet -- 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)
• HsSource. A full parser for Haskell 98 source, based on the Happy parser generator (see section 5.4.1), is maintained in the GHC CVS repository: http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/hslibs/hssource/ 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 in 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).

• Stratego -- Specification of Program Transformation Systems, see also http://www.stratego-language.org. Stratego is a modular language for the specification of fully automatic program transformation systems based on the paradigm of rewriting strategies.
• HSX. 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 front-end.
• HsOpt. 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.
• Strafunski. ... 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 2000. 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).
• 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.
• Derivable type classes, Ralf Hinze and Simon Peyton Jones. See also GHC documentation.
• Template 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, ghc."
• Scrap 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 type-specific code. 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 extension.
• Ultra (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.
• MAG 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.
• Cover (Combining Verification Methods in Software Development) at Chalmers: 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: unfolding, folding, abstraction, and definition introduction/elimination. Synth is currently maintained by Gines Moreno .
• Tabaluga. A predecessor to Strafunski - no longer maintained.

Haskell IDEs, program development and maintenance tools, editor modes, ..

• VS Haskell. Extending GHC to provide an API for plugging it into Visual Studio.
• hIDE -- a programming IDE for Haskell.
• Program 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)
• JCreator 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.