Friday Random Ten, May 29th

Leave a reply
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. Van Der Graaf Generator, “The Sleepwalkers (live)”: Wow.
  10. 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.

Finger Tree Update: I forgot something

11 Replies

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.

counted-finger-tree-list.png

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.

Finally: Finger Trees!

Leave a reply

stone fingers_478fc739a1585.jpg

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.

Continue reading →

Cloud Computing

Leave a reply

cloud-creatures.jpg

In general, I try to keep the content of this blog away from my work. I don’t do
that because it would get me in trouble, but rather because I spend enough time on work, and blogging is my hobby. But sometimes there’s an overlap.

One thing that’s come up in a lot of conversations and a lot of emails it the idea of cloud computing. A lot of people are interested in it, but they’re not really sure of what it is, or what it means.

So what do we mean when we talk about “cloud computing”? What’s the cloud? How’s it different from good old-fashioned client/server computing?

Continue reading →

You can't write that number; in fact, you can't write most numbers.

Leave a reply

In my Dembski rant, I used a metaphor involving the undescribable numbers. An interesting confusion came up in the comments about just what that meant. Instead of answering it with a comment, I decided that it justified a post of its own. It’s a fascinating topic which is incredibly counter-intuitive. To me, it’s one of the great examples of how utterly wrong our
intuitions can be.

Numbers are, obviously, very important. And so, over the ages, we’ve invented lots of notations that allow us to write those numbers down: the familiar arabic notation, roman numerals, fractions, decimals, continued fractions, algebraic series, etc. I could easily spend months on this blog just writing about different notations that we use to write numbers, and the benefits and weaknesses of each notation.

But the fact is, the vast, overwhelming majority of numbers cannot be written
down in any form.

That statement seems bizarre at best. But it does actually make sense. But for it to
make sense, we have to start at the very beginning: What does it mean for a number to be describable?

Continue reading →

Dembski Responds

83 Replies

Over at Uncommon Descent, Dembski has responded to my critique of
his paper with Marks. In classic Dembski style, he ignores the
substance of my critique, and resorts to quote-mining.

In my previous post, I included a summary of my past critiques of
why search is a lousy model for evolution. It was a brief summary of
past comments, which did nothing but set the stage for my
critique. But, typically, Dembski pretended that that was the entire
substance of my post, and ignored the rest of it. Very typical of
Dembski – just misrepresent your opponents, create a strawman, and
then pretend that you’ve addressed everything.

Continue reading →

Friday Random Ten, May 8th

Leave a reply
  1. Gordian Knot, “Singing Deep Mountain”: As frequent readers of my FRTs may have figured out, I’m not typically a big fan of instrumental progrock. Most of the time, I find it to be
    cold, sterile stuff – technically impressive, even amazing – but utterly devoid of meaning,
    emotion, or feeling. Gordian Knot is one of my favorite counter-examples to show that it’s not
    the vocals that I’m missing; GK manages to create instrumental music that’s got
    both incredible technical virtuosity and real feeling.
  2. Jason Ricci and New Blood, “I Turned Into a Martian”: a few weeks back,
    a commenter on my last FRT suggested that I might like Jason Ricci and New Blood. He
    was absolutely right. One YouTube video I found describes Ricci as “a cross between
    Muddy Waters and Frank Zappa”. That’s a pretty dead-on description. Ricci and New Blood
    play incredible blues, with a mixture of other influences, which would be pretty
    decent stuff just by itself. But then Ricci is a nearly supernatural harmonica player.
    The things that the guy can do with a harmonica are just astonishing. And the rest of the band aren’t exactly slouches. Highly recommended. (YouTube clip at the end of the post.)
  3. Spock’s Beard, “The Slow Crash Landing Man”: Decent neo-prog. Not a particularly
    special track, but not bad.
  4. Riverside, “Before”: Riverside is a band I recently discovered via E-music. They’re
    a phenomenal neo-progressive band. Their sound is hard to describe; somewhere between
    Marillion, King Crimson, and Porcupine Tree.
  5. Mono, “mere your pathetic light”: another really fantastic post-rock ensemble,
    very much in the “godspeed” vein. Really excellent stuff.
  6. Frost, “Welcome to Nowhere”: Yet another new neo-progressive band for me. I was
    ordering some CDs, and threw this in on a whim. They’re quite good – a bit on towards the
    poppy-end of neo-progressive. If you like Marillion, there’s a good chance you’ll like these guys. In particular, they’re good at the same kind of wonderful transition that Marillion is known for.
  7. Steve Hackett, “Omega Metallicus”: Hackett is always terrific.
  8. Marillion, “80 Days”: speak of the devil, Marillion pops up. As much as I like some
    of the new, Marillion influenced neo-progressive bands, when Marillion comes through the headphones, it’s just different. There’s just a depth to them that not many bands can
    match. Spock’s Beard, Frost, Jadis – they’re good. But they’re not in the same league as
    Marillion.
  9. Tony Trischka Band, “Haunted Hand”: Tony Trischka’s first album with his jazz band. I’m a bit biased here, because I know Tony personally, and he’s one of the most genuinely
    nice people I know. I love his band, and Tony playing jazz on the Banjo is even
    better than Bela Fleck.
  10. The Flower Kings, “The Melting Pot”: and if you want to make even Marillion sound
    like a bunch of pikers, just put on the Flower Kings.

Dembski's Latest: "Life's Conservation Law", and why it's stupid

Leave a reply

So. William Dembski, the supposed “Isaac Newton of Information Theory” has a new paper out with co-author Robert Marks. Since I’ve written about Dembski’s bad IT numerous times in the past, I’ve been getting email from readers wanting me to comment on this latest piece of intellectual excreta.

I can sum up my initial reaction to the paper in three words: “same old rubbish”. There’s really nothing new here – this is just another rehash of the same bankrupt arguments that Dembski has been peddling for years. But after thinking about it for a while, I realized that Dembski has actually accomplished something with this paper: in his attempt to argue that evolution can’t possibly outperform random-walks without cheating, he’s actually explained exactly how evolution works. He attempts to characterize that as cheating, but it doesn’t work.

Continue reading →

Moronic Probability and Stupid Physics

Leave a reply

Via the Bad Astronomer comes one of the most pathetic abuses of
probability that I’ve ever seen. I’m simply amazed that this idiot was willing
to go on television and say this.

The Daily Show With Jon Stewart M – Th 11p / 10c
Large Hadron Collider
thedailyshow.com
Daily Show
Full Episodes		 Economic Crisis First 100 Days

The crank in question is Walter Wagner, the moron who tried to use a lawsuit
to stop the LHC from being activated. (Just that much, already, is amazingly silly;
he sued in Hawaii, but the LHC is in Geneva, Switzerland. How does a Hawaiian court
have any jurisdiction?)

Anyway… Wagner claims that the LHC could destroy the earth. See, there’s a tiny theoretical chance that the right collision in the LHC could create a microscopic black hole. According to Wagner, if that happens, the black hole will swallow the entire earth.

That claim is, itself, based on some pretty bad math. The only theory that predicts
that it’s possible to create a microscopic black hole also predicts that such a black
hole would evaporate – that is, would completely disappear in a burst of energy – immediately. The
exact same math that predicts that you could create a black hole in a high-energy collision also
predicts that the hole would be destroyed before it had time to do any damage. If you tweak it so that the black hole lasts longer, the energy requirements change so that it’s no longer possible to create it in the LHC. To make the black hole last a microsecond is absolutely beyond the
energy of any collider that we could ever build on the earth.

But let’s skip that – demonstrating that is pretty complicated. To get an idea of
the level of understanding of the guy who claims that there’s a real danger, let’s just
take a look at what he says.

When asked what the probability of the LHC destroying the earth is, he says 50%. Why?
Because either it could happen, or it couldn’t – therefore, there’s a 50% chance of it happening.

You could argue that that’s naive Bayesian reasoning – but if you did, you’d be an idiot. Classic Bayesian arguments about stuff like this would say that you use 50/50 as an initial prior in the absence of any other information; then you adjust that based on whatever
other information you have available. For Mr. Wagner’s stupid argument, it’s based on
a complex physical theory – a complex physical theory which provides lots of information
which you can use to update your probability estimate.

Mr. Wagner’s 50/50 claim is based on the fact that he’s absolutely clueless about how any of
this stuff works. He clearly doesn’t understand probability, and he clearly doesn’t understand
physics.

But he’s awfully funny.

A Quick Bit of Temporal Logic: Introducing CTL

Leave a reply

This post is something that I’m thinking of including in my
book. I haven’t decided whether I want to spend this much time on
logics; they’re really interesting and fun – but there’s lots of
other interesting and fun stuff, and there’s only so much space.

The topic of the moment is temporal logic – that is, a logic which
is built for reasoning about things that change over time.

To begin with, why do we want temporal logic? Most of the time,
when we want to use logical reasoning, we use predicate logic. So why
do we need another logic?

Continue reading →