Karl's Hacking Blog

On File Names

2011-07-25T10:30:00.003-05:00

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:

Provide a wrapper interface for existing file systems that understands and enforces all the relevant syntactic and semantic details.
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

2011-03-02T14:54:00.002-06:00

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

2010-12-07T21:14:00.005-06:00

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

2010-10-30T10:59:00.002-05:00

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

2010-10-10T23:05:00.003-05:00

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

2010-10-04T21:21:00.003-05:00

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.

Announcing kdwm 0.1.0

2010-09-18T19:48:00.004-05:00

I am pleased to present the first usable release of KDWM, a window manager that does what I want. My work so far on KDWM has had two purposes: creating a tiling window manager that works exactly the way I want it to, and learning a lot about Haskell and window managers in general.

If you are just so excited that you want to start using KDWM right now, you can download it.

If you'd like to browse the source or read the user documentation (which is also included in the download package), visit Github.

"Do Records" for Haskell

2010-09-06T23:32:00.006-05:00

While working on a parser written with Parsec, I began to feel annoyed at some repetitious code like this:

This pattern is no doubt common in any Parsec grammar which produces a fairly straightforward AST. As demonstrated, each field of the particular AST node being constructed is mentioned three times. This pain can be reduced somewhat by using terse names for the intermediate bindings, but this detracts from the readability of the code.

I created a solution to this problem using Template Haskell. The previous example can then be written like this:

Take a look at how it works.

Jargon

2010-08-03T13:28:00.003-05:00

A friend recently shared this infographic about how the Internet works on Google Reader. Go read it first. What struck me about it is how full of unexplained jargon it is, despite the fact that the creator was clearly trying to make something anyone can understand. Just as bad as jargon, the graphic also employs a lot of conceptual jargon: that is, ideas which, without further elaboration, probably seem nonsensical to an outsider.

In addition to criticism, I will give my suggestions about what could have been said.

let's try to strip a little of the mystery from this great web: Okay, this is not jargon, but it's still a poor choice of words. It may unintentionally further the average person's conflation of "the Internet" and "the world wide web," something which a graphic trying to explain the Internet should want to avoid.
language: Most people have never encountered the concept of a formal language. While formal and human languages share many characteristics, only formal languages are fundamentally useful for inter-computer communication. To use the word "language" without explaining briefly what makes computer languages different is not a good idea. People may end up thinking that the computers are calling each other up on the phone and speaking English. This wouldn't be hard to correct: just say that a computer language tends to have "simple grammatical rules which are rigidly followed."
protocol suite: The graphic wastes space using and explaining this term, in reference to TCP/IP, when it could have simply said "the Internet relies on two protocols: TCP and IP." The concept of a "protocol suite" is irrelevant to understanding the Internet.
addresses and names: Here the graphic is using two different analogies simultaneously to explain IP addresses. It would have been better to choose one, with more space devoted to explaining the analogy, since neither one is perfect. In fact, a better analogy than either of these is to say that an IP address is like a phone number. DNS is then simply a phone book. The main difference which must be explained is that when a computer's IP address changes, it's not a big deal, because all the phone books update automatically.
dynamic and static addresses: This is not truly a black-and-white distinction, nor is it especially important for an understanding of the Internet. It would be better to simply say that some computers' phone numbers change more often than others.
server: This term is used without explanation. If it is going to be used, it would probably be best to explain the client-server model in a bit more detail, before the diagram. You might think this is hard, but it isn't. Just mention that "client" and "server" are two roles a computer can play at any moment. Typically, your computer is a "client," which means it is asking for information, and a "server" somewhere else is providing that information back to you.
that diagram with the arrows: This diagram is very confusing. There's no way to understand from the diagram what order things happen in. You can't easily follow a particular piece of data as it flows through the system. It would have been better (and more informative) to separate the DNS query into another diagram (or simply remove it), since the DNS query is a separate request using a separate connection. Then, the remaining diagram could have truly been done in a data-flow style.
ones and zeroes: Chances are anyone who has enough interest in computers to make it this far down the infographic has already heard this cliché explanation, but it's not that helpful. How does a person with no technical knowledge even fathom the idea that all information can be turned into ones and zeroes? An example here of that translation would be immensely helpful toward creating understanding. A good (and exciting) example would be to show how a small image can be imagined in pixels, with RGB color values, which can each be represented in binary.
host, megabit, URL: These terms are all used, without explanation, in the bottom portion of the graphic, which is mostly devoted to explaining how huge the Internet is. Besides that, all that explanation of the hugeness is pretty much unrelated to how the Internet works. It would have been better as a separate graphic.

I would have created a graphic incorporating all my suggestions, but I am not much of a designer. If you want to, feel free, but please let me suggest edits to the text before you put it online.

Master of Science

2010-07-31T20:05:00.003-05:00

For those who don't already know, I have completed my M.S. thesis.

Adventures in Template Haskell

2010-07-22T10:55:00.012-05:00

I've been working on a window manager lately, but this post isn't about that. Perhaps a later one will be.

In the course of this work, I stumbled across a sort of gap in what you can easily do with Haskell's record syntax:

Basically, getting an updated record where a function has been applied to a particular field involves naming the field and the record twice. The longer the names, the worse it gets. I solved this problem with some Template Haskell:

It gets even better when the record you are updating is the state of a State monad:

Since the record doesn't need to be named, the lambda is avoided.

Take a look at the code to see how it works.

A Safe and Improved Replacement for vim Modelines

2010-07-15T20:17:00.006-05:00

If you work on multiple projects which have different source code formatting conventions, vim's modelines can be useful. They allow a file to specify vim options which should be set when that file is loaded, such as options relating to the treatment of tabs. However, enabling modelines can be risky if you are editing files written by other people. Furthermore, maintaining a particular modeline across all the source files in a project is an aggravating but necessary task.

Today I wrote a little solution to this problems which I call "dirmode". It is a vim plugin which provides a feature somewhat like modelines, except that the options are stored in a separate file and affect all files in the directory where the options file is located.

The plugin is already usable and useful, albeit under-documented. I do have plans for some improvements, which you can read about in my to-do list. Also, have a look at the source if you are interested.

Flowing

2010-07-08T16:07:00.006-05:00

Here is the other crossword puzzle produced by my camping trip, Flowing.

I realized today that a few words in this puzzle which seemed real out in the wilderness turned out to be somewhat imaginary. With the help of modern technology, I managed to replace those words without disrupting everything else too badly.

Urbanism

2010-07-07T23:21:00.005-05:00

Here is another crossword puzzle, Urbanism.

I am aware that this puzzle does not quite follow the conventions which I have been striving for: it contains a slight asymmetry and a single two-letter word. I don't think it's much of a problem. I would like to experiment with some "non-traditional" shapes, which will probably be even less symmetrical.

Unlike my previous puzzles, this puzzle grid was constructed without any electronic aids. I like the result better because the words feel more personal. But, I was more deliberate about using the black space to keep different parts of the puzzle fairly separate. I don't know if I could make a puzzle with Harry Truman's level of openness without some computerized help.

Another puzzle will be out soon. I made two grids on my recent trip into the wilderness, but I haven't written any clues for the second one.

Harry Truman

2010-06-28T01:38:00.005-05:00

After watching Wordplay, I was inspired to try making a crossword puzzle again. Here it is.

Edit: I fixed a typo in 44-Across. Also, the puzzle has been re-typeset in a slightly better fashion. (This came about as the result of automating the entire typesetting process. Maybe I should write about how that works.)

Pidgin with Less Windows

2010-06-05T23:09:00.006-05:00

I use Pidgin for my instant messaging, but I also use a tiling window manager. Getting the conversation window to appear in the right place is a tricky problem. After years of horrible kludges, I finally got around to solving this problem the right way: by changing Pidgin to make new conversation tabs appear inside the Buddy List window. So, I just have to put that window in the right place once, and all (one of) my pidgin windows are in the right place all the time.

Now, I am not a Pidgin developer. I've never even made a Pidgin plugin until tonight. So, the pre-pre-alpha-quality code which I'm revealing here is about as much of a horrible kludge as all my previous window manager tricks. But, this kludge works better than all the previous ones, so I'm sticking with it, and I'll get the code cleaned up over time.

By the way, there is a two-year-old enhancement request for this feature on the Pidgin Trac. The approach suggested in the comment there by deryni is the approach I used, and it seems to work fine.

So what is that approach? First, there is a plugin. Pretty much all the functionality is in the plugin (but not quite, because I needed to extern some functions that used to be private to the conversation window module, and I made a slight addition to the heirarchy of GTK containers inside the Buddy List window). So, in order to use this plugin, you actually need to build the entire Pidgin source tree with my patches.

Oh yeah, my patches. Here they are. There are two files in there that you need. patch is a diff of my changes to the main Pidgin source tree. onewin.c is the plugin source. Put it in $PIDGIN/pidgin/plugins, and once you've built the Pidgin source, go into $PIDGIN/pidgin/plugins and run make onewin.so to build the plugin. Then copy onewin.so into ~/.purple/plugins. (Note: it seems that you can't just run the pidgin binary from the source tree, because it can't find some important modules, like the IM protocol handlers.)

One more step is required for the plugin to work, but first I will digress a bit into its implementation. Pidgin has a concept called "conversation placement functions." There are a bunch of default placement functions which provide behavior like "one conversation per window" or "all conversations in one window." My plugin provides a new conversation placement function called "onewin" that puts conversations inside the Buddy List window. In order for my plugin to actually do anything, though, Pidgin has to decide to use the onewin placement function. I haven't yet figured out how to do that in any reasonable way, so I just edited ~/.purple/prefs.xml so that /purple/conversations/placement was set to onewin. (You also need to have the plugin enabled. Right now, it will show up in your plugin list as "Hello World" because I haven't changed its name. I'm not sure what happens if you try to use onewin when the plugin isn't enabled.)

There are some known issues with the plugin. You can look at my to-do list if you are interested.

There are also a lot of unknown issues with the plugin. If you find any of them, please tell me.

Finally, I will note that I am building and testing this on Arch Linux i686. I think it should build on any platform where Pidgin builds, but I'm not going to try it. If you do, I'd like to hear about it.

Geometric Series in Haskell Using [..] Notation

2010-03-21T00:43:00.009-05:00

I was reading the docs earlier today for Haskell's Enum class. Any instance of Enum can be used in the [..] notation, which has four forms: [a..b], [a,b..c], [a..], and [a,b..]. The implementor of Enum a can make these forms do anything, so long as they produce a value of type [a].

It occurred to me that I could create a type, and a corresponding Enum instance, which would make the [..] notation produce a geometric series rather than the usual arithmetic series. I called this type Geo. I also made an instance Integral Geo so that the [Geo] could be turned into a list of more usable numeric type. But I didn't stop there, because using the type directly would be ugly: map toInteger ([1,2..16] :: [Geo]).

So, I made a function geo :: (Integral a) => [Geo] -> [a]. So now, to get a geometric series in a reasonable type, the user only had to say geo [1,2..16].

Then I realized that, unlike when generating an arithmetic series, integral inputs do not guarantee integral outputs. So, I changed the type Geo to be an instance of Fractional rather than Integral, so that you can do things like take 5 $ geo [2,1..] and get the right answer.

If you want more detail, ask me or take a look at the code. An example progam is included.

Erdot

2009-03-19T18:04:00.011-05:00

It occurred to me that I could write Entity-Relationship diagrams using Graphviz, but I knew it would be clunky. I created a quick bit of Perl to translate a simple ER description language into Graphviz code, which I have called Erdot.

For example:

entity foo
entity bar
entity baz attr a b c

weak entity quux

relate abc foo bar!*
relate def bar* baz* attr z

relate manages foo<manager> foo<subordinate>

weak relate ghi baz quux

becomes:

Current issues:

The heirarchical layout used by dot is not much like the layout of a typical hand-drawn diagram. Other layout engines included with Graphviz provide a better layout, but fail to correctly handle edge labels. There might be a way to configure one of those engines to avoid drawing the edge labels on top of everything else (and each other).
The script could be much more powerful if the ER descriptions were parsed with a CFG instead of a quick hack. Maybe I will take this as an opportunity to learn about the grammar system in Perl 6.

Erlang Quick Reference

2008-12-08T21:26:00.006-06:00

Here is an Erlang Quick Reference I just made. I am basically a beginner at Erlang, so I'm not sure if I've covered the right bases or covered them correctly. Suggestions and corrections are welcome.

Module contracts in Perl

2008-12-07T03:55:00.006-06:00

I whipped up a little Perl module which foists a contract upon a subroutine. It replaces that subroutine with one which checks the arguments and return value against a predicate. The predicates themselves conform to a simple interface: they must be able to check a value, returning true or false, and they must be able to describe themselves. The latter enables the contract system to provide helpful error messages when a violation occurs.

Here is an example use of the module:

The contract function takes three arguments: the name of the subroutine (which must be in the package you are calling from), the predicate for the argument list, and the predicate for the return value. Contract::Predicate exports some predefined predicates as well as the means to create new ones.

In the example, the call to foo results in a violation, because the function does not return an integer as the contract requires.

Interesting tidbits:

When the contract system calls the original function which it has replaced, that call needs to be done in the proper context (array, scalar, or void). AFAIK, you cannot do a call in void context and get the return value of that call. If a function with a contract is called in a void context, the return value contract is not checked. My guess is that this won't matter much in practice. Then again, many subroutines should only be called in certain contexts, so perhaps in addition to the return value predicate, contract should accept some indication of which contexts the function may be legally called in.
Replacing the functions is done with Sub::Override, which is not a part of the base Perl distribution. It is on CPAN and exists as a Debian package (libsub-override-perl). This module isn't strictly necessary, but I couldn't get it to work the old-fashioned way. (I also didn't spend much time trying.) One interesting feature of Sub::Override which makes it bad for this particular application, but which is a neat idea in general, is that when you do an override, you get back an object, and that object's destructor undoes the override. Consequently, Contract has an internal list of Sub::Override objects which it has to keep around forever.
I ought to get an account on CPAN and put this up there. I wonder if there are other modules like it? Even if there's a better one, writing this was a quick, fun exercise.

You can get the source.

FFI in PLT Scheme

2008-12-06T04:48:00.003-06:00

This is way too easy: