Just about three years ago, I created the
automatic rule-based time
tracker (arbtt), a tool that quietly runs in the background, records
your current windows and their titles, and allows you to later process
this data using, well, rules. By now, I have almost half a million
records, spanning 317 days of me working at the computer. Processing
this amount of data has become very memory-hungry: It takes 1G of RAM to
process my data. Other users, with a presumably higher sampling rate,
report even worse performance, which finally made me approach the problem again.
Naturally, one wonders why it is such a memory hog, after all it
takes just one run over the data to produce a report. The data itself is
a lazy list so the garbage collector should the be able to drop the
seen elements immediately.
But arbtt is able to print several reports in one run; there is even
an option (
--each-category) that creates a number of reports based on
the data itself. The code was structured that first a number of values
that are possibly used by several reports are first created one and then
re-used by the reports. And then there is the issue of the filters: The
user specifies a what predicates are interesting (e.g., those where he
was active) and some reports need to know not only which samples were
matched, but also distinguish the consecutive runs of selected samples.
Lots of reasons that made it hard to not use the list of of samples
several times, which causes it to be completely retained in memory. The
idea of completely rewriting everything in a much more imperative way
was not appealing. But luckily Haskell s good abstraction possibilities can help here.
What is the correct way to traverse a lazy list and calculate some information about it? It is a strict left fold, i.e. an algorithm that can be represented as arguments to
foldl' :: (s -> x -> s) -> s -> [x] -> s
For those who are new to folds: The first argument is a function that processes one element from the list, returning the new state of the processing. The second argument is the initial state. And
foldl' can apply such an algorithm to a list to return a final state.
So obviously I had to express my reports as left folds. To think clearer about it, I gave them a name. I also added a finishing step to the mix, which is handy:
data LeftFold x a = forall s. LeftFold
start :: s,
process :: s -> x -> s,
finish :: s -> a
A value of type
LeftFold x a is then an algorithm that traverses a list of
xes and returns something of type
a. The
forall s. means that the user of such a processor must not make any assumptions about the type of the state. I also have a function that runs such a list processor, simply by invoking
foldl' with the arguments stored in the
LeftFold constructor:
runLeftFold :: LeftFold x a -> [x] -> a
runLeftFold (LeftFold st1 p1 f1) xs = f1 (foldl' p1 st1 xs)
Now, as a Haskell programmer, I am searching for monads everywhere, and it really would have been nice if this were a monad, as they are very easy to compose. But unfortunately, they do not form a monad. If they did then I could decide after running one processor and looking at the result how I would want to process the list now, but this obviously contradicts with the desire to traverse the list only once.
But there is the monad s smaller ugly sibling, the applicative functor. One can still somewhat nicely compose them to form more complex algorithms, just with more restrictions. Here is my instance:
instance Functor (LeftFold x) where
fmap f (LeftFold st1 p1 f2) = LeftFold st1 p1 (f . f2)
instance Applicative (LeftFold x) where
pure x = LeftFold () const (const x)
LeftFold st1 p1 f1 <*> LeftFold st2 p2 f2 = LeftFold
start = st1 :!: st2,
process = \(s1 :!: s2) x -> p1 s1 x :!: p2 s2 x,
finish = \(s1 :!: s2) -> f1 s1 (f2 s2)
The
:!: operator is a
strict tuple constructor. This is important, as otherwise the fold would be come a lazy one, I would be building up huge numbers of thunks and performance would be very bad. For the same reason every list processor should make sure that its state does not build thunks once it is in weak head normal form.
Now I am at a abstraction level that I feel comfortable working in, by writing functions that combine the list processors in various ways. Probably the most important one for me is already present in the libraries (here with a specialized type):
sequenceA :: [LeftFold x a] -> LeftFold x [a]
This is the whole trick: Now I can, based on the user input, run any number and selection of reports in one single list traversal. I find it very elegant that under the hood , the strict tuples are nested at precisely the right depth depending on the length of the list.
As hinted at before, I do some interesting stuff that was previously represented as lists of lists of values. Expressing these as left folds was a bit tricky, but again, the complexity is contained in the combinators that I wrote (although it still gets confusing, check out
processIntervalReport in Stats.hs):
monoidFold :: Monoid m => LeftFold m m
mapElems :: LeftFold y a -> (x -> y) -> LeftFold x a
filterWith :: (x -> Bool) -> LeftFold (Bool :!: x) a -> LeftFold x a
onSelected :: LeftFold x a -> LeftFold (Bool :!: x) a
onJusts :: LeftFold x a -> LeftFold (Maybe x) a
onAll :: LeftFold x a -> LeftFold (Bool :!: x) a
runOnGroups :: (x -> x -> Bool) -> LeftFold x y -> LeftFold y z -> LeftFold x z
runOnIntervals :: LeftFold x y -> LeftFold y z -> LeftFold (Bool :!: x) z
lfLength :: LeftFold x Int
lfFirst :: LeftFold x (Maybe x)
lfLast :: LeftFold x (Maybe x)
toList :: LeftFold x [x]
concatFold :: LeftFold [x] [x]
As a result, the program now only requires 10MB and runs 18% faster.
If you wonder why, in the definition of
runLeftFold, I do not apply the finish function strictly: That is intentional; I am actually passing the result of a processor that calculates some often required data (e.g. total time recorded) as an argument to all the list processors. (Near the end of the main function in
stats-main.hs) This loop works fine as long as I am using these only in the
finish functions.
There is one downside to this approach: I cannot easily calculate stuff on demand
and share it between two reports. Previously, I could just bind this to a variable, pass it to all reports, only if at least one is interested it would be evaluated and if several are interested, the result would be shared. I do not have a good solution for this yet.
The code above is in the self-contained module
LeftFold.hs in the arbtt sources.
Several People have had this idea before, here is
one blog post by Max Rabkin.
Flattr this post
As you may know, when Phil Zimmermann published PGP, his goal was to counter
the wide spying possibilities the development of electronic communications
offered to the authorities, by promoting the general use of encryption so that
1. governments would not be able to restrict it afterwards and 2. it becomes
possible to encrypt messages for privacy without drawing suspicion.
Now, cryptography has made its way and is widely use, but mostly for
commercial website and only sparsely for mail. Indeed, contrary to signing,
encrypting a message requires that the recipient has a crypto key and is able
and willing to use it to decrypt your message.
To alleviate this problem, I thought that it would be useful to have a way,
when sending a message, to tell your recipients that you would like that they
encrypt their answers, because you are able and willing to get encrypted mail.
I think the most relevant way to do that would be by adding a dedicated header
field:
Automatically devising a build order that allows to bootstrap Debian, currently
fails (amongst other reasons) because of the lack of metadata information about
which build dependencies can potentially be dropped from source packages. If
that information was available, an algorithm could decide which build
dependencies to drop so that dependency cycles can be broken.
Finding droppable build dependencies of a source package is something only
humans can do. This is because it involves to manually analyze and test the
build system of a source package. Build systems are neither uniform nor do they
encode their dependencies in a way that can directly be mapped to Debian
packages. Therefor they are not machine readable.
One idea to solve the dilemma, is to find a Linux distribution that provides
the following:
Another bug-fix release of 
It appears that a 
I was working on writing tests for gnome-settings-daemon a week or so ago, and finally got blocked on being unable to set up upower/ConsoleKit/etc. the way I need them. Also, doing so needs root privileges, I don t want my test suite to actually suspend my machine, and using the real service is generally not suitable for test suites that are supposed to run during make check , in jhbuild, and the like these do not have the polkit privileges to do all that, and may not even have a system D-Bus running in the first place.
So I wrote a little 
How to get it
As St phane mentioned in the python3-lxc blog entry, the API hasn t yet been finalized and llxc itself is in an early state and many changes are planned, so it s definitely not meant for production use yet, but since we believe in release early, release often in the free software community, here goes
Currently, llxc.py itself is *very* Ubuntu specific and its only been tested on Ubuntu 12.04, but that will be fixed once more of its kinks have been ironed out. Some people are also working on getting python3-lxc on other distributions, which will help a lot.
The llxc.py script itself is hosted on Github: 
We've been thinking about getting a dog for ages,
but it's been difficult to work out the logistics when we've been
travelling so much. Well, today's the day!
Yesterday, 
So, let's start with an introduction:
To shortly describe the main 
The IPv6 patch set for 