+++
title = "List Out of Lambda"
snip = "Down the rabbit hole we go!"
date = 2013-03-30T14:00:00Z
draft = false
+++
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:
```javascript
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.
[The Little Schemer]: http://www.amazon.com/dp/0262560992/?tag=stelos-20
[SICP]: http://www.amazon.com/dp/0070004846/?tag=stelos-20
{{% toc %}}
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:
```javascript
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:
```javascript
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:
```javascript
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:
```javascript
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:
```javascript
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`.
```javascript
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!
```javascript
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.
```javascript
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":
```javascript
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:
```javascript
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](http://i.imgur.com/kqu5jy9.jpg). 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:
```javascript
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`:
```javascript
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.
```javascript
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:
```javascript
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:
```javascript
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.
```javascript
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:
```javascript
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:
```javascript
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:
```javascript
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).
```javascript
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:
```javascript
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:
```javascript
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 itself, 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:
```javascript
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:
```javascript
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:
```javascript
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:
```javascript
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`:
```javascript
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:
```javascript
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:
```javascript
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:
```javascript
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.
```javascript
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:
```javascript
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:
```javascript
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:
```javascript
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.
[a gist]: https://gist.github.com/sjl/5277681