## 1. IntroductionDynamic Logic Programming (DLP) combines the strengths of safe, stratified, side-effect-free logic programming in defining concepts with the power of transition rules for prescribing behavior. Because concept definitions in DLP are safe and stratified and side-effect-free, dynamic logic programs are simpler than general logic programs and they allow for more efficient implementation. At the same time, the possibility of writing transition rules adds expressive power without compromising the simplicity of logic programming. In Dynamic Logic Programming, the states of the application environment are modeled as instances of a database (here called This short paper provides technical detail about the syntax and semantics of Dynamic Logic Programming. Section 2 describes the concept of datasets; Section 3 gives details of view rules; and Section 4 covers transition rules and shows how they are used in formalizing dynamic behavior. ## 2. DatasetsA A A A The The A ## 3. View DefinitionsA basic logic program is a set of rules that define new relations in terms of existing relations. Such view definitions take the form of Prolog-like rules with the constraint that the rules are safe and stratified and side-effect-free. The vocabulary of a basic logic program is a superset of the vocabulary of any dataset to which it is applied. It includes the object, function, and relation constants used in the dataset, but it can include additional object, function, and relation constants as well. Basic logic programs can also include a new type of symbol, called a
A A
The following expression is an example of a rule. Here,
Intuitively, a rule is something like a reverse implication. It is a statement that the conclusion of the rule is true whenever the conditions are true. For example, the rule above states that A A rule in a logic program is The rule shown below is safe. Every variable in the head and every variable in the negative subgoal appears in a positive subgoal in the body. Note that it is okay for the body to contain variables that do not appear in the head.
By contrast, the two rules shown below are not safe. The first rule is not safe because the variable
(Note that this condition is stronger than necessary. We do not need every rule to be safe; we just require that the program as a whole is safe. The definition of this broader notion of safety is a little complicated and the distinction is unnecessary here, so we skip over this subtlety in the interests of simplicity.) We say that a set of view definitions is As an example, assume we have a unary relation
This is a complicated ruleset, yet it is easy to see that it is stratified with respect to negation. The first two rules contain no negations at all, and so we can group them together in our lowest stratum. The third rule has a negated subgoal containing a relation defined in our lowest stratum, and so we put it into a stratum above this one, as shown below. This ruleset satisfies the conditions of our definition and hence it is stratified with respect to negation.
By comparison, consider the following ruleset. Here, the relation
There is no way of dividing the rules of this ruleset into strata in a way that satisfies the definition above. Hence, the ruleset is The problem with unstratified rulesets is that there is a potential ambiguity. As an example, consider the rules above and assume that our dataset also included the facts View definitions in basic logic programs are required to be both safe and stratified with respect to negation. This is a departure from view definitions in Logic Programming languages like Prolog, which permit rules that are unsafe and logic programs that are not stratified. The semantics of view definitions in basic logic programs can be formalized by defining the result of applying a basic logic program to a dataset. The resulting An Given this notion, we can define the result of single application of a single rule to a dataset. Given a rule Using this notion, we define the result of repeatedly applying the rules in a single stratum Σ to a dataset Δ of facts in the vocabulary of the stratum below. Consider a sequence of datasets defined recursively as follows. Γ Finally, we define the It can be shown that there is only one extension for any basic logic program applied to any dataset. Although it is sometimes possible to stratify the rules in more than one way, this does not cause any problems. So long as a program is stratified with respect to negation, the definition just given produces the same extension no matter which stratification one uses. Note that the extension of any function-free basic logic program on a finite dataset must be finite. Also, the extension of any non-recursive basic logic program applied to a finite dataset must be finite. In both cases, the extension can be computed in time that is polynomial in the size of the dataset. In the case of recursive programs without function constants, the result must be finite. However, the cost of computing the extension may be exponential in the size of the data, but the result can be computed in finite time. For recursive programs with function constants, it is possible that the extension is infinite. In such cases, the extension is still well-defined; but in practice it may be necessary to use a different algorithm to compute whether or not a given atom is in the extension. There are multiple choices here. See Ullman's book on Database Systems and Knowledge Base Systems for a discussion of some usable approaches. ## 4. Transition RulesIn our discussion thus far, we have been talking about the use of datasets and basic logic programs to describe individual states of the world. In many application areas, it is necessary to describe not just individual states but also transitions between states. Transition rules and dynamic logic programs provide the means for us to describe such changes. The language of Dynamic Logic Programming is a superset of the language of Basic Logic Programing. Every basic logic program is also a dynamic logic program. As in Basic Logic Programming, we can write ground atoms and view definitions. However, in Dynamic Logic Programming, we can also write "transition rules", which encode information about how the state of the world changes (over time or in response to external stimuli). A transition rule is an expression of the form shown below. Each rule consists of (1) a literal (an atom or a negation of an atom) or a conjunction of literals, (2) a double shafted forward arrow, and (3) a literal or a conjunction of literals. The literals on the left are called
Intuitively, the meaning of a transition rule is simple. If the conditions of a rule are true in any state, then the effects must be true in the For example, the following rule expresses the fact that, when p(a) is true and q(a) is false, then p(a) becomes false and q(a) becomes true in the next state.
As with view definitions, the conditions and effects of rules may contain variables to express dynamic information in a compact form. For example, we can write the following rule to express the fact that the preceding transition rule holds for all objects.
As with view definitions, transition rules are required to be The transition rule rules shown above are all safe. However, the rules shown below are not. The effect of the first rule contains a variable that does not appear in any condition. In the second rule, there is a variable that appears in a negative condition that does not appear in any positive condition.
If we were to allow the first of these rules, the resulting dataset might contain infinitely many effects (all the instances of the rule's effect). If we were to allow the second rule, we might have to check infinitely many conditions (all of the instances of the negated condition). A dynamic logic program (DLP) is simply a collection of view definitions and transition rules. As with basic logic programs, we are interested primarily in dynamic logic programs that are finite. However, in analyzing dynamic logic programs, we occasionally talk about infinite DLPs, e.g. the set of all ground instances of the rules. We can define the result of executing a dynamic logic program on a given dataset to be a sequence of datasets in which the first dataset is the given dataset and every other item in the sequence is obtained by applying the transition rules of the program to the preceding dataset. More formally, given a transition rule The The Finally, we define the Note that there is a significant difference between dynamic logic programs and production systems. In most production systems, one rule is executed at a time. (Many rules may apply, but typically only one is "fired".) In dynamic logic programs, all transition rules are executed simultaneously, and all updates (both deletions and additions) are applied to the dataset before the rules fire again. This simplifies the specification of dynamics in many cases, and avoids many problems endemic to sequential update systems, such as unintended race conditions and deadlocks. ## 5. ConclusionIn practice, it is common to extend the simple version of Dynamic Logic Programming described here to include "built-in" relations (e.g. arithmetic) and other operators (e.g. aggregates). The syntax and semantics of such extensions are a little messy. Luckily, they pose no significant theoretical challenges; and, in the interest of brevity, they are not covered here. The intent of this article is to provide a concise but reasonably rigorous account of the syntax and semantics of Dynamic Logic Programming. For motivation and examples of all of these concepts, see the textbook Dynamic Logic Programming. |