Vim users: subscribe to this blog

Regular Vim tips and tricks: http://dailyvim.blogspot.com/. It already saved me once as I had forgotten the very useful @@ sequence that repeats last used macro.

Nokia Ovi barely usable

What is going on with the world's largest mobile phone company? Their strategy is to become big on the net but, man, for me their Ovi is a huge disappointment.

OK, it works fine from my N82 but with Firefox 3 (Linux) some features don't work at all! Yesterday I was trying to define my mobile phone model for Ovi (which should be automatically determined since I had already created an account using my phone's web browser) and the UI just didn't work. I couldn't press "next". The button wasn't there. And another thing, the UI was _really_ slow - not far from unusable.

So I tried the newest Opera and this time the button appeared and I managed to set my mobile model for the system. Still, the system was painfully slow.

What was positive I managed to upload an image to the system from my phone which was my initial goal. And the sync feature worked.

Today I logged in to Ovi again from my desktop - maybe the slowness was just a temporary problem? Nah, it's still slow.

Considering Ovi, Nokia's web technology is insufficient. They should take example from Google on how to make web apps that are platform independent (in my experience, having experimented Google apps from several software and hardware platforms with no problems) and user friendly in easiness of use and responsiveness.

Vim cheatsheet wallpaper

I decided to put a beautiful vim cheatsheet in good use. Usually the right display is enough for my apps (irssi, shell, browser) and the left display is quite empty. So why not use this gorgerous cheatsheet as the wallpaper?

Basic's not the answer, write in C

This made me laugh, and so I must link it here.

A CPS question and answer

Continuation passing style is a hard concept. Recently one fellow pasted the following piece of Haskell code in IRC and asked for its meaning:

cfold’ f z [] = z
cfold’ f z (x:xs) = f x z (\y -> cfold’ f y xs)

cfold f z l = cfold’ (\x t g -> f x (g t)) z l

It is a fold implemented in continuation passing style. Let's see what we can say about the type of cfold'. The function cfold' takes a function f of three arguments. The first argument of f is of some type t, the second argument is of some type t1, and the third argument is another function. The other function takes one argument of type t1 and its return value is the same as cfold's, that is, t1. Finally the return type of f is t1 as well. The second argument z of cfold' is something of type t1. The third argument of cfold' is a list of ts that is pattern matched in the definitions of cfold'. Thus, the type signature of the whole function is cfold' :: (t -> t1 -> (t1 -> t1) -> t1) -> t1 -> [t] -> t1.

Next, what can we say about the definition of cfold'? When the third argument, that is a list, is an empty list, it returns what ever is the value of its second argument of type t1. If the list is non-empty, we return what is returned by calling f when it is given x -- the head of the list (of type t), then z of type t1, and a function from t1 to t1.

At this point we start calling the first argument of cfold', that is f, a continuation. In the second definition of cfold' the control is passed to a continuation f. The continuation is a recipe of what to do next. The continuation is given the head of the list and a base value for the fold. The trailing anonymous function from t1 to t1 allows the continuation to get the result of the fold for the tail of the list.

Now, given the fold implemented in CPS, how do we, for example, multiply the elements of a list together? The continuation must contain that logic. Our continuation was a function of type (t -> t1 -> (t1 -> t1) -> t1). The first argument was the head of the list, the second argument was the base value for the fold, and the third argument was the way to get result of the fold for the tail of the list. So the definition for the continuation must be something like this:

(\x t g -> (*) x (g t))

It says that given the head of the list, x, a base value for the fold, t, and the function g that yields the result of the fold for the tail of the list when it is given t, the result of the whole fold is the list head multiplied by the value of the fold for the list tail.

Now cfold' alone is not describing much. We define cfold that passes the continuation, that does the actual folding, to cfold'.

If we try cfold with the sum function, a base value of zero and a one element list containing the number one, the expression reduces as below:

cfold (+) 0 [1]
(\f z l -> cfold' (\x t g -> f x (g t)) z l) (+) 0 [1]
cfold' (\x t g -> (+) x (g t)) 0 [1]
(\f z (x:xs) -> f x z (\y -> cfold' f y xs)) (\x t g -> (+) x (g t)) 0 [1]
(\x t g -> (+) x (g t)) 1 0 (\y -> cfold' (\x t g -> (+) x (g t)) y [])
(+) 1 ((\y -> cfold' (\x t g -> (+) x (g t)) y []) 0)
(+) 1 0
1

So for a non-empty list, cfold' calls the continuation, that performs the folding, and for an empty list it returns the base value.

Hello, autojump

Now everybody go and install autojump! It has quickly proved itself by improving my directory browsing experience in the shell.

Description:

* I remember the software name was "auto..." something, and all my code is in ~/koodi.

Before:

$ cd ~/koodi/auto<tab> <enter>

Now:

$ j auto <enter>

Benchmarking llvm-gcc and gcc

I just compiled llvm-gcc (4.2.1 with LLVM 2.6svn) and did some benchmarking. Given a naive implementation of the Fibonacci sequence (fib.c):

#include <stdio.h>

unsigned long int fib(int n) {
   if (n < 3)
       return 1;    
   return fib(n-2) + fib(n-1);
} 

int main() {
   int i;
   for (i=1; i < 46; i++)
       printf("fib(%d) = %ld\n", i, fib(i));
   return 0;
}

Then we compile with -O3:

llvm-gcc -O3 fib.c -o fib-llvm-gcc
gcc -O3 fib.c -o fib-gcc

And the results:

time ./fib-llvm-gcc
real 0m3.053s
user 0m3.052s
sys 0m0.000s

time ./fib-gcc
real 0m11.176s
user 0m11.173s
sys 0m0.004s

That is something.

What comes to code size (both in x86 assembly), the faster is also the smaller:

wc fib-llvm-gcc.S
108 288 1900 fib-llvm-gcc.S

wc fib-gcc.S
291 738 4485 fib-gcc.S

Job Interview Failure

I have been fortunate enough in my career to avoid IT job interviews up to this point. It has been that I have been asked not the other way around. It is quite amusing that I have worked as an interviewer but never been interviewed myself. So yesterday I went to my first IT job interview to see what it is like to be on the other end of the table.

Now I'm going to write what are generally the three most important human features in hiring context.

The most important part of yourself to show in an interview is that you are exceptionally passionate about your subject. There are a lot of people who know how to design and write programs competently, but those with passion are the ones with the greatest chance to stand up and achieve something remarkable. Real passion is something very rare.

The second most important part of yourself is that you are specialized. The greatest companies do not seek people that are generally competent in every aspect, but the people who are the best in some aspect. Usually the passionate are also the most specialized.

The third most important part of yourself is to show that you are not a hoax, that you know what you are talking about. This is the easiest part to do. Everybody with the slightest sophistication can show this. With the passionate this is self-evident.

What comes to my first interview yesterday, I think I emerged as an enthusiast and not as a complete clown. But I made one terrible mistake. I drew myself as a generalist - not a specialist. I did not convince the interviewer, nor did I deserve it. Albeit knowing all this, I somehow managed to fail.

---

So I accepted the research trainee position in TKK.

A summer trainee offer from TKK

My search for a job seems to have paid off. TKK is offering a summer trainee position in a research group that develops computer aided verification and testing techniques. I have five days do decide whether or not I'm accepting the position there.

The position was my first choice from the positions offered by TKK, but I'm going to see whether one certain company would like to hire me within five days - if their hiring machinery is even efficient enough for it to be possible.

Nondeterminism in Haskell

In nondeterministic programming an expression may have more than one value. In SICP we are given the following logic puzzle with its Scheme solution:

"Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's. Where does everyone live?" (SICP, pp. 418)

A Haskell version of the (almost) same solution follows (Control.Monad and Data.List are needed):

type Name = String
type Floor = Int

adjacent :: Floor -> Floor -> Bool
adjacent a b = abs (a-b) == 1

distinct :: [Floor] -> Bool
distinct l = l == nub l

dinesman :: [[(Name,Floor)]]
dinesman = do
  baker <- [1..5]         
  cooper <- [1..5]         
  fletcher <- [1..5]
  miller <- [1..5]         
  smith <- [1..5]         
  guard (distinct [baker,cooper,fletcher,miller,smith])         
  guard (baker /= 5)         
  guard (cooper /= 1)         
  guard (not (fletcher == 1) || fletcher == 5))         
  guard (miller > cooper)
  guard (not (adjacent smith fletcher))
  guard (not (adjacent fletcher cooper))
  return [("Baker", baker),
          ("Cooper", cooper),
          ("Fletcher", fletcher),
          ("Miller", miller),
          ("Smith", smith)]

Nondeterminism allows us to omit writing the loops that try all possible execution paths. Nondeterministic computing can be imagined as if the computer simultaneously tried all the possible branches of a computation, where the computation branches every time there are multiple choices to proceed, and stops the branches that yield no result, and finally, returns all results from the succeeded branches.

Our nondeterministic process proceeds as follows. Initially we state that each person may live in any five possible floors. That makes 3125 different initial branches to take. The first restriction drops all branches where two or more persons would share the same room. That leaves 120 active branches. The next restriction drops all branches where Baker is living on the top floor. The next restriction drops all branches where Cooper is living on the first floor, etc. Finally what we have is one remaining branch that is the only solution to the problem.

To understand the code, let's take a look on Haskell's MonadPlus class. The class defines two operations:

class Monad m => MonadPlus m where
mzero :: m a
mplus :: m a -> m a -> m a

The operation mzero denotes failure while the operation mplus denotes choice or combination. Here are the semantics of the operations:

mzero >>= f = mzero
a `mplus` mzero = a
mzero `mplus` b = b
a `mplus` (b `mplus` c) = (a `mplus` b) `mplus` c

The first reads that if a failure is applied on some action, the result is still a failure. The second reads that if something other than a failure is added to a failure, the result is the non-failure thing. The third reads that if a failure is added to something other than a failure, the result is again the non-failure thing. The two previous definitions are thus analogous to logical OR. The last one reads that the mplus binary operation is associative.

It appears that lists are instances of MonadPlus, defined as below:

instance MonadPlus [] where
mzero = []
a `mplus` b = a ++ b

The previous means that with lists, the empty list represents a failure and appending represents combination.

Let's go back to the code. The guard operation which we use to make restrictions on branches is defined as follows:

guard :: MonadPlus m => Bool -> m ()
guard True = return ()
guard False = mzero

So guard is an operation that takes a boolean expression and returns a () value meaning "no information" if the boolean argument evaluates to true, and mzero if the boolean argument evaluates to false.

So when a single branch runs a guard operation in our code, at that point, we have some combination of the floor numbers for each person. If the predicate is true, the branch will continue normally. If the predicate is false, the guard yields a failure. From the definition of MonadPlus, we remember that a failure applied on anything yields a failure. It means that the first failing guard will fail the whole branch. Succeeding branches will return a list of name-floor pairs. The return value of the function is just a combination of the results of all succeeded branches.

Does it work?
>> dinesman
[[("Baker", 3), ("Cooper", 2), ("Fletcher", 4), ("Miller", 5), ("Smith", 1)]]