Category Archives: Java

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.

Jesse Tilly at Memphis JUG

This month’s Memphis Java Users’ Group meeting featured Jesse Tilly of IBM Rational Software, who spoke to us on static analysis. He will be doing a more product-intensive session, “What is IBM® Rational® Software Analyzer® Telling Me?”, at the upcoming IBM Rational Software Conference. (Don’t be misled by all those “circle-R”s; I just linked to the title from the conference web site.)

For our meeting, Jesse left the branding iron at home. He began with an overview of the history and benefits of static analysis. The major portion of the presentation offered a practical approach to analysis as part of a development project, including a detailed how-to on interpreting and using analysis results. Jesse finished with return to history, drawing unexpected parallels with the analysis of Enigma traffic at Bletchley Park during WWII—the background for Allen Turing‘s later theoretical work that led to the computers we program today.

Because Jesse had an early flight, our regular door-prize drawing followed his presentation. In our lightning talk segment, Matt Stine introduced Morph AppSpace, I presented on “Structured Functional Programming” (pdf here), and Walter Heger gave a quick look at jGears.


Recommended reading:

Encryption and cryptanalysis are deeply entwined with computing, whether in history(Codebreakers: The Inside Story of Bletchley Park) or in imagination (Cryptonomicon).

Two highly-respected tools for static analysis in Java are FindBugs and PMD; both web sites offer excellent documentation and other reference material.

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:

Jared Richardson at Memphis JUG

I’ve been very happy with the progress of the Memphis Java Users’ Group under Matt Stine‘s leadership, and last night kicked it up a notch, with a visit by Jared Richardson, author of Career 2.0 and Ship It!, and NFJS speaker!

Jared’s talk on refactoring your career was full of practical advice, engagingly presented …

Just stop right there! This is your Second-Guessing-Self speaking. Do you realize that you’re starting to gush? Even worse, you’re breaking my adjective-per-paragraph rule. Don’t tell your readers what to think! Just give them the facts and let them draw their own conclusions.

But S-G-S, I really enjoyed his talk, and—judging from their reactions—so did everyone else there. He even had Diane talking back to him, and you know how shy and retiring she is.

I’m more concerned about looking professional than about your enjoyment. Be objective!

Whatever…

Jared covered a rich list of specific suggestions for developing one’s writing and speaking skills; he also discussed a variety of contributions to open-source projects as a way to build visibility, reputation, and connections. These topics were all illustrated with examples from his own career, such as how he wrote the JUnit totorial that’s a front-page Google result.

The evening was rounded out with a discussion of goals and how to set and achieve them.

I have to say that hearing Jared was one the most enjoyable—but effective—kick in the seat of the pants I’ve had in quite a while! (Take that, S-G-S!)

Those who heard him speak (especially his advice on writing 😉 ) will understand when I say, “Thanc yew, Jerrid Rytszchurdsen!”