Everything is a file – including punctuation

Unix, stop messing with my head.

davemc@slarti:~$ which [
/usr/bin/[

Stop it. Seriously.

Okay, so [ is a command. A program. An executable. Not some syntactic massage oil applied by the shell's if and while and such (although the man page hints that in some shells it may well be).

And it has most of the same behaviour as test... that, at least, makes sense. Except that [ expects a ] as its final argument, while test doesn’t.

Huh. Cool.

Comments (1)

SSH and DNS

I just needed to share that, a couple of hours ago, I finally worked out why SSH was slow to connect inside my home network. This has been nagging me for… well, years, probably. It’s one of those problems that I didn’t run into too often, and it only caused about five seconds of inconvenience each time, so it never really passed the threshold of dealing with it. Except today, for some reason.

It turns out that my server (running Ubuntu 9.10) was doing a reverse DNS lookup every time, presumably out of some effort to log the domain name of the machine trying to connect to it. The forum discussion that pointed in this direction is here; below is an outline of what I did to fix it and/or should do to fix it more elegantly, in case anyone’s interested.

Short-term solution: edit /etc/ssh/sshd_config on the server and add the line:

UseDNS no

…so that it doesn’t bother with the lookup. Then restart the SSH daemon:

sudo /etc/init.d/ssh restart

Medium-term solution: add /etc/hosts entries on the server for each computer in the house. Also, get the router to assign them static IPs. (I should probably do this anyway; I’ve just been lazy about it.)

Long-term solution: find out whether my router can work as a DNS server, or, failing that, run one on the Ubuntu box.

Leave a Comment

*pop*

…is the sound my head made when reading this post about lazy error handling in Java. You see, functional programming and Java are completely disjoint sets of neurons in my head. Seeing Java code formatted like Lisp and doing lazy evaluation… requires some rerouting.

And when the post finished with:

But there’s more to come, as Thrower has higher aspirations still. It’s not just a functor. It’s a monad.

Okay, look, I followed a link into the middle of this. I really should start somewhere earlier. I wonder if there’s a Lambda Calculus for Dummies?

Or The Complete Idiot’s Guide to Forcing Programming Methodologies into Languages that Go Out of their Way Not to Support Them?

Leave a Comment

Sudoku speedup

Previous version: 10 hours.

With the latest improvement: 33 seconds.

1         9   15 5 12   3        
    2   3     7   1     10   13  
    13 7           14 11   9      
16 12   8     2         7     3  
13       11 10 3   2           14  
  4         7   12              
14 5     15     9   7     4     6
        12     16 4     6   11 10 13
15   14     8       9 16 2   12 7  
    1 5 6     13     15   2      
10 9       11     13 8 14     4   16
      16     9 14   10       13 5  
      6 5     8   2            
  13       2   12 15 5       1 11  
8 1   3                 15   2  
      9   15     11   7 13 5      

Leave a Comment

4×4 Sudoku

The Java sudoku solver is coming along nicely. There are still a few obvious things missing; in particular there’s a simple strategy that should speed up solving quite a bit. (Which I won’t try to explain here.)

After that’s done, there’s a plan in the back of my mind to make it multi-threaded, or possibly even distributed. I’m not sure about the best place to split it up yet… For solving a puzzle that’s known to have one solution, or towards the end of generating a puzzle where only a few of the branches are valid, splitting up the brute force tasks should be fairly useful; but for choosing a value for the first cell of an empty puzzle, every branch has a valid solution, so having multiple threads exploring all of them is pointless. The most profitable time to split up the task would be early enough that the available branches are deep, and will take a while for each of the threads to explore; but late enough that only one of them is expected to be valid.

The interesting question is whether it’s possible to recognise that point.

Anyway, here’s a result from the current version. The 4×4 (er, 16×16) puzzle below took just over ten hours to generate.

6             2   15     16   11  
  2   4   3 8 12   5            
5 16 11     13 4           1   14  
  8 13           14           9 4
      14     1     7   3   4 6  
12 13 7       6 15         2   8 9
3       16 12     10     13       7
9           13 5       16   1    
  7   11         8   3       2  
13     16 8         10 1 7 4 3   6
  6           11     9 2       1
    8 1   5               13    
  15     14   3 16 2   5   12      
          2     4              
14     12   7 9 1     16   11   13  
2                 11       5 1 3

Comments (2)

Java Sudoku

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|
+---+---+---+

Leave a Comment

Encapsulation vs Security

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.)

Comments (19)

Nested chaos

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.

Leave a Comment

abs gotcha

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 -231 but not +231). 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”.

Leave a Comment

What’s wrong with this picture?

Leave a Comment