# Category Archives: Work

## Computer Science Stack Exchange Live!

cs.SE in nondescript beta style

Since my post in December, Computer Science Stack Exchange has gone through private beta and is now accessible for everybody. Head over to cs.stackexchange.com and take a look! We are waiting for your questions so do not hesitate to post anything you have always wanted to know in computer science1, be it theory, applied or even practical!

We also need more expertise: out off almost 190 questions sixteen have yet to receive a good answer. among those are one about equivalence of Büchi automata and linear μ-calculus and another about efficiently learning regular languages.

You might also want to check out our hottest questions, including why Quicksort is often considered the best sorting algorithm, encryption using NP-hard problems and connections between Gödel’s incompleteness theorem and the halting problem.

I am very excited about this site. One one hand, it gives me the opportunity to share my knowledge in computer science with a wide variety of people, and I like teaching. On the other hand, I get to learn a lot. Not only do people ask about things I know next to nothing about so I can learn from the answers, but there are also original concepts. My favorite is Patrick’s proposal of heap automata; I have spent several hours contemplating his question about their power and follow-up questions.

I hope to see you on cs.SE soon!

1. Mind the FAQ, though.

## Spread Out List Items With LaTeX beamer

Everybody tells you that presentation slides should contain only as few pieces of information as possible. If you need more than one word or picture you better have at most three to five items. If you try to do exactly that using beamer for $$\LaTeX$$, this is what you get:

Aesthetics aside, item placement is just bad. You would want the items to fill the available space somewhat. In normal documents, package enumitem allows you to control such things both globally and per environment. It seems to conflict with beamer, though. I headed over to tex.SE and got good answers; Werner suggests to add this to the preamble:

\usepackage{etoolbox}
\makeatletter
\patchcmd{\@listI}{\itemsep3\p@}{\itemsep3em}{}{}
\makeatother

With this, your beamer slides do way better:

Note that you can adjust spacing by changing number and unit in \itemsep3em.

## Computer Science StackExchange Upcoming

I have posted about Stackexchange before. Helpful folks on various sites have solved many a problem I have had since then. I have posted a bunch of answers which—hopefully—helped out others in return. To say the least, I am convinced of the StackExchange model and am continually amazed at its effectiveness.

The wealth of knowledge saved on the StackExchange network1 has become so extensive that if you google for programming or LaTeX related problem almost certainly a question on Stackoverflow or tex.SE comes up. If not, asking there is often faster than searching the webs and/or trying around. Especially on tex.SE you can expect great answers in a matter of hours.

Now an exciting thing has happened: A proposal for a computer science site has reached commitment phase! That means that a number of people have to vote for the site in order to move it to a beta phase after which it will be a full-fledged member of the network2. The new site is to complement Stackoverflow and its derivates on one and cstheory.SE on the other side, filling the massive gap in between. I am very excited about this; if the community on cs.SE can be only half as good as on some other sites we are about to create the best resource for computer science students, researchers and users the web has seen so far.

But we are not there yet! First we have to have enough people commit to using the new site, then we need a successful beta. If you want this to happen, head over to area51, commit and be part of the community from the start!

1. Licensed under Creative Commons, mind!

## On Planarity of Control Flow Graphs

For our master’s project, we include visualisation of control flow graphs of Java bytecode as a user interface feature. When discussing the feature, a question quickly became apparent: are control flow graphs (CFG) planar? If so, we expect drawing them to be relatively easy. If not, however, we can abandon hope for being able to always draw nice graphs.

Obviously, unconditional jumps can cause arbitrarily nasty CFGs; that is not surprising as GOTOs are generally to be considered harmful. We agreed, however, that we should rather consider basic blocks of actual Java rather than arbitrary bytecode, as it is Java code we want to talk about. Sadly, even if we disregard labelled break just to be save, Java CFGs are not planar in general. The examples we found suggest that this is true for most procedural and object oriented languages, too.

## Lazy Deserialization in Java

While coding away on our master’s project, my team and I faced a problem. In our setting, users provide Java byte code to a client application which instruments it and passes the resulting JAR archive to remote servers via RMI. The servers execute this code in separate processes and feed it inputs values fetched from the client, again via RMI. Now, this can be a problem as users may provide their own implementations for those input values. Both client and separately started processes have, of course, access to these implementations, but servers may not.

The solution intended by Sun back then is to set up a code repository servers can access and download the necessary code from. We considered this overkill given that the server does not even care about the value1: after RMI deserializes the input, we immediately serialize it again and pass it directly to its child process. Dynamically loading all classes from the archive at hand felt messy for the same reasons.

So we came up with this pattern which I call lazy deserialization:

import org.apache.commons.lang.SerializationUtils;

class Value<T extends Serializable> implements Serializable {
private final byte[] data;
private transient T value;

Value(T value) {
this.value = value;
this.data = SerializationUtils.serialize(value);
}

T get() {
if ( this.value == null ) {
this.value = (T)SerializationUtils.deserialize(this.data);
}

return this.value;
}
}

As long as servers does not access the wrapped value, everything is fine; as far as they are concerned, they are passing around dressed-up arrays of bytes. In our case, we added several primitive—and therefore trivially serializable—members of the wrapped value to this class in order to enable the server to be able to report back certain things.

I think this pattern can be of use in any situation that involves passing around serialized objects only some nodes are interested in. After all, you might want to avoid deserializing even if you have access to all necessary class files; after all, (de)serializing can take up quite some time you might want to see better spent.

1. Especially so as we have a many-to-many relation between clients and servers, that means many repositories and many loaded classes you do not need.