Showing posts with label programming. Show all posts
Showing posts with label programming. Show all posts

Friday, September 18, 2015

Mercurial koans

A young acolyte approached Master Hg.  "Master Hg, what is the nature of Mercurial Branches?"

Master Hg replied, "Branches are markers attached to every commit, indelible and eternal."

The acolyte nodded.  "Master, if we use branches for tracking new features in our product, how are we to avoid namespace pollution?"

Master Hg regarded the acolyte coolly.  "Mu.  Branches are lines of development, forgettable and ephemeral."

At once, the acolyte was enlightened.

A student was working under Master Hg.  "Master, yesterday I discovered a seven-headed hydra in our history."

Master Hg nodded, saying nothing.

"I did not wish to fight the beast, but I noticed it resided entirely on a separate branch.  So I closed the branch, and thought it dealt with.  But today I looked again and saw the hydra still lived.  Why was the branch not closed?"

"The branch was indeed closed," replied Master Hg, "leaving six branches open."


Ed. note: This koan is obsolescent and has no successor.

One day, a traveler from a faraway land sought Master Hg's guidance.  "Master Hg, I wish to alter history."

Master Hg nodded, smiling warmly.  "What you seek is easily attainable.  History is supple and easily rewritten."

Excitedly, the traveler began researching in Master Hg's veritable library and shared his work with others.  After many days, he returned.  "Master, when I tried to share my changes with my friends, as I have done in my homeland, the DAG became extremely confused and I had to re-clone the server.  Why does Mercurial not work correctly?"

Anger flashed across Master Hg's face.  "What you seek is impossible.  History is unyielding and changing it the domain of the gods."

"But mere days ago," the traveler protested, "you told me otherwise."

"I find it curious you remember events which did not occur," replied Master Hg.

The traveler stormed out angrily.  It was many hours before enlightenment struck him.

Friday, April 3, 2015

Why I don't use hg-flow

I recently had a chance to read A successful Git branching model (the branching model underlying the popular git-flow and hg-flow extensions), and I found it rather interesting.  For NBTParse, I've been following a modified form of Mercurial's standard branching.  I thought about trying to adapt my work to use hg-flow, but I realized the differences are largely cosmetic:
  • My main development descends from the @ bookmark, just like the "develop" branch of Driessen's model.  Conveniently, Mercurial automatically updates to this bookmark when cloning, if there's no obvious target revision.
  • Although I rarely bother with them, feature branches are easily supported as bookmarked alternate heads of the default named branch.  I may use them more often once NBTParse approaches stability and it becomes necessary to keep the trunk stable(ish) leading up to a beta release.
  • I use release branches, much like Driessen.  Mine are named branches instead of bookmarks, but this is mostly a matter of the former not existing under Git.  The release branches also have bookmarks, which are reused from one branch to the next; this makes it easy to (automatically) find the current unstable release branch (it's just release-unstable), for example.
  • Much like feature branches, hotfix branches are just bookmarked alternate heads of release branches.  Again, I rarely bother with them, since my release branches remain open for as long as the released product is supported.  However, they can be useful if a fix is likely to require multiple commits or the attention of multiple developers.
  • Now we come to the "master" branch.  I must admit, I don't quite have a master branch, but I have the next best thing.  All my releases are tagged, and the latest unstable (and stable, once we hit stable) is bookmarked.  I can just do hg log -r 'tag("re:version-.*")' to find everything that would have been on the master branch if I had one.  If I only want stable releases, I can use a more precise regex (e.g. ^version-\d+\.\d+\.\d+$).  Oh, and those revsets work in Bitbucket's search interface, too.
I'm sure Driessen's model is extremely helpful for him and lots of other developers, and it's nice to see people looking at nontraditional branching strategies.  But I guess I just don't see much value in rearranging my commits like this; my revision DAG is complicated enough already.

Friday, February 20, 2015

NBTParse

For quite some time, now, I've been working on a Python library called NBTParse.  It's designed to manipulate Minecraft worlds.  It's been languishing in a not-ready-for-prime-time state for the longest time, but I've finally decided to start working towards a 1.0 release.  As a motivator for that, I've begun rapid releases of 0.x.0 versions.

Each new 0.x.0 release will happen on the first Thursday of the month.  0.2.0 dropped on the 5th, but I didn't think to blog about it until now.  It can be had from PyPI under the name nbtparse (that is, you can run pip install nbtparse as usual).  If you don't have a C compiler, you may have difficulty with this.

Let's talk about the current status of the library.  It's currently very rough, with a number of serious shortcomings.  The biggest is the lack of a lighting engine.  In short, it doesn't adjust lighting information after altering the terrain.  Because of this, terrain manipulation is highly risky at the moment, with great potential to corrupt saves.  In other words, back up your saves before playing with this.  But you knew that already; it's listed as pre-alpha in PyPI, after all.  Work on the lighting engine has not seriously begun yet, so this will likely remain the case for a long time.  On the other hand, I hope to at least have heightmap updating in time for 0.3.0 (this will hopefully prevent any corruption from actually crashing Minecraft, though you'll still experience lighting errors).

Another issue is Minecraft 1.8 compatibility.  In short, there is none.  While 1.8-isms are nominally accessible, they're not particularly fun to work with right now.  Fortunately, this is mostly a matter of sitting down and writing declarative code to describe the new features.  It should be fairly straightforward once I get around to actually doing it.  I hope to have this in 0.3.0.

Finally, the API is not yet stable.  Some aspects of the library may change as we move closer to 1.0, without backwards compatibility.

Friday, September 19, 2014

The Pendulum and the Winch

I often find that explaining computer science to non-computer-scientists is difficult.  It's been said that computer science is like no other field of study.  Well, I think that's a rather strong claim to make.  What follows is a translation of a standard problem in computer science into physics.  It is an analogy, unrealistic but nevertheless interesting.

I have a pendulum, supported by some apparatus ultimately connected to a pillar or pole.  It is possible to move the apparatus up or down, but only by manually detaching and reattaching it by hand.  I have a winch affixed to this apparatus which may raise or lower the pendulum.  It is connected to a coil of rope or string (which, for the purposes of this problem, is infinitely long yet magically takes up a finite volume), and can be remotely controlled at the press of a button.  The winch is also geared discretely; it only turns in units, and then only one at a time.

I wish to carry out a series of experiments involving varying the length of my pendulum.  In particular, I often want to lengthen the pendulum.  Most of the time, this setup suits me quite well.  But sometimes, I find I need a pendulum longer than the apparatus is high off the ground.  In these situations, I need to climb the pillar and move the winch up.  In so doing, I may need to start an entire experiment over again because the pendulum lost energy while I was climbing.  How can I avoid or minimize those climbs in proportion to the maximum length of the pendulum?  We must assume I do not know the maximum length in advance, perhaps because my experiments are highly complex and difficult to predict, or perhaps because they are directed by someone else's instructions, and they did not think to tell me in advance how long a pendulum I would need.

Thursday, June 13, 2013

Why I am not recommending GeoNode

For the past few weeks, I've been working for a professor on a project involving geographical data.  As part of this project, I was asked to evaluate GeoNode.  So I looked at the website, and after wandering around for a while trying to get past the usual marketing bullshit (side note: Can anyone explain to me why so many open source projects these days have such enormous quantities of marketing bullshit?), I eventually found some real documentation.  It was in the form of a developer "workshop," however, so I was a bit leery of it.

Friday, January 18, 2013

One-time pads with Python

A one-time pad is a kind of unbreakable encryption.  For most encryption, breaking it is a matter of throwing a lot of computational resources at the problem.  Typically, the amount of resources needed greatly exceeds the amount that is practical to obtain, so most modern cryptography is secure enough.  There are, however, some downsides to modern cryptography, the biggest of which is its complexity.  If we want to use crypto for something like bank transactions, complexity is not that big of a deal, because centralization can hide most of the complexity from end-users.  But if, for instance, you need to implement secure communications without a centralized certificate authority, effectively implementing secure communications becomes a lot harder.

Wednesday, August 8, 2012

An exercise

Sometimes, I feel like stretching my programming muscles.  A while ago, I read about this problem, or one like it.  It's not an especially hard problem, but I'd like to go over it anyway, because low-level data types can be unintuitive.

Suppose you have two integers a and b.  You want to add them, but you also want to be sure they don't overflow.  You're working in a language where overflow is undefined, such as C.  You can't use arbitrary precision variables or anything fancy like that, nor can you make use of low-level things like CPU overflow detection.  You need to guard against overflow mathematically, without the use of any of those systems.  Maybe you're working on a reduced architecture that doesn't provide overflow detection.  Maybe your language or library is deficient and lacks an arbitrary precision integer type.  It doesn't really matter.  The point is, taking away all those "outs", we're left with a somewhat interesting problem.

Here are some assumptions you may make:
  1. You have a constant called INT_MAX which is equal to the largest integer which can be represented on your system.  You also have another called INT_MIN, which serves a similar purpose for the smallest (most negative) integer.
  2. You're working in two's complement, but overflow is still undefined.
  3. You do not have the exact number of bits available (but you could figure it out from INT_MAX, so that's not much of a restriction).
  4. You may throw an exception to indicate an overflow condition.
Actually think about this problem for a few minutes.  I'll put the solution after the break.  I really think most people who are likely to read this blog can solve this on their own, so please actually try this.