Code Runner – a Dbus service to execute code

Code Runner is an idea that spawned off from another open-source project codechecker that I am part of. In the codechecker project, we have a command line utility called setuid_helper, that runs a user’s submission program in a restricted environment. The program is restricted accesses to resources like CPU time, memory, number of files it can open, number of bytes it can write onto the filesystem etc. On top of this the program can be run as a unprivileged user. The setuid_helper utility also provides that option of running the user’s program in a chroot’ed environment. If you think about it, all malicious submissions can be ‘safely handled’ using the setuid_helper program. The Code Runner project provides a Dbus service that wraps the functionality of the setuid_helper. The advantages of the Dbus service is that, almost all high level programming languages have Dbus bindings and this service becomes immediately accessible to all those developers. It also abstracts away the details of setuid_helper. Currently, the Code Runner project is available here. The gitorious repo has a README that helps in getting started. Depending on the no. of consumers for the Dbus service, I would spend time on writing an installer for the same. If you find this idea cool, feel free to drop a comment

Inversions problem – haskell way

Given an array of numbers A, we need to find the number of distinct pairs such that,
i < j,  A[i] > A[j]
The naive algorithm would be to make ‘n’ choose 2 comparisons and determine the number of inversions in them. This has a worst case complexity of O(n^2).
We can do better than that by modifying merge sort algorithm, which has a worst case complexity of O(nlogn). That takes care of introduction to the problem and the solution.
I learned haskell but never really used it. It was fading away like high school math did. This problem provided the opportunity to dust some manuals and read some bookmarked sites on programming in haskell. The fun I get out of writing small programs in haskell is that, it allows me to think of a problem without knowing how a computer works. All imperative programming languages need you to understand that you manipulate system’s memory to get the desired result.
The following is an implementation of the solution in haskell:
‘imerge’ takes two sorted lists and returns a tuple containing number of inversions present in the merged list and the merged list.

‘imsort’ takes a list and it’s length and returns a tuple containing number of inversions present in the initial list and the sorted list.

imerge :: (Ord a) => [a] -> [a] -> (Int, [a])
imerge [] bs = (0, bs)
imerge as [] = (0, as)
imerge (a:as) (b:bs)
	| a == b = (fst (imerge as bs), a:b:snd (imerge as bs))
	| a < b = (fst (imerge as (b:bs)), a:snd (imerge as (b:bs)))
	| otherwise = (length (a:as) + (fst (imerge (a:as) bs)), b:snd (imerge (a:as) bs))

imsort :: (Ord a) => [a] -> Int -> (Int, [a])
imsort [a] 1 = (0, [a])
imsort a n = ((fst algo) + (fst (imsort (drop r a) (n-r))) + (fst (imsort (take r a) r)), snd algo )
	where r = n `div` 2
              algo = imerge (snd (imsort (take r a) r)) (snd (imsort (drop r a) (n-r)))

sort :: (Ord a) => [a] -> [a]
sort a = snd (imsort a (length a))

inversions :: (Ord a) => [a] -> Int
inversions a = fst (imsort a (length a))

I hope to see some haskell experts come by and comment on the code.