Monthly Archives: April 2008

Why separate compilation is a good thing

I was talking with a friend about why I hate C++ (it’s actually a complicated tolerate/hate relationship), and mentioned that templates don’t have separate compilation. “That’s not really a big deal”, my friend replied. I remember a time when I thought the same thing. So what if I have to recompile some other stuff when I change a file? Projects of the size I work on take under a minute to compile from scratch anyway. And that will become even less of an issue as computers get faster.

The real benefit to separate compilation is not about speed. It means that whether code compiles is independent of the code that depends on it, or in other words, type safety is modular. Imagine if in mathematics theorems were only true sometimes, depending on how they were used. Those are pretty crappy theorems, because you have to know the proof in order to use them (I know I have used theorems whose proofs I haven’t understood!).

And C++ templates are indeed non-modular. Rewriting the body of a function but not its type signature can cause code to fail to compile. You can imagine how irritating this would be if you’re a library author (or even a library user).

It’s for this reason that I like FRP, because its behavior is definitional: the semantics of a value (signal or event) only changes when the code that created it changes, but not when code that uses it changes. So even the runtime of an FRP program is easier to reason about than the compile time of C++ (watch as I make sweeping incorrect generalizations!).

What’s a natural transformation?

For some reason I’ve had a great amount of trouble learning category theory. I think a lot of that is that most of the literature sucks. But I don’t blame it, in fact I find it encouraging, because it indicates that there is a brain-rewiring involved: people who know category theory cannot teach it, because as a consequence of learning it, they are thinking in a fundamentally different way.

However, thanks to the Stanford Encyclopedia of Philosophy, a resource which consistently provides good intuition for mathematics when the literature is otherwise impenetrable, I think I finally get natural transformations.

I always heard that a natural transformation is “just like a polymorphic function”. I never really got that, especially since wikipedia said a natural transformation acted on functors but a function is a morphism (in Hask).

Let’s work in the context of an example. I’ll look at concat :: [[a]] -> [a] because it has only one argument and only one type variable, so that will simplify things for us. Let’s also recognize that there are two functors appearing here: [] on the right and []°[] on the left.

Here’s the formal definition, which I wish to decode: A natural transformation η relates two functors (F and G) with identical source and target. It maps objects in the source category to morphisms in the target category. For every morphism f: X \mapsto Y in the source category, \eta_Y \circ F(f) = G(f) \circ \eta_X.

So here F is []°[] and G is []. Our natural transformation concat must associate objects (types) to morphisms (functions) and satisfy the above equation. To expand that equation, let’s realize that [](f) (where [] is the functor) is map f and []°[](f) is map (map f). These are part of the definitions of these functors, and in Haskell correspond to the definition of fmap.

The equation is thus: for all functions f :: x -> y, concaty . map (map f) = map f . concatx. Holy smokes! That’s the free theorem for concat! (note: that paper was another that I never really grokked; maybe I’m grokking it now)

If I could go back to last week and help myself understand, I would have said: a polymorphic function in Haskell is a collection of morphisms in Hask, not a single one, and the equation above is what guarantees that it’s actually parametrically polymorphic (doesn’t care what type it is).

So the following pseudohaskell would not define a natural transformation:

concat' :: forall a. [[a]] -> [a]
  | a ~ Int   = const []
  | otherwise = concat

Because the equation fails to hold for, say, show :: Int -> String: concat'String . map (map f) /= map f . concat'Int because concatInt = const []. That makes sense, because concat' is not parametrically polymorphic.

A question I have is what a polymorphic function is when it’s acting on type constructors that aren’t functors. Is that just a “polymorphic function” and doesn’t necessarily have a categorical parallel?

I guess the weirdest thing about category theory is how natural trasformation was defined. I think I have an intuition for what it is now, but I would never fathom defining it that way. Thinking of objects only as their relationships to other objects is a mind bender.

Music Gear Review

Over the past couple years, I have accumulated many thousands of dollars of musical equipment. I thought I would take some time to review the pros and cons of what I’ve purchased for future imitators :-). You can hear this gear in action in all the SNW recordings.

Main keyboard: Nord Stage 76

I bought this refurbished on eBay for $2,400. It’s the one I’m playing in the picture. This is my favorite piece of musical equipment ever, way better than those fancy $6,000 KORG boards. I think this keyboard’s strongest point is its aptitude for improv settings: after spending some time getting familiar with the controls, I don’t have to spend any time getting just the sound I want, even if I never thought I’d want it beforehand. All the sound tweaks are physically there in front of me, not hidden in layers of touch-screen menus that take 30 seconds to get to. It sounds inefficient, but it’s exactly what is needed for improv.

There are 4 major sections: organ, piano, synth, effects. The organ and piano sections are top-notch, with excellent reproductions of B3 (with manual drawbar controls, which work great, but turn out to matter less than I thought they would) and a few types of electric piano (and the obligatory acoustic piano, which is a very nice patch). It doesn’t matter that there are only a few types though, because they really sound perfect, and tweaks to the sound can be done via onboard effects.

The synth section sucks, I essentially never ever use it. That’s okay in my situation because both of my other keyboards cover that area very nicely, but it’s something to keep in mind.

It has 12 effects in the effects section (plus a great amp sim that I have enabled almost all the time), but there is a weird situation about what effects can be active at the same time. There are three sections, and each effect is in only one of them. So you can only have 3 effects active at the same time, and not all combinations are possible. I thought this would be limiting, but in practice it works fine, and the interface is very streamlined once you learn it.

If this keyboard broke or was stolen, I wouldn’t hesitate to buy the exact same thing again. This is the perfect keyboard for improv.

Upper keyboard: Nord Lead 3

So impressed by the Nord Stage, about six months later I bought another Clavia product, the Nord Lead 3 (now discontinued) on eBay for $1,000. It’s a pretty cool instrument, but I do not rate it anywhere near as high as the Stage.

The idea is that it emulates old analog synthesizers. The keys have nice action (unweighted), and I of course love the hands-on control (I could never use a keyboard with menus!). But it just isn’t that versatile. The patches all sound too “old-school”, too “fat” (generally a positive adjective in the synth world, but sometimes I want a really skinny sound, and that’s very hard to get). Also the glide function is linear, meaning the pitch changes at a constant rate from the source key to the destination key, which is much less flexible than Reason’s exponential glide, where the rate depends on the distance from the source to the destination (so if I want a faster glide, I “help it along” by pressing a higher key). And I use glides a lot in my synth leads, so that flexibility is very important.

What I do like about it is the hands-on envelope controls. Most of the time I pick a lead patch at random and just start playing with it. The biggest thing that makes a lead patch inappropriate is the envelope: it starts too abruptly, or it has a really long release (so there’s a sloppy sustained effect, when I want it to be tight). But the envelope controls are right there so I can quickly fix those problems instead of clumsily cycling through patches until I find one I like (messing up the music in the meantime). I also like the chord glide a lot. It’s kind of a gimick, it really only sounds like one thing, but it’s a really unique sound.

Right-hand keyboard: M-Audio Radium 61 + Reason 4

The oldest part of my rig is the keyboard on my right side, a crappy little M-Audio MIDI controller that I got for $80 on eBay, and Reason as the software synthesis behind it (bought for $300 new). The Radium 61 has okay action, but occasionally a key sticks which is pretty much unacceptable. I really should replace it. But it has some configurable controls on it, which are quite essential to what I do. But really, the important part of this keyboard is Reason.

Reason I rate almost as highly as the Nord Stage. If something happened (I don’t know what that would be, it’s software!) I would replace it immediately. It covers the Stage’s ass in the synth area, with the most amazing leads and pads I have ever had the pleasure of using. I had to spend some time configuring it for improv use, though. Here’s how:

I went through every patch and tried it out a little. If I liked it, I put it in a favorites group according to what it is (eg. “strings”, “pad”, “lead”, “choir”, …). Then I made a big rack and created one instrument for each favorites group, and selected the first one in that group. That way when I push the next and previous patch buttons it selects the next of my hand-picked patches in that group, rather than whatever is next on the list it was originally in. When play I move a lot between types, and less frequently between instruments in a type.

I also have four effects set up: reverb (with a similar patch setup), delay, distortion, and flanger. The parameters of the effects are mapped to the controls on the MIDI controller. That part came later, and was very important; once I did that I got a lot more power out of my right-hand keyboard. In retrospect I would do away with the flanger though, since I never use it. Oh, and I also have master volume mapped to one of the controls on the MIDI controller, because it’s impossible to predict the right volume ahead of time.

Right-hand keyboard accessory: Mackie C4

There is one thing Reason is missing though: hands-on controls (especially the aforementioned envelope controls). Using the mouse sucks. That’s why I bought the Mackie C4 control surface, basically just a big board with a bunch of configurable dials on it. I got it for $1,000 new. Not recommended.

The biggest problem with it is the way it’s mapped to Reason. Most of the dials available by mouse in Reason are mapped to the control surface, but they’re in different places for each virtual instrument! So if I want to change the attack on the lead I’m playing, I have to know whether the lead is “implemented” in the Subtractor, Maelstrom, or Thor. I don’t know that, I don’t want to have to think about that, I just want to change the attack! There are dynamic labels, so if my eyes were available during a jam session, which they typically are not, then I could hunt and figure it out. But essentially it completely fails at what I bought it for.

The main thing I use it for nowadays is for 6 buttons: next/prev type, next/prev patch, next/prev reverb patch. (The reverb has separate buttons since I’m often in the “scope” of another instrument when I want to tweak the reverb). A grand is a lot to pay for six buttons.

The only thing that’s keeping me from selling it is the fact that, if I were persistent, I could learn Reason’s control-mapping format and remap everything in a sane way. But the format is really complicated and undocumented, and I just haven’t had the energy to do it.

Amp: Peavey KB/A something

Got it for $150 on eBay. Does the job, could be better. It doesn’t have wheels! One of the three inputs broke, which was annoying but didn’t matter since I only use one input anyway. But I think it would be worthwhile to get a nicer amp.

Audio Interface: E-MU 1616

I bought this used on eBay for $160. This card has served me very well since my upgrade from the terrible M-Audio firewire card. I repeat, do not go near M-Audio for an audio interface! As for simple record/playback stuff the EMU has never been caused any issues whatsoever. It can be a tight fit when recording though, since I can really only get 6 inputs (the other 10 they advertise have to come from an external ADAT box, which can be pricey). I use 3 inputs for myself, so that gives me room for a single room mic on the drums, and a line in from two other musicians. That worked well for SNW because I never wanted to grow beyond 4 people, but for other situations I’d have to expand. Fortunately I could (presumably) just invest in an ADAT box and have tons of inputs without having to pick a new interface.

The SNW recordings here and here were made using the EMU, three inputs for myself, one for Evan (bass) and single room mic on drums. It’s pretty incredible how good the sound quality can be for such a simple setup, but it doesn’t quite match the earlier recordings Eric made with a much nicer interface and a whole drum mic setup.


Those are the expensive parts of my rig, hopefully someone has stumbled upon this while trying to create something similar and I’ve helped out. There are a lot of bells and whistles: four sustain pedals, an expression pedal (for the Stage), and a tap tempo pedal (for Reason). I will say something about the tap tempo pedal: it was very hard to find one at all, here’s the one I got. It works great. The rest of the details are not that important.

C’est la vie

A comment arrived a few minutes ago asking for details of the life flux I mentioned in passing here. I was messing with my blog and had to restore from backup, so I lost the original comment. Sorry, whoever you were.

Back in December a message arrived on haskell-cafe announcing a Haskell job opportunity in Belgium, a startup called Anygma developing some FRP stuff. I idly replied, saying that I was a student interested in working part-time remotely from Colorado. It was worth checking out, but didn’t mean much.

A few months pass.

My dad was dropping me off at my house after we saw “In Bruges” (a very entertaining movie, by the way) with my mom (who was in town from Hawaii). The two of us were sitting in his truck when the Belgium job came up, presumably because of the location of the movie. He convinced me that even if the job isn’t that great, the opportunity to move away from my home town, especially to Europe, is one that shouldn’t be missed. I was feeling particularly distant from my friends at the time, Eric (of SNW) had just fled to Argentina, Karlin and I hadn’t (and still haven’t) seen each other in months, I had become disinterested in continuing my math major. All my attachments seemed to have vanished just in time for this opportunity.

I stepped out of the truck and went in my front door. I remember having to go to the bathroom, but instead of that I turned on my computer and hastily prepared my resume. I was excited but also hurrying, as if the job would vanish if I didn’t finish in an hour. I sent my resume in together with an informal cover letter explaining my situation and my change of heart.

I received an enthusiastic reply the very next day, and we began corresponding about the project, logistics, etc.

But, c’est la vie, I acquired some new attachments.

My roommate just started dating a girl he met in the university open source group. A few weeks ago I met a friend of hers named Karen, a graduate student of Classics (Latin literature). She has one among the sharpest tongues I have ever heard, almost as though every utterance of hers were a little poem. We both maintain a deep but friendly eye contact when talking to each other, and we can align to the same wavelength very quickly, in a manner of speaking. To sum up a long schmaltzy series of compliments, I have not so admired someone since—well let’s say since my middle school crush, accounting for emotional subjectivity :-).

Unfortunately she started seeing a friend of hers just (seriously, like the previous day) before I met her. Notwithstanding, she has got my emotions all tumbling around, which inspires me to compose music. She’s the reason for the symphonic poem I posted last week, and the next one coming up in the series that I have been working on for a few hours a day. Whatever happens with life, I hope not to lose contact with her, because this one’s special. I just may not end up dating her. I could live with that.

Woman: attachment no. 1. Friends: attachment no. 2. I have been really enjoying being with my friends lately; not Namaste and Jude so much as the more remote nerdy crowd (Jessa, Daniel, Stirling, Richard). It’s possible that that’s a consequence of my moving away though, that I’m appreciating my friends more and vice versa.


Last weekend Anygma flew me out to San Francisco for an “interview” of sorts, which doubled as a visit to my good friend Max. I wish I could give the details of why I had an interview for a job in Belgium in San Francisco, but I am under NDA. :-)

The interview was… interesting. Peter obviously knows what he’s doing, because he made me seriously consider whether I wanted to be working in the software industry. If I do, then Anygma is where I ought to work; it is so amazingly close to my interests and philosophy that I would be a complete idiot to turn it down (unless I thought the management were incompetent, which I don’t). But it seems inescapable that developing a piece of software is at least 80% polish, and polishing is what I don’t like doing much. I’m more a mathematician than an engineer: I like to ask “why” rather than “how”. Other than that huge blow, the interview went well.

I spent 4/20 with Max, and we had a good jam session with his band. I brought home a disoriented feeling, questioning my life plans.

It didn’t help that when I got home Namaste had returned from a sort of “vision quest”, where he abandoned everything he owned and drove up to live in the wilderness. Long story short: Turns out he wasn’t quite prepared (we all knew that) and was mostly helping his impulsive friend. He plans to prepare for the next year and go back.

When he described the experience to me, it almost shook my world out of its socket (which would be awesome I know, but I don’t think I’m ready for that). Inspired by a quote from one of my musical influences, John Medeski, I seriously considered becoming a full-time musician for a while as a new experience.

But after talking with some friends and a little simmering, I abruptly realized that I would be a fool to turn down the job. I cannot predict what it would be like at all, and I love working in Haskell no matter what I’m doing. Two days ago I sent Peter an email expressing that I’m still interested.

Present day. Present time. Aahahahaha.

And I haven’t heard back yet.

This is the fun part. Having committed myself emotionally to a new life, and now wondering whether it’s just fantasy.

I’m just sitting here waiting, blogging about my personal life. Waiting for any word from Belgium, composing music and thinking about Karen, afraid to start any technical projects for fear that I will abandon my composition, generally not having any idea what I’m doing. It feels very different from how I am used to living my life.

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!

Symphonic Poem no. 1

I just finished, in some sense, the first of a series (hopefully) of symphonic poems. I took a long break in the middle of writing this, so I could be mistaken, but I think it took about 20 hours total. It still needs a little tweaking; in particular some of the harmonies on the climaxes are drowned out by the percussion and poor instrument balancing, and I’m not sure if I’m happy with the ending (it’s meant to be a little unsettling…). But the idea is there.


Stop Using Undecidable Instances

I’d say a good 5% of the threads on the haskell-cafe mailing list have something to do with the typechecker doing strange unexpected things. And the test code for 100% of these features one of the two lines:

{-# LANGUAGE UndecidableInstances #-}
{-# -fallow-undecidable-instances #-}

There was one today asking why the typechecker was getting into an infinite loop… do people not know what undecidable means?! (This isn’t as rhetorical as it is phrased, people without a formal CS education probably do not) It seems like Haskell programmers, new and experienced alike, throw around this flag at the drop of a hat whenever a GHC error message suggests it.

STOP IT! You will enjoy Haskell much more if you just stay the heck away from this flag. The most common example I see is superclassing:

  class Group g where
      (%) :: g -> g -> g
  instance Num g => Group g where

This is okay only so long as there are no other instances of Group. Let’s say the typechecker comes across an expression of the form True % False. (%) has the type Group g => g -> g -> g, so it will unify g with Bool and we get the type of the expression as Group Bool => Bool. Then we check the constraint Group Bool, searching for instances that match. Oh, here’s one, Group g. So we pick that instance and add the necessary constraints, and the type becomes Num Bool => Bool, which of course fails. The type checker does not backtrack to find another instance Enum g => Group g if you defined it, it just dies. If you defined explicitly Group Bool then it will probably work because of the order in which it checks for instances, but relying on this is a bad idea. But certainly two instances of this form will always break. The solution is (unfortunately) to use a newtype:

  newtype AdditiveGroup g = AdditiveGroup { fromAdditiveGroup :: g }
  instance Num g => Group (AdditiveGroup g) where

In this case it was actually good that you had to do that though, since Num forms more than one group, it’s good to mark which one you mean.

What worries me more is that mtl uses UndecidableInstances, with a simple comment saying:

-- This instance needs -fallow-undecidable-instances, because
-- it does not satisfy the coverage condition

No proof, no rationale why this is always solvable. It seems like another “GHC told me to add the flag so I did” (however it probably is not).

</rant>    <!-- obviously -->

Git Revolution

I’ve been learning about git, and have generally been excited about the distributed model. I mean, I used svk, but a robust distributed model is quite exciting. Tonight I had a completely crazy idea: to make a game around git.

I brainstormed and I brainstormed, many brains rained. And then it hit me: this is perfect for my interesting-concept-but-needs-work-game Revolution.

A slight refresher: Revolution is an open-ended strategy/role-playing board game; i.e. people have roles, and they can do things consistent with their roles and their resources, but are not restricted to strict game rules. Whether they are capable of doing something is determined by an impartial game master. We did a few play-tests, and it was interesting, but it was frustrating for many people. This was because the core game dynamics were not very rich (intentionally, I wanted the player-created content to create the richness), but also because players felt cheated by the GM because other players were getting advantages for “unfair” moves that they didn’t think of. A lot of balancing decisions had to be made by the GM in real-time, and it’s very easy to disagree with those if they work out in your opponent’s favor.

My current idea, which I hope is mature enough to play-test tomorrow, is to do away with the GM in favor of a GM-like game dynamic. And that game dynamic will be provided by git!

Here’s the idea: everybody gets a repository which has the state of the world in it. Everyone also has files somewhere describing their role (some kind of player-specific ability perhaps) and what resources they currently have. And then during a game round everyone makes changes and commits them with a description of why they were capable of making that change. During the game round people also share their repositories with each other, and people merge in changes as they see fit. A soft rule is that you shouldn’t merge changes which don’t make sense; i.e. if a farmer builds an international airport, nobody should merge that. But they could if they wanted, it’d just be weird.

So there are a bunch of worlds floating around which probably disagree with each other. What is the real state of the world? I think it’s just the most popular commits. So if more than half of the player branches have incorporated a commit, it gets merged into the “real world” branch. And the real world branch is what determines if people have accomplished their (hidden) goals to score points. I’m not sure the goal/point thing still makes sense, but that’s all I can think of for now.

Git should make this super easy. For ease of communication, I’ll probably just set up a central repository with one branch per player. Players are allowed to modify whatever the hell they want, so commit hooks are not necessary. The only thing I need is a script which finds the most popular commits and merges them.

All that’s left is the hard part: the actual game dynamics…