[Back]

W. Dvorak, G. Gottlob, R. Pichler, S. Woltran:
"Alternation as a programming paradigm";
Talk: PPDP'09 - 11^th International ACM SIGPLAN Symposium on Princeples and Practice of Declarative Programming, Coimbra, Portugal; 09-07-2009 - 09-09-2009; in: "Proc. of the 11^th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming", A. Porto, F. J. Lopez-Fraguas (ed.); ACM Press, (2009), ISBN: 978-1-60558-568-0; 61 - 72.

Alternation is a common tool in complexity theory, where it has been used to prove various complexity classifications. In this work, we show that it can also be used to enhance the expressive power of the imperative part of a programming language. 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. Moreover, we show that many practical problems have a very natural and succinct description in terms of alternation. 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.

http://dx.doi.org/10.1145/1599410.1599419

Project Head Reinhard Pichler:
Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung