Monthly Archives: October 2007

Crumbs of Mind

Here is the Strange New Worlds session from October 18th.

  • 01 – an idea that I want to come back to at shows: Evan and I play solid chords at random every two bars, and Eric does his thing. (And then, as usual, we see where it goes from there). It turned out very jazzy.
  • 02 – all over the place, a “suite” more than a song, and it has some really incredible passages but has trouble holding together as a cohesive whole. In particular, I’m proud of myself for stepping outside my usual box and assigning more things for my hands to do than they are comfortable with.
  • 03 – a song template we’ve been working on
  • 04 – another suite, fools around in a bluesy theme for a while. Starting at about 9 minutes in, it gets moving on a really steady trance, which is quite cool. It also features a good amount of that classical tone that we get sometimes.
  • 05 – short and sweet
  • 06 – Evan the madman
  • 07 – one of our typical sounding songs, pretty funky though.
  • 08 – Crumbs of Mind – my favorite of the session, named after George Crumb whose piece “Black Angels” I quoted during the song. This one is very, very creepy, in a good way. Best with headphones.
  • 09 – Nonstandard Soul – cool and soulful
  • 10 – another funky one
  • 11 – 3 and a half minutes of noodling (that’s what I get for not editing), followed by an interesting but not great slow, trippy jazzish thing.
  • 12 – we were searching for a direction to take the last song. Evan said “one last freakout?”, and I said “something elegant”… the result was a little bit of both.

I was pushing various sorts of experimentation this session, since I had been growing a little tired of our “usual sound” (not that I think it’s bad, of course, but I hear it for three hours twice a week!). It turned out really well. I like all the tracks, and most of them are pretty unique, both in terms of what this band does and what music is like in general.

Computing without a middle

Here’s an uncontrived scenario:

You have just recieved two Haskell modules from Microsoft (so there’s no way you will ever get the source). One of the modules is called Greeter, the other called MeaningOfLife. MeaningOfLife was written by God, for his own record keeping, in case he ever forgot. The rumor is that Microsoft purchased a portal from hell to heaven and sent spies to recover the MeaningOfLife module from him.

God doesn’t call himself “God”. He has a private name, and only he and his wife the “virgin” know it. God has another module, which he keeps locked up in a divine safe, which is a function that returns the encryption key for the meaning of life when given his name as input. Its type signature is:

    getEncryptionKey :: Name -> Divine EncryptionKey

(God keeps all of his computations in the Divine Monad)

You don’t have access to that function, all you have is the seemingly useless user interface function:

    getMeaningOfLife :: (Name -> Divine EncryptionKey) -> Divine String

This function asks for the user’s name, and sends it to the encryption key function which it has been passed, and returns the meaning of life. But it’s even more hopeless for you: you can’t even brute force it, for Name and EncryptionKey are both abstract data types to which you do not have the internal representations.

Discouraged, you look at the other module that Microsoft sent you, Greeter. It was also recovered during the spy mission, one of God’s first Haskell programs when he was learning. It has a single function, which, given the user’s name, friendlily says hello to the user:

    greet :: Name -> Divine ()

But again, you are out of luck, for Name is abstract and we don’t know how to make one.

It seems we are at an impass. We cannot run any of the new code we received, even just to test it, because we cannot create the encryption key generating function for getMeaningOfLife, and we cannot generate names for greet! What do we do?

Why, what’s this? A recent thread on Haskell Cafe explains that the law of excluded middle can be encoded in haskell’s type system as:

    exmid :: (MonadCont m) =>  m (Either (a -> m b) a)

That is, exmid asserts the existence of either a type a or a function which takes an a and returns anything you want. You could use this if only Divine was an instance of MonadCont. Looking in the docs, you are surprised to find that it is! Of course it is; God has the power to go back in time if something happens that he doesn’t like (in fact the “red button” that begins nuclear war actually just invokes the Modern Age continuation so we can try again. It’s like the reset button on your Nintendo.).

And this provides just what we need. We can finally have the meaning of life! Just:

    divineMain :: Divine ()
    divineMain = do
        em <- exmid                  -- get the function of excluded middle
        case em of
            Right name -> do         -- either a Name exists
                greet name
            Left fn ->  do           -- or a function taking names to Divine EncryptionKeys exists
                putStrLn "Get ready for it: Ready?  Here's the meaning of life!"
                meaningOfLife <- getMeaningOfLife fn
                putStrLn meaningOfLife

(The liftIOs have been omitted for readability)

Your heart racing, you run the program:

Get ready for it: Ready? Here's the meaning of life!
What is your name?  Luke
Hello, Luke, have a nice day.

And it worked! It actually worked! You were friendlily greeted (if you are me).

What happened here is that exmid certainly could not create a Name, how would it have the power to do so? So it couldn’t take the Right branch. All that was left to do is to take the Left branch, coming up with a fake function that claimed to satisfy what was asked of it (in this case, taking a Name to an EncryptionKey), in hopes that it wouldn’t be called (then exmid would get off clean easy). But when we passed that function to getMeaningOfLife, getMeaningOfLife did call it. Exmid noticed that this fake function that it created was passed a Name, which it was previously unable to conjure. Never one to miss an opportunity, exmid jumped back in time and took the Right branch instead, passing the right branch its newly acquired Name.

Put less anthropomorphically, using exmid we glued greet into the “middle” of getMeaningOfLife, where it was least expecting it (okay, I guess that was still anthropomorphic).

So there you have it, the Curry-Howard law of excluded middle is useful; it’s not all abstract theoretical gobbledygook.

For reference, the implementation of exmid follows, some dense abstract theoretical gobbledygook:

   exmid :: (MonadCont m) => m (Either (a -> m b) a)
   exmid = exeither' exmid'
       exmid' f g = either return g =<< callCC (\cc ->
                              return . Left =<< f (cc . Right))
       exeither' e = e (return . Left) (return . Right)

No Total Function from Infinite Sequences of Booleans onto the Integers

Yesterday I found out about a remarkable algorithm which can take any total predicate (function returing true or false) on infinite sequences of bits and find an infinite sequence which satisfies it (and implemented it). It’s a counterintuitive result, since you’d think that you can’t search the (uncountably) infinite space of bit sequences in a finite amount of time, but you can.

This implies some results about how much total functions can encode. For example, there must not be any total function from infinite sequences of bits onto the integers (such that any integer is reachable using a suitable infinite sequence). If there were, you could use this algorithm to decide any predicate on the integers, which would be a far-too-powerful mathematical tool.

But I couldn’t prove it, not without citing the algorithm. Why must there not be any such function, besides that it would make the algorithm incredibly powerful (so powerful that you could prove its impossibility, but that proof method was not good enough for me, because it could have been that the algorithm had an error).

The proof was actually hiding in the proof on sigfpe’s blog, but I couldn’t see it at first. So I’ll give a more explicit version here.

Let f be a total function from sequences of bits onto the integers (f : (Z -> Bool) -> Z). Let df(xs) denote the greatest index that f reads when given the argument xs. Now, for example, choose an xs such that f(xs) is 0. df(xs) is the greatest index that f reads, so f doesn’t depend on anything greater (for this argument), so every sequence with the prefix xs[0..df(xs)] has the value zero.

Now make a binary tree corresponding to the input sequence, where a node is a leaf iff the sequence leading to the node is the shortest prefix that completely determines f‘s output. Every possible extension of the sequence leading up to the leaf maps to the same value, so we informally say that the leaf itself maps to the value (even though the leaf represents a finite sequence and f takes infinite sequences).

This tree has infinitely many leaves, since there must be (at least) one leaf for each integer. And now, just as sigfpe did, invoke the König lemma, “every finitely branching tree with infinitely many nodes has at least one infinite path”. That infinite path represents an input to f for which it will not halt. That is to say, f was not total after all!

Boulder Buy’em Poker

The boulder gamedev club had a card game jam this week. My group made a poker variant. It’s pretty good (it received the high praise from Namaste, “I’m not sure if it’s better than no limit Texas Hold’em”). The game has been dubbed “Boulder Buy’em” by Paul Steinbrecker. Here are the rules.

Each player, as usual, starts with some chips somehow. There’s a dealer button on one of the players, and it rotates clockwise each round.

Something to note while reading this: there is no “dealing”, and players do not receive a new hand each round. Instead they build their hand over the course of multiple rounds.

The round proceeds in several phases:

  1. Ante
  2. Auction
  3. Claims
  4. Discards

The Ante phase is just an ante. Each player puts in a fixed ante.

The Auction phase is quite unlike any other poker game. Cards equal to the number of players are placed on the table, 2 of them face up1, the rest face down. It’s an auction for first choice of cards to put into your hand. The player on the dealer button makes a fixed blind bid (double the Ante in our playtests). Then there is a free auction without ordering (just calling out numbers with the dealer acting as the auctioneer); for cases without a dedicated dealer, it’s possible to use a turn-based auction style. There is no minimum increment for bidding, except as restricted by the chip values (it is perfectly reasonable for the blind to be 10, someone to bid 100, and then someone else bid 105). The winner of the auction pays the amount he bid, everyone else pays nothing. The winner then takes a card from the table of his choice, face up or face down, and the rest of the players take cards from the table in clockwise order.

The Claims phase is much more like a traditional poker hand. Most rounds there will be no claims, but the dealer should make the request for claims each round. The first person to say “claim” after the request initiates a claim. He chooses any number of cards from his hand and places them on the table face down in front of him, optionally in addition to some chips (as an opening bid). Then, proceeding clockwise around the table, each player has the standard options (raise, call, fold). When a player raises or calls, he chooses cards from his hand to put on the table. If the number of cards the player plays exceeds the maximum number of cards anyone has on the table, then it “counts” as a raise in terms of actions: everyone else gets another chance to act. It also counts as a raise if it was a monetary raise, of course. Whenever a player acts, he gets a chance to put more cards on the table face down in front of him, but not to remove any cards.

When the bidding completes, everyone is either folded or has the same amount of money and some cards (not necessarily the same number) on the table (modulo all ins). There is then a showdown. Starting with the last person to bid or raise, proceeding clockwise, a player can show his cards or muck. The best hand takes the whole pot, including the pot built up over the past few rounds from the auction phases. All the cards which were played on the table are reshuffled into the deck, including those of folded players. Players get to keep cards which they never played on the table.

On the Discard phase, all players who have more than seven cards in their hand choose cards to discard down to seven, and the dealer reshuffles those into the deck.

In tournaments, if a player does not have enough for the ante, he pays whatever he can into the ante. No special splitting is necessary in this case (think about it). It is strongly advised to claim that round (because otherwise the player is definitely out).

If the player on the dealer button does not have as much as the blind bid, then the blind bid is equal to the player’s stack and starts from there. That is, if the blind is 50, but the player only has 10, then the blind is considered 10 and it is perfectly reasonable for another player to bid 15.

If a player wishes to sit out, he must sit out until the round after the next claim, so his next ante will be into an empty pot. Harsh and variable, I know. This is necessary to keep player from sitting on a good hand not paying ante until the pot is huge.

1During heads up, only one of the two cards is face up. All the other rules remain the same.

Universal Architecture

It seems that every somewhat-seasoned software architect I talk to has some concept of a “universal architecture”, a term whose definition will become clear after I give an example. For example, at NetDevil on the LEGO project our universal architecture was “interfaces”; that is, every major component of the program was a singleton which implemented this interface base class. Instead of these singletons calling methods on each other, instead they would pass “messages” (structs which were upcast to a generic message base) to an “interface manager” which then delegated them to whichever interface they belonged to, where they then had to be downcast. You’d have to see it to believe it, but it was essentially a poorly-typed equivalent to ordinary method calling.

And the quality of this architecture that makes me write about it today is the fact that it has nothing to do with the game we were writing, or even games in general. I can imagine this engineer saying “every program I write fits into this architecture”. I consider that statement to be the same as the axiom of limitation of size in NBG set theory—if you can say this about an architecture, then it is a worthless architecture (with some exceptions). And here’s why:

There’s a reason that they call the languages we use to write software general-purpose programming languages. They’re supposed to have all the language features you need to write any type of program, and none left over that are only suited to certain types of programs (this is an ideal, but most languages come pretty close). Therefore, any “universal architecture” into which every program fits is a witness to a flaw in the language you are using. But language designers are usually pretty good—they think of an awful lot of patterns and make sure that they fit into the language. So it’s very likely that by using a universal architecture you are either trying to stuff programs which don’t actually fit into it, creating lots of unnecessary engineering problems to cram it in, or you are just duplicating an already existing language feature (as was the case above).

There are some exceptions on both sides of the coin. For example, in C you might have a universal architecture, because C isn’t really a complete language as I see it. You might add an architecture for object-oriented inheritance which has some nice features using macros and whatnot. But then you should just be using C++; they already did it, and they did it pretty well (considering what they had to work with—C :-). Also, I think it’s reasonable for a universal architecture to handle garbage collection, because that’s a nice thing to have for all programs. And most general purpose programming languages have garbage collection these days. So really it’s the same coin: you’re using a language with missing features.

So the next time you write a universal architecture, ask yourself the question “what language feature would solve the problem that this architecture is solving?”. If none, then toss your architecture, and make one more specific to the problem you’re trying to solve right then (otherwise you’ll probably end up soft coding to some extent). If so, then hunt for a language which has that feature; there probably is one. If you can’t find one, look at Perl 6, the language with all possible features (it probably has a library routine which is your program already written—unfortunately, Perl 6 is not completely implemented yet, so join the project! :-). But seriously, there probably is some language with that feature. There may be other reasons that that language is unsuitable, but “I don’t know it” is not really a good reason. If there is a real reason that language is unsuitable, go ahead and design your architecture, but learn about the language that has the feature so you can benefit from the research done while developing that language.

Preach, preach, preach. Really it all comes back to my architectural philosophy: you have to identify the “fundamental algebra” of your program. What is the identifying feature of this problem, the feature that makes its solution nonroutine, the feature that makes me want to design an architecture instead of just using one? As soon as I started thinking in terms of this, my programming productivity skyrocketed, because I realized that there was no such feature, so I stopped designing architectures! “Oh, this program (like most) admits a straightforward OO design.” Unfortunately for the programmers who are so commonly also deep thinkers, most solutions are just routine. And that’s the best way to do them. I suppose that is a merit of Java: it restricts you so much that doing anything but a routine solution is grotesquely hard.

But there is some falsity to be gleaned here. I made it sound like all general purpose programming languages are the same. But, as usual, your solution will heavily depend on the language you’re using. My typical argumentitive antitheses are Java and Haskell, since they are both “pure” along different axes. A straightforward design in Java will bring out the OO essence in your problem, whereas a straightforward design in Haskell will bring out the mathematical essence in your program. When I first started writing in Haskell, I got extremely annoyed by its lack of polymorphism in the OO sense. Say you have this pseudo-C++ program:

    class Animal;   // all typical subclasses, Dog, etc.
    class Foo {
        virtual Animal* getAnimal() = 0;
    class Bar : public Foo {
        Animal* getAnimal() { return new Dog; }

This program has no obvious Haskell translation. As I got more experienced with the language, I realized that OO is not the One True paradigm, that most problems I want to solve have a natural OO solution and a natural functional solution, and they are very, very different. They solve the same problem, with comparable (but different) areas of modularity, etc.

After that long-winded digression, we can come back to Universal Architecture. I think we, as architects, should put more focus on finding the natural solution in the language we’re using, rather than trying to add a language feature to a language that doesn’t have it. Every time I’ve tried to do that (which is plenty; it seems each time I learn a new language I try to map the features I like about it into whichever language I happen to be using) I just end up with a mess. … Or worse yet, adding a language feature to a language that already does have it (see first example :-).

What’s up with Google?

For the past week, every now and then, Google stops working.,, for all values of blah give me a “the connection was reset” error. is fine, but is broken. It happens for the whole local network here.

And yet, if I ssh into my server on the CU campus, everything works as expected. Does my router have some weird sporadic firewall? Is comcast dropping the ball? Intentionally? I have no idea what’s going on.