I keep a picture of Dijkstra in my office as motivation. I don’t necessarily agree (anymore) with his perspective on correctness and formality, but I have to respect his persistent pursuit of the ideal.
If in physics there’s something you don’t understand, you can always hide behind the uncharted depths of nature. You can always blame God. You didn’t make it so complex yourself. But if your program doesn’t work; there is no one to hide behind. You cannot hide behind an obstinate nature. A zero is a zero, a 1 is a 1. If it doesn’t work, you’ve messed up.
This Geek Hero comic by Salvatore Iovene reminded me of a recommendation I made about programming a few years back. Even with the best documentation and planning, effective programmers must keep a lot of state and context in their heads. That’s why it’s so difficult to get back into the flow the next day, why even a 10-minute interruption can cost hours, and why — above all else — we can’t call it a day until we reach ‘a good stopping point’.
The trouble is, most people are terrible at predicting how long it will take to get to that stopping point. That gut feeling that we’re “really close to fixing this bug” (or finalizing that class, or finishing this refactoring) can last for 4 or 5 hours — until either we do finish it, or we determine for certain that it’s an order of magnitude more work than we thought. In grad school, my office-mate’s girlfriend once asked me what was going on when her beau said he’d be home in an hour, but three hours later she’d phone and he’d still be there. I’m sure many hacker widow(er)s are familiar with this scenario.
I don’t claim to have a solution to the problem of restoring context after an interruption; however, I have come to believe that insisting on a good stopping point is counterproductive. Let’s say you get there: bugs fixed, test suites passed, clean code committed, and you go home happy. I claim that the context problem will be even worse the next day. You sit down, type ‘make’, and it builds cleanly. You type ‘make test’ and it succeeds spectacularly. You type ‘svn status’ and your working copy is clean. Now what? Meh. Fire up the feed reader and ease into your day.
Imagine this alternative. You’re implementing a new function you’ll need to fix a bug, but it’s getting late. You hit the build button, ready to try it out, but instead you get 21 compiler errors. Perfect — go home now. WHAT!? I know, it pains the hacker’s brain even to imagine it. That’s not a stopping point! But think about tomorrow. You sit down, build it, and suddenly you are pulled right back into the code, fixing the errors. Sure, it will take you a bit longer without the immediate familiarity you had last night, but you’re already engaged in a simple, low-level activity that will help you restore context quickly.
One area of study in my CS101 course (a broad overview of the field, mostly for non-majors) is why computers use binary representations, and how to represent numbers, text messages, pictures, and even music in binary. Computers are really only good at number-crunching, but they’ve become pervasive in other pursuits because, in the end, it’s all just numbers.
So one little exercise I prepare for students is to convert icons to and from hexadecimal strings, just like I did in the 80s with graph paper and pencil, to program sprites (animated icons) on my TI-99/4A home computer.
This one here is an alien from the early arcade game Space Invaders. I dig up icons of Atari Pac-Man ghosts, and the little alligators from Pitfall. I’m sure they’d rather see high-resolution WoW avatars in 24-bit color, but nobody would want to encode one by hand. The point is, once you understand the basic process of binary encoding, anything you want to do is just a matter of scale and patience.
10 LET $ALIEN = "183C7EDBFF245AA5"
Hexadecimal is still amazingly useful in computer programming, so it’s unfortunate that the novice’s only exposure to it is in error messages, such as the BSoD. I brag about how one summer I could add and subtract very fluently in hex, when I was coding device drivers for serial communications. I’m not sure they’re impressed…
I was bitten by this bug in version 1.9.2 of the Moodle course management system. It prevented restoring a backup made by any newer version of Moodle. Of course, such a restore could fail if it relies on features particular to the newer version. So there’s a conditional that will display a message to that effect, but within the conditional was a typo:
In other words, by trying to warn the user about possibly erratic behavior, it caused definite failure.
It’s dreadfully familiar, isn’t it? Just a throwaway conditional that you assume will work without sufficient testing. Just a fault that slipped into a point release and was fixed in the next one. Not a big deal, but there’s a lesson here.
My position on the static/dynamic typing divide is well established, even though I’m not as entrenched as some. I will somewhat happily use Python or PHP for web applications. I advocate for Scheme, and I think Ruby is neat. But I’m still disappointed whenever I produce or find faults that by all rights should have been caught by a compiler. It just demonstrates the increased importance of automated testing with coverage analysis when using dynamic languages.
This short video (3:24) is about an idea I have for an automated tool that would tutor and assess students on fundamental skills in computer programming. I call it the ‘codeTutor’. I find that students that need a lot of practice on rudiments are often not willing or not confident enough to create their own exercises, and I don’t have the time to keep them inundated with practice problems. So here’s my idea:
If you think this is a {useful,great,dumb,old,…} idea, leave a comment or get in touch by email. If you’d like to participate in building or testing, even better. I’d want the tool to run as some kind of {Flash,Java} applet, or maybe Java WebStart program, just to lower the barrier to running it. Since it will do some non-trivial manipulation of syntax trees (and for a variety of other good reasons), I may write it in Scala instead of just Java. I’ve been toying with Scala for a few days, even producing little Swing (GUI) apps, and I’m fairly pleased.
Bootstrapping a compiler can be a finicky process, because many compilers are written in the language that they compile. It’s easy to paint yourself into a corner if you’re not extremely vigilant about binaries and configuration management.
I wanted to try SMLserver, a system for writing database-backed web services using Standard ML. It is tightly integrated with the MLkit compiler.
Unfortunately, the distributed binaries would not run on my installation of Debian stable (codename ‘etch’) because they expect a newer version of ‘libc’, the main system library. Upgrading that library could be pretty disruptive, which defeats the purpose of running a ‘stable’ distribution.
Unlike many compiler code bases, MLkit can be built by compilers other than itself, namely SML/NJ and MLton. Ordinarily, this would simplify the process, except that the SML/NJ version it requires is ancient (and doesn’t itself compile out of the box anymore on this system) and MLton has extreme memory demands.
Fortunately, an older binary of MLkit (4.3.0) runs on this system, but at best that’s a starting point. Once a particular revision can bootstrap itself, it’s natural for the source language to evolve beyond what the previous revision could handle. But in this case, the changes were small. Version 4.3.0 lacks some pieces of the ‘Posix.FileSys’ module that 4.3.2 needs, but they were small enough to rewrite:
Index: src/Tools/MlbMake/MlbFileSys.sml
===================================================================
--- src/Tools/MlbMake/MlbFileSys.sml (revision 2311)
+++ src/Tools/MlbMake/MlbFileSys.sml (working copy)
@@ -49,9 +49,9 @@
| EQUAL => SysWord.compare (b,d)
fun unique link f =
- let val s = if link then Posix.FileSys.lstat f else Posix.FileSys.stat f
- in (Posix.FileSys.inoToWord(Posix.FileSys.ST.ino s),
- Posix.FileSys.devToWord(Posix.FileSys.ST.dev s))
- end
+ let val {dev,ino} = OS.FileSys.fileId f
+ in (Word.fromInt ino,
+ Word.fromInt dev)
+ end
end
Index: src/Manager/Manager.sml
===================================================================
--- src/Manager/Manager.sml (revision 2311)
+++ src/Manager/Manager.sml (working copy)
@@ -807,7 +807,6 @@
val fu = (Posix.IO.close (Posix.FileSys.creat (lockfile ^ unique,Posix.FileSys.S.iwusr)) ; true) handle OS.SysErr _ => false
val f = if fu
then (Posix.FileSys.link{old=lockfile ^ unique, new=lockfile}; true)
- handle OS.SysErr _ => Posix.FileSys.ST.nlink (Posix.FileSys.stat (lockfile ^ unique)) = 2
else false
in if fu then (Posix.FileSys.unlink (lockfile ^ unique); f) handle _ => f
else false
Version 4.3.0 can build 4.3.2 patched thusly, which can then bootstrap its unmodified self. Really, I lucked out here. Imagine having to do this across a major compiler release cycle!
Over the past few days, I’ve been cleaning up compromised web sites that run PHP-based content management systems. This got me thinking (not for the first time) about the sad state of CMS security.
One of the key problems is that CMS software is not always treated with the same level of care as regular system software. As with any net-facing software, flaws must be carefully tracked and patches swiftly applied. This is tricky because CMSs are not always installed using the regular package administration system; often they are uploaded into the public_html spaces of regular users.
But I want to address an underlying problem that has more to do with the design of these systems themselves (which of course impacts their suitability for packaging and maintenance in something like the Debian archive). In my experience, many content management systems jumble together the following kinds of files and code that should — following the principles of least privilege and privilege separation — be kept distinct:
Data files or scripts that should directly correspond to URLs.
Data files or scripts that are merely included or opened from other files, and therefore should not be reachable from any URL.
Code that needs privilege to write to the file system or database.
Code that merely needs read privilege.
Directories in which the code can create and modify files.
Writable directories whose contents are accessible as URLs.
Writable directories accessible as URLs, in which script extensions (.php, .cgi, etc.) are honored.
The astute reader should be able to deduce the security implications of each of the above, but here are some hints. Web-accessible library code increases the surface area for exploits. Writable, web-accessible directories invite spam content. Writable, executable, web-accessible directories are havens for malware.
Keeping these categories distinct would not just increase the baseline security of the CMS, it would also improve usability with other tools like chroot jails and suPHP. The latter provides privilege separation by executing scripts with the privileges of their owner rather than the web user (www-data), but of course that requires spawning a new process for each request. One of the reasons that PHP (and later, Python) proliferated in web applications is the lower overhead of running the interpreters as modules within the web server. By isolating the bits of code that need write access, one might achieve a better compromise of efficiency and security.
I understand that a reason for flouting security conventions (apart from ignorance) is ease of installation. Content management systems are often set up by naive users over FTP connections to unprivileged accounts on shared hosts. But I believe it’s entirely possible to design the system more securely for expert users or site administrators, while still allowing naive users their (more vulnerable) one-click installs. Pay-as-you-go security. The content management systems that do get packaged for Debian are usually configured in a pretty reasonable way, but it’s telling that the worst offenders don’t get packaged at all.
For my rngzip XML compression tool, written in Java, I wanted to incorporate LZMA, a fast compressor based on Lempel-Ziv (like gzip), but with better compression ratios and the same or better speed. Apparently 7-Zip is somewhat popular in the Microsoft world, but has not made much impact on Unix yet, perhaps because the original implementation was extremely dependent on Microsoft APIs. That seems to be changing: ‘lzma’ and ‘p7zip-full’ packages are available in the new Debian etch release.
Anyway, there is a Java implementation of LZMA, but it does not use the standard FilterOutputStream approach of the java.util.zip package — closely followed for implementations of BZip and PPM-based arithmetic coders. And it’s not nearly as simple as changing around some method names.
No, the LZMA encoder wants to pull bytes from an InputStream and push the compressed representation to an OutputStream. In contrast, the FilterOutputStream approach is a ‘push’ model — the caller remains in control, pushing bytes to the encoder as it pleases. I had seen this contrast before, for example in XML parsing itself. The Simple API for XML (SAX) is a ‘push’ technique, which is why writing SAX event handlers is such a pain. I can hardly fault the author of the LZMA encoder for wanting to structure the code this way. It makes it much simpler, and if all you’re doing is compressing existing files, you don’t need a stream processor.
Of course, the programming languages geek in me recognizes this dilemma as a need for coroutines! The push/pull controversy is really about which module wants to be in control. With a single thread of control, all but one of the cooperating modules must be turned inside-out, written in a passive structure. Sometimes this isn’t too hard, and sometimes it’s monstrous.
With coroutines (or continuations, which can implement them), all of the modules can be written as though they maintain control, simply ‘yielding’ results to each other across the divide. Java doesn’t have coroutines or continuations, but it does have multi-threading. So, once I recognized what was needed, in short order I whipped up an LzmaOutputStream (and LzmaInputStream) that spawns the Encoder (Decoder) in a separate thread and passes bytes to it using a blocking queue. Classic producer/consumer concurrency, which should delight my students in Operating Systems.
I’ll make the code available here at some point, but if you’re looking and can’t find it yet, let me know! Efficiency is horrible at the moment, because I’m currently using ArrayBlockingQueue<Integer> from the Java library. This means, I presume, that each byte dropped into the queue is allocated as a new object! Might have to implement my own blocking queue with semaphores and a lighter-weight int[] representation.
Update (18 April 2007): code is now available here, and I ditched the generic ArrayBlockingQueue.
Ugh, again I fight this battle. While hacking on my XML compression tool ‘rngzip’, I’m subclassing Java’s input/output stream hierarchy. The read and write methods use int instead of byte so that we may use -1 to represent end-of-file.
But surprisingly, Java bytes are signed. There is no way to specify unsigned numbers, and the primitive casts automatically do sign extension So when you cast a byte containing 0xFF into an integer you get 0xFFFFFFFF, which is -1. This can cause a great many bugs, some of them not apparent until you’re processing a binary stream with bytes equal to 0xFF.
The decision to use int here is questionable too, but Java has no lightweight way to specify ‘byte option’.
I’m giving a talk on Thursday for our CS club (a student ACM chapter). Our compilers course is hardly ever offered, because it ends up being a fairly arcane topic considering the career goals of the majority of our students. There are ways to make it more relevant of course, but I don’t want to argue either way on that today.
Instead, I decided to put together a fun little talk for the club on some of the ‘big ideas’ in the area. Here’s the abstract:
One of the more profound concepts in computer science is compiler bootstrapping: very often, the compiler for a programming language is written in that language itself. This begs an almost mystical question: what compiles the compiler? (And what compiled that compiler, and so on…) The first part of this talk is an adaptation of the famous Turing Award speech “Reflections on Trusting Trust” by Ken Thompson, co-inventor of the UNIX operating system. We explore the bootstrapping concept, and how to exploit it to devious ends. The second part is a very brief introduction to program analysis and compiler optimization, using static single assignment form.
I’ve been experimenting with some code to show that technique of teaching the compiler once, and then removing it from the source. Ken Thompson used the example of control codes, with a fragment of code that essentially said case '\n': return '\n'; but I found an enlightening post on the topic that cites this trick, from a Pascal compiler:
The value of INTEGER_MAX was ‘taught’ to the compiler at some point in its evolution, but since the compiler compiles itself, it is no longer needed. Pray you don’t lose all the binaries!
I’d like to turn the talk into a screen-cast, just because I’d like to experiment with that as a pedagogical format, and (I think) I have the tools. We’re starting to see lots of ‘Web 2.0’ tool-builders publish video tutorials. I doubt I’ll record any audio/video directly during my talk, but rather use that as a trial run of the script. Watch this space!
The first week of classes seemed to go okay. I’m excited about exchanging code with students using Subversion. Not for group projects, mind you, but in place of downloading my support code and stubs, then emailing back their solutions.
Today I’ve been toying with GeekOS, trying to increase my understanding, and look for other projects to do with it. When I was taking and teaching OS at Maryland, I recall doing much lower-level projects: video and keyboard drivers, getting the task switching code to work, etc. Finally understanding the task switching mechanism was a big eureka moment, I believe. I kept trying to figure out how to jump to the next task in the queue, when really what you do is return to it. From the point of view of each task, it makes a call to the Yield() function, and then sometime later, returns from it. The whole trick is to do the context and stack switch and make the call from one task return to another.
Anyway, GeekOS seems to be designed for higher-level projects now, because the video, keyboard, and task-switching code is all in place from the start. But of course, that doesn’t prevent me from clearing it away, down to just the bootstrap code, and taking my students along on that journey.
Next week, I’m going to talk about PC video modes, and how to write characters and attributes (colors) to video memory. So today I started playing with basic VGA modes, the simplest standard one being 320×200 with 256 colors, also known as mode 13h. I imported some bitmap font code from the Linux console drivers, hacked on the screen.c driver a bit, and now I have GeekOS running in VGA:
That’s a 6×11 font, and seemed to be the best-looking choice with the limited resolution and non-square pixels of mode 13h. But it’s parameterized well enough that I can change a few definitions and employ other fonts stolen from Linux. Here’s a more typical 8×8:
Kind of deliciously chunky, and takes me back to those early days of the PC, when many graphical programs had text that looked about like this. Linux also has a 4×6 font, which is pretty much unreadable, but at least you get 80 columns:
(All of the screen-shots are shown here at 67%, so click through to see the actual size.)
For the past several weeks, I had been getting up to 30 spam comments per day in the moderation queue. None of them appeared on the site, but receiving the email notifications and having to clear out the queue periodically was a pain. Besides, when I set up WordPress, I took care to implement my own custom “Turing test,” where would-be respondents must answer simple questions like “What is Prof. League’s first name?” Were the spam-bots lucky or clever enough to be answering these questions correctly? Or were they somehow bypassing the test?
This morning, I finally had a chance to investigate what was going on. I added some tracing statements to the commenting functions, so that when they were invoked I would receive an email with some information about variables and control flow. Some tracing emails started showing up within 15 minutes, and I learned two things: the spam-bots were not providing correct answers to my Turing questions (that’s good), and the IP addresses in the traces and the ones getting spam into the moderation queue were disjoint (that’s bad). Well, good and bad. It means that the spam-prevention measures in the regular comment code are working, but also that there must be a back door.
By grepping the server logs for yesterday’s spam-submitting IP addresses — don’t know why I didn’t think of that first thing — I discovered the back door: trackbacks. This is a facility for one blog post to link to another as a comment. This is an interesting idea, but since it’s some other blogging software that does the posting, I can’t really implement extra spam prevention measures here. So I decided just to disable trackbacks and pingbacks completely. That should do the trick!
The byte type in Java is, strangely, signed. So bytes range from –127 to +128. So you cannot write byte b = 0xCA directly (because 202 > 128) but the (byte) cast does sign extension.
The problem I’m fighting with now is with input/output streams. The OutputStream class has two methods that take byte arrays, but the abstract method write that takes an int. With the InputStream, the abstract read returns an int mainly so that it can return –1 for end-of-file, so I guess that write uses an int for consistency.
But here’s where it gets really weird. Normally converting between byte and int does sign extension, but apparently that’s not what you want here… or is it? The specification of void OutputStream.write(int):
Writes the specified byte to this output stream. The general contract for write is that one byte is written to the output stream. The byte to be written is the eight low-order bits of the argument b. The 24 high-order bits of b are ignored.
and of int InputStream.read():
Reads the next byte of data from the input stream. The value byte is returned as an int in the range 0 to 255. If no byte is available because the end of the stream has been reached, the value -1 is returned. This method blocks until input data is available, the end of the stream is detected, or an exception is thrown.
Got it? In both methods, just the lower 8 bits are used, except in the case where read() returns –1 for EOF. But here’s the thing—OutputStream violates its own contract:
import java.io.*;
class StreamTest extends OutputStream {
publicvoid write(int b) throws IOException {
System.out.println("Writing int " + b);
}
publicstaticvoid main(String[] args) throws IOException {
byte[] bs = { (byte)0xCA, (byte)0xFE,
(byte)07F, (byte)032 };
new StreamTest().write(bs);
}
}
The above code sets up a byte array, and passes it to OutputStream.write(byte[]), which in turn iterates and calls my overridden write(int). But in converting byte to int, it does the normal sign-extension widening, so that it’s not just the lower 8 bits I need to pay attention to in write, it’s the lower 7 bits and the sign. (Update: oops, I overlooked that the representations are the same thanks to two’s complement!)
Arguably, write doesn’t need to be as picky about the sign as read, since read uses –1 to indicate EOF. Indeed, if I try:
then it outputs –54 64 0 0, because the 0xFF = –1 is interpreted as EOF. The read method needs some sign-inverting logic like: bs[i] > 0? bs[i] : bs[i]+256
This all started with some 3rd-party library code I’m trying to use, for arithmetic encoding (compression) using prediction by partial match. They defined filtering input and output streams that seem to work okay in tests, but fail miserably as soon as I wrap them in a DataOutputStream. It turned out that they were doing sign-inversions — not in the way I showed above — but in a weird place. As long as you write bytes as an array and then read them as an array, it happened to work. But if you write an array and then read one at a time, the conversions don’t work out. They also seemed to take the specification of write(int) at face value, just assuming that the parameter would be non-negative.
In AI yesterday, I began describing genetic algorithms, a.k.a. evolutionary programming. I thought it important to get the essence of Darwinian evolution on the record too: descent with modification plus selective survival. I find that even among people who are generally supportive of evolution, and science in general, there is a lot of misunderstanding about how it works.
By watching the reactions on my students’ faces, I began to realize how brutal the whole thing sounds. Evolution has an enormous death toll. Lots of critters must die in order for the average fitness of the population to increase. This carnage, resulting from competition for scarce resources, is not optional; it’s essential.
It sounds all the more sinister when I mention that we will impersonate gods by applying our own selection criteria to the population. This isn’t natural selection, it’s artificial. You get to live and reproduce because you came closer to solving my problem than your peers did. In contrast, natural selection seems like a harmless truism: those who are good at surviving and reproducing are more likely to survive and reproduce.
Again, I tried to make the lecture more interactive with props. And nothing represents the concept of chance better than dice. Ideally, for an in-class demonstration, I’d like to leave nothing to chance. But in this case, I gave the dice to my students, put the success of my demo in the hands of Fortuna, and thus demonstrated my own ‘faith’ in the evolutionary process.
We ran through a simulation on the board, where I wrote 6 random 6-bit strings, and computed their fitness as solutions to a 0-1 knapsack problem with 6 elements. As my students passed and rolled the dice, we went through tournament selections, cross-overs, mutations, etc. The average fitness score of our offspring were clearly increasing compared to their parents. And I thanked Fortuna when, on the final roll of the die, a mutation flipped precisely the right bit to produce the optimal solution to the problem. (If that didn’t happen, I’d either have to go on to a 3rd generation, or be content with demonstrating just an increased average and max fitness.)
Such a gloomy, rainy day. Perfect for staying home and hacking.
One course I’m teaching this semester is artificial intelligence. It has nothing to do with my usual areas of interest, but it has always had a special place in my brain. Especially the early symbolic stuff… it’s good fun, no matter that the grand claims for it never panned out.
So I decided, in my subversive PL geek way, to use this opportunity to introduce my students to Scheme. Specifically, I’m using the PLT DrScheme environment as a companion for my AI course. I know that true Lisp is traditional, but I was really seduced by Scheme in my younger years (until ML came along) and it has been a pleasure so far to come back to it. Plus I can set up some nifty cross-platform graphical simulation thingamabobs for my students, which they’ll appreciate.
I chose the AI book by Nilsson. In my first course, we used Winston, and Russell/Norvig seems to be dominant these days. But I’m never one to choose the dominant platform just because it’s dominant (haven’t owned a copy of MS Windows since version 3.0). I still have fond memories from Winston, and was a touch disappointed to find that it hasn’t been updated in all these intervening years.
Anyway, Nilsson starts out with a “grid world” inhabited by an intelligent agent (robot). The first task is to try to make the robot follow the wall clockwise around the room. In other words, the first smidgen of intelligent, goal-directed behavior is to avoid walking into walls. Impressive, eh? Next stop: The Matrix.
So, I used DrScheme to bring the grid world to life, and allow my students (who, after all, have no Scheme exposure at all) to dig right in developing little wall-following robots, just by typing stuff like (if (or s1 s2) ’north (if … )), where s1–s8 are sensors for the 8-directions (clockwise starting from north-west) that return true if a wall is detected. Once you set up your little if-then-else robot controller, you can graphically place a robot on the grid and have it travel one step at a time around the room. The code for my simulator is here: gridworld.zip; just open grid-main.scm in DrScheme. (Select the graphical language, with MrEd + MzScheme.)
Next we’re going to jump right in to two kinds of machine learning, first by inferring a decision tree from a set of examples (Quinlan ID3 algorithm), then by evolving robot behavior by genetic programming. Both of these can be readily applied to the robot world, among other applications.
The students seemed fairly excited by Scheme, on their first exposure. “It’s so easy,” one said, although admittedly he had just been watching me; they have yet to write any code on their own. Nevertheless, I was a little surprised by the enthusiasm. Good signs.
Say No to Extra credit
Neeraja
Sauerkraut
Rob
Rumble
link
Filed under 
Tagged 
Related posts • 
