Lazy big-O and Haskell Answers

Programming

First, Evan has a host of interesting articles about Haskell, and I found his lazy big-O article particulary interesting.

Next, Eric Warmenhoven has recently taken up Haskell and posted some Haskell questions on his blog. Eric, here are some answers for you.

First, regarding shared libraries. While Haskell can be compiled to machine code, and GHC is a popular way to do that, a standard C way of representing information about a library (.h and .so files) is not really rich enough for Haskell. Consider, for instance, that functions may accept arguments of a wide range of types (or even things such as lists of any type). Haskell also performs type checking, and thus must know the type of arguments a function expects, as well as its return type, at compile time. So you do not generally compile Haskell code directly to .so files, but rather use the compiler’s module or package support to do that. See Cabal for more information on packages. Through the FFI (Foreign Function Interface), it is possible to both call into C and be called from C with Haskell code, if that’s where you want to go. It is actually easier in Haskell than in any other high-level language I’ve dealt with before.

Regarding circular module deps — I’ve never used them and can’t really comment. I can say, though, that the .boot files are internal files created by GHC.

Regarding practical stuff in tutorials — I share your complaint there. I have found a few that are better than the others: Yet Another Haskell Tutorial, and Haskell: The Craft of Functional Programming, 2nd ed., by Simon Thompson. Several of us are working intermittently on a project called Haskell V8 — take a look and darcs send me patches! I would say that Haskell’s I/O system is the most powerful I’ve seen in many ways — especially with regard to laziness — and in the upcoming GHC 6.6 release, it will be both lazy *and* blazingly fast. Very nice.

There isn’t much Debian-specific documentation, but there is a draft policy and a mailing list (link to it is in the policy doc).

Hope this helps!

Renovation: Weeks 8-9

House Renovation, ,

We’ve been very busy lately, so I’m a bit behind on renovation updates.

I’ve posted the photos for weeks 8 and 9. The new kitchen is starting to take shape!

We’re also going to get a nice heating/air system. My great uncle, who is doing that work for us, came up with a 3-zone system. We’ll have one furnace & AC, but three temperature sensors. There will be motorized dampers in the ducts that are controlled by that system, so we can direct hot or cold air only where it needs to be. We’ll break even on it now because we can make do with a smaller AC and furnace, and will save money over the long run due to lower utility bills.

We also learned that the wood floors in pretty much the entire house can be saved, so that’ll be nice, too.

Here’s a sample:

Click here for the rest.

Renovation Update: Weeks 6-7

House Renovation

The big news out at the farm this week is the foundation on the house. In 6 days of work, the foundation people have already demolished the old foundation, leveled up the house, dug out the area for the new foundation (which is digging down and out to expand the foundation to cover the whole house), and poured the walls. So the house is now sitting on new walls.

Here are some photos of the foundation work in progress.

Peter

General, ,

I was meaning to write this story two weeks ago, but then the fire happened… So better late than never.

My brother Peter is participating in a ministerial inquiry program this summer. College students can spend a summer as an intern at a church and start to get a real feel for what it’s like to be involved with ministry.

Two weeks ago, Peter gave his first sermon at the church he’s with this summer. He compared the task of a bunch of college guys trying to figure out how to get their bathroom clean to that of figuring out how to spread Jesus’ word. A great (and entertaning!) sermon for sure.

We went back to hear his second sermon today — a more serious, but no less vibrant, one about how Elijah felt that he wasn’t up to the task the Lord had in mind for him. Peter did a great job again, and gave me some things to think about.

Now, since I’ve been going through pictures this weekend, here’s a picture of Peter back when he was 6. Our parents were having drywall installed at the time, and Peter and I found the stilts that the drywall installers were using one evening. We had a lot of fun walking around on them.

Peter is the one on the left with the smile, toy sheriff’s badge, hat, and pen on his shirt. (He still has the smile and pens, but I haven’t seen the badge or hat in awhile.) I’m the one on the right, looking annoyed that I’m not on my preferred side of the camera lens. I really was enjoying myself until then ;-)

Bowling with Grandpa

General,

I’ve been taking photos for a long time. Today I found some pictures I had taken back when I was 11.

My grandpa used to like to take my brother and me bowling. Grandpa was a good bowler and played on a team. I wasn’t a good bowler. But it was fun because it was the two of us and Grandpa, and he’d always take us out to eat afterwards, too.

Here is a picture I took while bowling with Grandpa back in 1991:

It’s fun to look at some of these old pictures. They sure bring back the memories. And sometimes there are worthwhile ones like this in between all the photos of pets and household objects.

Whose Distributed VCS Is The Most Distributed?

Software,

Lately I have been trying out a number of distributed version control systems (VCS or SCM).

One of my tests was a real problem: I wanted to track the Linux 2.6.16.x kernel tree, apply the Xen patches to it, and pull only specific patches (for the qla2xxx driver) from 2.6.17.x into this local branch. I wanted also to be able to upgrade to 2.6.17.x later (once Xen supports it) and have the version control system properly track which patches I already have.

But before going on, let’s establish what it means to be an ideal distributed VCS:

  • 1. The fundamental method of collaboration must be a branch. A checkout should mean creating a local branch on which a person can commit and work without having to involve the server. An update from some central server should take the form of a merge from that branch to the local branch.
  • 2. Branching should be cheap. It should be easy to create a local branch, the operation to do so should be fast, and it shouldn’t take an inordinate amount of space. It should also be as easy as possible to branch from a remote repository.
  • 3. Merging between branches is intelligent. It should be easy to merge another branch with your own. The VCS should know which changesets from the other branch are already on yours, and should not attempt to merge changesets that you have already merged previously.
  • 4. Inividial changesets should be mergeable without bringing across the whole history. You should be able to bring across the minimum number of changesets necessary to effect a specific change. This corresponds to my test case above. Future merges from the whole branch should, of course, recognize that these changesets are present already.
  • 5. Branching preserves full history. A branch should be a first-class copy of a repository, even if the repository is remote. It should contain the full history of the branch it was made from, including diffs for each individual changeset and full commit logs, unless otherwise requested by the user.
  • 6. Merging preserves full history. A merge from one branch to another should also preserve full history. Changesets merged to the local branch should retain the individual, distinct diffs and commit logs for each changeset.

There are also some things that we would generally want:

  • 7. It is possible to commit, branch, merge, and work with history offline.
  • 8. The program is fast enough for general-purpose use.

Evaluation

Let’s look at some common VCSs against these criteria. I’ll talk about Arch (tla, baz, etc), bzr (bazaar-ng), Darcs, Git, Mercurial (hg), and Subversion (svn) for reference.

1. The fundamental method of collaboration must be a branch

All of the tools pass this test except for svn.

2. Branching should be cheap

Everyone except svn generally does this reasonably well.

The tla interface for Arch had a pretty terrible interface for this, so it took awhile simply due to all the typing involved. That’s better these days.

Darcs supports hardlinking of history to other local repositories and will do this automatically by default. Git also supports that, but defaults to not doing it, or you can store a path to look in for changesets that aren’t in the current repo. I believe Mercurial also can use hardlinks, though I didn’t personally verify that. bzr appears to have some features in this area, but not hardlinks, and the features were too complex (or poorly documented) to learn about quickly.

svn does not support branching across repositories, so doesn’t really pass this test. Branches within a repository are not directly supported either, but are conventionally simulated by doing a low-cost copy into a specially-named area in the repository.

3. Merging between branches is intelligent

Arch was one of the early ones to work on this problem. It works reasonably well in most situations, but breaks in spectacular and unintelligble ways in some other situations.

When asked to merge one branch to another, Darcs will simply merge in any patches from the source branch onto the destination which the destination doesn’t already have. This goes farther than any of the other systems, which generally store a “head” pointer for each branch that shows how far you’ve gone. (Arch is closer to darcs here, though ironically bzr is more like the other systems)

Merging between branches in svn is really poor, and has no support for recognizing changesets that have been applied both places, resulting in conflicts in many development models.

4. Inividial changesets should be mergeable without bringing across the whole history

Darcs is really the only one that can do this right. I was really surprised that nobody else could, since it is such a useful and vital feature for me.

Both bzr and git have a cherry-pick mode that simulates this, but really these commands just get a diff from the specific changeset requested, then apply the diff as with patch. So you really get a different changeset committed, which can really complicate your history later — AND lead to potential conflicts in future merges. bzr works around some of the conflict problems because on a merge, it will silently ignore patches that attempt to perform an operation that has already occured. But that leads to even more confusing results, as the merge of the patch is recorded for a commit that didn’t actually merge it. (That could even be a commit that doesn’t modify the source.) Sounds like a nightmare for later.

Arch has some support for it, but in my experience, actually using this support tends to get it really confused when you do merges later.

Neither Mercurial nor svn have any support for this at all.

5. Branching preserves full history

git, darcs, and Mercurial get this right. Making a branch from one of these repos will give you full history, including individual diffs and commit logs for each changeset.

Arch and bzr preserve commit logs but not the individual changesets on a new branch. I was particularly surprised at this shortcoming with bzr, but sure enough, a standard bzr merge from a remote branch commited three original changesets into one and did not preserve the individual history on the one commit.

svn doesn’t support cross-repo branching at all.

6. Merging preserves full history

Again, darcs, git, and Mercurial get this right (I haven’t tested this in Mercurial, so I’m not 100% sure).

Arch and bzr have the same problem of preserving commit logs, but not individual changesets. A merge from one branch to another in Arch or bzr simply commits one big changeset on the target that represents all the changesets pulled in from the source. So you lose the distinctness of each individual changeset. This can result in the uncomfortable situation of being unable to re-create full history without access to dozens of repositories on the ‘net.

Subversion has no support for merging across repositories, and its support for merging across simulated local branches isn’t all that great, either.

7. It is possible to commit, branch, merge, and work with history offline

Everyone except Subversion does a good job of this.

8. The program is fast enough for general-purpose use

All tools here are probably fast enough for most people’s projects. Subversion can be annoying at times because many more svn commands hit the network than those from others.

In my experience, Arch was the slowest. Though it was still fine for most work, it really bogged down with the Linux kernel. bzr was next, somewhere between arch and darcs. bzr commands “felt” sluggish, but I haven’t used it enough to really see how it scales.

Darcs is the next. It used to be pretty slow, but has been improving rapidly since 1.0.0 was released. It now scales up to a kernel-sized project very well, and is quite usable and reasonably responsive for such a thing. The two main things that slow it down are very large files (10MB or above) and conflicts during a merge.

Mercurial and git appear to be fastest and pretty similar in performance.

All of these tools perform best with periodic manual (or scheduled cron jobs) intervention — once a month to once a year, depending on your project’s size. Arch users have typically created a new repo each year. Darcs users periodically tag things (if things are tagged as part of normal work, no extra work is needed here) and can create checkpoints to speed checkouts over the net. git and Mercurial also use a form of checkpoints. (not sure about bzr)

Subversion works so differently from the others that it’s hard to compare. (For one, a checkout doesn’t bring down any history.)

Conclusions

I was surprised by a few things.

First, that only one system actually got #4 (merging individual changesets) right. Second, that if you had to pick losers among VCSs, it seems to be Arch and bzr — the lack of history in branching and merging is a really big issue, and they don’t seem to have any compelling features that git, darcs, or Mercurial lack. #4 was a unique feature to Darcs a few years ago, but I figured it surely would have been cloned by all the other new VCS projects that have popped up since. It seems that people have realized it is important, and have added token workaround support for it, but not real working support.

On the other hand, it was interesting to see how VCS projects have copied from each other. Everyone (except tla) seems to use a command-line syntax similar to CVS. The influence of tla Arch is, of course, plainly visible in baz and bzr, but you can also see pieces of it in all the other projects. I was also interested to see the Darcs notion of patch dependencies was visible (albeit in a more limited fashion) in bzr, git, and Mercurial.

So, I will be staying with Darcs. It seems to really take the idea of distributed VCS and run with it. Nobody else seems to have quite gotten the merging thing right yet — and if you are going to make it difficult to do anything but merge everything up to point x from someone’s branch, I just don’t see how your tool is as useful as Darcs. But I am glad to see ideas from different projects percolating across and getting reused — this is certainly good for the community.

Updates / Corrections

I got an e-mail explaining how to get the individual patch diffs out of bzr. This will work only for “regular”, non-cherry-picked merges, and requires some manual effort.

You’ll need to run bzr log, and find the patch IDs (these are the long hex numbers on the “merged:” line) of the changeset you’re interested in, plus the changeset immediately before it on the same branch (which may not be on the same patch and may not be obvious at all on busy projects.) Then, run bzr diff -r revid:old-revid-string..new-revid-string.

I think this procedure really stinks, though, since it requires people to manually find previous commits from the same branch in the log.

First steps with git and I’m not all that pleased

Software,

I have been tracking 2.6.16.x here because Xen doesn’t have patches for 2.6.17 yet (why on earth that is, I don’t know.) But I need a few 2.6.17.x patches to the qla2xx driver. So I figure this is an opportunity to learn git.

I learned git, but then quickly learned that I can’t just pull random commits from one branch to another. I have to use git cherry-pick, which doesn’t actually pull the commit unmodified — it takes a diff, and commits a new patch based on that diff. So I expect problems later when I bump the local branch to 2.6.17.

This seems depressingly like arch/baz/bzr, and is a good reason for me to stay with darcs for now. This same operation with darcs would have been trivial, AND darcs would have automatically pulled in prerequisite patches rather than giving a merge failure and making me find them manually.

Fire updates

House Renovation

Whew. Lots has been going on the past couple of days.

First, many thanks to all that sent us e-mails, comments, and notes. We appreciate it! It’s nice to have people the care.

Next, in addition to the first set of fire photos I posted, I have now added more photos: a second set of fire photos. Note that there are two pages to that as well.

I’ve also added some photos to the Grandpa’s Farm set — this shows what things looked like back in April, before the fire. The buildings that burned are the barn, calf barn, and chicken house.

On to the updates…

Monday I went out to the farm first thing in the morning. Some areas were still smoldering — basically wherever there was hay. It was a bit concerning. I went up to the 2nd floor in the house and took some photos of the yard.

I headed on in to work. Later in the evening, I went back out to check on things. Two fire fighters were back out there with a fire truck dousing the remaining smoldering areas. Apparently the fire fighters had been checking on the place intermittently all day and had been out there with water earlier as well.

The Goessel Fire Dept. is an all-volunteer department. These people aren’t getting paid for this, and they do an EXCELLENT job. Someone was out at 1AM Monday, again at 10AM Monday, then twice more with the truck. They did all this on their own — I hadn’t asked them to. It is amazing how much these people care about the community and taking care of fires.

I also never knew how long bales of hay burn.

Here’s one of the new photos: