Thursday, November 19, 2015

A picnic for a rainy day

I made a crossword again. This one even has a theme!

Get the PDF.

Saturday, August 8, 2015

Return

You probably thought this blog was dead. So, have a crossword! This is my first crossword that completely follows the typical American layout conventions.

As usual, it's late at night and there could be a typo. Please send me bug reports.

EDIT: Due to popular demand, I have devised a way to render this crossword onto a single page.

Thursday, September 13, 2012

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.

Monday, July 25, 2011

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.

Wednesday, March 2, 2011

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.

Tuesday, December 7, 2010

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.

Saturday, October 30, 2010

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.