Editing Logic programming (section)

=== Answer set programming ===
{{Main|Answer Set Programming}}

Like Datalog, Answer Set programming (ASP) is not Turing-complete. Moreover, instead of separating goals (or queries) from the program to be used in solving the goals, ASP  treats the whole program as a goal, and solves the goal by generating a stable model that makes the goal true. For this purpose, it uses the [[stable model semantics]], according to which a logic program can have zero, one or more intended models. For example, the following program represents a degenerate variant of the map colouring problem of colouring two countries red or green:
<syntaxhighlight lang="prolog">
country(oz).
country(iz).
adjacent(oz, iz).
colour(C, red) :- country(C), not(colour(C, green)).
colour(C, green) :- country(C), not(colour(C, red)).
</syntaxhighlight>

The problem has four solutions represented by four stable models:
<syntaxhighlight lang="prolog">
country(oz). country(iz). adjacent(oz, iz). colour(oz, red).   colour(iz, red).

country(oz). country(iz). adjacent(oz, iz). colour(oz, green). colour(iz, green).

country(oz). country(iz). adjacent(oz, iz). colour(oz, red).   colour(iz, green).

country(oz). country(iz). adjacent(oz, iz). colour(oz, green). colour(iz, red).
</syntaxhighlight>

To represent the standard version of the map colouring problem, we need to add a constraint that two adjacent countries cannot be coloured the same colour. In ASP, this constraint can be written as a clause of the form:
<syntaxhighlight lang="prolog">
:- country(C1), country(C2), adjacent(C1, C2), colour(C1, X), colour(C2, X).
</syntaxhighlight>

With the addition of this constraint, the problem now has only two solutions:
<syntaxhighlight lang="prolog">
country(oz). country(iz). adjacent(oz, iz). colour(oz, red).   colour(iz, green).

country(oz). country(iz). adjacent(oz, iz). colour(oz, green). colour(iz, red).
</syntaxhighlight>
The addition of constraints of the form <code>:- Body.</code> eliminates models in which <code>Body</code> is true.

Confusingly, ''constraints in ASP'' are different from ''constraints in CLP''. Constraints in CLP are predicates that qualify answers to queries (and solutions of goals). Constraints in ASP are clauses that eliminate models that would otherwise satisfy goals. Constraints in ASP are like integrity constraints in databases.

This combination of ordinary logic programming clauses and constraint clauses illustrates the generate-and-test methodology of problem solving in ASP: The ordinary clauses define a search space of possible solutions, and the constraints filter out unwanted solutions.<ref>Eiter, T., Ianni, G. and Krennwallner, T., 2009. Answer Set Programming: A Primer. In Reasoning Web. Semantic Technologies for Information Systems: 5th International Summer School 2009, Brixen-Bressanone, Italy, August 30-September 4, 2009, Tutorial Lectures (pp. 40-110).</ref>

Most implementations of ASP proceed in two steps: First they instantiate the program in all possible ways, reducing it to a propositional logic program (known as ''grounding''). Then they apply a propositional logic problem solver, such as the [[DPLL algorithm]] or a [[Boolean SAT solver]]. However, some implementations, such as s(CASP)<ref>{{cite journal |first1=J. |last1=Arias |first2=M. |last2=Carro |first3=E. |last3=Salazar |first4=K. |last4=Marple |first5=G. |last5=Gupta |title=Constraint Answer Set Programming without Grounding |journal=Theory and Practice of Logic Programming |volume=18 |issue=3–4 |pages=337–354 |date=2018|doi=10.1017/S1471068418000285 |s2cid=13754645 |doi-access=free |arxiv=1804.11162 }}</ref> use a goal-directed, top-down, SLD resolution-like procedure without
grounding.