Don’t return null; use a tail call

Why should an object-oriented programmer care about tail-call elimination? Isn’t that just another esoteric functional programming concept? Maybe not.

Back when dinosaurs roamed the earth, a common technique for performing a subroutine call worked this way:

1. The caller stored the address at which it wished to resume execution in a known place (e.g. adjacent to the called routine’s code);
2. The caller branched to the called routine’s entry address;
3. Upon completion, the called routine branched indirectly to the stored return address.

Of course, this technique precluded both recursive and re-entrant calls, but those were regarded as esoteric, theoretical concepts with little if any practical use (see the “Historical Footnote” below). Times change, but programmers are still living with constraints whose roots go back to the kinds of mechanism described above. We all know that a simple and correct recursive routine can still founder on the stack overflow reef. But I recently saw a blog post by Zachary D. Shaw that rubbed a bit more salt in that wound.

His post on Returning Null discusses an alternative to the common idiom of returning a null result as a way of saying “not found”. In his post, the caller passes itself as an argument (using a suitable interface type, of course), and the callee responds by invoking either a “found” or “not found” method on the caller. This models the interaction as an exchange of specific and appropriate messages, instead of encoding the “not found” case in an abnormal value which the caller must decode in order to determine what to do.

I’m currently enjoying the book Growing Object-Oriented Software, Guided by Tests by Steve Freeman and Nat Pryce, of mock objects fame. That book reminded me of the value of separating the design concept of passing messages from the implementation detail of writing methods. It would be nice to be able to use such a technique without stack depth raising its ugly little head as an issue, however fleeting.

Simon Harris posted on this issue from a Ruby perspective, and Guy Steele’s Fortress blog has an elegant illustration in that language. Of course, Steele’s 1977 paper is the ultimate resource on the subject. Even the name of that paper has had its influence.

---

Historical Footnote: The November 1963 issue of Communications of the ACM contained a short piece entitled “Recursive programming in Fortran II“. Membership is required to download the PDF, but you can get a sense of the attitudes of the time just by reading the abstract on the linked page.

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.

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:

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:

• Anything by “Uncle” Bob Martin.
• The origin of the Model-View-Controller (MVC) paradigm.

---

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.