ASP-01 | Just the Facts ...
A Gentile Introduction to Logic Programming using Answer Set Programming (ASP).Photo Credit: Imagen3Facts
The simplest concept in Logic Programming is a fact:p .
A fact consists of an atom (in this case the constant p) which always start with a lower case letter (a ... z) and must be terminated by a period ("."). Atoms are the fundamental building blocks of ASP programs. They represent the basic "things" or "concepts" that exist in your problem domain. An atom is an atomic sentence that cannot be broken down into simpler components (hence "atomic"). Each atom represents a single, indivisible truth about the domain. For example, if the domain in question is programming languages, then one might have the following facts (each consisting of a single atom):imperative .
declarative .
Unlike traditional programming where variables hold values, these atoms are their own values — they represent pure truths about our world. The atom imperative simply means "imperative exists as a truth". Think of it as defining the basic building blocks of reality for your specific problem.(In formal logic terms, this approach is called a Herbrand interpretation where we build a "universe of truths" from the ground up using just the atoms we declare. Looking at the example above, our universe contains exactly two truths: { imperative declarative }. This collection represents everything that exists in our current "world of discourse".)The beauty of this approach is that you get to play "universe creator". You decide what fundamental truths exist in your problem space. While you could describe the same concepts with terse atoms:i .
d .
you'd essentially be creating an obscure universe that future-you would struggle to understand. Semantically (that is, the meaning of) the two programs are equivalent but in the case of the former (2), the meaning is much more immediately obvious to the reader than the latter (3).Even though many academic examples use single letters, I strongly recommend making your atoms clear and meaningful. These workspaces will only use single letters when demonstrating generic logical concepts where the actual meaning doesn't matter.(Note that white space is not relevant (meaning that p. and p . are equivalent).)Predicates
Facts can express relationships or properties through predicates:language(imperative) .
language(declarative) .
A predicate defines a relationship between terms or describes a property that holds true. While this may look like a function call to imperative programmers, it's actually declaring a relation. This mirrors how humans naturally reason about the world. We don't think "call function language() with parameter imperative", we simply know that "imperative is a language".In this case, (4) is stating that both 'imperative' and 'declarative' have the property of being a language. The predicate language(imperative) is stating a fundamental truth about our universe and not executing an operation. Think of predicates as "describing the world" rather than "doing something".One does not need to define this relation (language) or any of its arguments. (In fact, one cannot define the signature of the relation. There is no syntax in the logic programming language to support it. This is one of the challenges of reading logic programs especially if coming from an imperative language background in which types play a significant part.)Arity
When referring to these atoms one uses the convention <predicate name> / <arity>. In (4) the predicate name (also called functor or predicate symbol) is language and the arity — the number of arguments — is 1 so one writes language/1. The simple atoms in (4) are also predicates but with arity of 0. It is possible to write these atoms in the same way:imperative() .
declarative() .
and refer to them as imperative/0 and declarative/0. This is inconvenient to write and is considered bad practice.It is possible to have predicates with the same name but different aritylanguage .
language(imperative) .
language(natural, imperative) .
The three predicates are language, language/1, and language/2, respectively. imperative and natural are terms.Complex relations can be trivially defined:on(book, desk) .
above(shelf, desk) .
The first relation (on/2) may be read as "the book sits on the desk" and the second (above/2) as "the shelf is above the desk". How did one know that it was "the book sits on the desk" and not "the desk sits on the book"? Unfortunately, you don't! The language itself does not know or even care. As long as the programmer uses the relation consistently then the correct answers will be found. It is left to the programmer to define and manage these conventions.Programs, Solvers and Answer Sets
Each of the above groups of statements is complete program. Processing a logic program using a solver results in answer sets. An answer set consists of all atoms that can be derived from the statements in the program. For example, the answer set for program (1) is which simply returns the atom p that it was given. Similarly (and confusingly for imperative programmers), the answer set for program (4) is {language(declarative) language(imperative)}
{above(shelf,desk)on(book,desk)}
Answer Sets
When a solver processes a logic program, it produces answer sets — collections of atoms that represent valid solutions. Think of answer sets as "possible worlds" where certain combinations of atoms are simultaneously true. An answer set consists of all atoms that can be (acyclically) derived from the rules of the program.Like any proper set, answer sets are unordered collections of unique elements:p .
q .
p .
The answer set for (8) is and not { p p q }. The order doesn't matter: { p q } and { q p } represent the same answer set. (These workspaces generally present atoms in lexicographical order to make scanning and reading easier.)A program can have multiple answer sets if there are different valid combinations of atoms that satisfy all the rules. Each answer set must be:- Justified: every atom must be supported by facts or rules
- Minimal: contains only necessary atoms (no extras)
- Stable: can't add or remove atoms without breaking rules
Think of it like building with blocks — you can only add pieces properly supported by what's underneath, and you can't remove pieces others depend on. The solver systematically builds these sets using stable model semantics until it finds all valid solutions.Some key properties of answer sets:- A program with no answer sets has no solutions
- The order of answer sets is arbitrary (
{ p } { q } = { q } { p }) - Answer sets are always minimal (if
{ p } is valid, { p q } cannot be since { p } is a (proper) subset of { p q }) - The empty set
{ } precludes other answer sets (the empty set is the subset of any other set)
Set notation { } will be used throughout to emphasize that an answer set is just that: a set.
Statement Order
Unlike imperative programs, the statements in ASP can be written in any order. For example, (2) can be written as:declarative .
imperative .
and it will have no impact on the answer sets. Because answer sets and the atoms within them are independent of order (i.e. they form a set), it makes sense that the statements that compose an ASP program also form as set and are therefore order independent!
Combining Facts | Connectives
Conjunction
As you already saw above, multiple facts may be specified:p .
q .
This can be read as "p and q" and results in a single answer set with those atoms .A conjunction may also be found within a predicate:language(imperative ; declarative) .
This program results in the same answer set as (4) {language(declarative) language(imperative)}
on(book,shelf ; computer,desk) .
The results are {on(book,shelf) on(computer,desk)}
," binds before ";" to support this case. Remember that white space is not relevant so this could have been written:on(book, shelf ; computer, desk) .
which makes it harder to see the relation between the pairs.Note that parenthesis cannot be used for grouping in this case:on((book, shelf) ; (computer, desk)) .
{on((book,shelf)) on((computer,desk))}
(book,shelf) form tuples — ordered collections of terms. While valid syntax, using tuples this way typically isn't what's intended when working with predicates.
Disjunction
A fact may be the disjunctive combination of two or more atoms (separated by a semicolon ";"):p ; q .
This is read as "either p or q" and results in two answer sets each with their own atom (which is also read as "either p or q").There are two things to notice from this example:- The result of a program may consist of multiple answer sets — there may be multiple solutions to a problem.
- You cannot rely on the semicolon to indicate whether are statement is a conjunction as in (11) or disjunction as in (15). In (11) a semicolon is used simply because a comma cannot be used. (Remember that a comma is used to separate terms in a predicate (see (13) for example).) See "Final Note on Disjunctions" below for more information.
Combinations
The conjunction and disjunction of atoms may be combined:m .
p ; q .
This is read as "m and either p or q" and results in two answer sets each having two atoms .fruit(apple ; orange) ; vegetable(carrot ; beet) .
This combination results in {fruit(apple) fruit(orange)}{vegetable(beet) vegetable(carrot)}
Combinations++
To give a small taste of what is to come and demonstrate the combinatoric power of logic programming, think about the following examples before looking at the answer sets:m ; n .
p ; q .
Results in .parent((janie ; pete ; tommy ; zuzu), (mary ; george)) .
Results in:{parent(janie,george) parent(janie,mary) parent(pete,george) parent(pete,mary) parent(tommy,george) parent(tommy,mary) parent(zuzu,george) parent(zuzu,mary)}
;" and "," operators.Final Note on Disjunctions in Facts
Any delimited set of atoms in a fact results in a disjunction of those atoms:p , q .
andp ; q .
produce the same answer sets and , respectively. In other words, it's not the comma or semicolon that determines if the atoms form a conjunction or disjunction. It is best to use a semicolon as it will provide a visual reminder that it is a disjunction since a comma is used in rules to denote a conjunction.One final example of this:p ; q , r .
results in as expected since no matter what delimiter is used, it is a disjunction.
Free Your Mind
Forget everything you know about programming. No, really — throw it all out. Those carefully crafted loops, meticulously managed variables, and precisely planned procedures? Gone. You're about to enter a world where you don't tell the computer how to solve problems. You simply describe what's true about your world and let logical reasoning do the rest.Think about how you naturally solve problems. You don't think "initialize variable x, increment counter, check condition…". You think in terms of facts and relationships. "Books go on shelves, shelves go on walls, therefore books end up on walls." ASP mirrors this natural reasoning process.ASP isn't just another tool in your programming toolbox. It's an entirely different way of thinking about problems. One that may feel strangely familiar because it's closer to how your mind already works. Welcome to a world where you stop instructing and start describing, where solutions emerge from truth rather than procedure.
