Fractal Friday: Another Fractal Pizza

Here’s a pizza modeled after a variant of the Koch snowflake, and it’s perhaps a bit more aesthetically appealing than the previously posted pie.  Sadly, an examination of the pepperoni distribution (not to mention the ever-so-cute tiny pepperoni themselves) will reveal that this is a ‘Shop job, so it seems that the three-recursion/edibility barrier has not yet been broken.  Even were it to be real, you’ll notice that the fourth and fifth levels are incomplete, so we’d have to count it out in any case. [Edit: miscounted due to tiny WordPress editing window; there are four legitimate (if PhotoShopped) fully complete levels.)

(Via proofmathisbeautiful.)

Linux and Sundry

An Emacs Bisection

cricket on a screenA problem has been following me around for a couple of years.  Emacs, in which I have been spending more than a small portion of my time, has had a problem that would manifest in any non-X mode.  It persisted across multiple terminals: putty on Windows back to a Linux box, emacs -nw in a GNOME Terminal , even a bog-standard Linux console.  Specifically, hitting ‘Page Up’ and would result in the string ‘5~‘ being printed and ‘Page Down’ would result in '6~‘.  Not deadly, but just enough to throw me off my stride when moving around files.  I’d never gotten around to sorting in out, since it worked just fine when running as an X server.

This came up after the PLUG meeting last night, over pizza and beer at the Best House last night.  As Walt pointed out, there was almost certainly a very good reason for this, and it would be living somewhere in the years of messy accretions that comprise my .emacs file and its satellites.

I knew this was probably the case.  Like most .emacs files, mine was not planned.  It grew from bits and useful snippets, mode hooks, random configurations, pieces that crept in as distribution cruft, and pastings of now-unknown provenance.  The whole morass needs a good mucking out, but that’s not on the to-do list.  Perhaps, though, I could finally get the nagging problem resolved.

The first test was an obvious one: remove all the startup files and see if the problem went away.

Now, at some point I acquired a set of XEmacs startup files.  The reason for this is hazy…I haven’t used XEmacs in years.  Nonetheless, there it is: an .xemacs folder with an init.el and custom.el.  At some point, something broke when I tried to take my .emacs file and .emacs.d folder without bringing .xemacs along for the ride, so the path of least resistance was to let it follow me from machine to machine ever since.

After renaming all the startup files, the problem was indeed gone and I could happily page up and down.  From there on, the process is a mechanical one: add files back in until it fails, then comment everything out in the file and add chunks back in until the problem returns.  Once it does, you can be pretty sure you’ve isolated the problem.

Indeed, the problem was lurking in .xemacs/init.el, in the following pair of lines:

(global-set-key "e[" 'enlarge-window)
(global-set-key "e]" 'shrink-window)

It seems to me like a slightly odd manifestion, but there you have it.  With those lines removed, my Emacs bliss is unimpeded.

I really ought to get around to getting rid of that XEmacs cruft.

(CC-licensed image of a cricket from TaranRampersad‘s flickr photostream.)

Planet PLUG Programming

Extract n largest values from a Python dict

Having stashed a bunch of data in a python dict, one often needs a quick way to extract the n largest.  Inconveniently for the particular problem I was working on, the key value for the dict was an object and the associated value was a floating-point weight.  A quick-and-dirty method is to use insert all the dict-keys into a heap, using the dict-value as the heap-key Fortuitously, Python has both a heap module and convenient functions for using it in exactly this way.

import heapq

def dict_nlargest(d,n):
    return heapq.nlargest(n ,d, key = lambda k: d[k])

d = { 'a':10.0, 'b':2.0, 'c':5.0, 'd':3.0, 'e':15.0 }
print dict_nlargest(d,3)

Which neatly prints a list of the keys associated with the three largest values:

['e', 'a', 'c']

The heapq.nlargest() function can also use arbitrary object attributes as keys, as well, by supplying a one-argument function to the named parameter key. (This is the role of the lambda in the examples above and below.)

import heapq
class Toy:
    def __init__Toy(self, s, i, f):
        self.s = s
        self.i = i
        self.f = f

l = [ Toy('a', 10, 4.4), Toy('b', 4, 12.0),
      Toy('c', 2, 20.0), Toy('d', 1, 5.0) ]

# largest by the 'f' attribute
print heapq.nlargest(2, l, key = lambda o: o.f)

# largest by the 'i' attribute
print heapq.nlargest(2, l, key = lambda o: o.i)

This is fine for a one-off, but you’ll likely want to maintain this information in a data structure if this you’ll be performing this operation multiple times on a large collection.


Natural Selection for Self-Optimizing Haskell Code

I’ve been playing around with Haskell, Clojure, Scala and Mercury recently, and even though Clojure seems to be winning my heart, I’ve found much to admire about each language.  Haskell and Mercury, in particular, are nicely brain-twisty.

The recent release of a new backend for GHC that can generate code for LLVM is quite exciting.  Even more interesting is this blog post by Don Stewart (co-author of Real World Haskell) exploring genetic algorithms (via the Acovea toolkit) to select sets of LLVM compiler optimizations.  The process isn’t fast (Acovea chews on the options for four hours), but the improvements for even these preliminary explorations are striking.  This approach is worth watching; there is a lot of performance waiting to be squeezed out of modern processors, and it’s even better if we can design approaches that allows automatic optimization for each platform. (Don suggests that he’s working on a wrapper library to allow you to simply issue a main = evolve main' and let it go.)

Natural Computation Self-Organization

Computation with slime mold

Here’s some natural computation at the University of Oxford: using slime mold for efficient network planning.  They selected a somewhat interesting test for efficiency, comparing the patterns of slime-mold tubes to the design of the Tokyo subway system.

The researchers distributed oat flakes in a pattern similar to the locations of major cities and turned the Physarum polycephalum loose in, as it were, downtown Tokyo.  As the slime mold established its transport system, the resulting networks closely resembled design of the real-world human-engineered railways.

From their experiments, the researchers have developed a self-organizing mathematical model and simulation that I’d like to look at more closely.

The full text of the article “Rules for Biologically Inspired Adaptive Network Design” by  Tero, et al. is, alas, behind a paywall, as is too much current research, though Science (the journal where it was published) does have a popular take , as do Wired and BoingBoing.

Photo credit: Science/AAAS


Beautiful pictures of honeycomb formation

I am enchanted by these images of the process of honeycomb formation. An enterprising apiculturist put a glass bell over a hole in the top of a hive and took a series of photos as the bees extended their residence into the new atrium.

There’s been quite a bit of research on the self-organizing behaviors that result in these architectual patterns. For example, this paper by Belić, et al. describes how the workers build parallel combs hanging from the roof of an empty hive. It’s interesting to observe how the cylindrical chamber alters these dynamics, with the comb strands distributed relatively equally around the circumference.

Visit’s Curiosities for the full series.

Linux and Sundry

Eliminating a nasty, loud ‘crack’ before playback in Ubuntu Karmic

Ever since installing Karmic on my main box, audio has been an intermittent annoyance.  While I like the idea behind pulseaudio, its presence in Karmic has certainly has contributed to a few headaches (made painfully worse when I imprudently tried exploring the network multicast features).  I’ve had most of the bugs worked out for a while, except for one: before a sound is played back, a loud, unpleasant, sharp crack is emitted by the speakers.  After that, sound playback proceeds normally…music, further OS alert beeps, no problem.  However, after a period of idleness without any sound activity (ten seconds, in fact), the next speaker access will result in the same loud report.  Even though annoying, this problem has not been critical.

The box is custom-built system based around an Asus P6T motherboard, which has has an onboard RealTek ALC1200 for sound.  This shows up in Linux as

00:1b.0 Audio device: Intel Corporation 82801JI (ICH10 Family)
HD Audio Controller

and thus uses the snd_hda_intel kernel module (Intel High-Definition Audio).

Having just had occasion to look into my /etc/modprobe.d/alsa-base.conf, I found this exceedingly suspicious pair of lines:

# Power down HDA controllers after 10 idle seconds
options snd-hda-intel power_save=10 power_save_controller=N

The 10-second time-out surely could not be a coincidence.

Sure enough, commenting it out has removed this lingering audio annoyance (which turns out to be completely unrelated to pulse).  It appears this issue is already known:  As one commenter observed: “I was also affected by this. I think this is a bug – speakers should not produce unpleasant sounds for [no] apparent reason.”  This is a sentiment with which I can only agree.

Linux and Sundry

Moonlight just works

On the way into Philadelphia today, my train was delayed. While the rain seemed rather pleasant as I walked to the station, the winds had been strong enough to disrupt service.  An earlier train had been disabled on the line, blocking the tracks. In all, it made for a thoroughly tedious experience, and not one to encourage me in my attempts to use public transit nor bolster my (non-existent) love for SEPTA.

Eventually, a “rescue train” came along to extract we poor passengers from our misery. The extraction was not timely, and rather than arriving forty-five minutes early for the lecture on a multi-robot planning, I arrived forty-five minutes late: just in time to miss the end.

You can imagine I was quite pleased, then, when a friend told me the video would be available online. Unfortunately, the link he sent me was for a lecture earlier in the month. Even more distressingly, the recording was only provided via Microsoft Silverlight. I simply do not understand why a computer science department that runs mostly on Linux keeps returning to suckle at a Windows-only, proprietary teat. Disgruntled, I made a note to check out Moonlight at some point.

Somewhat later, I ran an apt-cache search moonlight on my main research box (currently on Karmic), and sure enough, moonlight-plugin-mozilla looked plenty promising. A simple sudo aptitude install moonlight-plugin-mozilla, and it was on its way.

I returned to writing email. A few minutes later, I heard the sound of talking: a video was playing somewhere. Irritated, I tried to figure out if a video one of my open tabs had launched itself. I was somewhat gobsmacked when I found it was the lecture mentioned above: unless I somehow managed to restart Firefox in a memoryless stupor, it seems that the Moonlight plugin insinuated itself into a running Firefox 3.5.7 instance, loaded the player, and kicked off the playback without any intervention.  Impressively smooth and simple.

This may partially make up for my annoyance with Karmic’s compiz, which has an annoying habit of dying out from under X every day or two.

Complex Adapative Systems

Swarm Leadership

atari-400National Geographic has a brief article about some interesting research at the University of Sussex.  The authors of this paper (irritatingly, behind a paywall and my University doesn’t have a subscription) suggest that swarm behavior may be disproportionately influenced by its most weakest, hungriest, or otherwise most desperate individuals.

This does suggest some interesting approaches for controlling (or subverting!) self-organizing systems.  I’m reminded of a paper I read recently by Franco Zambonelli, “Self-Management and the Many Facets of “Non-Self“, which suggests controlling swarm-inspired computing systems by introducing a (relatively smaller) number of manager agents that, by their actions, guide the overall collective behavior.

Photo Credit: CC-licensed image of a grackle swarm by Adam Baker

Linux and Sundry

Why you should be using zsh RIGHT NOW!

Yesterday, I gave a presentation to the PLUG North chapter of the Philadelphia Linux Users Group, delving into some of the cooler features of the Z shell.  I slandered other shells outrageously, but, disappointingly, failed to start a religious war.

The entire presentation was given from the command line using GNU screen and tpp (a text-mode presentation program).

  • zsh-2009.pdf: A quick conversion of the presentation to PDF by way of LaTeX
  • zsh-2009.tpp: tpp source for the presentation
  • zsh-2009-demo.txt: Notes to myself containing possibly interesting examples to put zsh through its paces

I’ll be posting my .zshrc as well, once I get around to sanitizing it.

If you’re in the Philadelphia area and didn’t make it to the talk, you have another chance: I’ll be giving a newly-enhanced version in February at the newly-formed PLUG East chapter.  Check the PLUG meetings page for schedule and location information.