Clingo (Answer Set Programming)

Answer Set Programming (ASP) looks like Prolog, but works differently: a program is a description of a problem, and a solver finds all "answer sets" (stable models) that satisfy it. Clingo, from the Potassco group in Potsdam, is the most widely used system.

Paradigm: Logic Programming

What Makes Clingo (Answer Set Programming) Special

  • Generate and test. You write rules that generate candidate solutions (choice rules) and constraints that eliminate bad ones. The solver does the search.
  • Solutions, not queries. A run returns whole solutions, called answer sets, and can enumerate all of them or find an optimal one with #minimize.
  • Constraints are one-line rules. A rule with an empty head, such as :- edge(A,B), assign(A,C), assign(B,C)., means "this must never happen".
  • Compact notation. 1 { assign(N,C) : color(C) } 1 :- node(N). says every node gets exactly one color. Intervals such as 1..4 and pooling color(red;green;blue) keep programs short.
  • Fast, modern solver. Clingo uses conflict-driven clause learning, as SAT solvers do. It solves scheduling, configuration and planning problems that are hard to program by hand.

Example: Coloring a map with three colors

node(1..4).
edge(1,2). edge(2,3). edge(3,4). edge(4,1). edge(1,3).
color(red;green;blue).

% every node gets exactly one color
1 { assign(N,C) : color(C) } 1 :- node(N).

% neighbors must differ
:- edge(A,B), assign(A,C), assign(B,C).

#show assign/2.

How It Works

  • node(1..4) expands to four facts, and color(red;green;blue) to three.
  • The choice rule is the generator: for each node, pick exactly one color. There are 34 = 81 candidate assignments.
  • The constraint removes every candidate where two connected nodes share a color. What is left are valid colorings.
  • #show assign/2. prints only the assignments. Running clingo 0 colors.lp lists all answer sets, and node 1 and node 3 always differ from each other.

History and Where It Is Used

ASP is used for product configuration, scheduling and timetabling, bioinformatics, planning and explainable AI. Clingo also powers the package concretizer in Spack. See the Clingo lesson in the DSL roadmap for more.

Learn More