Category Archives: General

Blog Upgrade

I just gave WordPress a much-needed upgrade, from version 1.3 to the latest version 2.5. I have to say, WordPress 2.5 is a very nice piece of software. I was extremely pleased by the upgrade process, which painlessly preserved my archives all the way back to 2003, even from such an old version. Commercial upgrade support is seldom that good.

It still requires a bit of hacking to get things just right. The theme I selected is gorgeous, and 15 times better than any other theme I found on the WordPress themes site. But it had a stupid “wallpaper selector” on the top banner. How useless. I had to dive into the code and find the line to comment out to remove it. But I guess that’s the theme designer’s fault.

Go WordPress! You are yet another shining example of high-quality open source software!

SVK, you’re not wanted here, git it?

After trying and failing to restore the soylent repository from my svk mirror, svk broke. It wouldn’t let me push or pull from any of my mirrors, for no discernable reason. Instead of hacking it out, I decided to get my hands dirty with git, which I have heard good things about. So far so good, after the usual new SCM ritual (create new repository, whoops, “oh, that’s how that works”, delete, create new, whoops, “oh, pull doesn’t mean pull”, delete, …).

My old svn misc repository will be hanging around, since I have links into it floating around, but it will go unmaintained. Behold the new git misc repository!

Sleepless Night

It’s one of those nights again. A night I am tired enough to sleep, but I just don’t want to for a reason that evades me. Instead, I’m staying up watching bad movies and wasting time. One way, I thought, to waste time would be to write some nonsense in my blog.

My life is pretty busy right now, in a way that would be judged by someone else to be completely the opposite. When I’m not staring at my computer, I’m playing the piano. But inside I know that the aforementioned someone else doesn’t know what he is talking about. Here’s some of the interesting stuff I’m working on:

I have a very powerful incarnation of FRP with well-defined (but occasionally spooky) semantics. The world is broken up into signals (values that vary over time) and events (somewhat spooky). It has a nice referential transparency-like property which I painstakingly maintained in my design (which was not entirely easy since Event is isomorphic to IO (or rather, a transformer thereof)). It was very tempting to allow things like writing files and allocating names for objects inside events. But I thought it through, and the property I want to maintain disallows those things. Anyway, I programmed a little shoot-em-up in the FRP library I wrote, and it’s quite encouraging. I still am not sure quite how to think in FRP, but the abstraction abilities are amazing (as expected). The only problem is that it is quite slow at the moment, but there are abundant opportunities for optimization in the library, which I just haven’t had the inspiration to implement.

I’m also working on several games. The first is the linguistic magic game that I’ve been talking about here on and off for several years. I have the simulation, and even a rough spec for the language (which is reminiscent of the aborted child of Esperanto and Finnish). I can’t say much about it without going into a lot of detail, so I’ll just put that off until later.

The other game I’m working on is a music and rhythm game, which has hopes of transcending the sight-reading trend. I have tried to design an improvisation game before, and it was never too promising. But this one is promising, and I have it basically fully specced out in my head. I’m going back the other direction towards sightreading, but not all the way. It’s a hybrid of sightreading and improvisation, where the game is serving as the conductor (remember my founding idea for SNW?) and you, the player, are serving as the musician. As an example flow, the computer would give you a drum beat and might start you off with a Guitar Hero style sightreading thing as a bassline; i.e. “play this line verbatim”. You repeat that 6 times, and then the computer takes over: the bassline continues, but your fingers do not. Then maybe it gives you a line to play, but it just tells you the notes and the order, not the rhythm. You are in charge of inventing the rhythm for that line. And so on. There are soloesque line sections where it gives you a set of notes, and you just have to play all the notes in the set, but the order and rhythm is up to you. There are invent-your-own-bassline sections, where you play any bassline you like, but then you’ve got to repeat it (and keep coming back to it throughout the song). The key, tempo, drum part, and song structure are dictated by configuration files, but the exact incarnation of the song is up to the player.

I’m also learning Hungarian Rhapsody no. 2 by Liszt on the piano, which is the second most rediculously difficult song I’ve ever attempted (the first being—*snicker*—Rachmaninoff’s 3rd Piano Concerto, which, needless to say, I did not get very far into).

Orson Scott Card Improvs

Last week I picked up a book of short stories by Orson Scott Card. Two of them (so far) have inspired improvisations:

  • The Maker (from “Unaccompanied Sonata”)
  • Songbird (from “Mikal’s Songbird”)

The Maker is an uptempo and very dissonant, built on augmented chords and a random alternating bassline.

Songbird is one of the most complex pieces I have improvised so far. It is harmonious (it stays diatonically in one scale almost the whole time), but there are at least three voices that I can identify. While improvising this one, I kept thinking to myself that I should end it soon before I mess up, because I can’t keep up the complexity… but I didn’t. I just kept going until the song wanted to end. In my opinion, this is one of my best improvs to date.

Oh, I should say something about “Mikal’s Songbird”. This is a jewel of Orson Scott Card’s work: great story, beautifully written, captivating to read. I highly recommend it.

Screenplay

Here’s a sketch of a short screenplay I’d like to write.

Depict a stereotypical “successful businessman” finishing a day’s work (closing a deal or something), driving home in his nice car, sitting in front of his top-notch TV set and beginning to play a video game. Repeat a few times, with some, but not too much, variety. Playing somewhat, again not too much so, digital-sounding music.

Pan out to find that this depiction is in fact on a top-notch home theater, a video game being played by an identical stereotype, but a different actor. He expresses boredom or frustration somehow, that he wants his character in the game to do something different. Frustrated, he turns off the console and walks outside.

Depict him climbing trees, hopping across a river on stones, other fun things in organic environments. Playing fluid, organic music. Close with him jumping on a goomba.
image of goomba

Suggestions?

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'
     where
       exmid' f g = either return g =<< callCC (\cc ->
                              return . Left =<< f (cc . Right))
       exeither' e = e (return . Left) (return . Right)

What’s up with Google?

For the past week, every now and then, Google stops working. google.com, reader.google.com, blah.google.com for all values of blah give me a “the connection was reset” error. gmail.com is fine, but mail.google.com 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.

Bad Habits

Going off to live in a new place often causes you to redefine yourself as a person: to break down old bad habits and replace them with new, more productive patterns. Then when you come back, the old bad habits kick right back in again and all that work you put in to redefine yourself is put aside.

Well, I’ve never lived anywhere but here in Boulder (I lived for a year in Maryland when I was 5, but that doesn’t really count). But I figuratively went off to a new place when I started CU, and then again when I went to work at NetDevil. You could see traces of a hard-working, responsible person coming out. In school, I went to class all the time and worked hard; during work, I went every day and did my job well (but didn’t want to work any more that I already was, which is why I left).

Now I’ve come back; I am not enrolled in school and I’m unemployed. I have loads of spare time on my hands again. And just as expected, I’ve rebuilt my old bad habits…

… For some definition of “bad”. Now I have a chance to look back on the last few years. What have I done that I’m proud of?

  1. Got good grades in school.
  2. Made two or three computer games.
  3. Wrote two songs.
  4. Started a band.

#4 I did after I took my scholastic hiatus but before I was employed. But I don’t want to say “it doesn’t count”, because it still could have been the school environment that influenced me to do that. Regardless, this all pales in comparison to my old, bad habits:

  1. God bad grades in school.
  2. Made one computer game per month, approximately.
  3. Wrote two songs per month.
  4. Learned a new challenging piano piece every month.
  5. Became well-known as a contributor in the Perl community.

Looking back, my bad habit of learning is much faster than the new, responsible habit of learning, because my bad habit is to learn by myself at my own level and speed, and my new habit was to learn at the rate others were teaching me.

In summary, I like my bad habits much better. I enjoy myself more, I’m more satisfied with my creative output, and I’m always well-rested. While a student or employed, I’m usually fatigued from working as well as being ill-rested (as a byproduct of trying to be creative), and my creative output is pitifully small. Over the past week after my return from my vacation (which I took promptly after quitting NetDevil), I saw my old rate of creativity completely revitalized, more than it has been in years.

At some point I learned not to waste time: to use idle time and energy to learn and to create. And I love that about myself. That’s what allows me to become excellent at whatever I do; “hard work” is not what does it. The mind works best when it is free to experiment—without deadlines and without stress.

But I have a bit of an internal conflict—conflicting fears even. I fear that if I stay with my bad habits then I will never “get anywhere”. My goal was to get a PhD and become a professor. But I also fear that as a PhD student and as a professor—or whatever I end up doing—I would keep my responsible habits and be dissatisfied with my creative work.

I think I can disarm the first one, though. What is “getting somewhere”? There are a lot of professors who make major contributions to their fields, but there are a lot of professors who don’t. Someone in the math department once commented that for the majority of math dissertations, the number of readers is roughly proportional to the number of authors. The other part of “getting somewhere” is making money, but my skills (which, mind, I have developed thus far on my bad habits) can definitely do that for me when I need it.

As far as I can tell, the only thing I am missing by not taking the school route is colleagues, who can indeed help me learn faster and bring me to more advanced levels. But it’s not that I can’t find such people elsewhere; I certainly had no trouble in the Perl community. I think I will still contribute to mathematics and computer science even if I stopped formal education right now.

It looks like I just argued to myself that there’s no need for school anymore. That’s a frightening prospect because it’s been on my radar to go to graduate school for so long. In particular, Karlin’s parents have been highly influential in my life and I respect them very much, and they are quite keen on my finishing a bachelors and persuing a graduate degree. As far as I have convinced myself, though, I would actually cripple myself by going back to school and not taking things at my own pace. This may be the time to devise a nonstandard lifestyle on which I can support myself and have the freedom I need. I have been considering starting a rehearsal studio business…

Dilemmas aside, I’m very happy that my bad habits have returned to me.

Platonism

Studying all this decidability theory is fundamentally changing my view of the universe. In particular, I am losing my Platonism.

It all begins with the halting problem, which isn’t so much a problem anymore as a result. It states that there is no computer program which can tell whether another computer program will ever finish. The proof is so remarkably simple that I will paraphrase here:

Suppose there were such a program. Call it infinitely_loops(prog, input). It uses a magical complicated procedure to analyze prog and determine whether, when input is fed as the input to prog, prog will get into an infinite loop or not. Now let’s write a new program, called gah, which takes as input input, which is the source code for a program:

    // include source code for infinitely_loops here so we can use it
    if (infinitely_loops(input, input)) {
        exit();            // (a) finish immediately
    }
    else {
        while (true) { }   // (b) infinite loop
    }

Just to be clear: gah takes a program as input and then asks whether, when you feed it its own source code as input, whether it gets into an infinite loop. If it does, then gah exits immediately. If it doesn’t, then gah itself gets into an infinite loop.

Finally, we ask the question: what is the value of infinitely_loops(gah, gah)? That is, does gah get into an infinite loop when you feed it its own source code? Well, there are two possibilities;

  1. It does get into an infinite loop. But then look at the if statement above. We gave gah itself as input, so input = gah. Substituting, the if statement reads if (infinitely_loops(gah, gah)), which is what we’re asking about. The condition would be true, in which case our program would take branch (a) and exit immediately. But that’s no infinite loop, that’s definitely finishing. So there’s a contdadiction, which leaves only the remaining alternative:
  2. It does not get into an infinite loop. But in that case, in the if statement above, our program would have taken branch (b), so it would have entered the infinite loop we wrote there. Another contradiction!

So, since it can’t infinite loop, and it can’t not infinite loop, we have a contradiction, so our only assumption that the program infinitely_loops exists must have been false. There is no such program!

Okay, that was a little longer than I remember it. Still, the logic is simple and there is nothing magical about it.

I understood the halting problem even when I was in high school. I understood it, but I did not grok it. I thought it was totally neat that, after being introduced to programming and feeling like I could do anything, that there were computer programs which were impossible to write. Well, of course there are such programs: you can’t write a program which will tell you what will happen tomorrow. But this was a program which you could ask a real question to, a question which had an absolute, definite yes or no answer, and the program would not be able to answer it. That’s cool, isn’t it? It kinda gives meaning to being human, a kind of irreplacability, right?

Well, that’s what I thought at the time. I continued in college to study set theory and decidability theory, where I learned about Gödel’s incompleteness theorem. Unfortunately, that proof is not simple enough to repeat here :-). His theorem says that no matter how many assumptions you make, there will always be a statement in math which you cannot prove true or false. I’m not going to go into detail, but essentially he wrote down a logical statement which meant “such-and-such computer program eventually finishes”. Keep in mind that it’s very easy to write a computer program which will eventually write down everything that is provable (careful with the precedence there: it runs forever, writing down statements; it means that if you give me any provable statement, it will eventually write it down in its sequence). A proof is just a sequence of letters, and a computer is capable of checking whether a proof is valid. So just enumerate proofs, one-by-one (in practice this is completely infeasable, but we’re theorists!), check if it’s a valid proof, if so, write down what it proved. So if you could prove Gödel’s statement for any machine, then you could easily write a program which decided whether other programs infinite loop or not. But we just showed that that’s impossible, so it must also be impossible to prove Gödel’s statement.

This is when my mind started collapsing. The halting problem is not about what computers can do. It talks about all of mathematics. It means that determining whether computer programs infinite loop is a mathematically impossible problem, for both humans and computers. There are computer programs which the greatest mathematicans and programmers in the world could look at for years and never be able to determine whether or not it ends, without just running it (and if you run it, then you can wait until it ends and say “yes! it ends”; but if it doesn’t, you can wait forever until you die, never knowing whether it’s going to end or not).

Well, maybe it’s a problem in our reasoning skills. Maybe our logic is consistent, but it’s missing something that would conclude these things. Well, it turns out no. Gödel, the genius he was, also proved that if in every logically consistent world (“world” defined loosely, “mathematical system” is more accurate) a statement is true, then our proof system will be able to prove it. So then the halting problem becomes even more mind-boggling: there is some phantom statement we could add to logic that would allow us to prove that the machine does stop, and another phantom statement we could add that would allow us to prove that it does not. We hope (though, due to Gödel again, cannot prove) that our logic is consistent and represents the structure of information in the world. So how can whether this machine stops or not depend on which logic we use? It’s a fact! It either stops or it doesn’t!

I originally wrote about twice as much as you see here, but I realized that I wasn’t saying much, just going in circles. Essentially the whole idea of facts is vanishing from my world model. There are things that are true, and there are things that are false, and then there is fantasy. I don’t think our logic has holes, things that are true but it can’t prove given the proper assumption. It’s more like we’re asking questions about whether something will happen in the future, and in the case that it will, we will know only when it does. Notice that I didn’t consider the case that it won’t… because that case doesn’t even make sense :-).