30 March 2009

Postfix Expressions

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.

28 March 2009

Blogs by Researchers

Which researchers are more inclined to blog?

Methodology:

  1. pick a conference/workshop
  2. go thru the program committee (PC) and search for the word "blog" on each homepage
  3. 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:

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

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

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.

16 March 2009

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

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.

Summer School on Programming Languages

Here's a summer school that you'll enjoy if you care about programming languages. The location is in the middle of nature (and that's great). The food is quite tasty (at least by my standards). The density of smart people was overwhelmingly cool. In lectures I didn't get bored as I did in all UCD courses and I didn't fell asleep because I didn't understood one word as in most research talks. The density of information was just right: I could follow almost all that was said, but with great effort.

If you are still unconvinced, check out the list of speakers.