indessed roscivs

In computer networking, there are a variety of different terms used to describe the process of moving bits of data from one place to another. Today I’m going to compare three oft-used terms—throughput, latency, and jitter—through the antics of our usual friends, Bob and Alice.

Alice and Bob like to send each messages, but they live across town from each other, making communication a bit difficult. So, they hire various courier services to deliver their messages as fast as possible.

Throughput (often imprecisely called bandwidth) is a measure of how many messages can be sent in a particular time frame—for example, a hundred pages of messages per day. Unfortunately, this measure reveals much less information than you’d initially think. For example, two different courier services could both send one hundred pages of messages per day, but have vastly different models. The first might pick up a single package of a hundred pages in the morning, and deliver it in the evening. The second might only be able to carry a single page at a time, but can deliver each page in only five minutes. Nevertheless, if the second has exactly one hundred pick-up times per day, it has exactly the same throughput as the first—one hundred pages per day.

Latency is one key measure for distinguishing different services that have identical throughput. Also called “lag”, this measures how long it takes a courier to get from Alice to Bob. The latency of the first courier from above is one day; the second courier’s latency is only five minutes. Since they both have identical throughput, the second courier is definitely preferable to the first.

However, connections often differ in both latency and throughput. For example, imagine a courier that takes a day to deliver a single package of a thousand pages, compared to a courier who delivers only a hundred pages a day, but each page can be delivered in only a few minutes. Alice might prefer the first if she’s trying to send a library of books to Bob, but might prefer the second if she’s trying to carry on a conversation. Even though the throughput of the first is better, a conversation isn’t so much concerned about how many pages can be sent in a day—it’s more interested in how fast the responses can be sent back and forth.

This, of course, doesn’t mean that the throughput is completely unimportant. A courier that could send a message every thirty seconds but could only send one word at a time would probably not be preferable to one that sent a whole page every two minutes, unless only two or three words needed to be sent before requiring a response. The best connection is the lowest-latency one that can accommodate messages of approximately the same size that need to be sent without a response. But what if the time it takes the courier to deliver messages varies?

Jitter is a measure of the variation in latency. For example, one courier might be able to send one page every minute, and each page takes exactly one hour to reach its destination. Meanwhile, another courier can also send a page every minute, but each page can take anywhere from five minutes to several hours to be delivered. But if the average delivery time is also one hour, then both couriers have identical latency. But the second courier has much higher jitter than the first. When does this matter?

Let’s say that Alice is sending a novel to Bob. As soon as Bob gets a page, he starts reading—but, being a slow reader, it takes him an hour to finish a single page. If Alice uses the first courier, then Bob will be able to start reading the novel when the very first page arrives, and continue uninterrupted until he finishes the last page. As soon as he finishes one page, the courier arrives with the next one. If Alice uses the second courier, however, then sometimes the courier will arrive before he finishes a page (not a problem), and sometimes the courier will arrive quite a while after he finishes a page, forcing Bob to have to wait, annoyed, wondering how the story will continue.

Bob can still have an uninterrupted reading experience with the second courier; he just needs to exercise some patience before picking up that first page. If he waits a few hours before he starts reading, then future jitter doesn’t matter as much. After he finishes the first page, even if the next courier is a bit late, he still has the previously-delivered second page. As long as the courier averages at an hour page (Bob’s reading rate), he’ll be able to read cover to cover without any maddening gaps in the middle of the story.

But what if Bob reads faster than a page an hour? What if he reads a page every half an hour? Well, using either of the two couriers, he can simply wait for half the time required to deliver the entire novel before he starts reading. That way, when he finishes the first half of the book (that was delivered before he started), half of the second half will be delivered. Once he finishes that half, half of what’s remaining will have been delivered. He can continue in this same way until he finishes the penultimate leaf, just as the final page is being delivered, once again enjoying an uninterrupted reading experience.

My reasons for disliking the GPLv3 are simple: the requirements it introduces go above and beyond protection of Stallman’s original four freedoms, and attempt to control other things beyond the scope of these freedoms. For example, some corporations were taking copyleft software and putting it on hardware devices that would detect modifications to the software and refuse to run any modified code. To Stallman, this is a violation of Freedom 1, since adaptations of the program will not work on that device. However, you are perfectly free to run your adapations on another device or on a modifed device, so I consider Freedom 1 intact. The restrictions of the GPLv3 are attempting to enforce further freedoms above and beyond the original four—hardware-related freedoms, not software-related freedoms.

Furthermore, the GPLv3 has aggressive “patent retaliation” clauses.^[1] When originally developing the General Public License, Stallman was worried about the situation where someone might hold a software patent for a bit of Free Software that someone else wrote. This would in everyone losing the Four Freedoms (including the original author of the software!) except for the patent holder, who could do whatever they wanted with the software, including charging money to allow others to use it.

Stallman wisely placed a clause into the GPLv2 stating that “any patent must be licensed for everyone’s free use or not licensed at all.”^[2] In other words, if I have a software patent that covers something in Free Software that somebody else wrote, I am not allowed to distribute that software unless I provide a free license for anyone.

The GPLv3 goes much further than this, causing the distributor to “lose their license and any patent licenses that accompanied it.” For example, let’s say I’m a large software company with many patents, some of which could possibly apply to some Free Software that somebody else wrote, which I distribute. Meanwhile, a competing large software company writes some totally different software that obviously violates my patents, and I decide to sue them. The competing company decides to point out this piece of Free Software that I’m distributing, and claims that my patent applies to that piece of Free Software, and hence I must provide a patent license “for everyone’s free use or not at all.”

If the court decides that the patent in question does indeed apply to this piece of Free Software, then if the software is licensed under the GPLv2 I can simply stop distributing the software, pay copyright violation damages to the author of the software, and continue on with my lawsuit against my competitor. If, however, the software is licensed under the GPLv3, then if the courts decide that I “knowingly relied” on the patent license, then I automatically lose my patent and cannot enforce it against anyone, ever again.

This is exactly what Stallman wants, because he believes that software patents are a blight on humanity and should be abolished. I happen to agree on this point, but I disagree that such retaliatory features should be part of a general-purpose software license. This goes way beyond trying to protect the four freedoms for a particular piece of software. Instead, it uses the license as a weapon against an unrelated battle against software patents in general.

While I agree with the battle, and will fight the good fight, I do not choose to use the software I write as a weapon in that war. That is why I will not use the GPLv3.

In 1999, Richard Stallman penned an essay that is now known as The Free Software Definition. In it, he details four requirements, or “the four freedoms,” which are requisite for software to be considered “free” (as in liberty, not as in price):

• The freedom to run the program, for any purpose (freedom 0).
• The freedom to study how the program works, and adapt it to your needs (freedom 1).
• The freedom to redistribute copies so you can help your neighbor (freedom 2).
• The freedom to improve the program, and release your improvements to the public, so that the whole community benefits. (freedom 3).

(Access to the software’s source code is a prerequisite for freedoms 1 and 3.)

There are two types of Free Software licenses. The first type simply provides the recipient of these software with these four freedoms. The second type requires that anyone who distributes this software must do so with a license that guarantees the four freedoms. The second type is called “copyleft” (a pun on “copyright”).

The difference is easy to explain. In the 1990s, Microsoft took the source code to some Free Software called BSD, and copied some of that code into Windows in order to allow Windows to connect to the Internet. But when Microsoft distributes Windows, they do not provide the recipient of Windows with those four freedoms. This is a license of the first kind.

In 2002, Apple took the source code to some Free Software called KHTML, and copied some of that code in order to make Safari, the default web browser on Apple systems. When Apple distributes Safari, they are required to provide those four freedoms for the part of the KHTML code they copied. In other words, they provide the source code, and allow everyone the freedom to do with that source code the things listed above.

I really like the Four Freedoms, and I distribute much of the software I write on my own time under a copyleft license that Richard Stallman wrote, called the General Public License (or GPL) version 2.0. However, on June 29th, Richard Stallman released a new version of this license, the GPL version 3.0, which he will now release all his software under. This license is much longer, much more complex, and has many more requirements than version 2.0, and many people in the Free Software community are questioning the wisdom of the license—including me. I will likely not use the license for any code I write myself, and will be very hesitant to contribute source code to GPLv3 projects.

In my next post, I’ll talk about my reasons why.

Once upon a time, there was an email program named PINE. Wikipedia says that its recursive acronym, “Pine Is Not Elm” (another early email program) has been disavowed by the creator the application, saying that it never stood for that, but it remains my favorite recursive acronym to this date.

PINE was created around 1990 by the University of Washington, back before webmail was popular and even before email clients like Eudora, Juno, or Outlook became popular. It was completely text-only, and could be used on one of those old computer terminals that didn’t even have a processor, that was simply one of hundreds of screens into a massive computing framework called Unix. My first experience with email was using a terminal emulator, connecting to a Unix-like computer called VAX at a local medical university. The program they used for email was PINE.

Over the years, I’ve used a lot of different email programs. But I seem to always come back to PINE. The reason is partially due to its simplicity, but also due to the flexibility of being able to run it in a terminal emulator. That means that, anywhere I am in the world, I can ssh into my home computer and check my email over an encrypted connection, without having to use a web browser or ever click the mouse. For such a text-centric application as email, freedom from the mouse is a godsend.

Unfortunately, PINE is not Free Software. It doesn’t cost any money, but you can’t modify it or redistribute it in some cases. Over the years, development has lagged considerably, with some modern features (such as Unicode support) being left out. But today, I discovered that the University of Washington has been developing a replacement for PINE, called Alpine. Fully Open Source, and fully Free, this new program, once completed, should provide PINE fanatics like me with a fully-featured email client that will stay up to date for many years to come. I’ve already signed up for the alpha mailing list, and I’ll keep you posted on their progress.

I’m taking the Alpine slide!

An oft-repeated canard is how the Qwerty keyboard that we use today was intended to slow down typists, and that the only reason we don’t switch to something vastly more efficient is because everyone’s already using Qwerty keyboards. While it is true that the Qwerty keyboard gets its layout due to typewriter jams that no longer exist in the computer era, the changes weren’t intended to slow people down, but rather, to move oft-used pairs of letters apart from each other on the keyboard. Some people even claim that this improves the efficiency of Qwerty typers as compared to random (or pure alphabetical) layouts.

When confronted with studies calling into question the ability of Dvorak typists to significantly outperform Qwerty typists, Dvorak users often instead emphasize that most typists switch to Dvorak for ergonomic reasons, stating that their carpal tunnel symptoms went away after switching. This may be true, although I’d be interested to see studies that question whether the symptoms go away because of the layout in particular, or if switching to any arbitrary non-Qwerty layout improves their condition. If the latter, it may turn out that if everyone were to switch to Dvorak and use it from birth, then switching to Qwerty later on in life could reduce carpal tunnel symptoms as well! Or, of course, Dvorak could end up being intrinsically better, but I’d love to see some hard research on the topic.

What I’m mostly concerned about, though, is typing speed. If I get a significant boost out of an alternate keyboard layout, I’d be tempted to make the switch. Dvorak doesn’t seem like a likely candidate for me, although Developer’s Dvorak, which is similar to Dvorak but specially suited for the arcane symbols that software developers type day in and day out, seems appealing. But how can such a thing be measured?

Obviously home-row keys are the easiest to hit. A keyboard that keeps me on the home row most of the time will win out, all other things equal. But the “alternating hands” thing is important too—if I’m on the home row but I have to hit a bunch of keys with the same hand, that’s likely to feel less efficient than alternating back and forth but adding in some above-home-row keys. In fact, I’d say that for me personally, keys above the home row are just as easy or easier to hit as home row keys.

So if I were analyzing a string of text to see how difficult or easy it would be to type, home row and above-home-row would get the easiest rating. Typing two consecutive characters with the same hand would get a slight penalty; two characters with the same finger a steeper penalty. Anything that requires the row below home or the “number” row would get a steep penalty as well. “Finger travel distance,” a concept many use to measure efficiency, doesn’t really affect my typing so I wouldn’t use it as a concept in and of itself.

What would be interesting is to run a key-logging program that kept track of all the keystrokes I made throughout the day, what order, and at what time I made them. Then another program could take that information as input and check against various keyboard layouts to see which layout is most efficient (given my above “rules”) for a typical day of typing. This Dvorak site has a similar “efficiency”-checking program that you can use on any arbitrary block of text.

Everything—that is to say, everything—on a computer is eventually, at the lowest level, turned into zeros and ones. Every web page, every mp3, every image, every movie, every keystroke, every video game—at the end, it’s all just zeros and ones. Sometimes the path from those zeros and ones (bits, in computer terminology) to the final product is a long and circuitous path, but other times it’s a fairly simple one.

Because everything ends up as zeros and ones, people who deal with bits on a regular basis needed an easy way to represent very long sequences of those zeros and ones. For example,

0100100001100101011011000110110001101111

is a more than a little cumbersome. If you had to copy down that sequence of bits onto a piece of paper, you might have to check several times to make sure you’d copied it accurately.

The first thing we tend to do to make things easier is to put spaces in between groups of four (much like people put commas every third digit to make 1,000,000 easier to read).

0100 1000 0110 0101 0110 1100 0110 1100 0110 1111

Already that’s a great deal easier to take in at a glance. Now, there are only a limited number of four-bit patterns. For instance, the pattern “0110” appears several times in the above seequence. So we’ve developed a set of symbols, where each symbol represents an entire four-bit pattern. For example, we could have some funky symbol like µ stand for “0110”, and a different funky symbol for “0101”, etc. Instead of using funky symbols, however, we instead decided (in the long tradition of using already-existing symbols to represent something completely different) to use the numbers 0 through 9 and the letters A through F. This gives us a total of sixteen symbols, which map perfectly to the sixteen possible four-bit patterns, exactly as follows:

0000    0	1000    8
0001    1	1001    9
0010    2	1010    A
0011    3	1011    B
0100    4	1100    C
0101    5	1101    D
0110    6	1110    E
0111    7	1111    F

This means that we can represent that unwieldy sequence of zeros and ones with ten simple characters:

4 8 6 5 6 C 6 C 6 F

Because there are sixteen symbols, we call this system of representing zeros and ones hexadecimal. In practice, pairs of hexadecimal numbers are usually grouped together, which makes it easier to read:

48 65 6C 6C 6F

This is much easier to read, remember, and copy than our original blob of forty zeros and ones.

Also, sometimes it can be confusing whether, when we write “48”, we’re talking about the hexadecimal numbers representing “0100 1000” or whether we’re talking about the decimal number “48”. To help eliminate this confusion, we typically prefix hexadecimal numbers with “\x” or “0x”. For example, 0x48 represents “0100 1000”, and 0x6C represents “0110 1100”.

Tomorrow I’ll talk about some of the specific ways things on your computer are reduced to zeros and ones—like this post, for instance!

There is a curious dilemma in universities today with regard to the field of computer science. Historically, computer science was part of the mathematics department. Many of the foundational concepts of computers—boolean logic, algorithms, formal systems, functions, lambda calculus—these were all purely theoretical concepts residing squarely inside the math department before computers came along. Furthermore, the earliest computers were primarily used for mathemetical calculations (that’s why they’re called computers, after all—a term which previously was reserved for humans who crunched numbers for a living), either by mathematicians or physicists. So it was only natural that, as computers became part of the modern university, classes on computer theory would be part of the math department.

Since those early years, computers have become so popular and such a force of their own that most universities have a separate “computer science” department (although typically still conjoined with the mathematics department in some way). As computers have matured, non-mathematical uses of them have grown increasingly common. The art of programming, with its roots in pure mathematics, looks much less like mere formulas and equations than it once did. And, finally, those who are majoring in computer science these days typically go on to be software developers—not theoretical mathematicians. As a result of all these factors, the face of computer science departments has changed radically.

Many people lament the passing of the traditional “computer science” discipline, full of mathematicians (not programmers) and rich with theory and symbols (not software development models). Where is the computer science of Knuth, or Dijkstra, who allegedly said, “Computer science is no more about computers than astronomy is about telescopes”? Has it died, pushed out of our universities in the increasing trend towards university-as-trade-school?

I don’t think so. In many ways, the discipline of the early computer science pioneers has been sucked wholly back into the math department. Many of the same mathematical concepts present in those early computers are still heavily studied and examined in the math department, with computers as a useful resource, not the focus—just like computer science once was. It’s just not called “computer science” any more.

Unfortunately, I think a result of this paradigm shift is that the brilliant mathematicians are ceasing to have as strong an effect on the software development world as they once did. There’s not as much cross-culture as there was when the two disciplines were more closely interrelated.

Another problem is that, after traditional computer science was reabsorbed by the math department, nobody has been able to agree on what the “new” computer science discipline should be. The mixed nature of a typical computer science department faculty—made up of both “old-school” theory-heavy, math-heavy powerhouses as well as people with years of real-world software development experience from industry—just exacerbates the problem.

Some believe that the department should prepare its students for jobs in software development, since that’s where a significant percentage of them end up. Others think that the department should focus on theory, and that development-centric classes belong in trade schools, or at least a different department. As Joel Spolsky (author of several books on software development) puts it in characteristically tongue-in-cheek fashion:

[E]lite schools think that teaching practical skills is better left to the technical-vocational institutes and the prison rehabilitation programs. You can learn mere programming anywhere. We are Yale University, and we Mold Future World Leaders. You think your $160,000 tuition entititles you to learn about while loops? What do you think this is, some fly-by-night Java seminar at the Airport Marriott? Pshaw.

So universities are typically stuck in this middle-world of half mathematics, half software development. Students who want the former struggle through the programming-heavy classes of computer architecture and compilers, while those who are interested in the latter have to wade through theory-heavy classes like automata theory and “database” classes that have very little real-world utility.

So what do I think should happen? I think there should be a theory-centric track fully inside the math department, and a development-centric track (perhaps called “software engineering”, as many universities are leaning towards) full of programming-heavy courses on software design, development methodologies, and code maintenance. The development-centric track shouldn’t be simply “learn how to program” nor “learn what development tools are popular today”—I do agree that such tasks should be left to trade schools and the like. But there’s a lot of university-appropriate knowledge that has been applicable for decades and will be applicable for decades to come that is specific to software development.

I believe this is the world we’re heading towards, but as always, the transition period will be one messy, bumpy ride.

The reason I brought up the topic of formal grammars yesterday is that John Backus, a pioneer in the field of computer science and creator of the first high-level programming language (FORTRAN), passed away last Saturday. He’s probably known best for Backus-Naur Form (BNF), a formal notation for describing formal grammars. In BNF, my example grammar from yesterday would look like this:

<S> ::= <N> <V> <N>
<V> ::= saw | kissed
<N> ::= Bob | Jill

The major differences are the use of “::=” instead of an arrow, and the use of a vertical pipe “|” as sort of a shorthand to compress multiple production rules into one.

Not only is BNF a simple and standard way of representing grammars, but there are computer programs that will take as input a grammar in BNF, and automatically generate code that will parse (generate the derivation rules) for any given string. This turns out to be very convenient, since nearly all computer languages can be described in BNF. (Like Java, for example.)

Now, not every grammar is as simple as my example grammar, which could only generate eight unique strings. Nearly every formal grammar that is remotely interesting can generate an infinite number of strings. For example, here’s another very simple grammar in BNF:

<S> ::= <S> <S> | a

This grammar can generate strings like, “a”, or “a a”, or “a a a”, and so on. It can generate an infinite number of strings (or you can say the language of this grammar contains an infinite number of strings), but obviously it doesn’t contain every possible string. “a b a”, for example, is not in this language.

Chomsky, when describing formal grammars and formal languages, separated them out into four distinct categories of complexity, also called the Chomsky Hierarchy. The very simplest kind is called a “regular grammar”. Regular grammars are only allowed to have two types of rules:

<X> ::= z
<X> ::= <Y> z

In other words, a rule can either consist of a single nonterminal on the left, and a single terminal on the right, or a single nonterminal on the left, and a single nonterminal on the right followed by a single terminal. The grammar I listed above does not qualify, since it has a rule with two nonterminals on the right-hand side. However, the language it describes (strings of “a”s) can be described by a regular grammar.

Would anyone care to try their hand at finding it?

Noam Chomsky is an interesting fellow. Most who have heard of him are surprised to hear that he is one of the most influential linguists of the 20th century. (Linguists, on the other hand, are often surprised to hear that he is widely known as a political activist.) But his contributions to the field of linguistics are wide and varied. Even more curious is the fact that some of these contributions have helped shaped the field of computer science.

Chomsky, in the 1960s, came up with a theory called transformational grammar, maintaining that humans have some sort of innate way of telling whether a given sentence is grammatical or ungrammatical, and that foundationally, this sense is common across all humans no matter what the language. As part of this idea, Chomsky also discussed formal grammars, which are mathematically precise ways of describing a “language”. Although Chomsky believed that formal grammars were unable to fully express the intricacies of human languages, his formal grammar theory has become the foundation of modern computer languages.

The central idea is that of a generative grammar: a set of rules for transforming strings. Chomsky was the first to formalize this idea back in the 50s. Under the formal definition, a grammar has exactly four pieces: a set of “nonterminal symbols”, a set of “terminal symbols”, a list of “production rules”, and a single “starting symbol” from the set of nonterminals. Let’s try a concrete example.

The set of nonterminals: <S>, <N>, <V>. The set of terminals: Bob, Jill, saw, kissed. The starting symbol: <S>. As for the production rules, they must be of the format: X → Y. My example grammar has only five production rules:

1. <S> → <N> <V> <N>
2. <V> → saw
3. <V> → kissed
4. <N> → Bob
5. <N> → Jill

What a production rule means is that if you have something on the left-hand side of a rule anywhere in your string, you can, if you so desire, change it to the corresponding bit on the right. For example, if I have the string “<N> <N> <N>” I can, using rule #4, change my string to become “<N> Bob <N>”. (I also could have changed any of the other two symbols using rule #4, or I could have used rule #5 instead.)

You can look at a formal grammar like this as something of a game: given the starting symbol and using production rules, what strings of terminals are possible? Here’s one possible string, with its full derivation:

1. <S> (starting symbol)
2. <N> <V> <N> (rule #1)
3. <N> <V> Bob (rule #4)
4. <N> saw Bob (rule #2)
5. Jill saw Bob (rule #5)

Now my string contains all terminal symbols, so my use of production rules must come to an end. (Production rules may have anything on the right-hand side, but the left-hand side must only contain nonterminals—which is where the name “terminals” comes from, because once your string contains only terminals, it is finished.)Another variety of the game consists of starting with a given string of terminals, and attempting to figure out the proper derivation for it. For example, can you give the derivation for “Bob kissed Jill”? How about “Bob saw”? Or “Jill kissed Jill”? (Hint: one of those strings has no valid derivation.)

Strings with a valid derivation—there’s some way to get to them via the starting symbol—are said to be “in the language described by the grammar”. Strings without a valid derivation—no matter what rules you apply, you can never get to them from the starting symbol—are said to “not exist in the language described by the grammar”. A “formal language,” then, is the list of all strings that a generative grammar can produce.

How many different strings are in the language produced by my example grammar? First one to post them all gets a cookie!

How much do you know about world-renowned cryptographer and security expert Bruce Schneier? Did you know that Bruce Schneier’s discrete logarithms are uncountable and continuous? Or did you know that Bruce Schneier writes his books and essays by generating random alphanumeric text of an appropriate length and then decrypting it?

These and more wondrous, astounding, and supremely geeky facts about Bruce Schneier can be found at geekz.co.uk/schneierfacts.