Talk on Programatica at the Workshop in Refactoring Functional Programs

by Thomas Hallgren
February 9, 2004

This talk consisted of two parts:

a note on the use of refactoring in the development of the Programatica tools
a quick demo of some of functionality of the Programatica Haskell browser

A note on the use of Refactoring in the Programatica project

In the early days Programatica project, about three years ago, there was a plan to experiment with several extensions of Haskell in parallel. Work started on an extensible Haskell front-end, using the Haskell Source library supplied with GHC as a starting point.

Refactoring #1

To be able to work in parallel on multiple versions of the front-end, and share as much code as possible between them, the data types for abstract syntax was refactored from the original directly mutually recursive data types

data Id = ...
data Exp = ... Exp ... Decl ... Pat ... Id ... Type ...
data Decl = ...
data Pat =  ...
data Type = ...

into a two-level structure, with a set of nonrecursive definitions and a separate set of knot-tying recursive definitions

data Id =
data E e d p t = ... e ... d ... p ... Id ... t ...
data D e d p t = ...
data P p = ...
data T t = ...

newtype Exp = Exp (E Exp Decl Pat Type)
newtype Decl = Decl (D Exp Decl Pat Type)
newtype Pat = ...
newtype Type = ...

This allows the abstract syntax for an extension of the language to be formed by taking the union of the base structure with an extension and tying a new recursive knot. For example, to extend the syntax of expressions, the following definitions could be used:

data E2 e = ...
newtype Exp2 = Exp2 (Either (E Exp2 Decl2 Pat Type) (E2 Exp2))
newtype Decl2 = Decl2 (D Exp2 Decl2 Pat Type)

To allow functions traversing abstract syntax to be reused in extensions, they need to be refactored in a similar way. Since no refactoring tools for Haskell were available, this refactoring was achieved by tedious manual work.

For reusable functions, we made use of the class system in Haskell, turning every function intended to be extensible into a method of a class. For example, there was a function to compute the free variables of a piece of syntax

class Free s where free :: s -> [Id]

instance Free Exp where free (Exp e) = free e
instance (Free e,Free d, ...) => Free (E e d p t) where free = ...
...

Refactoring #2

At a later point, it was decided to also make the type of identifiers a parameter in the data types for the abstract syntax.

data Id =
data E i e d p t = ... e ... d ... p ... i ... t ...
data D i e d p t = ...
data P i p = ...
data T i t = ...

newtype Exp i = Exp (E (Exp i) (Decl i) (Pat i) (Type i))
newtype Decl i = Decl (D (Exp i) (Decl i) (Pat i) (Type i))
newtype Pat i = ...
newtype Type i = ...

In this step, also the definition of the classes with methods involving identifiers needed to be changed:

class Free i s | s->i where free :: s -> [i]

instance Free i (Exp i) where free (Exp e) = free e
instance (Free i e,Free i d, ...) => Free i (E e d p t) where free = ...
...

This required the use of multi-parameter classes. The fact that the type of the abstract syntax uniquely determines the type of identifiers is captured with a functional dependency. The number of degrees of freedom thus remains the same, and we avoid introducing type ambiguities.

Again, this refactoring step was implemented manually. It would probably take a rather sophisticated refactoring tool to automate program transformations of this kind...

Demo of the Programatica Tools

The demo included

Using the Programatica Haskell Browser to browse Haskell code in general, including how to find the type of arbitrary identifiers.
A quick overview of the Programatica extension of Haskell with P-Logic.
A quick demo of the evidence management functions of the Haskell browser.

Screen shots and additional details can be found in our Haskell Workshop 2003 Demo Abstract.