Theory and Practice

Irrational

2009-10-28T10:40:00.000+02:00

A cute math puzzle that I saw twice in the past week.

There are three parts. The first two are supposed to be very easy.

Are there two irrational numbers a and b such that a+b is rational?
Are there two irrational numbers a and b such that ab is rational?
Are there two irrational numbers a and b such that a^b is rational?

Sources: The Princeton Companion and Richard Lipton's blog, quoting a talk by Manny Blum.

Overflow

2009-10-22T12:25:00.001+03:00

How do you use StackOverflow and MathOverflow?

I sometimes find answers on StackOverflow while googling for technical problems. For example, yesterday I wanted to know what is a good way to center code typeset with the LaTeX package listings. I didn't find out, so I'm stuck with nesting four environments: figure, center, tabular, lstlisting. Instead, I found someone asking on StackOverflow how to top-align two listings that go on the same row of a tabular environment. There were a few overly complicated answers, so I added mine (\lstset{boxpos=t}). Notice that it's more of a coincidence that StackOverflow got involved—I never planned to answer a question there. In fact, whenever I feel like helping random people and I go to StackOverflow or MathOverflow and click on "Unanswered" I end up sad because I never know how to answer any question.

So, do you use these websites? If yes, then how do you interact with them?

PS: In other news, expect this blog to be quiet until next year. I'm suppose to write a dissertation. Wish me luck.

Reducible Flowgraphs 0

2009-10-16T17:57:00.007+03:00

A summary of some basic results on reducible flowgraphs. Feedback is welcome. In particular, the ‘easy’ and ‘obvious’ parts are notorious for hiding mistakes. So let me know if something doesn’t look as ‘easy’ as I claim. This post is also available in PDF form.

Preliminaries. A flowgraph is a digraph with an initial node 0 from which all other nodes are reachable. Typically nodes represent statements in some low-level language (like Java bytecode) and edges represent possible successors in an execution. There are various restricted classes of flowgraphs that have been studied and are important in practice. For example, if a flowgraph is a dag (has no cycles) then the program terminates for all inputs; if a flowgraph is a two-terminal series–parallel graph then it corresponds to programs written using only two simple composition operations: sequence (;) and choice ([]). The subject of this post, reducible flowgraphs, is a class of flowgraphs that correspond to programs that can be written without using goto — loops like while and for suffice.

Definition 1 A flowgraph is reducible when it does not have a strongly connected subgraph with two (or more) entries.

A graph is strongly connected when there is a path x ↝ y for all nodes x and y. Node x is an entry for a subgraph H when there is a path 0 ↝^p x such that p ∩ H = {x}. (By notation abuse, p and H stand for sets of nodes, including the endpoints for the path.)

There are at least three other equivalent definitions, as Theorem 1 shows. Those definitions use a few more graph-theoretic concepts. A node x dominates node y when all paths 0 ↝ y contain node x. An edge x → x (for some node x) is a cycle-edge. A depth first search (DFS) of a flowgraph partitions its edges into tree edges (making up a spanning tree known as a DFS tree), forward edges (pointing to a successor in the spanning tree), back edges (pointing to a predecessor in the spanning tree, plus cycle-edges), and cross edges (the others). Tree edges, forward edges, and cross edges form a dag known as a DFS dag.

Theorem 1 ([1, 2]) The following statements about a flowgraph are equivalent:

It is reducible.
Every back edge has its source dominated by its target, for all DFS trees.
It has a unique DFS dag.
It can be transformed into a single node by repeated application of the transformations T₁ and T₂:
- T₁: Remove a cycle-edge.
- T₂: Pick a non-initial node y that has only one incoming edge x → y and glue nodes x and y.

Proof. It is not hard to show (by taking the contrapositive) that (1) ⇒ (2) and (2) ⇒ (3) and (3) ⇒ (1) and (4) ⇒ (1). It remains to show that (4) is implied by one of the others, which I’ll do, again, by looking at the contrapositive.

(1) ⇒ (4): If T₁ and T₂ cannot reduce a graph to a single node then the graph must have a strongly connected subgraph with two entries. This task can be split in two: First, show that if T₁ and T₂ cannot be applied at all then there is a strongly connected subgraph with two entries; second, show that applications of T₁⁻¹ and T₂⁻¹ maintain the existence of a strongly connected subgraph with two entries.

First part: If T₁ and T₂ cannot be applied then each non-initial node has ≥ 2 (distinct) predecessors. The initial node must have ≥ 2 (distinct) successors, let’s call them 1,…,k. Let’s look at nodes x and y ranging over this set. Because node y must have a second incoming edge there has to be a path x ↝ y for some x. If we can find x ≠ y for all y then we are done, since at least two of 1,…,k must be in strongly connected subgraph. Otherwise, let’s examine some node y whose second incoming edge comes from a cycle y ↝ y. The other nodes in this cycle must themselves have some second incoming edge which might come from some node x ≠ y, and we are done as before. Otherwise, we apply recursively the same reasoning on the subflowgraph induced by the nodes of the cycle y ↝ y (with node y as the initial node).

Second part: Easy. (Some would say ‘exercise’.) ☐

The loop forest. Typically a programmer writes in a language with while, which gets desugared, and then various tools (like optimizers or program verifiers) must reconstruct the loop structure of the original program. You may wonder why not keep the while constructs around in the low-level language:

Fewer language constructs means other algorithms are easier.
If the programmer is abusing goto we still want to know what he meant.

An important property of reducible flowgraphs is that there is a natural definition for loops. Intuitively, we want loops to be strongly connected subgraphs and, in reducible flowgraphs, such subgraphs can be associated with their entry.

Definition 2 In a reducible flowgraph, the loop L_x associated with the node x is the unique maximal strongly connected subgraph for which node x is an entry.

Such a graph always exists because a strongly connected subgraph of a reducible flowgraph is dominated by its unique entry. In other words, Definition 2 says that the loop L_x is the set of nodes y that are dominated by node x and also have a path y ↝ x back to the entry. (The path 0 ↝ x that witnesses node x being an entry cannot contain any dominated node y ≠ x.)

Proposition 1 Loops are strongly connected.

Proposition 2 Two loops are either disjunct or one is included in the other.

Proof. If node x dominates node y and there exists a node z ∈ L_x ∩ L_y then L_x ∩ L_y = L_y. If there is no domination between node x and node y then there is no node dominated by both so L_x ∩ L_y = ∅. ☐

When we extend the definition of loops to non-reducible graphs we’ll make sure that Propositions 1 and 2 still hold. Thus, it always makes sense to talk about a loop forest (in which there is a path L_x ↝ L_y when L_x ⊇ L_y).

The structure of loops in reducible flowgraphs can be analyzed by looking at what back edges they contain. A cycle is a graph of the form 1 → 2 → ⋯ → k → 1. Every cycle (which is a subgraph) of a flowgraph must contain one back edge. In reducible flowgraphs a stronger statement holds.

Lemma 1 Every cycle in a reducible flowgraph contains exactly one back edge.

Proof. Suppose there is a cycle x′ → x ↝^p y′ → y ↝^q x′, which contains back edges x′ → x and y′ → y. By definition, the nodes of a cycle are distinct, but we allow paths p and q to be (not necessarily both) of length 0 so it is possible that x = y′ and it is possible that y = x′. Every path 0 ↝ x′ must contain node x according to statement (2) in Theorem 1. Since there are paths 0 ↝ y ↝^q x′, this implies that all paths 0 ↝ y must contain node x (because path q does not contain node x, since they are part of a cycle). In other words, node x dominates node y. Symmetrically, node y dominates node x. This is only possible if x=y, which is a contradiction. ☐

Figure 1: flowgraph examples

Because of Lemma 1, Hecht and Ullman [2] originally defined loops in reducible graphs by associating them to back edges: The loop L_{y → x} is the union of paths x ↝ y that do not use node x as an intermediate node, plus the back edge itself. This shows that there isn’t really only one natural way of defining loops in reducible flowgraphs. For the graph in Figure 1(left) the old definition gives loop L_{1 → 0}={0,1} nested in loop L_{2 → 0}={0,1,2}, while our definition only finds the loop L₀=L_{2 → 0} (plus the uninteresting L₁={1} and L₂={2}). The problem with the old definition, however, is that it does not imply Proposition 2 as can be seen in Figure 1(right).

Definition 2 is always more coarse grained than that of Hecht and Ullman [2].

Lemma 2 In a reducible flowgraph, we have L_x = ∪L_{y → x}, where the union ranges over back edges y → x.

def dfs_forward(x):
  assert status[x] == unseen
  status[x] = seen
  for y in succ[x]:
    if status[y] == unseen:
      dfs_forward(y)
    elif status[y] == seen:
      backpred[y] += [x]
  for y in backpred[x]:
    dfs_backward(y, x)
  status[x] = done

def dfs_backward(y, z):
  y = find(y)
  if inner[y] != -1 or y == z:
    return
  if status[y] != done:
    print ’NOT reducible!’
    exit(1)
  inner[y] = z
  union(y, z)
  for x in pred[y]:
    dfs_backward(x, z)

Figure 2: finding loops in reducible flowgraphs

Tarjan [4] described an algorithm for recognizing reducible flowgraphs. Ramalingam [3] presents a modified version that identifies the loop forest. (Tarjan [4] says that Ullman discovered independently the same algorithm, although he didn’t publish it. Ramalingam [3] doesn’t say that he presents a modified algorithm. Perhaps the modification is folklore?) The core of a Python implementation appears in Figure 2. After executing dfs_forward(0) we have x==inner[y] when L_x ⊃ L_y and there’s no other loop in between. In other words, the array inner contains the parent pointers of the loop forest. The array succ represents the flowgraph through adjacency lists; the array pred represents the reversed graph through adjacency lists. The functions union and find are the standard union-find with the added trick that find(x) is guaranteed to return the z in the last call union(y, z) that involved the set to which x now belongs. (Figuring out a nice way to implement this trick is not hard, but fun.)

Remark 1 The recursive implementation looks nice but it tends to crash the stack, especially in Python, which has a rather low default recursion limit (1000 on my computer).

It is hopefully not too hard to see why this algorithm works after all those lemmas and theorems.

More to come. I plan three more posts: (1) finding loops in graphs that are not reducible, (2) making graphs reducible, and (3) summary of advanced results.

References

[1]: Mattew S. Hecht and Jeffrey D. Ullman. Flow graph reducibility. 1972.
[2]: Mattew S. Hecht and Jeffrey D. Ullman. Characterizations of reducible flow graphs. 1974.
[3]: Ganesan Ramalingam. Identifying loops in almost linear time. 1999.
[4]: Robert Tarjan. Testing flow graph reducibility. 1974.

Thanks to Claudia Grigore for feedback.

Time, learning, teaching, markup

2009-10-15T15:10:00.005+03:00

A rant about blog-writing technology.

This term I am not teaching so that I can focus my energies on writing a thesis. Instead, I found other creative ways of wasting time. I have recently succumbed to peer-pressure and started using Facebook and Twitter. I am also writing blog posts.

I realized recently that my knowledge about reducible flowgraphs is shallow. Normally I’d go and read about them from a textbook or some old articles and perhaps even do a few exercises. This time I decided to apply an advice I heard often: “The best way to learn a subject is to teach it.” Since I don’t teach, the next best thing is to write a blog post about it. (That’s not entirely true: Even if I would teach a blog post would be a better option, because I’m usually either demonstrating and have little say on the content, or I’m in charge of a course on a subject like Unix programming — good luck with fitting graph theory in there.)

The obvious question is: Why is this post not about reducible flowgraphs and instead it rants about an inexistent post about reducible flowgraph? OK, perhaps phrased like that it isn’t quite ‘obvious’. Maybe this works better: Get to the point!

Well, I’m technology frustrated. The mechanics of writing and publishing should take an insignificant amount of time compared to the time it takes to produce the content. Alas, that’s not the case when you want to convey information using:

text
drawings
code (in a programming language)
(math) formulas

Let’s see what’s available. (La)TeX is very good for text and formulas. You just go and write your text. A new paragraph is achieved by 2 enter keys, marking up a block of text with italics takes 5 extra characters, inserting a link takes 9 extra characters. For formulas, it is superb: I can typeset a_b with 5 keys, including the 2 delimiters. (If you think I’m crazy to count keys, wait until I tell you how many you need in the xML family of languages.) For drawings (La)TeX is again very good if you use the TiKZ package. Describing pictures in that language is so cool that I often fantasize about using it to introduce kids to programming. For code, the LaTeX(-only) package listings does a decent job: You have to bracket the piece of code with the right environment (34 keys), but sometimes you need to configure it to get nice results.

However, there is a big problem with LaTeX: browsers don’t know how to render it. Browsers know how to render xML: HTML, XML with style-sheets, MathML, SVG, and so on. Unfortunately, writing in these languages is a nightmare because they were designed to be easily consumed and produced by programs, not by people. Of course, you may use an editor that hides the details, but there are two problems with that approach. First, I know of no good editor that handles all those four types of content. Second, switching between keyboard and mouse takes time and disrupts focus so wysiwyg editors are out of the question for me. The corollary to that is that what I want is a language that lets me type easily the content. After that is available, fancy editors can bring minor improvements.

But let me be more explicit about why using xML is horrible. For text it is fairly OK. A new paragraph is achieved by a minimum of 3 keys (or 7 keys if you want proper bracketing of tags) but you usually type the 2 extra enters anyway to have the paragraphs nicely layed out while editing. Marking up a block of text with italics takes 7 extra characters. Inserting a link takes 14 characters (5 more than for LaTeX, which is ironic considering that when people think HTML they think links). But it gets worse. The xML way to typeset a_b is to use MathML and it takes… 89 characters! (Plus, locally the file must have the extension xml so I’m not sure it will work on Blogger.) Call me crazy, but I’m not willing to trade 5 characters for 89 characters no matter how better structured and more explicit the latter is. For drawings there’s something called SVG, which is similarly verbose, although perhaps not quite as bad when compared to TiKZ (or metapost). For typesetting code the xML solution is actually quite good: You just put the code in the proper environment (31 keys) and then you let a script do its job. I never saw it fail (although the implementation is quite hackish).

There is of course the option of writing LaTeX and converting that to xML. There are a few tools around to do just that. The best, in my opinion, is HeVeA. It handles text perfectly. For TiKZ drawings you can add an environment (again, around 30 keys) and it will make PNGs out of those. Cool. For formulas it uses plain HTML (no MathML) so the result works on older browsers but looks uglier than it could on newer ones. (MathML support is experimental, and it doesn’t work on my files.) You also have the option of transforming selected formulas to images (just like you do with TiKZ pictures). This makes sense if the formulas are complicated, in which case the HTML-only rendering is likely to suck. For code, HeVeA has some built-in special handling of the listings package, which produces results that I find quite ugly. HeVeA is almost ideal, except it is hard to customize, even though it’s supposed to be easy. For example, I want to translate the lstlisting LaTeX environment into a pre block with a certain class and let the script I mentioned do the syntax highlight. Why? It looks better and it is backed by Google, meaning that it’s likely to be more up-to-date than the internals of HeVeA. (HeVea has one great developer, but he is still one.) This customization seems to require changing the OCaml code of HeVeA and that is not easy. I also want to change some uses of df and dd tags and some purple (yuck!) things it generates but, again, I need to spend some time to figure out how to do it: It’s not easy. Of course, one solution for code is to turn it into images: That would look OK (though no colors) but it precludes readers to do copy and paste.

Another LaTeX to HTML converter is latex2wp. It handles text OK. It handles formulas by exploiting Wordpress support, which makes it unusable on Blogger or other sites (unless you are willing to piss off Wordpress for using their resources to drive traffic to a competitor). This brings up another point about HeVeA: If you are a Wordpress user it makes sense to exploit their support for LaTeX. But, good luck with convincing HeVeA to translate $a_b$ into $latex a_b$ . Finally, if I remember correctly, latex2wp has no support for drawings or code.

HeVeA is a successor written by Luc Maranget of a convertor written by the Xavier Leroy. (And, if you don’t know who the latter is, then you are not a computer scientist.) Xavier remarked that an ideal solution for writing technical documentation would be to design a new language that is easily convertible to both LaTeX (to produce printable PDFs) and xML (for easy viewing in browsers), but practically most people writing technical stuff would prefer to use LaTeX and will be reluctant to learn a new language. That was before Wikipedia: Its markup language is convertible to both HTML and PDF (through LaTeX?). Alas, I think their tools are not publicly available. (If they are and are easy to use on Linux I want to know!) Supposing that the tools are available, there is a bigger problem: While text, code, and math are supported, drawings have to be written in the verbose SVG.

That was the motivation. Now comes the challenge.

Design a concise language for describing documents with text, drawings, code, and formulas. Make it feel familiar by having syntax similar to existing languages. Implement translations to LaTeX and xML. Make sure the implementation is very easy to customize. (Keep in mind the failings of HeVeA in this area.) The usage of the tool should be as easy as tool -tex docname.

Now, why didn’t I think of using that as a project when I was teaching?

PS: In case you wonder, I wrote this in LaTeX and used HeVeA.

Ambiguity in CLOPS

2009-09-29T01:31:00.001+03:00

A problem we hit while working on CLOPS. We know a good solution but it makes a nice puzzle.

Problem. A digraph has letters on edges, so there is a word corresponding to each walk. Given two nodes m and n, are there two distinct walks m ↝ n that have the same corresponding word?

Examples. We are looking at walks from blue to red.
In the graph

there are no two distinct walks with the same word.

If the graph

has the letter x on all edges then there are two distinct walks corresponding to the word xxxxxxxxxxxxxxxxx (length 17).

Comment. This problem amounts to finding whether a CLOPS input file, which is a regular grammar for what can go on the command line of a program, is ambiguous.

My most beautiful result

2009-09-27T16:23:00.002+03:00

Celebrity gossip and physics mix well

2009-09-27T14:15:00.001+03:00

A short review of Gina.

I have recently finished reading Gina says a (free) book by Gil Kalai. My opinion: not light bedtime reading! Indeed, I started reading at 11pm and finished around 3am... because I couldn't stop. But I was joking: It is fairly light reading. It is also quite depressing and should be hidden from high-school students trying to choose a career path. (Yes, I'm joking again: I don't really think hiding data is a good way of attracting kids to science.) On the other hand, I think it has great potential in popularizing some nice mathematical results.

If you like gossip about celebrities you will certainly love this book!

There is no segfault: sort of an answer

2009-09-27T13:13:00.001+03:00

[edit: updated link to dead cat]

My attempt at answering my own puzzle.

But first I should acknowledge that the title comes from the song There is no dead cat. Second, I should note that my presentation of what induction means is unnecessarily redundant: The base case is included in the induction step given that there is a smallest element. (And, yes, that’s my strange sense of humor.)

OK, now the challenge: Under which conditions can we conclude P(n) for all n∈ S given that ∧_{k≠ n} P(k) implies P(n) for all n∈ S?

Read literally the question is not interesting: “Under which conditions p implies q?” has the obvious and useless answer “q, since p ∧ q implies q.” So, why is this an interesting question? Because we reduce the former to the later whenever P(n) has the form “the piece of code n is OK,” for some value of OK, one example being “does not dereference a null pointer.” Another reason that makes the question interesting to me is that I feel we are justified in looking at code one function at a time to assess whether it “goes wrong” but I don’t know it, because I never read or gave a coherent explanation: The matter is always treated as “obvious” as far as I can tell. Also, I formulated the problem in more general terms so that the answer has a chance of being useful in a different setting than program verification. Finally, I vaguely remembered reading that modular reasoning about a system is a form of coinduction: After reading a little about coinduction I’m not so sure anymore. (I looked at slides introducing coinduction in Coq by Yves Bertot and at blogs like n-category and a neighborhood of infinity. Reading through this tutorial is slow.)

The intuitive reason why we can analyze program pieces one at a time is that any counterexample is an execution that has one place where null is dereferenced. A bit more precise: An execution is a sequence of states. A state is a pointer to the next program statement to be executed plus the content of the memory (that is, a map from variables to values). The wrong state is special. The assumption ∧_{k ≠ n} P(k) amounts to “ignore executions that go to the wrong state after executing a statement of a module k ≠ n.”

Problem. Can we use modular reasoning to put upper bounds (other than zero) on the number of errors that can occur in an execution? For example, is it possible even in principle to conclude that “this program may break its contract at most three times during its execution” without doing a global analysis? I suspect not.

Is there a useful way to generalize the answer with “executions”? Since I’ve been reading about model theory I’m inclined to view the program as a theory whose models are its executions. In this language the trick is that we can systematically explore parts of a model where a formula may not hold, assuming that in all other parts it does hold.

For the record, I’m not satisfied with my answer.

There is no segfault

2009-09-21T03:50:00.000+03:00

A short puzzle related to induction.

To prove that all elements of a set S have a property P we can use induction:

[induction step] we show that the elements of size s have the property P, assuming that all elements of size <s have it, and
[base case] we show that the smallest elements have the property P

For example, if S is the set of natural numbers and the size of a natural number is itself, then we can prove that 2Σ_k≤nk=n(n+1) by showing that:

[base case] 2Σ_k≤0k=0, and
[induction step] 2Σ_k<nk=n(n-1) ⇒ 2Σ_k≤nk=n(n+1)

As another example, if S is the set of (non-empty) binary trees in which each node either is a leaf or has exactly two children then we can show that the number of leafs is one more than the number of non-leafs by induction. In this case the size is the number of nodes in the tree. If we denote by l(t) the number of leafs in the tree t and by k(t) the number of non-leafs, then the statement we want to prove is l(t)-k(t)=1 for all trees t. Induction says that it suffices to show:

[base case] l(•)-k(•)=1, and
[induction step] (l(t₁)-k(t₁)=1 ∧ l(t₂)-k(t₂)=1) ⇒ l((t₁,•,t₂))-k((t₁,•,t₂))=1

You may want to take a moment to convince yourself (if you haven't already) that the base case and the induction step are fairly easy to check for both examples above.

But there is another type of induction! Suppose you have a program Q that is a set S of functions and you want to prove the following theorem: Program Q will not dereference a null pointer. One way to approach this task is to prove for each function that it will not dereference a null pointer ("throw NullPointerException" in Java, segfault in C, etc.) assuming that all the other functions in the program do not dereference a null pointer.

However, there is something troublesome about this. Until now we had an order: We think about the first proof by induction as first showing that an identity holds for n=0 then for n=1 then for n=2,... and whenever we get to proving for some value we rely on what was proven "before". But the last proof enjoys no such property: We can happily have a program made out of n functions, each calling all the n functions. Let's put it differently. Say we have four functions: a, b, c, and d. Is it possible for a, b, and c to be OK but d not? No, it isn't, because one of the proof obligations was to show that d is OK given that the others are. But... what's stopping c and d to be both not OK?

Still, I claim the proof is fine. Can you see why it works? What are the general conditions under which such proofs work?

A Good Companion

2009-09-14T16:08:00.001+03:00

A short "review" for the The Princeton Companion to Mathematics.

The Princeton Companion
to Mathematics

Sample Entry: Fermat's
Last Theorem

Podcast interview with
editor Timothy Gowers

Saturday I found a bookshop that I like. It has four floors: basement (bargains), ground (fiction), first (humanistic subjects), second (scientific subjects). This is contrast to the usual fiction and fiction bargains, plus some nude pictures counting as "art".

I stayed on the second floor for five minutes before deciding to buy The Companion. It is remarkable that it is expensive: 80 euro. It is also remarkable that within those five minutes two other people decided to buy it.

Compressed preface. The book leans towards examples rather than formalism. The core is a set of chapters on branches of mathematics that are being developed actively by today's researchers, such as, arithmetic geometry, numerical analysis, and theoretical computer science. Other parts worth mentioning are the concept index (useful for when you are too ashamed to admit you are completely lost in someone's argument) and the set of biographies of mathematicians. I'll let the other goodies surprise you.

My opinion after one hour. Contributors were chosen by expertise and expository skill so I was surprised to not see Knuth. I guess he's getting old and needs to finish his book. The typesetting uses Palatino fonts and is really well done. (Even the annoyingly small parentheses that Terence Tao uses have been fixed and now have the proper size. :p) OK, now let's get to less trivial things! The book is awesome! It's something I would have absolutely loved to have when I was in high-school and it's something that I will use as a bed-time reading for a while. It is very different in flavour from Knuth's books, though. It covers a lot of breadth and intuition but does not go into depth. That is intended, since in-depth study is fairly easy to carry on now that most scientific articles are available online. The big picture, however, can be acquired only by attending conferences, and few are lucky enough to be able to do it.

PS: It's a "review" and not a review because a proper review is done after you read the whole book. That won't happen any time soon.

Facebook Politics

2009-09-14T15:21:00.002+03:00

It's interesting how otherwise smart people get worked up by irrational arguments, usually involving politics or religion. A colleague of mine was flooding my Facebook recently with basically this argument:

Treaty T is bad because:

It is written by crooks in city F (F stands for "far away")

It gives more power to people in city F and takes it away from people in city C (C stands for "close by" or "capital", your choice). Voters know more about the people in city C.

Now, if you didn't spot yet why this is insanely illogic, let me help.

First, let us make clear the assumptions:

People in city F are crooks.
We (voters) don't know people in city F well enough for an informed vote but we do know people in city C well enough for an informed vote.

This begs the question:

How do you know some people are "crooks" if you don't know enough about them?

The assumptions are inconsistent. That should be enough to make any logician puke. But let's assume only one of them is false.

So, first we assume that people in city F are crooks. So what? It doesn't follow in any way that treaty T is bad. A treaty is good or bad depending on what it contains, not depending on who wrote it.

Now let's assume they may be crooks but we don't know for sure because we don't know enough about them. How is that an argument against the treaty T?? Since people get their information through television, radio, and Internet the distance is completely irrelevant. Of course, it may be that media (who pushes information onto the sheepish voters) makes a bad choice in selecting what is important. That may very well be, but that's an argument against the media, not against the treaty. If the media would suddenly decide to only talk about the private life of Paris Hilton, does that mean that we can't vote for anyone else because we don't know enough about them? No, it means that the media is fucked up.

To make it clear, I am not arguing for the treaty for the simple reason that I did not read it. Before I read it I do not feel competent enough to preach to others how they should vote. However, I would prefer to see a little less fanaticism and a little more reason in my "inbox".

PS: Since I spent enough time on this spamming issue, be advised I will not read any comment on this post. Feel free to comment if you need to vent.

carnival 56

2009-09-09T12:54:00.001+03:00

It seems the Carnival of Mathematics is trying to get back to life. Here's my modest help: a link.

Java is fast, they say on ##java

2009-08-19T16:24:00.002+03:00

Which class from the Java runtime environment you should use when you need a stack.

The package java.util contains a few classes suitable for pushing, poping, and peeking in stack style.

	push	pop	peek
Stack	`s.push(e)`	`s.pop()`	`s.peek()`
ArrayList	`s.add(e)`	`s.remove(s.size()-1)`	`s.get(s.size()-1)`
LinkedList	`s.addFirst(e)`	`s.removeFirst()`	`s.peekFirst()`
ArrayDeque	`s.addFirst(e)`	`s.removeFirst()`	`s.peekFirst()`

All but ArrayDeque implement the widely used and known interface List.

Let's see how efficient are the implementations in JRE6, in relative units.

	time	space
Stack	x2.09	x1.6
ArrayList	x1.15	x1.3
LinkedList	x1.27	x3.02
ArrayDeque	1	1

Yep, ArrayDeque is best both in terms of time and speed. If you need a subtype of List then go with ArrayList. If you want to eat memory like crazy for no good reason then try LinkedList. And if you have a thing for names like Vector (which Stack extends) then, well, go for it. Just don't say I told you to use it. Finally, if you are a speed junkie and you know in advance the maximum possible size of the stack, then you can implement your own for a x1.2 speed-up (compared to ArrayDeque).

Just for the record, a basic stack operation for ArrayDeque takes about 15ns on my old laptop.

Good bye, and stay tuned for the next useless microbenchmark results.

Type Inference in C++

2009-07-03T15:00:00.003+03:00

A short note to let you know about a long-missed C++ feature you can now use.

Since gcc 4.4 (21 April 2009) you can now skip giving the types of variables that you initialize. Do you remember the old macro

#define foreach(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)

? Well, you can now write

#define foreach(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)

In fact, since the definition is shorter now, you might even consider ditching the macro altogether. After all, macros cause bugs that take much time to track down.

Edit: Oh, yeah. I forgot to mention that auto will be a standard C++ feature, while typeof is a GNU extension.

Type Inference in Java, for Generics

2009-07-01T17:28:00.001+03:00

An unexpected failure of the Java compiler. Or is it a failure of the Java type system?

Java programmers write repetitive code like

HashMap<String, Integer> foo = new HashMap<String, Integer>();

all the time. Those who seek beauty in their code may choose to use the Google collections library and write instead

HashMap<String, Integer> foo = Maps.newHashMap();

Constructors and static methods interact in very different ways with generics. If you say new Foo() you instantiate a raw type, which is quite different from a what you get by saying new Foo<Bar>(). On the other hand, static methods are the beneficiaries of a little bit of type inference, as specified by sections 15.12.2.7 and 15.12.2.8 of the Java Language Specification (Third Edition). The actual rules are complicated (and I haven't read them yet) but the idea seems to be to use two sources of information:

the types of the actual arguments
if the result is "assignment convertible" to some type T then this type T is used too.

The reason why the Google collections library works is the second bullet: The compiler uses the type of foo to figure out how to instantiate the type arguments of Maps.newHashMap.

OK, that was the background. Now let's see some examples.

Would you expect the following code to compile?

interface A {
  static enum Foo { BAR; }
  static enum Bar { FOO; }
}

class B<T extends Enum<T>> {
  private B() {}
  public static <T extends Enum<T>> B<T> get() {
    return new B<T>();
  }
}

public class C {
  public static void main(String[] args) {
    B<A.Foo> b = B.get();
  }
}

Yes, it works. The Sun Java compiler 1.6.0_13 has no problem in handling the sort-of recursive bound put on the type.

Now, would you expect the following to work?

interface A {
  static enum Foo { BAR; }
  static enum Bar { FOO; }
}

class B<T, S> {
  private B() {}
  public static <T, S> B<T, S> get() {
    return new B<T, S>();
  }
}

public class C {
  public static void main(String[] args) {
    B<A.Foo, A.Bar> b = B.get();
  }
}

Again, it works flawlessly. After all, why would multiple type arguments confuse the compiler?

So, you'd expect the following to work too, won't you?

interface A {
  static enum Foo { BAR; }
  static enum Bar { FOO; }
}

class B<T extends Enum<T>, S extends Enum<S>> {
  private B() {}
  public static <T extends Enum<T>, S extends Enum<S>> B<T, S> get() {
    return new B<T, S>();
  }
}

public class C {
  public static void main(String[] args) {
    B<A.Foo, A.Bar> b = B.get();
  }
}

Tough luck, though: It doesn't work. Apparently "no instance(s) of type variable(s) T,S exist so that B<T,S> conforms to B<A.Foo,A.Bar>". I would have thought that T=A.Foo and S=A.Bar would do the job.

As I said, I haven't read yet the relevant sections in the Java specification to see if this a problem with the language or a problem with the compiler. The thing is that the two sections take 10 and a half screens on my monitor, which signals that I should put aside maybe one whole day for it, and I don't have one whole day to spend. My hope is that it is a bug in the compiler, because otherwise I'd loose some confidence in the language itself. After all, there's something fishy about a 10-pages algorithm that doesn't end up trying the obvious solution.

BDD sucks, BDD rocks

2009-05-30T17:17:00.001+03:00

Whining mode.

BDD (Behavioral Driven Development) is the most idiotic thing I've ever heard of. It is a buzzword that stands for something I completely don't understand. So, how can I say in such strong terms that it is idiotic if I don't even know what it is about? Simple: It breaks Google. Whenever I search for information about BDDs (Binary Decision Diagrams) I find complete garbage. OK, it's not that bad: Scholar gives sensible results.

Related to Transitive Closures

2009-05-27T20:22:00.003+03:00

A problem that Mikolas bumped into.

Alice has a graph G that is closed under transitivity. Bob wants to reconstruct the graph G but Alice would only answer with YES or NO to questions of the form "is there an edge from node m to node n?". Help Bob achieve his task with as few questions as possible.

There are two possible cases. One is that Bob must aim for a minimum number of questions for the worst possible graph G. (Equivalently, Alice is evil and she keeps changing the portions of the graph G she didn't "commit" to yet, just so that Bob needs to ask more questions.) The other is that Bob aims for an expected minimum, thinking that Alice drew the graph randomly from some bag of graphs. (In the simplest case the bag is a set of all possible graphs.)

The number of nodes N is known in advance to Bob.

Any pointers?

Puzzle Answer: Postfix Expressions

2009-05-25T14:14:00.000+03:00

A solution to a two-month old puzzle.

A while back I posted a puzzle asking for a recursive and stackless postfix expression evaluator. A bit over a week ago I received a solution from Ashutosh Mehra. (Go on, have a look at his blog. It's quite nice.)

At first sight this seems like a lowly coding exercise. And it is, but with a catch: It is designed to illustrate two fundamental ideas that should be part of every programmer's ethos.

Recursion is equivalent to loops.
Recursion is implemented with stacks.

If one of these two fairly obvious statements is not built into you, then you'll have trouble finding a solution. The first statement implies that any program can be written without using loops. How? First, write all the loops using only while. Second, replace each loop while (C) B; with a call to a new function loop defined as follows:

void loop(ARGS) {
  if (!C) return;
  B; loop();
}

The condition C and the body B will probably refer to some local variables. In order to have them accessible for reading and for writing from loop we send as arguments ARGS pointers to them, and modify C and B accordingly.

Exercise: What to do if B contains break? (Note: The solution to this is supposed to be easy if the previous two paragraphs were understood.)

What about the stack? We also want to get rid of the stack.

The solution is again easy if you remember that local variables (and function arguments) come from a "stack". So the key idea is to use the call stack as the operand stack. This said, enjoy the solution.

#include <stdio.h>
#include <ctype.h>

int add(int x, int y) { return x + y; }
int sub(int x, int y) { return x - y; }
int mul(int x, int y) { return x * y; }
typedef int (*op_t)(int, int);
op_t op[256];

int c; /* last read character */

void read_digits(int* y) {
  if (!isdigit(c = getchar())) return;
  *y = eval(*y, c - '0');
  read_digits(y);
}

int eval(int x, int y) {
  read_digits(&y);
  return op[c](x, y);
}

int main() {
  op['+'] = add, op['-'] = sub, op['*'] = mul, op['|'] = add;
  printf("%d\n", eval(0, getchar() - '0'));
}

When the function eval(x, y) is called, the top value in the operand stack is y and the value just before is x. While the next token is a digit it calls itself recursively eval(y, new_digit). The "while" part is implemented by the recursive function read_digits. When the token that says what operation should be performed between x and y is read, the operation is performed and the result returned.

This variant is somewhat wasteful of memory.

Startups and the Crisis

2009-04-08T00:11:00.001+03:00

Short reviews of a few websites.

For the past few months I've been told there's an economic crisis. I've also been told about a few startups. I would have thought that in hard times people are less inclined to risk. Can anyone explain me why the opposite seems to hold? While you think about that, I'll list the sites:

TaskWriter is a site for keeping track of what you need to do. Once you go to the website you see a "please wait while I'm loading" sign and while waiting you can read that you should use this site because it's the fastest. Now, that may sound ironic, and it is. Still, once the login box appears it gets much quicker. Registering is hassle-free. Once you get in you see that the main functionality of the website is to keep track of TODO lists where items are one line long. The obvious concern is: "Do I want my TODO list on some random website?" I guess the answer depends on whether you have something to hide.

EasyTrack is a site for Romanian companies that have many cars and want to track them. Why Romanian? Probably because maps are rented and it's expensive to rent good maps for everywhere. Why track the cars? To optimize costs. I hear that giving your employees cars as a perk may be costlier than it sounds. It's probably easier to abuse than a free lunch, anyway.

Balaurul (The dragon) is a search engine for jobs… in Romania. Now I finally see some correlation with the economic crisis: More people must be looking for jobs. I wonder if similar search engines are already successful in other countries. The business model is a little too Google for my taste: simple web design, attract ads. Usually cool stuff is different.

Disclaimer: TaskWriter and EasyTrack are the startups of two of my friends from college. I also met two of the three people that started Balaurul.

Others: My brother-in-law is starting a software development company, after being CTO for a long time in a company that provides software solutions for restaurants and hotels. Finally, three of my students will work for themselves for a while.

I hope many of these will be successful. I really do. All the people involved are high quality. Which makes me wonder what would happen if they would all work together. This must be a key ingredient in making a successful business: Getting many good people to work together. I wonder how you do that.

WHY Java

2009-04-03T03:34:00.001+03:00

Y in Java.

Y is a cute concept from lambda calculus. It's easy to define in Haskell.

y f = f (y f)
fact r 0 = 1
fact r n = n * r (n-1)
f = y fact

An execution of f 3 computes 3!:

f 3
  = y fact 3
  = fact (y fact) 3
  = 3 * y fact 2
  = 3 * fact (y fact) 2
  = 3 * 2 * y fact 1
  = 3 * 2 * fact (y fact) 1
  = 3 * 2 * 1 * y fact 0
  = 3 * 2 * 1 * 1

While showing this to Claudia I realized that I never coded Y in Java. It's interesting to see how long it is.

interface Fun { int go(int n); }
interface UntiedFun { int go(Fun f, int n); }

public class Rec {
  public static void main(String[] args) {
    System.out.println(f(10));
  }

  public static int fact(Fun f, int n) {
    if (n == 0) return 1;
    return n * f.go(n-1);
  }

  public static int Y(final UntiedFun f, int n) {
    return f.go(new Fun() {
      public int go(int n) { return Y(f, n); }
    }, n);
  }

  public static int f(int n) {
    return y(new UntiedFun() {
      public int go(Fun f, int n) {return fact(f, n);}
    }, n);
  }
}

Great stuff you can do with recursion. Which reminds me: Did you figure out the last puzzle?

Postfix Expressions

2009-03-31T00:28:00.002+03:00

Puzzle: recursive postfix evaluation.

On Saturday the Computer Science&Informatics School of the University College Dublin has a local programming competition. That, and a problem from Mihai, reminded me that I didn't post puzzles here in a long time. This one is an implementation puzzle.

A typical way to evaluate a postfix expression is to use a stack.

#include <stdio.h>

int stack[1<<20]; /* operand stack */
int sz; /* stack[0..sz) is used */

int main() {
  int c; /* last read character */
  while ((c = getchar()) != '|') {
    switch (c) {
    case '+': --sz; stack[sz-1] += stack[sz]; break;
    case '-': --sz; stack[sz-1] -= stack[sz]; break;
    case '*': --sz; stack[sz-1] *= stack[sz]; break;
    default:
      if ('0' <= c && c <= '9') stack[sz++] = c - '0';
    }
  }
  printf("%d\n", *stack);
}

The code above assumes that operands are digits, that the only allowed operators are +-*, that the input is terminated by |, and that there are no other characters.

The problem is: Can you implement this without:

an explicit stack
loops

Both should be replaced by recursion. As usual, you can email me solutions to radugrigore at gmail.com and I'll post the best solution plus a list of those who solved the puzzle.

Blogs by Researchers

2009-03-29T00:52:00.003+02:00

Which researchers are more inclined to blog?

Methodology:

pick a conference/workshop
go thru the program committee (PC) and search for the word "blog" on each homepage
eliminate blogs that don't contain any Computer Science post in the last 5 posts

I do not include the blogs I know about that can't be found using the methodology above. Why? (1) If the same rules are applied to different communities then the results say something about the difference between communities. (2) I want to simulate what an outsider would be able to find with little effort.

Results:

ECOOP: Analysis, design methods and design patterns; Concurrent, real-time or parallel systems; Databases, persistence and transactions; Distributed and mobile systems; Frameworks, product lines and software architectures; Language design and implementation; Testing and metrics; Programming environments and tools; Theoretical foundations, type systems, formal methods; Versioning, compatibility, software evolution; Aspects, Components, Modularity, Reflection; Collaboration, Workflow. PC with 29 people. Blogs:

TACAS: Specification and verification techniques for finite and infinite-state systems; Software and hardware verification; Theorem-proving and model-checking; System construction and transformation techniques; Static and run-time analysis; Abstraction techniques for modeling and validation; Compositional and refinement-based methodologies; Testing and test-case generation; Analytical techniques for secure, real-time, hybrid, critical, biological or dependable systems; Integration of formal methods and static analysis in high-level hardware design or software environments; Tool environments and tool architectures; SAT solvers; Applications and case studies . PC with 29 people. No blog.

FTfJP: specification techniques and interface specification languages; specification of software components and library packages; automated checking and verification of program properties; verification logics; language semantics; program analysis; type systems; security. PC with 15 people. No blog.

STOC: algorithms and data structures; computational complexity; cryptography; privacy; computational geometry; algorithmic graph theory and combinatorics; randomness in computing; parallel and distributed computation; machine learning; applications of logic; algorithmic algebra and coding theory; computational biology; computational game theory; quantum computing and other alternative models of computation; theoretical aspects of areas such as databases, information retrieval, and networks. PC with 24 people. Blogs:

Michael Mitzenmacher

If you apply this to some other conferences I'd be interested in the results. Blogs are a good way for researchers to spread the important ideas in their specialized areas. The rate of researchers with blogs is very low.

[Edit] You may say blogs.py page, where page is the URL of a conference page that contains the program committee, to get a list of probable blogs. This cuts down the manual work a lot (but also misses some blogs, if the authors do not include "blog" in the link text).

Command Line Options

2009-03-28T21:08:00.000+02:00

A short introduction to CLOPS, a Java library for parsing the command line.

Did you ever write public static void main(String[] args)? If so, did you ever use args later? If yes and yes then you need CLOPS.

I can hear you saying that "handling args is very easy and doesn't justify learning a new technology." You are right that the benefits of a technology have to be weighted against its costs, and one of the most important costs that a technology incurs is the time spent learning it. Obviously, this poses a problem: How can you balance benefits and costs before learning? To solve this dilemma, it seems to me, most people rely on the assessment of others. So hear my word: Learning CLOPS is much easier than you think! Alas, I'm biased because I contributed to the design. I understand if you don't believe me: I started to contribute late precisely because in the beginning I was a skeptic myself. I had to see something working before changing my mind.

Most technologies have a complexity threshold: Products more complex than the threshold benefit from using the technology; products less complex than the threshold are hurt. HTML is a technology. Is it worth learning HTML for writing a blog? Not really. But is it worth learning if you want to develop a serious web-site? Probably. ViM is another technology. Is it worth learning for writing email? Definitely not. Is it worth learning for writing C programs? Maybe.

So what's the complexity threshold of CLOPS? A simple way to assess the complexity threshold of a technology is to pick a task and complete it with and without the technology. Let's write a program that prints "Hello world!" when run with no arguments, prints "Goodbye cruel world!" when run with the argument -bye, and prints a usage message in all other cases.

public class Main {
  public static void main(String[] args) {
    if (args.length > 1 || (args.length == 1 && !args[0].equals("-bye"))) {
      System.out.println("Usage: hello [-bye]");
      return;
    }
    if (args.length == 1)
      System.out.println("Goodbye cruel world!");
    else
      System.out.println("Hello world!");
  }
}

The CLOPS version is almost the same length:

public class Main {
  public static void main(String[] args) {
    HelloParser parser = new HelloParser();
    if (!parser.parse(args)) {
      System.out.println("Usage: hello [-bye]");
      return;
    }
    if (parser.getOptionStore().isByeSet())
      System.out.println("Goodbye cruel world!");
    else
      System.out.println("Hello world!");
  }
}

That's not too bad. But we do have to write one more file, let's call it hello.clo, that describes the command line.

NAME:: Hello
ARGS:: Bye: {"-bye"}
FORMAT:: Bye?;

To compile we must say

clops hello.clo
javac -cp clops-runtime.jar:. *.java

and to run we say

java -cp clops-runtime.jar:. Main

This is definitely more complicated than not using CLOPS. It indicates that for such a simple example it is not worth using CLOPS. But, by the same argument, for this example it is not worth using the build system ANT. Why write a build.xml file when you can get away without? Yet, for some strange reason some people keep using ANT even for such small projects. (Not me.) I believe the reason they are using it is that they get into a routine: copy the build.xml file of an old project, modify a little inside, and then operate in a familiar environment. It makes sense. Even if later the build process becomes more complicated than just invoking the Java compiler, it still is the case that a build can be achieved by one command: ant. The price, copying and editing slightly a file in the beginning, is something most developers are willing to pay.

It's the same with CLOPS. As soon as the command line starts to get a little more complicated you begin to feel the benefits. Are there two boolean options that shouldn't be given at the same time? You add one line to hello.clo: Your program and your documentation are updated. Does an option represent a file name that must exist? You add one keyword in hello.clo: Your program and your documentation are updated. Can an option appear only after another certain option? You guessed: You modify hello.clo slightly and you are done.

OK, now that you are convinced that it's worth using CLOPS when you write a command line tool it is time to address another question: Why would you write a command line tool in Java as opposed to, say, C? (If you are still not convinced that you should try CLOPS, then please pretend that you are for the next 5 minutes.) Well, why not? There are many programs that contain command line tools and are written in Java, such as web service testers, 3D graphics tools, bug finders, messenging and communication tools, testing frameworks, backup tools, and data reporting tools. It is true that at the moment most command line tools are written in C, but this will change. Of course, we'd be happy to see a C port of CLOPS.

We'd also be happy to hear what you think.

A Change

2009-03-28T02:20:00.001+02:00

Welcome to my new blog.

Hurray to a new beginning!

Blogger provides the new look&feel that replaces the ancient one I designed.
The title reflects a focus on readers.

The 13th World Multi-Conference on Systemics, Cybernetics and Informatics

2009-03-16T10:09:00.002+02:00

I've just been invited to submit a paper to The 13th World Multi-Conference on Systemics, Cybernetics and Informatics. I wonder what I did to deserve such an honor. I also wonder if there are idiots that don't suspect what this is after reading the name of the conference: an idiocracy-style joke. I googled for the name of the organizer (Nagib Callaos), and sure enough, he's a prank. Stay away if you don't want your name tainted forever.