Category Archives: Software Development

20 Days of Clojure: Day 3

Ok, so first we made a very hard-coded sqrt, then we improved it by adding the concept of fixed points, which made the algorithm easier to see in the code. Here’s how we can improve it even further. Go to 32:30 in this video (stop at the break at 43:00):

First we define an average-damp function. This function takes a function as its argument and returns another function which takes a number and returns the average of that number and result of calling the function argument on the number. It’s easier to say that in clojure:

    (defn average-damp [f]
        (fn [x] (average x (f x))))

f is a function, average-damp creates a new function that takes x (a number) and that new function averages x and f(x).

Now that I have that, I define sqrt like this (you can find average and fixed-point in yesterday’s post):

    (defn sqrt [x] (fixed-point (average-damp (fn [y] (/ x y))) 1))

Tomorrow, we’ll use this to implement another way of finding sqrt.

20 Days of Clojure: Day 2

Yesterday, we built a simple sqrt using Heron of Alexandria’s algorithm. The problem with the code is that it had some generically useful ideas, but it was all hard-coded to only work with sqrt. Also, it was not clear what exactly the algorithm was.

In the SICP lecture they fix it by passing functions around since Lisp treats functions as first-class data-types. Here’s the fix explained (23:30 in the video, stop at 32:30):

See the video for the Scheme implementation. Here it is in clojure.

    (defn sum ([] 0)
        ([x] x)
        ([x & more] (+ x (apply sum more) )))

    (defn average
        ([] 0)
        ([x] x)
        ([x & more]
            (/ (+ x (apply sum more)) (+ 1 (count more)))))

    (defn abs [x] (if (< x 0) (- x) x))     (defn close-enough? [u v]
        (let [tolerance 0.00001]
            (< (abs (- u v)) tolerance)))     (defn fixed-point [f start]
        (loop [old start new (f start)]
            (if (close-enough? old new)
                new
                (recur new (f new)))))

    (defn sqrt [x] (fixed-point (fn [y] (average (/ x y) y)) 1 ))

    (prn (sqrt 9))

A fixed point of a function f is a value y such that f(y) = y. This improved code, which implements the same algorithm as before, uses a generic fixed-point function that takes a function and a guess and tries to find the fixed point by setting the next guess to f(guess). You can see it all in the video. The things in clojure you need to know:

  1. fn [arg1 arg2] is lambda (λ), so where fixed-point takes a function as the first argument, we create one on the fly to be (average (/ x y) y) where x is the argument to sqrt (closed around our function) and y is the argument defined by fn.
  2. Since clojure compiles to Java and uses Java calling conventions, it does not have automatic tail-recursion. Instead, you use the recur special operator which will create a constant space loop back to the last loop or function definition. Loop/recur is explained on the Functional Programming page of the clojure site (at the bottom).

But, even this can be improved, as we’ll see tomorrow.

20 Days of Clojure: Day 1

Ok, this might be hard to keep up, but nothing ventured …

Rich Hickey is going to be coming to Northampton on March 20th to talk about clojure. In preparation for that, I am going to blog every day in March about clojure — then, hopefully we can post the results of his talk.

If you don’t have clojure yet — go get it. Start here to learn basic clojure syntax (there is also a download link). Clojure is trivial to get running and you definitely want to play with it a little to understand the rest of this. The quick description of clojure is that it’s a dialect of Lisp that runs on the JVM. It has support for immutable and persistent data-structures and a concurrent programming model.

Today I’m going to start with some of the work I did to learn clojure through translating SICP lectures. In the first lecture, the first interesting program starts at 56:20 in this video:

Starting there presumes you know some basic Lisp syntax. This is the program he eventually writes to calculate the square root (in Scheme):

    (define (improve guess x)
        (average guess (/ x guess)))

    (define (good-enough? guess x)
        (< (abs (- (square guess) x)) .001))

    (define (try guess x)
        (if (good-enough? guess x)
            guess
            (try (improve guess x) x)))

    (define (sqrt x) (try 1 x))

I have left out implementations for square and average here. This code and the algorithm is explained in the video. Here it is in clojure (I defined average and square — you could just use Java, but I am trying to keep it all in clojure for now)

    (defn sum ([] 0)
        ([x] x)
        ([x & more] (+ x (apply sum more) )))

    (defn average
        ([] 0)
        ([x] x)
        ([x & more]
            (/ (+ x (apply sum more)) (+ 1 (count more)))))

    (defn abs [x] (if (< x 0) (- x) x))     (defn square [x] (* x x))

    (defn improve [guess x]
        (average guess (/ x guess)))

    (defn good-enough? [guess x]
        (< (abs (- (square guess) x)) 0.001))     (defn try-sqrt [guess x]
        (if (good-enough? guess x)
            guess
            (try-sqrt (improve guess x) x)))

    (defn sqrt [x] (try-sqrt 1 x))

    (prn (sqrt 9))

If you take this and put it in a file named sqrt.clj, you can run it like this (after downloading clojure):

    java -cp clojure.jar clojure.lang.Script sqrt.clj

And it will print out:

    65537/21845

Explanation of the differences between the two examples:

  1. clojure uses defn to define functions and puts arguments in []
  2. sum and average implementations show how clojure can overload on arity (number of arguments)
  3. try is reserved for exception handling, so I renamed the try function to try-sqrt
  4. the answer is in clojure’s rational number format, since all of the computation was adding and averaging integers and rationals, the result is a rational number and clojure preserves that.

Tomorrow, I’ll improve this so to make it more generic. A lot of what I used in this can is explained in the clojure Functional Programming support page.

Book Review: Collective Intelligence: Part I

51AnWLR89xL._AA240_

I’m at about the halfway point in Programming Collective Intelligence by Toby Segaran, and even if the second half was blank, I’d be telling everyone to read this book. It’s been a while since I’ve read a technical book this good. It excels because of a combination of three factors:

  1. Useful algorithms
  2. Shown in real-life situations
  3. With real data that you can get yourself

The basic idea of the book is to show different ways of using user-generated datasets to extract information and make decisions. Each chapter tackles a different problem and shows a few ways to approach it. All of the examples are in Python, but even if you don’t know Python, you should be fine if you know any structured language. Practically every example either uses some dataset that he tells you how to get, or a public API that is free to access.

This book is the first I’ve read that relies on the current maturity level of the web. A few years ago, it wouldn’t have been possible to provide so many relevant examples. In a few years, the API’s might be out-of-date — but don’t let that stop you — the algorithms are timeless.

The choice of Python is a good one for a few reasons. Firstly, it’s pretty clear to read even if you don’t know it. Secondly, list-comprehensions are a pretty good way to think about data crunching (which these algorithms do a lot), and, finally, there are many freely available Python libraries to deal with the public APIs he uses.

To give you an idea of Toby’s approach, I’m going to run through my favorite chapter so far, the one on Optimization. The quick description of the problem domain should be familiar to every programmer — solve NP complete problems like the traveling salesperson. Basically, Optimization techniques can be used in situations where (1) you can’t analytically solve the problem (2) the solution set is too large to exhaustively search (3) you can express the cost of a possible solution such that better solutions have a lower cost than worse ones and (4) solutions that are “near” each other have similar values for cost.

Toby’s first example is how a family can choose flights so that they arrive at the same airport from all over the country at nearly the same time and depart for home a few days later at nearly the same time. The cost function is a combination of the actual costs of the tickets and the difference in time between the earliest and latest flights. He goes on to provide a dataset of flights, describes setting up optimization problems in general, and shows the python code to implement the cost function.

Then he introduces a few optimization algorithms, implements them, and discusses their relative strengths and weaknesses. The next section applies these techniques to real data on Kayak.com using the standard Python DOM parser, minidom. The final section shows how to apply these techniques to other problems like pairing students in a dorm and network visualization. Other chapters get a similarly exhaustive treatment.

I really hope that this is the future of technical books.

Scrum at Atalasoft: Burndown charts from FogBugz

Earlier this year we adopted Scrum to manage our releases. Our internship program used it for their project, and then the rest of the development team started adopting some practices — we found it useful enough that we decided to run the 5.0 release as a Scrum project.

I am acting as the Scrum Master, which means that among other things, that I am responsible for generating the burndown chart. Although we have adopted Visual Studio Team System for source control, we are still using FogBugz for bugtracking, so we don’t get the automatic Scrum tools in VSTS. With a little work, I was able to generate what I need. FogCreek publishes the FogBugz schema, so it’s pretty easy to get the data you need. Since they don’t really store historical estimates and elapsed time, you have to get each date’s datapoint for the chart on the actual date, you can’t get previous days (They do store it in comments, but I decided it was not worth parsing the data, since I have to generate the chart every morning anyway).

This query can get the list of open cases for a person and release:

SELECT
  hrsOrigEst,hrsCurrEst,hrsElapsed,
 ixBug,sTitle,sstatus 
FROM bug,person,fixfor,status
WHERE
  bug.ixPersonAssignedTo = person.ixPerson 
  and person.sFullName=? 
  and bug.ixFixFor=fixfor.ixFixFor 
  and bug.ixStatus=status.ixstatus
  and FixFor.sFixFor=?

For burndown charts, you are interested in the total difference between hrsElapsed and hrsCurrEst for active cases. I also track the total hrsCurrEst to see if we’re reestimating cases or if new cases are being added to the sprint.

Even though I don’t parse the automatic comments (BugEvents) for the estimated and elapsed time, I do want to eyeball them (to track down anomalies).&nbsp; Here is the SQL for that.

SELECT dt, cast(sChanges as varchar(8000)) as changes
FROM bug,bugevent
WHERE
     bug.ixBug = bugevent.ixBug and bug.ixBug=?
ORDER BY dt desc

I probably wouldn’t need to do this if FogBugz would just do sub-totals of Estimates and Elapsed time on their filters (when I group by Owner), but it’s not so bad.

I take this data and copy to Excel and use linear regression on the data to get an idea of how we’re doing on getting the sprint done in time. I generate the chart, and put a copy in our internal wiki, so everyone in the company can see our progress.

In this article, Joel says: “In FogBugz 6 there’s one place where we need to do literally millions of calculations to display a single chart on a single web page” — I’m hoping that that means some kind of release trend chart.

API UI

I saw this article on Reddit that applies principles from human-factors design to API design. I think that’s a great idea, but this suggestion sounds weird to me.

Now we could use progressive disclosure to help reduce the complexity of that JButton class: put the expert stuff in an object returned by a getExpertKnobs() method, and the graphics subsystem hooks in an object returned by a getIntegrationHooks() method, and you would be left with a button API that had just a handful of methods—the basic methods we all need.

This brings the number of methods in a button from about 100 to about 10, which sounds great until you try to subclass. Overriding a method that’s in the object returned by the getExpertKnobs method would be a little tricky. It’s likely that you don’t even know the real class of that object because those methods are likely to return references to interfaces, plus the component code is in charge of constructing the objects, so there would have to be a way plug into that too, so that your subclass is constructed. I agree that the interface would be much simpler for most users, but it is much more complex for subclassers.

There’s also the issue of what would be in the expertKnobs object. Some of the methods in JButton that would go in there actually come from JComponent or Component. In fact, as we progressively go down the class hierarchy, we are adding methods into the class that might belong together, which means that there is probably an expertKnobs class for each component class.  But, the getExpertKnobs() method is probably introduced early in the hierarchy — what does it return? Will I have to downcast to get to the button’s expert knobs?

I don’t have a solution — but these issues probably drove the design of JButton more than the idea that they just sloppily added a 100 methods without giving a thought to the complexity of the class.

But the point is taken, and I like the idea of using hard won knowledge from other domains in software design. 

Another recent blog on this topic was Steve Hawley’s Principle of Least Astonishment  essay — the last topic, on layering APIs, has his approach to this problem.

WinFX Generation

Been looking around WinFX and specifically XAML recently. Not sure I think writing XML is a great way to write a GUI (but billions of web pages clearly prove me wrong). My first impression is that one of the benefits is going to be automated creation of XAML — not from tools, but from our own programs.

It’s been 10 years since HTML was a household word and I still feel like it’s easier to hand write it than use a WYSIWYG tool. I also never really liked using dialog editors. Even good ones like Delphi have too many limitations, especially when it comes to layout. So, I’m not expecting much from the tool support for XAML. But since it’s just a text format, it should be pretty easy to generate from a simpler format (or from models). I’m looking forward to playing around with that idea.

Presentation Links

Here are some links I’ve collected on giving presentations. I have been revisiting them lately in preparation for my talk next month.

Apple XCode CPlusTest Port

C++ (and Cocoa) unit testing is built into XCode on OSX. I am writing an application right now that I plan to port to Windows. When I wanted to see how portable my code was, I decided to get all of the unit tests passed on Windows.

Unfortunately, XCode does not use CppUnit, which is already portable. Here is some code I wrote that you can use to run your XCode generated unit tests on Windows.