Ever since SudokuBan (bit rot guilt guilt), a sudoku solver has sort of been my one-step-beyond-”Hello world” program for new languages. Although Java isn’t exactly a new language for me, the re-familiarising process is more or less the same; so I kicked off a sudoku solver in Java. And just a few minutes ago I sort of got it trivially working.

By “sort of” and “trivially” I mean that I’ve tested its ability to solve an empty grid. That is, given an empty 3×3 (or more correctly 9×9) sudoku grid, it can fill it with numbers that would be a valid solution. It doesn’t do randomness yet, so the solution it finds is by some definition the “first” valid sudoku (adding randomness is the first step to generating new puzzles). In principle it should be able to solve existing puzzles, but I haven’t tried it yet. In fact I don’t think the class has enough exposed to be able to fill in the puzzle’s starting cells. Hmm.

The Mercurial repository is public if anyone would like to follow along, or copy my copious mistakes.

Incidentally, the “first” sudoku looks like this:

+---+---+---+
|123|456|789|
|456|789|123|
|789|123|456|
+---+---+---+
|231|674|895|
|875|912|364|
|694|538|217|
+---+---+---+
|317|265|948|
|542|897|631|
|968|341|572|
+---+---+---+

Here’s my ten-word review of Joshua Bloch’s Effective Java: If You Write Java, You Need To Read This Book.

I wanted to say that up front, because I’m about to talk at great length about one of its shortcomings, which would give the impression, purely by wordcount, that I don’t think it’s a good book. This is just a reflection of how many more words it takes to explain a negative point than a positive one. The book is irrefutably useful and you should read it (if you write Java).

To give the issue a bit of context, here’s a fact that I was only dimly aware of before doing some mid-reading research:

If you get the security settings right, the Java Virtual Machine guarantees access control.

If you declare a field private, and you’re running a trusted JVM, and the security manager is set to disallow JNI and changing accessibility through reflection and a handful of other things, then you can run untrusted third-party code in the same process and even pass those objects to the untrusted code and it will never be able to get at the private field.

This is such a big deal that I don’t understand why it isn’t a bigger deal. It’d be impossible to make this kind of claim in a natively compiled language, because you can always pointer-arithmetic your way to the private data. Python makes only the vaguest of gestures in the direction of information hiding, and certainly doesn’t guarantee it. Maybe C# and the rest of the .NET family make some guarantees, I’m not sure (although whether you’d trust Microsoft to get the security right is a different story (but then, the same question should be asked of Sun Oracle)).

Here’s the issue though. This means that access control in Java actually has two different (although overlapping) purposes: encapsulation, and security. And they’re not the same thing.

Encapsulation is about reducing the complexity and increasing the abstraction of classes by hiding their implementation. Security is about stopping people from seeing or changing data that they shouldn’t be able to. Security is for protecting users from malicious programmers; encapsulation is for protecting programmers from themselves.

Security at this level isn’t always possible. If you’re writing a library for other people to use in a JVM that they control, you can’t expect to hide anything from them – they can turn the security manager way down, or change your bytecode, or run a modified JVM. (At university we had an assignment that involved black-box testing of algorithms that we were given as obfuscated JARs. I worked out that you could peek at some of the internals by rebuilding the Java standard libraries with String declared non-final, and passing in a subclass with some instrumentation added. And no, I didn’t actually do it.)

Most times that someone compromises their own system, they can only do damage to themselves. Of course, you probably still want to make your library as tight as possible so that it isn’t a security hole for other code that it interacts with. The point is that it can be dangerous, or at least an unnecessary programming burden, to rely on language guarantees for security if you’re not always going to have control of the platform.

On the other side, encapsulation isn’t always desirable. Well, maybe it is. There’s heated debate about this. Some people (many of them Java devotees) argue that programmers will find and use every available undocumented feature, and anything you inadvertently expose will doom you to support it forever. Others (e.g. a high proportion of Python fans) say that an API is as much a social contract as a technical one, and that if someone wants to work around an interface that doesn’t meet their needs then, well, we’re all adults, and they’re welcome to do so as long as they accept the consequences if the implementation changes.

The point is that encapsulation and security are different requirements. Making a field private because it’s an implementation detail is one decision; making a field private because using it would open a security hole is a very different decision. If you try to squeeze the concepts into one then at some point you’re going to make a poor decision. And now we get to my one (and minor) gripe with Effective Java: it doesn’t do enough to distinguish between them.

Some of Bloch’s points (e.g. Item 10: Always override toString) are clearly about programmer-friendly abstractions. Other points (Item 76: Write readObject methods defensively) are clearly about security – no programmer would (or could, reliably) exploit it just to get around API restrictions. In one place (Item 39: Make defensive copies when needed) he mentions that a particular security measure has a big enough performance hit that it can be valid to leave it open, if it’s in an environment where misuse will only hurt the (mis)user. But in other places it’s not so clear exactly what kind of advice he’s giving, which could lead readers to apply the advice in the wrong way.

Part of this might be that Bloch is writing from the perspective of someone who worked on the Java platform APIs, which sit in the part of the Venn diagram where encapsulation and security do overlap: they’re widely used, so any leaky implementation details are guaranteed to become a compatibility issue; and they’re the basis for every other API (even a trivial class extends Object) and available to malicious code even on a trusted JVM, which effectively makes them part of the platform’s security guarantee. And I suppose you could argue (indeed, he says something similar to this in the introduction) that you don’t always know where your code will end up, so aiming for as much encapsulecurity as possible isn’t a bad thing.

And frankly that’s a pretty good argument. Which is why you still need to read this book.

(A few other things bugged me while reading it, but most of them were directed at Java rather than the book itself. There might still be another post or two in this topic.)

This morning I told someone I’d find a document and send it to them by tomorrow. Tonight I got around to looking for it.

First hurdle: it’s not on my laptop. Okay, not a problem; it’s a few years since I last saw it, so it’s probably on my… old laptop. The hard drive of which I wiped and put in a housing to use as portable storage.

Not to worry, before I wiped that drive I copied its contents to… the server that I’m not using anymore because I replaced it with a fit-PC2. (Did I mention? I got a fit-PC2. It’s awesome. Barely ever goes above 10W.)

But that’s okay, because I copied the contents of the old server to the new one. Except a few things that I didn’t copy because the hard drive is smaller in the new one, which wasn’t a problem at the time because I was going to start a new backup system involving removable drives. Which I haven’t gotten around to yet. But I would have remembered to copy this, because it’s important, and not very big, and…

Oh.

Never mind, the old server is still here, I’ll just crawl around under the desk, shuffle a few plugs around, and start it up.

Huh. Doesn’t want to power up. Maybe I unplugged it to make room in the power board.

Nope, plugged in. Maybe there’s something up with the power cord.

And also with this spare power cord.

So I’ve now resorted to transplanting the drive into another box (not the first time this particular drive has had this treatment) so that I can boot a server that I’ve replaced to get a file that I’ve copied several times but not to anywhere that I could immediately get at it, all so that… well okay I really did need that file, but boy did it make me work for it.

This weekend I’m setting up a backup system.

No, seriously. I will.

Maybe.

Am I the only one who didn’t know about this?

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

int main(int argc, char **argv)
{
    printf("%d\n", abs(INT_MIN));
    return 0;
}

Which gives:

davemc@zaphod:~/devel$ gcc -o abstest abstest.c
davemc@zaphod:~/devel$ ./abstest
-2147483648

The abs function, in C, is undefined if you call it with INT_MIN (because a two’s-compliment 32-bit int can be -2³¹ but not +2³¹). In Java, it’s specified to return Integer.MIN_VALUE.

I feel slightly betrayed that abs can return a negative number. Actually, I feel more betrayed that this isn’t a classic drummed-into-our-heads-in-every-programming-guide-and-uni-course-ever gotcha.

In other news: Google doesn’t do what you expect if you search for “man abs”.

https://www.microsoft.com/protect/fraud/passwords/checker.aspx

DreamHost migrated me to a 64-bit server about a week ago, which broke the Mercurial build I was using to host some repositories. Just got it up and running again (and upgraded to 1.6.4 along the way), and now that it looks like I’m actually keeping some momentum with this blog, I’ve added a link to the repositories in the sidebar.

Now that I look at it… wow, there’s some old, crufty, ugly stuff there.

Well, anyway, now there’s a link.

Emacs is on my long list of things that I love in theory, but in practice have only the most tenuous of grips on. (See also: Go, wine tasting, Fourier analysis. Also, I know I ended a sentence with a preposition. Suck it up.)

So – and I say this with all love and in spite of my new year’s resolution – Eclipse with Counterclockwise? So much easier to use than Emacs with SLIME. Almost certainly less powerful, but for the purposes of learning a language, I do not care.

Last time I worked with Java was before my Lisp days (or at least various attempts to get into Lisp), so I’m looking at it again now with a different context. So when I came across this use of an anonymous class in Effective Java (comments removed for brevity – bad practice shut up shut up):

static List<Integer> intArrayAsList(final int[] a) {
    if (a == null)
        throw new NullPointerException();

    return new AbstractList<Integer>() {
        public Integer get(int i) {
            return a[i];
        }

        @Override public Integer set(int i, Integer val) {
            int oldVal = a[i];
            a[i] = val;
            return oldVal;
        }

        public int size() {
            return a.length;
        }
    };
}

…my first thought was “waaaitaminute… Java has closures?”

Now, it took a while for my memory of these things to come back, and a bit of searching to fill in the gaps… it turns out Java doesn’t quite do closures (it doesn’t work with non-final variables because it actually copies them behind the scenes), and at any rate there’s still the whole anonymous class mess instead of first-class functions (which I’ve always found annoying).

Then, it turns out that there’s a proposal to get first-class functions and lambda expressions in Java. And not from some random functional programming fanboy, but taken seriously by Sun and at one point planned for inclusion in Java 7 (it’s now deferred to Java 8).

All of this makes me wonder though… How does Clojure implement closures? Does it have some roundabout way of doing it that could mess up performance in opaque ways? Or is the JVM really that much more flexible than the Java language lets on? Or is Clojure a completely degenerate Lisp dialect?

Apparently I’ve got more reading to do.

We don’t always talk about who comes up with what behind the scenes for Darths & Droids – and in fact I haven’t been as involved in writing lately anyway – but I do feel the need to claim credit accept blame for the atrocious pun in strip 475. (Click here to ruin the joke.)

According to our wiki, I suggested it on March 11, 2008. So the guys have had over 2½ years to veto it. I consider that a failure on their part.

Here, have some Perlin noise.

Drag to rotate and change the rate of bubblyness.

This is just some random stuff that I’ve been messing with to get back into the swing (pun intended?) of Java. The code is embarrassingly ugly so I’m not going to put it up it in its current state.

(Note: Java 6 update 21 doesn’t play nicely with something in a non-obvious way.)

(Note 2: In fact it seems to be not working on a wide variety of machines. There could be multiple issues here. Hmm.)

(Note 3: Possibly it just needs a newer version of Java than I’m using at work. I’m starting to re-discover my old impression that OpenGL in applets is more trouble than it’s worth.)

(Note 4: You know what, I’m sick of this asking for security permissions and whatnot every time the front page loads. The applet is moved below the fold. Continue at your own risk.)

» Continue reading “Perlin noise applet”