This Ain't No Content

I'm always uneasy when I see boolean parameters, particularly in a public method signature.  I think they're a minefield for misunderstanding because they're so information poor.  Really, it's one bit of information, which is good for computers but terrible for people.  Until recently, I've always thought in terms of creating two methods for each boolean parameter.  Sometimes this is good but sometimes not really.

Yesterday, I came across a suggestion in Effective Java (2nd Ed.) that I like: use Java 5 enums instead of booleans. Two advantages

1. the enum values can be made much more readable than true or false
2. the values can be extended if there are more than two scenarios in future

From what I can tell, this site no longer features in the big G's index, which means that my resume and this blog can no longer be found through a search.  There's a sad side to this, because it means that my old posts, that some people did find helpful, can no longer be found.  I don't think this is a big deal because, with the size and variety of the worldwide web, answers to questions can be found elsewhere.  Besides, some of those posts are dated in terms of technology.  I no longer use it and I doubt others do.

The happy side is that I get to write what I want when I want without fearing an audience.  This site may or may not get back into the index.  (I suspect that upgrading the blog software and the associated churn probably caused a few dings, which wouldn't have helped after not adding any new non-content for a couple of years.)  It matters not, one way or the other.  The main thing for me is to get unblocked and not being in the index, I feel I have breathing room.

This time I decided to not use any previous versions as a starting point. Again I made mistakes that ended up causing endless loops on some of the test cases. The previous solution was somewhat in the functional style, using recursion instead of looping. I went further this time and passed array slices rather than indices for good measure.

No doubt in my mind this is the worst implementation so far. It's verbose and hard to understand. It has special case checks. It uses a lot of stack for storing array slices. I particularly dislike the special handling needed for the second recursive call — when the top half of the array is searched, a correction must be applied to the index for the whole array.

I've had one lesson hammered into my skull. When the array slice gets to two elements, size/2 stays at one. Hence, when the value is in the first half of the array, it is vital to search the array up to the item before the midpoint. It's surprising that this is required for correctness as well as in order to avoid unnecessary work.

module BinChopper

    def chop(n,a)
        if a.empty?
            return -1
        end
        if n == a.midpoint_value
            return a.midpoint
        end
        if a.size == 1
            return -1
        elsif n < a.midpoint_value
            return chop(n, a[0 .. a.midpoint - 1])
        elsif n > a.midpoint_value
            return apply_correction(a.midpoint,
                        chop(n, a[a.midpoint + 1 .. a.size - 1]))
        end
    end

    def apply_correction(mid, target)
        if target < 0
            return target
        else
            return 1 + mid + target
        end
    end

end

class Array

    def midpoint
        return size / 2
    end

    def midpoint_value
        return self[midpoint]
    end

end

Doing it recursively is a simple re-write. The while changes to an if and the asignments of hi and lo turn into recursive calls. In a language with tail call removal, this would not be any worse than the iterative version. I don't think Ruby is one of those languages. However, I do think this version is a bit easier to read than the first one.

module BinChopper

    def chop(n, a)
        return recursive_chop(n, a, a.length - 1, 0)
    end

    def recursive_chop(n, a, hi, lo)
        if lo > hi
            return -1
        end
        mid = (lo + hi) / 2
        if a[mid] == n
            return mid
        elsif (a[mid] > n)
            return recursive_chop(n, a, mid - 1, lo)
        else
            # a[mid] must be less than n
            return recursive_chop(n, a, hi, mid + 1)
        end
    end

end

Now that I have a laptop from work I don't need to exile myself the spare bedroom in order to try things out on the computer. Thanks to wi-fi I have ruby and vim, which means I can look at kata again.

Actually, I wanted to try out binary chop, as it's something I can use on a work project. Stupidly, I tried first to write the code cold. That didn't work. Not only did I have the fencepost errors and the endless loops — the code was getting uglier as I kept thinking of special cases. It probably didn't help that my Ruby is rusty from lack of use. I've been spoiled by IDEs and auto-completion: one almost forgets what it's like to get compile errors.

So I resorted to pen and paper. A funny thing happened: all Dave's tests passed at once. The code was easier to read and more coherent. Binary chop is about the simplest problem I know for which it's really worth taking a break from the keyboard.

Interesting to compare with other people's work. Jim Weirich did a version three years ago. Here's mine:

module BinChopper

    def chop(n, a)
        lo = 0
        hi = a.length - 1
        while lo <= hi
            mid = (lo + hi) / 2
            if a[mid] == n
                return mid
            elsif (a[mid] > n)
                hi = mid - 1
            elsif (a[mid] < n)
                lo = mid + 1
            end
        end
        return -1
    end

end

Originally, I was using single letter variable names but I like Jim's short but meaningful names better. I thought of the invariant a little differently: I decided the loop would terminate after the high and low markers went past each other. (By the way I think his calculation of the midpoint is buggy. I should lay off the crack pipe. His calculation is obviously correct and I'm stealing it.)

Now of course coming up with one implementation of binary chop is straightforward. I'll have to see how motivated I am to find four more ways to do it.

Big personal news this weekend. It was the first anniversary of my marriage and I got a green card as a present.

This year, after a break of one year, I went to the No Fluff, Just Stuff conference. Having spent nearly a month and a half during the summer reading up on work material while job hunting, it was harder this time to find good sessions. APIs and frameworks are boring unless they're very new or very different. I already know enough about Ruby and Rails that I don't want to attend an introductory session on either. Too bad, because Dave Thomas is an entertaining speaker.

The talk that that left me thinking was about Seaside, a web framework written in Smalltalk. I'd heard a bit about it, but not enough. Glenn Vanderburg tends to delve a little more into the hard stuff than most speakers. Novelty and technical depth is just the kind of thing I'm looking for these days.

I'm reading Joshua Bloch's Effective Java and getting quite a lot of it. The book is a catalogue of numbered items of advice, some standard, some controversial, with fairly detailed exposition on each.

Item 14: Favor composition over inheritance is uncontroversial, being a restatement of the second principle of object-oriented design in Design Patterns, the famous Gang of Four book by Gamma and company. However, in his discussion, Bloch writes that

Sometimes the combination of composition and forwarding is erroneously known as delegation. Technically, it's not delegation unless the wrapper object passes itself to the wrapped object [Gamma95, p. 20].

I think Bloch misread page 20 and, thanks to the reference, I was able look at page 20 over his shoulder:

Delegation is a way of making composition as powerful for reuse as inheritance [...] [W]ith inheritance, an inherited operation can always refer to the receiving object through the this member in C++ [...]. To achieve the same effect with delegation, the receiver passes itself to the delegate to let the delegated operation refer to the receiver.

This text is suggestive, however the example that follows makes no attempt to achieve the this effect. In the example, Window object delegates an Area() operation to a Rectangle object. The Window object does not pass itself to the Rectangle.

In the Glossary of the GoF book, on page 360, there is another definition of delegation: An implementation mechanism in which an object forwards or delegates a request to another object. The delegate carries out the request on behalf of the original object. I haven't edited anything out this time.

I think Bloch took something optional and made it an essential part of the definition of delegation. The paragraph I quoted from the GoF is a little ambiguous, but the rest of the book seems clear: it is still delegation even if the delegating object does not pass itself as part of the request to its delegate.

To be sure, this is a detail of no importance. The definition of delegation doesn't really depend on the GoF. My quibble hardly affects my opinion of Effective Java: it's still a book I'm glad I bought. It's just a case where the reference doesn't give support to the author the way it appears to.

I've been unemployed for most of July and will be for most of August.

During the last few weeks, job hunting has taken priority over blogging. The first opportunity I found out about, on July 11th, was the one that turned into an offer, on August 5th. I start at the new job on the 22nd.

At my previous job, I was a lone developer. Therefore, I took an approach to professional development that involved a lot of reading. Becoming self employed without an income, I took up reading as more or less a full time day job. I did update my resume and hit the job boards, but not as my primary activity. I wanted to pace myself and not set up too many contacts with possible employers at once.

I was surprised to find that a lot of the tech bubble infrastructure is still in place. There are headhunters who search for people they can pass on to employers for a fee. Some headhunters are conscientious, others spam with abandon. In one case, I got an urgent e-mail and voice mail from someone looking for a fluent Japanese speaker. The word "Japanese" did occur in my resume, but I never pretended to speak the language.

I was lucky. I didn't find the employer; a headhunter found me and figured out I was suitable for the position. I didn't answer every question perfectly in the interviews, but I got better as I progressed. This employer was more technically focussed than most; it paid off to read up on the details of Java, threads and RMI (among other things).

I have nearly two more weeks of leisure. I'll keep up with the reading, but I'll also have time to take care of chores and errands. If the earning member of the household could get time off, we'd probably go somewhere. But there's no need to go anywhere for warm, sunny weather. I'll try to enjoy the relaxed pace of summer while I still can.

Laurent has some thoughts on the value of duplication. They are laudably contrarian.

However, I can't quite bring myself to think duplication is often a good thing. Certainly, for a manager who needs to get a quick assessment of whether a given chunk of code is good enough, it can be expedient to compare it to another chunk that is known to be good.

This approach of looking for duplication will work if the aim is very short term. Humans are good at pattern recognition. We can assume that there are other practices in place to make sure the code works properly (testing for one). If it looks okay and works okay, it probably is okay.

I see a couple of problems here.

For one, why is a manager having to judge whether a given chunk is okay? I know that every manager who has been in the trenches is tempted to go back, even if only vicariously. However, the best people to judge code are programmers who work in the same area. And nobody likes to look bad in front of their peers.

For another, it only applies if the two code chunks really should look alike. Sometimes that will be true: if we are employed it is often because we have experience solving the same type of problem. But new code jury-rigged to fit into a template of the old code, that might be a positively bad thing. Looking at it would not be enough to tell if that was the case.

It's often good to be able to refer to primary sources. I came across one such reference this morning for the Law of Demeter

For all classes C, and for all methods M attached to C, all objects to which M sends a message must be

• M’s argument objects, including the self object or
• The instance variable objects of C.

(Objects. created by M, or by functions or methods which M calls, and objects in global variables are considered as arguments of M.)

That's an OOPSLA paper from 1988, with references going back further, notably to work by Parnas on decomposition into modules.

The Law of Demeter, when used in coordination with three key constraints, enforces good programming style. These constraints require minimizing code duplication, minimizing the number of arguments passed to methods and minimizing the number of methods per class.