Mark Chu-Carroll (aka MarkCC) is a PhD Computer Scientist, who works for Google as a Software Engineer. My professional interests center on programming languages and tools, and how to improve the languages and tools that are used for building complex software systems.
Chaos is a complicated topic. There are lots of preliminaries that are useful to understand if
you really want to grasp what chaos is, and how you can usefully analyze and characterize it. One
of the really useful concepts is attractors. Attractors aren't specific
to chaotic systems - most real-world dynamical systems have attractors. But attractors
are extremely useful in understanding chaotic systems, and how they different
from more tractable dynamical systems.
So what's an attractor? Take a dynamical system we described in the last post, and look at its
phase space. The phase space isn't just a random cluster of points. It's got a very rich structure
to it. An attractor is a piece of structure of many systems that appears when you view the systems
evolution over time. Speaking informally, an attractor is sort of like a black hole in the
phase space: it's a region of the space where if you get sucked into it, you'll never
leave.
Attractors have shapes, and the shape of the attractor can tell you lots of interesting
things about the behavior of the system. One interesting bit of trivia to convince
you to read the rest of this: chaotic systems have attractors, and the attractors for
chaotic systems usually have fractal shapes.
One of my pet peeves about people and math is that most
people don't really have a clue of what math is. I've been writing
this blog for something over three years, and by the standards of
a lot of people, I've almost never written about math.
Yesterday, my son's kindergarten class had a picnic. On my way home,
I was listening to the local NPR station, which was interviewing some
crossword puzzle writer whose name I cannot remember; I will therefore refer
to him as "crossword-boy". (It was not Will Shortz; Shortz is much smarter than the
guy they were interviewing.) At one point, they asked him something about
Sudoku.
His response was a bit disjointed - he couldn't decide whether to talk about
the history of Sudoku or about his opinion of it. His opinion is that it's
incredibly dull and pointless, and that designing good Sudoku doesn't require as
much creativity as designing good crosswords. (Just that much is annoying: I'm
a Sudoku addict, and I've definitely noticed dramatic differences in Sudokus
from different places. Will Shortz's Sudoku books have great ones; most computerized
Sudoku games generate rather boring ones; the ones in most newspapers are
obviously computer generated.)
In the course of babbling about how uninteresting, non-creative, and
unsatisfying Sudoko puzzles are, he let loose with the real stupidity: "You know,
Sudoku doesn't even have to use numbers, it can use any 9 symbols. It's not a
mathematical puzzle at all.
Because it doesn't rely on arithmetic, according to crossword-boy,
it's not mathematical at all. He went on to say that it's
just a logic puzzle, not a math puzzle at all.
Sorry pal, but logic is math.
Sudoku is an incredibly mathematical puzzle. It's not an
arithmetic puzzle, but it's a highly mathematical one.
In computer science terms, it's a moderately
complex constraint-solving puzzle.
Math is more than arithmetic. It's more than numbers. Math
is really the formal study of logic and structure. Numbers and arithmetic
are one kind of structured system described using logic which can be
studied and understood using math. But pretty much everything
with a precise, formal structure to it has at least an element of
mathematics. The structure of crossword-boy's crossword puzzles
is fundamentally mathematical.
This is an edited repost of something I wrote nearly three years ago. You can
see the original post and comments here.
Over at Dr. Isis's blog, there's a post answering a reader's question about whether to tell her
postdoc advisor about her troubles with clinical depression. I agree with Isis's advice - without
knowing the advisor really well, you can't be sure of how they'll react. If the postdoc
had become ill due to something like a diabetic episode, where the change in schedule and
environment caused by taking a new job messed up the PDs control of their blood sugar - well, there
wouldn't be an issue. The PD would be able tell their advisor they had a medical issue without
worrying too much about repercussions. But mental illness is different: the fact is that there is a
very strong stigma attached to mental illness, which makes it different from other illnesses.
This is something that's very important to me. I have people very close to me who have
dealt with profound mental illness, and I've seen them suffer from the effects of the stigma
associated with it. And I am mentally ill myself: I have clinical depression.
About a month ago, I decided to make a nice special meal for my wife for mothers' day. I asked
her what she wanted, and she said duck. This made me happy, since I consider duck to be one
of the most wonderful foods in the entire universe.
I decided that instead of making one of my regular duck dishes, I'd try something new. I had absolutely no idea what I was going to do: I just went to the store, and looked around
to find something that appealed to me. I ended up creating a dish that's a real winner: duck breast in a port wine and mushroom sauce.
Ingredients
2 large duck breasts
4 shallots
1 clove garlic
3 tablespoons butter.
2 cups red wine.
1/2 cup port wine.
1 pound wild mushrooms, sliced.
4 or 5 dried morels, rehydrated in water, then drained and sliced thinly.
Instructions
Prepare the duck breasts: Take your duck breasts, trim off any
excess fat or gristle, and cut a cross-hatch pattern into the skin on
the breasts. (This will both help the marinade penetrate, and make the
fat in the skins render more cleanly.)
Make the marinade: Put 2 shallots into a food processor, and mince them. Then add
the red wine, and a generous dose of salt.
Put the duck in the marinade, and let it sit for an hour or two.
Sear the duck breasts:
Heat an unoiled pan till it's good and hot.
Take the duck breasts from the marinade, and pat them dry, ten sprinkle
lightly with salt and pepper.
Put the duck breasts into the pan, skin side down. Reduce the heat to medium,
and cook them skin side down for 3 minutes. Then turn them over, and cook for
another three minutes on the other side.
Then remove them from the pan, and let them rest for five minutes. (You can
go ahead and start the sauce while they rest.)
Slice the breasts into medium-thick slices. You want them sliced a bit more thickly
than is typical for a seared duck breast, because they're going to cook a little
bit in the sauce, and you still want the centers to be nice and rare.
Make the sauce:
Slice the second two shallots as thinly as possible.
Melt 2 tablespoons of butter in a pan. Add sliced shallots and the
minced garlic, and cook until the shallots are transparent.
Add the mushrooms, and some salt. Cook until the mushrooms are
done. (How long that'll take will depend on the mushrooms you picked;
fresh chanterelles will cook in seconds; portobellos will take a few minutes.)
Add the port wine, and let the sauce reduce until most of the liquid from the
wine is gone. Taste it now, and add salt and pepper.
Remove from the heat, and add another pat of butter, and stir it around until it
melts.
Put it all together:
Add the sliced duck breast to the hot sauce, and toss it so that the
duck is well coated.
Serve - arrange the duck slices on the plate, and cover with a generous helping
of the mushrooms.
I served this with some slow-cooked collard greens, and a nice bottle
of 1997 Australian Shiraz.
I do all of the cooking in my house; my wife amazing at baking, but she's just totally lost when it comes to cooking. But given my commute, it's hard to start making a nice dinner when I get home, and have it done in time to be able to eat, and have some time with my kids before they go to bed. So I like to make large dishes on the weekend, so that we've got a couple of days during the week when we just need to heat something up. So casseroles are a great thing.
The big secret to it is spices: in my experience, the difference between
a really good pasticcio, and a bland boring one is the spices in the meat. The
flavor of the good ones comes largely from a very nice middle-eastern spice
blend called "ras el hanout". Ras el hanout can be a bit hard to find, but it's worth the trouble of searching for. It's got a lot of ingredients, and the exact
combination is very individual. So you want to either find a recipe and make your own
blend, or else find someplace that makes a good one. It's typically got things like cloves, cinammon, cardamom, mace, paprica, black pepper, and dried rosebuds(!). I've
found a ras that I really like from the spice house.
Ingredients
Meat Sauce:
2 lbs ground beef.
1 1/2 teaspoons ras el hanout.
1 minced onion.
2 large cloves garlic, minced.
2 teaspoons salt.
1 can diced tomatoes.
1/2 teaspoon oregano.
1/4 cup dry sherry.
2 egg whites.
Bechamel:
1/4 cup butter.
1/3 cup flour.
2 cups milk.
2 eggs + 2 egg yolks.
1/4 cup parmesan cheese.
1 teaspoon salt.
Pasta:
1 1/2 lbs pasta.
1 tablespoon butter.
1 pinch salt.
Instructions:
Cook the pasta. (to be authentic, it should be long hollow noodles - like
uncut penne; I just used penne). When its done, toss it with just enough butter
to stop it from sticking together, and a pinch of salt.
On high heat, brown the meat. While it's cooking, add most of the salt,
and half the ras el hanout.
Remove the meat from the pan. Deglaze with the sherry, and dump the liquid into the meat.
Add some olive oil to the pan on medium heat.
Add the onions and the garlic, and sautee them until they're translucent.
Add the meat back to the pan.
Add the can of tomatoes, any remaining sherry, the remaining ras el hanout,
and the oregano. When it comes to a boil, reduce the heat, and simmer until most of the
liquid has evaporated. Remove from heat, and set aside to cool.
When it's cooled a little bit, mix in the egg whites. It should be cooled enough that the eggs
don't just cook when they hit the meat. They're there to act as a binder, to get the meat to
hold together in the casserole, so you don't want them to bind until the casserole is
cooked.
Melt the butter on medium heat. When it's all melted, add the flour, and cook until the
flour starts to turn golden. Then add the milk and salt. Cook it until it thickens - it
should turn very thick.
Once it's thickened, remove it from the heat, and add in the grated cheese and the eggs,
and mix thoroughly.
In a rectangular casserole, put half of the pasta on the bottom of the pan. Cover it
with half of the meat. Then add the other half of the pasta, and the remaining meat.
Spoon the bechamel sauce over the top of the casserole, to form an even layer.
Cover lightly with foil, and bake at 350 for 30 minutes.
Remove the foil cover, and bake for another 20 minutes, until the bechamel on top starts
to brown.
In my first chaos post, I kept talking about dynamical systems without bothering to define them. Most people who read this blog probably have at least an informal idea of what a dynamical system is. But today I'm going to do a quick walkthrough of what a dynamical system is, and what the basic relation of dynamical systems is to chaos theory.
The formal definitions of dynamical systems are dependent on the notion of phase space. But before going all formal, we can walk through the basic concept informally.
The basic idea is pretty simple. A dynamical system is a system that changes
over time, and whose behavior can be (in theory) described a function that takes
time as a parameter. So, for example, if you have a gravitational system which
has three bodies interacting gravitationally, that's a dynamical system. If you
know the initial masses, positions, and velocities of the planets, the positions of all three bodies at any future point in time is a function of the time.
One mathematical topic that I find fascinating, but which I've never had
a chance to study formally is chaos. I've been sort of non-motivated about
blog-writing lately due to so many demands on my time, which has left me feeling somewhat guilty towards those of you who follow this blog. So I decided to take this topic about which I know very little, and use the blog as an excuse to
learn something about it. That gives you something interesting to read, and
it gives me something to motivate me to write.
I'll start off with a non-mathematical reason for why it interests me.
Chaos is a very simple idea with very complex implications. The simplicity of
the concept makes it incredibly ripe for idiots like Michael Crichton to
believe that he understands it, even though he doesn't have a clue. There's an astonishingly huge quantity of totally bogus rubbish out there, where the authors are clueless folks who sincerely believe that their stuff is based on chaos theory - because they've heard the basic idea, and believed that they
understood it. It's a wonderful example of my old mantra: the worst math is no math. If you take a simple mathematical concept, and render it into informal non-mathematical words, and then try to reason from the informal stuff, what
you get is garbage.
The Flower Kings, "The Truth Will Set you Free": One of the superlong Flower Kings opuses - in fact, the first thing by the Flower Kings that I ever heard.
Solas, "Pastures of Plenty": a stunning version of the old Guthrie song, played by one of my favorite Irish bands. It's a brilliant cover - the original song is clearly there, and yet its embedded in a reel.
Valley of the Giants, "Cantara Sin Guitara": truly fantastic post-rock. Valley of the Giants is the first PR ensemble that I think really
stacks up to Godspeed.
Jadis, "Standing Still": neo-progressive rock, produced by
Marillion's guitarist. It's a bit on the poppy side, but after listening
to it a bunch of times, it's really grown on me. Jadis's songs tend to have
decent poppy hooks, but they've also got a lot of complexity, and they
have the ability to keep surprising you with their changes even after
multiple listenings.
Riverside, "Volte-Face": more neo-prog. But this time, it's a band that I love without reservations. Riverside is the greatest new band that
I've heard in a very long time. Highly recommended.
Keith Emerson Band, "The Art of Falling Down": the great Keith Emerson is back. Emerson is a really brilliant keyboardist, and I used
to love his stuff with ELP. But then ELP fell apart; he tried to bring it back a couple of times, with results ranging from mediocre (Emerson, Lake and Powell) to piss-poor (Three). Then he went off to do mediocre movie soundtracks. And now, he's back with a new prog-rock band. And they're good. They're not ELP, but they're better than any other post-ELP work that he's done.
Cynic, "Evolutionary Sleeper": What do you get when you mix up
death metal, neo-progressive rock, and jazz fusion? That's the best
description I can come up with for Cynic. I gave Cynic a listen based on
a suggestion from a reader after I raved about Gordian Knot; Cynic includes
Sean Malone, the genius behind GK. They're really excellent.
Darcy James Argue's Secret Society, "Transit": another hard to describe group. Modern big-band jazz, with influences from classical
music. Very interesting stuff. Not my favorite, but definitely very cool and well worth a listen. I suspect it will grow on me with time.
Van Der Graaf Generator, "The Sleepwalkers (live)": Wow.
John Corigliano, "Fantasia on an Ostinato": Corigliano is one of my favorite modern classical composers. This is an intimate little piece for solo piano. Very beautiful, very stirring, and yet very delicate.
And as a special bonus, this irresistible video of two dancers playing Bach's Tocatta and Fugue on the giant piano at FAO Schwartz.
As an alert commenter pointed out, I left out one really important thing in
my earlier post about finger trees. That's what I get for trying to write when
I'm sick :-). Seriously, this is a point that's implied by the post as it stands, but never explicitly stated - and since it's really important, it
should be stated explicitly.
The monoid-annotated tree structure doesn't replace the original
data structure: it's superimposed on it.
So, as I said: cons-cell style lists are ubiquitous and beloved by
functional and non-functional programmers. In finger trees, you're
not getting rid of them. The point of finger trees is to let
you keep the convenient data structure, with its basic operations
and properties intact, and to augment it with a tree that lets you search it efficiently.
To illustrate: here's the number list example from yesterdays post. The
original list is at the bottom, with green pointers representing the
original cons-list next-pointers. The monoid-annotated tree is on top,
with red pointers. The combination of the original list with the
monoid annotated tree is a finger tree.
The point of this is that you've still got your cons list. All of the
beautiful recursive/iterative algorithms that walk the list continue to
work exactly the way that they would in the traditional cons-list: for code that walks the list, the fact that there are finger-tree pointers
sitting on top of the list is irrelevant - and, in fact, completely invisible. For algorithms that want to search the list, the tree structure is there,
and allows the searches to be performed much more quickly than they could be on
the traditional list. The superposition of those two structures is the
genius of the finger tree.
For ages, I've been promising to write about finger trees. Finger trees are
an incredibly elegant and simple structure for implementing sequence-based
data structures. They're primarily used in functional languages, but there's nothing
stopping an imperative-language programmer from using them as well.
In functional programming languages, lists are incredibly common. They show up everywhere; they're just so easy to use for recursive iteration that they're ubiquitous. I can't think of
any non-trivial program that I've written in Haskell, Lisp, or OCaml that doesn't use lists. (Heck, I've wound up using cons-cell libraries a couple of times in C++.)
Of course, lists aren't perfect. In fact, for some things, they absolutely suck. Suppose I've got a really long list - like a list of names and phone numbers from a telephone book. My local phone book has 600 pages of names; and the pages are incredibly dense - there've got to be at least a couple of hundred names per page. So in a phone book for a suburban region of New York City, the list of phone numbers will have 120,000 names. Now imagine that I want to look
up one name in that list - on average, I'm going to have to chase through 60,000 pointers. 60,000 isn't a huge number for a computer, but still, chasing 60,000 pointers is a pretty big deal. If I stored them in an array, it would be a lot less convenient for some tasks, but I could use
binary search to find names, and I could find any name in no more than 16 comparisons - and the whole shebang would be contiguous, so I wouldn't even be chasing pointers.
What finger trees do is give me a way of representing a list that has both the convenience
of the traditional cons list, and the search efficiency of the array based method.
