When I wrote last October in defense of strong AI, I promised to take on the ‘uncharitably narrow’ notion of algorithmic used by Ian Tattersall to argue that machines will never achieve consciousness.
In The Monkey in the Mirror (2002), he writes “Computers by their nature are algorithmic, rapidly applying a fixed set of rules to the solution of well-defined questions” [page 71]. He refers here to IBM’s Deep Blue playing chess, the canonical example of a machine accomplishment that, while impressive, is surely not conscious. From this example, he extrapolates:
Human consciousness is very clearly non-algorithmic. Even if we have to conclude [...] that subjective awareness in ourselves and our relatives is due ultimately to a mass of electrochemical events in the brain [...] it is equally clearly not the product of a mechanism that dutifully clicks through a listing of tasks and ‘if-then’ choices.
I bristle a bit at this formulation, and I imagine it must annoy most software developers. It’s too narrow, in at least two dimensions. First, it seems to exclude non-determinism and parallelism: a genetic algorithm is still an algorithm. But more crucially — even if we assume deterministic sequential code — Tattersall appears to underestimate the complexity of everyday computer programs.
It doesn’t take very much code to produce a system whose precise behavior is practically unpredictable, even by the person who wrote it. We may use strategies such as functional decomposition to design a system to target specific requirements, but as the system evolves complex behaviors emerge. If they didn’t then debugging would be easy.
Yes, ultimately any deterministic program is expressed as a list of simple instructions and branches — millions of them, coupled with sophisticated data structures in an infinite number of configurations! Tattersall makes it sound like little more than a flowchart you could hang on the wall.
I don’t claim that our current programs are conscious, or intelligent in any strong sense. But don’t rely on a naïve notion of algorithmic to argue that machines cannot be conscious.
I’m catching up on my feeds following a 2-week vacation, and I keep hearing about this “Google Wave” thing. So finally I watched the video. And because I’ve been looking for a reason to try out the timer feature of org-mode, I made some timed notes to go along with the video.
0:01:31
HTML5 app… will forget you’re looking at a pure
browser app.
0:02:02
Lars and Jens Rasmussen, behind Google Maps
0:04:06
Stephanie Hannon, project manager
0:05:11
email invented >40 years ago, before internet itself
0:05:47
what might email look like if it was invented today?
0:06:18
email systems collate related messages into
conversations
0:06:25
wave starts w/conversation = lightweight tree structure
of messages, and users participating.
0:06:40
conversation object = shared object, hosted on a server
somewhere.
0:07:38
built with Google Web Toolkit and HTML5
0:08:19
spelling auto-correction, like on iphone
0:09:35
reply to part of message by splitting it
0:10:35
Shiny.. firefly reference.
0:10:39
Character-by-character echo during IM.. speeds up
conversation.
0:12:47
adding new participants.. avoid the “cat and mouse”
where ppl reply to early one without all participants.
0:13:17
playback to see messages in order
0:14:10
GWT pronounced “gwit”
0:14:39
Private reply possible within the wave.
0:15:10
Any subtree can restrict access to subset of
participants.
For a one-time strong static type snob, I’ve become pleasantly enamored with Python lately. Seriously — it’s a Lisp for a new generation. I remember when I first heard about Python, people seemed to place it in the same class as Perl (so-called scripting languages) and since I already let Perl taint my brain, I figured one was enough. That was a mistake.
What really made me take a closer look at Python was the object-relational mapping in Django. Specifying data models in Django is natural, convenient, powerful and — get this — there’s no code-generation step. No turn-the-crank-and-output-a-mess-of-code tool to add to your Makefile. Advocates of Domain Specific Embedded Languages in Haskell might even be pleased, except that it doesn’t take three Ph.D. dissertations’ worth of language extensions to satisfy the type checker. (Ouch — did I just bite the hand that fed me? Whatever, it’s a ’blog… the medium practically invites polemics.)
Anyway, test-driven development (TDD) is a necessity for dynamic languages. When a typo in a method name has no ramifications until run-time, there had better be some unit tests exercising that code frequently and automatically. Once you have the framework in place, it’s a baby step to writing a test that fails before you code the feature that satisfies it.
I ought to take it further. I’m not yet coverage-testing. Ideally, commenting out any single line of code should cause some test to fail. Even changing a ‘<’ operator to ‘≤’ should cause some test to fail. That’s how you get to more lines of test code than normal code.
And now Dijkstra’s spirit is looking over my shoulder, muttering something about “hopelessly inadequate”. Oh well, maybe in a few weeks I’ll be hacking together something in Scala or proving something in Coq, and I’ll change my mind about static type discipline again.
The iTunes smart playlist feature is remarkably easy to use and can do some pretty sophisticated things. But there’s one more feature I’d like to have: I’ll call it a weak reference, by analogy to a similar concept in computer programming languages.
Without going into mind-blowing detail — this isn’t a post about programming languages — a weak reference is a way to refer to some object so that you’re not required to keep it around. Think of bibliographic references from one book to another in the library. A strong reference from book A to book B would mean that you can’t check out book A without also taking along B! In contrast, if it’s a weak reference, then you might check out A, encounter the reference to B, and say “Oh well, I don’t have that book with me right now.”
Playlists (smart or not) are the primary way that I specify which songs are copied to my iPod. I have one dumb catch-all list “iPhone” into which I can dump anything I definitely want synchronized. There’s a smart list “Recently added” that makes sure that any tracks added to the library in the past 3 months end up on the iPod. Also, anything with a star rating gets copied, so that will include lots of individual songs that are (for me) the highlights of their albums, for example.
Maybe you see where I’m going with this.
I want to create smart playlists to specify queries, and I’d like to sync those queries to my iPod, but I don’t want membership in that list to be enough to pull all matching songs onto the player — it would just contain those that match the query and are on the device already by virtue of being on other lists.
Here’s an example: I have a smart playlist on iTunes called “not classical” that simply excludes tracks from certain genres (classical, opera, speech, broadway) that I don’t want to pop up in an otherwise wide-ranging shuffle. Now, if I specified that “not classical” should be synchronized to my iPod, it would pull in much of my library, and would not fit. However, if I could sync it as a weak reference, then I could still use the results of that query applied to tracks already on the player.
The other day, for kicks, I wrote a small program to embed a hidden image within another image, and another to extract the hidden image. This is called steganography:
…the art and science of writing hidden messages in such a way that no-one apart from the sender and intended recipient even realizes there is a hidden message, a form of security through obscurity. By contrast, cryptography obscures the meaning of a message, but it does not conceal the fact that there is a message. [Wikipedia]
With hidden image embedded; the differences are all but invisible.
Embedded image partially revealed by shifting colors; click through to see more.
Step through the demo on flickr, and read the descriptions to understand what’s going on. In this technique, I use 6 bits per channel for the outer, visible image, and 2 bits per channel for the hidden image. However, the composed result is pretty much indistinguishable from the original.
The programs use the GraphicsMagick variant of the ImageMagick library. (I had GM ready to go already because I used it for other projects.) If you want to play with these images yourself, the JPEG conversions on Flickr will not work; download this PNG instead.
// Steganographic decoder, requires GraphicsMagick
// Copyright 2009 Christopher League
// This is free software; you may distribute & modify it under GNU GPLv3
#include<Magick++.h>
#include<iostream>
using std::cout;
using std::string;
using namespace Magick;
Quantum revealDisguisedColor(Quantum q)
{
// just keep lowest 2 bits, then amplify by 2^6
return (q & 3) << 6;
}
intmain(int argc, char** argv, char** envp)
{
InitializeMagick(*argv);
assert(argc == 3);
const string samplePath = argv[1];
const string outputPath = argv[2];
cout << "Loading " << samplePath << '\n';
Image im (samplePath);
Geometry g = im.size();
cout << "Dimensions are " << (string)g << '\n';
cout << "Depth is " << im.depth() << '\n';
assert(im.type() == TrueColorType);
for(unsigned x = 0; x < g.width(); x++) {
for(unsigned y = 0; y < g.height(); y++) {
Color c = im.pixelColor(x, y);
cout << (string)c << " --> ";
c.redQuantum(revealDisguisedColor(c.redQuantum()));
c.greenQuantum(revealDisguisedColor(c.greenQuantum()));
c.blueQuantum(revealDisguisedColor(c.blueQuantum()));
cout << (string)c << '\n';
im.pixelColor(x, y, c);
}
}
cout << "Writing " << outputPath << '\n';
im.write(outputPath);
return 0;
}
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!
jan
Kevin
RW
siva
pir
link
Filed under 
Tagged 
Related posts • 
