Answer set application programming: A case study on Tetris

Abstract

Answer-Set Programming (ASP) is a successful branch of the logic programming paradigm with many applications in modelling and solving of NP-hard problems. Combinatorial problems are the main application domain of ASP and it seems unsuitable for serving as a programming language for interactive applications. However, we conjecture that there is no theoretical obstacle for using ASP to that end. As witnessed by functional programming, it can be useful to use a declarative paradigm for creating applications. In this work we explore possibilities, benefits, and drawbacks, of programming an interactive application in ASP. We find that this is hard mainly for the following reasons: managing change over time, interaction with the user, generating output that is ordered (i.e., not a set), handling persistence of certain data, and ensuring efficiency. ASP and related fields provide powerful techniques for representing actions and change, executing programs with respect to external environments, and processing external events. Even if the full power of these techniques is not required to build an interactive application, combining them is necessary, and putting together these concepts in a practical framework is challenging. We realize such an integration in a framework we call Answer Set Application Programming framework which is based on the HEX language and features syntactic shortcuts to make application programming more intuitive. We describe design decisions and discuss alternative possibilities. Our sample application is a playable version of Tetris which demonstrates that ASP can be used as a general-purpose programming-language.