Moonbase

I spent some time skimming Jörg Arndt’s ebook Matters Computational (formerly titled “Algorithms for Programmers”) today. It’s the companion to his comprehensive library of C++ algorithms FXT, and probably one of the most impressive programming resorces I’ve read in a long time. Just the low-level bit-manipulation section alone is worth the download. Subject matter (corresponding to the content of FXT) includes:

Fast Fourier Transform (FFT), complex and real-valued, Fast Hartley Transform (FHT). Convolution (cyclic, linear and weighted), correlation and power spectrum. Mass storage convolution and fast multiplication routines. Number Theoretic Transform (NTT), Walsh Transform, Reed-Muller transform, Haar Transform, Wavelet Transform. Combinatorial generation: Combinations, Permutations, subsets. Sorting, Searching, Stack (FIFO), Queue (LIFO), heap and priority-queue. Bit-manipulations, shift registers (LFSR), modular arithmetic and computation in binary finite fields GF(2**n).

(From FXT’s LSM entry)

According to the author, a print version will also be available soon, but the ebook will remain online for free download. Check it out!

Here’s a chiptune I wrote for practice today. It’s a little repetitive, but not very long and kind of fun:

Chiptune – 2010-06-04 by MenTaLguY

Those of you who have played the original NES Ninja Gaiden probably remember dying. A lot. Ever wonder how protagonist Ryu Hayabusa would fare if he were put in a game of more modest difficulty?

Behold.

Super Mario Bros. Crossover – Ryu Hayabusa Trailer

(Super Mario Bros. Crossover and the Ryu video was created by Exploding Rabbit)

I learned last night that the recent “sinkhole” in Guatemala isn’t actually a sinkhole (the result of dissolving carbonaceous rock), but a “piping feature” caused by water transporting loose subsurface material in an extreme type of erosion.

(Image credit: Paulo Requec, via the Government of Guatemala)

This distinction has important implications for what caused the hole, how to deal with it, and whether it is likely to happen again.

Read more...

Last year, Cliff Click gave a great talk about the behavior of modern processors at JavaOne. (It originally made the rounds in January actually, but I wasn’t actively blogging at the time.) It’s absolutely essential watching for anyone interested in parallel programming, since it covers many aspects of modern cache and execution architecture which get exposed when you start running code in parallel in a shared-memory setting. But he has a lot to say even when it comes to single-threaded performance.

Chances are that if you haven’t watched this talk, your mental picture of the hardware you program is wrong. Even if you don’t have time to watch the talk itself, his slides are available in PDF format.

The Resurgence of Parallelism is a really wonderful capsule summary of the state of art in parallel programming, most of which was established decades ago, prior to the present parallel computing renaissance.

Parallel computation has always been a means to satisfy our never-ending hunger for ever-faster and ever-cheaper computation. In the 1960s and 1970s, parallel computation was extensively researched as a means to high-performance computing. But the commercial world stuck with a quest for faster CPUs and, assisted by Moore’s Law, made it to the 2000s without having to seriously engage with parallel computation except for supercomputers. The parallel architecture research of the 1960s and 1970s solved many problems that are being encountered today. Our objective in this column is to recall the most important of these results and urge their resurrection.

You know what they say: those who fail to learn about the past are doomed to reinvent it, poorly. If you’re not a subscriber or a member of the ACM, give the article a read before it disappears behind the ACM paywall!

(Hat Tip: Lambda the Ultimate)

Edit: An aside, regarding one of the article’s conclusions:

The full benefits of functional programming and composability cannot be fully realized unless memory management and thread scheduling are freely managed at runtime. In the long run, this will require merging computational memory and file systems into a single, global virtual memory.

I suspect this is true, but I think we are also going to have to sacrifice the illusion of locality to do it. The resulting global storage is not going to look quite like the virtual memory of today.

Boston Dynamics’ LittleDog robot is a scaled-down counterpart to their more famous BigDog (essentially a robotic pack animal — despite what the pictures might suggest, it doesn’t move with particular grace), used for exploring the finer points of locomotion in controlled settings. Some people find these robots threatening, but personally speaking I think they’re rather beautiful. These sorts of things deserve to be appreciated not only as technology, but also as art.

Recent versions of the LittleDog control software originally by Dr. Katie Byl are becoming especially impressive:

The latest version of the LittleDog Robot

Of course not every demo comes out so perfectly (though I believe this is older footage):

LittleDog Clips and Outtakes

Edit: having thought about CouchDB views more, it probably makes sense to do things more like CouchDB as far as sorting: CouchDB has distinct document IDs and (explict) sort keys. “Intrinsic” (implicit) document ordering is hairier to deal with.

I should have realized this sooner. My work-in-progress static site generator Hx has a lot in common with document-oriented databases like CouchDB, and even CouchDB in particular. So much so that I’m in grave danger of reinventing the wheel.

Like CouchDB, Hx deals with a store of structured documents, and identifies these documents using hierarchical (slash-separated) paths as document ids. As in CouchDB, Hx documents are serialized data structures. Just like in CouchDB, Hx has “views” (although I call them “filters”) which have a mapping function which takes an (id, document) pair and emits zero or more new (id, document) pairs. I could go on, but I’ve probably made my point…

(Of course, if it came down to it, Hx would make a really crappy CouchDB replacement. It doesn’t even do the same kind of work on the user-facing end. It’s just that there’s an awful lot of overlap in the problem space that the internals are concerned with.)

I really should have caught on to this when I wrote an experimental CouchDB storage backend for Hx and it turned out to be so extraordinarily trivial. I guess it took a while to sink in.

At this point I’m almost wondering whether I should drop most of the Hx codebase and use CouchDB for everything but the front-end page templating. Hx does have some features which would be hard to do directly with CouchDB:

• pluggable storage backends, and support for reading from multiple backends at once
• a default storage backend (an inheritance from Hobix) which uses YAML files in a directory structure
• a mechanism for subsetting and remapping the document id space (mostly for the sake of mapping documents to different output paths)
• a fairly convenient YAML DSL for building “views” as pipelines
• support for Liquid templates as “views”
• a notion of intrinsic document ordering

So, there are actually a lot of subtle impedence mismatches which would prevent me from replacing most of the Hx internals which CouchDB right now. But, perhaps some of the features which cause them are worth sacrificing. For example, YAML is nicer to edit than raw JSON, but I could always convert JSON documents to YAML and back for human editing (via e.g. hx edit). Old Hobix users (like me for example, I just carried over my Hobix entries to Hx) would be left out in the cold, but I could always provide a script to import Hobix entries into CouchDB. Do I really need views to be order-preserving? I could always sort later in the pipeline.

Something for me to think about anyway.

I read a really striking article on the New York Times site this morning, where writer Laura Munson recounts one of the darkest periods of her marriage. Despite the opening, it’s not a divorce story, and it’s not a begging-him-to-stay story, but something else entirely.

Sure, you have your marital issues, but on the whole you feel so self-satisfied about how things have worked out that you would never, in your wildest nightmares, think you would hear these words from your husband one fine summer day: “I don’t love you anymore. I’m not sure I ever did. I’m moving out. The kids will understand. They’ll want me to be happy.”

…

Gut-wrenching pause. How could he say such a thing? That’s when I really wanted to fight. To rage. To cry. But I didn’t.

Instead, a shroud of calm enveloped me, and I repeated those words: “I don’t buy it.”

You see, I’d recently committed to a non-negotiable understanding with myself. I’d committed to “The End of Suffering.” I’d finally managed to exile the voices in my head that told me my personal happiness was only as good as my outward success, rooted in things that were often outside my control. I’d seen the insanity of that equation and decided to take responsibility for my own happiness. And I mean all of it.

…

I said: “It’s not age-appropriate to expect children to be concerned with their parents’ happiness. Not unless you want to create co-dependents who’ll spend their lives in bad relationships and therapy. There are times in every relationship when the parties involved need a break. What can we do to give you the distance you need, without hurting the family?”

…

I simply had come to understand that I was not at the root of my husband’s problem. He was. If he could turn his problem into a marital fight, he could make it about us. I needed to get out of the way so that wouldn’t happen.

Privately, I decided to give him time. Six months.

I had good days, and I had bad days. On the good days, I took the high road. I ignored his lashing out, his merciless jabs. On bad days, I would fester in the August sun while the kids ran through sprinklers, raging at him in my mind. But I never wavered. Although it may sound ridiculous to say “Don’t take it personally” when your husband tells you he no longer loves you, sometimes that’s exactly what you have to do.

Instead of issuing ultimatums, yelling, crying or begging, I presented him with options. I created a summer of fun for our family and welcomed him to share in it, or not — it was up to him. If he chose not to come along, we would miss him, but we would be just fine, thank you very much. And we were.

And, yeah, you can bet I wanted to sit him down and persuade him to stay. To love me. To fight for what we’ve created. You can bet I wanted to.

But I didn’t.

I barbecued. Made lemonade. Set the table for four. Loved him from afar.

And one day, there he was, home from work early, mowing the lawn. A man doesn’t mow his lawn if he’s going to leave it. Not this man. Then he fixed a door that had been broken for eight years. He made a comment about our front porch needing paint. Our front porch. He mentioned needing wood for next winter. The future. Little by little, he started talking about the future.

Read the whole thing.

Buddhists will recognize the practice of detachment, students of classical philosophy an expression of the Stoic ideal, and theologically-literate Catholics the beginnings of disinterested love.

We cannot ultimately control what others do, or what they think of us. We are however responsible for those things which are within our power (like our own interior life, and the way we treat others). Unfortunately, particularly given society’s encouragement, it’s very easy to become fixated on the things outside our control, at the expense of the things which are, and at great cost to ourselves (and to others).

As the Stoic philosopher Epictetus wrote in his Enchiridon:

Some things are in our power, and others are not. In our power are opinion, pursuit of a thing, or turning away from it: in short, whatever are our own acts. Those things not in our power include the body, property, prestige, and influence: in short, those things which are not our own acts. Those things in our power are by nature free from restraint or hinderance, whereas those things not in our own power are weak, slavish, subject to the power of others. Remember that if you regard the things which are by nature slavish to be free, and the things which are in the power of others to be your own, you will be hindered, you will lament, you will be disturbed, you will blame both gods and men….

(After translation by George Long)

Of course, in spite of the Stoic ambition, suffering can never be wholly eliminated in this life. As The Buddha and The Princess Bride say, “life is suffering,” and relationships certainly are life. But a great deal of suffering in life is preventable, stemming from a failure to recognize what belongs to us and what belongs to others.

When we love others as extensions of ourselves, we are really loving an illusion, and invariably wound one another when the reality doesn’t conform. It is when we recognize the reality of others, including their status as independent moral agents like ourselves, that we become truly free to love them — and give them the freedom (which is not a guarantee, but a prerequisite) to love us back.

If you really love someone, let them go. But don’t give up on them.

I got a fairly lengthy response from reader JF Miller to my earlier post, Pearls Before Breakfast, which I thought I ought to share. His wasn’t the only response in this vein, but it was the longest and most thoughtful:

Of all the places to run this experiment, they may have chosen the worst. Not for the sound, I’ve been through L’Efaunt a couple of times and it has the wonderful “wet” acrostics that a violin deserves. But, the social setting was working against everything.

I grew up in a small town, and when I moved to the Bay Area for grad school, I was thrilled with the prospect of being able to get so many places without an hours drive in a car. I loved getting off of BART at Market street to hear the musicians, many, of who pay with their street performances the bills that their work with the ballet or the symphony does not cover.

After 4 years of commuting, I learned that Market Street with it’s tourists is the exception. There are three types of people found in public transit stations, Those trying to get somewhere, those operating the infrastructure, and Scammer. Mass transit is one of the only venues that people go to without the intention of giving their attention to anything in particular. We go to a museum to give our attention to the art, or a ball game to sport, or church to God. But on BART your attention is free to be impinged upon by anyone with a mind to try to take it. I very quickly learned to do like everyone else and hostly deny my attention to anyone not connected with my journey. It took only one or two awkward encounters to learn that even making eye-contact could mean spending the next 10 minutes justifying your right to the money in your wallet against any number of fake (or true) sob stories meant to play on guilt and social custom.

The people in the subway that day did not win a free concert from a violin virtuoso they had it thrust upon them while they were trying to get to work. More then 1000 people acknowledged that public transportation in order to preform its function in society must, of necessity, not tolerate distraction from its purpose. I would suggest that the experiment be repeated, this time during lunch hour in a mall or shopping center where they will find better and quite different results.