Monthly Archives: November 2007

From Sets to Numbers: Climbing Up to the Rationals

When last we left off, I’d used set theory to show how to construct the natural numbers; and then from the natural numbers, I showed how to construct the integers. Now, we can take the next step in building
up the full tower of numbers, showing how if we’ve got the natural numbers defined in sets, we can define
the rational numbers using sets and our constructed integers.

Continue reading

Billy's Best Buddy Billy: Order isn't order unless Billy or Billy say it's order!

An alert reader pointed out that William Brookfield posted a response to
my two part debunking of his argument for design based on a mangling of the second law of thermodynamics. I debated whether it was worth responding to; Mr. Brookfield’s got so little readership that I never noticed his response in my referals, even though it was posted on July 3rd! I check my referals regularly (I’m obsessive about seeing who is linking to my blog), and I’ve never seen ICON-RIDS show up.

But, today, I’m sitting in the hospital while my mother has knee surgery; I’m bored; and I have a throbbing headache. So I’m not up to doing much that requires any serious exercise of my brain. So mocking a moron seems right up my alley this afternoon.

Continue reading

Erlang: a Language for Functional Concurrency (Updated!)

Several commenters pointed out that I made several mistakes in my description of Erlang. It turns out that the main reference source I used for this post, an excerpt from a textbook on Erlang available on the Erlang website, is quite out of date. I didn’t realize this; I assumed that if they pointed towards that as a tutorial, that it would represent the current state of the language. My bad. As a result, several things that I said about Erlang – including some negative comments, were inaccurate. I’ve updated the article, and the changes are marked with comments.

As long-time readers will recall, one of my greatest interests in programming languages. A while back, I wrote a tutorial on Haskell, which is one of the most influential languages currently in the programming language research community. Haskell is a pure, lazy, functional language which gained a lot of attention in recent times for being incredibly expressive, while maintaining a solid theoretical basis with well-defined semantics. What made Haskell unusual was that it’s a completely pure functional language – meaning no true state at all – not for I/O, not for assignment, not for mutable data – but through the
use of a clever construct called a monad, you can create the effect of state without disturbing the functional semantics of the language. It’s quite a nice idea, although I must admit that I remain somewhat skeptical about how scaleable it might be.

One of the competitors of Haskell for mindshare in the community of people who are interested in functional programming languages is a language called Erlang. In many ways, Erlang is a polar opposite to Haskell. Erlang is, basically, a functional language, but it’s designers didn’t object to tossing in a bit of state when it made things easier. It’s dynamically typed,
and even for a dynamically typed language, it’s support for typing is weak. It’s gotten its attention for a couple of big reasons:

  1. Erlang was designed by Ericsson for implementing the software in their switches and routers. It’s the first functional language designed by a company for building production applications for extremely complex performance-critical low-level applications like switching and routing.
  2. Erlang is specifically designed for building distributed systems. As I’ve mentioned before, programming for distributed systems is incredibly difficult, and most programming languages are terrible at it.

Concurrency and distributed systems are a big deal. I’d argue that programming for concurrency and distribution are the biggest problems facing software developers today. Pretty much every computer that you can buy has multiple processors, and to take full advantage of their power, code needs to use concurrency. And the network is an unavoidable part of our environment: many of the applications that we’re writing today need to be aware of the internet, and need to interact with other systems. These are just simple facts of the modern computing world – and software developers need tools to deal with them.

Continue reading

Almost Friday Recipe: Carmelized Onions, Mushroom, and Sausage Stuffing

Because of the holiday, I’m posting my recipe early this week. It’s actually too late, but I don’t let little things like reality worry me.

This is my thanksgiving turkey stuffing. The origins of this stuffing date back to my discovery of the “black turkey” recipe. I tried it one year, and the stuffing was really good, but the whole thing was just insanely overdone – everything about it was overcomplicated, and there were so many spices muddled up in the stuffing that I just didn’t believe that there was any way that you could taste all of them. So over the next few years, I experimented, and eventually came up with this recipe, which makes the best stuffing I’ve ever tasted. I actually prefer to cook this outside of the bird – it develops a nice crust baked on its own. But to give it that “roasted in the turkey flavor”, I usually take a basting bulb, and give it a few good squirts of turkey drippings while it’s cooking.

Ingredients

  • 3 loaves of bread, preferably a bit stale.
  • 3 lbs sweet yellow onions, sliced thin.
  • 6 cloves garlic, minced.
  • 2 lbs portabello mushrooms, diced into 1/2 inch cubes
  • 1 lb miscellaneous mushrooms, sliced.
  • 1/2 head fennel, sliced thin.
  • 2 stalks celery, diced.
  • 3 carrots, diced.
  • 2 lbs sweet italian sausage. (I use turkey sausage, but real pork sausage would probably be even better.)
  • Salt and pepper.
  • 1 tsp each marjoram and thyme.
  • 1/2 tsp dry mustard.
  • Olive oil.
  • 4 cups chicken stock.
  • 1/2 cup brandy.

Instructions

  1. Heat about 4 tablespoons olive oil on medium high heat. Add all of the onions, and cook them until they’re well carmelized. This will probably take between a half hour and 45 minutes. If the onions start to stick to the bottom of the pan, add some water to get them to unstick.
  2. Reduce the heat to medium, add a bit more oil, then add the garlic, fennel, carrots, and celery,
    and cook until the vegetables are soft.
  3. Add the mushrooms, and let them cook through.
  4. Add the spices, and salt and pepper to taste.
  5. Add the brandy and about 2 cups of the chicken stock, and stir. When it comes to a boil, turn off the heat.
  6. Throw the bread into a food processor, and grind it into coarse crumbs. Pour the crumbs over the cooked stuffing base. Press the crumbs down until some of the liquid from the base comes
    through the crumbs. Add enough stock to make the bread moist. Then let it sit for 15 minutes
    or so.
  7. Stir the bread crumbs into the stuffing base. Cover it, and set it aside to cool. It needs
    to be cooled to room temperature, which will take at least an hour.
  8. Get the sausage, and remove it from its casings. Fold the meat into the stuffing mixture until
    it’s well blended. Add more stock if you need to to keep everything moist.
  9. Take a large roasting pan, and oil it liberally with olive oil. Then put the stuffing into
    it, pressing it in so that it’s packed tightly. Brush to top lightly with olive oil.
  10. Bake in a 350 degree oven until the inside of the stuffing reaches 170 degrees. Baste
    with turkey drippings once or twice while it’s baking. Depending on the depth of your roasting
    pan, this will take between one and two hours.

From Sets to Arithmetic

Even though this post seems to be shifting back to axiomatic set theory, don’t go thinking that we’re
done with type theory yet. Type theory will make its triumphant return before too long. But before
that, I want to take a bit of time to go through some basic constructions using set theory.

We’ve seen, roughly, how to create natural numbers using nothing but sets – that’s basically what
the ordinal and cardinal number stuff is about. Even doing that much is tricky – witness my gaffe about
ordinals and cardinals and countability. (What I was thinking of is the difference between the ε series in the ordinals, and the ω series in the cardinals, not the ordinals and cardinals themselves.) But if we restrict ourselves to sets of finite numbers (note: sets of finite numbers, not finite sets of numbers!), we’re pretty safe.

Of course, we haven’t defined arithmetic – we’ve just defined numbers. You might think it would be
pretty important to define arithmetic on the numbers. If you thought that, you’d be absolutely
Correct. So, that’s what I’m going to do next. First, I’m going to define addition and subtraction – multiplication can be defined in terms of addition. Division can be defined in terms of multiplication
and subtraction – but I’m going to hold off on defining division until we get to rational numbers.

Continue reading

Friday Recipe: Chicken and Bean Sprouts

This is a very simple, authentic chinese dish. It’s a great example of what real chinese food
is like – it’s a lot lighter and more delicate than what’s typically passed off as Chinese food in the US. You should really go to a chinese grocery store for the bean sprouts: you’ll get them fresher, and a
hell of a lot cheaper. (My local chinese grocery sells bean sprouts for under $1/lb; at the local
grocery store, I can buy one-half a pound of sprouts for $4.) Like most real chinese food, a this isn’t
a full meal by itself – a real chinese meal has several contrasting dishes served together.

Ingredients

  • 1 lb. fresh bean sprouts.
  • 1/2 large onion, sliced thin.
  • 3 large dried black mushrooms.
  • 1 teaspoon sugar.
  • 1 teaspoon salt.
  • 3 tablespoons soy sauce.
  • 2 tablespoon vodka.
  • 2 chicken breasts, sliced into long thin strips.
  • 3 scallions, green parts sliced thin.

Instructions

  1. Remove the soaked mushrooms from the water, squeeze the excess water out, and
    slice them into narrow strips.
  2. Take the sliced chicken breast, and mix in 1 tablespoon of the
    soy, and 1 tablespoon of the vodka, and let it sit for five minutes.
  3. Heat a pot of boiling water, and blanch the bean sprouts for about 1 minute,
    then remove and rinse with cold water.
  4. Heat a wok on high heat, until it’s smoking hot. Put in about 1 tablespoon of
    oil, then add the chicken, and stir fry until it’s browned and just barely cooked through. Then remove it
    the wok, and put it aside. Try to leave as much of the oil from cooking the chicken as you can in
    the wok.
  5. Add a bit more oil to the wok – just enough to be able to cook the onions. Make sure the
    wok is really hot, then add the onions. The idea is to get them to brown on the outside,
    while the centers are still almost raw.
  6. As soon as they start to brown a bit, add in the bean sprouts, and stir around. This will cool
    the wok a bit, because of the bulk of the sprouts.
  7. Add the mushrooms, the salt, the sugar, the remaining soy and vodka, and the chicken.
  8. Stir around until the sprouts are nice and hot. Add the scallions, give it one last
    stir, and then dump it into a serving bowl.

Serve it with rice.

Tiptoeing into Type Theory

When Cantor’s set theory – what we now call naive set theory – was shown to have problems in the form of Russell’s paradox, there were many different attempts to salvage the theory. In addition to the axiomatic approaches that we’ve looked at (ZFC and NBG), there were attempts by changing the basis of set theory – discarding sets in favor of something similar, but with restrictions that avoid the problems of naive set theory. Today, I’m going to talk about an example of the latter approach, called type theory. Type theory is a very different approach from what we’ve seen before, and one which is particularly useful and interesting to people in my neck of the woods.

Continue reading

Basics: Proof by Contradiction

I haven’t written a basics post in a while, because for the most part, that well has run dry, but once
in a while, one still pops up. I got an email recently asking about proofs by contradiction and
counterexamples, and I thought that would be a great subject for a post. The email was really
someone trying to get me to do their homework for them, which I’m not going to do – but I can
explain the ideas, and the relationships and differences between them.

Proof by contradiction, also known as “reductio ad absurdum”, is one of the most beautiful proof
techniques in math. In my experience, among proofs of difficult theorems, proofs by contradiction are the
most easy to understand. The basic idea of them is very simple. Want to prove that something is true? Look
at what would happen if it were false. If you get a nonsensical, contradictory result from assuming its
false, then it must be true.

Continue reading

Why did Set Theory start with transfinite numbers?

I was visiting my mom, and discovered that I didn’t leave my set theory book on the train; I left it at her house. So I’ve been happily reunited with my old text, and I’m going to get back to a few more posts about the beautiful world of set theory.

When you talk about set theory, you’re talking about an extremely abstract notion, one which is capable of representing all sorts of structures: topological spaces, categories, geometries, graphs, functions, relations, and more. And yet, almost every description of set theory plunges straight into the cardinal and ordinal numbers. Why? That’s a question that mystified me for quite a long time. Why do we take this beautiful structure, which can do so many things, and immediately jump in to these odd things about infinities?

Continue reading

Friday Recipe: Catfish in Dashi Sauce

This dish is one of my own creations. It’s inspired by reading
Ming Tsai’s cookbooks, and seeing how he combines things. But as far as I
know, he doesn’t do anything like this.

You really need catfish for this. I’ve tried it with other fish, but
it just doesn’t work as well. Catfish has a unique flavor and texture which
is particularly well-suited to this.

Continue reading