Expressiveness

What is expressiveness in a programming language? When I began thinking about this, I came up with a lot of different answers. I am not going to try to tell you what the right answer is, because I don't know. I suspect there isn't one, but the candidates are interesting.

The number of programs in the language.

This definition is typically preferred by the argument that expressiveness is not a meaningful quality of programming languages, because all Turing-complete languages are capable of expressing exactly the same set of programs. However, we can bring a lot of nuance into the situation by noting that:

• Real computers aren't actually Turing machines
• Not all programming languages are Turing-complete

The number of unique programs in the language.

This is the definition preferred by somebody who is really ambitious and wants to express lots of useful programs. So, if a language L has ten million ways to print "Hello, world!" but can't do anything else, such a person would not call it expressive. This starts to get at one of the problems of defining expressiveness: we need to know who is doing the expressing, what they might want to express, and how they go about choosing what to express from among the many possibilities. Language L might be a great productivity enhancer at MegaHelloWorldCorp.

One problem with this definition is that it might be equivalent to the previous definition, which we have already grown bored of. Whether or not it is equivalent depends on what you mean by "a language" and what you mean by "unique". What you probably mean by "unique" is not "the same string" but "the same in effect". So you are probably safe.

The number of different ways to write the same program.

This definition says that programs are like poems. The proponent of this argument already has a particular program in mind. (The poet has an idea to convey.) The difficult thing is not finding the program you want to implement, but finding the most beautiful way to write it down.

This is still tricky. Most languages will let you repeat yourself in ways that don't accomplish anything. For example, if your poem in C is two syllables short on the second line, you could try augmenting it like this:

int main(int argc, char **argv) {
  printf("Answer: %d.\n", 40 + 1 + 1);
}

This is why poets don't like to have editors: there's always the risk of constant-folding.

The compactness with which programs can be written.

This definition reveals a trend. We have been moving away from expressiveness as something that relates to what can be written and moving toward how it is written. Of course, the desire for compactness presents certain challenges. Should compactness be measured across all programs, or only useful ones? What is a useful program? (It's the program I'm writing right now.)

We might also want to ask why we are interested in writing less, because this will affect how it is measured. Perhaps we are slow readers, and want to reduce how long it takes to read someone else's code. Does whitespace count as making a program longer? What if that whitespace is significant to the meaning of the program? If whitespace doesn't count, does using the period as an operator make a more concise language than using the colon?

One oft-cited example of programming language redundancy is a line like this, from Java:

List<List<String>> foo = new ArrayList<List<String>>();

On the one hand, we can observe that there is a lot of redundancy here. On the other hand, we are gaining some information on both sides of the assignment, since the type we gave to foo is more abstract than its actual type. On the other other hand, if foo is a local variable that's only used for two lines, giving it an abstract type may not be doing enough good to justify all that typing. On the other other other hand, Eclipse would've done all the typing for us if we weren't writing a blog post into a <textarea>.

So at least we're getting somewhere.

Epilogue

I started on this tangent because of this article. I'm still not sure what I think of that blog as a whole, although I know it was interesting enough to read past my bedtime. Although I agree with the spirit of that post, I found his treatment of expressiveness to be a bit narrow.

Also, if you prefer the concrete "look at what I implemented" posts, don't worry. I've been so busy implementing things that I haven't posted in over a year, but one of these days I will.

On File Names

Many programs have input languages that they accept. Compilers and interpreters accept programs, web browsers accept web pages, database systems accept queries, and file systems accept file names. An input language can be a great way to get input from a user.

But programs should not be using these input languages when they communicate with each other. Why? Because if program A is manipulating strings in the input language of program B, then A is reimplementing at least some of the syntactic and semantic logic that is already in program B. These reimplementations, besides being wasted effort, tend to be brittle and buggy.

In some areas, we've made great progress in dealing with this problem. For example, there are many libraries which allow for the manipulation of program source code. But there is one input language in particular whose semantics are at least partially reimplemented by nearly every substantial program in existence: the language of file names.

Lest you think that the language of file names is trivial, consider all of these syntactic and semantic details which a robust program must consider:

• Relative and absolute paths
• Trailing slashes
• Parent and self references
• Special files (devices, pipes, directories, and symbolic links)
• Hard links
• Permissions (having a file name doesn't mean you can open it)
• Existence (having a file name doesn't mean it exists)
• Platform-specific issues, such as:
  • Supported characters in names
  • Special characters (like the path separator)
  • Whether or not particular kinds of links are supported
  • What permissions are supported
  • Oddities like Windows drives

Now, I will briefly consider solutions to this problem. Much more about solutions will come in a future post. Two options have come to mind:

1. Provide a wrapper interface for existing file systems that understands and enforces all the relevant syntactic and semantic details.
2. Provide a fundamentally different file system. This option is more powerful, and I have some ideas about how this power can be used which I will discuss in a future post, hopefully with a prototype implementation of such a file system.

Read This

Read this: On the cruelty of really teaching computing science by Edsger W. Dijkstra. Yes, it's a bit long, but it is best read carefully and completely.

Frontiers

Since I should be doing homework, here's a crossword puzzle: Frontiers.

As usual, I haven't done extensive proofreading: that's what my loyal readers are for. If you find anything that is or might be wrong, please tell me.

Announcing Argon 0.2.0

I am pleased to announce the release of Argon 0.2.0, a declarative tiling window manager.

This release seems to be fairly solid. I have been using it for a week without any crashes. But, to be fair, my testing of features that I don't regularly use has not been extensive.

Anyway, Argon is now featureful, usable, and well-documented. Check out the website.

Un-over-engineering the ACM Digital Library

I have a gripe with the ACM Digital Library website. It is too hard to get the BibTeX from an article's page. Now, you might be thinking that I am crazy. After all, the link to the BibTeX is right there.

Well, that link is stupid. Its real target isn't the BibTeX (in fact, it's the citation page you are already on). Thus, you can't right-click and save the BibTeX file directly. Instead, it helpfully opens the BibTeX in a new window via its onclick event handler. And that's actually the same window for every article, so if you find a bunch of articles and click all the BibTeX links thinking you will get something sensible, you actually get one window showing the BibTeX of whatever you clicked on last.

I have created an alternative. It's not perfect, but it only took about 45 minutes to create, including all the time needed to learn how to make and package an extension for Chrome. What this extension does is add an inline frame containing the BibTeX so you can copy it to your bibliography database.

One caveat: the extension is currently hard-coded to work on two domains: portal.acm.org and portal.acm.org.ezproxy.library.wisc.edu. The latter is how I browse ACM from home. I could change this to work more generally (and thus request more permissions upon install), but it already works for me. Go ahead and submit a patch if you want to.

Argon

Now that the pace of my schoolwork is starting to pick up, I have had less time to work on my window manager. But I have made progress. However, my claim that the first release was usable may have been premature. At least, it wasn't usable to me, and since I am my entire target audience, that is a bit of a problem. So, I will not be making another release until I have actually started using my window manager for my own window-management needs.

One other accomplishment is that my window manager is longer called "KDWM", which was rather dull. It now has a more exciting name: "Argon". But I didn't only choose this name because it did well in the focus groups. Argon (the window manager) was originally meant to be "declarative". When I began working on it, I had a few ideas about what that would mean to a window manager, and they all turned out to be wrong. Eventually, I dropped the word from every document—except the acronym, where it lived on in the letter "D".

I have since discovered that Argon is quite declarative indeed, and the new name is intended not only to sound wonderful but also to emphasize that fact. How does it do this? Argon, the element, is one of the noble gases, which means that its electronic configuration is stable enough that it almost never engages in chemical reactions. I want my Argon to exhibit a similar level of stability and predictability.