Monthly Archives: January 2008

What makes linear logic linear?

Sorry for the lack of posts this week. I’m traveling for work, and
I’m seriously jet-lagged, so I haven’t been able to find enough time
or energy to do the studying that I need to do to put together a solid

Fortunately, someone sent me a question that I can answer
relatively easily, even in my jet-lagged state. (Feel free to ping me with more questions that can turn into easy but interesting posts. I appreciate it!)

The question was about linear logic: specifically, what makes
linear logic linear?

Continue reading

Friday Random Ten

  1. Godspeed You! Black Emperor, “Antennas to Heaven”: What can you really say about the greatest post-rock ensemble ever?
  2. The Windmill, “Please Keep War Stories to a Minimum”: a recent post-rock discovery of mine, via bitmunk. Excellent group.
  3. Rachel’s, “An Evening of Long Goodbyes”: Rachel’s is one of the more classical-leaning post-rock groups. They’re wonderful.
  4. Peter Schickele, “Listen Here, Tyrannosaurus Rex”: The discoverer of PDQ Bach, actually doing something really goofy in his own name. Fun, but silly.
  5. The Flower Kings, “Man Overboard”: The Flower Kings are, without the slightest doubt, one of the greatest, if not the greatest of the neo-progressive bands, and they could give the best of the original proggers a run for their money. This track is part of their double-album “Unfold the Future.” It’s an interesting piece – it starts off as a
    what seems like a simple little ballad, but the chorus involves a bunch of wonderfully strange chords and time changes. Just brilliant.
  6. The Redneck Manifesto, “Bring Your Own Blood”: Another great post-rock band in,
    roughly speaking, the Mogwai vein. Another really great group – The Redneck Manifesto is one of my favorites.
  7. Marillion, “Toxic”: a live version of Marillion covering a Britney Spears song. Who knew that a Britney tune could be anything other than total trash? Still not exactly a brilliant piece of music, but it’s not garbage, either.
  8. Apothecary Hymns, “The Marigold”: A nifty track by a very hard to categorize
    band. They’re sort of vaguely like early Fairport Convention, but with a very modern instrumental sound. I first heard these guys on New York’s NPR station. They’re really good.
  9. Mogwai, “I know you are but what am I?”: Mogwai – among the best post-rock out there. Not enough good things that I can say about them. This track is an ethereal wonder.
  10. Spock’s Beard, “Onomatapea”: the first track off SBs first album after the
    originally band leader found religion and quit. I know a lot of SB fans dislike this album, and particularly dislike this song, but I really don’t know why. It’s the first SB song I heard, and I still think it’s terrific – better than a lot of the older Morse-written stuff.

Friday Recipe: Real Fried Rice

One of the staples of chinese cooking is fried rice. Unfortunately, what we get in
American restaurants when we order fried rice is dreadful stuff. The real thing is
absolutely wonderful – and very different from the American version.

The trick to getting the texture of the dish right is to use leftover rice. Freshly cooked rice won’t work; you need it to dry out bit. So cook some other chinese dish one night, make an extra 2 cups of rice, and then leave it in the fridge overnight. If you can, take it out of the fridge a couple of hours before you’re going to cook, to get it to room temperature. Then when you’re ready to start preparing all the ingredients, use your hands to crumble the rice – that is, break up the clumps so that the grains aren’t sticking together.

What I found surprising about real fried rice was that you don’t put any soy sauce into the rice. The rice is the heart of the dish, and you don’t want anything as strongly flavored as soy sauce to disturb the fine, delicate flavor of good rice.

I generally start with around two cups of uncooked rice to make a large portion for four people.


  • 2 cups rice (uncooked measure), prepared the day before, and left to stand
  • 1/2 large onion, finely diced.
  • 1/2lb ground meat. (I use ground chicken thighs; ground pork is more traditional.)
  • 1 tablespoon of soy sauce.
  • Vegetables (quantity to taste); something like snow peas, green beans, broccoli
    florets, etc – something nice and crisp.
  • 1 tablespoon finely minced pickled turnip. (You can get this in a chinese grocery
    store. If you can’t find it, just leave it out.)
  • Salt, to taste. Approximately 1 teaspoon.
  • Green parts of two scallions, finely chopped.


  1. Mix the soy sauce into the ground meat, and let it marinate for a few minutes.
  2. Heat your wok on high heat, then put in the ground meat and stir-fry until nicely
    browned. Then remove the meat, leaving the drippings in the wok.
  3. Add the onions to the pan, and stir-fry quickly until they start to soften.
  4. Add the vegetables and turnip, and stir around until the veggies just start to cook.
  5. Lower the heat to medium, add the rice, sprinkle with the salt, re-add the ground
    meat, and continue to stir until the rice is hot and just barely starting to brown.
  6. Add the scallions, stir one last time, and serve.

This is a recipe that you should feel free to fool around with. It’s pretty versatile. After thanksgiving, I make leftover turkey fried rice; if we buy a roast duck and have leftovers, I make duck fried rice. It also supposedly comes out very well with smoked ham as the meat. One chinese chef even suggested adding finely diced tomatoes to it, which
surprising worked extremely well!

Capturing More Symmetry using Categories: Groupoids

Today’s entry is short, but sweet. I wanted to write something longer, but I’m very busy at work, so this is what you get. I think it’s worth posting despite its brevity.

When we look at groups, one of the problems that we can notice is that there are things
that seem to be symmetric, but which don’t work as groups. What that means is that despite the
claim that group theory defines symmetry, that’s not really entirely true. My favorite example of this is the fifteen puzzle.


The fifteen puzzle is a four-by-four grid filled with 15 tiles, numbered from 1 to 15, and one empty space. You can make a move in the puzzle by sliding a tile adjacent to the empty
space into the empty. In the puzzle, you scramble up the tiles, and then try to move them back so that they’re in numerical order. The puzzle, in its initial configuration, is shown to the right.

If you look at the 15 puzzle in terms of configurations – that is, assignments of the pieces to different positions in the grid – so that each member of the group describes a single tile-move in a configuration, you can see some very clear symmetries. For example, the moves that are possible when the empty is in any corner are equivalent to the moves that are possible when the empty is in any other corner. The possible moves when the space is in any given position are the same except for the labeling of the tiles around them. There’s definitely a kind of symmetry there. There are also loops – sequences of moves which end in exactly the same state as the one in which they began. Those are clearly symmetries.

But it’s not a group. In a group, the group operation most be total – given any pair of values x and y in the group, it must be possible to combine x and y via x+y. But with the 15 puzzle, there moves that can’t be combined with other moves. If x = “move the ‘3’ tile from square 2 to square 6”, and y = “move the ‘7’ tile from square 10 to square 11”, then there’s no meaningful value for “x+y”; the two moves can’t be combined.

Continue reading

Databases are hammers; MapReduce is a screwdriver.

A bunch of people have sent me links to an article about MapReduce. I’ve hesitated to write about it, because the currently hyped MapReduce stuff was developed, and extensively used by Google, my employer. But the article is really annoying, and deserves a response. So I’m going to be absolutely clear. I am not commenting on this in my capacity as a Google employee. (In fact, I’ve never actually used MapReduce at work!) This is strictly on my own time, and it’s purely my own opinion. If it’s the dumbest thing you’ve ever read, that’s my fault, not Google’s. If it’s the most brilliant thing you’ve ever read, that’s my credit, not Google’s. I wasn’t asked to write this by Google, and I didn’t ask their permission, either. This is just me, the annoying geek behind this blog, writing solely
on my own behalf, speaking for no one but me. Got it?

The reason that I’m interested in this is because it’s related to my PhD work. Back in
grad school, what I worked on was applying parallelism to structured data in
non-scientific applications. That’s pretty much what MapReduce does. And the solution
that I proposed was a kind hierarchical scatter/gather operation – which is, very nearly, the
way that MapReduce works. The big difference? MapReduce beats what I did. The guys who designed MapReduce noticed something that I didn’t, and took advantage of it, which made M/R programs a lot cleaner and easier to write. The article that I’m going to discuss criticizes M/R for exactly that key idea.

Continue reading

Before Groups from Categories: a Category Refresher

So far, I’ve spent some time talking about groups and what they mean. I’ve also given a
brief look at the structures that can be built by adding properties and operations to groups –
specifically rings and fields.

Now, I’m going to start over, looking at things using category theory. Today, I’ll start
with a very quick refresher on category theory, and then I’ll give you a category theoretic
presentation of group theory. I did a whole series of articles about category theory right after I moved GM/BM to ScienceBlogs; if you want to read more about category theory than this brief introduction, you can look at the category theory archives.

Like set theory, category theory is another one of those attempts to form a fundamental
abstraction with which you can build essentially any mathematical abstraction. But where sets
treat the idea of grouping things together as the fundamental abstraction, category
theory makes the idea of mappings between things as the fundamental abstraction.

Continue reading

Friday Recipe: Cantonese Steam Fish

I’m a big fish eater. In general, given a choice about what to eat, I’m
usually happiest when I get to eat a nice fish. Even now that I’ve started eating
beef again, most of the time, I’d rather eat a nice piece of wild salmon
than pretty much anything made of beef.

When it comes to cooking fish, I think that there’s no cuisine that does
a better job with fish than Chinese. The chinese style of cooking fish is, in
my opinion, perfect. It relies on getting really good quality, fresh
fish – and then doing as little to it as you reasonably can, so that the wonderful
flavor of a really fresh fish comes through.

The best example of that is a Cantonese steamed fish. You do so little to
it – and yet the result is one of the best dishes in the entire world. To make this
work, you need a really fresh, smallish fish. I typically do this with either rainbow trout or striped bass, and I try to get it from someplace where I can be sure that the fish was
swimming no more than 24 hours before. The easiest place to find fish like that is usually
a chinese grocery; American grocery stores often have fish that’s been sitting on ice for a long time. Chinese shoppers are, properly, very picky about their fish, so you tend to get it much fresher from a chinese grocery.

Continue reading

Friday Random 10

Haven’t done this in a while: 10 random tracks from my iPhone:

  1. Porcupine Tree, “The Sky Moves Sideways”
  2. Mogwai, “I Chose Horses”. Mellowness from one of the greatest Post-Rock groups around.
  3. Thinking Plague, “Lux Lucet”. Thinking Plague is one of the strangest things
    I listen to. I don’t know quite how to describe it. Often atonal, seriously dissonant when not outright atonal, oddly structured. It’s very peculiar stuff, definitely not to everyone’s taste.
  4. Gordian Knot, “Singularity”. A very hard/loud instrumental piece. Definitely in the prog genre. Beautiful guitar solos, great bass pulse driving it.
  5. Marillion, “King”.
  6. Lunasa, “Punch”
  7. Naftule’s Dream, “The Wanderer”. Would you believe progressive Klezmer?
  8. King Crimson, “Neal and Jack and Me”.
  9. Pink Floyd, “Marooned”. It’s a crime to call this dreck Pink Floyd, when in
    fact it’s really nothing more than Dave Gilmour masturbating with his guitar. Ick.
  10. PDQ Bach, “Es War Ein Dark Und Shtormy Night”. If you’re not in the know,
    PDQ Bach is the alter ego of Music professor Peter Schickele. He claims that PDQ is
    the 13th illegitimate child of J.S. Bach. Schickele in constantly “finding” PDQ Bach
    compositions lining birdcages, etc. This is from PDQ’s period of setting “poetry” to
    what passes for music to PDQ. Featuring words like “Approaching I saw ein Knight in shining armor with ein codpiece enorm,” set to pseudo-Schubert. Great for laughs, and not to be
    missed if you get a chance to see him live!

The Nasty Little Truth about Idiots Who Don't Understand Dimensions

I managed to trash yet another laptop – the city commute through the subways seems to be pretty hard on computers! – so while I’m sitting and slowly restoring my backups, I was looking through the folder where I keep links to crankpots that I’d like to mock someday. I noticed one that I found quite a long time ago – and to my surprise, I realized that I never wrote about it! And given that I’ve been mocking relativity-haters lately, it’s particularly appropriate to cover it now.

The site is called “The Nasty Little Truth About Spacetime Physics”. It takes quite a different approach to criticizing relativity. As we’ve seen in past posts, most anti-relativity rants dislike relativity because it implies that there is no fixed reference frame – that there’s no such thing as an absolute velocity, no distinguished point at the unmoving center of the universe. That’s not this guys tack; no, he’s much smarter than that. His argument is that if you accept the idea of spacetime as defined by relativity, that
it logically implies that motion is impossible – and since we can clearly move, than means
that relativity is wrong!

Some of the most famous physicists in the world are not telling the truth about one of the most taken for granted concepts in scientific history. They are not telling us how they can come up with their fanciful time travel theories (wormholes, advanced and retarded waves traveling in spacetime, etc…) using a model of the universe that precludes the possibility of motion. Nothing can move in spacetime or in a time dimension-axis by definition. This is because motion in time is self-referential. It is for this reason that Sir Karl Popper compared Einstein’s spacetime to Parmenide’s unchanging block universe[*], in which nothing ever happens.

Before I continue, less I be immediately branded as an anti-relativity crank, let me make it perfectly clear that I agree with the mathematical and predictive correctness of both the Special and the General Theory of Relativity.

Now that is some primo crackpottery! You’ve got to love it when the crackpot starts off his argument by both denying that he’s a crackpot, and refuting his own argument!

Continue reading

Fields, Characteristics, and Prime Numbers

When we start looking at fields, there are a collection
of properties that are interesting. The simplest one – and
the one which explains the property of the nimbers that
makes them so strange – is called the
characteristic of the field. (In fact, the
characteristic isn’t just defined for fields – it’s defined
for rings as well.)

Given a field F, where 0F is the additive
identity, and 1F is the multiplicative identity,
the characteristic of the field is 0 if and only if no
sequence of adding 1F to itself will ever result
in 0F; otherwise, the characteristic is the
number of 1Fs you need to add together to get

That sounds confusing – but it really isn’t. It’s just
hard to write in natural language. A couple of examples will
make it clear.

Continue reading