Category Archives: tutorial

BuilderBuilder: The Model in Haskell

This post describes the first model in Haskell for the BuilderBuilder task. We will develop the model incrementally until we have rough parity with the Java version.

I’m experimenting with ways to distinguish user input from system output in transcripts of interactive sessions. This time I’m trying color, using a medium blue for output. I will appreciate feedback on whether that works for you.

Step one: defining and using a type

The simplest possible Haskell version of our model for a Java field is:

data JField = JField String String

However, the PMNOPML (“Pay Me Now Or Pay Me Later”) principle says that we’ll regret it if we stop there. In fact, later comes quickly.

We can create an instance of JField in a source file:

field1 = JField "name1" "Type1"

To do the same in a ghci session, prefix each definition with let, as in:

*Main> let field1 = JField "name1" "Type1"

Step two: showing the data

Trying to look at the instance yields a fairly opaque error message.

*Main> field1

<interactive>:1:0:
    No instance for (Show JField)
      arising from a use of `print' at <interactive>:1:0-5
    Possible fix: add an instance declaration for (Show JField)
    In a stmt of a 'do' expression: print it

Remember that in Java the default definition of toString() returns something like com.localhost.builderbuilder.JFieldDTO@53f67e; that’s also obscure at first glance. Haskell just goes a bit further, complaining that we haven’t defined how to show a JField instance. We can ask for a default implementation by adding deriving Show to a data type definition:

data JField = JField String String deriving Show

After loading that change, we get back a string that resembles the field’s defining expression:

*Main> field1
JField "name1" "Type1"

Step three: referential transparency

Our first model represented a Java class by its package, class name, and enclosed fields. The Haskell equivalent is:

data JClass = JClass String String [JField] deriving Show

The square brackets mean “list of …”, so a JClass takes two strings and a list of JField values. I’ll say more about lists in a moment, but first let’s deal with referential transparency.

We can build a class incrementally:

field1 = JField "name1" "Type1"
field2 = JField "name2" "Type2"
class1 = JClass "com.sample.foo" "TestClass" [field1, field2]

or all at once:

class1 = JClass "com.sample.foo"
                "TestClass"
                [   JField "name1" "Type1" ,
                    JField "name2" "Type2"
                ]

and get the same result:

*Main> class1
JClass "com.sample.foo" "TestClass" [JField "name1" "Type1",JField "name2" "Type2"]

As mentioned previously, only one of those definitions of class1 can go in our program. To Haskell, name = expression is a permanent commitment. From that point forward, we can use name and expression interchangeably, because they are expected to mean the same thing. That expectation would break if we were allowed to give name another meaning later (in the same scope).

Consequently, we can define a class using previously defined fields, or we can just write everything in one definition, nesting the literal fields inside the class definition. As we’ll see later, this also has implications for how we write functions; a “pure” function and its definition are also interchangeable.

Step four: lists

The array is the most fundamental multiple-valued data structure in Java; the list plays a corresponding role in Haskell. In fact, lists are so important that there are a few syntactical short-cuts for dealing with lists.

  • Type notation: If t is any Haskell type, then [t] represents a list of values of that type.
  • Empty lists: Square brackets with no content, written as [], indicate a list of length zero.
  • Literal lists: Square brackets, enclosing a comma-separated sequence of values of the same type, represent a literal list.
  • Constructing lists: The : operator constructs a new list from its left argument (a single value) and right argument (a list of the same type).

For example, ["my","dog","has","fleas"] is a literal value that has type [String] and contains four strings. "my":["dog","has","fleas"] and "my":"dog":"has":"fleas":[] are equivalent expressions that compute the list instead of stating it as a literal value.

By representing the fields in a class with a list, we achieve two benefits:

  • The number of fields can vary from class to class.
  • The order of the fields is significant.

Step five: types and records

Given a JField, how do we get its name? Or its type? We can define functions:

fieldName (JField n _) = n
fieldType (JField _ t) = t

and do the same for the JClass data:

package   (JClass p _ _ ) = p
className (JClass _ n _ ) = n
fields    (JClass _ _ fs) = fs

but all that typing seems tiresome.

Before solving that problem, let’s note two other limitations of our current implementation:

  • Definitions using multiple String values leave us with the burden of remembering the meaning of each strings.
  • The derived show method leaves us with a similar problem; it doesn’t help distinguish values of the same type.

If you suspect that I’m going to pull another rabbit out of Haskell’s hat, you’re right. In fact, two rabbits.

Type declarations

We can make our code more readable by defining synonyms that help us remember why we’re using a particular type. By adding these definitions:

type Name     = String
type JavaType = String
type Package  = String

we can rewrite our data definitions to be more informative:

data JField = JField Name JavaType deriving Show
data JClass = JClass Package Name [JField] deriving Show

Record syntax

The second rabbit is a technique to get Haskell to do even more work for us. We represent each component of a data type as a name with an explicit type—all in curly braces, separated by commas:

data JField = JField {
     fieldName :: Name ,
     fieldType :: JavaType
} deriving Show

data JClass = JClass {
     package   :: Package ,
     className :: Name ,
     fields    :: [JField]
} deriving Show

When we use this syntax, Haskell creates the accessor functions automagically, and enables a more explicit and flexible notation to create values. All of these definitions:

field1  = JField "name1" "Type1"
field1a = JField {fieldName = "name1", fieldType = "Type1"}
field1b = JField {fieldType = "Type1", fieldName = "name1"}

produce equivalent results:

*Main> field1
JField {fieldName = "name1", fieldType = "Type1"}
*Main> field1a
JField {fieldName = "name1", fieldType = "Type1"}
*Main> field1b
JField {fieldName = "name1", fieldType = "Type1"}

Step last: that’s it!

We have covered quite a bit of ground! The complete source code for the model appears at the end of this post. With both Java and Haskell behind us, we have most of the basic ideas we’ll need for the Erlang and Scala versions.


Recommended reading:

Real World Haskell, which is also available
for the Amazon Kindle
or on-line at the book’s web site. I really can’t say enough good things about this book.


The current BuilderBuilder mode in Haskell, along with sample data, is this:

-- BuilderBuilder.hs

-- data declarations

type Name     = String
type JavaType = String
type Package  = String

data JField = JField {
     fieldName :: Name ,
     fieldType :: JavaType
} deriving Show

data JClass = JClass {
     package   :: Package ,
     className :: Name ,
     fields    :: [JField]
} deriving Show

-- sample data for demonstration and testing

field1  = JField "name1" "Type1"
field1a = JField {fieldName = "name1", fieldType = "Type1"}
field1b = JField {fieldType = "Type1", fieldName = "name1"}

field2 = JField "name2" "Type2"

class1 = JClass "com.sample.foo" "TestClass" [field1, field2]

studentDto = JClass {
    package   = "edu.bogusu.registration" ,
    className = "StudentDTO" ,
    fields    = [
        JField {
            fieldName = "id" ,
            fieldType = "String"
        },
        JField {
            fieldName = "firstName" ,
            fieldType = "String"
        },
        JField {
            fieldName = "lastName" ,
            fieldType = "String"
        },
        JField {
            fieldName = "hoursEarned" ,
            fieldType = "int"
        },
        JField {
            fieldName = "gpa" ,
            fieldType = "float"
        }
    ]
}

Updated 2009-05-09 to correct formatting and add category.

Advertisements

BuilderBuilder: Haskell Preliminaries

The next step in the BuilderBuilder project is to develop a model in Haskell that is analogous to the Java model in the previous post. This post will introduce just enough Haskell to get started; the next post will get into the BuilderBuilder model.

Environment:

I’m using GHC 6.10.1, obtained from the Haskell web site. There are a variety of platform-specific binaries; I used the classic configure/make/install process on OSX. (For Java programmers, make is what we used instead of ant back in the Jurassic era.) Consult the Haskell Implementations page for details on obtaining Haskell for your preferred platform.

The complete development environment consists of two windows: one running a text editor, and the other running ghci, the interactive Haskell shell that comes with GHC.

Haskell introduction:

Use your text editor to create a file named bb1.hs with this content:

-- bb1.hs

-- simplest possible data declarations

data JField = JField String String

-- sample data for demonstration and testing

field1 = JField "id" "String"

-- sample function

helloField :: JField -> String
helloField (JField n t) = "Hello, " ++ n ++ ", of type " ++ t

Then run ghci as follows, where user input is underlined:

your-prompt-here$ ghci
GHCi, version 6.10.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> :l bb1.hs
[1 of 1] Compiling Main             ( bb1.hs, interpreted )
Ok, modules loaded: Main.
*Main> helloField field1
"Hello, id, of type String"
*Main> 

We started ghci, told it to load our source file (the :l … line), and then invoked the helloField function on the sample field. Now let’s examine the Haskell features used in that code. The lines beginning with double-hyphens are comments, and will be ignored in the description.

Defining data types

Because Haskell emphasizes functions, it’s no surprise that the syntax for defining data types is very lightweight. The Java BuilderBuilder model represents a field with two strings, one for the name and one for the type. The simplest possible Haskell equivalent is:

data JField = JField String String

This defines a data type named JField. It has a constructor (also named JField) that takes two strings, distinguished only by the order in which they are written.

Defining values

The next line of code defines an instance of this type:

field1 = JField "id" "String"

The equal sign means “is defined as“. That statement defines field1 as the instance of JField constructed on the right-hand side. It is not declaring and initializing a mutable variable. Within the current scope, attempting to redefine field1 will produce an error. (More about scope later.)

Defining functions

Finally, we have a simple function that converts a JField to a String.

helloField :: JField -> String
helloField (JField n t) = "Hello, " ++ n ++ ", of type " ++ t

Everything in Haskell has a type, including functions. The double colon means “is of type“, so the type of helloField is function from JField to String.

The value of applying helloField to a JField containing strings n and t is defined by the expression on the right-hand side. Haskell regards strings as lists of characters; the ++ operator concatenates lists of any type. The names n and t are only meaningful within that definition, similar to the local variables in this Java fragment:

public static String helloField(IJField f) {
    String n = f.getName();
    String t = f.getType();
    return "Hello, " + n + ", of type" + t;
}

Type inference

Java requires that we explicitly declare the local variables as type String. But in Haskell, because JField is specified to have two String values, the compiler can infer the types of n and t In fact, the entire first line of helloField is not necessary. The defining equation in the second line explicitly uses a JField on the left and constructs a String on the right. Therefore, the compiler can infer JField -> String as the type of the function. Haskell’s type inference allows us to write very compact code without giving up strong, static typing.

To see that in action, add the following line to the end of your bb1.hs file:

hiField (JField n _) = "Hi, " ++ n

(The underscore is a wild card, showing the presence of a second value but indicating that we don’t need it in this function.)

Reloading bb1.hs in ghci allows us to see type inference at work.

*Main> :l bb1.hs
[1 of 1] Compiling Main             ( bb1.hs, interpreted )
Ok, modules loaded: Main.
*Main> hiField field1
"Hi, id"
*Main> :type hiField
hiField :: JField -> [Char]

As we’ll see later in this series, Scala brings type inference to the JVM environment. Coming from the dynamic language side, the Diamondback Ruby research project is adding type inference to Ruby. So perhaps type inference is (finally) an idea whose time has come.

We’ll pick up more Haskell details along the way, but we have enough to start defining our first BuilderBuilder model. That will be the subject of the next post.


Updated 2009-05-09 to fix formatting.

BuilderBuilder: The Model in Java

This post will describe a tiny Java model for implementing the BuilderBuilder task. It is simple almost to the point of crudity, because the goal of the series is to compare languages and styles, not to produce production-ready sample code.

This post will focus on the parts of the overall data flow highlighted below:

GenerationModel.jpg

The interfaces:

I’m using interfaces to hide implementation from the remainder of the code. The first version will use simple DTOs, but I want to leave other options (e.g. by reflection against existing DTO classes) open for later exploration.

This first model has two interfaces; one for a Java class:

package com.localhost.builderbuilder;

public interface IJClass {
    public String getPkg();
    public String getName();
    public IJField[] getFields();
}

and the other for a Java field:

package com.localhost.builderbuilder;

public interface IJField {
    public String getName();
    public String getType();
}

We all know that “the simplest thing that could possibly work” doesn’t mean “the stupidest thing that could possibly work”. The use of an array may cross that line, but it was a deliberate choice. Developers who moved to OOP from imperative programming are very familiar with arrays. We’ll be able to compare array processing against the FP style of list processing, and perhaps consider other OOP alternatives later on.

First implementations:

In the spirit of eating our own dog food, the simple DTO implementation of those interfaces will contain their own Builder inner classes. Given that, there’s no surprise in the JFieldDTO code, which appears at the end of this post.

The JClassDTO class throws in one new wrinkle—instead of having a fields(IJField[] fields) method that accepts an entire field array, JClassDTO.Builder provides a field(IJField field) method that accepts one field at a time, accumulating them to be placed in an array by the instance() method. The complete code for JClassDTO is given at the end.

It remains to be seen whether this DTO-style implementation is throw-away code, but getting a first implementation in hand will allow us to start comparing data types and structures with the other language, and then move directly to the generation phase of the project. We can always come back and add features (and complexity 😉 ) at a later time.


Recommended reading:


The JFieldDTO implementation:

package com.localhost.builderbuilder;

public class JFieldDTO implements IJField {

    private final String name;
    private final String type;

    public static class Builder {
        
        private String name;
        private String type;

        private Builder() {
            // do nothing
        }

        public Builder name(String name) {
            this.name = name;
            return this;
        }

        public Builder type(String type) {
            this.type = type;
            return this;
        }

        public JFieldDTO instance() {
            return new JFieldDTO(name, type);
        }
    }

    public static Builder builder() {
        return new Builder();
    }

    private JFieldDTO(String name, String type) {
        this.name = name;
        this.type = type;
    }

    public String getName() {
        return name;
    }

    public String getType() {
        return type;
    }

}

The JClassDTO implementation:

package com.localhost.builderbuilder;

import java.util.ArrayList;
import java.util.List;

public class JClassDTO implements IJClass {

    private final String pkg;
    private final String name;
    private final IJField[] fields;

    public static class Builder {
        
        private String pkg;
        private String name;
        private List<JFieldDTO> fields;

        private Builder() {
            fields = new ArrayList<JFieldDTO>();
        }

        public Builder pkg(String pkg) {
            this.pkg = pkg;
            return this;
        }

        public Builder name(String name) {
            this.name = name;
            return this;
        }

        public Builder field(JFieldDTO field) {
            this.fields.add(field);
            return this;
        }

        public IJClass instance() {
            return new JClassDTO(
                pkg,
                name,
                fields.toArray(new JFieldDTO[fields.size()])
            );
        }

    }

    public static Builder builder() {
        return new  Builder();
    }

    private JClassDTO(String pkg, String name, IJField[] fields) {
        this.pkg = pkg;
        this.name = name;
        this.fields = fields;
    }

    public String getPkg() {
        return pkg;
    }

    public String getName() {
        return name;
    }

    public IJField[] getFields() {
        return fields;
    }

}

Updated 2009-05-09 to fix some formatting and to add a category.

BuilderBuilder: The Task

Short version:

Given minimal information (package, class name, and collection of fields described by name and type), produce Java source for a data transfer class, including a static inner class that functions as a builder.

The data flow of this task looks like this:

GenerationDataFlow.jpg

Given data in a specified input format, a loader will consume the input to produce a model of the class and fields. A code generator will consume the model and produce Java source. The “direct construction” case allows model instances to be produced by code without the need for source data.

Long version:

Data transfer objects (described here) may be used to pass data across boundaries (between systems via network, between Java and non-Java systems, etc.) Developers supporting the Registrar’s office at Bogus University might create a data transfer class representing a student, beginning as follows:

package edu.bogusu.registration;

public class StudentDTO {
    private String id;
    private String firstName;
    private String lastName;
    private int hoursEarned;
    private float gpa;
    // ... other fields
    // ... construction method(s)
    // ... get methods
}

Constructing an instance of StudentDTO is commonly done in one of two ways:

  1. calling a constructor that has a parameter for every field, or
  2. calling a no-argument constructor, then calling a set… method for every field.

The first approach can minimize clutter in the client code that creates a StudentDTO and, more importantly, makes it easy for StudentDTO to be immutable. But as the number of fields grows, so does the parameter list to the constructor call; it becomes ugly and potentially error-prone. The second approach makes the initialization more explicit, at the cost of losing immutability. For this series, we’re going to go through door number three.

Enter The Builder

We’ll create another class whose job is to construct StudentDTO instances. Making it a static inner class to StudentDTO allows us to keep the construction machinery private, giving us more control over the way clients obtain an instance. It also allows us to re-use the idea without name bloat; any FooDTO can have an associated FooDTO.Builder.

Usage

The code is a bit tedious, so we’ll begin with a sample of the intended usage.

StudentDTO student = StudentDTO.builder()
    .id(ID)
    .firstName(FIRST_NAME)
    .lastName(LAST_NAME)
    .hoursEarned(HOURS_EARNED)
    .gpa(GPA)
    .instance();

The static method StudentDTO.builder() provides an instance of the inner Builder class. There is a method on Builder for each field of StudentDTO. Each of those methods returns the Builder instance, allowing the chaining shown in the sample. Finally, the instance() method returns an instance of StudentDTO

The net effect is that of a constructor method with named parameters; we can provide them in whatever order we wish, and can even do the initialization in stages:

StudentDTOBuilder studentBuilder = StudentDTO.builder()
    .id(ID)
    .firstName(FIRST_NAME)
    .lastName(LAST_NAME);
// some tedious computation of HOURS_EARNED
studentBuilder.hoursEarned(HOURS_EARNED);
// some tedious computation of GPA
studentBuilder.gpa(GPA);
// and finally
StudentDTO student = studentBuilder.instance();

(I’m not suggesting that we should use it that way; just demonstrating the flexibility of the technique.)

The Code

There’s a high level of redundancy, so I’ll post just enough to show how the code is organized; the remainder should be obvious.

package edu.bogusu.registration;

public class StudentDTO {

    private String id;
    private String firstName;
    private String lastName;
    private int hoursEarned;
    private float gpa;

    public static class Builder {
        
        private String id;
        // etc. for all StudentDTO fields
        private float gpa;

        private Builder() {
            // nothing here
        }

        public Builder id(String id) {
            this.id = id;
            return this;
        }

        // similar methods for the other fields

        public Builder gpa(float gpa) {
            this.gpa = gpa;
            return this;
        }

        public StudentDTO instance() {
            return new StudentDTO(
                    id,
                    firstName,
                    lastName,
                    hoursEarned,
                    gpa
            );
        }
    }

    public static Builder builder() {
        return new Builder();
    }

    private StudentDTO(
            String id,
            String firstName,
            String lastName,
            int hoursEarned,
            float gpa
    ) {
        this.id = id;
        this.firstName = firstName;
        this.lastName = lastName;
        this.hoursEarned = hoursEarned;
        this.gpa = gpa;
    }

    public String getId() {
        return id;
    }

    // all StudentDTO fields have get methods

    public float getGpa() {
        return gpa;
    }

}

Just a few key points before closing:

  • The constructors are private to control instance creation. Client code never uses new... () for either class. In addition, we can later address the question of making sure that all required data are present, so that a “half-baked” instance is never created.
  • Each StudentDTO field is shadowed in StudentDTO.Builder. This represents the “work-in-progress inventory” without creating an inconsistent or incomplete object.
  • The ugliness (and risk) of a zillion-parameter constructor for StudentDTO is hidden from the client. Only the generator needs to see that monster.
  • Much of the redundancy is driven by Java’s approach to explicit, static typing. Code generation will keep the many repetitions of the same information in synch.

That’s enough to get a simple version of the problem on the table. Next time, we’ll begin looking at internal representations: first in Java, then in Haskell, Erlang, and Scala.


Recommended reading:

BuilderBuilder: The Agenda

The “BuilderBuilder” posts will be my exploration of one question: “What does Functional Programming mean to me as a practicing OO software developer?” Despite contemporary buzz about how FP will save the world from bugs and single-threaded code, I don’t want to read (or write) another clever Fibonacci number generator, or another theoretical explanation of category theory and monads. I want to see what FP is like when it sits down the aisle from me in work clothes.

To pursue that goal, I’m going to explore a programming problem that meets these criteria:

  1. Its purpose would be recognizable to a working programmer.
  2. It is large enough that a clever one-liner won’t suffice.
  3. It isn’t (consciously) chosen to cater to either OO or FP.
  4. It will require me to try things outside my daily comfort zone.

That last point means that I’ll make mistakes and do stupid things. I hope the record, warts and all, helps someone else (including me, later on) avoid them.

The problem I’ve chosen is a specific code generation task, which I’ll describe in the next post. There is a wide range of opinions on source code generation, but source code is one thing that any programmer understands, regardless of other application domain specialization.

Because my goal is exploration, and I’m starting with unequal familiarity with the languages I’ll use, the code almost certainly won’t be idiomatic or make best use of all available libraries. In fact, I’ll probably do more than necessary “by hand” to avoid bias toward more familiar tools. I may be able to address some of that along the way, based on accumulated experience (or helpful feedback, hint, hint… ;-).

OK, enough meta-talk. Next up, the task.

Design by proof

The idea of proving programs correct has been around (and hotly debated) for roughly forty years. The irony is that some proof advocates anticipated by more than thirty years what the agile advocates are now saying:

Designing with verification in mind improves the quality of the resulting design.

To be even more specific, compare these statements:

Design the proof,
then write the code so that
it meets the obligations of the proof.
  Write the test first,
then write the code so that
it passes the test.
Edsger Dijkstra   (paraphrased)   Kent Beck   (paraphrased)

I’ve experienced the benefits of following both pieces of advice. Let me apply this approach to a little bit of design which I’ll then use in the Project Euler series. There’s a small amount of algebra involved, but if you don’t want to bother with that, let me request that you at least look at the last section for the punchline.

Sum thing

Consider the following sums, where i in each case ranges from 1 to n:

Power Sum Expanded form Closed form Factored form
0 ∑ i0 1 + 1 + 1 + … + 1 n1 n
1 ∑ i1 1 + 2 + 3 + … + n 1/2 n2 + 1/2 n1 n(n+1)/2
2 ∑ i2 12 + 22 + 32 + … + n2 ?
3 ∑ i3 13 + 23 + 33 + … + n3 ?

Let’s assume that we need the solutions for the last two rows (and Google is down at the moment 😉 ). Using the “designing with verification in mind” approach, we can work them out for ourselves.

Sum of squares

Noticing that ∑ i0 is a polynomial of degree 1, and ∑ i1 is a polynomial of degree 2, we might suspect that the sum of i2 is a polynomial of degree 3. If so, the problem amounts to finding the coefficients for ∑ i2 = an3 + bn2 + cn + d. Let’s assume that as the structure of the solution, and apply test cases to that assumption.

Test case 0: The sum must be zero when n is zero; a03 + b02 + c0 + d = d, therefore d must be zero. That streamlines the polynomial to ∑ i2 = an3 + bn2 + cn.

Test case 1: Adding (n+1)2 to the sum for n must be equal to the result of substituting (n+1) for n in the polynomial.

  an3 + bn2 + cn + (n+1)2
an3 + (b+1)n2 + (c+2)n + 1
and  
  a(n+1)3 + b(n+1)2 + c(n+1)  
an3 + (3a+b)n2 + (3a+2b+c)n +(a+b+c)

These two reduced expressions can only be equal if we can satisfy the equations implied by the coefficients for n2, n1, and n0:

n?   Coefficients   Satisfied if
n2   b+1 = 3a+b   a = 1/3
n1   c+2 = 3a+2b+c   b = 1/2
n0   1 = a+b+c   c = 1/6

So we have a solution of 1/3 n3 + 1/2 n2 + 1/6 n, which we can factor to n(n+1)(2n+1)/6.

Sum of cubes

Based on that success, we’ll pursue the coefficients for ∑ i3 = an4 + bn3 + cn2 + dn + e.

Test case 0: The sum must be zero when n is zero; a04 + b03 + c02 + d0 + e = e, therefore e must be zero, therefore ∑ i3 = an4 + bn3 + cn2 + dn.

Test case 1: Adding (n+1)2 to the sum for n must be equal to the result of substituting (n+1) for n in the polynomial.

  an4 + bn3 + cn2 + dn

+ (n+1)3
an4 + (b+1)n3 + (c+3)n2 + (d+3)n + 1
and  
  a(n+1)4 + b(n+1)3 + c(n+1)2 + d(n+1)  
an4 + (4a+b)n3 + (6a+3b+c)n2 + (4a+3b+2c+d)n + (a+b+c+d)

Again, we look at the coefficients for descending powers of n:

n?   Coefficients   Satisfied if
n3   b+1 = 4a+b   a = 1/4
n2   c+3 = 6a+3b+c   b = 1/2
n1   d+3 = 4a+3b+2c+d   c = 1/4
n0   1 = a+b+c+d   d = 0

So we have a solution of 1/4 n4 + 1/2 n3 + 1/4 n2, which we can factor to (n(n+1)/2)2.

The punchline

“That’s no exponential, that’s my polynomial!” But seriously, folks…

The mathematicians among us–those who haven’t died of boredom–will recognize what we’ve done as an informal (hand-waving) inductive proof.

But I hope that the programmers among us will recognize what we’ve done as test-driven development and (re)factoring. Allowing verification to drive design offers a number of benefits, including:

  • The result itself is verifiable.
  • Each step along the way is more obvious and involves less risk.
  • The result is usually cleaner and more understandable.

Incidentally, I first encountered the term “factoring” applied to programs in Leo Brodie‘s book Thinking Forth (1984). Given my background in Mathematics, it immediately clicked with me. Brodie introduced the idea with a quotation which seems entirely contemporary, once we get past the dated terminology:

“If a module seems almost, but not quite, useful from a second place in the system, try to identify and isolate the useful subfunction. The remainder of the module might be incorporated in its original caller.”

(The quotation is from “Structured Design“, by W.P. Stevens, G.J. Myers, and L.L. Constantine, IBM Systems Journal, vol. 13, no. 2, 1974, © 1974 by International Business Machines Corporation)

As a working developer, I’m excited by the potential of these techniques and the underlying ideas. But as a card-carrying member of the Sid Dabster fan club, I’m constantly amazed at the number of ideas that were actively in play in our field thirty or forty years ago that are now regarded as new, innovative, or even radical.


Recommended reading:

Why functional programming?

The canonical answer to that question is probably “Why functional programming matters“, but here’s a specific example that makes the case nicely.

Neil Mitchell is working on Supero, an optimizing compiler for Haskell which includes some ideas from supercompilation. But that’s not important right now.

What is important is the technique Mitchell uses in the blog post at the second link above. Algebra. As in junior-high-Algebra-I-algebra. The old “if a = b then you can substitute either one for the other” kind of Algebra.

Functional programming is based on defining functions.

  def square(i: Int) = i * i

In pure functional programming, where side-effects are not allowed (or at least kept securely behind bars), you can treat that definition as an equation; wherever you see square(foo) you can rewrite it as (foo * foo) and vice versa. This applies even when foo is an arbitrarily complex expression (don’t worry about operator precedence or extra parentheses right now; that’s not the point).

The point is that you can’t do that with confidence for impure (i.e., having side-effects) languages. Consider trying that replacement in something as simple as…

  n = square(++i);

…which clearly is not the same as…

  n = ++i * ++i;

…at least in most cases. Are there any special cases where it’s the same? Would the answer be different if the enclosed expression had been i++ instead?

If you even had to think about it for one millisecond (or, like me, thought “That’s ugly! I’ll think about it later!”) that’s exactly the point. In a pure language the question can’t even come up. You’re free to do the rewriting, either way, any time.

(Fair warning: You don’t need to know Haskell to read Mitchell’s post, but it helps. Even if you don’t, it’s worth the little bit of time it takes to work through his example. The cheat sheet at the bottom of this post is a quick introduction for non-Haskell-speaking readers, or non-Haskell-reading speakers.)

Mitchell takes a simple task, breaking a string into a list of words, and shows a simple and obvious function for the task. However, that simple and obvious function ends up with redundant “is it a space?” tests against some characters. Mitchell does a bit of refactoring, using simple substitute-equals-for-equals steps, to track down and eliminate the redundance, resulting in an equivalent (still simple) function that runs faster.

All of this is based on the facts that:

  • more powerful functions can be composed out of simpler ones, and
  • pure functions ensure that the obvious substitutions work.

For me this makes a powerful demonstration of the benefits of the functional approach, whether I’m using Haskell, Scala, or even a non-FP language such as Java. (Not only does functional programming matter, knowing why functional programming matters matters as well.)


Cheat sheet

For newcomers to Haskell notation, here’s a bit of explanation. Please don’t hold the length (or any shortcomings) of my explanation against Haskell. I’m assuming a reader who’s never seen Haskell before (or any similar language), and so say something about almost every token. Feel free to skip the obvious, with my apologies.

Mitchell’s analysis works on this original function…

  words :: String -> [String]
  words string = case dropWhile isSpace string of
                     [] -> []
                     s -> word : words rest
                         where (word, rest) = break isSpace s

…which breaks a string into a list of words (strings).

The special-character soup isn’t really that bad, if you use your Captain Zowie decoder ring. It helps to know three facts:

  • indentation shows nested structure, instead of using curly braces,
  • function application doesn’t require parentheses, and
  • a Haskell String can be considered as a list of characters.

The first line…

  words :: String -> [String]

…declares the type of words as function from string to list of strings. Specifically:

  • the double-colon can be read “has type”,
  • the arrow indicates a function taking the type on the left, yielding the type on the right, and
  • the square brackets on the right read “list of”.

The second line…

  words string = case dropWhile isSpace string of

…starts the definition of words, using a parameter named string (which we already know is of type String from the first line). The phrase…

  dropWhile isSpace string

…returns a left-trimmed version of string. It applies isSpace to successive elements of string, repeating as long as the result is true, and returns what’s left (either because there’s nothing left or because a character is found for which isSpace is false). It does so without modifying the original string, just as String#substring does in Java. That left-trimmed (sub-)string is then subjected to a case analysis, by way of pattern matching.

Remember that the result of left-trimming was produced either because there were no characters left, or because a non-space character was found. Therefore, there will be two cases to consider. The line reading…

  [] -> []

… reads “if you have an empty list (of characters) then return an empty list (of Strings)”. We (and the Haskell compiler!) can infer the parenthesized types because we know that trimming a string produces the String (list of characters) being inspected, and the type declaration on the first line says that the function produces a list of String.

The last two lines address the case in which there actually were some characters left after trimming.

  s -> word : words rest
      where (word, rest) = break isSpace s

For a non-empty string s… Wait! What’s s and how do we know it’s a non-empty string? Remember that we’re in a case (glance back at the original above to see the indentation) and we’ve already eliminated the possibility that the trimmed string we’re examining is empty. So the value in hand must be non-empty. And pattern matching give us the ability to name things on-the-fly, more or less the equivalent of defining a local variable in e.g. Java. So, as I was saying before I so rudely interrupted myself…

For a non-empty string s, the result is a word followed by the words from the rest of the string, where those two things (word and rest) are constructed by breaking s at the first space (the first character for which the function isSpace returns true). The single-colon is often read as “cons”, in homage to Lisp. It constructs a list (of some type) by gluing a value (of the correct type) onto the beginning of a list (of the same type). Becuase word is a String and words rest is a list of String, the entire expression word : words rest is also a list of String.

Notice that both dropWhile and break have two arguments: another function (isSpace in both uses here) and a list. This works because dropWhile and break are higher-order functions, which take functions as arguments and use them whenever needed. If you cross your eyes and squint a little, this begins to look like design patterns in OO.