NATHANWIEGAND.COM

I’ve spent my entire adult life in academia. For some reason academia, even in software engineering courses, doesn’t really harp on best practices or good patterns to know. It is possible that some do and that I’ve just missed it since I specialized in theory. So, this article will be the first in a larger category of articles which will describe patterns and techniques that I should have known but didn’t.

Episode 1: opaque pointers

I don’t care what anyone says. C is a great language. About a year ago I undertook the task of implementing a Fibonacci heap for use in an empirical analysis of two labeled graph algorithms. I put the code away months and months ago, but luckily I just found out that I got some CPU time on a very prestigious cluster so I’ve been reworking the implementations to collect better statistics. Also, since I’m finally going to do this analysis and it’s going to be published (at least in my dissertation) then I will most definitely release all of the code so that the experiments can be replayed and verified. So, since other people will look at this code I’ve spent several hours over the last few days cleaning it up and making the interfaces more reasonable. This lead me to actually pulling my fibheap out into its own stand alone project.

The fibheap isn’t ready for GitHub just yet (though look for it soon), but I’ve been working on the API and learning a lot about how this kind of thing should work. The user should be completely unaware of the internal structure of the data structure. He shouldn’t be able to mutate it in any way except through the accessors that the API provides. Though, sometimes he will need to hold pointers to particular elements in the heap (for DecreaseKey calls). This means that we need some way of providing access to elements without giving away any of our top-secret structure. So, the very simple concept that I should have known about: opaque pointers.

The crux of the matter is to separate declaration from definition just like we were always told (except in the case of templated classes… sigh). In the example of the fibheap, we want the user to have a handle to the fibheap but to otherwise not be able to affect the heap except through the API functions. So, we do this:

/* FILE: fibheap.h */
typedef struct FibHeap FibHeap;

FibHeapElement *fibHeapGetRoot(FibHeap*);
unsigned int fibHeapGetSize(FibHeap*);

And that’s it. There is no definition of the structure here, only a declaration of it. Then:

/* FILE: fibheap.c */
struct FibHeap {
  FibHeapElement *root;
  unsigned int size;
};

Because only the declaration is in the header, whenever the user does #include "fibheap.h" he only gets the name of the struct, not the layout. Thus the user cannot access either of the fields without the accessor functions fibHeapGetRoot(FibHeap*) and fibHeapGetSize(FibHeap*). No instantiation for you! (caveat: the user could easily define the struct himself and have access to the internals of the structure. This is the kind of hard opt-in that hopefully makes it clear to the user that he’s violating the spirit of the API and that this will not necessarily be stable with future versions.)

So, to summarize:

The next installment will be of a couple of ways that you can provide partial information to the user instead of none. Stay tuned!

This is one of the new Google Search Stories. I must say, pretty beautiful. I think this is a pretty good answer to those silly Bing commercials.

For years I’ve wanted to write a book. My friend Charles and I thought about writing a book on probability back when I was an undergraduate. Most recently I’ve been thinking about writing a computer science book which is an introduction to algorithms. This was spurred by my teaching exactly such a class this semester.

CS260 at the University of Alabama is entitled “Foundations of Computer Science”. This course is intended to be an introduction to the theoretical aspects of the field, ranging from analysis of algorithms to simple datastructures. This course is for second semester students, so unfortunately they’ve only had one semester of programming and don’t have a very strong math background. This means that we can’t do the more rigorous analysis of algorithms and fun proofs that would need things like counting and inductive proofs. So, I’ve decided to take a different tact. I’m trying to help them develop an intuition of the concepts by starting with the implementation of some algorithm (sorting algorithm, actually) and walking them toward a function which is computes how much work is required without actually doing the work. By then plotting these function they can get a visual representation of how much work is actually being done and see its relation to other mathematical functions. This has actually proven pretty effective at teaching asymptotics without actually teaching asymptotics.

Therefore, the book that I want to write is an introduction to theoretical computer science via empirical analysis. What if someone scoops me because of this? I don’t care. I think that this would actually help a lot of students and if I don’t get enough time to do it, then someone else should. So, I’m going to try to start putting the sketches of sections here. Eventually I’d like to set up a system like Bryan O’Sullivan had for Real World Haskell with random internet users being able to comment on parts of the books with suggestions. Stay tuned!

I just heard about Mantis a PHP based bug-tracker. I’ve never really had experience with any of these and it looks much lighter weight than Bugzilla or something like that. I haven’t even gotten to play with it yet because of installation issues. So, let me share some of them with you now:

Go ahead an temporarily create a muser user in my MySQL db:

GRANT ALL ON *.* TO muser@locahost IDENTIFIED BY 'somepassword';

You’ll take away global permissions in a minute.

Now, just unzip the Mantiz in some directory that your webserver has access to and then navigate to it in your browser. This was “/var/www/mantis” and http://localhost/mantis for me.

Following the instructions will get this all installed. Now, I don’t have a mail server, so I cannot create users. So, the default user is “administrator” and the default password is “root”. This took me some googling to figure out.

Create a new user for yourself. Note that if you don’t have a mail server running, you cannot successfully create an account because you don’t know what the temporary password is. There’s probably a better way to fix this, but here’s how I did it.

Create a new file in your webdirecotry named “w.php”:

< ?php
$mynewpassword='whatever';
echo md5($mynewpassword) . "
";
echo crypt($mynewpassword);
?>

When you run this, the output should be some very long string. For me, the first one did the trick. Copy this one to the clipboard. So, let’s get our hands dirty and fix this. Go into mysql as root (sudo mysql):

mysql> USE  bugtracker;
mysql> UPDATE mantis_user_table
             SET password='WhateverYouCopiedEarlier'
             WHERE username='yourusername';

Now, try to log in to your Mantis. If this didn’t work, try the second long string that “crypt” generated. If that didn’t work, um, sorry.

Ok, so putting things back the way you found them:

REVOKE ALL ON *.* FROM muser@localhost;
GRANT ALL ON bugtracker.* TO muser@localhost;

Finally, you should disable your “administrator” account.

That’s all I have for now. I might have a review or something later. This was just a brief writeup of what was necessary for me to get rolling.

I just saw a post on /r/programming asking people to describe their dumbest coding mistakes. Instead of just posting one of mine there, I’ll do it here.

Many, many years ago, back in 2005 when I was a green grad student and an all around n00b, I got the opportunity to work on the auto-discovery daemon for OpenMosix (may it rest in peace). OpenMosix was a self-assembling cluster system. You would just install it on several machines in the same subnet, and bam you’d have a cluster that automatically distributed jobs. On with the story.

I don’t remember what part of the daemon I was working on. It was already doing some auto-discovery and self assembly. I was pretty pleased. The basic idea was that it would fork off a listener and have another process that would chatter on broadcast announcing its presence. At some point, about 5 minutes into the run, the whole thing would segfault. More precisely, at 4:38 in, it would segfault. Wait, what? The same exact amount of time to crash? That’s just weird! Well, no kidding.

This killed me for several hours. I had no idea what was up. That’s the day I got familiar with using GDB to attach to running processes. And what did I discover? I out clevered myself. I had code like this:

fprintf(stdout, "This is some stupid debugging \
message that I'll eventually remove\n");

That looks all well and good. Why is a printf breaking? Well, it’s breaking because of this line:

fclose(stdout);

See above where I said that I out-clevered myself. Basically, I wanted to turn off all that annoying debugging chatter. So, what the hell, why not just close stdout? It worked! No more chatter. Well, that’s not all. See, whenever using printf, I was writing to a closed file handler… but it was buffered. So, my program would continue to run, dumping silly messages to this buffer until the buffer ran out of space and it smashed some import part of memory causing the segfault. Oops.

So, what did I learn? Debugging messages are important, but use some kind of clever logging system, even if it’s just a series of macros. Sometimes, if your idea seems really clever, take a step back because it might lead you to more trouble than it’s worth.

I’m still familiarizing myself with WordPress and its features. This is a code test:

C:

int foo(double bar) {
  return bar ^ 0x1111000;
}

I’d like to be able to have source code highliting done staticly. Anyone know of a plugin for that? (ans: CodeHighlighter)

Haskell:

fac 0 = 1
fac n = (*) n $ fac $ n - 1

JavaScript:

function silly() {
  this.foo = "bar";
  document.body.appendChild(document.createElement("hr"));
}

I’ll be editing this post occasionally to try to test new features, like LaTeX support amongst others.

This is a
$latex i\hbar\frac{\partial}{\partial t}\left|\Psi(t)\right>=H\left|\Psi(t)\right>$
test.

I’m in the process of migrating from Blogger to WordPress.  Because of control issues, I like to run things on my own server.  So I had Blogger uploading everything to my server via SFTP.  However, this service is coming to an end in late March, thus I had to investigate other options.  WordPress seems pretty cool so far, though it is very memory intensive.

I’ll be slowly moving things over.  I might just leave the old things in place as an archive and start this one off fresh.

That’s all for now.