Work smarter

From Some AI Koans (attributed to Danny Hillis):

A novice was trying to fix a broken Lisp machine by turning the power off and on.

Knight, seeing what the student was doing, spoke sternly: “You cannot fix a machine by just power-cycling it with no understanding of what is going wrong.”

Knight turned the machine off and on.

The machine worked.

Today’s lesson: Cargo Cult Programming is no substitute for sitting down and figuring out what’s going wrong.

Also, threads are tricky.

And more on Dan’s question

Also from Mr. Lippert’s immutability discussion (specifically the comments to post #4, “An Immutable Queue“): we have a Carnegie Mellon dissertation — I’m telling you, those CM guys are, collectively, The Man — on Purely Functional Data Structures (PDF) from one Chris Okasaki (now a professor at West Point, apparently), the book version thereof, and for those of shorter attention span some Power Point slides on the same topic from one Benjamin Pierce at the University of Pennsylvania. Go nuts, Dan!

Thinking a little harder about Item 13

Eric Lippert has another post up in his immutability series, this one about using immutable binary trees to represent immutable maps. (“Map” = “hash” or “dictionary”, for you perl and python folks. I understand that the technical term is “associative array.”)

I skimmed the post, said to myself “that makes sense,” then went back and stared at the code samples for a bit and said “wait a minute….” Because the map interface has methods like Add() and Remove(), and so does the tree interface. What’s immutable about that?

I was halfway through writing a comment asking Mr. Lippert what the hell was going on, when I figured it out. Yes, you can call Add() and Remove(), but those methods don’t actually modify the map (or the tree) you call them on. Instead — this is what I saw, when I looked closely — they return a new map (or tree), identical to the original apart from whatever was added or removed. Instead of mutators that change the internal state of an object, you have something much closer to a mathematical function, describing a relationship but never altering any values.

Anyway, it turns out that if I’d actually read all of Mr. Lippert’s other posts, he explains all this, specifically in post #2 of the series, “A Simple Immutable Stack.” He goes on to demonstrate how, contra most people’s first instincts including mine, immutable data structures of this kind can actually use less memory than the traditional mutable kind, because, being as all the pieces they’re built up out of are also immutable, they can safely share as much of their internal state as they have in common.

It strikes me that something like this is probably the answer to Dan‘s question about representing mutable state in functional languages. Functional expressions may not be able to modify anything, but they can always produce new results.

(The “Item 13” in the title is from Effective Java: Item 13: Favor Immutability. Since it’s the Bible, we might as well cite chapter and verse — as long as the numbers haven’t changed in the second edition.)

Comments closed due to spam.

New directions in parallelism

(Attention conservation notice: The two most important things I link to here can also be found in Neal Gafter’s recent “Is the Java Language Dying?” post, which you might well find more interesting anyway.)

Parallelization and multithreading were topics that kept coming up at JavaPolis — largely for the pragmatic reason that, as James Gosling pointed out, while Moore’s Law is still going strong, chipmakers seem to be running out of ways to turn more transistors into higher clock rates, and instead are using those transistors to pack on more cores. Most any desktop or laptop you buy this year is going to be dual-core, and servers are looking at four to eight. Of course, you can get pretty good value out of two cores just by websurfing in the foreground and compiling in the background, but a quick back of the envelope, double-every-eighteen-months calculation gets you hundred-core consumer machines by 2017. What then?

A hundred cores might sound silly; but I expect the idea of a PS3 with eight specialized cores running at 3.2 GHz would have sounded silly when the first 33-Mhz PlayStation shipped, too. Say it’s only fifty, though. Say it’s twenty. Say it’s ten. Most developers wouldn’t have a clue how to use ten cores efficiently, let alone a hundred. As a Swing developer, I generally feel pretty pleased with myself if I can keep track of more than just “the event dispatch thread” and “everything else.” We’re all going to have to get a lot better at multithreading if we want to make good use of next year’s hardware.

Gosling was pretty pessimistic. He called massive concurrency

The scariest problem out there… Thirty years of people doing PhD theses on parallel programming, and mostly what they’ve done is hit their heads against brick walls.

Well, there’s brick walls and brick walls. Luckily (I know I was complaining about not having a PhD from Carnegie Mellon earlier, but for purposes of this discussion, we’ll say “luckily”) I’m not doing a PhD thesis, so I can hope for other, harder heads to knock these particular walls down for me. And, as it happens — now we get to the point of this post, if you made it this far — harder heads than mine are working on it:

Doug “concurrency” Lea’s Fork/join framework:
A lightweight system for parallelizing tasks that can easily be divided into smaller subtasks. (PDF here, javadoc here. The code’s available as part of Lea’s <a href="util.concurrent package, though you’ll probably want to grab just the source for those classes since a lot of the rest of the package — Closures and whatnot — is now superseded by standard libraries.) This came up a lot in JavaPolis, mostly in the context of the closures argument, what sort of language features would make this kind of framework easier to use, whether we should all just be programming in Scala, and so on. It should be standard in Java 7.
Haller and Odersky’s Actors model (PDF):
A single abstraction that “unifies threads and events”. (Apparently this was popularized by Erlang.) If I get this right, actors are worker objects that encapsulate a thread, and can receive and react to arbitrary messages either synchronously (event-style) or asynchronously (thread-style). I haven’t dug too far into this paper. Haller’s got an actors tutorial that may be more accessible. Of course, it’s all in Scala, and the fact that it’s not that easy (perhaps not even possible?) to do in straight Java is one of the motivations behind BGGA closures. There’s also a long Wikipedia article on the general concept.

I keep stretching for some sort of pun involving threads, Lobachevsky’s parallel postulate, and Tom Lehrer’s well-known assertion that Lobachevsky was the greatest mathematician “who ever got chalk on his coat.” (MP3 here.) Lucky for you I’m not reaching it.

Running short of excuses

I’ve been saying (to myself, anyway) for several years that the main thing stopping me from learning Objective-C and NeXTStep Cocoa programming — that is to say, contemporary Mac programming — was my addiction to the refactoring support I get from Java tools like IDEA and Eclipse. Meanwhile, it’s hasn’t been hard to find Obj-C programmers dismissing any demand for automated refactoring tools as lazy whinging from weak-minded Java monkeys.

But, lo and behold, Apple’s gone and added refactoring support in Xcode 3. It’s fairly limited (where’s my Safe Delete??) so far, but it does include Fowler’s “refactoring Rubicon,” Extract Method. In fact, it extends it to “Extract Function” as well, since Obj-C supports top-level functions. (So Xcode 4 ought to have all kinds of crazy refactorings.)

So, “no refactoring tools” clearly can’t be my excuse any more for not learning Obj-C / Cocoa. Gotta think of something else. “After I learn Flex,” maybe?