Too much of a good thing: not all functions should be object methods OOP is several different ideas put together, the most important of which is Fine-Grained Information Hiding.

One can think of information hiding as being the principle and encapsulation being the technique. A software module hides information by encapsulating the information into a module or other construct which presents an interface.

The basic principle of all OO languages is that relatively small things—such as individual accounts in a business program—each encapsulate both their data (in the form of members) and their algorithms (in the form of methods). Our notions of members and polymorphism both work to this goal of hiding information. There’s a lot more to most OO languages, such as whether they include a notion of types and what mechanisms they use for sharing common behaviour. But let’s look at this one principle: objects are responsible for their data and for their algorithms.

should objects be responsible for all of their own behaviour?

There’s a general idea that in a well-constructed program, each object “knows” how it ought to behave. That’s what its methods are for. Quite obviously, objects cannot be responsible for everything involving them in a program. If each object completely encapsulated all of the things it could do or be involved in, you would never pass one object as a parameter in a message to another object.

For every complex problem, there is a solution that is simple, neat, and wrong.

For example, you would never have collections. If every object “knew” how to organize itself into collections, you wouldn’t need an Array or Hash, would you? In practice, each object in a system can be involved in many different actions. It has to be responsible for some of them, and it has to play a secondary, passive role in others. Most OO programs do not have every object implement its own collections methods. They may include some form of specialization so you can have an array of accounts, but an array of accounts is still not an account.

subject.verb(object)

In the English language, we have the idea of a Subject and an Object in a sentence. For example, when we say “Jack loves Jill,” Jack is a subject and Jill is an object. Jack loves. Jill is loved. It’s the same in OO programs. Sometimes objects are actively doing things through their methods. Sometimes other object’s methods are doing things with them.

Verbing Weirds Language

Good OO design is, in part, doing a good job of choosing the right bifurcations: given a list of nouns and verbs, making the right decisions about which nouns ought to be the active nouns, the subjects, the ones that “own” the verb in the form of a method. And thus consciously making decisions about which objects ought to be the passive nouns, the objects of the verbs, the ones that don’t implement the methods.

Unfortunately, there are lots of places where we can err on the side of giving too much responsibility to individual objects. It’s understandable, given that OO is theoretically all about objects being responsible for themselves. But as in many other things, in practice good OO is about objects being responsible for a little as possible (but no less!), not as much as possible.

the kingdom of nouns

One common symptom of this problem is a system that has objects for all of the obvious nouns or entities, but not for the verbs. OO began with languages like Simula, where the paradigm was trying to represent real-world entities such as automobiles on a highway. From that time forward, the emphasis has been on having objects for each noun in the problem domain. In such traditionally-organized OO programs, the “verbs” or actions are all attached to objects as methods.

Not all “verbs” have a clear separation between a single entity that is the subject or active entity that ought to own the verb’s definition and the secondary, passive subject entities that should not own the verb’s definition. The easiest examples of this are operations that are intended to be commutative.

For example, many languages define addition as a method belonging to numbers or magnitudes. In Smalltalk, the expression 1 + 2 actually means “send the message + 2 to the object 1.” At first glance, this seems elegant: the number 1 handles the message + 2 as integer addition, while 1.0 would handle the same message with floating point arithmetic. What more could you want?

Well, there is a huge problem with this arrangement: Addition is commutative. 1.0 + 2 must give the same result as 2 + 1.0. Using a simple message to implement addition means that you must be excruciatingly careful to handle all of the possible cases so that you do not accidentally violate this property. Now of course, the designers of system classes like Integer and Float went to this trouble. But if you want to add another magnitude class—say CurrencytwoPlaceDecimal—you have to open up all of the system classes and modify them so that 1 + ThirtyCents gives the same result as ThirtyCents + 1.

beware of breaking symmetry

Of course, you may not need to implement a new magnitude class. Fine. But what about symmetric relations like comparison? This is a major pitfall for OO developers: in many cases you need to write a test of equivalence or equality (operations like ==, equal?, eql?, eqv? and all of the other variations on the same theme). In every one of these cases, horrible things will happen if your operation is not symmetric. For every case, x.eql?(y) if-and-only-if y.eql?(x).

This is obviously easy when x and y are both the same kind of object. What happens when they’re different, but still logically equivalent? It turns out that implementing commutative operations and symmetric relations as methods doesn’t work very well. It forces you to smear duplicate logic over many different classes (or prototypes, if your language swings that way).

Here’s a practical example. Let’s say you want to implement a form of equivalence for collections. For ordered collections like lists, what you want is that if two ordered collections have the same members, in the same order, they are equivalent. It’s easy to imagine writing such a method as a mixin for all of your ordered collections. It obviously knows about iterating over ordered collections (recursively, if you grew up with Godel, Escher, Bach on your night stand). Note that you may not have an indexed collection: you might have a list where you simply retrieve values in order.

And likewise, you can write a collection equivalence method for dictionaries like hash tables: if two objects have the same values at the same keys, they are equivalent. Again, a simple mixin will handle things for dictionaries.

Now comes the wrinkle: you decide that an ordered collection ought to be equivalent to a dictionary where the keys are the integers ascending from zero. In other words, ('foo' 'bar' 'blitz') ought to be equivalent to { 0 => 'foo', 1 => 'bar', 2 => 'blitz' }. How are you going to code this? Well, the dictionary mixin could obviously handle equivalence to an ordered list. But we need symmetry, so we have to “open up” the ordered collection mixin and add code for equivalence to dictionaries.

Actually I made up the term object-oriented and I can tell you I did not have C++ in mind. The important thing here is that I have many of the same feelings about Smalltalk.

I’m holding my nose, we have not one but two different code smells: 1) Why is one piece of logic in two different places? 2) Why do ordered collections know anything at all about dictionaries, and why do dictionaries know anything at all about ordered collections? The latter is especially disturbing: the whole point of OO is information hiding. How does having ordered collections and dictionaries knowing about each other help us to hide information?

The obvious answer to me is that the knowledge of how to compare an ordered collection to a dictionary does not belong in ordered collections or in dictionaries. The requirement that relations like equivalence be symmetrical across heterogeneous types implies that the types themselves cannot be responsible for implementing equivalence for themselves.

There are similar problems of code duplication and information leakage apply to modelling relations (why do we declare has_one and belongs_to in Rails) and implementing the <=> operator in Ruby. It looks like having verbs “belong to” the subject noun is often a good idea, but not always a good idea.

commuting the sentence of execution

Maybe some verbs belong to objects, but some are best on their own? Maybe + and <=> and equivalent? really ought to be emancipated from their subservience to objects and ought to have their own definitions.

There are two real approaches to object-orientation. The first is known as message-passing. You send an object a message and ask it to deal with it. (This would not work with many people in this newsgroup.) The meaning of the message is local to the object, which inherits it from the class of which it is an instance, which may inherit it from superclasses of that class…

The second approach is generic functions. A generic function has one definition of its semantics, its argument list, and is only specialized on particular types of arguments.

What we ought to do is take some of the verbs and give them their own place in our programs, instead of hanging them off nouns. This isn’t such a revolutionary idea: Common Lisp’s Metaobject Protocol does this exact thing, providing generic functions. A generic function is, in effect, a verb raised to the same level of abstraction as a noun.

This isn’t some revolutionary idea limited to “powerful” languages either: the Java collections framework uses a Comparable interface for ordering collections. The compareTo(...) method belongs to an object. By way of—ahem—comparison, the Comparator interface extracts comparison out of the subject object and puts it in a separate function object. You can perform sorts in Java either way.

If we aren’t using Common Lisp, can we build the verbs we want out of the tools at our disposal? In other words, can we Greenspun generic functions in languages like Java and Ruby?

generic functions in java, plus a detailed look at method dispatching

Let’s start by thinking about generic functions in a Java-like language.

Returning to our example of writing equivalent?, we might make an Equivalent class with a single method, perhaps we can call it eval. So we end up with something like Eqivalent.eval(foo, bar). Java-like languages allow us to write different versions of the eval method with different type signatures, so we can write:

public static boolean eval (List foo, List bar) { ... }
public static boolean eval (List foo, Map bar) { ... }
public static boolean eval (Map foo, List bar) { return eval(bar, foo); }
public static boolean eval (Map foo, Map bar) { ... }

And so forth. Are we done?

No, our code is broken. What happens when we decide that the “default” equivalence is the == relationship. We can’t write:

public static boolean eval (Object foo, Object bar) { return foo == bar; }

This is hideously broken in languages like Java. You’re almost all nodding in agreement, but please be patient while I explain it anyway: you probably want to pass this along to someone who really needs to be told why it is broken, so why don’t I go ahead and explain it for them?

What you want is that if two objects are of the more specific types—List and Map—we will call the more specific version of the eval methods. But if we can’t “match” one of the more specific eval methods, we want to use eval (Object foo, Object bar). Too bad, that’s not how Java works. Java uses two completely different ways to figure out which method to call when you overload methods!

Way number one is is for figuring out that when you call noun.verb(...), where do we find the definition for verb? This lookup is effectively done at run time, so that even if your code looks like this:

public static void printSomething(Object foo) {
    System.out.println(foo.toString());
}

Java will look up the method toString based on foo’s actual type when the method is called, even though you declared it to be an Object. That’s polymorphism at work, and it’s the information hiding working for us. Each object can do it’s own thing where toString is concerned, and we don’t have to worry about it. This is called single dispatch, because it figures out which method to call based on just one of the nouns, the subject noun a/k/a the receiver of the method invocation.

But that’s not what happens when we write this:

public static void printSomethingElse (Object foo, Object bar) {
    if (Equivalent.eval(foo, bar))
        System.out.println("2 x " + foo);
    else System.out.println(foo.toString() + ", " + bar.toString());
}

It will always call eval (Object foo, Object bar). It will not call eval (List foo, List bar) if you pass it two lists. That’s because although each of our methods have the same name—eval—Java treats them as different methods, and it figures out which one to call based on the declared types of the parameters at compile time, not on the actual types of the parameters’ values at run time.

Besides writing a Lisp interpreter in Java, your next best bet for building a generic function the way we want it is to find a way to turn Java’s single dispatch into a multi-dispatch, to dispatch on two nouns, foo and bar.

The good news is this: dispatching at run time on two different types is a well-known problem, and the solution is called double dispatch. The problem with double dispatch is that it moves our equivalence code back into our nouns, and we don’t want that.

The Visitor pattern might be handy: it’s a way to add methods to an object at run time in a language like Java that supposedly doesn’t do that. If we decide that everything to be compared using Equivalent.evalimplements an interface called Visitable, we can build a double dispatch system that doesn’t require putting an equivalent? method in the entities being compared:

interface Visitable {
    Object accept(final Visitor visitor);
}

interface Visitor {
    Object visit(final Object obj);
    Object visit(final List list);
    Object visit(final Map map);
}

public class Equivalent {

    static boolean list_list (List foo, List bar) { ... }
    static boolean list_map (List foo, Map bar) { ... }
    static boolean map_map (Map foo, Map bar) { ... }
    static boolean object_object (Object foo, Object bar) { ... }

    public static boolean eval (final Visitable foo, final Visitable bar) {
        return foo.accept(
            bar.accept(
                new Visitor () {
                    public Object visit(final Object bar) {
                        return new Visitor () {
                            public Object visit(final Object foo) {
                                return object_object(foo, bar);
                            }
                            public Object visit(final List foo) {
                                return object_object(foo, bar);
                            }
                            public Object visit(final Map foo) {
                                return object_object(foo, bar);
                            }
                        }
                    }
                    public Object visit(final List bar) {
                        return new Visitor () {
                            public Object visit(final Object foo) {
                                return object_object(foo, bar);
                            }
                            public Object visit(final List foo) {
                                return list_list(foo, bar);
                            }
                            public Object visit(final Map foo) {
                                return list_map(bar, foo);
                            }
                        }
                    }
                    public Object visit(final Map bar) {
                        return new Visitor () {
                            public Object visit(final Object foo) {
                                return object_object(foo, bar);
                            }
                            public Object visit(final List foo) {
                                return list_map(foo, bar);
                            }
                            public Object visit(final Map foo) {
                                return map_map(foo, bar);
                            }
                        }
                    }
                }
            )
        )
    }
}

If that looks like a lot of work to you, I agree. You’re basically replicating Java’s run time dispatching on two types, so you need a bit of a matrix. Is it worth the effort? Let’s consider what this wins you:

• Your entities or objects no longer need to know all about other types of entities;


• It’s easier to make sure that commutation and symmetry are preserved when the code for a relationship is in its own class and not smeared over multiple entities.

And best of all, you have a nice place for your verbs, and they are no longer second-class citizens behind the nouns.

---

Update: A few people have suggested alternate approaches to implementing multiple dispatch in Java. I think there are various trade-offs to be made, and several different implementations ought to be considered before you write production code.

However, the point of the article is to suggest that not all functions should be implemented as methods of subject objects. I think it makes that point regardless of what you think of using a Visitor and a double dispatch.

Here’s an alternate approach from Laurie Cheers:

interface Classifiable
{
    int classify();
}

// I know this isn't valid Java, but it makes the example much clearer. The alternative is to tiresomely spell out every combination.
#define PAIR(a,b) (a|(b<<4))

abstract class DoubleDispatchable
{
    abstract Object list_list(List a, List b);
    abstract Object list_map(List a, Map b);
    abstract Object map_map(Map a, Map b);
    abstract Object object_object(Object a, Object b);

    const int OBJECT = 0;
    const int LIST = 1;
    const int MAP = 2;

    Object dispatch(Classifiable a, Classifiable b)
    {
        switch(PAIR(a.classify(), b.classify))
        {
            case PAIR(LIST, MAP): return list_map(a,b);
            case PAIR(MAP, LIST): return list_map(b,a);
            case PAIR(LIST, LIST): return list_list(a,b);
            case PAIR(MAP, MAP): return map_map(a,b);
            default: return object_object(a,b);
        }
    }
}

class Equivalent extends DoubleDispatchable
{
    Object list_list(List a, List b) {...}
    Object list_map(List a, Map b) {...}
    Object map_map(Map a, Map b) {...}
    Object object_object(Object a, Object b) {...}

    bool eval(Classifiable a, Classifiable b) { return dispatch(a,b) != false; }
}

What trade-offs, you ask? The Visitor pattern given gets the compiler to guarantee that you write each of the nine cases, whereas hand-written tests and logic simplifies the code.

I specifically chose the Visitor pattern because it seemed more in keeping with the spirit of the Java language and culture, trading verbosity for compiler safety.

I'm extremely comfortable with the other trade-off, emphasizing readability and simplicity. Although, if you go far enough down that road, you might as well look at other languages ;-)

Labels: java, lispy, popular

  ¶ 11:24 PM

  Hard-Core Concurrency Considerations Kevin Greer responded to What Haskell teaches us about writing Enterprise-scale software with some insightful emails about the pros and cons of using purely functional data structures for managing concurrency in a multi-processor environment. I’ve reproduced them (with his permission) below.

Now, your first reaction might be, “Ah, Reg is not nearly as smart as he thinks he is.”

If you feel like giving me some credit, you can keep in mind that I was not writing the definitive essay on designing concurrent software, just pointing out some interesting overlaps between what I consider to be the most academic programming language around and the most practical requirements in business applications.

But there’s something more important to take from this.

The original post was a response to someone asking whether there was any value to the stuff you read on programming.reddit.com. His query was whether reading about Haskell was practical. My response was, yes it is, and here are some examples of where functional data structures have an analogue in concurrent data structures. My thesis (that’s a two dollar word for “point”) was that many “impractical” things have a lot to teach us about things we will encounter in the pragmatic “real world.”

Of course, most people read the post and thought, “Cool, some neat stuff about concurrency.” Nothing wrong with that. If you value tips on concurrent programming (and I certainly do), you’ll find Kevin’s emails very insightful.

And if you are still wondering whether you should look at “impractical” and “academic” material like Haskell, Erlang, or other things not being promoted by MegloSoft, consider that one of the papers Kevin cites describes a data structure running on a 768 CPU system. Is this in a University lab somewhere? No, it is in a company that promotes itself as an Enterprise-Scale Java company.

You simply can’t assume that everything the industry tells you to learn is everything you need. Or that any one source (Cool! Raganwald has a new post on Lazy Evaluation) has the definitive answer.

You need to commit to life-long learning to be a software developer. Some of that learning is straightforward MSDN Magazine stuff, simple updates to things you already know. And some of that learning is a little further out on the curve.

Without further ado, here is one of the most comprehensive technical replies to a post on my blog I’ve received to date.

Concurrency Considerations

Hi Reg,

I was just reading your article on concurrent collections and have a few comments:

1. Just because readers do not update the structure doesn’t mean that they don’t need to synchronize. This belief is a common source of concurrency bugs on multi-processor systems.
   
   Unless you synchronize on the root of your data-structure (or declare it as volatile), you can’t be sure that your cache doesn’t have a stale version of the data (which may have been updated by another processor). You don’t need to synchronize for the entire life of the method, as you would by declaring the method synchronized, but you still need to synchronize on the memory access. You hold the lock for a shorter period of time, thus allowing for better concurrency, but you still have to sync.
   
   If you fail to synchronize your memory (or declare it as volatile), then your code will work correctly on a single CPU machine but will fail when you add more CPU’s (it will work on multi-core machines provided that the cores share the same cache). If you have a recursive datastructure (like a tree) then you will need to actually synchronize on each level/node, unless of course you use a purely functional data-structure, in which case, you’ll only need to synchronize on the root.
   
   Given that you need to make a quick sync anyway, this approach is not much better than just using a ReadWrite-lock (it is slightly better because you can start updating before the readers finish reading (not a big deal for get()’s but potentially a big deal for iterators()), but then again updates are more expensive because of the copying).


2. I don’t think that you should be using Haskell as a model of “Enterprise-scale” anything. “Enterprise-scale software” usually entails “Enterprise-scale hardware” which means, among other things, multiple-CPU’s. The problem is that Haskell purely-functional model doesn’t support multiple-CPU’s (it’s true, check the literature (except for specialized pipelined architectures, but not in the general case)).
   
   The whole processing “state” is essentially one large purely-functional data-structure. The problem of synchronizing your data-structure appears to be eliminated, but it has really just been moved up to the top-level “state” structure (monad), where the problem is actually compounded. This is worse, because not only would you need to lock your structure in order to make an update, but you would in fact need to lock “the whole world”.
   
   Some people will advocate launching one process per CPU and then using message passing to communicate between them. This is just a very inefficient (many orders of magnitude slower) way of pushing the synchronization issue off onto the OS/Network-stack. (Q: What do multi-core systems mean for the future viability of Haskell?)


3. You forgot to mention the common technique of using “striping” to improve concurrency. Basically, what you do is create multiple sub-datastructures which each contain only a sub-set of the data. You can partition the data based on the hash of the key being stored. You then wrap the whole thing up so that it still has the same interface as the single data-structure.
   
   The advantage of this approach is that when you use a ReadWrite lock you only need to lock a small portion of the data-structure, rather than the whole thing. This allows multiple updates to be performed in parallel. This is how Java’s concurrent collections work. See: ConcurrentHashMap: Java creates 16 sub-structures by default but you can increase the number when even more concurrency is required.


4. Have a look at Azul’s non-blocking HashMap implementation. They can do 1.2 billion hashMap operations per second (with 1% of 12 million/sec of those being updates) on a 768 cpu machine (the standard Java ConcurrentHashMap still does half a billion ops/sec which isn’t bad either) . This shows how scalable non-functional methods can be.
   
   I’ve never read of any Haskell or other purely-functional implementation being able to scale to anywhere near these numbers.

Summary: Using a purely-functional data-structure does make it easier to support multiple readers, but you still need to sync briefly at the “top” of the structure. Striping has the added advantage of also supporting multiple-writers as well, and in practice, this is a much bigger win. Haskell is inherently limited to a single CPU, which doesn’t match modern hardware; especially of the “enterprise” class. Shared-memory models of concurrency have demonstrated much better performance than purely-functional models.

Best Regards,

Kevin Greer

p.s. I've actually implemented a b-tree structure for very large data-sets and chose to use a purely-functional data-structure myself. My reason for doing so was that I have some very long-running read operations (~8 hours) and I obviously can't afford a ReadWrite lock that's going to starve writer threads for that long.

Another nice advantage of using purely-functional data-structures is that they make it easy to implement temporal-databases that let you perform time-dependent queries.

I just wanted to point out that if all you have is quick-reads then purely-functional is no different than a simple ReadWrite lock and that a super-pure implementation, as with Haskell, doesn't scale to multiple-CPU's or to highly concurrent updates. However, it can be used to good effect in combination with striping or other techniques.

(A tangential note: Java's GC is getting so good in recent releases that P-F data-structures are becoming much more efficient (given that P-F generates more garbage).)

p.p.s. One more advantage of functional data-structures (the largest advantage for me actually):

They map well to log(or journal)-based storage. Functional data-structures never update old data, but instead, just create new versions. If your data-structure uses disk-based storage then this means that you never need to go back and overwrite your file; you only need to append data to the end of the file. This has two advantages:

1. This works well with the physical characteristics of hard-disks. They have incredibly high transfer rates (10’s of Megs/sec) but very slow seek times (~ 200 seeks/sec if 5ms access time). If you are adding say 1k objects to a data-structure which requires 2 updates on average to a file then you’re looking at about 100 updates per second. If on the other-hand you write all of these updates to the end of the file then you’re looking at say 20,000 updates per second!


2. You can’t corrupt old data with interrupted writes. The old data is always still there. The only place that a corruption occur is at the end of the file, in which case you just scan backwards until you find the previous good head of your data-structure.

---

This is fantastic stuff to share, thanks, Kevin!

What other tips can readers contribute for people building highly concurrent software (besides the frequent use of JProbe Threadalyzer, of course)? What online resources (papers, articles, books) do readers recommend for the professional developer?

Labels: java, passion, popular

  ¶ 2:17 PM

  A parable illustrating the importance of the differences between Scheme and Common Lisp in a world where Java is the Lingua Franca of Programmers An encounter on a bridge.

Labels: java, lispy

  ¶ 1:13 PM

  Rails-style creators in Java, or, how I learned to stop worrying and love anonymous inner classes Let’s begin with a well-known problem: creating a Map that is to be pre-populated with a few values. Here is some naïve code that creates a Map and then puts two values into it:

final Map<String, Object> mm = new HashMap<String, Object>();
mm.put("foo", "Strive To Finish Up");
mm.put("bar", "Public House");

Although this works, the problem with the naïve code is that it does not say with conviction that the two put calls are part of the creation of the Map. If you move code around, it’s easy to drop a line. This code is literal, but it is not literate.

Most Java programmers¹ are familiar with the Map Initializer Idiom:

final Map<String, Object> m = new HashMap<String, Object>() {{
    put("bar", "saloon");
    put("bash", 7);
}};

This creates a new Map and populates it with two members. This is a big improvement. The initialization is clearly embedded in the line of code that creates the Map. Thanks to a small syntax hack, it is (by Java standards) concise.

If you’re into the details, it actually creates a new anonymous inner class that extends HashMap. The inner class doesn’t add any new instance members, but it does contain an initializer: code between braces is run when instances are initialized. That’s why there are double braces: the outer set delineates the body of the anonymous inner class, the inner set delineates the initializer block.

Note that your new Map isn’t exactly equal to any HashMap, because it has a different class. That sometimes matters.

POJOs

Many Java programmers labour with applications where the original architect wielded the Golden POJO Hammer: absolutely everything in the application looked like a POJO nail. I work with one such code base: it is obviously a traditional Procedural application. Getting anything done involves calling a global procedure and passing in a bunch of arguments.

The original architects worked for one of those Global Services companies, and you can’t charge hundreds of dollars an hour² writing programs that our grandparents would recognize from the sixties. So to add a layer of OO, they turned every procedure call into a method, so a simple call like:

final BigDecimal balance = AccountModule.getAccountBalance("12345-678");

became:

final BalanceDoer doer = new BalanceDoer();
doer.setAccountNumber("12345-678");
doer.doit();
final BigDecimal balance = doer.getBalance();

(The nice thing about using this “OO Style” is that you get named parameters and multiple return values. I shall leave it to the static type checking enthusiasts to point out the drawbacks of this approach.)

Well, we can use the same initializer idiom with POJOs like BalanceDoer (although you may have to move doit() outside of the initializer if you need checked exceptions):

final BalanceDoer doer = new BalanceDoer() {{
    setAccountNumber("12345-678");
    doit();
}};
final BigDecimal balance = doer.getBalance();

Again, you get a more literate snippet of code: the initialization and invocation all belong together, and you have put them together. If you move this around, you won’t drop an important line by mistake. And you get to save some keystrokes if there are a lot of fields to initialize.

If you dare to use protected fields in POJOs (this is heresy to the “lock everything down so that other programmers subclassing your stuff can’t actually change anything” zealots), you can even write accountNumber = "12345-678"; in the initializer instead of using a setter.

I prefer that form, it looks a lot more like what you are trying to say: this field has this value for this doit call. That may be a matter of taste, or I may be overlooking something important.

Remember, your new object is an instance of an anonymous inner class, not of the original POJO class. This matters greatly if you test for class membership with equals instead of substitutability with instanceof.

What does this have to do with Rails?

This is where we could go off on a long essay about how using things like Lisp, Smalltalk, and Ruby on Rails opens your mind to possibilities. That when you get used to MyModel.create(:foo => 'Shove That Fish Under'), you look for ways to make your Java code easier, and so forth.

But honestly, you knew that already, didn’t you?

Update: Writing programs for people to read.

---

1. Where by “most,” I mean those who haven’t been hiding under the “Java-programs-must-only-contain-approved®-design-patterns: all-other-idioms-are-considered-hard-to-read-by-mediocre-colleagues” rock.
   
   In my experience, that is the majority of good programmers. If reading blogs convinces you otherwise, remember that many of the best people are too busy building good stuff to write about building good stuff.
   
   Update: A commenter expressed some surprise that this is a well-known idiom. Have a look at Double Brace Initialization.
   
   The other Java people, the ones with time on their hands, or the ones that consider themselves “too good to program,” are the ones that write posts explaining why Java programs must be dumbed down to the lowest common denominator. I also blog. Draw your own conclusions from the evidence.


2. Not this company, although that’s an amusing post.

Labels: java

  ¶ 10:10 AM

  What does Barbara Liskov have to say about Equality in Java? Erick Reid posted some code showing his standard implementations of equals and hashCode in Java (updated link). His implementations draw heavily on Joshua Bloch’s principles. I think he’s done a great job in implementing the Java standard implementation of equality. On the other hand, I’m a little disquieted by the way equality works in Java.

Here’s a shorter version of his equality method for a class, TempBean, that has members _foo, and _bar:

public boolean equals(Object object) {
  if (object != this) {
    if (object != null && getClass().equals(object.getClass())) {
      final TempBean other = (TempBean) object;
      return (_foo == null ? other._foo == null : _foo.equals(other._foo)) &&
          (_bar == null ? other._bar == null : _bar.equals(other._bar));
    }
    return false;
  }
  return true;
}

The interesting part for me is the test for class equality: getClass().equals(object.getClass()). Compare and contrast to:

public boolean equals(Object object) {
  if (object != this) {
    if (object != null && object instanceof TempBean) {
      final TempBean other = (TempBean) object;
      return (_foo == null ? other._foo == null : _foo.equals(other._foo)) &&
          (_bar == null ? other._bar == null : _bar.equals(other._bar));
    }
    return false;
  }
  return true;
}

This works when object is a TempBean. That’s almost the same as the first code. It’s different when object is an instance of TempBean but not a TempBean.

For example:

void doSomethingSeussian (final TempBean thingOne) {
    final TempBean thingTwo = TempBean.getThingFromBox(/* ... */);

    if (thingTwo.equals(thingOne)) {
        // ...
    }
}

thingTwo is obviously a TempBean. Or is it? What does the factory method getThingFromBox do? And what if thingOne is an instance of a subclass of TempBean? What if it has exactly the same _foo and _bar as thingTwo? Why isn’t it equals?

Does this sound farfetched? What if it doesn’t even have any different members, it only varies in some subtle implementation way? For example, what if thingOne is a ThreadSafeTempBean that guarantees thread safety in a way that is otherwise transparent to clients? Or a MockTempBean that is used for unit tests?

All equalities are equal, but some are more equal than others

If you program in Java, you probably already know that == is not the same thing as equals. One measures identity , whether two objects are the exact same identical object in memory at the same location. (Unless they are those dratted primitives, in which case it measures value equality). Identity is almost useless in Java, it breaks all over the place, and that’s why it’s rightfully rare.

Value equality is where the interesting problem lies. There are two kinds of value equalities: physical equality (“these two are identical copies of the same object in every respect”) and logical equality (“for my purposes, these two are equivalent”).

The basic problem here is that equals captures physical equality, which ignores the Liskov Substitution Principle, one of the fundamental principles in OO design. It is leaking the implementation, just like a leaky abstraction.

(I think a lot of the problem starts when people conflate interfaces with classes. There’s a big difference between saying “this is the interface TempBean, and here is how to tell if any two TempBeans are equals to each other” and saying “this is an implementation of a TempBean, and if you want to know whether it is the exact same thing as another implementation, here is how to do it.”

The former ought to be very common, and the latter quite rare in OO programs.)

It isn’t easy to fix the physical equality problem. If you use the second form of code, you get an equals method that is not symmetric (thanks, Marc!). In the examples above, thingOne.eqauls(thingTwo) is not always the same as thingTwo.equals(thingOne)! And if you’re implementing a HashMap, which kind of equality do you want to use for deciding whether a key is already in the collection?

This last question is another way of pointing out that equality is not an easy thing to define if you mix the notion of polymorphism into a language. Do you always want logical equality? I can easily think of code that would break horribly if you made a HashMap that respected the Liskov Substitution Principle for keys. And I can also think of code where I want a map or set that respects the Liskov substitution principle.

What can we do about this?

To make equality adhere to the Liskov Substitution Method in a language like Java, you can’t make it an object method. One of the other cherished notions in OO design is that every object ought to know everything about its behaviour. But this objects can’t know how much detail a client wants in making the comparison.

The piece of code that ought to know how to compare two TempBeans is the TempBean class (which is also the TempBean interface in Java, but Java doesn’t allow code in interfaces). We’re off to a good start, the code for equals is in the TempBean class. But where we went wrong is making it an instance method. What happens if it’s a static method?

public static boolean equivalent(TeampBean left, TempBean right) {
  if (left != right) {
    if (left != null && right != null) {
      return (left._foo == null ? right._foo == null : left._foo.equals(right._foo)) &&
          (left._bar == null ? right._bar == null :left. _bar.equals(right._bar));
    }
    return false;
  }
  return true;
}

Now you can write code like:

void doSomethingSeussian (final TempBean thingOne) {
    final TempBean thingTwo = TempBean.getThingFromBox(/* ... */);

    if (TempBean.equivalent(thingTwo, thingOne)) {
        // ...
    }
}

Without worrying about whether either variable holds a TempBean, a ThreadSafeTempBean, or a MockTempBean. It’s true that sometimes you care very deeply about the difference. But most of the time, you probably do not, and using an equals method that does care is wrong.

Labels: java

  ¶ 9:40 PM

  Don't have a COW, man? What Haskell teaches us about writing Enterprise-scale software Berlin Brown asked:

I read programming.reddit religiously but I rarely see something that could be used in a non-startup environment. Am I wrong, or are you considering deploying a haskell enterprise web application? And if the stuff discussed isn’t relevant for the next 5 years (i.e. an erlang based webapp) will it ever be relevant?

Yes, I use what I read on programming.reddit.com in my day job. That’s one of the reasons I have this day job: it’s part of what I do to sift through all of the cool stuff and find the things that are practical today.

Since you mentioned Haskell:

Consider a multi-threaded application with shared memory, like a really big web server that has some big shared collection of things in memory. From time to time you add things to the big collection, from time to time you remove them.

Pessimism and coarse-grained locking

One way to arbitrate multiple threads is to have one copy of the collection with strict locking protocols that apply to its coarse-grained operations like add, remove, and fetch.

In a language like Java, you can synchonize those methods and you’re done. You have just implemented mutex locking: only one thread can use the collection at a time. If one thread is fetching something from the collection, all other threads must wait, even if all they want to do is fetch things as well.

That sucks tbng qvpx, especially if you do lots of reading: why should thread 546 have to wait to fetch something just because thread 532 is currently fetching something?¹

Read and write locks

The next improvement is to have two kinds of locks: read locks and write locks. Two or more threads can lock the collection for reading, but if any thread locks the collection for writing, all of the other threads have to wait until it is done.

This works for about 17 clock ticks, and then you fix the bug by adding a new rule: if a thread wants a write lock but one or more threads have read locks, it has to wait, but any other threads that want read locks can’t have them. Even though the only threads with locks have read locks, they still have to wait.

The thread waiting to write gets a kind of pending write lock that blocks all other threads from taking out new locks. And then you fix the next bug by saying that all threads waiting wait in a priority queue so that the read threads aren’t starved by write threads and the write threads aren’t starved by read threads.

You now have a system that is pretty fast a long as you don’t write things very often. For example, you could build a fairly nice cache using read-write locking provided it is tuned so that you get lots of hits and only rarely have to drop things from the cache or add things to the cache. But if you’re doing something like maintaining a big index in memory where you have to make lots of updates, the writes will slow everything down.

These kinds of locking protocols are called pessimistic protocols: you assume bad things will happen and prevent them from happening up front by blocking threads from executing until it is safe to proceed.

Multi-version concurrency control

Another way to arbitrate multiple threads is to make copies of the collection whenever you perform an update.² You maintain multiple versions of the collection. When a thread needs the collection, it grabs the latest copy. When it wants to remove or add elements, it writes a new copy without disturbing an existing copy.

This works really well in that threads that only want to read are never blocked. They always run at full speed, even if another thread is in the middle of an update. Hand-waving over how you figure out the whole “latest copy” thing, this scheme doesn’t work so well for threads that write.

The problem is one of serialization: this word means, if some set of operations takes place on the collection, the result must be the same as if the operations were conducted one at a time on the collection. There is no guarantee of the order of the operations, just that the result is the same as if they had been carried out in some order.

Let’s use an example. Say our collection is a Map. It starts empty:

{ }

Operation A adds an element:

{...a: "A"...}

As does operation B:

{...b: "B"...}

And operation C:

{...c: "C"...}

If we start with an empty hash and perform all three operations, the result should be { a: "A", b: "B", c: "C" }, exactly the same result as if each operation were performed serially, one after the other. But what happens if each operation is performed by a thread that grabs the initial copy, {} and writes its result back to the collection? Something called a race condition: the result will be { a: "A" }, { b: "B" }, or { c: "C" }, with the “winner” being the last one to write its result.

We can fix this problem in a couple of ways. One way is to keep the versions so that reading threads work at full speed, but use mutexes for write locks so that only one thread can write at a time. That’s simple, and if you can figure out a cheap way to make copies, works pretty well.

That’s your pessimistic protocol again (threads that write have to wait on other threads that write), but it’s a huge win for threads that read.

Making this work is tricky. Copying the entire thing is expensive, so you need to do clever tricks where you only copy the things that change and share the things that don’t change. And you can get a big, big win if you can avoid write conflicts by arbitrating conflict at a finer grain. For example, a HashMap uses a set of linked lists. If two different threads write to different “buckets,” you can merge their results rather than rolling one back and starting again.

There is a lot of extra overhead for this if a thread wants to write while another thread is reading a version, so it is only a big win if writes are fairly rare. Remember, one of the big wins is that reads never wait on writes because they work with immutable versions of the collection.

Depending on how many threads you have, what kinds of operations are most likely, and other factors, this kind of system can be orders of magnitude faster than coarse-grained pessimistic locking.

Sometimes you want a slightly different protocol. The aforementioned is often called single write, many reads. It requires threads that plan on writing to know in advance they need to write. But for something like a cache, you don’t know you need to write until you miss the cache. And then it’s too late to get a write lock.

Optimism and many writes, many reads

The easiest way to avoid having to pre-declare whether a thread is a reader or a writer is by letting all of the threads do as they please. They all get the latest version and chug happily along.

When they are finished, if they never executed an add or remove we let go of the copy of the collection and we’re done. If a thread wants to write, it makes a copy as above and writes to its copy. But it doesn’t have to grab a lock while it is writing, so writes don’t wait on other writes.

Now, if a thread has executed a write (an add or remove), when it is done we check the result to see if it violates serializability.

For example, we can number our versions. Let’s say that {} is version 0. The first thread to finish, let’s say it’s the thread performing operation B, creates its result: { b: "B" }. Now it checks the collection to see if anyone has updated it since B read the collection. The collection is still at version 0, so B can write its result. B writes { b: "B" } to the collection and calls it version 1.

Next A finishes and notices that the collection is at version 1. This is a problem, because A is working with an updated version 0, so it has to throw out its work, fetch version 1, and try again. This is exactly the same thing as using a source code control system like Subversion to resolve conflicts.

This many reads, many writes strategy is called an optimistic protocol because you do work in the hope that nothing will cause you to throw it out and try again. It’s a big win if writes do happen at the same time, but they rarely conflict.

For example, if you have a good strategy for merging writes, this is huge.

So what?

Well, it would be great if you didn’t have to reinvent the wheel and have to work out all of the implications when you want to make a really fast shared collection in a multi-threaded environment. What you want is someone to share a wealth of experience about how to make really fast copies of things by only changing the little bits that you change instead of the whole thing, and so forth.

I like languages which say, “No, you don't want to write it the way you’re thinking. There’s a vastly better way to solve this whole class of problems.” Me: brain explodes

Where do you go for that kind of information? How about to people who spend all day thinking about collections that cannot change because their programming languages are purely functional?

Yes, what I’ve just described is exactly how languages like Haskell implement mutable collections like dictionaries and lists. In purely functional languages, collections never change. Adding something to a collection is really creating a new collection with an extra element. This is the exact same implementation that we need for building optimistically locked collections in a multi-threaded environment!

Haskell teaches us extremely useful techniques for writing Enterprise-scale software.

And more techniques: Hard-core concurrency considerations

---

1. Now, you might be saying, “what a waste, this is like locking a table in a database when we should be locking rows.” But if you look at the database closely, it does lock the table when you perform certain actions like deleting a row. Or it does something more complicated, and now that you’ve read the entire post, you know what it really does.


2. Making Copies on Writes is called copy on write semantics, or COW for short. Chew on that for a while.

Labels: java, lispy, popular

  ¶ 10:38 PM

  Why Why Functional Programming Matters Matters I recently re-read the amazing paper Why Functional Programming Matters (“WhyFP”). Although I thought that I understood WhyFP when I first read it a few years ago, when I had another look last weekend I suddenly understood that I had missed an important message.¹

Now obviously (can you guess from the title?) the paper is about the importance of one particular style of programming, functional programming. And when I first read the paper, I took it at face value: I thought, “Here are some reasons why functional programming languages matter.”

On re-reading it, I see that the paper contains insights that apply to programming in general. I don’t know why this surprises me. The fact is, programming language design revolves around program design. A language’s design reflects the opinions of its creators about the proper design of programs.

In a very real sense, the design of a programming language is a strong expression of the opinions of the designer about good programs. When I first read WhyFP, I thought the author was expressing an opinion about the design of good programming languages. Whereas on the second reading, I realized he was expressing an opinion about the design of good programs.

Can we add though subtraction?

It is a logical impossibility to make a language more powerful by omitting features, no matter how bad they may be.

Is this obvious? So how do we explain that one reason Java is considered “better than C++” is because it omits manual memory management? And one reason many people consider Java “better than Ruby” is because you cannot open base classes like String in Java? So no, it is not obvious. Why not?

The key is the word better. It’s not the same as the phrase more powerful.² The removal or deliberate omission of these features is an expression about the idea that programs which do not use these features are better than programs which do. Any feature (or removal of a feature) which makes the programs written in the language better makes the language better. Thus, it is possible to make a language “better” by removing features that are considered harmful,³ if by doing so it makes programs in the language better programs.

In the opinion of the designers of Java, programs that do not use malloc and free are safer than those that do. And the opinion of the designers of Java is that programs that do not modify base classes like String are safer than those that do. The Java language design emphasizes a certain kind of safety, and to a Java language designer, safer programs are better programs.

“More powerful” is a design goal just like “safer.” But yet, what does it mean? We understand what a safer language is. It’s a language where programs written in the language are safer. But what is a “more powerful” language? That programs written in the language are more powerful? What does that mean? Fewer symbols (the “golf” metric)?

WhyFP asserts that you cannot make a language more powerful through the removal of features. To paraphrase an argument from the paper, if removing harmful features was useful by itself, C and C++ programmers would simply have stopped using malloc and free twenty years ago. Improving on C/C++ was not just a matter of removing malloc and free, it was also a matter of adding automatic garbage collection.

This space, wherein the essay ought to argue that Java compensates for its closed base classes by providing a more powerful substitute feature, left intentionally blank.

At the same time, there is room for arguing that some languages are improved by the removal of harmful features. To understand why they may be improved but not more powerful, we need a more objective definition of what it means for a language to be “more powerful.” Specifically, what quality does a more powerful programming language permit or encourage in programs?

When we understand what makes a program “better” in the mind of a language designer, we can understand the choices behind the language.

Factoring

Factoring a program is the act of dividing it into units that are composed to produce the working software.⁴ Factoring happens as part of the design. (Re-factoring is the act of rearranging an existing program to be factored in a different way). If you want to compare this to factoring in number theory, a well designed program has lots of factors, like the number 3,628,800 (10!). A Big Ball of Mud is like the number 3,628,811, a prime.

Composition is the construction of programs from smaller programs. So factoring is to composition as division is to multiplication.

Factoring programs isn’t really like factoring simple divisors. The most important reason is that programs can be factored in orthogonal ways. When you break a program into subprograms (using methods, subroutines, functions, what-have-you), that’s one axis of factoring. When you break an a modular program up into modules, that’s another, orthogonal axis of factoring.

Programs that are well-factored are more desirable than programs that are poorly factored.

In computer science, separation of concerns (SoC) is the process of breaking a program into distinct features that overlap in functionality as little as possible. A concern is any piece of interest or focus in a program.

SoC is a long standing idea that simply means a large problem is easier to manage if it can be broken down into pieces; particularly so if the solutions to the sub-problems can be combined to form a solution to the large problem.

The term separation of concerns was probably coined by Edsger W. Dijkstra in his paper On the role of scientific thought.

—Excerpts from the Wikipedia entry on Separation of Concerns

Programs that separate their concerns are well-factored. There’s a principle of software development, responsibility-driven design. Each component should have one clear responsibility, and it should have everything it needs to carry out its responsibility.

This is the separation of concerns again. Each component of a program having one clearly defined responsibility means each concern is addressed in one clearly defined place.

Let’s ask a question about Monopoly (and Enterprise software). Where do the rules live? In a noun-oriented design, the rules are smooshed and smeared across the design, because every single object is responsible for knowing everything about everything that it can ‘do’. All the verbs are glued to the nouns as methods.

In a game design where you have important information about a rule smeared all over the object hierarchy, you have very poor separation of concerns. It looks at first like there’s a clear factoring “Baltic Avenue has a method called isUpgradableToHotel,” but when you look more closely you realize that every object representing a property is burdened with knowing almost all of the rules of the game.

The concerns are not clearly separated: there’s no one place to look and understand the behaviour of the game.

Programs that separate their concerns are better programs than those that do not. And languages that facilitate this kind of program design are better than those that hamper it.

Power through features that separate concerns

One thing that makes a programming language “more powerful” in my opinion is the provision of more ways to factor programs. Or if you prefer, more axes of composition. The more different ways you can compose programs out of subprograms, the more powerful a language is.

Do you remember Structured Programming? The gist is, you remove goto and you replace it with well-defined control flow mechanisms: some form of subroutine call and return, some form of selection mechanism like Algol-descendant if, and some form of repetition like Common Lisp’s loop macro.

Dijkstra’s view on structured programming was that it promoted the separation of concerns. The factoring of programs into blocks with well-defined control flow made it easy to understand blocks and rearrange programs in different ways. Programs with indiscriminate jumps did not factor well (if at all): they were difficult to understand and often could not be rearranged at all.

Structured 68k ASM programming is straightforward in theory. You just need a lot of boilerplate, design patterns, and the discipline to stick to your convictions. But of course, lots of 68k ASM programming in practice is only partially structured. Statistically speaking, 68k ASM is not a structured programming language even though structured programming is possible in 68k ASM.

Structured Pascal programming is straightforward both in theory and in practice. Pascal facilitates separation of concerns through structured programming. So we say that Pascal “is more powerful than 68k ASM” to mean that in practice, programs written in Pascal are more structured than programs written in 68k ASM because Pascal provides facilities for separating concerns that are missing in 68k ASM.

For example: working with lists

Consider this snippet of iterative code:

int numberOfOldTimers = 0;
for (Employee emp: employeeList) {
    for (Department dept: departmentsInCompany) {
        if (emp.getDepartmentId() == dept.getId() && emp.getYearsOfService() > dept.getAge()) {
            ++numberOfOldTimers;
        }
    }
}

This is an improvement on older practices.^{5, 6} For one thing, the for loops hide the implementation details of iterating over employeeList and departmentsInCompany. Is this better because you have less to type? Yes. Is it better because you eliminate the fence-post errors associated with loop variables? Of course.

But most interestingly, you have the beginnings of a separation of concerns: how to iterate over a single list is separate from what you do in the iteration.

Try calling a colleague on the telephone and explaining what we want as succinctly as possible. Do you say “We want a loop inside a loop and inside of that an if, and…”? Or do you say “We want to count the number of employees that have been with the company longer than their departments have existed.”

One problem with the for loop is that it can only handle one loop at a time. We have to nest loops to work with two lists at once. This is patently wrong: there’s nothing inherently nested about what we’re trying to do. We can demonstrate this easily: try calling a colleague on the telephone and explaining what we want as succinctly as possible. Do you say “We want a loop inside a loop and inside of that an if, and…”?

No, we say, “We want to count the number of employees that have been with the company longer than their departments have existed.” There’s no discussion of nesting.

In this case, a limitation of our tool has caused our concerns to intermingle again. The concern of “How to find the employees that have been with the company longer than their departments have existed” is intertwined with the concern of “count them.” Let’s try a different notation that separates the details of how to find from the detail of counting what we’ve found:

old_timers = (employees * departments).select do |emp, dept|
  emp.department_id == dept.id && emp.years_of_service > dept.age
end
number_of_old_timers = old_timers.size

Now we have separated the concern of finding from counting. And we have hidden the nesting by using the * operator to create a Cartesian product of the two lists. Now let’s look at what we used to filter the combined list, select. The difference is more than just semantics, or counting characters, or the alleged pleasure of fooling around with closures.

* and select facilitates separating the concerns of how to filter things (like iterate over them applying a test) from the concern of what we want to filter. So languages that make this easy are more powerful than languages that do not. In the sense that they facilitate additional axes of factoring.

The Telephone Test

Let’s look back a few paragraphs. We have an example of the “Telephone Test:” when code very closely resembles how you would explain your solution over the telephone, we often say it is “very high level.” The usual case is that such code expresses a lot more what and a lot less how. The concern of what has been very clearly separated from the concern of how: you can’t even see the how if you don’t go looking for it.

In general, we think this is a good thing. But it isn’t free: somewhere else there is a mass of code that supports your brevity. When that extra mass of code is built into the programming language, or is baked into the standard libraries, it is nearly free and obviously a Very Good Thing. A language that doesn’t just separate the concern of how but does the work for you is very close to “something for nothing” in programming.

But sometimes you have to write the how as well as the what. It isn’t always handed to you. In that case, it is still valuable, because the resulting program still separates concerns. It still factors into separate components. The components can be changed.

I recently separated the concern of describing “how to generate sample curves for some data mining” from the concern of “managing memory when generating the curves.” I did so by writing my own lazy evaluation code (Both the story and the code are on line). Here’s the key “what” code that generates an infinite list of parameters for sample beziér curves:

def magnitudes
  LazyList.binary_search(0.0, 1.0)
end

def control_points
  LazyList.cartesian_product(magnitudes, magnitudes) do |x, y|
    Dictionary.new( :x => x, :y => y )
  end
end

def order_one_flows args = {}
  height, width = (args[:height] || 100.0), (args[:width] || 100.0)
  LazyList.cartesian_product(
      magnitudes, control_points, control_points, magnitudes
  ) do |initial_y, p1, p2, final_y|
    FlowParams.new(
      height, width, initial_y * height,
      CubicBezierParams.new(
        :x => width,          :y => final_y * height,
        :x1 => p1.x * width,  :y1 => p1.y * height,
        :x2 => p2.x * width,  :y2 => p2.y * height
      )
    )
  end
end

That’s it. Just as I might tell you on the phone: “Magnitudes” is a list of numbers between zero and one created by repeatedly dividing the intervals in half, like a binary search. “Control Points” is a list of the Cartesian product of magnitudes with itself, with one magnitude assigned to x and the other to y. And so forth.

I will not say that the sum of this code and the code that actually implements infinite lists is shorter than imperative code that would intermingle loops and control structures, entangling what with how. I will say that it separates the concerns of what and how, and it separates them in a different way than select separated the concerns of what and how.

So why does “Why Functional Programming Matters” matter again?

The great insight is that better programs separate concerns. They are factored more purely, and the factors are naturally along the lines of responsibility (rather than in Jenga piles of abstract virtual base mixin module class proto_ extends private implements). Languages that facilitate better separation of concerns are more powerful in practice than those that don’t.

WhyFP illustrates this point beautifully with the same examples I just gave: first-class functions and lazy evaluation, both prominent features of modern functional languages like Haskell.

WhyFP’s value is that it expresses an opinion about what makes programs better. It backs this opinion up with reasons why modern functional programming languages are more powerful than imperative programming languages. But even if you don’t plan to try functional programming tomorrow, the lessons about better programs are valuable for your work in any language today.

That’s why Why Functional Programming Matters matters.

---

1. And now I’m worried: what am I still missing?


2. Please let’s not have a discussion about Turing Equivalence. Computer Science “Theory” tells us “there’s no such thing as more powerful.” Perhaps we share the belief that In theory, there’s no difference between theory and practice. But in practice, there is.


3. I am not making the claim that I consider memory management or unsealed base classes harmful, but I argue that there exists at least one person who does.


4. The word “factor” has been a little out of vogue in recent times. But thanks to an excellent post on reddit, it could make a comeback.


5. So much so that we won’t even bother to show what loops looked like in the days of for (int i = 0; i < employeeList.size(); ++i).


6. Another organization might merge employees and departments, or have each department “own” a collection of employees. This makes our example easier, but now the data doesn’t factor well. Everything we’ve learned from databases in the last forty years tells us that we often need to find new ways to compose our data. The relational model factors well. The network model factors poorly.

Labels: java, lispy, popular, ruby

  ¶ 10:21 PM

  Programming Language Stories C

A fellow needs a dog house, so he hires a contractor. This guy is a C programmer who’s between jobs at the moment, and he says forget those wimpy “agile” wooden dog houses, he can build the dog house out of bricks, it will last forever and is stronger than any wood structure.

The client is doubtful, but that sounds very impressive, and the contractor says this is how all the real-world dog houses are made, so he agrees. Well, it takes forever: it seems every time the contractor thinks it’s finished, they discover there’s a chink between the bricks and there’s a leak. With wood you just trim to fit, but with bricks you have to plan everything in advance so that the bricks line up just right.

But Spring turns to Summer turns to Autumn, and the job is done. The client pays up, and the contractor’s about to leave when he stops and thinks for a moment before speaking.

“Hey,” the contractor says, “You paid for a pallet of bricks, and I used all but one. It’s a shame if it goes to waste. Why don’t I see if I can use it somewhere?” The client asks like what, and before you know it the contractor has scored a contract to build a brick path for the dog from the back door to the dog house. He orders some more bricks, gets to work right away, and this time things go a little better.

The contractor is now doing C++ on the side. And he uses some new bricklaying techniques he learned from Effective C++: there are these funny angle braces everywhere thanks to his path building templates. Soon that job is done and the contractor collects his fee. He’s about to leave, but he reaches into his tool chest and pulls out a brick.

“Hey,” the contractor says, “You paid for another pallet of bricks, and I used all but one on the path. It’s a shame if it goes to waste. Why don’t I see if I can use it somewhere?” The client is happy with the path, asks like what, and before you know it the contractor has scored another contract, this time to build a brick wall enclosing the yard. He orders some more bricks, and gets to work right away.

Meanwhile, the contractor has become a Visual C++ programmer and reads MSDN magazine religiously. He applies his new skills to building the wall: he has all these fancy tools that can put up sections of scaffolding when you push a button. of course, there are huge holes you have to fill in yourself, and the scaffolding has all these crazy joins and angles, it’s hard to change anything or understand how the entire wall fits together, but it feels like you’re getting a lot done because the system seems to move a lot of bricks for you.

Well, the wall takes forever, and it doesn’t look that good when it’s finally done. But the client pays up and the contractor is ready to leave. But he stops for a moment and pulls a brick out of his tool chest.

“Hey,” the contractor says, “You paid for two more pallets of bricks for the wall, and I used all but one. It’s a shame if it goes to waste. Why don’t I see if I can use it somewhere?”

The client has had enough of this, and he decides he’s going to show the contractor how he feels. “Give me that brick,” he orders. The surprised contractor hands it over. “I don’t give a rat’s ass about this brick” the client huffs, and he throws the brick clear out of his yard.

“I need to get work done, not talk to contractors all day about bricks. And besides, I’ve talked to the big landscape contracting companies, and they all say nobody is using bricks, everyone has switched to sharp tools and netting. Now get out.”

Ruby on Rails

Just inside the gates of heaven, St. Peter sits at a desk checking people in.

Peter: “Welcome to heaven. Programming language?”

The man at the front of the line says, “Smalltalk.”

Glancing at his clipboard, Peter says, “Room 33. Be very quiet as you pass Room Six.”

The process repeats itself with the next person in line:

Peter: “Welcome to heaven. Programming language?”

Person #2: “Common Lisp.”

Peter: “Room 17. Be very quiet as you pass Room Six.”

The next person moves to the front of the line with a look of curiosity on her face.

Peter: “Welcome to heaven. Programming language?”

Person #3: “Python.”

Peter: “Room 54. Be very quiet as you pass Room Six.”

Person #3: “Why do you keep telling us to be quiet as we pass Room Six?”

Peter: “Because the Ruby on Rails People are in Room Six, and they think they’re the only ones here.”

—Snarfed from Eric Sink’s Baptists and Boundaries

Java

A mother was preparing the pot-roast for Sunday’s big family dinner. Before searing it and placing it in the pan, she carefully sliced the ends off. Her three year-old daughter asked “Mommy, why do you cut the ends off the roast?”

She answered, “My mom taught me to do it that way, and it’s delicious, so it must be a good idea. Maybe the juices from the meat mix with the vegetables?”

Everyone sits down for dinner, and when Father is serving the roast, the daughter remembers her question. She turns to Grandma and asks, “Grandma, why did you teach Mommy to cut the ends off the roast?”

Grandma thinks for a moment and says, “What a delightful question! I always used to cut the ends off the roast, it’s how my mother taught me. I don’t know why she did that, there must have been a good reason.” Grandma sits for a moment, remembering her mother. “Well,” she continues, ” there must have been a good reason. Now eat your dinner before it gets cold!”

The holidays roll around, and they’re having dinner at Grandma and Grandpa’s house. “Hey!” Grandma says to the little girl, “You know what, I was going through your great-grandmother’s things, and I found the old roast pan. We sure made some good pot roast in it. Let’s make pot roast with it tonight in her honour!”

They get out the pan and wash it up. It’s old, and well-seasoned. Grandma looks it over. “It’s smaller than I remember. I was a little girl, and everything looks bigger when you’re small!”

They put the roast on the counter before searing it. Just then, Grandpa walks by. “Do you want me to cut the ends off the roast?” he asks. “It’s the only way you’ll get it to fit in that small pan.”

Grandma and the little girl look at each other. And they smile.

Scheme

A fellow is on vacation, and he decides to ride one of those “scenic” double-decker buses that drive around from attraction to attraction. The upper level is open-air, and he’s the only one up there. He looks around, and decides that instead of re-reading his copy of The Little Schemer, he’s going to really enjoy himself: he lights a cigar.

No sooner has he lit the cigar when a woman comes huffing and puffing upstairs, carrying one of those sub-miniature dogs people use as fashion accessories. She takes one look at our man and demands he put the cigar out: it is offensive to the dog.

“Madam,” our man asserts, “this cigar is not offensive. Let me tell you its secrets.”

“Eschewing inferior mass-market tobacco, I order whole, functional leaves—at great expense and with difficulty—from a small collective in Cuba that still grow cigar tobacco the old-fashioned, original way.”

“Unsullied by automatic rolling machines or other push button devices, I roll each cigar, myself, by hand. Using secret tobacco-macro techniques that are impenetrable to the typical ignorant cigarette smoker, I am able to pack as much smoking pleasure into a single cigar as would take a carton of cigarettes—nay, it is impossible to enjoy a smoke from regular cigarettes as much as I enjoy the elite, exclusive flavour of my cigars.”

The woman is not impressed. “If your cigars are so good, how come nobody smokes them?” she asks. “If your cigars are so good, how come so many clubs and restaurants permit cigarettes but forbid cigars?”

Our fellow is so irate he begins to splutter. “If you or your dog are unable to understand that the purity, the perfection achieved long ago on a remote island far from consumerism and mass productio—” But he is unable to finish, for the woman imperiously sweeps the cigar from his mouth and flings it over the side of the bus.

“That’s what I think of your pompous cigar.” She tells him.

He glares at her for a moment, then years of oppression, of being forced to live with the hated cigarettes against his will, bring him to a boil and he commits an unthinkable act. With a wrench, he seizes the dog and flings it after his cigar. There is a moment of uncomprehending shock, and then the woman begins to howl.

Well, the bus driver hears all this and slams on the brakes. For a moment everything is higgledy-piggledy, and just as the woman’s wails return to their full volume, everyone is shocked to see the dog come trotting up, unharmed.

And what do you know: the dog has—nestled gently in its mouth—the most unexpected thing:

Gur Oevpx.

---

If you enjoyed these stories, you may also like Why You Need a Degree to Work For BigCo and more recently, A Venture Capitalist passes away peacefully, and....

Labels: java, lispy, ruby

  ¶ 3:10 PM

  Program in Java? You must be joking!

The Y combinator design pattern in Java is easily understood and can be used and maintained by unskilled, entry-level programmers.

Cuius rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.

You know, this kind of joke seems to rile Java apologists to no end. They come out of the woodwork with their web browsers set to flame. Absolutely no criticism of the language that powers everything from the web to space exploration (although there is never any talk of toasters) is allowed.

And do not criticize the culture in any way whatsoever. Although it’s perfectly ok to boast that Java is designed to appeal to the widest possible diversity of skill levels, you may not suggest that Java programmers are stupid. Or else.

I am trying not to tell anyone what to do, but I have an observation. Have you ever heard a politically incorrect but extremely funny joke about a member of a particular culture? You know you have. And furthermore, the joke was probably told by a member of the group victimized in the joke.

The unwritten rule is, if you’re a member, jokes are fair game. I was once with some, ahh, members of a religion that directly predated and evolved into Christianity. They were telling some jokes about their culture and religion. I had heard a few such jokes, but I wisely refrained from telling any. It’s not allowed. That’s the rule: outsiders may not joke.

So back to Java. Guess what? I’m an insider. I write Java code every working day. If you care about hollow appeals to authority, I once wrote a Scheme implementation in Java. I was also the team lead for JProbe Threadalyzer, a tool that analyses multi-threaded Java behaviour. And the development manager for JProbe Server-Side Suite (the aforementioned thread analyser, plus profiling, code coverage, and memory debugging tools). And various J2EE implementations with various degrees of Enterprisy-ness.

None of that makes me an expert. Nor does it make me right when I criticize or joke. But it does give me a certain smug right to joke. And don’t we all need a laugh from time to time, even if we’re laughing at ourselves? Perhaps especially if we're laughing at ourselves?

I think it’s a sign of good health to be able to laugh at ourselves and criticize our foibles. For all of the talk of Java as a “mature platform,” don’t you agree that “not taking criticism well” is a little, well, immature?

So since it’s Friday:

A Muslim, a Vegetarian, and a Java Programmer are traveling by foot, and they stop at a farm house to sleep for the night. The farmer is impressed at the obvious sophistication of the Java Programmer’s tales of Enterprise wonder, and he invites her into the house. The Muslim he sends to the hayloft, and the Vegetarian can sleep in the barn.

Well, the farmer is just pouring a night-cap and listening to the Java Programmer describe the time she knocked together a farm workflow application in less than a million lines of XML configuration code when there’s a knocking on the door.

He opens the door and the Vegetarian is standing there. “I’m sorry,” the Vegetarian apologizes, “But you slaughter animals in the barn, and eating meat is offensive to my beliefs. I cannot sleep in the barn.” The farmer thinks this is bunkum, but he was raised to be courteous to his guests, so he asks the Vegetarian to swap places with the Muslim.

The farmer knocks back his drink and turns down the lights. He can hear the Java Programmer setting up a sleeping bag factory to generate down-filled singleton sleeping containers in the living room. His wife is reading in bed, and he’s looking forward to catching up on the Wall Street Journal.

Well, he is just about to climb into bed when there’s a banging on the door. He opens the door, and the Muslim is standing there. “I’m sorry,” the Muslim apologizes, “But you keep pigs in the barn, and pigs are profane according to my beliefs. I cannot sleep in the barn.”

Muttering, the farmer rouses the Java Programmer off the couch and asks her to switch with the Muslim. He climbs into bed and has just started to read an interesting article on hedging commodity futures with convex derivatives when there’s a thunderous hammering at the door. His wife tells him to stay put and she goes to answer it. The farmer hears some excited talking, and a moment later his wife is at the bedroom door.

“Honey,” she says, “it’s the pigs.”

Labels: java, popular

  ¶ 11:59 AM

  Closures and Higher-Order Functions There has been a great deal of interest in closures lately, driven in great part by the fact that there is talk of adding some form of anonymous functions to the Java. Most of the time, people talk about “adding closures” to Java, and that prompts a flurry of questions of the form “what is a closure and why should I care?”

The discussion around closures tends to go on and on about the “closing over” of free variables and only lightly touch on the biggest change to Java: functions as first-class objects with a lightweight syntax for creating them. Making it easy to do something basic like define a new function is more than just a little syntactic sugar: it makes it easy to do new things with functions that were impractical when you needed a lot of boilerplate to make anything work.

Without understanding functional programming, you can’t invent MapReduce, the algorithm that makes Google so massively scalable.

I’m going to try to explain first class functions using Ruby (it is possible to write code that does exactly the same thing using the current Java feature set, however the result is so wordy that it obscures the basic idea being presented: call it accidental complexity, or perhaps yellow code.)

Ruby is a good language for demonstrating features that ought to be in Java. Like Java, Ruby uses squiggly brace syntax. Like Java, everything in Ruby is an object—whoops, Java has primitives. Okay, like Java, functions are represented as objects.

In Java you write:

interface IFromIAndI {
   Integer call(Integer a, Integer b);
}

IFromIAndI add_two_integers = new IFromIAndI() {
   public Integer call(final Integer a, final Integer b) {
      return a + b;
   }
};

(The Java convention is to name things in lowerCamelCase, but we’ll ignore that. If you need to print this essay on a dot-matrix printer you may want to make some changes first.)

In Ruby you write the function as:

add_two_integers = lambda { |a,b| a + b }

Later on, when you want to call your function in Java, you write:

add_two_integers.call(35, 42);

And if you like semicolons, you write the exact same thing in Ruby:

add_two_integers.call(35, 42);

You can do the same thing with multiplication:

multiply_two_integers = lambda { |a,b| a * b }

First Class Functions

In the examples above, functions look a little like methods. The Java version is obviously implemented as a method. But what we did in both cases was assign the resulting function to a variable. In Java, assigning a method to a variable is not particularly easy (it is possible using reflection).

Anything that can be assigned to a variable is a value. If it can also be passed as a parameter or returned from a method (or function), we say it is a first class value. Functions as first class values, or first class functions, are very interesting. For example, what can we do passing a function as a parameter to another function?

Hmmm. Well, I am breaking a cardinal rule of selling something. We’re talking about shiny new toys without identifying a problem to be solved. Let’s talk about my favourite problem: writing the same thing more than once, violating the DRY principle.

Here are two pieces of similar Ruby code:

adder_wth_acc = lambda { |acc, list|
   if list.empty?
      acc
   else
      adder_wth_acc.call(acc + list.first, list[1..-1]) # [1..-1] returns a copy of the list without the first element
   end
}
adder = lambda { |list|
   adder_wth_acc.call(0, list)
}
adder.call([1, 2, 3, 4, 5])

And:

multiplier_with_acc = lambda { |acc, list|
   if list.empty?
      acc
   else
      multiplier_with_acc.call(acc * list.first, list[1..-1]) # [1..-1] returns a copy of the list without the first element
   end
   }
   multiplier = lambda { |list|
   multiplier_with_acc.call(1, list)
}
multiplier.call([1, 2, 3, 4, 5])

What do they both do? Pretty much the same thing: they accumulate the result of some binary operation over a list of values. adder accumulates addition, and multiplier accumulates multiplication. You could call this a “Design Pattern.” If you did that, you would use the exact chunk of code everywhere. I would call that retrograde. Didn’t our predecessors invent the subroutine so we could eliminate writing the exact same piece of code over and over again?

Why can’t we do the same thing? Well, we can. A subroutine does the same thing over and over again, but it takes different parameters as it goes. What is different between adder and multiplier? Ah yes, the adding and multiplying. Functions. What we want is a function that takes a function as a parameter.

Well, we said that with first-class functions, functions are values and can be passed as parameters. Let’s try it:

folder = lambda { |default_value, binary_function, list|
   fold_with_acc = lambda { |acc, list|
      if list.empty?
          acc
      else
          fold_with_acc.call(binary_function.call(acc, list.first), list[1..-1])
      end
   }
   fold_with_acc.call(default_value, list)
}

Now we can use our function that takes functions as a parameter:

folder.call(0, add_two_integers, [1, 2, 3, 4, 5])
folder.call(1, multiply_two_integers, [1, 2, 3, 4, 5])

This is much better. When functions can take functions as parameters, we can build abstractions like folder and save ourselves a lot of code. Note that this would be a lot harder to read if we had to surround all of our functions with Object boilerplate in Java. That’s one of the key reasons why ‘syntactic sugar’—making it brief—is a big win.

And you know what? Functions are values, not just variables that happen to hold functions. These work just as well:

folder.call(0, lambda { |a, b| a + b }, [1, 2, 3, 4, 5])
folder.call(1, lambda { |a, b| a * b }, [1, 2, 3, 4, 5])

There’s just one problem (actually two, but I’m saving one for later): everywhere you use our new folder function, you need to remember that add_two_integers needs a default value of zero, but multiply_two_integers needs a default value of one. That’s bad. Sooner or later you will get this wrong.

What we need is a way to call folder without having to always remember the correct initial value. Should we extend our understanding of a function to include a default initial value for folding? If we’re thinking in Java, maybe our IFromIAndI interface needs a getDefaultFoldValue? I think not. Why should a function know anything about how it’s used? And besides, as we build other abstractions out of functions we’ll need more stuff.

If we aren’t careful, we’ll end up implementing the Visitor pattern on functions, and all of our brevity will go out the window. No, what we want is this: in one place we define that folding addition starts with a default value of zero and in another place we say we want to fold, say, [1, 2, 3, 4, 5] with addition. Then when we want to fold something else with addition, like [2, 4, 6, 8, 10], we shouldn’t have to say anything about zero again.

Adding Curry

What we need is a function that folds addition. Didn’t we say that functions are values that can be returned from functions? How about a function that makes a folding function? We should pass it our initial value and our binary function, and it should return a function that performs the fold without needing an initial value as a parameter:

fold_coder = lambda { |default_value, binary_function|
   fold_with_acc = lambda { |acc, list|
      if list.empty?
          acc
      else
          fold_with_acc.call(binary_function.call(acc, list.first), list[1..-1])
      end
   }
   lambda { |list|
      fold_with_acc.call(default_value, list)
   }
}

Now we can do the following:

adder = fold_coder.call(0, lambda { |a, b| a + b })
adder.call([1, 2, 3, 4, 5])
adder.call([2, 4, 6, 8, 10])

No more remembering that addition starts with a default of zero.

Actually, there’s a far simpler way to avoid having to remember the default value when you want to fold over addition. But let’s just play along so that we don’t have to come up with an entirely new set of examples to demonstrate the value of functions as first-class values.

Functional programmers (as opposed to the rest of us dysfunctional programmers) will recognize this as currying our folder function. Currying is when a function takes more than one parameter and you combine one of the parameters and the function to produce a function that takes fewer parameters.

Here’s a currying function in Ruby:

curry = lambda { |fn,*a|
   lambda { |*b|
     fn.call(*(a + b))
   }
}

(This is an improvement on an earlier version, thanks to Justin's comment.)

So you can use our new function to create an increment function out of our adder and a treble function out of our multiplier:

plus_one = curry.call(add_two_integers, 1)
times_three = curry.call(multiply_two_integers, 3)

If you are ever asked, “what good is currying?,” I hope I’ve given you an example you can use to explain why currying matters, and why people do it all the time (possibly without explicitly naming it). Although it doesn’t look like much when looking at trivial examples like functions that multiply by three, it’s much more useful when creating folders and mappers where you want some of the parameters to remain constant.

Composition

Our examples combined functions and non-functions to create new functions. Here’s an example from a recent post, Don’t Overthink FizzBuzz, where I give a method for composing two functions. The idea is that if you have multiple functions that each take one argument, you can combine them using compose. I also have a method that generates functions, carbnation:

# fizzbuzz.rb

def compose *lambdas
  if lambdas.empty?
    lambda { nil }
  elsif lambdas.size == 1
    lambdas.first
  else
    lambda do |n|
      lambdas.first.call(compose(*lambdas[1..-1]).call(n))
    end
  end
end

def carbonation(modulus, printable_form)
  i = 0
  lambda do |n|
    (i = (i + 1) % modulus) == 0 && printable_form || n
  end
end

print(((1..100).map   &compose(     carbonation(15, 'FizzBuzz'), carbonation(5, 'Buzz'), carbonation(3, 'Fizz'))).join(' '))

The simple explanation of how it works is that carbonation generates functions that replace every so many elements of a list with a printable string. Compose composes any two or more methods together. So if you want to print out 100 numbers, but replace every third number with “Fizz,” every fifth with “Buzz,” and all those that are third and fifth with “FizzBuzz,” you generate a function for each replacement, compose them together with compose, and then map the numbers from one to one hundred to the resulting überfunction.

When you look at this today, it seems weird and unreadable by Java standards. I wonder if adding first-class functions with simple syntax to Java will lead the Java community to a place where code like this will not appear out of place?

Just one more thing

So we started by saying that people are getting hung up on what makes a closure a closure, and there has been less emphasis on the benefits of using functions as first-class values. Did you notice that our folder function actually includes a non-trivial closure?

If you look at the fold_with_acc function, it makes use of binary_function, a variable from its enclosing lexical scope. This is not possible with the current version of Java: if you translate this to Java, when you make fold_with_acc and anonymous inner class, you will have to copy binary_function into a final member to use it. It simply won’t compile if you try an idiom-for-idiom translation, even adding explicit types.

And then if you look at the anonymous function it returns, lambda { |list| fold_with_acc.call(default_value, list) }, that anonymous function uses default_value,another variable from the enclosing lexical scope. Once again you will have to fool around with final variables to make this work, or perhaps declare full-fledged object with constructors.

(If you try writing this simple example out in Java, you quickly find yourself inventing a lot of classes or interfaces. And they have some complicated types, like a function taking an integer and a function taking two integers, returning a function taking a list of integers and returning an integer.

After twenty minutes of that, you understand why the ML and Haskell communities use type inference: If the types are that complicated, it’s incredibly helpful to have the compiler check them for you. Yet if the types are that verbose, it’s incredibly painful to write them out by hand. Even if your IDE were to write them for you, they take up half the code, obscuring the meaning.

You also get why the Ruby on Rails community doesn’t care about type checking: types for CRUD applications are way less complicated than types for first-class functional programs.)

That’s Interesting

Part of the interest in closures is in simplifying the syntax around functions, and part of the interest is in the way that access to enclosing scope would simplify a lot of code. There’s a whole debate around the value of simplification in a world where all serious languages are Turing Equivalent.

I hope you’re convinced, by now, that programming languages with first-class functions let you find more opportunities for abstraction, which means your code is smaller, tighter, more reusable, and more scalable.

For me, simpler is just nicer until something reaches a certain tipping point: when it becomes so simple that the accidental complexity of using it goes away, I will start using it without thinking about it. Tail optimization is like that: as long as recursion is slower than iteration and sometimes breaks, I have to think about it too much. But when I’m not burdened with “except…” and “when performance is not a factor…” it becomes natural.

And then something interesting happens. It changes the way I look at problems, and one day I see a whole new way to do something that I never saw before. Functions as first class values are definitely one of those things that change everything.

Further Reading

If this has whet your appetite for more, Structure and Interpretation of Computer Programs is the book on higher-order functions and how they can be used as building blocks to create more elaborate abstractions such as object-oriented programming.

The Seasoned Schemer devotes an entire book to the uses of functions. Although the examples are in Scheme, the language is dead simple to learn and the techniques in the book can be applied to Ruby and Java (or at least to a future version of Java where you do not need functors).

The second edition of Programming Ruby is an indispensable guide. Even if you will not be using Ruby immediately, pick it up and discover why so many people are lauding the language's simple, clean design and powerful Lisp-like underpinnings.

As the author says, “Higher-Order Perl: Transforming Programs with Programs is about functional programming techniques in Perl. It’s about how to write functions that can modify and manufacture other functions.

“Why would you want to do that? Because that way your code is more flexible and more reusable. Instead of writing ten similar functions, you write a general pattern or framework that can generate the functions you want; then you generate just the functions you need according to the pattern. The program doesn’t need to know in advance which functions are necessary; it can generate them as needed. Instead of writing the complete program yourself, you get the computer to write it for you.”

It’s worth reading even if you have no intention of using Perl: the ideas span languages, just as SICP is worth reading even if you don’t use Scheme at work. And be sure to read Higher-Order JavaScript and Higher-Order Ruby. They translate HOJ’s ideas to other languages.

Notable Follow-ups:

Some useful closures, in Ruby: “The Dylan programming language included four very useful functions for working with closures: complement, conjoin, disjoin and compose. The names are a bit obscure, but they can each be written in a few lines of Ruby.”

From Functional to Object-Oriented Programming: “OO allows a traceable connection between the conceptual design level and the implementation level. Concepts have names, so you can talk about them, between programmers and architects.”

HOF or OOP? Yes!: “First-class functions are a natural fit with OO, as evidenced by their presence in OO languages that aren’t glorified PDP-11 assemblers with some OO stuff bolted on the side.”

But Y would I want to do a thing like this?: “To truly learn a new tool, you must not just learn the new tool, you must apply it to new kinds of problems. It’s no good learning to replace simple iteration with first-class functions: all you’ve learned is syntax. To really learn first-class functions, you must seek out problems that aren’t easily solved with iteration.”

Labels: java, lispy, popular, ruby

  ¶ 11:55 PM

  Please design a deck of cards in Java Dear Future Colleague:

I’ve been asked to perform a quick technical evaluation of your résumé before we ask you in for an interview. You obviously have the right kind of experience and I’m looking forward to meeting you soon.

We are asking all candidates to perform a little exercise before coming in for the first meeting. I realize you have a great deal of relevant experience, so this will not take very much of your time at all.

And I’m sure you appreciate the fact that we value ability and merit above certifications and other pieces of paper.

Please design a deck of cards in Java

Imagine that we are writing a casino program. We are not going to write the whole program right now, just the part of the program that has to handle the decks of cards to be used by the rest of the program.

If you are not familiar with the kind of cards used in European card games (like Poker, Bridge, Blackjack, Crazy Eights, Rummy, and so on), please write back and I will give you a different problem. You should be comfortable with concepts like the ranks of the cards, the suits, shuffling, and dealing.

Your task is to design the interfaces and/or classes we would need for the deck(s) of cards. At a bare minimum, your classes should handle everything we need to know about decks of cards, the cards themselves, and operations on decks of cards like shuffling, dealing, removing cards from a deck (some games have one or two jokers, some don’t, some only use the cards from 9 and up, some from 7 and up, some use them all), and combining decks (Canasta uses two, four, six, or more decks of cards with jokers!)

You do not need to worry about the mechanics of games like hands of cards, ranking Poker hands, knowing about Trumps or Bowers (as in Euchre and Bridge), discard piles (as in most games), or melds (as in Gin, Rummy, and Canasta). Imagine that other people will write all of that stuff using your classes for decks and cards.

Please be specific about the interfaces, abstract classes, and concrete classes you will need. There is no need to actually write the bodies of methods, but please be specific about what the methods are called, what parameters they take, and what they return (if anything).

I am especially interested in the relationships between the classes. Although you don’t have to write out each method, if you expect that a method would call other methods in your design, please say so.

For example:

class Deck {

// calls Card.arrangeRelativeTo(Card othercard)
public void shuffle () { ... }

}

You can see that in this hypothetical design cards have some ability to arrange themselves relatively to each other and I am documenting that Decks can be shuffled and they use the Cards’ arrangeRelativeTo method to do so. Obviously, you don’t need to follow that design. It’s just an example.

This extends to constructors. Does creating a Deck create Cards? Or does it use Cards that already exist? Or are Cards not even objects but are represented by primitive types?

About UML

You can just write out the skeleton of the classes and interfaces. If you prefer to use UML, be my guest. As long as your design answers all of the questions I have, use whatever notation you prefer. Just don’t fall into the trap of letting the notation drive the design: just because a certain type of UML diagram doesn’t indicate the CREATES-A relationship, that doesn’t mean you shouldn’t add it: what’s important is the design, not the document.

Requirements?

Feel free to email or call with any questions you might have about requirements. This is not meant as a test of your ability to read my mind about what I want or to ask insightful questions. So, it’s ok to ask me questions. If you have a choice to make, it’s also ok to just decide.

For example, you might wonder how to represent which cards are left in a deck after dealings some out. Should you use a standard OO pattern like a List or Set? That might be fine if our Casino program is a single-user game. But if we are running a web-based virtual casino with many thousands of users, performance might be important enough that we consider using something like a bitfield for each deck.

If you want, you can ask what’s more important. Or you could just decide for yourself. Using a bitfield for performance is a fine decision. So is having a standard OO design. Each works well for a particular set of requirements.

So don’t be too concerned about asking a million questions. I just want to get a basic idea of your comfort level designing OO software.

Thanks,




Reg Braithwaite

p.s. This isn’t a trick question. There’s no right answer, and as I said above I don’t even expect full implementations, so you don’t even have to write code that compiles.

There is absolutely no need for a bunch of stuff I didn’t ask about, like requirements in three-ring binders or JUnit test cases. I know that you are probably tempted to show off your depth of experience and SDLC knowledge, however I really only want to know how you would approach the design in this question.

Please save the other stuff for the interview. Just because I don’t need to know about it right now doesn’t mean I don’t agree that it’s important!

Labels: java, jobs

  ¶ 10:00 AM

  Trick or Bleep? I like to post fun stuff on Fridays. I also repost old stuff from time to time when my brain is page faulting or when something I’m reading reminds me of an old post. Today both were true: I spotted this post about interviews going wrong and I remembered an interview where I was the hapless victim.

There has been some refreshing commentary on the post and also on reddit. I want to give my thoughts on one issue. Was the interviewer posing a “trick question,” trying to find out how I negotiate conflict? This subject has attracted a lot of attention since Joel Spolsky recently raised the issue, and while it didn’t cross my mind at the time, it’s worth considering.

The question posed to me was, list all of the ways to call instance and class methods in Java. I listed a bunch of things, and at the end, I included:

    someInstanceVariable.staticMethod();
    // calls the staticMethod of someInstancevariable's declared class

The interviewer told me I was wrong, and I shrugged, explaining that I thought I was right, but no big deal if I was wrong, since I never use that style of call, so it wasn’t an issue. The interviewer later told me that he did not like my answer, and indeed I did not get an offer.

If this was a trick question, ok, you had me! I am not afraid to argue points where I believe there is a direct connection between the issue and the outcome of software development projects. If I really believe it is irrelevant, I don’t argue even if I have a personal preference. So I’ll happily go along with any particular coding style you advocate (including none), and if you insist that I use Eclipse for Java instead of TextMate, fine.

The problem with that question (let’s be clear, it’s my problem, not the interviewer’s problem), is that I don’t really care whether Java lets you call a static method via an instance of a class. The reason I don’t care, as I explained to the interviewer, is that I will never allow that code to get into the repository.

For those who are too busy with Lisp to know all of Java’s warts, the problem is that static or class methods are never polymorphic. So if you write:

    // (yes, I know about public vs. private. These are obviously in 'package scope')

class House {
    static String doorAction () { return "closes and locks"; }
}
class S___House extends House {
    static String doorAction () { return "bangs"; }
}

and you do this:

    final House structure = new S___House();
System.out.println(structure.doorAction());

You get closes and locks instead of bangs. Always. This is not what happens with instance methods, and that’s because so-called ‘static methods’ in Java are really global functions that live in class namespaces. The compiler resolves the function doorAction by looking up the declared type of structure at compile time. Its actual type at runtime is irrelevant. C++ programmers recognize this as the difference between virtual and non-virtual functions.

Back to the “trick question.” My problem is that since I never have and never will use this, I’m not going to argue whether it’s legal or not. It will never have the slightest impact on any project I’m on. If you want an argument, let’s discuss why you think we should use this idiom in production code.

I honestly don’t think it was a trick question. If the interviewer knew it was legal and wanted an argument, he could have (and I suggest should have) chosen a different thing to argue, something a little more obvious, such as telling me it is legal and polymorphic, and then seeing whether I (a) know that it is not polymorphic, and (b) argue with him.

I don’t use questions like this, but I can see the value of this second question: a really experienced person knows exactly why it isn’t polymorphic and can discuss the kinds of bugs you will get if you try to write code depending on it.

What do you think? Was this really a trick question? If so, should I have been more aggressive in arguing the subtle points of Java law?

p.s. The interviewer later told me that he did not like my answer, and indeed I did not get an offer: one benefit of much water having passed under the bridge is a more balanced perspective. I no longer assume that this one question is the only reason the interviewer decided I was not appropriate.

I may have been overqualified, too talkative, too reflective, or even too meticulous (when given the programming challenge of permuting a string, I was apparently the only candidate to ask what the output should be when the string contained duplicate letters). Perhaps the interviewer had already decided the interview outcome before this question was discussed.

And do you know what? I’m not so sure I wouldn’t have reacted the same way as the interviewer. One of the big “No Hire” flags for me is a candidate who doesn’t fundamentally “get” a programming language. Anyone can “Learn Blub in 21 Days,” memorizing code snippets and patterns by rote. But such candidates often have no clue how a language works, how its features interact with each other to make those memorized code snippets work.

Let’s say that I’m interviewing and I don’t know that Java (which isn’t particularly OO in theory or in practice) allows this bug of calling a static ‘method’ via an instance of a class. Is that so bad? Of course not, it’s a wart on the language. It’s not like knowing that it is allowed reveals a deep understanding of how Java works. So not knowing this isn’t a fundamental flaw in a Java developer or interviewer.

Now a candidate tells me that this thing works. Well, I might jump to the conclusion that the candidate really doesn’t get the difference between static and instance methods, that the candidate will have trouble understanding the various scoping issues involved with instance members and static members. I could easily believe that this candidate will draw a complete blank when working with inner classes.

An interviewer who didn’t happen to know this bit of Java trivia might reasonably infer that thinking it works betrays a superficial knowledge of Java.

Labels: java, jobs

  ¶ 8:14 PM

  In praise of informed choices

First, a word from our sponsor

You know, this whole “Blub” thing has too many negative connotations. It has become, like “Star-Bellied Sneetch,” a way of labeling people.

“You use J, therefore you’re a Blub Programmer.”

“There’s no such thing as Blub, therefore I can’t be a Blub Programmer.”

For the remainder of this post, we are going to discuss things in terms of informed and uninformed choices. This is a functional description and it focuses on a one-time behaviour. If you like the old terms, you know where to find grep.

One argument against the idea that there is one overarching continuum of language or tool “power” is that tools specialize. The most appropriate tool for building CRUD database-backed web applications may not be the most appropriate tool for building interactive games.

Success through specialization

Within a particular specialization, there is still a continuum of power. There may be a programmer who insists that Visual Basic backed ASP pages provide all the power she will ever need for CRUD web applications, and there is no need to Ruby, ASP.NET, or any of the other advances on the technology she likes. This sounds remarkably like she is making an uninformed choice, doesn’t it?

The specialization argument is invoked quite often. When I hear it from someone who has taken the time to become comfortable with several different approaches to solving a problem, I give it some credence.

But how often do we hear someone say, “Oh, language X. Yeah, I hear that’s kind of specialized for Artificial Intelligence. And Y is probably terrific if you need to do some startup thing where you need to make a lot of changes as you go. I haven’t tried it, because I don’t do Y-like stuff. But for my purposes Z is the way to go. Each language has its specialization, and Z is best for what I’m doing.”

Are those the words of someone who really understands X or Y and why anyone would need those weird features X and Y programmers boast of? Or what parts of languages X and Y would or wouldn’t apply to the problem at hand? Or is this just a way of sounding Fair and Balanced?

Just because tools may provide specialized benefits depending on the problem at hand, that doesn’t mean that the particular tool a programmer chooses is the best possible or best available. In other words, uninformed choice can be local to a problem domain.

In a fight between a bear and an alligator

My second conjecture about specialized tool hypothesis is that most tools evolve over time away from specialization and towards generalization. Java, the language often mentioned in the same breath as uninformed choice, began its life as a specialized language for embedded programming. Toasters, set-top boxes, that kind of thing. Other languages have seen the same trend towards trying to solve all problems for all people.

The older a language or tool is, the more likely it is a general-purpose tool. The converse tends to be true: the younger a language or tool is, the more likely it is to be specialized. The latter seem to be true even if the designers and sponsors intend it to be a general-purpose tool, because younger tools have smaller ecosystems.

Take a language with a relatively small ecosystem: it may have been designed as a general-purpose tool, but if the the most popular stable, widely used libraries and frameworks support building Ajax-ified CRUD applications, it is a specialized tool as compared to a language that seems to support building everything up to an including interplanetary navigation.

So It seems that some languages boast flexibility, others specialization. It seems unrealistic to expect that the specialized language can beat the generalized language. Unless you are comparing the languages on the basis of the specialized language’s “home turf.” In a fight between a bear and an alligator, terrain determines the outcome.

Now someone argues, “Hey, you wouldn’t try to fight a fire with a Maserati or drive the Autobahn on a Segway.” The specialization argument. Ok. But is that really the comparison? All too often, I hear that argument, but what I see in the toolbox is a mini-van, the king of popularity, the vehicle that does several different things equally poorly.

Honestly. Are programmers clinging to Haskell, Erlang, and Postscript because their needs are specialized and within their niche these languages are the best possible choice? Or are they vocally defending a language that does an awful lot of things in awkward ways against languages that solve their exact problem in an elegant way?

Java is not an uninformed choice, and neither is Visual Basic

Languages and tools are not uninformed. It’s the breadth of experience applied to making a choice that counts. Making a popular, comfortable, established, unfashionable, safe choice does not make you uninformed. An uninformed choice is made in ignorance of the benefits of making other choices.

If you think that your next CRUD application would need anywhere from one half the code to one tenth the code if you used a specialized meta-programming tool like Ruby on Rails, but you’re sticking with ASP because that’s what the client asked for, you’re making an informed choice.

If you write a new application and make heavy use of functional programming constructs for the first time, good for you. If you choose to leave an existing application more or less as-is and you don’t refactor every method to remove mutable local variables, good for you again. You’re making an informed choice.

Some uninformed choices are conservative choices, but so are are some informed choices. You can’t tell the difference merely by examining the language or tool chosen.

Conservative? Or just Uninformed?

I have a little litmus test for identifying an informed choice that just happens to be conservative. I don’t claim it’s infallible, and I have done absolutely no research to back it up. But in the interest of keeping the amusement value up, here is my proposal:

When you see a program written in a conservative, “safe” language, and you want to know whether the programmer is a made a fully informed choice, examine the source code looking for evidence that the programmer has been exposed to other programming paradigms.

Uninformed programmers invariably stick to whatever has been promoted as the sole, orthodox way to write programs for their language. If they need to work around a language limitation, they will do so using well known conventions such as widely disseminated “design patterns.” They can invariable name a dozen or more such patterns, but can never name a single language that handles these problems in a different way.

The informed but conservative programmer has learnt something from other tools, other languages. The principles find their way into her work. A conservative programmer might have extremely pragmatic reasons for doing some work in Javascript. But she uses the Prototype Library to implement higher-order functional programming. Or she might need to build something really big and hairy in C++. But she’ll implement Lisp’s map and reduce as a library so that C++ programs can vectorize on a grid with thousands of computers.

The uninformed programmer may have heard of these things, but not only will they eschew other tools and languages, the eschew the ideas behind them as well.

Although the act of implementing a more powerful language on top of a more conservative language is sometimes frustrating and often derided by purists, it is a sign that the programmer has thought deeply about the best way to solve a particular problem, and is not afraid to port what they like from one environment to another.

What do you think? Do informed but conservative programmers incorporate features and paradigms from other tools and languages into their work?

Labels: java

  ¶ 9:52 PM

  Are we Blub programmers? From time to time I open my email and find someone asking a question:

What the hell is Blub? I take from context that it may be a pejorative generalist term for programming languages that encourage writing pablum instead of programs. Or maybe it really is a new language out there that has a huge following I'm unaware of.

Actually, Blub is a hypothetical programming language Paul Graham invented when describing something very interesting: the Blub Paradox:

Blub falls right in the middle of the abstractness continuum... As long as our hypothetical Blub programmer is looking down the power continuum, he knows he's looking down. Languages less powerful than Blub are obviously less powerful, because they're missing some feature he's used to. But when our hypothetical Blub programmer looks in the other direction, up the power continuum, he doesn't realize he's looking up. What he sees are merely weird languages... Blub is good enough for him, because he thinks in Blub.

The interesting things about this paradox is that almost any language could be Blub. The pre-requisites for a language being Blub are (a) there is at least one language less powerful than Blub, (b) there is at least one language more powerful than Blub, and (c) that there be at least one programmer using Blub who accepts (a) but refutes (b) because he or she cannot see how the more powerful language is more powerful. She does not think in the idioms that the more powerful language affords.

When I use the term, I am thinking of the language and also the programmers around it. Could Java be Blub? Sometimes, possibly often, but only when I'm thinking about Java programmers who dismiss Ruby's features as unnecessary. Could Ruby be Blub? Sometimes, but only when I'm thinking about Ruby programmers who dismiss macros as unimportant.

Could Lisp be Blub? I suspect that Erlang and Haskell programmers might say that it is, provided we can find a Lisp programmer who feels that all progress in programming languages stopped when Common Lisp was standardized.

At the same time, Java is not Blub when I am thinking of programmers who are perfectly aware of its shortcomings and deliberately Greenspun around them for pragmatic reasons. The same goes for any other language: it is sometimes Blub, and sometimes not Blub.

So... I use the term "Blub" to refer to a programming language in the context of intransigent programmers who feel that their chosen tool is the best tool possible.

Programming consists of overcoming two things: accidental difficulties, things which are difficult because you happen to be using inadequate programming tools, and things which are actually difficult, which no programming tool or language is going to solve.

This provokes a very obvious question: How do we know which things are accidentally difficult and which are actually difficult? Is it only because we haven't discovered the right tool yet?

It's easy to find a Java programmer who believes that all of the Design Patterns in the GoF's book are necessary. She believes that the difficulties of applying those patterns are actual difficulties of programming systems. It is only when she learns a different language that she realizes how the patterns were strongly driven by limitations in Java's object model.

At that point she has an epiphany and understands that what she thought were actual difficulties were merely accidental difficulties. And the line between "accidental" and "actual" moves for her.

No matter how much each us us thinks we know right now, are we nevertheless like this Java programmer, unable to see the difference between accidental and actual differences because we simply haven't discovered a more powerful tool?

Are we Blub programmers?

update: In praise of informed choices and Lisp is not the last word

Labels: java, lispy, popular

  ¶ 4:40 PM

  If Sneetches with Stars use Java, and Sneetches without Stars use Ruby, who uses ML? ML is a programming language featuring type inference: you don’t have to encumber your code with type declarations, the compiler can figure them out for you. So… are type inference languages like ML for Sneetches with or without stars? Or another kind of Sneetch entirely?

Now, the Star-Belly Sneetches had bellies with stars.
The Plain-Belly Sneetches had none upon thars.
Those stars weren’t so big. They were really so small
You might think such a thing wouldn’t matter at all.

Update: More than a few people have written that Steve Yegge's association of static typing with neatness and dynamic typing with slovenliness runs opposite to their impressions of the kinds of people who strongly prefer one or the other. I used Steve's terms in the original post, partly because I thought people would get the same joke I thought Steve was making. It looks like they don't, nobody wrote to say "LOL." I have changed the terms to something that represents what I think of the cultural divide between programmers who like Java and programmers who like Ruby.

Let’s review. Sneetches with stars like to use a colour-coded label maker to label the drawers, boxes, and files in their office. Once glance at everything and you know what it holds. Sneetches with stars add extra labels even when you don’t need them. For example, if a box is labeled ‘tax receipts’, each piece of paper inside has a post-it note saying tax receipt’, even if it’s obviously a tax receipt and lives inside the tax receipts box.

What is Stariness?

Sneetches with stars like these languages we say are statically typed. What do we mean by the word static? We mean it can be resolved at compile time. Other words for this idea are invariant or constant. Sneetches with stars like languages where the type of each entity can be resolved at compile time.

Some people are always critical of vague statements. I tend rather to be critical of precise statements; they are the only ones which can correctly be labelled "wrong."

Let’s dive into this a little deeper. (My apologies to my readers who were actually paying attention to the stuff in first year computer science that isn’t a requirement for getting a job at BigCo.) What does it mean when we say “something can be resolved at compile time”? That expression is laden with implementation details like assuming we’re using a compiler. But it’s a convenient short-hand for saying something about the program that is true every time you run the program.

Consider the final declaration in Java. If you write:

final String snafu = "situation normal...";

We know that the variable snafu always holds a reference to the constant string "situation normal...". No matter what data you feed to your program and how you mangle it, snafu will always be "situation normal...". Do you agree? (Joe Campbell, put your hand down. Yes, there is a back door way you can change the contents of a String in Java.)

Java can take advantage of this to perform constant propagation. Everywhere you write snafu, Java can substitute "situation normal..." and throw away the variable lookup. To get away from arguing about back doors in the String class, let’s consider one of the primitive types, a boolean. If you write:

final boolean foo = true;
    // code without assignments to foo
    if (foo) {
        // do something
    }
    else {
        // do something else
    }

Wouldn’t you agree that the compiler can get rid of the variable lookup and the if statement? The path through the code is always through the // do something path every time you run the program.

Now back to the word stariness. We really mean the amount of stuff about the program that can be resolved at compile time, or if you prefer, the amount of stuff that is true every time you run the program.

In the example above, the compiler can figure out which branch the program will follow at compile time, because that variable is true every time you run the program.

Stuff that is always true is useful. For most programs, we have an idea in our head about “correctness.” What we mean when we talk about a program being correct is that it produces desirable results every time you run the program.

A formalist is one who cannot understand a theory unless it is meaningless.

Stariness is thus similar to correctness. And that’s why a lot of people, the Sneetches with stars, are obsessed with it. Being able to “prove” something about their program (“the method call foo.bar(5) never throws a MethodNotImplemented exception”) feels a lot like being able to prove that their program is correct.

It feels a lot like it, but it isn’t the same thing. The reason it isn’t the same thing is that while its true that a program throwing MethodNotImplemented exceptions is probably not correct, it’s not true that a program that doesn’t throw such exceptions is correct. It just feels, somehow, more likely to be correct because we’ve thrown out one of the infinite ways it can be incorrect.

Now that we’ve dispatched that logically, let’s be clear about something: just because stariness does not enforce correctness, it doesn’t mean that stariness isn’t useful. Stariness is useful. Period, no debate.

Back to inferences

Type inference is also for Sneetches with stars. A language with type inference resolves the type of each entity at compile time by inspecting the program and figuring the types out through inspection. It’s a lot like the way a compiler can look at the Java code above and figure out that you always // do something and you never // do something else. The code looks sorta like you could go either way, but the compiler knows better.

Languages with type inference look like variables can have any type, but the compiler knows better. Remember the labels that the verbose declaration Sneetches with stars love? Type inference languages still have labels, but the labels are hidden inside of the files and boxes where you can’t see them.

Remember when manufacturers used to put their labels inside clothes instead of right across the front? Same thing. The rules for what goes where are strictly enforced, it’s just that if you can figure out what goes where with a bit of common sense, you don’t need a label or a post-it note.

Compare these two snippets of Java:

final String[] words = { "foo", "bar", "blitz" };
final int word_length = words.length;
final String[] anagrams = new String[word_length];

…and…

final words = { "foo", "bar", "blitz" };
final word_length = words.length;
final anagrams = new String[word_length];

Hey, if a variable is final, we can figure out its type in Java through simple inspection. Making that work in the compiler is something an intern ought to be able to do over a Summer work term!

(Frank Atanassow pointed out that techniques exist for inferring the types of nearly all Java variables through inspection of programs. But this simple case is enough for our purposes.)

So if we take a valid Java program and simply erased type declarations whenever we could logically deduce the type of the variables (using our simple scheme), but left them in whenever we were not sure of the final type of the variables, we would have exactly the same program. Nothing about it has changed except it has fewer symbols. It’s just as starry, it is just as static, it is no more or less correct than it was before we erased some symbols.

And you over there itching to say something about IDE refactorings and auto-completions: None of those go away either. You can rename things and move things and press command-tab to get an object’s methods whenever you like. So… would you agree that type inference of this sort doesn’t change a starry program into a starless program? This isn’t about stariness versus starlessness, it’s about the obsessive-compulsive desire to label everything.

The bottom line: type inference does not change a statically typed language into a dynamically typed language. It’s still starry.

So why can’t the Sneetches without stars use type inference?

Think of types as being like values and objects like variables. A statically typed language is one where there are no type re-assignments. Some languages enforce this. But if you write a program in a static way, you can still reason about it. This is why lots of people think that we can “neaten up” languages like Ruby by adding type inference to the compiler: they're thinking about programs that are neat to begin with, but we happen to have written them in a language for Sneetches without stars.

And whenever someone talks about a refactoring IDE or an auto-completing IDE for a dynamic language, they’re talking about performing some type inference on Ruby programs that are written in a static way. So… what’s the holdup? We said we could add type inference to Java in a Summer. Where’s the intern to add it to Ruby?

Programmed. In me somewhere, he thought, there is a matrix fitted in place, a grid screen that cuts me off from certain thoughts, certain actions. And forces me into others. I am not free. I never was, but now I know that; that makes it different.

The problem is that the set of all programs that are "starry" is a subset of the set of all programs that parse correctly. So either not all starless programs are neat, or not all portions of a starless program are neat, or both.

Let’s compare back to our Java snippet. Remember:

final boolean foo = true;
// code without assignments to foo
if (foo) {
    // do something
}
else {
    // do something else
}

The compiler could infer that we always follow the first branch because it knows that final variables are not reassigned. They’re immutable. What happens if we erase the final keyword as well:

boolean foo = true;
// code that might have assignments to foo
if (foo) {
    // do something
}
else {
    // do something else
}

Now the job is much harder. We have to examine all the code in between the declaration and the use of foo. If there are any assignments involving things we can't know until runtime, we can't know the value of foo until runtime.

For a very large class of programs, we cannot infer the contents of a variable with less runtime complexity than running the program for every possible input. This is why compilers have limitations on the optimizations they can perform, and humans still need to do some thinking about writing fast programs.

This exact same thing happens with types. In statically typed languages, types are never re-assigned. Whether explicitly declared or inferred, they're immutable. But in languages like Ruby where methods can be added and removed dynamically, where messages can be forwarded dynamically, where we can even send messages dynamically, the types of objects are fully mutable.

In starless languges, there is no final keyword on the types of objects. We can no longer infer the type of a variable in any but the simplest, degenerate cases.

The type inference problem in dynamically typed languages is exactly the same as the inferring the possible contents of a variable problem. The inferring the contents of a variable problem is doable for a restricted set of programs. And the way we tell the compiler that a variable is a member of this restricted set is with the final keyword.

Likewise, the way we tell a compiler that the type of a variable is also restricted is that we use a language where the type of every variable is final. It’s the same thing: we don’t reassign final variables and we don’t change types on the fly.

Starlessness is not about writing programs without labels. Starlessness is when you write dynamic programs. Dynamic doesn’t mean ‘unlabeled’. As I showed above, if the final keyword is there, the label is mostly optional. But if you don’t have final, you’re writing dynamic programs.

Truly starless programs have dynamic types: types that change at run time. they are not always one thing or another. For example, what if you write an Object-Relational Mapper (“ORM”) that reflects on the database structure at run time. That is, you can change columns in a database table and you get new getters and setter methods in your program. Without recompiling.

In a fully static language (with or without type inference), you can’t do that. Think of Java’s JDBC: you have to fool around with methods that get values and pass a column name as a parameter. Or maybe you create a hash. And C# is getting this capability, but of you look closely you still have to define the “type” of a query through the LINQ syntax.

Are Sneetches with stars ever starless?

A dynamically typed language lets us define an object holding a database row with methods for each column. But we can’t know at compile time whether our program will throw a MethodNotImplemented exception because we don’t know whether someone will monkey with the database structure. That sounds bad.

But what happens if you write the same thing in a neat program? Aha! a SQLException! it seems that there are dynamic things that must be dynamic no matter what you do.

This is a specific case of Greenspunning. There are some facilities of dynamic languages that you are going to need. If you don’t have them built into your static language, you will build them yourself or use a framework that has already built them for you. Other examples I have seen in Java programs include:

Spring and Hibernate;
Any use of Class.forName(...);
Any use of dynamic proxies;

In essence, you’re being a Sneetch without a star but twisting your starry language to permit starlessness. And for those portions of the program that are no longer nice, starry bundles that can be examined at compile time for invariant behaviour, you are indeed in dynamic territory and have to live with the risks.

In my experience, all non-trivial starry programs contain this kind of starlessness. To my admittedly inexperienced eyes, starlessness is the hallmark of expert programming in starry languages ("expert" does not necessarily mean "more desirable," especially in the minds of those who believe that programs should be written and maintained by mediocre developers).

Eating cake

So… can we say that since you can write starless programs in neat languages, you can have the useful benefits of stariness when you need it and the flexibility of starlessness when you need that too? Isn’t that better?

Yes, you can say that. And you may be right, for you. The Boo people believe that: their language has a duck keyword for when you feel like a Sneetch without a star. Be aware that at this moment in history, languages designed for Sneetches without stars seem to have much better features for writing starless programs than languages for Sneetches with stars. So my observation is this:

If you dislike the verbosity of starry languages like Java but like the feeling of safety, try a type inference language. Don’t go to a starless language if you don’t intend to actually write dynamically typed programs.

My experience is that if you are frustrated by the amount of work you have to do to express the algorithms in your head, you should look at a language that removes your frustration. If you're using Java and don't like the verbosity, find a language that celebrates brevity while preserving static typing. But if you're using Java and find yourself pushing more and more logic out of java because its type system is too static or too inflexible, you should consider a language with a different approach to typing.

Computer languages differ not so much in what they make possible, but in what they make easy.

Why would the Sneetches without stars use starless languages?

Writing starless programs on top of neat languages is exactly the same thing as writing automatic memory management routines on top of a manually managed programming language or writing functional programs on top of a noun-centric object-oriented language.

You can take that statement as an argument in favour of specialized languages for Sneetches without stars or as an argument against them. My guess is that the above statement is true and a Rorschach Inkblot: You will interpret it as confirmation of your existing prejudices.

Labels: java, popular, ruby

  ¶ 3:34 PM

  The trade-off between power and ease of use in library interfaces Rusty has another great contribution to the discussion about locking down interfaces (a/k/a "final good or bad" also a/k/a "concrete good, abstract bad").

Rusty points out that restricting an API makes it more accessible:

The I in API stands for interface, and interfaces are for people, not just machines. APIs can be complex, confusing things... The smaller and simpler the API is, the easier it is to learn and use; the more likely it is that the API will be used correctly.

I'm going to repeat and double underscore my suggestion that there are different approaches to the problem of designing software that other programmers must incorporate into their own designs.

Rusty points out the obvious: there is a far greater 'market' for smaller and simpler things than for powerful things:

For instance, you can switch a class from storing persistent data in a file to storing it in a database or vice versa. Sometimes this is important; but be honest: how many times have you really needed to do this? Out of the thousands of classes you’ve written, how many have had significant changes in their internal data structures? Maybe 1 in 10? And in how many have you actually needed multiple simultaneous implementations? Maybe 1 in 100, or less?

True. But ummm... Does it matter whether you want to do something like this once a day, once a week, one a month, or once during a project? If you ever want to do this, why shouldn't it be possible?

Let me jump in and answer the question for you: there's a trade off to be made between power and ease of use. The power to do unusual things (like climb roof cracks or modify frameworks) comes at the expense of ease of use (as measured by the narrowness of the interface).

So if you make it possible for me to do powerful things, you might make your code harder to use for some class of people who never need to do these things. I'm all for that. There's a knob you can turn when you create your design: power vs. accessibility for the masses.

(I don't say power vs. simplicity: thanks to the Turing Tar Pit, it is possible to make something extremely simple, but have extraordinary power because you have provided the basic building blocks that allows your client programmer to do almost anything. For example, the programming language Scheme has just five 'special forms'. Almost all of the resulting power in the language, including the ability to define new Domain Specific Languages, comes from the way these five elements can be combined to create new forms.)

I really think it comes down to thinking about your 'clientele' when you design frameworks or libraries. Remember that this started with someone calling for the final keyword to be deprecated from the Java language. C'mon. Java.

Think about the Java programming culture for a moment. If I were writing a Java library for widespread use, I would consider Rusty's position carefully. After all, most of the people who would lament any restrictiveness have probably bailed and are hacking rails right now. But the remaining Java folks want their IDE and their compiler to catch all of their bugs for them. So if you 'cut against the grain', you provide power nobody wants at the expense of the simplicity they need to be productive in their environment.

But if I were writing a Rails plugin... wait! You couldn't write a Rails plugin if DHH had locked rails down to begin with. Anyways, anything you do in the Ruby world should be far more open. You have a different clientele, with a different culture. It's really that simple.

Of course, there's a trivial argument that all that 'powerful but unrestricted stuff' only works in small teams. That once you have 100+ programmers hacking on something you need more safeguards than a Missile Silo.

All I can say in response is that (1) everything that has ever impressed me in software was done by small teams, not big ones. Just twenty-nine people created the entire Macintosh computer, for example. And (2) given that productivity diminishes sharply with team size, shouldn't we be trying to find ways to make big teams smaller, such as by giving them more powerful tools?

So I think that for a different programming culture, with a different kind of client programmer, you want and need to follow a different design philosophy that emphasizes trusting your client and providing as much power and flexibility as possible.

This isn't a 'bad practice you can get away with in a small team' any more than rear-wheel drive and a manual transmission are bad engineering choices that you can get away with if a driver actually knows how to drive. Or than Scrum is a bad practice you can get away with if your team is gelled and motivated. They are appropriate choices under specific circumstances for a specific clientele that has the requisite skills and attitude. This is my theory.

Conclusion:

So you ask me, is my theory bad? And I reply with a question, for whom?

Labels: java

  ¶ 10:21 AM

  Reg suffering from high-altitude hypoxia? Respected Java and XML Guru Elliotte Rusty Harold has posted a very nice discussion of Eiffel's Design by Contract principles. Along the way, he makes a vicious ad hominem attack, accusing me of architecture astronautics (he actually stooped to using using the word "theorist," which means, someone who blogs when they should be coding). But I digress.



The gist of his post is that since we don't have language-level support for Design By Contract, we ought to use final to accomplish as much invariant enforcement as possible. He suggests that final should be the default choice, that interfaces should be rare and concrete classes plentiful in a design, and that support for polymorphism is less-important than enforcing invariants:

Preconditions, postconditions, and invariants are at the core of data encapsulation. They are the first and most important pillar of object oriented programming. Inheritance and polymorphism are second and third respectively, and are less important.

While controversial, this argument is cogent. I would say it is consistent with a specific kind of design philosophy, one that would be as at home in Ada or Modula as it is in Java. This is in marked opposition to the design philosophy of SmallTalk and Squeak, so I would say it is not very object oriented.

Is that a bad thing? I don't think so. Principles like data encapsulization, modularity, contract enforcement, and componentization are extremely valuable and can be realized in many different ways. For example, what do you think the Erlang programming language or the Linda communication and coördination frameworks are are all about? It's not just concurrency, dude.

The large-scale Java applications I've seen have been particularly devoid of true object orientation, and people seem perfectly happy with that. (Rough metric: the OO-ness of a Java application is congruent to the reciprocal of the number of public static methods in the source code).

So my conclusion is that if you want some advice on writing robust, large scale Java applications in a style that has been proven to be useful over the last several decades, you will find Rusty's post informative.

p.s. My tongue was in my cheek when I composed the title and suggested that one of the most socially conscious Java bloggers in the world was vicious. But you knew that.

p.p.s. If you feel that either Rusty or I can be correct but not both of us, please accept my condolences. How long has it been since imagination passed out of your life?

Labels: java

  ¶ 10:03 AM

  Ready, Aim, Final There're some interesting rants going on about Java's final keyword. And Mike Bowler does a decent job of explaining what final does. As Mike points out, all of the ranting is about whether you should declare classes and methods final.

The arguments against declaring classes and methods final are persuasive. It makes it really hard to unit test anything. You are putting future programmers in a straightjacket (that's actually part of the spirit of bondage and discipline languages like Java, but that doesn't mean it's a good idea). And some refactoring becomes impossible.

When I look at these arguments, I see evidence of a deeper malaise. The problem isn't the final keyword. The problem is the lack of separation between interfaces and implementations.

Take java.lang.String. This class is final, and that is a royal PITA. If you want to extend String to do neat things like keep track of SQL injection safety you are SOL. Now if there was a String interface, and everyone declared their instance variables with the interface instead of the implementation, there would be no problem with a final String class.

Do you need a flag for whether the String is SQL-safe? Use delegation instead of inheritence. No problem. Do you need pluggable storage behaviours for handling special character sets? Use aggregation and a Strategy pattern.

Separating the String interface from the String implementation solves our problems nicely.

I'm 100% ok with the final keyword in implementations. I think it's ok to make a class and say, this is the FizbangImplementationClass. For example, if you were making a sort class for some reason, it would be a little weird to override the actual sort algorithm. If you do, maybe it isn't really a-kind-of FizbangImplementationClass, so it shouldn't extend that base class. It ought to conform to the same interface but be implemented as something else.

At no time in the near future will I be proposing JSR666, "How to fix the Java language so that you can write elegant, object-oriented code." But if I do, my suggestion will be to make every class an interface automatically. (This is not an original idea.)

Here's how it would work. We keep all of the existing syntax exactly as we have it. But the first addition is that you can have class A implement class B. Note that class B is a class, not an interface. This means class A acquires the public members of class B but not their implementations. Now you can 'override' to your heart's content. The final keywords do not affect this, because you are actually implementing an interface.

Is this bad? I don't think so. Framework authors that declare methods final are usually trying to ensure some consistency within a class. If you are implementing the class instead of extending it, you can build it from the ground up. If you need some of the class's behaviour you can use delegation and the orginal class will retain its original behaviour.

The second addition is that when you declare a variable to be of a certain class, you are naturally declaring it to be the interface of the class. So anything declared as a String is actually declared as the String interface, not the String class.

(There are other, subtle changes that are needed. Should String.class refer to the class and String.interface refer to the interface separately? Order plenty of espresso and let the committee thrash this kind of question out).

This could be all accomplished within the current language if everyone was disciplined about declaring interfaces. However, Gosling and Steele set the tone for the Java language when the original libraries contained precious few interfaces and tons of classes. I think it's too late to get everyone to change. So some language change is needed to handle the zillions of lines of existing code.

Or, you could take another approach and eschew languages that deliberately restrict your expressiveness. It's a big world out here, and it would be a shame if you don't get out from behind your desk and travel once in a while :-)

Updates: Elliote Rusty Harold triple-underscored his support for the final keyword, while suggesting that interfaces are mostly bad, and I responded with respect for our differences.

Then Rusty provided some excellent reasons for locking interfaces down in his designs, and I explained why I believe there're legitimate reasons to choose Rusty's approach for some programmers and more flexibility for others.

Labels: java, popular

  ¶ 10:28 AM