Higher order stuff

It has been over a month since my last post. And as I will be on vacation in a few days which will probably take me off line for a while I thought I should send some sort of ping before disappearing to Provence.

We had been busy finishing our paper on WMAP multipole vectors and soon after got busy with Wolfgang, my office mate, thinking about entanglement entropy. The latter project is not yet in a stage to be discussed in detail but I think this potentiallly quite interesting.

Instead, today I would like to mention a book that I have been reading recently: It's "Higher Order Perl" by Mark Jason Dominus. This is the most interesting computer book I have read for years. It has the potential to change my thinking about programming as much as the first time I learned about Perl.

If you have formal trainig in computer science and talk Lisp each day, this is will not be too interesting to you. But if you like me learned programming the street style there are a few things to note.

When I have to explain why I like Perl so much I could say it's because you can write nice short effective programs and it's very easy to communicate to the compiler what you want. Plus you have regular expressions and don't have to worry about memory management and garbage collection. But usually, I explain how much I liked the idea (of course like all not unique to Perl) that if you have a collection of several things integers are natural labels in very few cases, thus an array is rarely what you really want. It's a bit lik e coordinates. One option is to call things by their name which gives you a hash ($lastname{Robert} is much more natural than $lastname[1]).

The other case is that you don't care that some element is the 4711th as long as you get all of them either at once or you get one after the other (and can iterate over those like in a foreach $element(@list) construct). This gives you lists. If you have a list, you can take the first element and the rest and you can add elements to the beginning and the end. No need to worry how many elements there are as long as there are more than zero.

The "higher order" in the title of the book refers to the possiblility to have functions that return functions (or rather references to functions. So what?, I hear you think. Well, for the mathematically inclined: This allows you to go to the dual space of your data! Instead of manipulating the data, you can now manipulate the ways to access the data. And you should know that the dual space can in general be of very different size. Think of your examples in functional analysis or about distributions: There you first restrict yourself to very nice functions, the "test functions" and then look at their dual space which gives you distributions, quite powerful objects that are more general than functions.

Now back to the programming examples: Think again of a list. I mentioned, the only thing you needed to do with lists is take them as a whole or access the next element. But this is really enough! It is enough to pretend you know the list if you know a way to always get hold of the next element.

For example, with this you can come up the the universal doubling function. It takes a list and returns a list that has each element doubled. But in fact, all you do is to answer the question for the next element by going to the original list, taking the next element from that, double it and return it. Or you can interlace two lists or concatenate them by using obvious strategies to return the next element of the resulting lists.

This way, you can of course handle infinite lists that don't fit into your memory like the list of all integers. This is where really the power of the dual space notion comes in. All you return is a function that computes the next element. From this you can obtain the list of even numbers by applying the doubling function or the list of primes by discarding integers that are not prime.

Isn't that neat? Go get this book and read it!