Beyond my expectations Fri Jul 14 10:09:55 CEST 2006

Whenever you are tempted to say something controversal, you can relativize your statement a bit like "Personally, I think that ...", "From my point of view.. ", or even better "It can be argued that...". You do that to prevent steering up dust. Well, for the following statements I won't need such things:

The Common Lisp Workshop was a huge success. Success in terms of people attending the workshop. Success in terms of people hacking Common Lisp. Success in terms of progress parts of the audience made despite the task I have choosen was way to big for a one hour workshop.

Actually I should say 3 1/2 hour workshop. I talked for twice the time I planned for and was surprised that both parties involved sustained this: First, that I am able to concentrate for such a long time on talking sense about non-trivial ideas, second that the audience appearently was able to listen to me.

I hope to repeat this workshop somewhere sometime (if you are interested just mail me), but as in this very moment in your personal time dimension there is no workshop happening (presumably because you are looking at a website), I put the course material online http://lisplab.at/workshop/.

The beauty of Haskell Fri Jun 23 09:16:52 CEST 2006

Lately, I was indoctrinated by the Common Lisp camp. A bigger surprise it is when such a guy starts bloging about the beauty of Haskell.

But still it's true. There are ideas that are expressible with such an elegance that's impossible for me to walk by not prising it. And most of them are about infinity. First of all, Haskell is a lazy language. Most of you know that this means expressions are only evaluted when really needed.

One special aspect of Haskell's affinity to infinity is that we are able to joggle with infinite lists. Don't be afraid my Lisp loving friend, the syntax sugar is worth it. So don't hasitate when I introduce to you the syntax sugar for the finite list of natural numbers ranging from 1 to n, [1 .. n], and the sugar for the infinite list of number starting from 1, [1 .. ].

But are we able to ever print such an expression? No, we are not. Because it would take infinite time to evaluate. But we can do something else.

Taking the first n elements and pretending that we will increase n ever more until it reaches infinity, gives us the original list. Of course, we won't held on to this promise, and content ourselfs with the approximation of the infinite list by a finite list of its first n elements. Printing such a finite list should be possible, but what does that mean for Haskell evaluation?

To understand, let's look at definition of take, the function that gives the first n elements of a finite or infinite list.

take n [] = []
take 0 xs = []
take n (x:xs) = x:take (n-1) xs

The base cases should be obvious: Taking n elements from an empty list must return an empty list. Taking 0 element from any list returns an empty list. The recursive case is trivial too. For any remaining n (that is n>0) construct a new list with x as head an the rest of the available elements as tail. The result: take returns the first n elements.

The syntax sugar: ':' is the cons operator, [] is any empty list and (x:xs) generates a cons when encountered in the right hand site of a function definition, or when encountered in a parameter position, (x:xs)causes the cons to be destructured into the variables x (head) and xs (tail).

Applying take to an infinite list obviously make it finite and hence computable in finite time. take 4 [1 .. ] prints the first four elements of the infinite list of natural numbers. But how does that work under the hood?

take 4 [1 .. ] = 
1 : take 3 [2 ..] =
1 : 2 : take 2 [3 ..] =
1 : 2 : 3 : take 1 [4 ..] =
1 : 2 : 3 : 4 : take 0 [5 ..] = 1:2:3:4: [] = [1,2,3,4]

The lazyness is achieved by poping single elements of the infinite list and adjusting the list boundaries respectively. Due to lazyness, the remaining part of the infinite list [5 ..] falls off unevaluated and we have successfully cutted out a computation that would have taken us infinitely long to compute. That's quite a good optimization ratio, isn't it?

But that's just the beginning. Haskell can be twisted even more by using recursive variable definitions. Function definitions that are recursive are nothing new to most of us, but how should we define stuff like that x = 2x - 1 ? This particular case has a solution, but what about stuff like x = 1/x? Should we assign 1 or -1 to x?

Haskell doesn't answer such questions, but thanks to the lazyness of evaluation variable definition can be made recursive too. This eases the implications of an assignment, as we are not forced to assign the variable an evaluation result.

A few prequisites are needed to understand the following examples. For the Lisp programmers, the map function has nothing new except the Haskell syntax. It's equivalent to mapcar. The list model is the same as in Lisp, the list [1,2,3] is syntax sugar for right-associative chaining of conses, (1:(2:(3:[])))

After the whole syntax blabla, here is the definition of map

map f [] = []
map f (x:xs) = f x : (map f xs)

Applying a function f to the empty list returns an empty list. Applying the function to a list will split its cons cell into the parameters x and xs, reading head and tail. The result is the construction of a mapped element as head of a new list, while the rest is the rest of the elements mapped with f. No surprise here for folks used to recursions.

Let's redefine our natural numbers using another nice feature of Haskell. The head biting tails.

succ n = n + 1
n = 0 : map succ n

As we have seen before map applies a function succ to all elements of a list. Here we have a rather strange definition of the natural numbers claiming that it contains 0 as its first element and the rest is given by a mapping of itself using a function that add one to its argument. But reading succ as the Peano's successor function gives sense to this definition. The function map successively consumes elements of n, but also produces elements. After 0 is consumed in the mapping process, map starts to effectively feed itself.

We can even do this in parallel. But before we need a two list version of map. Here it is,

map2 f [] ys = []
map2 f xs [] = []
map2 f (x:xs) (y:ys) = f x y : (map2 f xs ys)

In Haskell, the map2 function is called zipWith, but that is a rather strange name, so I won't use it.

Now more fun: Here we have a recursive definition of all factorial numbers. Please stare at it for a while.

factorials = 1 : map2 (*) [1 ..] factorials

It works by weaving the infinite list of natural numbers into the recursive infinite list of factorials, that start with 1 as it initial element.

take 10 factorials => 
[1,1,2,6,24,120,720,5040,40320,362880]

Joy.

Enough of recursive infinite list variable definition. We take a step back and show some applications of infinite lists. I would like to spare you with the details of list comprehensions, a particular syntax sugar element that resembles the set definition one occasionally sees in mathematical papers. But to accommodate for that, I need to introduce you the filter function. It filters all elements out of a list for which a predicate function returns False.

 
filter f [] = []
filter f (x:xs) = 
  case (f x) of 
   True  -> x : filter f xs
   False -> filter f xs

'Nough said.

primes = sieve [2 .. ] 
sieve (x:xs) = x : sieve (filter (\y -> y 'mod' x > 0) xs)

Sieve is a recursive filtering function for infinite lists. We presume that all numbers from 2 onwards are prime and filter them via the sieve function. Ah, I forgot, the term (\y -> y 'mod' x > 0) denotes a function for one argument, namely y. Haskell authors argue that the backslash reassembles the λ symbol best in ASCII, and hence they chosen it to stand for lambda. One might disagree, but this insight helps to read the expression as λy. y mod x > 0 and conclude that this is a predicate function that will return true for all y that ain't divisible by x.

The function starts by assuming that 2 is prime. It filters out all elements that are not relative prime to 2 and hands of that filtered list to the next iteration of sieve. Please notice that we are filtering an infinite list here before handing the result to a never ending recursion. Insight into this is only partially available by code staring.

take 10 primes =>
[2,3,5,7,11,13,17,19,23,29]

Insight or not, we can simply start using it. Let's assume the following definition gives us all factors of a number n.

factors n = filter (\m -> n 'mod' m == 0) [1 .. n]

We can turn the list of factors into the list of prime factors by intersecting this finite list with the infinite list of primes.

The problem with intersecting a list with an infinite list in generel is that it will never end, because we can never be lazy and assume that we have looked at enough elements of the infinite list to conclude that we filtered enough. But in this particular case, we have the advantage of knowing that the list of primes is sorted, and our factor list is sorted as well.

Here is our ordered intersect function that makes clever use of that fact.

oisect _ [] = []
oisect [] _ = []
oisect (x:xs) (y:ys) =
  if x == y 
    then x : oisect xs ys
    else 
      if x < y then oisect xs (y:ys)
               else oisect (x:xs) ys

We do something similar to merge sort here. There are three recursion cases: When the next two items are equal in both lists, we can safely add it to the new list. If not, let's assume that x<y. We can safely drop of the item of the first list because due to sorting it is guarranteed that the second list will never contain an item that is smaller than y, hence there is no item that can fulfill the equation x==y. Hence, x can't be part of the intersected list. The same argumentation apply when y<x as it is in the otherwise case.

Now, after all the work here is the reward:

primefactors n = oisect (factors n) primes

An elegant definition of prime numbers: the intersection of all factors of n with the infinite list of prime number. Joy.

Of course, this is all theory. I'm not sure whether it'd be a good idea to start writing a web browser in Haskell. I haven't seen such things so I can't judge. However, after all the elegance I have to conclude that Haskell definitely deserves to be looked at.

Common Lisp Workshop Tue Jun 13 19:40:25 CEST 2006

I will give a Common Lisp Workshop for novice Common Lisp programmers. Everyone in reasonable driving range of Vienna is invited to

MetaLab - http://metalab.at Sunday, 25th of June, 18:00-20:00.

Features: 45 minutes presentation of Common Lisp basics, break, 1 hour hack your own tic-tac-toe. For the later workshop part, it is necessary to bring your own laptop! Nothing else than an ssh client is required.

The workshop is intended for programmers with experience in other languages but no experience in Lisp. The event is free.

Welcome LiLA! Wed Jun 7 17:52:03 CEST 2006

Hamburg, April 2006. A few guys, a bar, and liters of cheap water. The right soil for male talk when no girls are listening. Right, it's all about Common Lisp.

I was attending ECLM06 and with me more Austrians than anticipated. After a quick hello, the idea was clear. We need to plan planning a strategy for the subversive infection of our fellow countrymen with the fruits of the theoretic work around the Lambda Calculus: Lisp!

After the regular phase of idleness, and occassional real life contact, I came up with the cute name LiLA, for Lisp Lovers Austria. But the name was found to be revealing on our true nature, and "Lovers" was substituted by the more neutral word "Lab" (thanks for the suggestion Patrik!). <Add more idleness here>, and right after that lisplab.at went online!

Our name, Lisp Lab, also fits neatly with a project we are associated with: metalab. metalab is an open center in the heart of Vienna, providing us with space and infrastructure for our meeting and events.

Talking of events, there will be Common Lisp Introduction workshop in metalab soon. I'm aiming to hold a two hour workshop consisting of 45 minutes talk, break and one hour hacking on your game-theorically perfect tic-tac-toe implementation. For the latter, we can also go for a more stupid computer player, otherwise playing and knowing the game will end in a draw is no fun.

Watch this site for a date/place announcement of the CL intro.