Inspired by my friend Tiago, I installed the classic Winamp skin in my MP3 player of choice, Audacious. I had forgotten how useable it is — better contrast and easier targets to click than all of the other skins shipped by default with Audacious.

A port of the Winamp skin is available at Gnome-Look.

For your copy’n'pasting pleasure, here’s how to dowload, unpack and install it from the command line:

wget http://gnome-look.org/CONTENT/content-files/64790-Winamp.tar.gz
tar zxvpf 64790-Winamp.tar.gz
mkdir -p ~/.local/share/audacious/Skins
mv Winamp ~/.local/share/audacious/Skins

For Audacious 2.x: In Audacious, choose View → Interface → Winamp Classic Interface. Open Preferences (Ctrl+P) and go to the Skinned Interface pane.

For Audacious 3.x: In Audacious, choose File → Settings… → “Appearance” tab. In “Interface Settings” choose “Winamp Classic Interface”.

There should be a “Winamp” entry in the list of skins now. Pick it and enjoy this true classic.

This post is aimed towards comp sci students who studied lambda calculus but never really “got” the Y Combinator, the best-known fixed point combinator. Lambda calculus does not feature recursion, but using fixed point combinators, we can easily produce recursive functions, making it able to describe all computable functions (in other words, equivalent to a universal Turing machine). Here’s our friend Y:

Y = λf· (λx· f (x x)) (λx· f (x x))

With it, you can write a non-recursive version of a function, apply Y to it, and you get the equivalent recursive functionality, even though lambda calculus does not provide recursive functions. It’s not hard to understand what it does, but the mystery for me was always how it does it.

In my experience, a major barrier to understanding it was having to deal with several unfamiliar things at the same time, each of which makes a different part of my brain uncomfortable: the semantics of lambda calculus, the syntax of lambda calculus, and the problem at hand.

So, to focus on the problem at hand, let’s get rid of the rest.

Semantics of lambda calculus: untyped lambda calculus amounts (roughly speaking) to a very simple functional language with lazy evaluation. All we have is functions, but through smart encodings we can represent numbers and booleans with nicely crafted chains of functions. To simplify things, then, let’s just assume we already have numbers, arithmetic, if/then/else. Next, let’s get rid of lazy evaluation and switch to early evaluation, which is what we’re used to use in typical imperative programming languages. To do this, we’ll have to use this variant of Y, which is called Z:

Z = λf· (λx· f (λy· x x y)) (λx· f (λy· x x y))

Yes, it is a bit longer (we added the blue bits), but believe me, it’s easier to understand, and once you get this, it’s just a matter of recalling lazy evaluation from those functional programming classes and applying the same logic to Y.

Next, the syntax: lambda calculus is made of terms, abstractions and applications, which in programming language parlance are just variables, function declarations and function calls. Therefore, we can simply rewrite it using some familiar notation and get rid of the weird syntax and precedence rules for now. I won’t even use a functional language: let’s take a restricted form of Lua, using only features provided by lambda calculus to make the syntax clearer:

Z = function(f)
       return (function(x)
                  return f(function (y)
                              return (x(x))(y)
                           end)
               end)(function(x)
                       return f(function (y)
                                   return (x(x))(y)
                                end)
                    end)
    end

All right, it’s not exactly readable. But we’ll get there. Assuming you’re comfortable with functions as first-class values that can be returned and passed as arguments, the weirdest thing here is that in the first return we have a function being declared and called “inline”, receiving as a parameter another function identical to itself. Let’s make this flow a bit clearer by using local variables, but strictly as “aliases”. In other words, it won’t run any different, so we don’t use any extra features that are not part of lambda calculus — note that the our use of local variables here will be equivalent to macro substitution:

Z = function(f)
       local f1 = function(x)
                     return f(function (y)
                                 return (x(x))(y)
                              end)
                  end
       local f2 = function(x)
                     return f(function (y)
                                 return (x(x))(y)
                              end)
                  end
       return f1(f2)
    end

Ok, so this is the function we want to understand. It still makes no sense, but we can see that Z calls one function (f1) passing to it an identical function (f2). These identical functions return the result of calling f (the thing we want to make recursive), but giving as its argument another function that uses something that calls itself (x(x)). A strong scent of self-reference in all this — no wonder, as we know the key to recursion is in there somewhere. But let’s stop trying to reverse-engineer it. Let’s build it instead.

First, let’s recall what this function is good for. What we’d like to have is recursive functions, like this one that calculates the factorial:

fact = function(n)
          if n == 0 then
             return 1
          else
             return n * fact(n-1)
          end
       end

But we can’t have this in lambda calculus. Actually, all of it is fine, except for the recursive call to fact(). We don’t have recursion yet.

The best we can do is to write a function that does one step of the recursion and leaves the next step to be done by someone else. Like this:

stepper = function(next_step, n)
             if n == 0 then
                return 1
             else
                return n * next_step(n-1)
             end
          end

However, I said we would only use features provided by lambda calculus, which means we don’t have multiple arguments. Fortunately, through currying, we can get the equivalent to multiple arguments. This is one aspect of lambda calculus which I won’t hide in Lua syntax because it will come handy in our understanding. We’ll need to make stepper like this:

stepper = function(next_step)
             return function(n)
                       if n == 0 then
                          return 1
                       else
                          return n * next_step(n-1)
                       end
                    end
          end

The difference is that now, instead of doing stepper(some_next_step, 5), we have to do stepper(some_next_step)(5).

What this stepper construction makes clear is that we now have a “factory” function that returns our would-be-recursive function, except it only runs one step and uses another function that knows how to run the next step. You can think that stepper(next_step) actually returns a “step”, which is then run by calling it with (5).

But we need a function to run the next step to pass to stepper. How to obtain it? We call the factory to get the next step. Yes, like stepper(stepper).

Indeed, note that if we run stepper(stepper(stepper(stepper(stepper(stepper())))))(5), we get the equivalent result as fact(5). (You can try it in the Lua interpreter!)

Of course, we don’t want to write it like that. The plan, therefore, is to get a function that combines all these calls. It’s time for the combinator:

combinator = function(stepper)
                -- ?
             end

This function is meant to return something to replace all these nested stepper()s, so we want it to return a function that accepts our input argument:

combinator = function(stepper)
                return function(arg)
                          -- ?
                       end
             end

And it needs to run stepper() on the argument, of course, so it computes our desired function. But what will we pass as the next step?

combinator = function(stepper)
                return function(arg)
                          return stepper( --[[ ? ]] )(arg)
                       end
             end

Well, if what we want to produce is stepper(stepper(stepper(stepper(... then maybe what we need is to pass it stepper() again?

combinator = function(stepper)
                return function(arg)
                          return stepper(stepper)(arg) -- no!
                       end
             end

This is wrong because it will only run stepper twice (and of course we know the combinator doesn’t look like this). Think of stepper(stepper) function as it runs. If we pass 5 as the argument we get stepper(stepper)(5). It will get 5 as n and stepper as the next_step argument. It will eventually call next_step(n-1), that is stepper(4). But stepper expects a function as the argument, and not a number. In fact, if we run this in the Lua interpreter we get a type error. (In untyped lambda calculus we have no notion of “type error”, of course: what we get is just a lambda expression that makes no sense for us.)

We need to give stepper a function, so looks like we’ll have to make one.

combinator = function(stepper)
                local some_function = function()
                                         -- ?
                                      end
                return function(arg)
                          return stepper(some_function)(arg)
                       end
             end

(Again, I’m using a local variable here strictly as a “macro substitution”, just to make things more readable.)

To find out what to put in some_function, let’s think of what it will be used for. It will be passed to stepper, and therefore be used as the next_step. Does it mean it needs to take the numeric argument, then?

combinator = function(stepper)
                local some_function = function(arg)
                                         -- ?
                                      end
                return function(arg)
                          return stepper(some_function)(arg)
                       end
             end

If we’re receiving a parameter, it’s fair to assume we’ll have to do something with it. What we want to do with our input arguments is to run steps on them, so let’s get a step with stepper and do it.

combinator = function(stepper)
                local some_function = function(arg)
                                         return stepper( --[[ ? ]] )(arg)
                                      end
                return function(arg)
                          return stepper(some_function)(arg)
                       end
             end

Oh-oh, we’re back to the problem of what to give stepper! Does this mean we got into a loop? Well, note that if we just kept on doing the same, we would get the equivalent to stepper(stepper(stepper(...))):

combinator = function(stepper)
                local and_yet_another_step = -- ... !!!
                local yet_another_step = function(arg)
                                            return stepper(and_yet_another_step)(arg)
                                         end
                local another_step = function(arg)
                                        return stepper(yet_another_step)(arg)
                                     end
                return function(arg)
                          return stepper(another_step)(arg)
                       end
             end

But no, it does not mean we’re stuck in a loop. It means we’re getting close.

What we missed is that when we considered what to pass to the first stepper, we simply said it had to be a function taking the numeric argument. But what we want is a function that returns the result of stepper’s computation, but also produces the function for the next step! What we need is another factory-style function like when we transformed fact into stepper. Instead of going down one step, we’ll make a factory function that generates another function that goes down one step. While we’re at it, and that’s a key point, we’ll remove from it the responsibility of figuring out how to descend to the next level. We’ll do it just like when we did when we got rid of the recursion — just assume you get what you need as a parameter:

combinator = function(stepper)
                local make_step = function(next_step)
                                     return function(arg)
                                               return stepper(next_step)(arg)
                                            end
                                  end
                return function(arg)
                          return stepper(make_step)(arg)
                       end
             end

With a function like make_step, we can produce as many steps as we want. If you are mathematically inclined, by now you may be thinking of induction: yes, have we just constructed a way of solving one step of our problem assuming we have the solution for the next. That’s the spirit.

So, are we there yet? Does this work?

Not yet. Remember when we tried to do stepper(stepper)? It didn’t work because stepper doesn’t want a factory as an argument. It wants an actual step (remember that in our example it will use it to get the factorial of n-1). In other words, we don’t want to pass it a factory like make_step. We want make_step to make us a step. So let’s call it!

combinator = function(stepper)
                local make_step = function(next_step)
                                     return function(arg)
                                               return stepper(next_step)(arg)
                                            end
                                  end
                return function(arg)
                          return stepper(make_step( --[[ ? ]] ))(arg)
                       end
             end

Ok, we’ll call it, but what will we give it? Let’s look at what the argument of make_step is used for.

Wait a second, it is used to make a step as well! So, do we just give it… itself?

combinator = function(stepper)
                local make_step = function(next_step)
                                     return function(arg)
                                               return stepper(next_step(next_step))(arg)
                                            end
                                  end
                return function(arg)
                          return stepper(make_step(make_step))(arg)
                       end
             end

Yes, we pass it to itself. And we do the same with next_step too, since we’re doing the exact same thing. You see, here is where everything comes together: to have recursion, we need to have self-reference; and in lambda calculus, while a lambda term cannot reference itself in an abstraction (function definition), we have that a lambda term, when bound to a variable, can be applied to itself. The function above is indeed a fixed point combinator.

You may be finding strange that make_step passes itself as a parameter, then calls itself passing itself as a parameter… is this an infinite loop? Not necessarily, because in between each step, we don’t run stepper(next_step(next_step)) right away. It is “packed” inside a function(arg)...end. (These are the extra lambdas that the Z combinator has compared to the Y combinator.)

Speaking of that, is this code the same as the straight Lua translation of the Z combinator I presented above? Let’s recap:

Z = function(f)
       return (function(x)
                  return f(function (y)
                              return (x(x))(y)
                           end)
               end)(function(x)
                       return f(function (y)
                                   return (x(x))(y)
                                end)
                    end)
    end

Doesn’t look much like it, does it? But let’s take a closer look at our combinator. Turns out that in that final return, instead of building that step function explicitly, we can simply call make_step and get the same results:

combinator = function(stepper)
                local make_step = function(next_step)
                                     return function(arg)
                                               return stepper(next_step(next_step))(arg)
                                            end
                                  end
                return make_step(make_step)
             end

(In compiler terms, it is as if the first iteration had been “unrolled” before.)

Remember when I said the local variables were just macro substitutions? If we expand the two instances of make_step, we get this:

combinator = function(stepper)
                return (function(next_step)
                           return function(arg)
                                     return stepper(next_step(next_step))(arg)
                                  end
                        end)(function(next_step)
                                return function(arg)
                                          return stepper(next_step(next_step))(arg)
                                       end
                             end)
             end

Now, the only difference is that stepper is being called inside function(arg)...end, while in the other one it’s being called outside. It works the same, because the purpose of function(arg)...end there is just to “hold” the expansion of arguments between each call of stepper. We need this because Lua does not use lazy evaluation. To make our function just like Z, we do this:

combinator = function(stepper)
                return (function(next_step)
                           return stepper(function(arg)
                                             return (next_step(next_step))(arg)
                                          end)
                        end)(function(next_step)
                                return stepper(function(arg)
                                                  return (next_step(next_step))(arg)
                                               end)
                             end)
             end

There we are! The exact same function, only with different variable names.

Finally, to test it:

local factorial_step = function(f)
                          return function (n)
                             if n == 0 then
                                return 1
                             else
                                return n * f(n - 1)
                             end
                          end
                       end
local factorial = combinator(factorial_step)

print(factorial(5)) -- we get 120, yet no function in our code ever calls itself

As we can see, there’s nothing magical about the Y combinator: it produces recursion by using the only form of self-reference provided by the lambda calculus, which is self-application of variables. To get the loop started, since there’s no way to bind the outermost abstraction (function) to a term (variable) so it can apply to (call) itself, it is simply written down twice.

I tried to explain this this as clearly I could (given the assumptions I made about prior knowledge about programming languages and basic lambda calculus). This was actually the flow of thought I followed when understanding the combinator. It clearly follows a “programmer” mindset, which may not be the best method for everyone, but I hope it may be useful for others as it was for me. Corrections, comments and suggestions are welcome.

Following @gbedin’s suggestion, I will try to post here links to cool talks I watch and often tell him about, so the links can remain on a more “permanent” place than Twitter.

In this talk, Joel Spolsky describes some practical aspects related to community-building that went into the design of StackOverflow.com.

These are some steps usually I follow to make myself comfortable when I have to work with Debian-based distributions. The exact commands were written for Ubuntu 10.10, and they assume you have powers to run “sudo”. Most of this should be possible as well if you don’t, but the order of things switch around a bit (eg, you’d have to install ZSH using Compile). Steps 1-4 describe a minimal set. The remaining steps relate to some of my preferences.

Step 1: Download the Rootless Installer

wget http://svn.gobolinux.org/tools/trunk/Scripts/bin/CreateRootlessEnvironment

Step 2: Run it

chmod +x CreateRootlessEnvironment
./CreateRootlessEnvironment

Answer “y” when asked to recompile binaries; answer “u” (use new) when asked about settings files. Answer “y” when asked about adding the Rootless launcher to your profile files (bash_profile, zshrc, and so on).

Step 3: Switch to ZSH

You may need to install zsh first in the host system:

sudo apt-get install zsh

Now you can switch:

chsh -s /bin/zsh
echo "prompt lode cyan" >> ~/.zshrc

It’s easiest to just log out and back in to make sure your environment variables are sane.

Step 4: Fix some settings

The current version of Scripts refers to outdated mirror URLs. Edit ~/Programs/Scripts/Settings/Scripts/GetAvailable.conf and replace all references to “kundor.org/gobo/” with “gobolinux.org/”:

sed -i 's,kundor.org/gobo,gobolinux.org/,g' ~/Programs/Scripts/Settings/Scripts/GetAvailable.conf

Step 5: Install Compile

InstallPackage Compile

Choose “sa” to skip all dependencies. Your host system already has everything that’s needed.

Step 6: Install Mtail

Mtail gives us nice colorized outputs for a number of scripts.

Compile mtail

Step 6: Install Dit

Dit is my text editor.

You may need to install Subversion, Autoconf and Lua first in the host system:

sudo apt-get install subversion autoconf liblua5.1-dev lua5.1

(It should be possible to install these packages and all its dependencies in your home using Compile, but if you can, it’s easier to simply install it in the host system.)

Now let’s build Dit. Since Debian packages use a nonstandard suffix for the Lua libraries, we need to pass an extra option during build.

Compile dit --configure-options --with-lua-suffix=5.1

Again, use “sa” to skip all dependencies it may ask for.

Yesterday I had my first experiences with Ubuntu Studio, a Linux distribution specialized in music and video production. For a long time I wanted to setup somewhat of a mini-home-studio environment, and I decided to give the Linux audio ecosystem a try once again. My previous attempts usually resulted in all sorts of trouble from compilation difficulties with beta software (ever tried Ardour back in 2001?) to driver problems (ever tried USB soundcards on Linux-PowerPC?). Evidently, I was not playing the odds to my favor, so this time I wanted to make things as straightforward as possible: I decided to pick a Linux distribution that’s dedicated to music production.

At first I considered 64Studio, a Debian derivative which used the best-known music distro, but it seems dormant, with the latest release being 2 years old. The other option was Ubuntu Studio, so that’s what I went with.

The distro

The release I’m using is Ubuntu Studio 10.10 (Maverick Meerkat). Installation went smoothly, as is expected these days, especially for an Ubuntu derivative. A negative point is that the laptop’s WiFi was not recognized — I need to look into that later. Apart from that, everything seems fine. The distro has a dark gray theme typical of audio apps. I made a full installation, installing software for 2D and 3D graphics, video and music. Clearly, the distro is biased towards music: there’s a great number of music apps and only a few in the other categories. I don’t mean this to be a full review of the distro; I’m sure you’ll find a few of those out there.

My gear

I installed the system to an HP laptop (dual-booting with my main distro, GoboLinux, of course). It has one of those HDA-Intel sound cards, which are pretty standard (can’t verify the exact models right now). So far, I tried it with two devices:

• Line6 PODxt - for audio recording
• Yamaha S90 ES - for MIDI

Audio with the PODxt

Experiences with the PODxt went well. It was recognized correctly and I had success recording and playing through it using Ardour. The Ardour setup screen had an option for using two devices, and for a while I thought I could record with the PODxt and listen through the laptop speakers driven by the HDA-Intel, but selecting this option and clicking “OK” froze the system entirely — by the way, this was the only way I managed to crash the system so far. I doubt anyone would want to use laptop speakers as monitors anyway, so I guess sticking to the headphones plugged into the PODxt makes more sense for now anyway. (That won’t cut it when I get to recording with other people in the room, but I’ll think of something.)

One cool thing was plugging Hydrogen, the drum machine software, to Ardour via JACK. After I properly configured Hydrogen to use JACK and enabled the “JACK transport” button, both apps would play and stop in sync when I used the Play and Stop buttons in Ardour. By creating a bus in Ardour and hooking Hydrogen to it I could even control the volume of the drums through Ardour (including automation). One thing I notice but didn’t look further, though, is that seeking the track (rewind, fastforward) doesn’t sync between apps, but I think I was doing something wrong — I need to look more into it.

For plugging devices and applications via JACK I used Patchage, which has a great interface. Took me a while to figure out that green slots are ALSA, blue slots are JACK and red slots are JACK-MIDI.

MIDI with the S90 ES

No success with the Yamaha yet, but it looks like it’s possible. After plugging the keyboard to the computer via USB (using the “USB To Host” connection), new MIDI devices were detected and a number of ALSA ins and outs (properly named as “Yamaha S90 ES”) showed up in Patchage. After learning the difference between JACK-MIDI and ALSA-MIDI I reconfigured JACK Control to use MIDI “raw” mode and restarted the JACK server (which often required a number of retries). Red ports for capture and playback showed up and I could plug them to MIDI apps, but there’s something missing still, as I can’t get notes recognized by the apps when I play the keyboard; perhaps some configuration in the keyboard. So far, I could only drive MIDI apps using the Virtual MIDI Keyboard application, clicking notes on the screen.

Conclusion

Ubuntu Studio solved half of my problem: compiling all this stuff. The other half of the problem is configuring everything. But I can already be productive with the setup I have at this point, which is great. MIDI would be nice to have and would open a number of other possibilities, especially after playing with the various virtual instrument apps available.

It’s nice to see how well Linux audio has progressed. Device plug-and-play is really here and apps respond accordingly. Configuration still has a number of variables and can often be complicated but that’s almost to be expected — the ethos of Linux is to give the user endless possibilities. That’s really the feeling I get by playing with all this great software… I still have hundreds of plugins to try out!