Paul Butler.org

Yesterday, a group inside Google released a new programming language called go. Among the many comments on the new language, I noticed a number of people rhetorically asking if there is really room for more programming languages. I’ve seen the same sentiment expressed before, seemingly whenever someone releases a pet language (Arc, Factor) or rediscovers an older programming language (Smalltalk, Erlang, LISP).

I’m convinced that there is, in fact, room for more programming languages.

I recently read The Mythical Man Month, the 1975 classic about software engineering. Two things stuck out at me. First, that compared to programmers in 1975, programmers today are spoiled by hardware. Many software constraints, like memory and CPU speed — let alone the size of the program on disk — are not issues worth much thought for many software projects. There are of course exceptions: low-level systems code, graphics, data-intensive calculations (in other words, “the fun stuff”) — but in general, application programmers face far fewer constraints than they did 35 years ago. The second thing that struck me is how comparatively little programming has changed since then. Despite the loosening of constraints, we still write applications that, say, directly use pointer arithmetic and manually allocate and deallocate memory.

It’s not just C++, either. Here’s an experiment. Consider the last program you wrote in any language. Imagine you had to describe, in plain English, your program. The description must be complete enough that another programmer could read it and produce your program. Not your program exactly, of course, but one that satisfies the same requirements your program does. (If you actually try this, you may get something that looks like it was written by a lawyer who charges by the comma. That’s fine.)

Now compare your description to the program’s source code. The source code is almost certainly several times longer, less intuitive, and less descriptive. And yet, if your description is precise enough, all the source code does is communicate the same idea to the compiler.

There are two main things that differentiate the source from your description. One is that the source is designed so that a computer can parse it. This amounts to having some regular structure and a well-defined meaning to all the symbols. The other difference is that the description defines what the program should do, and the source describes how. These differences both contribute to the verbosity of the source code, but I suspect the latter contributes more (consider how concise formal math notation can be, despite having structure and being well-defined).

The obvious way to make a language more expressive, then, is to make it more declarative — to describe what the program does, not how it does it. Ideally our programs could be completely declarative. We could translate the description we wrote for the experiments a few paragraphs back into a more formal language, without adding any implementation details. Then we would have a compiler that created a program which satisfied our description and produced an executable. This type of programming is actually possible in certain, constrained domains (SQL and Prolog, for example), but unfortunately there isn’t a good general algorithm to translate any program we describe declaratively into machine instructions.

The best we can do, then, is to give imperative languages more declarative features. In fact, many high-level language features fall under this category. Take continuations, which let you say “resume code at this point” instead of how “store these pieces of state there, then restore the state and return here when called”. Or list comprehensions, which let you say “give me a list satisfying these properties”, rather than “loop through these elements and do that to them, discarding them if this is not true”. Or iteration constructs, which let you say “do this stuff for each element in that”, without specifying that space must be allocated for a counter, how to look up each element, or that the counter is incremented after each element.

All of those concepts have existed for decades. When available, they make code easier to write, understand, and modify. But even today, if you want to develop a native, cross-platform application, you have to give them all up or resort to using a relatively obscure language like Haskell.

It’s unfair to expect C++ to evolve to support these features, because it has decades of legacy code that it must be backwards compatible with. The language must be improved by either breaking legacy code or adding language features in an awkward sort of tacked-on way. Neither works very well, so the language evolves slowly or not at all.

I don’t mean to knock C++; sometimes it’s exactly what the problem needs. But I think a lot of programmers’ time is wasted solving high level problems with low level tools.

I’m doubtful that any one language will ever be the right tool for every job. Certain abstractions work well with certain domains (continuations with web programming, the actor model with concurrency, etc.), and abstractions that are baked into the language tend to have advantages to those that aren’t.

That’s why I welcome new programming languages. And as long as programming languages are less expressive than written English, I’ll keep welcoming them.

Most people who like puzzles or study computer science have probably encountered the famous N-Queens problem. If you haven’t, before reading any further, try this online version of the most popular form, the 8-Queens problem.

The 8-Queens problem is to find positions on a chess board for eight queen chess pieces so that none of them “threaten” the others. Since a queen in chess can move horizontally, vertically, and diagonally, this means placing each queen on her own horizontal, vertical, and diagonal lines.

The N-Queens problem is a generalization of the 8-Queens problem with (surprise) queens instead of 8, on an board instead of a standard chess board.

In the spirit of Perl Golf, I wondered what the minimal amount of code would be to solve the N-Queens problem. As an arbitrary target, I picked 140 characters, also the limit on message length imposed by Twitter. I picked Haskell, knowing its list functions and generally terse syntax would come in handy. Naturally, I broke all the conventions that would cost extra characters, like using whitespace and explicit function signatures.

Since Haskell modules have a bit of overhead that would use up my valuable characters, I had to cheat a bit by leaving the module declaration out. The only way to run the program unmodified is to name it .ghci to trick GHCi into using it as a start script.

The result follows. I used 140 characters exactly, including the newline character.

Pretty, eh? Fine, maybe not, but it works:

> nqueens 4
[["a2","b4","c1","d3"],["a3","b1","c4","d2"]]
> nqueens 5
[["a2","b4","c1","d3","e5"],["a3","b1","c4","d2","e5"],
["a3","b5","c2","d4","e1"],["a4","b2","c5","d3","e1"],
["a2","b5","c3","d1","e4"],["a1","b3","c5","d2","e4"],
["a4","b1","c3","d5","e2"],["a5","b3","c1","d4","e2"],
["a1","b4","c2","d5","e3"],["a5","b2","c4","d1","e3"]]

The result is a list of queen positions given as coordinates on a chess board (generalizing them in the obvious way).

As an example, the result ["a1","b5","c8","d6","e3","f7","g2","h4"] would look like this:

Eight Queens Solution (created with ChessUp)

Before I explain how it works, I’ll put the whitespace back in.

Ignore diagonal movements for now — we could call it the N-Rooks problem. If we want to place rooks on a chess board so none of them are threatened, each needs to be in its own column and row. If you number the rows , each solution corresponds to a permutation of these numbers. The board above, for example, would be [1, 5, 8, 6, 3, 7, 2, 4]. So to solve the N-Rooks problem in Haskell, all we need is permutations [1..n].

That’s a good start, but we have to consider the diagonal lines as well. The simplest way to do this is to assign the columns numbers from to . Then add those to the number of the row the queen in that column is in (remember, since we are using permutations, there is exactly one queen in each column).

For example, if we add [1, 5, 8, 6, 3, 7, 2, 4] and [1, 2, 3, 4, 5, 6, 7, 8], we get [2, 7, 11, 10, 8, 13, 9, 12]. The resulting numbers are all different, so the queens are all on different diagonal lines — at least for downward diagonals. For upward diagonals, we could do the same thing but use [N..1] instead of [1..N].

Since every character counts here, it’s better if we can do both diagonal directions at once. This complicates things a bit because without caution, the numbers for upward diagonal lines will overlap with those for downward diagonal lines. Fortunately, we can just add a constant factor of at least to either set of lines. This is essentially what the code above does, although the arithmetic is a bit more cryptic to keep the character count down.

The resulting list will have elements — for the upward diagonal lines and more for the downward ones. Now we can use nub to rid the list of duplicates. If the list had no duplicates — that is, each queen is on her own diagonal lines — the length of that list will still equal after duplicates are removed. That makes it a valid solution, so it is included in the result.

I should note that this algorithm isn’t (nearly) as efficient as a standard backtracking approach as described on Wikipedia’s eight queens puzzle solutions article. But good luck getting one of those solutions into a tweet.

I was curious to know how many companies were founded by UWaterloo’s class of 2009, so I put together a list. It’s probably incomplete (let me know in the comments), but it may be of interest to anyone who follows the entrepreneurial community in Waterloo.

NeverBored Studios is a Waterloo-based game company founded by Velocity “alumni” Jimmy Ho, Thomas Ang, Orin Bishop, and Steve Truong. They are working on an iPhone game called ThreadBound, which they demo on YouTube. They were recently covered on TechVibes.

EightyTwenty Group, founded by Ray Cao and Aditya Shah in Toronto. They are working on enterprise software for law firms. Ray is a former president of Impact. I had the pleasure of working with Ray at Polar Mobile (another UWaterloo start-up) last summer. He and Aditya are smart and capable guys, so I’m looking forward to seeing EightyTwenty Group progress. EightyTwenty Group was featured in a National Post article in March.

Giftah originated as a Velocity project. Although it is only a part-time project for founders Rezart Bajraktari, Nick Belyaev and Henry Finn, they’ve managed to create a functional site that has been featured on CTV and The Montreal Gazette. They also won $2,000 at the Velocity Project Exhibition.

Unsynced is a Toronto software start-up founded by Ted Livingston, Vassili Skarine, and Vick Yao. They are developing BlackBerry software to allow users to sync their music collection and listen from their BlackBerry. Unsynced won free patent filing services at the (Winter 2009) Velocity Project Exhibition. They were also featured on TechVibes.

Mississauga-based Soeie is developing a tool for organizing research called Thinkpanda. I can’t find names of the entire founding team, but I do know that Fahd Butt has the title “CTO” (“Chief Thinker Officer”). Technically I think these guys are class of 2008, but since Thinkpanda is a new product and looks promising, I’ve included them anyway. They also have a cool logo.

Update: I found another (thanks, Peter)

Allerta started as the Velocity project of Eric Migicovsky. They are working on a wristwatch which, among other things, displays the caller ID from your BlackBerry when you get a call. Eric was profiled in The Record last October after winning a $1,000 pitch competition. Allerta is based in Waterloo.

A few observations:

• Most start-ups left Waterloo to go to Toronto.
• Three of five were part of Velocity. To me, this is some validation for Velocity after just two terms.
• Two consumer web apps, two mobile apps, and one enterprise software company.
• Most of the founders were engineering students.

Update 2: corrected Fahd Butt’s title (thanks, Rajesh)

I’ve written a little python function which I have found to be very helpful for debugging. It takes a function, and returns a function which is identical to the original except that it prints a message to the console with useful information every time the function is called or returns.

Here is the function:

The function can be used as a decorator. For example, in this simple (and inefficient) recursive Fibonacci sequence function:

The result:

The level of indent reflects the level of recursion, and the [#...] at the end of each line is the number of times the function has been called.

The level of indent is independent of the function being called, so it is helpful with mutual recursion as well. For example, when used with the functions even and odd from my earlier post on tail recursion, the result looks like this:

I find it useful to stick @report before the function I am having trouble with, and use comments to turn it on and off while I’m debugging that function. It can also be used at times other than function declaration, for example: report(base64.encodestring)(‘test’).

Update (July 6, 2008): Fixed so that keyword arguments are printed as well.

Update (August 16, 2008): Changed .__repr__() to the more proper repr().

A while ago I posted a PHP implementation of a diff algorithm I came up with¹. Since it was well received, and it’s a useful little algorithm to have, I created a Python version as well.

There are a few performance improvements as well. The PHP version creates an array in memory proportional to the square of the size of the input, while the Python version’s array is directly proportional to the size of the input. I also sped up how the algorithm finds the indexes of the “new” elements in the “old” array.

Download simplediff.py

¹ It is probably the same algorithm that others use, but I haven’t gotten around to getting an ACM membership to access the related papers

After spending a lot of time in Scheme, it’s hard not to think in recursion from time to time. When I recently started to improve my Python skills, I missed having Scheme optimize my tail recursive calls.

For example, consider the mutually recursive functions even and odd. You know a number, n, is even if it is 0, or if n – 1 is odd. Similarly, you know a number is not odd if it is 0, and that it is odd if n – 1 is even. This translates to the python code:

This code works, but only for x < 1000, because Python limits the recursion depth to 1000. As it turns out, it is easy to get around this limitation. Included below is a generic tail_rec function that could be used for most cases where you need tail recursion, and an example of it used for the odd/even problem.

It’s not as pretty as the Scheme version, but it does the trick. Of course, the odd/even functions are just for the sake of a simple example and have no real-world use, but the tail_rec function could be used in practice.

April 2009 Update: this article has recently had some popularity. One of the more common comments is that tail_rec could be used as a decorator. In fact, this isn’t true, because even and odd need access to the raw, undecorated versions of each other in the creation of the lambda.

Update: Due to lack of time and interest (on my part), I am no longer maintaining JSSpamBlock or ImageScaler.

JSSpamBlock and ImageScaler were both originally one-day projects that turned out to be a bit more popular than I expected. Recently I have neglected to update them at all, but with reports of ImageScaler not working on WordPress 2.3, I decided to put a day aside and make some changes I had been meaning to make for a while.

A new version of ImageScaler was released last week (thanks to David Karlsson for doing most if not all of the work). I still got comments that it didn’t work with WordPress 2.3, so I installed WordPress 2.3 myself to see what the problem is. I didn’t have any issues, but I made some changes to ImageScaler that might make it more likely to work. If you still have problems with WordPress 2.3, let me know. I also made another major change – images hosted on other servers were previously ignored by ImageScaler and left as-is. Now they are mirrored on the server and can be re-sized properly. Also, images are now always resized so that the aspect ratio is preserved. You can download ImageScaler 1.1 from WordPress.

The new version of JSSpamBlock doesn’t need a database. It uses sessions instead. I also cleaned up the code a bit and tested it with WordPress 2.3. You can download JSSpamBlock 2.0 from WordPress.

Update: Due to lack of time and interest (on my part), I am no longer maintaining JSSpamBlock or ImageScaler.

I just noticed a trackback from Brandon Cheketts about a PHP script he has released that lets you incorporate functionality similar to JSSpamBlock in any website, called bcSpamBlock. He also released a WordPress plugin based on JSSpamBlock that uses the script.

Although both plugins take advantage of the same limitation of spam bots – that they ignore JavaScript, the way they verify the codes is different. While JSSpamBlock uses a database, bcSpamBlock uses one-way encryption to verify the codes. Although this is a clever way to do it, I chose not to do it in JSSpamBlock for a reason: Storing the code in a database ensures that, even if a spammer were to write a bot targeting sites with JSSpamBlock, each comment posted would require the bot to parse another page from the server. Each code sent to the browser can only be used once. The problem with not using a database is that you have no way to verify that the codes sent from the browser are being used for the first time, and not the 10th.

Georg Kaindl made similar comments about the database being unnecessary, and I wrote a more lengthy response explaining why it was. He then came up with a clever solution – including the post’s ID in the hash. It still isn’t quite as secure as JSSpamBlock (I hate to use the word “secure” to describe what I admit is “security-by-inconvenience”, but I can’t think of another word that fits), but for all practical purposes it should be just as good. The only difference is that spammers could post multiple comments to any given post while only parsing the page once, while JSSpamBlock would require the page to be parsed once for each comment. The other advantage is that I do not have to rely on the JSSpamBlock user to come up with a unique salt in order for the protection to be secure. bcSpamBlock gets around this in a clever way, by using unchanging environment variables to generate the salt.

Another way to look at it is that generating a random code for each page view does not actually increase security (over using the same code for each page view) unless you use a database. So for a plugin that doesn’t use a database, this only gives the illusion of security. You might as well use the code “4422″ for everything, and it would be just as secure. This might sound bad, but any bot that is currently blocked by JSSpamBlock would be blocked by this as well. The only reason JSSpamBlock does more is to make it harder to write a bot that specifically targets JSSpamBlock. It may sound egotistical to suggest that a spammer would ever bother to write a bot specifically targeting the plugin, but for the extra cost (milliseconds of CPU time), I think it is worth making the plugin slightly more future-proof.

Update: Due to lack of time and interest (on my part), I am no longer maintaining JSSpamBlock or ImageScaler.

This blog has been a bit slow since I started school, partly because of the extra work but also partly because the “just for fun” projects I have been working on have gotten larger. At the same time, I hate to neglect my existing projects to start other ones. Given that, I was very lucky to have David Karlsson, who had released a modified version of Image Scaler, agree to incorporate the original functionality back in so that I could make it an official release. The biggest improvement is that you can now set a maximum width and height, which are used to resize all the images. So if your theme breaks with images over 600 pixels in width, Image Scaler is a graceful way to stop this from happening.

You can download Image Scaler 1.0 from WordPress, where it is hosted.

Update: Due to lack of time and interest (on my part), I am no longer maintaining JSSpamBlock or ImageScaler.

WordPress has a cool WYSIWIG editor that lets you easily resize images by dragging the corner around. The problem is that WordPress does not actually resize the image, it just tells the browser to display it smaller. This means that the full sized image is being sent to the browser, which makes the page load slower and take up more bandwidth. Additionally, most browsers are bad at resizing images, so the images look worse than if they were properly resized.

To get around this, I wrote a WordPress plugin called ImageScaler. I am still waiting for it to be approved by WordPress for hosting, so I have hosted it myself for now. It requires GD (almost all web hosts with PHP will have GD). It should work with PHP 4, but it has only been tested on PHP 5.

[Example removed]

Update: the plugin is now hosted by WordPress.