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, bene ts, and drawbacks, of programming an interactive application in ASP. We nd 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 e ciency. ASP and related elds 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.
Answer-Set Programming (ASP) is a successful approach for modelling and solving NP-hard problems. We propose a framework for general-purpose applicationprogramming based on ASP and realize Tetris as a case study.
Using ASP instead of imperative languages like Java would likely be met with skepticism. We think this is mainly due to the following reasons: rstly, ASP is lacking features such as input/output facilities and programming libraries; secondly, Prolog aimed for the same but it set a negative example since it forced programmers to think in terms of the evaluation underlying Prolog (e.g., using red cuts). The resulting application programs cannot be understood in a declarative way since their (temporal) behavior is based on the Prolog search/evaluation algorithm.
We therefore consider it paramount to maintain declarativity when aiming to broaden the scope of ASP. In this work we realize a small application, the game Tetris, to investigate from a practicioner's perspective how far ASP can serve as a basis for application programming. We identi ed several critical points: the interaction of real time, logical time (steps) and state of a program, external e ects that in uence ASP reasoning, and causing change in the outside world.
We present a theoretical framework to achieve the above and we report on an implementation of this framework. The feasibility of our approach is demonstrated by ASPeTris, an interactive and playable implementation of Tetris which features editing the player name, playing the game, interrupting and continuing a game later, and a persistent high score list. Figure 1 shows two screenshots of ASPeTris.
Our Answer-Set Application-Programming framework (ASAP) allows
declarative reasoning between two logical time points: the closest time point in the past
(called prev) and the closest time point in the future (called next). ASAP enables
interaction with the real world through external atoms and actions, similar as in
acthex
Idle
ASP > > uents change Actions
initial = prev1 uents
> >
uents change
and real time are coupled via events. An event, such as keyboard activity or a
timer, triggers evaluation of ASP semantics to determine the e ect of the event.
An ASAP program de nes the reaction of the application to an event in terms of
new uent values and actions to be executed as a consequence of the event, such
as drawing the user interface or starting a timer. Actions have an execution order
and ASAP provides speci c syntax for comfortably de ning that order. After
executing actions, the framework waits for arrival of the next event which triggers
evaluation of ASP semantics anew. Fluent inertia is realized using the encoding of
The conceptual view of time in ASAP is shown in Figure 2. Real time and logical time are synchronized via the order of events. Reasoning is based on the previous logical time point, and actions are executed after computing the next logical time point. (Events that occur in the meantime are enqueued and processed later.)
This paper contributes a framework for ASP application programming which features the following concrete solutions: (i) inertial uents for declarative reasoning about program state; (ii) event- and action-based interaction with the outside world; (iii) a syntax to specify the execution order of actions; (iv) out-of-the box persistence for selected uents; (v) a working prototype implementation of the framework in hex and a playable version of Tetris.1 We found that Tetris is a demanding application scenario which points to necessary improvements of ASP syntax, software engineering tools, and solvers. At the same time our realization of Tetris shows that the declarative nature of ASP can be exploited as a strength in application programming. We believe that this work can be bene cial both for application programming and for ASP.
We give preliminaries in Section 2, discuss uents and time in Section 3, events in Section 4, actions in Section 5, persistence and the overall framework in Section 6. We discuss related work in Section 7 and conclude with Section 8. 1 Source code is available at https://bitbucket.org/peterschueller/asap-aspetris .
Answer Set Programming (ASP). We assume familiarity with ASP
Applications that interact with users are usually driven by the input from the user.
If the user clicks the menu button, the menu should appear, if the user clicks on exit,
the program stops, if the user gives no input, then the application should remain
in its current state (or the state evolves in a pre-de ned manner). Altogether, the
behaviour of an application is driven not only by a sequence of inputs but also
by the passage of time. Hence managing the change of state over time is one of
the most important concepts that distinguishes classical usage of ASP for solving
combinatorial problems from its usage for programming applications. Fortunately,
ASP has been applied to perform reasoning with time, in particular (i) in planning
(e.g.,
In an interactive application, reasoning is done on-line while the application is running and while future input is not yet known, which is similar to stream reasoning. At the same time, applications mostly have one deterministic future, and running an application means to determine what changes from the present to the future. This is similar to executing an action in planning and it also requires to solve the frame problem, i.e., the problem of what does not change.
We next combine notions of planning and stream reasoning to obtain a
declarative treatment of time and change in ASP applications. We use inertial uents
To work with uents we de ne uent atoms that are of the form #initially fluent=v in the head of a rule, with fluent and v as above.
The Tetris game area is de ned using a rule with an #initially head: #initially area(X,Y)=empty :- xcoo(X), ycoo(Y). where xcoo and ycoo represent x and y coordinates of the game area.
The stones in a falling piece are represented in an atom fallingStone(X,Y,S) with coordinates X and Y and stone of type S. If a piece cannot fall further, fixPiece becomes true and the game area is changed to contain the stones of the falling piece: area(X,Y)=S@next :- fixPiece, fallingStone(X,Y,S).
All uents are inertial: if the value is not changed by any rule, it stays at the value from the previous situation. This is realized by a rewriting to ordinary ASP atoms and an inertia encoding inspired by existing ASP planning systems. A uent fluent=v@prev is transformed into an atom val(fluent,v,1), similarly fluent=v@next becomes val(fluent,v,0). The reserved predicate val is used throughout the program to represent the values of uents, 1 denotes the previous situation and 0 the next. We decided to use 0 and 1 in this way to allow a straightforward extension for programs that need to look further into the past with increasing integers, e.g., 2 would be the situation before 1.
An initialization atom of form #initially fluent=v can only occur in the head
(1)
(2)
of a rule and is rewritten to ifluentinit(fluent,v). Initialization and inertia of
uents is handled by the following rules, inspired by
sit(0). sit(1). prevsit(0). ifluent(F) :- ifluentinit(F,_). val(F,V,S+1) :- &event[first], ifluentinit(F,V), prevsit(S). (5) val(F,V,S+1) :- not &event[first], &prevval[F](V,S),
prevsit(S), sit(S+1), ifluent(F). val(F,V,0) :- not nval(F,V,0), val(F,V,1). nval(F,V,0) :- not val(F,V,0), val(F,V,1). :- 2 <= #count { V : val(F,V,S) }, ifluent(F), sit(S). :- 0 = #count { V : val(F,V,S) }, ifluent(F), sit(S). (3) (4) (6) (7) (8) (9) (10) Facts (3) de ne situations of interest: we can access the previous situation's uent values with time point S=1 and in every evaluation of the program we consider two situations: prev=1 and next=0 (see also Fig. 2). Rule (4) represents which uents exist, (5) manages initialization where &event[first] is true in the rst evaluation of semantics (see Algorithm 1). External atom &prevval[F](V,S) provides access to the value of uent F in the answer set of the previous evaluation of the program. If an evaluation yields a uent value at time point S, in the next evaluation this uent value is provided as &prevval[F](V,S) and shifted to time point S+1 using (6). Inertia is realized using (7) and (8): a value in the past possibly remains like that in the future, moreover (9) and (10) ensure that each uents has a single unique value per situation. This encoding has the advantage that it does not require to de ne a uent domain, which is particularly important for uents with a practically in nite domain such as player names and highscores. The encoding relies on the &prevval[.](.,.) external atom to `remember' the history of uent values, i.e, the values f=v@prev. Note that determining the next state f=v'@next with the help of inertia is realized purely in ASP (without any outside machinery).
Note that the above rules can handle an arbitrary amount of previous situations by adding situations to the extension of sit and prevsit predicates in (3). In ASPeTris we did not encounter a need for more than one previous situation.
A natural question is whether all atoms in an ASP application should be uents.
Similar to the notion of the volatile part of a program in incremental answer set
programming
In an interactive application we must forget past information, since every point
in time adds new atoms, meaning that eventually atoms with information about the
past occupy all available memory. This is mainly a practical issue which we solve by
using a xed window of size k = 2. Several more involved aspects of such reasoning
have been analyzed in stream-based reasoning
Regarding the future values of uents, one can model just the next point in time, or several future steps. The latter may allow easier modelling but it is not strictly necessary, since anything deduced for k steps in the future may be deduced at k 1 steps in the future by looking back k 1 steps into the past. We here consider a minimal setting with a single future time point.
The ASP semantics of the application program are evaluated repeatedly. But how often should the ASP program be evaluated? In principle, one could evaluate immediately after evaluation of the previous time step nished. This realizes a busy-loop which is easy to implement but wastes resources. We therefore decided to evaluate the program only if some event occurred, e.g., a key press or an expired timer.
Conceptually, the only thing happening between the previous and the next situation is the evaluation of an ASP program to determine the future. This takes time in practice, therefore a thread collects all events that happen during this time in an event queue which preserves the order of events.
Events are exposed to the application program through external atoms, so their occurrence and the properties of an event can be obtained through hex as truth values. For example, &event["keyboard","special"]("Esc") becomes true if the `Esc' key is pressed on the keyboard. Multiple events may be treated by the same rules, for example &event["keyboard","normal"](Key) becomes true if any character or number key is pressed and the key is instantiated in the variable Key.
Displaying the name of the player in uent player and editing that name is achieved by the following short set of ASP rules, #initially player="New Player". player=New@next :- &event["keyboard","normal"](Key), player=Old@prev, &concat[Old,Key](New). (11) (12) (13) (14) where (11) declares the uent, (12) displays it, (13) appends a pressed key to the uent's value, and (14) removes the last character if Backspace is pressed. The required string operations are realized in external atoms &concat and &chop.
An important design issue regarding events is the question whether one iteration should handle a single or multiple events. Handling multiple events at once requires to process them in a particular order or as if they happened simultaneously. The former strategy means to represent multiple steps in one evaluation, which would make application programs more complex. Moreover, we already handle multiple time steps using repeated evaluation, hence this strategy would introduce redundancy in the framework. The latter possibility creates additional complexity as several events potentially compete for what should happen in the program, e.g., to move the Tetris piece to the right and to the left simultaneously.
While realizing ASPeTris we observed that handling only a single event at a time greatly simpli es the application program and helps to avoid bugs. Moreover, in case an event depends on complex conditions, one may be tempted to check these conditions in the framework and outside of ASP. However, this makes the interface between ASP and the outside world more complex and duplicates reasoning facilities. We decided that the ASAP framework should provide only basic events, whereas complex conditions are supposed to be represented in ASP.
The syntax of actions in our framework is inspired by acthex: an action is an atom preceeded by @ and contains as the last argument a number which is called the action's priority. For example, @exit(27,0) states that the program execution shall end with return code 27 and that the action has priority 0, i.e., it shall be executed as one of the rst actions. Multiple actions in an answer-set are executed in ascending order of their last argument (ties are broken arbitrarily).
Action ordering is especially important for drawing user interfaces: it makes a big di erence whether a blue rectangle is drawn and then some red text, or if the red text is drawn rst and then some blue rectangle (erasing the text).
We observe from imperative languages that establishing the order in which
statements are executed is no problem at all: the execution order is given straight by the
order of statements in the input program. This implicit ordering based on the
sequence of statements in the code is missing in ASP, because of the guiding principle
of declarativity: to treat programs and many aspects of semantics as (unordered)
sets instead of lists. Because the order of actions is relevant in an application, having
the possibility of ordering actions comfortably makes programs more maintainable
and readable. In functional programming, Monads
In the ASAP framework we therefore propose a minor syntactic addition, namely code blocks enclosed by [ and ] brackets. Actions in these blocks are automatically ordered in the same order as they appear in the source program, without the need to explicitly specify their priorities. We consider this syntactic sugar for specifying an order, although one might say this weakens declarativity. For example, the program [ ] draws a main menu consisting of the headline \ASPeTris Game Menu", followed by a newline, followed by the menu item \New Game".
In practice we realize this implicit action priority using a rewriter which transforms this into an ordinary hex program by removing the `@' symbol and adding to
ASP
Set
actions uent values previous uent values events
g n i tra em epO tsyS each atom a priority argument. Actions that are not inside square brackets receive priority 0, and if multiple square brackets occur, then the actions inside are ordered, but no order is enforced across both brackets, e.g., [ @aa. @bb. ] [ @cc. @dd. ] is rewritten to aa(0). bb(1). cc(0). dd(1). This guarantees that aa is executed before bb as well as that cc is executed before dd, but enforces no further ordering. Timers and Soft Events. In Tetris, pieces are falling from the top to the bottom without any user interaction, so a timer is required to trigger evaluation of a new situation. Timers are started using the action @startTimer(name,delay) where name indicates an identi er for the timer and delay is an integer in milliseconds. Timers produce events of the form &event[timer](name) which trigger evaluation of a new situation and can be handled like other events.
In ASPeTris, when the falling piece stops and is xed in the game area we also need to handle the elimination of full rows. This intuitively happens sequentially. To perform both, xing the piece and eliminating full rows in one time step, requires an extra copy of the gaming area, however. As an alternative, we introduce soft events which create a new time step and cause immediate reevaluation of the ASP program (bypassing all queued events). In our case this allows some separation of concerns and makes the program easier to write and read (at the potential cost of losing some declarativity).
An overview of the components of the ASAP framework is given in Figure 3, where arrows indicate information ow. The ASPeTris game is implemented purely as an ASP application program (top left component); the ASAP framework itself is mainly implemented as a Python program (center components) that controls the ASP evaluation and communicates with the operating system (right).
In addition to the above features, the ASAP framework also provides facilities for persistence, since this is an important topic for applications. Information is persistent if it remains known to the application across runs.
As we use uents in our framework, we chose to realize a selective persistence for uents. A declaration of the form `#persistent name.' in the program causes the code that takes care of &prevval[.](.,.) to store those uents that match 10 11 12
Algorithm 1: Core ASAP Algorithm.
input: Answer Set Application Program P (after rewriting, including uent engine) 1 A fval(F lu,V al,0) j (F lu; V al) in persistent storage on disk g // can be ; 2 f&event f(first) 7! 1g // initial event repeat 4 f&prevval f(F lu; V al; 0) 7! 1 j val(F lu,V al,0) 2 Ag 5 S AS(P; ff&prevval ; f&event g) // evaluate ASP application program if S 6= fA0 g then return "Error: zero or more than one answer set found." if @exit 2 A0 then return "Application nished." Execute actions in A0 ordered by their last argument.
Store to disk: f(F lu; V al) j val(F lu,V al,0) 2 A0 and F lu is #persistent g Ev next event in queue // waits for next event if queue is empty f&event f(Ev) 7! 1g
A A0 forever name to disk. The name matches if it matches the complete uent name, or if the uent name is a function term and the name matches the outermost function (for example `#persistent area.' makes all area(X,Y) uents persistent).
To restore a serialized state, the ASAP framework initializes &prevval[.](.,.) with the stored uent values. In the rst situation uents are then initialized using these previous values and if none is available, the #initial value of the uent is taken. The following rules achieve this when we use them instead of (5). prevFluent(F) :- &event[first], ifluent(F), &prevval[F](V,0). val(F,V,1) :- &event[first], prevFluent(F), &prevval[F](V,0). val(F,V,1) :- &event[first], not prevFluent(F), ifluentinit(F,V), ifluent(F). (15)
In ASPeTris we found it useful to make only selected uents persistent. For example the highscore list and the player name are persistently stored, however, the currently active menu item is not persistent (otherwise starting the game would always select `exit' from the previous run).
This notion of persistence makes it signi cantly easier to return to previous states of the application compared with imperative programming. In ASPeTris, simply by adding persistence of the game eld and the score and falling stones, we realized a `Continue Game' functionality. Note that we do not require explicit reading or writing of persistence, although using actions to that end might improve e ciency. Evaluation Algorithm. The core behaviour of the ASAP framework is given by Algorithm 1. Line 1 loads persistent uent values from disk. Line 2 prepares the initial event which causes loading persistence or falling back to initialization values in the rst iteration of the loop using encoding (15).
In the loop, line 4 con gures &prevval[.](.,.) to provide uent values in A to
the next evaluation of P . Line 5 evaluates the program with respect to the prepared
oracle functions for external atoms. We ensure that there is a single answer set (this
check could be replaced by mechanisms for selecting a preferred single answer set
as described in
This work is related to several important papers in the areas of planning and interacting with an (in nitely) changing world. Therefore we will only give a brief discussion of some important related work.
Our framework manages program state as uents and situations as already
described by
The acthex formalism
The oClingo framework and reactive ASP
Stream reasoning
Dedalus
Di erent from ASPeTris, most ASP research related to games focuses on
combinatorial problems of generating new game instances
In this paper we showed that ASP can be used for application programming, an area with many potential applications. We took inspirations from several existing areas of ASP and related areas and developed the ASAP framework which captures application programming and time-dependent interaction in a declarative way.
To demonstrate the feasibility of our approach, we implemented ASAP using the Python extension of the dlvhex solver, and within ASAP we realized ASPeTris, an implementation of the well-known game of Tetris. ASPeTris is a fully playable game: interactive input from the user is processed, the game is drawn, a list of highscores is persistenly stored, and the player name can be edited interactively. Our key contribution is a framework for interactive and declarative problem solving.
We furthermore proposed syntactic shortcuts that ease application programming: ordering actions implicitly by using their order of appearance in the input program, and an engine for uents to reason between logical points in time.
The work shown here is only a case study from which we have learned that the
following important issues need to be addressed in the future: (i) the full ASP code is
instantiated and evaluated over and over, which makes ASPeTris slow (2 frames per
second) and could be avoided if the solver would automatically disregard large sets
of irrelevant rules for evaluation; (ii) a declarative concept of modularity should
be integrated into the syntax to ease programming and simultaneously facilitate
automatic optimizations in the solver; (iii) a declarative method for error handling
to catch and treat exceptional cases within ASP itself would be useful; (iv) enabling
usage of nondeterminism within ASAP programs is an open issue; nally (v) a
notion of library functions to avoid `reinventing the wheel' over and over again
(e.g.,
We thank the anonymous reviewers and Yuliya Lierler for their feedback.