Steve Losh

Git Koans

2013-04-08T10:16:00Z

Silence
One Thing Well
Only the Gods
The Hobgoblin
The Long and Short of It

Silence

A Python programmer handed her ~/.gitconfig to Master Git. Among the many lines were the following:

[alias]
; Explicit is better than implicit.  If we want to merge
; we should do so ourselves.
pull = pull --ff-only

Master Git nodded. “git pull origin master,” said the programmer.

Master Git pulled down the latest changes on master and automatically merged them with the programmer’s changes.

“But Master Git, did I not say to only fast-forward in my configuration?!” she cried.

Master Git looked at her, nodded, and said nothing.

“Then why did you not warn me of a problem with my configuration?” she asked.

Master Git replied: “there was no problem.”

Months later the programmer was reading git --help config for a different reason and found enlightenment.

One Thing Well

A UNIX programmer was working in the cubicle farms. As she saw Master Git traveling down the path, she ran to meet him.

“It is an honor to meet you, Master Git!” she said. “I have been studying the UNIX way of designing programs that each do one thing well. Surely I can learn much from you.”

“Surely,” replied Master Git.

“How should I change to a different branch?” asked the programmer.

“Use git checkout.”

“And how should I create a branch?”

“Use git checkout.”

“And how should I update the contents of a single file in my working directory, without involving branches at all?”

“Use git checkout.”

After this third answer, the programmer was enlightened.

Only the Gods

The great historian was trying to unravel the intricacies of an incorrect merge that had happened many months ago. He made a pilgrimage to Master Git to ask for his help.

“Master Git,” said the historian, “what is the nature of history?”

“History is immutable. To rewrite it later is to tamper with the very fabric of existence.”

The historian nodded, then asked: “Is that why rebasing commits that have been pushed is discouraged?”

“Indeed,” said Master Git.

“Splendid!” exclaimed the historian. “I have a historical record of a merge commit with two parents. How can I find out which branch each parent was originally made on?”

“History is ephemeral,” replied Master Git, “the knowledge you seek can be answered only by the gods.”

The historian hung his head as enlightenment crushed down upon him.

The Hobgoblin

A novice was learning at the feet of Master Git. At the end of the lesson he looked through his notes and said, “Master, I have a few questions. May I ask them?”

Master Git nodded.

“How can I view a list of all tags?”

“git tag“, replied Master Git.

“How can I view a list of all remotes?”

“git remote -v“, replied Master Git.

“How can I view a list of all branches?”

“git branch -a“, replied Master Git.

“And how can I view the current branch?”

“git rev-parse --abbrev-ref HEAD“, replied Master Git.

“How can I delete a remote?”

“git remote rm“, replied Master Git.

“And how can I delete a branch?”

“git branch -d“, replied Master Git.

The novice thought for a few moments, then asked: “Surely some of these could be made more consistent, so as to be easier to remember in the heat of coding?”

Master Git snapped his fingers. A hobgoblin entered the room and ate the novice alive. In the afterlife, the novice was enlightened.

The Long and Short of It

Master Git and a novice were walking along a bridge.

The novice, wanting to partake of Master Git’s vast knowledge, said: “git branch --help“.

Master Git sat down and lectured her on the seven forms of git branch, and their many options.

They resumed walking. A few minutes later they encountered an experienced developer traveling in the opposite direction. He bowed to Master Git and said “git branch -h“. Master Git tersely informed him of the most common git branch options. The developer thanked him and continued on his way.

“Master,” said the novice, “what is the nature of long and short options for commands? I thought they were equivalent, but when that developer used -h you said something different than when I said --help.”

“Perspective is everything,” answered the Master.

The novice was puzzled. She decided to experiment and said “git -h branch“.

Master Git turned and threw himself off the railing, falling to his death on the rocks below.

Upon seeing this, the novice was enlightened.

List Out of Lambda

2013-03-30T14:00:00Z

If you ignore the practical issues of computers like size, weight, cost, heat, and so on, what do you really need in a programming language? Let’s play around with this question.

To understand this post you’ll need a basic understanding of how functions in Javascript work. If you can look at this code and understand what it prints, you’re good to go:

var x = 10;

var f = function(y) {
    console.log(x);
    console.log(y);
}

var g = f;

f(1);
g(2);

This blog post is a thought exercise. It’s not something you’d ever use for real code. But just like a guitarist practices scales that she won’t ever play in a song, we programmers should be exercising our brains every so often.

I’m going to use Javascript for the examples. Any language with first class functions and lexical scoping (basically: closures) will work. The examples would be prettier in a Lisp, but some people would be turned off by the syntax and miss out on some interesting ideas. Feel free to port the code if it bothers you.

If you’ve already seen this kind of thing before (maybe you’ve gone through The Little Schemer or SICP) you may want to just skim the code here and look for anything new.

If you haven’t seen anything like this, then you’re in for a treat! It’s all going to look extremely weird the first time you see it. Go slowly and make sure you understand each piece fully before moving on to the next. These concepts may be unintuitive, but they’re built from very simple pieces.

Finally: if you get stuck, don’t worry. Tracing out the execution of a function on paper can be a good way to wrap your brain around it (I recommend investing in a good lap desk for comfy reading and writing). If that doesn’t work, just close the window and come back tomorrow. Sometimes new concepts need a while to rattle around in your brain before they click into place.

Lists

Let’s get started. One of the most common things we do as programmers is grouping data together. Javascript has “arrays” built in to the language for this:

var names = ["Alice", "Bob", "Candice"];

What if Javascript didn’t come with arrays included? Could we create them (or something like them) ourselves?

To answer this, let’s think about the bare minimum we’d need to “bootstrap” something like an array. There are a number of ways to do this, but we’re going to look at one in particular.

We’ll call our array-like thing a “list”. To make it work, we need four parts:

The concept of “the empty list”.
A way to add an element to the front of a list.
A way to take a list and get the first element.
A way to take a list and get everything but the first element.

If we have those four things, we can build on top of them to do anything else we might want. For example: to make a list of one item, you add that item to the front of the empty list.

Let’s narrow this down further. There are lots of ways you could implement those four things — I’m going to use functions. Let’s sketch out an outline:

var empty_list = null;

var prepend = function(el, list) {
    // ...
};

var head = function(list) {
    // ...
};

var tail = function(list) {
    // ...
};

var is_empty = function(list) {
    // ...
};

Here are the descriptions of each of these items.

The empty_list is a special value that represents a list of zero elements. It can be anything, so for now we’ll use null (we’ll revisit this later).

prepend(1, some_list) will return a new list that looks like the old one, but with 1 stuck onto the front of it. So if we want to create a list of the numbers 1 and 2 we can say prepend(1, prepend(2, empty_list)) or “prepend one to the result of prepending 2 to the empty list”.

head(some_list) will return the first element in the list. Calling it on the empty list will be undefined, so we’ll just be very careful not to do that!

tail(some_list) will return a new list that’s like the one we gave it, but with the first element removed. Again, calling this on an empty list will make things explode.

is_empty(some_list) will return true if the list given to it is the empty list, and false otherwise.

Once we have those four functions (plus the special empty list value) we can start building on top of them, so let’s figure out how to make them!

List Out of If

If you haven’t seen anything like this before, you might think it’s time to start creating Javascript Objects. That’s certainly one way to do it.

Since this post is a thought experiment in what we actually need, though, let’s try to avoid using big language features (like Objects) unless we absolutely can’t avoid it.

So if we don’t want to use other language features yet, what are we left with? Well so far our skeleton only has functions (and null), so let’s try those!

Here’s the first working revision of the building blocks of lists:

var empty_list = null;

var prepend = function(el, list) {
    return function(command) {
        if (command === "head") {
            return el;
        } else if (command === "tail") {
            return list;
        }
    }
};

var head = function(list) {
    return list("head");
};

var tail = function(list) {
    return list("tail");
};

var is_empty = function(list) {
    return list === null;
};

Go ahead and paste that into a browser console and play with it:

var e = empty_list;

console.log(is_empty(e));
// true

var names = prepend("Alice",
                    prepend("Bob",
                            prepend("Candice",
                                    empty_list)));

console.log(is_empty(names));
// False

console.log(head(names));
// Alice

console.log(tail(names));
// Some function representing the list of ("Bob", "Candice")

console.log(head(tail(names)));
// Bob

But Where is the Data?

Did the definitions of those functions surprise you? Lists seem like such an important, object-oriented concept, but there only appear to be functions here!

Let’s look at how this actually works. First of all, the “empty list” concept is pretty straightforward:

var empty_list = null;

var is_empty = function(list) {
    return list === null;
};

We could have picked any arbitrary value here. null seemed appropriate, so I used that.

Now on to the meat of things: prepend.

var prepend = function(el, list) {
    return function(command) {
        if (command === "head") {
            return el;
        } else if (command === "tail") {
            return list;
        }
    }
};

This is where the real magic happens. Let’s think through it.

First of all, we know that when you prepend something to a list, you’re going to get a (new) list back. So whatever prepend returns must be a list.

Looking at the code, we can see it returns a function. So in our little thought experiment, a list is actually a Javascript function under the hood!

So what do we need to do with lists (aside from empty checking, which we’ve already covered)? Well, we need to be able to get the head and the tail. When we call prepend(h, t), we happen to be conveniently specifying the head and tail as the arguments! So in prepend we return a function that knows how to return its own head or tail when asked.

So a “list” is “a function that knows how to return its own head or tail when asked”. So our head and tail functions just need to ask nicely!

var head = function(list) {
    return list("head");
};

var tail = function(list) {
    return list("tail");
};

That’s it! We’ve created lists in 23 lines of code without using any fancy things like Objects. Before you move on, make sure you really understand why this works. Write out a few examples on paper.

var empty_list = null;

var prepend = function(el, list) {
    return function(command) {
        if (command === "head") {
            return el;
        } else if (command === "tail") {
            return list;
        }
    }
};

var head = function(list) {
    return list("head");
};

var tail = function(list) {
    return list("tail");
};

var is_empty = function(list) {
    return list === null;
};

Building on the Foundations

Now that we have lists, let’s implement a few common things on top of them as practice.

map

A common thing to do to a list is to create a new list by looping through it and doing something to each item. This is called “map”:

var map = function(fn, l) {
    if (is_empty(l)) {
        return empty_list;
    } else {
        return prepend(fn(head(l)), map(fn, tail(l)));
    }
};

If you’re not used to recursive definitions like this, you may way to take a few minutes and try to work out how it works. Here’s an example:

var square = function(x) {
    return x * x;
}
var numbers = prepend(1, prepend(2, prepend(3, empty_list)));

var squared_numbers = map(square, numbers);
// map(square, [1, 2, 3])
// prepend(square(1), map(square, [1, 2, 3]))
// prepend(square(1), prepend(square(2), map(square, [3])))
// prepend(square(1), prepend(square(2), prepend(square(3), map(square, []))))
// prepend(square(1), prepend(square(2), prepend(square(3), [])))
// prepend(square(1), prepend(square(2), prepend(9, [])))
// prepend(square(1), prepend(square(2), [9]))
// prepend(square(1), prepend(4, [9]))
// prepend(square(1), [4, 9])
// prepend(1, [4, 9])
// [1, 4, 9]

I’m using brackets here to represent lists, but remember that these aren’t arrays, but are actually the functions that were returned by prepend.

If you’re still not sure about this, trace out every step of map(square, empty_list) on paper. Then trace out every step of map(square, prepend(10, empty_list)).

Thinking recursively like this takes some practice. I have notebooks filled with pages like this. Experienced guitarists practice new material slowly and methodically — there’s no reason programmers shouldn’t do the same. Watching the function calls expand and contract on paper can help you feel in your gut how these things work in a way that just staring at the words can’t.

filter

We’re going to start moving a bit faster now, but you should still make sure you understand everything completely before moving on. Take as much time as you need. Write things out. Run them. Get a feel for them.

The next “utility” function we’ll build on top of lists is filter, which takes a function and a list, and returns a new list whose elements are those in the original that make the function return true. Here’s an example:

var numbers = prepend(1, prepend(2, prepend(3, empty_list)));
var is_odd = function(x) {
    return x % 2 === 1;
}

filter(is_odd, numbers);
// [1, 3]

Now let’s implement filter:

var filter = function(fn, l) {
    if (is_empty(l)) {
        return empty_list;
    } else if (fn(head(l))) {
        return prepend(head(l), filter(fn, tail(l)));
    } else {
        return filter(fn, tail(l));
    }
};

Take your time. Trace out some examples. Move on when you feel it in your gut.

and, or, not

Let’s take a slight detour to implement a few “helper” functions. Τhese don’t have anything specifically to do with lists, but we’ll need them later.

var not = function(x) {
    if (x) {
        return false;
    } else {
        return true;
    }
};

var and = function(a, b) {
    if (a) {
        if (b) {
            return true;
        } else {
            return false;
        }
    } else {
        return false;
    }
};

var or = function(a, b) {
    if (a) {
        return true;
    } else {
        if (b) {
            return true;
        } else {
            return false;
        }
    }
};

Javascript already has these things built in as !, &&, and ||, of course, but remember that in this thought exercise we’re trying to avoid using extra language features if we don’t need them. How far can we scrape by on just functions and if statements?

One small note: these functions are just normal Javascript functions, which means that and(a, b) will not short-circuit like a && b would. For our purposes here that won’t hurt us, but it’s something to be aware of.

List Out of Lambda

Now that we’ve had a bit more practice, let’s go back to our definition of lists:

var empty_list = null;

var prepend = function(el, list) {
    return function(command) {
        if (command === "head") {
            return el;
        } else if (command === "tail") {
            return list;
        }
    }
};

var head = function(list) {
    return list("head");
};

var tail = function(list) {
    return list("tail");
};

var is_empty = function(list) {
    return list === null;
};

There are a few things about this implementation that bother me. Our goal is to use as few language features as possible, but we’ve actually used quite a few! I count at least five:

Functions
if statements
Strings
Booleans (the true/false result of is_empty)
Equality checking (the === checks)

It turns out we can remove most of those things at the cost of a bit of readability (and more bending of our minds).

Let’s start by rewriting the core three functions to ditch those ugly strings, equality checks, and even the if statement:

var prepend = function(el, list) {
    return function(selector) {
        return selector(el, list);
    };
};

var head = function(list) {
    return list(function(h, t) {
        return h;
    });
};

var tail = function(list) {
    return list(function(h, t) {
        return t;
    });
};

You may want to get a snack before wrapping your brain around this one! There’s no strings, no equality checking, no if statements. But we still have lists!

The prepend functions still returns a function, just like before. Remember that in the last implementation, a “list” was really a function that knew how to give out its head or its tail when asked for them.

This time, we’re inverting the “asking”. In this version, a “list” is “a function that will tell another function about both its head and its tail when asked”. This time the asker gets both pieces, and can decide which one they want to use.

Let’s look at the head function:

head takes a list and says return list(...), which means: “Hey list, I would like you to tell all of your info to this little helper function I’m giving you”.
The list says return ...(el, list), which means: “Okay helper function, here’s my head and my tail, enjoy!”
The helper function that head originally gave was function(h, t) { return h; }. So when the list calls it with the head and the tail as arguments, it returns the head and ignores the tail.
head takes that result and just returns it straight through back to the caller.

tail works exactly the same way, but its helper function returns the second argument (the tail) instead of the first.

That’s it! The equality checking and if statements have disappeared. Can you describe where they’ve gone? What has taken their place?

Before we move on, let’s clean up the idea of the empty list. It’s still using null and equality checking. Let’s remove those and make things a little more uniform.

To do this we’ll need to change the other three functions a bit as well, but if you’ve understood everything so far it shouldn’t be too bad.

var empty_list = function(selector) {
    return selector(undefined, undefined, true);
};

var prepend = function(el, list) {
    return function(selector) {
        return selector(el, list, false);
    };
};

var head = function(list) {
    return list(function(h, t, e) {
        return h;
    });
};

var tail = function(list) {
    return list(function(h, t, e) {
        return t;
    });
};

var is_empty = function(list) {
    return list(function(h, t, e) {
        return e;
    });
};

We’ve now made lists a bit smarter. In addition to telling the helper function their head and tail, they also tell it “am I the empty list?”. We’ve modified the helpers head and tail to accept (and ignore) this extra argument.

We then modified is_empty to work just like head and tail.

Finally, we’ve redefined empty_list to match the rest of the lists instead of being a special, magic value. The empty list is now just like a normal one: it’s a function that takes an “asker” and tells that asker “Hey, my head and tail are undefined and I am the empty list”.

I used undefined here which is technically another language feature because it’s easier to read. Feel free to replace it with anything you want to make it more pure. Since we’re being very careful to never call head or tail on the empty list those values will never be seen anyway.

So after all that, we’ve finally implemented the building blocks of lists with only two things:

Functions.
true and false for empty lists.

If you’re up for a challenge, think about whether you could remove that second item (and if so, are you really removing it, or just using certain features of Javascript implicitly instead of explicitly?).

A Brief Intermission

Let’s take a minute to reflect on all the code we’ve seen so far. First, we have an implementation of lists that uses only functions and booleans:

var empty_list = function(selector) {
    return selector(undefined, undefined, true);
};

var prepend = function(el, list) {
    return function(selector) {
        return selector(el, list, false);
    };
};

var head = function(list) {
    return list(function(h, t, e) {
        return h;
    });
};

var tail = function(list) {
    return list(function(h, t, e) {
        return t;
    });
};

var is_empty = function(list) {
    return list(function(h, t, e) {
        return e;
    });
};

From this point on, we can now ignore the details of how lists are implemented. As long as we have head, tail, and prepend we don’t need to worry about what lists actually are under the hood.

We also built a few helper functions on top of this foundation:

var not = function(x) {
    if (x) {
        return false;
    } else {
        return true;
    }
};

var and = function(a, b) {
    if (a) {
        if (b) {
            return true;
        } else {
            return false;
        }
    } else {
        return false;
    }
};

var or = function(a, b) {
    if (a) {
        return true;
    } else {
        if (b) {
            return true;
        } else {
            return false;
        }
    }
};

var map = function(fn, l) {
    if (is_empty(l)) {
        return empty_list;
    } else {
        return prepend(fn(head(l)), map(fn, tail(l)));
    }
};

var filter = function(fn, l) {
    if (is_empty(l)) {
        return empty_list;
    } else if (fn(head(l))) {
        return prepend(head(l), filter(fn, tail(l)));
    } else {
        return filter(fn, tail(l));
    }
};

Before you move on, make sure all of this code is crystal clear. Come back tomorrow if you need to let it sink in. We’re about to go a lot deeper into the rabbit hole, so make sure you’re ready.

Numbers

If you look at the definitions of prepend, head, and tail, they’re pretty mind-bending. However, the definitions of map and filter are much more straightforward.

This is because we encapsulated the implementation of lists into the first four functions. We did all the hard work of building lists out of almost nothing at all and hid it behind that simple prepend, head, and tail interface.

The idea of creating things from simple pieces and abstracting them into “black boxes” is one of the most important parts of both computer science and programming, so let’s take it a step further and get some more practice by implementing numbers.

What is a Number?

For this blog post we’re only going to concern ourselves with non-negative integers. Feel free to try extending all this to include negative integers if you want more.

How can we represent a number? Well we could obviously use Javascript numbers like 14, but that’s not very fun, and we’re trying to minimize the number of language features we use.

One way to represent a number is a list whose length is the number. So we could say that [1, 1, 1] means “three”, ["cats", null] means “two”, and [] means “zero”.

The elements themselves don’t really matter, so let’s just pick something we already have: the empty list! Let’s write out a few to get a feel for this:

var zero = empty_list;
// []

var one = prepend(empty_list, empty_list);
// [ [] ]

var two = prepend(empty_list, prepend(empty_list, empty_list));
// [ [], [] ]

inc, dec

We’re going to want to do things with our numbers, so let’s start writing things that work with this “list of things” representation of numbers.

Our basic building blocks are going to be inc and dec (increment and decrement).

var inc = function(n) {
    return prepend(empty_list, n);
};

var dec = function(n) {
    return tail(n);
};

To add 1 to a number, we just push another element on the list. So inc(inc(zero)) means “two”.

To subtract 1, we just pop off one of the elements: dec(two) means “one” (remember we’re ignoring negative numbers).

is_zero

When we started working with lists we used is_empty a lot, so it’s probably a good idea to create an is_zero function at this point:

var is_zero = function(n) {
    return is_empty(n);
};

Zero is just represented by the empty list, so this one is easy!

add

Adding one is easy, but we’re probably going to want to add arbitrary numbers together. Now that we have inc and dec this is actually pretty easy:

var add = function(a, b) {
    if (is_zero(b)) {
        return a;
    } else {
        return add(inc(a), dec(b));
    }
};

This is another recursive definition. When adding two numbers, there are two possibilities:

If b is zero, then anything plus zero is zero, so we can just return a.
Otherwise, adding a + b is the same as adding (a + 1) + (b - 1).

Eventually b will “bottom out” and return a (which has been steadily getting bigger as b got smaller).

Notice how we didn’t say anything about lists here! The “numbers are lists under the hood” idea has been encapsulated behind is_zero, inc, and dec, so we can ignore it and work at the “number” level of abstraction from here on out.

sub

Subtraction is similar to addition, but instead of increasing a as b gets smaller, we decrease them both together:

var sub = function(a, b) {
    if (is_zero(b)) {
        return a;
    } else {
        return sub(dec(a), dec(b));
    }
};

Now we can say something like add(two, sub(three, two)) and the result will be a representation of “three” in our system (which, of course, is a list of three elements).

Pause for a minute now and remember that underneath numbers are lists, and underneath lists there’s nothing but functions. We can add and subtract integers and underneath it all it’s just functions shuffling around, expanding into other functions and contracting as they’re called, and this writhing mass of lambdas somehow ends up representing 1 + 1 = 2. That’s pretty cool!

mul, pow

For practice let’s create a way to multiply numbers:

var mul = function(a, b) {
    if (is_zero(b)) {
        return zero;
    } else {
        return add(a, mul(a, dec(b)));
    }
};

Building on add makes this pretty easy. 3 * 4 is the same as 3 + 3 + 3 + 3 + 0. Trace out the execution on paper if things are starting to get away from you. Carry on when you’re ready.

pow (“power” or exponential) follows a similar structure as mul, but instead of adding together the copies we multiply them, and our base is one instead of zero:

var pow = function(a, b) {
    if (is_zero(b)) {
        return one;
    } else {
        return mul(a, pow(a, dec(b)));
    }
};

is_equal

A common thing to do with numbers is to check if two are equal, so let’s write that:

var is_equal = function(n, m) {
    if (and(is_zero(n), is_zero(m))) {
        return true;
    } else if (or(is_zero(n), is_zero(m))) {
        return false;
    } else {
        return is_equal(dec(n), dec(m));
    }
};

There are three cases here:

If both numbers are zero, they are equal.
If only one number is zero (but not both, or the first case would have caught it), then they are not equal.
Otherwise, subtract one from each and try again.

When calling this function with two non-zero numbers, both will be decremented in tandem until one of them bottoms out at zero first, or until they bottom out at the same time.

less_than, greater_than

We can take a similar approach to implementing less_than:

var less_than = function(a, b) {
    if (and(is_zero(a), is_zero(b))) {
        return false;
    } else if (is_zero(a)) {
        return true;
    } else if (is_zero(b)) {
        return false;
    } else {
        return less_than(dec(a), dec(b));
    }
};

The difference here is that we have four cases.

If both numbers are zero, then a is not less than b.
Otherwise if a is zero (and we know b isn’t) then yes, a is less than b.
Otherwise if b is zero (and we know that a isn’t) then no, a cannot be less than b (remember that we’re ignoring negative numbers).
Otherwise decrement both and try again.

Once again, both numbers race to bottom out, and the outcome is decided by which one bottoms out first.

We could do something similar for greater_than, but let’s do it the easy way instead:

var greater_than = function(a, b) {
    return less_than(b, a);
};

div, mod

Once we have less_than we’re ready to implement division and remainders:

var div = function(a, b) {
    if (less_than(a, b)) {
        return zero;
    } else {
        return inc(div(sub(a, b), b));
    }
};

var rem = function(a, b) {
    if (less_than(a, b)) {
        return a;
    } else {
        return rem(sub(a, b), b);
    }
};

This pair is a bit more complicated than the three other basic operations because we can’t deal with negative numbers. Make sure you understand how it works.

Full Circle

At this point, we have a (very basic) working system of numbers built on top of lists. Let’s chase our tails a bit and implement a few more list functions that use numbers.

nth

To get the Nth item in a list, we just pop things off of it as we decrement N until we hit zero:

var nth = function(l, n) {
    if (is_zero(n)) {
        return head(l);
    } else {
        return nth(tail(l), dec(n));
    }
};

Under the hood there are really two lists getting things popped off as we iterate, because n is a number, which is a list, and dec pops things off. But it’s much easier to read when we’ve abstracted away the representation of numbers, don’t you think?

drop, take

Two handy functions for working with lists are drop and take.

drop(l, three) will return the list with the first three elements removed.

take(l, three) will return the list containing only the first three elements.

var drop = function(l, n) {
    if (is_zero(n)) {
        return l;
    } else {
        return drop(tail(l), dec(n));
    }
};

var take = function(l, n) {
    if (is_zero(n)) {
        return empty_list;
    } else {
        return prepend(head(l), take(tail(l), dec(n)));
    }
};

slice

Slicing a list is easy now that we have drop, take, and the ability to subtract numbers:

var slice = function(l, start, end) {
    return take(drop(l, start), sub(end, start));
};

First we drop up to the start, then take enough to get us to the end.

length

We can define length recursively like everything else:

var length = function(l) {
    if (is_empty(l)) {
        return zero;
    } else {
        return inc(length(tail(l)));
    }
};

The length of the empty list is zero, and the length of any non-empty list is one plus the length of its tail.

If your mind isn’t in knots by this point, consider the following:

Lists are made of functions.
Numbers are made of lists whose length represents the number.
length is a function that takes a list (which is a function) and returns the length as a number (a list whose length represents the number).
We only just now got around to defining length even though we’ve been using numbers (which use the length of a list to represent a number) for a while now!

Are you dizzy yet? If not:

var mylist = prepend(empty_list,
                     prepend(empty_list,
                             empty_list));
var mylistlength = length(mylist);

mylist is a list of two empty lists.

mylistlength is the length of mylist…
which is “two”…
which is represented by a list of two empty lists…
which is mylist itself!

Conclusion

If you liked this twisty little story, I highly recommend you check out The Little Schemer. It was one of the first books that really changed how I thought about programming. Don’t be put off by the fact that it uses Scheme — the language doesn’t really matter.

I’ve also created a gist with all the code. Feel free to fork it and use it for practice.

You could add some more utility functions for practice writing recursively:

append to add an item to the end of a list.
concat to concatenate two lists.
min and max which take two numbers and return the minimum/maximum one.
remove, which is like filter except it only leaves the elements that return false for the predicate.
contains_number, which checks if a specific number is inside a list of numbers.

Or if you want something more challenging, try implementing bigger concepts on top of the current ones:

Negative numbers.
Non-negative rational numbers.
Negative rational numbers.
Association lists (a data structure that associates keys with values).

Remember: the point is not to create something that runs well on a physical computer. Instead of thinking about how to make a particular combination of transistors and circuits have the right voltages, think about “computing” in the beautiful, perfect, abstract sense.

The Caves of Clojure: Part 7.1

2012-10-15T09:50:00Z

This post is part of an ongoing series. If you haven’t already done so, you should probably start at the beginning.

This entry corresponds to the beginning of post seven in Trystan’s tutorial.

If you want to follow along, the code for the series is on Bitbucket and on GitHub. Update to the entry-07-1 tag to see the code as it stands after this post.

It’s been a while since the last post, but I’ve been taking care of things and hopefully should be able to write a bit more now.

This post is going to be short. It’ll cover a relatively self-contained but interesting bit of Trystan’s seventh post. The rest of it will be covered in the next entry.

Summary
Region Mapping
Visualization
Results

Summary

In Trystan’s seventh post he adds vertical levels and stairs connecting them. I’m going to cover the first part of that now: mapping out regions.

There’s been a bit of refactoring since my last post which I’m not going to cover. If you want to see what changed, diff the tags in your VCS of choice.

Region Mapping

In order to decide where to place stairs, Trystan maps out “regions” of contiguous, walkable tiles after he generates and smooths the world. I’m going to do the same thing.

My goal is to create a “region map”, which is a map of coordinates to region numbers. For example, consider the following tiny world map:

..##..
..#...
..#.##
..#.#.

There are three distinct regions in this map:

11##22
11#222
11#2##
11#2#3

So the region map would look like:

; x y  region
{[0 0] 1
 [1 0] 1
 [4 0] 2
 [5 0] 2
 ...
 [5 3] 3}

This makes it easy to tell which region a particular tile is in (if any).

As usual, I’ll start with a few helper functions. These two functions are just for convenience and readability:

(def all-coords
  (let [[cols rows] world-size]
    (for [x (range cols)
          y (range rows)]
      [x y])))

(defn get-tile-from-level [level [x y]]
  (get-in level [y x] (:bound tiles)))

The all-coords function simply returns a lazy sequence of [x y] coordinates representing every coordinate in a level.

get-tile-from-level encapsulates the act of pulling out a tile from a level given an [x y] coordinate. This is helpful because of the way I’m storing tiles (note the ugly [y x]).

Next up is a function that filters a set of coordinates to only contain those that are actually walkable in the given level (i.e.: those that don’t contain a wall tile):

(defn filter-walkable
  "Filter the given coordinates to include only walkable ones."
  [level coords]
  (set (filter #(tile-walkable? (get-tile-from-level level %))
               coords)))

This uses the get-tile-from-level function as well as tile-walkable? from world.core.

Next is a function to take a coordinate and return which of its neighboring coordinates are walkable:

(defn walkable-neighbors
  "Return the neighboring coordinates walkable from the given coord."
  [level coord]
  (filter-walkable level (neighbors coord)))

This one is almost trivial, but I like building up functions in small steps like this because it’s easier for me to read.

Now we come to a function with a bit more meat. This is the core of the “flood fill” algorithm I’m going to use to fill in the region map.

(defn walkable-from
  "Return all coordinates walkable from the given coord (including itself)."
  [level coord]
  (loop [walked #{}
         to-walk #{coord}]
    (if (empty? to-walk)
      walked
      (let [current (first to-walk)
            walked (conj walked current)
            to-walk (disj to-walk current)
            candidates (walkable-neighbors level current)
            to-walk (union to-walk (difference candidates walked))]
        (recur walked to-walk)))))

In a nutshell, this function loops over two sets: walked and to-walk.

Each iteration it grabs a coordinate from to-walk and sticks it into the walked set. It then finds all the coordinates it can walk to from that coordinate using a helper function. It uses clojure.set/difference to determine which of those are new (i.e.: still need to be walked) and sticks them into the to-walk set. Then it recurs.

The code for this is surprisingly simple and easy to read. It’s mostly just shuffling things between sets. Eventually the to-walk set will be empty and walked will contain all the coordinates that we want.

Finally comes the function to create the region map for an entire level:

(defn get-region-map
  [level]
  (loop [remaining (filter-walkable level all-coords)
         region-map {}
         n 0]
    (if (empty? remaining)
      region-map
      (let [next-coord (first remaining)
            next-region-coords (walkable-from level next-coord)]
        (recur (difference remaining next-region-coords)
               (into region-map (map vector
                                     next-region-coords
                                     (repeat n)))
               (inc n))))))

This function also uses Clojure sets to its advantage. Once again, I loop over a couple of variables.

remaining is a set containing all the coordinates whose regions has not yet been determined.

Each iteration it pulls off one of the remaining coordinates. Note that I’m using first to do this. remaining is a set, which is unordered, so first effectively could return any element in the set. For this loop that doesn’t matter, but it’s important to be aware of if you’re going to use the same strategy.

After pulling off a coordinate, it finds all coordinates walkable from that coordinate with the walkable-from flood-fill function. It removes all of those from the remaining set, shoves them into the region map, and increments the region number before recurring.

Visualization

I’m going to save the rest of Trystan’s seventh post for another entry, but since this one ended up pretty short I’m also going to go over visualizing the region map I’ve just created.

First I need to generate the region map when I create the world, and attach it to the world itself so we can access it from other places:

(defn random-world []
  (let [world (->World (random-tiles) {})
        world (nth (iterate smooth-world world) 3)
        world (populate-world world)
        world (assoc world :regions (get-region-map (:tiles world)))]
    world))

The last line in the let is where it gets generated. It’s pretty straightforward.

I’d like to be able to toggle the visualization of regions off and on, so I’m going to introduce a new concept to the game: “debug flags”.

I updated the Game record to include a slot for these flags:

(defrecord Game [world uis input debug-flags])

I then updated the new-game function to initialize them (currently there’s only one) to default values:

(defn new-game []
  (map->Game {:world nil
              :uis [(->UI :start)]
              :input nil
              :debug-flags {:show-regions false}}))

The user needs a way to toggle them. For now I’ll just bind it to a key. In the future I could make a debug UI with a nice menu.

(defmethod process-input :play [game input]
  (case input
    :enter     (assoc game :uis [(->UI :win)])
    :backspace (assoc game :uis [(->UI :lose)])
    \q         (assoc game :uis [])

    \h (update-in game [:world] move-player :w)
    \j (update-in game [:world] move-player :s)

    ; ...

    \R (update-in game [:debug-flags :show-regions] not)

    game))

Now when the user presses R (Shift and R) it will toggle the state of the :show-regions debug flag in the game.

All that’s left is to actually draw the regions somehow. First, we only want to do this if :show-regions is true. I edited the :play UI’s drawing function to do this:

(defmethod draw-ui :play [ui game screen]
  (let [world (:world game)
        {:keys [tiles entities regions]} world
        player (:player entities)
        [cols rows] (s/get-size screen)
        vcols cols
        vrows (dec rows)
        origin (get-viewport-coords game (:location player) vcols vrows)]
    (draw-world screen vrows vcols origin tiles)
    ; ******************
    (when (get-in game [:debug-flags :show-regions])
      (draw-regions screen regions vrows vcols origin))
    ; ******************
    (doseq [entity (vals entities)]
      (draw-entity screen origin vrows vcols entity))
    (draw-hud screen game)
    (draw-messages screen (:messages player))
    (highlight-player screen origin player)))

The marked lines are the only new ones. I’m going to draw regions after/above the world tiles (so they’ll show up at all) but before/below the entities (so we can still see what’s going on).

Drawing the regions is fairly simple, if a bit tedious:

(defn draw-regions [screen region-map vrows vcols [ox oy]]
  (letfn [(get-region-glyph [region-number]
            (str
              (nth
                "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
                region-number)))]
    (doseq [x (range ox (+ ox vcols))
            y (range oy (+ oy vrows))]
      (let [region-number (region-map [x y])]
        (when region-number
          (s/put-string screen (- x ox) (- y oy)
                        (get-region-glyph region-number)
                        {:fg :blue}))))))

For now, bad things will happen if we have more than 62 regions in a single level. In practice I usually end up with about 20 to 30, so it’s not a big deal.

To sum up this function: it iterates through every coordinate in the level that’s displayed in the viewport, looks up its region number in the region map, and draws the appropriate letter if it has a region number.

Results

Now that I’ve got a way to visualize regions it becomes much easier to check whether they’re getting set correctly. Here’s an example of what it looks like when you toggle :show-regions with R:

As you can see, the small, closed off areas have their own numbers, while the larger regions sprawl across the map.

You can view the code on GitHub if you want to see the end result.

The next article will finish Trystan’s seventh post by adding multiple z-levels to the caves.

Why I Two-Space

2012-10-12T10:10:00Z

If you look at the source code for this blog, you might notice that all my blog posts (written in Markdown) have two spaces after every period.

Every so often this Slate article makes the rounds and annoys me. This time I figured I’d write a blog post/rant to get it off my chest once and for all: two-spacing is equal or superior to one-spacing in all non-trivial ways.

The Arguments for One-Spacing
Effort
Two-Spacing is Ugly
- Source and Presentation
- Typewriters
Power
Final Score

The Arguments for One-Spacing

If you read the aforementioned Slate article you’ll see that it presents a total of three arguments in favor of single-spacing after a period:

Many professional typographers find two-spacing ugly (though they have no actual evidence of its effects on readability).
It’s less work to press the space bar once instead of twice.
It’s pretty much arbitrary anyway, so why not?

You might also infer from the article’s tone that “you get to feel superior to those Neanderthals that use two spaces” is another argument in favor of it, but I’ll leave that one out because it can go both ways.

Let’s go through these arguments one by one and see how they hold up.

Effort

I don’t think the “it’s more effort to press the space bar twice” argument is at all compelling. The extra space may account for around half a percent of the keystrokes you type, depending on how long your sentences tend to run (mine usually end up fairly long, as you can see).

Not only is it not a large portion of your keystrokes, but the space bar has your two strongest digits dedicated solely to it! If any fingers are going to wear out from typing, it won’t be your thumbs.

You could get pedantic and mention increased file size as a disadvantage of two spacing, but let’s not quibble about a few bytes when I can hold 32 gigabytes on an SD card the size of a postage stamp.

Two-Spacing is Ugly

The Slate article is correct is saying that many professional typographers think two-spacing is ugly. My copy of The Elements of Typographic Style agrees. However, there’s more to the issue than a single blanket rule.

Source and Presentation

If you’re reading this in a web browser and look closely, you’ll notice that there’s only one space between each sentence. I said I used two, so what happened?

Web browsers, by default, collapse successive whitespace into a single space when it renders the HTML. You could put a thousand spaces between sentences in the source and it would still come out single-spaced.

Another widely-used format, LaTeX, splits the difference and actually uses somewhere between one and two spaces (by default).

The key idea here is that what you type and what the end user actually reads are two different things. They don’t need to be bound together. It’s possible to type two spaces but get one in your output (or in LaTeX’s case: an even more pleasing “one and a bit”).

If you’re using a WYSIWYG editor like Microsoft Word this may not be the case. For the high school students typing up papers for class: sure, go ahead and single-space. But if you’re still using Word to type up things like books, long blog posts, or technical documentation, you’re doing yourself a disservice. Learn to use a system like LaTeX so your source and rendered output aren’t locked together.

This means that “two-spacing looks ugly” doesn’t imply “you should not type two spaces when you write”. It actually implies “you should use a system that results in single-spacing when rendered”, and most of the common ones today will do exactly that.

Typewriters

So we’ve seen that the “extra spaces take more effort” argument isn’t convincing, and that “two-spacing in the final output is ugly” doesn’t prevent you from using two spaces in the input.

But so far I haven’t given you any reason for using two spaces. That’s the Slate article’s third argument: “it’s arbitrary anyway, so you may as well use one”.

Let’s fix that by examining the common holier-than-thou put-down of “two-spacing was useful back when people used typewriters, you dinosaur!”.

To his credit, the Slate author correctly points out that it’s not the fact that people used typewriters that made two-spacing popular, it was the fact that typewriters used monospaced fonts. Most people miss that logical leap.

Unfortunately he follows that up with:

Here’s the thing, though: Monospaced fonts went out in the 1970s.

For the average person typing up a school paper here and there, sure. But for many people doing a large amount of writing for LaTeX books and papers, technical documentation, code comments, mailing lists, blog posts, and lots of other things, it’s simply wrong for one big reason:

Text editors use monospaced fonts!

It doesn’t matter what editor you use. Vim, Emacs, TextMate, Sublime Text, Eclipse, Gedit, Notepad++? All of them use monospaced fonts.

Going back to the typewriter quip, this means that if people used two spaces when writing on typewriters because it looked better, then using two spaces in a text editor will look better. And we know that because there’s a distinction between source and presentation in non-WYSIWYG contexts, we can use separate strategies for each.

We can have our cake and eat it too! We can type two spaces after a period to make our text look better as we write, revise, and edit it, and then render it to single-spacing (or “space-and-a-half-ing”) to give our readers a beautiful reading experience with pleasant spacing.

So now two-spacing has a real advantage over single-spacing. That’s enough to make it preferable. But let’s look at one more advantage for power users, just to seal the deal.

Power

If you use Vim to edit text, you’re probably familiar with its “text objects”. Text objects are what let you move and act on whole chunks of text at a time. For example, instead of deleting a word letter-by-letter you can use daw to “delete around word”.

Vim comes with a “sentence” text object built-in. You can move around your document sentence-by-sentence with ( and ), and yank/delete/change/etc entire sentences with cas (“change around sentence”) and so on.

You can probably guess where this is going. If you single-space sentences Vim will do its best to “do the right thing”, but inevitably gets tripped up when you’ve got punctuation in your sentence. For example:

Bob started speaking. Hello, Mr. Smith! How are you today?
                                    ^
                                    cursor

What happens when you tell Vim to “delete around sentence” now?

Bob started speaking. Hello, Mr. How are you today?
                                  ^
                                  cursor

Well that’s not right! Vim can’t easily tell the difference between the period after “Mr” and the end of a sentence. What happens if you type your prose with two-spacing instead?

Bob started speaking.  Hello, Mr. Smith!  How are you today?
                                     ^
                                     cursor
Bob started speaking.  How are you today?
                       ^
                       cursor

This time Vim is able to delete the sentence correctly! Note that you’ll need to make sure to set cpo+=J in your ~/.vimrc file to tell Vim “don’t worry, I’m using two spaces like a sane person” for this to work.

Two-spacing provides more semantic information, which means that software can parse and work with it more easily. I’m sure Emacs has something similar, and if you or someone else ever needs to parse your writing programatically they’ll have an easier time.

Final Score

To recap, the arguments for single-spacing are:

Two-spacing is ugly in proportional fonts.
It’s less work to press the space bar once instead of twice.
It’s pretty much arbitrary anyway, so why bother with two?

Number 1 is irrelevant, because writing and rendering are (except in trivial cases) two orthogonal activities.

Number 2 isn’t very convincing.

Number 3 is false, because two-spacing gives you two advantages over one-spacing:

It looks better in your editor.
It gives you more power when editing and parsing.

So the next time you see that arrogant Slate article, feel free to be arrogant right back. Wield your extra spaces proudly, because they give you both comfort and power!