CodeWords

Transition to New Site

2011-10-26T23:55:00.000-06:00

This blog is now being retired in favor of the notes on my new site, which has an explanation of the transition. This blog will remain but will no longer be updated.

Steve Jobs, Rest in Peace

2011-10-05T22:13:00.001-06:00

Today a great entrepreneur, one of the great American capitalists, Steve Jobs, passed away at the rather young age of 56. As others have said, we are all a bit poorer for it.

I didn't always agree with his style, I wasn't always a fan of his company's products, and I certainly didn't like the personality cult that surrounded him, but I have great respect for the man who believed in what he did, thought big, sought to empower people, and did it with style and aesthetics. He is an inspiration to us all.

Finding Files with PowerShell, Part 2

2011-08-29T11:12:00.004-06:00

This version (see Finding Files with PowerShell) gives the full path of the items:

Finding Files with PowerShell

2011-08-16T14:22:00.003-06:00

I miss the UNIX find command in Windows. I could get it with Cygwin or GNUWin32, but that requires littering my machine with extra stuff. So, PowerShell to the rescue:

Reddit's Unique Web Server

2011-07-15T22:44:00.000-06:00

Reddit has quite a unique web server.

How Likely Are You to Be Dealt a Royal Flush?

2011-06-20T08:12:00.006-06:00

In the game of poker, you have a royal flush when you have a 10, J, Q, K, and A all of the same suit. Assuming a uniform random distribution of cards in the deck, what is the probability of being dealt a royal flush?

A royal flush consists of a certain five cards of the same suit. Assume we are dealt one of these cards. Then the suit is determined, and we now need the remaining four cards of that suit. So, let's take the probability of being dealt one of the certain five cards (10, J, Q, K, A) of any suit. Since there are five such cards per suit, and there are four suits (the set of suits is $ \{ \diamondsuit, \heartsuit, \clubsuit, \spadesuit \} $), then we can get any one of those cards to start building a royal flush. Therefore, the probability of getting a starting card is \[ P(\text{starting card}) = \frac{20}{52}. \] Once we have a starting card of a certain suit, our suit is restricted. That is, we may only get the remaining four cards from the same suit as our starting card. Then the probability of getting one of the four cards from the same suit is \[ P(\text{one of the four from the same suit}) = \frac{4}{51}. \] Likewise, after we get the second card, there are three left to get, so the probabilities are $ 3/50 $, then $ 2/49 $, and then $ 1/48 $. What, then, is the probability that we will get all of the necessary cards? It is the product of all these probabilities: \[ P(\text{all}) = \frac{20}{52} \cdot \frac{4}{51} \cdot \frac{3}{50} \cdot \frac{2}{49} \cdot \frac{1}{48} = \frac{1}{649\,740} = 1.539\ldots \times 10^{-6} = 0.000\,153\,9\ldots \%. \] Not very good odds.

Calculating the Number of Trailing Zeros in a Factorial

2011-06-18T21:54:00.007-06:00

The factorial function, denoted $ n! $, where $ n \in \mathbb{Z}^* $, is defined as follows: \[ n! = \begin{cases} 1 & \text{if $n = 0$,} \\ n(n - 1)! & \text{otherwise}. \end{cases} \] In the case of $ n = 10 $, $ 10! = 3\,628\,800 $. Note that that value has two trailing zeros. When $ n = 20 $, $ 20! = 2\,432\,902\,008\,176\,640\,000 $ and has four trailing zeros. Can we devise an algorithm to determine how many trailing zeroes there are in $ n! $ without calculating $ n! $?

Let us define a function $ z : \mathbb{N} \to \mathbb{N} $ that accepts an argument $ n $ that yields the number of trailing zeros in $ n! $. So, using our two examples above, we know that $ z(10) = 2 $ and $ z(20) = 4 $. Now, what is $ z(100) $?

An integer $ a $ has $ k $ trailing zeros iff $ a = b \cdot 10^k $ for some integer $ b $. Now, the prime factors of $ 10 $ are $ 2 $ and $ 5 $. So, what if we consider the prime factors of each factor in a factorial product? For example, consider the first six terms (after $ 1 $) of $ 100! $ and their prime factors. We omit $ 1 $ because of its idempotence: \[ \begin{align} 2 &= 2 \\ 3 &= 3 \\ 4 &= 2^2 \\ 5 &= 5 \\ 6 &= 2 \cdot 3 \\ 7 &= 7 \end{align} \] We see that $ 7! $ contains one $ 5 $ and (more than) one $ 2 $. Therefore, $ 7! $ contains a factor of $ 10 $, so we should expect there to be one trailing zero in $ 7! $. And we see that $ 7! = 5040 $, which does indeed have one trailing zero. This suggests that we could, for any integer $ n $ in $ n! $, cycle through the integers from $ 2 $ to $ n $, finding the prime factorization of each integer, and counting pairs of $ 2 $ and $ 5 $ that we find.

You might have noticed from our example of $ 7! $ that there are four $ 2 $s and only one $ 5 $. Consider that there are $ n/2 $ even factors in $ n! $—that is, every other integer factor of $ n! $, starting at $2$, is even. So there are $ n/2 $ even factors. Each of these has at least one $ 2 $ in its prime factorization, and many of them have more than one. Now consider how many factors of $ 5 $ there are in $ n! $: there are, in fact, $ n / 5 $. So, we can see that, for every $ 5 $ we find in $ n! $, there is a $ 2 $ we can match with it. This suggests that we only need count the $ 5 $s and not the pairs of $ 2 $ and $ 5 $.

This now suggests an algorithm, presented here in Java:

Using this algorithm, we find that $ z(100) = 24 $.

Adobe Reader's Big Problem

2011-06-10T16:27:00.000-06:00

I use PDFs often. Nothing excels them in fidelity of design to documents for which design is important. The Adobe Reader, in its 5.5 days and earlier, was the standard PDF reader of choice. But with version 6, serious bloat occurred, and Adobe Reader is only now, in its latest versions, recovering from that problem. I have a new problem with Adobe Reader, though. Take a look:

This is a document that appears to be made of scanned images placed in text pages, produced by $ \mathrm{\TeX} $. Note how the scanned images appear as completely useless gray boxes. Here is how the document should look, and does look, in other PDF viewers:

I have searched and searched on this matter, but the results are few and old, and whenever I try to employ a solution I do find, it doesn't work.

Generate a Zero-Valued UUID

2011-06-06T16:51:00.001-06:00

Say you want a UUID of 00000000-0000-0000-0000-000000000000, but you just want to make one fast, without having to find out the number and grouping of digits. Here's a way to do it:

The Beauty of Scheme

2011-05-27T11:14:00.001-06:00

Bertrand Russell once noted that

Mathematics, rightly viewed, possesses not only truth, but supreme beauty—a beauty cold and austere, like that of sculpture, without appeal to any part of our weaker nature, without the gorgeous trappings of painting or music, yet sublimely pure, and capable of a stern perfection such as only the greatest art can show. The true spirit of delight, the exaltation, the sense of being more than Man, which is the touchstone of the highest excellence, is to be found in mathematics as surely as poetry.

I think much the same can be said of code, especially code written in certain languages. There is something so elegantly simple and beautiful about Scheme (and Racket), for example, that shares the same aesthetics of mathematics.

A Human-Usable URL Parser for Python

2011-05-24T16:44:00.002-06:00

Yes, there is the urlparse module in Python 2.7 and the urllib.parse function in Python 3, but each of them just creates a 6-tuple of URL parts, and it's up to you to know that the query part, for example, is at position 4.

So here's a neat little wrapper around that functionality which gives named fields to each part:

So, to get the query part, you just do parsed_url.query instead of parsed_url[4].

How I Saved My Friends Lots of Money

2011-05-19T22:00:00.001-06:00

Last night I got a phone call from one of my neighbors. She told me that she needed to use some courseware for a class at her university and said that she was unable to use it, and that she was told by someone that she needed to upgrade Windows to use it. They further said that, since a Windows license costs on the order of $200, she should just buy a new laptop. Now, this courseware is a web application—just a web site—yet she was told to get a new laptop. Naturally, my BS-meter went off, and I asked if I could come take a look.

I went over and looked, and saw that the real problem was not that the web site didn’t work—it worked just fine—but that the course documents were Microsoft Word .docx files. Not having Office or any other office apps, she had nothing with which to open them. So, I told her the nature of the problem and installed LibreOffice. Problem solved for $0.

The moral of this story? These points:

“Computer literacy,” so called, is woefully scarce in our society. I don’t really fault my neighbor so much as the yahoo she spoke with who told her such outrageous nonsense.
Professors should make their course documents available as PDFs, which is the proper interchange format for important documents. (What’s interesting about this is that Microsoft Word 2007 and 2010, which use the .docx format natively, make producing PDFs from Word easier than ever before.)

Making System.Data.SQLite Work in an NServiceBus Endpoint

2011-01-28T14:01:00.000-07:00

Today a colleague and I worked on getting an an NServiceBus endpoint in a .NET 4.0 project that referenced System.Data.SQLite to work properly. It turns out that this is not as straightforward as it may seem.

The System.Data.SQLite binaries are targeted for the .NET 2.0 runtime. When referencing a .NET 2.0 mixed mode assembly in a .NET 4.0 project, additional configuration is required:

OK, that's fine. But when running an NServiceBus endpoint in the NServiceBus.Host.exe executable, it seems that this setting in App.config does not get applied in the context of NServiceBus.Host.exe. So, to get this to work, we had to turn the NServiceBus endpoint into a console application with a Main method that used reflection to invoke the Main method of NServiceBus.Host.exe. Doing this enables the above setting to be applied in the context of NServiceBus.Host.exe.

It took us the better part of a day to figure this out, so I'm memorializing it here for (my own) future reference.

Generate Test Files From the Command Line

2011-01-27T09:07:00.000-07:00

Note to self: I had to generate some files quickly to test the behavior of the .NET FileSystemWatcher. This little bash script will create 6 zero-filled files of of size $ 2 \times 10^i $ KiB, where $ i \in \{0, 1, \dots, 5\} $.

Retrying Code Execution

2011-01-11T07:39:00.000-07:00

I have a bit of code I'm working on at work that makes use of an HTTP endpoint to notify a legacy system of certain events. Because the network is not reliable, we have to handle the case when the network may be down. In this situation, it means to try again a few times, after which the processing request goes into an error queue, where it can be handled manually. So, I started out with something like this:

This calls the HTTP endpoint up to five times. If one of those times succeeds, it returns the result and stops trying. If it gets to the sixth time, it gives up.

Now, in my project, I have several of these types of calls to make. Much of the above code, namely the exception handling and flow control stuff, is common to all of them. So, using some functional .NET and an extension method, we can do this:

This will attempt to execute and return the value of func up to times times, and give up after that. With this extension method, we can now put our endpoint-calling code in a Func<int> and tell it to try to call the endpoint up to five times, like this: Now, is this the best way to do this? Maybe; maybe not. It's just something I've been toying around with in my attempts to eliminate duplication of the aforementioned ugly flow control code. I'll have to walk around in these shoes for a while and see whether I like them.

IE Doesn't Support the trim() Method(!)

2010-12-03T04:56:00.000-07:00

Here's yet another shocker from the half-baked world of Internet Explorer. Start up IE 8. Press F12 or start the Developer Tools. Then, click the Script tab and then the Console tab on the right pane. At the command line at the bottom, type
[sourcecode language="javascript"]
" this has padded whitespace ".trim();
[/sourcecode]
press Enter, and behold:

Insane! Thankfully, the folks at jQuery have taken care of this.

The ASP.NET MVC Request-Handling Pipeline

2010-12-02T03:41:00.000-07:00

[scribd id=44539131 key=key-mb5rsfz5wd7wk3u95t1 mode=list]

Java as DSL

2010-11-30T03:06:00.000-07:00

I love it:

http://twitter.com/#!/avalanche123/status/7062890318143488

Generate a Version 4 UUID With Javascript

2010-11-22T04:05:00.000-07:00

[sourcecode language="javascript"]
function uuid4() {
return "xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx"
.replace(/[xy]/g, function (c) {
var r = Math.random() * 16 | 0, v = c == "x" ? r : r & 0x3 | 0x8;
return v.toString(16);
});
}
[/sourcecode]

From Mvc2.TaskUI by Jonathan Oliver.

Roll Your Own Map/Reduce in Javascript

2010-11-18T02:31:00.000-07:00

I’ve been working on a very Javascript-heavy UI that allows the user to manipulate collections of objects. To ease the task of manipulation, I created a few methods on Array.prototype, which I rolled into a file I call iterable.js:

[sourcecode language="javascript"]
var Iterable = {
func: {
predicate: {
TRUE: function (x) { return true; }
}
}
};

Array.prototype.forEach = function (fn) {
for (var i = 0; i < this.length; i++)
fn(this[i]);
};

Array.prototype.filter = function (pred) {
var result = [];
this.forEach(function (x) {
if (pred(x))
result.push(x);
});

return result;
};

Array.prototype.distinct = function () {
var result = [];
this.forEach(function (x) {
if (!result.any(function (y) { return y == x; }))
result.push(x);
});

return result;
};

Array.prototype.any = function (pred) {
pred = pred || Iterable.func.predicate.TRUE;

for (var i = 0; i < this.length; i++)
if (pred(this[i]))
return true;

return false;
};

Array.prototype.indexOf = function (expr) {
if (!(expr instanceof Function))
expr = function (x) { return x == expr; };

for (var i = 0; i < this.length; i++)
if (expr(this[i]))
return i;

return -1;
};

Array.prototype.singleOrNull = function (pred) {
var filtered = this.filter(pred);
if (filtered.length == 0)
return null;
if (filtered.length > 1)
throw "More than one element returned.";

return filtered[0];
};

Array.prototype.map = function (fn) {
var mapped = [];
this.forEach(function (x) { mapped.push(fn(x)); });
return mapped;
};

Array.prototype.groupBy = function (sel) {
var groups = [];

this.forEach(function (x) {
var group = groups.singleOrNull(function (y) { return y.key == sel(x); });
if (!group)
groups.push({ key: sel(x), members: [x] });
else
group.members.push(x);
});

return groups;
};
[/sourcecode]

Note that this not particularly complete; for example, you’ll see that there is no implementation of a reduce function. It’s not here because I have not needed it in my project yet, nor am I likely to. But it would be easy to implement:

[sourcecode language="javascript"]
Array.prototype.reduce = function (fn) {
   if (this.length == 1)
   return this[0];
   return fn(this[0], this.slice(1).reduce(fn));
};
[/sourcecode]

Now, I’m aware of Underscore and others, so why did I do this? For two reasons, mainly: I only needed a subset of the functions that those libraries offer, and besides, it was fun.

The .Net HashSet

2010-06-08T14:48:00.000-06:00

I’m relatively new to .Net, coming from the world of Java. Now, the documentation of the HashSet class says, “The HashSet(Of T) class provides high performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order.” Fair enough, except that the HashSet class preserves insertion order. Furthermore, set1.Equals(set2) will return false even when the two sets contain the same elements but in a different insertion order.

This doesn’t sound like set semantics to me. Fortunately, you can remedy this with a simple extension method and LINQ:

[sourcecode language="csharp"]
public static bool SetEquals<T>(this HashSet<T> me, HashSet<T> other)
{
return me.All(other.Contains) && other.All(me.Contains);
}
[/sourcecode]

As you can see, the LINQ expression on line 3 is equivalent to the definition of set equality. Of course, the parameters to this method could be of type ICollection<T> or something for more genericity.

Endless Code

2010-03-08T15:20:00.000-07:00

Bad Code from unclebob on Vimeo:

[vimeo 9981123]

FYI: The piece heard in this video is Atmosphères by György Sándor Ligeti, who intended the listener “to become lost in the depth of the texture and tone and become completely oblivious to the passage of time,” according to Wikipedia.

Feed Reader Problems

2010-03-05T06:02:00.000-07:00

Garrett LeSage says that feed readers are not smart enough, and I agree. One of the problems I face is that not all feeds have the same "velocity," which I define as "number of posts per unit time." For example, I have a group of feeds in Google Reader that I read for work and professional development. However, I also read DZone.com and want to add its feeds to the group, but I don't, because its velocity is far greater than the velocities of any of the other feeds in the group. The result, of course, is that DZone dominates the group, and the posts from the other feeds get "crowded out." A feed reader should take into account how often I read the posts of a given feed, determine what those posts I read are about, and then filter accordingly (while offering me the opportunity to see the whole, unfiltered feed if I so choose). It should also offer suggestions of new feeds that I may find interesting.

No feed reader currently meets my needs---and it's not because there is a dearth of feed readers out there. Some come somewhat close, but none have yet done it right.

Sapir-Whorf in Software Engineering

2010-01-19T09:20:00.000-07:00

What follows is a short essay I wrote for my software engineering class last semester.

I have many interests; one of them is linguistics. I first heard of the Sapir-Whorf hypothesis, also called the linguistic relativity principle, some years ago and it caught my interest. Despite the many objections and resistance brought against it, I have always found it to be rather compelling.

It seems obvious to me that the language we use to describe and interface with the world should shape our cognition about the world. Many studies have been done which show this in natural languages. But it seems that there have been fewer studies about this principle in programming languages, especially in software engineering.

I remember when I took CS 330 about a year ago. CS 330 is a course on programming languages, and the language of the class is Scheme, a cousin of Lisp. Scheme is a functional programming language, which is to say that, in Scheme, functions are first-class objects, just like any other data type. This was the first time I was ever really exposed to the functional paradigm (although I saw a little of it before in Javascript), and it had a rather profound effect on my skills as a software developer. For when we studied Scheme and used it to investigate the principles of programming languages, my thinking about programming changed; it expanded into new realms, and I could see things that I had never really seen before.

One of the things studying Scheme did for me was to get me interested in programming languages and related concepts. But more immediately, it added to my cognitive landscape the idea of functional programming. Not long after I began to learn Scheme did I come to see the benefits of functional programming in other languages, like Python, which I learned has a "lambda" keyword like Scheme. Soon I began to incorporate functional principles in my work outside that class, in other classes, and so on. I was writing software in a way that I would not have done before without having been exposed to this new paradigm.

And thus it is with software engineering. The long use of the same tools, practices, patterns, languages, etc. often constrain our thinking and deprive us from creating elegant, simple solutions to problems. While I am a firm believer in process---process in the sense that there must be some means by which a software development organization develops its software, and that it should be at least somewhat structured, I also acknowledge the fact that adhering too rigidly to process and procedure can stifle creativity and ossify the mentality of an organization. This is to be avoided, since software development is a creative enterprise; it is by no means formulaic.

We software engineers, programmers, or whatever we like to be called, are, in a sense, linguists. We learn and use languages all the time. As such, we are subject to linguistic principles. Despite the objections of Chomsky and others, I have always found Sapir-Whorf to be true---so true, in fact, that it's a self-evident proposition.

Build Firebug Into Firefox

2009-02-27T05:49:00.000-07:00

The other day I came to a startling realization: that all of the major web browsers—except Firefox—have Firebug-like developer tools built into them. Specifically, these browsers:

Internet Explorer(!) 7 and 8

Safari

Google Chrome

Opera

This is clearly the way things are going. Firebug and similar tools are so critical to developing web apps now that I think the Mozilla Foundation ought to acquire Firebug and build it into Firefox. I'd accept making it an option on installation, defaulted to "off," so that non-developers needn't deal with it.