[Back]


Scientific Reports:

W. Dvorak, G. Gottlob, R. Pichler, S. Woltran:
"Alternation as a Programming Paradigm";
Report No. DBAI-TR-2009-64, 2009; 28 pages.



English abstract:
In this work, we show how the expressive power of an imperative programming language can be augmented by integrating alternation into it. In particular, we present Alter-Java - an extension of Java by language constructs to express alternation, i.e., a sequence of
"there exists" and "for all" statements. Indeed, many practical problems have a very natural and succinct description in terms of alternation. Two-player games are obvious representatives of this species. But alternation is by no means limited to games. Also many problems with a procedural description of the solutions have a very compact declarative description via alternation, among them the evaluation of logic programs. Alternation is commonly applied to complexity theoretical studies where it has proved very useful in various complexity classifications. In this work, we demonstrate that alternation is also a practically relevant programming paradigm which nicely fits into general purpose programming languages. In order to guarantee an efficient execution of such programs, we have introduced several optimizations. We also report on experiments with our implementation of Alter-Java. The results thus obtained illustrate that our alternation framework leads to competitive running times while the code to be written is significantly shorter than without this new language feature.

Created from the Publication Database of the Vienna University of Technology.