TITLE: Refactoring, Functional Programming-Style
AUTHOR: Eugene Wallingford
DATE: November 02, 2007  1:24 PM
DESC: 
-----
BODY:
Back in 2002, I had a sabbatical (which are, for political
reasons, called "professional development assignments" here)
to document some of the patterns of
programs that are written in a functional style.  So much
good work had been done by then on object-oriented patterns,
and a few people had begun to describe OO patterns that
were motivated by functional programming techniques.  But
few people had begun to document functional programming
patterns.  I had a feeling that something useful could come
from moving into that space.  In the end I didn't make the
sort of progress I had hoped, but I did learn a lot that has
continued to influence my teaching and research.

One of the areas explored as a part of that project was
refactoring functional programs.  I believe that refactorings
are the behavioral side of patterns, and by looking at work
on existing work on functional refactorings I hoped to speed
my search for patterns.  There hadn't been much work done on
refactoring functional programs at that time, but I wasn't
alone in thinking of it -- Simon Thompson and Claus Reinke
were just beginning their quite productive
<A HREF="http://www.cs.kent.ac.uk/projects/refactor-fp/">
   research program</A>
on the same topic.  That work, like most of the work that
deals with patterns and refactoring in functional programming,
focused more on the language-processing side of the topic,
considering refactorings as program transformation in the
vein of compiler optimizations.  What seems to me still to
be missing is a look at refactoring of functional programs
from the software developer's perspective:  I have a piece
of code that I want to restructure in order to improve its
design, or in order to facilitate the next addition to the
program.  What do I do next?

<A HREF="http://www.untyped.com/untyping/">
   <IMG SRC="http://www.cs.uni.edu/~wallingf/blog-images/misc/untyped-logo.gif"
        ALT="the logo of Untyped, a software firm"
        ALIGN="right"
        WIDTH="100"></A>

Noel Welsh recently wrote a blog entry called
<A HREF="http://www.untyped.com/untyping/archives/2007/08/refactoring_fun.html">
   Refactoring Functional Programs</A>
that makes a very nice contribution in the space.  Noel is
just the sort of person who should be documenting FP patterns
and refactorings, a practicing developer who works primarily
in a functional or mostly functional language and who is
growing a significant software system over time.  His essay
talks about a sequence of refactorings that he applied to his
system, a web application framework, which moved one of its
modules from a long-ish, overly complex, repetitive piece of
code to something shorter, simpler, and well-factored.  You
will enjoy reading the article even if you don't program in
Scheme, because Noel explains the thinking he did as he
attacked this piece of code, including an alternative step
that he considered but rejected due to the forces that affect
his system.

For the record, his three refactorings were these.  The names
are part mine, part his:
<UL>
<LI> convert mutually tail-recursive state machine to
     continuation-passing style </LI>
<LI> separate computational abstraction from control abstraction </LI>
<LI> convert continuation-passing style to direct style
</UL>

One of the things I like about this story is how it makes a
"round-trip" to CPS and back, using the trip to change the
program's design in a way that might have been inaccessible
otherwise.  I teach my students a similar "refactoring pattern"
when teaching them functional programming, make a round-trip
through
<A HREF="http://www.cs.uni.edu/~wallingf/patterns/recursion.html#3">
   Mutual Recursion</A>,
by way of
<A HREF="http://www.cs.uni.edu/~wallingf/patterns/recursion.html#7">
   Program Derivation</A>,
to convert a messy one-procedure solution into a clean and
one-elegant one-procedure solution.

I hope that other developers using functional programming in
the trenches will follow Noel's lead and document some of the
patterns and refactorings that they discover in their code and
process.  More than anything else, this sort of pragmatic,
nuts-and-bolts writing will help to increase the accessibility
of functional programming style to a wider audience of
programmers.
-----