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 What makes linear logic linear?

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 Capturing More Symmetry using Categories: Groupoids

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 Databases are hammers; MapReduce is a screwdriver.

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 Before Groups from Categories: a Category Refresher

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 Recipe: Cantonese Steam Fish