The Fugue

In CS language theory we sometimes talk about fixed points. Everyone seems to have a bit of a hard time understanding what a fixed point is at first, and I thought of an interesting analogy just now that will make sense to sysadmins.

When you go to install foo, with apt-get install foo, apt will tell you all the dependencies it will install, and it will also tell you the recommendations and suggestions, then ask for your permission. You might decide to say no and repeat the command with one or more of the suggestions added. Then it will do the same, but now with the suggestions of the suggested packages as well. You might repeat a couple of times. Finally, you will be happy with the selection of packages you're going to install. You've found the fixed point.

Apt itself does the same thing when resolving dependencies. If you remember rpm-based distros before apt-alikes, you used to have to find the dependencies fixed point by yourself. We called this rpm hell for good reason.

So when you're finding a fixed point in math, you're doing a similar thing. You're repeatedly performing the operation until further operations don't change the answer. The fixed point of a function f(x) is x₀ such that f(x₀) = x₀.

Levi pointed me to a presentation on Clojure, "a dynamic programming language for the JVM". That's actually a pretty bland description. I'd describe it at least as a dynamic functional concurrency-oriented lispy language for the JVM. The presentation was interesting, though I wish I had been able to follow the ant colony demo (it's audio-only).

It awakened the oft-recurring "functional floundering" feeling. I've written a semester worth of scheme in a programming languages course. I've read the Erlang book and written a little Erlang code. I recently went through a graduate course in programming languages with emphasis on denotational semantics. I understand the lambda calculus, functional programming, etc. But I feel completely stymied whenever I think about actually programming in a functional language.

I'm not sure what the root is, but I'm sure it boils down to lack of practice. That undergraduate course aside, I haven't had any practice. And since that course was very handholding (too much in retrospect), I don't feel like I took any practical skill away from it. Yet I feel that in the future functional programming for concurrency will be important, even if I'm not convinced it will be essential.

So I don't have time right now to really rectify the situation, but that doesn't stop me from wondering—how does one learn practical functional programming? What problem sets do you work through to get the needed practice? I suppose the question can apply to learning any new language, but there is much paradigm carry-over between imperative languages (and probably between functional languages). Are there certain problems that will aid that paradigm shift? If you feel like you've developed functional chops, in any functional language, I'd like to hear in the comments how you got there, what you'd change in retrospect, and your advice for me and others like me.

If ever you find yourself wanting to do some network programming in C, C++, or any other language that uses the socket paradigm, you must be careful. You are only inches from the edge of the precipice of insanity.

Luckily, some guy who calls himself Beej wrote a fantastic guide to network programming. He takes you by the hand and leads you gently away from the precipice. His guide is fun and easy to grok, but doesn't water the topic down. It's a fine piece of writing.

Even if you're writing Ruby network code, for example, which streamlines much of the insanity (thanks to exceptions and some nice OO abstractions like TCPServer), the socket concepts you will gain from at least skimming this guide will be a huge help.

Today I presented a 1-hour seminar on Computer Music to a summer camp group here at New Mexico State University. We talked about what we can do with computers, demonstrated Ardour, Audacity, and GarageBand, and had a good listen to a few quality pieces. We even mentioned U2.

My presentation is available as a PDF, and it has links to all the interesting sites we mentioned. For those that weren't there, I'd like to point out especially Real World Remixed where you can download sample packs for some great music, including Peter Gabriel and Afro Celt Sound System songs, and remix them yourself with something like Ardour. Hours of fun!

The lowly state machine, aka finite automata, is a beautiful and useful thing, on paper. But when it comes time to code one up, things can get ugly. You see, any first-year CS student can code up a state machine in the naïve way—with a state variable and a big nested while/case/if mess. It's hard to read, it's tedious to code, and it's very easy to get yourself all wet if you're not careful. Then there's the state transition table where you put all the state transition information in a hardcoded table, or in a source file that you write a program to generate the static table from, or if you're really fancy you read the source file at runtime. These get uglier than ugly, real fast.

I've always known deep down that there must be a better way to write state machines, at least in languages with the necessary niceties. I've implemented a number of semielegant state machines, but never really felt I hit on the One True Pattern™. Speaking of patterns, the Gang of Four have a state pattern for overengineering state machines with the magic of object-oriented programming. It's definitely more OO than the traditional approach. Probably one of the better ways to do it in C++ or Java. But let me share with you what I figured out in Ruby this evening.

Disclaimer: I'm probably not the first to come up with something like this, but I didn't see anything in my feeble attempts at googling state machine implementations. Second disclaimer: this is an agile state machine pattern; it doesn't concern itself with being bulletproof, all-encompassing, or high performance. But it's dead simple, very little code which is very easy to read, very flexible, and elegant. You and I should be able to adapt it to our needs easily many times over.

Here's a sample state machine, and the code for implementing it (in the code I add arbitrary final states and a transition action for demonstration purposes):

  require 'dfa'

  d = DFA.new('A', ['A','C'])
  d.transition do |s,a|
    ss = case [s, a]
         when ['A', 0]: 'B'
         when ['A', 1]: 'C'
         when ['B', 0]: 'B'
         when ['B', 1]: 'C'
         when ['C', 0]: 'D'
         when ['C', 1]: 'C'
         when ['D', 0]: 'A'
         when ['D', 1]: 'C'
         else raise "Invalid transition (#{s}, #{a})"
         end
    print ss
    ss
  end

  ary = [0,0,0,1,1,1,0,1,1,1,0,0].map do |a|
    d.eat a
  end
  puts
  p ary

The file dfa.rb which contains the DFA class is straightforward too.

Notice how you're free to implement the transition function however you like, e.g. by parsing a config file or hardcoding a state transition table, or clumping things together in an intuitive or even metaprogramming way if you have a lot of similar transitions. Notice that you don't have to do formal dances like defining the set of states explicitly, but the underlying theory is sound. Notice how you can get the input any way you please, and feed it to the state machine one piece at a time. Nothing is holding you down, you are free! And yet none of these things is in the least bit harder than if you hadn't used it. It's helpful but transparent. It is cuter than your cat and more loyal than your dog. Ok, I'll stop now.

The basic pattern is, in case you haven't been reading the code and documentation (ahem), abstract away the state-tracking stuff into the DFA object; provide the transition function which aligns nicely with theory (d: S x ∑ → S), and we'll look the other way if you sneak some transitional actions in there; and provide the input loop. All you really need in your pet language is first-class functions. Duck typing would (as always) be nice too, because then your states can be meaningful objects, eliminating an extra layer of indirection. It might not turn out as pretty in your language, but it would be as flexible and DRY.

Extending this to nondeterministic finite state automata wouldn't be hard, either, if that's what you need.

If you have a better way to do state machines (or a pretty-good way in $your_favorite_crippled_language), do tell in the comments.

My GAANN fellowship will be sending me to New Orleans in November for the International Computer Music Conference (ICMC). I'm pretty psyched about this. I've never been to an academic conference, and I've certainly never been to a conference about Computer Music. It's going to be a blast, and it's going to be very informative. Hopefully I'll be able to network with some people in the field working on research similar to my own (which will begin in earnest in January, since my coursework is (almost) done after this semester). There will be Computer Music conferences, and I'll be sure to catch some good old New Orleans Jazz too.

I haven't asked yet, but I'm hoping GAANN will send me to the Linux Audio Conference in Berlin next year, too.

Ever since I discovered ruby I've loved dynamic typing. I never paid much heed to people who got their knickers in a knot over how dynamic typing is "unsafe".

While working on Ardour this summer, I've literally been wrestling with C++, all because it is statically typed. The code I've been writing over the past month could have been done in one week with half my brain tied behind my back (which is the usual situation, by the way), if only C++ were dynamically typed.

In other ways static typing hasn't exactly got in my way, it just causes me to jump through hoops that seem silly, unnecessary, and inelegant. A simple concrete example will help. I'm doing undo serialization, and of course Ardour already serializes other things in order to save sessions. In C++ this means lots and lots of otherwise unrelated things all inherit from a common serializable base class. This is why multiple inheritance is necessary in C++. In Java you can use interfaces, which is better than multiple inheritance but not by much. In dynamic languages, you don't even have to give it a second thought. You just make sure everything that needs to be serialized responds to a serialize method, et voilá!

So as I've been wrestling I've had this nagging feeling that it's *me* that's broken, not C++. Have I become so spoiled by dynamic languages that I can't program efficiently in a static language anymore? Are the static people right and one day my whole world will come crashing in and all my ducks will keel over? Feelings of self doubt are part of being human, and these were some of mine this summer. Then I read a blog post by Bruce Eckel on Strong Typing vs. Strong Testing and my mind was put at ease. The thrust is, dynamic typing is good, and testing is necessary. I think this quote about Robert Martin (a C++ guru) sums things up nicely:

Robert came to more or less the same conclusion I have, but he did so by becoming "test infected" first, then realizing that the compiler was just one (incomplete) form of testing, then understanding that a weakly-typed language could be much more productive but create programs that are just as robust as those written in strongly-typed languages, by providing adequate testing.

I have a thought along these lines. Let's say you've got duck typing in full swing as in his examples. Now in the real world it sometimes happens that you choose a common ambiguous word for the duck method, like "run" perhaps, but more often than not you have methods that are named fairly specifically, like "speak" or "jump". The static argument is that you might accidentally call the method on something that won't do what you anticipate because it's not of the right type. But really now, how many of your objects that implement "jump" are going to be the wrong kind of objects in your application? Often the answer is none. So you jump through hoops for no reason.

Do read the article, it's fun and well-written. Even if you come out still clinging to your beliefs that static typing is Good and Wholesome, at least you'll see that us dynamic people aren't necessarily lazy, stupid heathens.

This monster keeps popping up and my rant switch has been flipped.

Google Research Blog has a post about how "nearly all binary searches and mergesorts are broken" because this can overflow:

int mid = (low + high) / 2;

Boy, have I got news for you. Computers are finite. If you put big enough numbers in, you will have overflow problems, period. Binary search and mergesort are no more broken than a+b or x*y or any other arithmetic operation in every program you have ever written.

All we have here is the need to recognize the limits of your computation. If you need to support big numbers, you can then deal with overflow. That might mean using 64-bit integers, or if you have just a little bit of overflow you can use some creative arithmetic and/or casting. The fun is endless, take it from a DSP programmer (overflow is an omnipresent concern in DSP programming).

So no, everybody's binary search and merge sort implementations are not broken. The algorithm is certainly not broken; theoretical discussion on algorithms is purposefully distanced from implementation concerns like how many bits you're working with, unless that happens to be the theoretical focus. So the textbooks and pseudocode are also not broken. The only thing that's broken is that some of us have forgotten that computers have limits, and we're surprised when all of a sudden the computer does what it was designed to do when the limits are reached.

It's official! I am one of the recipients of Google's Summer of Code grant. That means I get paid $4500 to improve Ardour according to my proposal over the summer. Combined with the GAANN fellowship I've received this means I can spend most of the time this summer writing code for Ardour and studying for quals.

My proposal was to modify Ardour so that plugins can be applied to regions instead of just tracks, both for realtime processing and bounced to disk. This is a feature I have sorely missed in Ardour, as it is an important tool for making electronic music and musique concrete efficiently. The other half is to add undo/redo serialization of the current undo system to allow unlimited undo across program instances.

I'm really excited for this opportunity. It will be my first serious involvement with a big and important open source project as a developer. I've often told myself I needed to get involved with one, and now I have an ideal opportunity to do just that.

There are two other SoC recipients for Ardour. One is adding basic MIDI recording and playback, and the other is doing a Windows port.

Ladies and Gentlemen, I bring you ruby/audio 0.1.1. This is primarily a bugfix release, but you fill find a few documentation and feature enhancements as well. Enjoy!