ASP is a peculiar programming language, that shouldn't be confused with the Astronomical Society of the Pacific, the band, or ASP.NET.
It's that kind of language which struggles to sum elements in a list, but needs only 6 lignes to solve any sudoku.
This is a tutorial to learn to read, write and use ASP for various tasks.
Our goals: decide the placement at table for your wedding, build your computer, solve riddles, Zelda's dungeons and sudokus.
After this tutorial, ASP will be an everyday tool, for instance to find solutions to your funny uncle's riddles, choose the best hostel, design a pathfinder for your robotic vacuum cleaner, or save time when you are coding and need quickly the results of a complex algorithm.
Introduction
This article is a tutorial i personnally want accessible for everyone, about Answer Set Programming, a declarative programming language implementing the constraint programming paradigm (as java implements object-oriented, and haskell the functional paradigm).
For those of you that know it, ASP will remind you Prolog, because the two languages stand on the same concepts, altought they do not implement it the same way.
L'objectif n'est pas seulement d'apprendre les bases en faisant joujou, The objective is not only to learn the basics while playing, but to develop programs that solve real life problems, with few additionnal lines to allow its use in everyday life.
In a way, this tutorial also targets peoples that didn't code yet ; after all, logical languages are the best to start :) I will observe a simplification effort during the whole tutorial, precisely to allow peoples with zero programming knowledge to get something out of it.
Aussi, une grosse partie du tuto est théorique. Ce n'est peut-être pas très équilibré, surtout au début. Also, a big part of the tutorial is theoretical. This is maybe not well balanced, especially at the beginning. If you are not versed into theory, go directly to installation, and play with the language introduction.
Quêtes annexes
You will find in this blog many other articles about ASP. They are, by reference to video games, optional side-quests, independant from the main matter found in this tutorial. A basic comprehension of ASP is sometimes necessary, so you should only reach side-quests after a good time on this tutorial.
Since this tutorial was initially written in french, the following side-quests are only available in french (currently none is available in english) :
- Encodings, about search space and cost induced by some encodings
- Temporal logic, about time representation and problem solving using that notion
Look up the page sources if you want a preview of incoming matter.
Few preliminaries links
Where we ask ourselves why writing a tutorial if it's all about sending people away
I will happily advice you the parallel reading of another tutorial ; it always help to get multiple sources to understand a concept. To be honest, i found only this one (en anglais), that pass really quickly over the basics.
The scripts and encoding used here are available on the repository learning-ASP. You can therefore download them, and participate to their development if needed.
Note that clingo, the grounder/solver we will use, comes with a complete manual, an impressive list of examples of various kinds in its sources (i insist, take a tour, there is an example for almost each feature of the solver), and an active mailing list where lots of interesting questions are raised and answered. (there is another mailing list for developers announcements, like new solver versions)
Also notes that this blog speak about ASP on a regular basis:
- Deponia and ASP : solve a game puzzle with ASP
- se-lang (french) : design astrophysical systems with ASP
Prerequisites
A bit of logic. Boolean, it's even better. Seriously, we will speak about logical programming ; knowing what is boolean logic and its main operators is a plus. However, you do not need an expertise: just basic understanding of the "and" and "or" operators in logic. In short, reading the examples in wikipedia page, or these one that are very cool but quite brutal. If you have better ressources, please share them ! (my contact is on the right)
General concepts
Where we discover how we will be eaten
Declarative programming principles
How to collect all positive integers lower than 100 and divisible by 3 ?
In python, or any other procedural language, a way of doing it (on the right after #, it's comments for humans, that the machine will ignore) :
for nb in range(1, 100): # for each number from 1 to 100
if nb % 3 == 0: # if the number is divisible by 3
print(nb) # print the number on screen
What you need to see here, is that we explain to the computer executing the code how to arrive to the solution that interests us. This paradigm, called imperative, consist to explain how to compute the solution.
It's in fact a quite unnatural approach, and you feel it when you start programming (or look at students). It's quite appalling to have to explain something to a computer which seems to have the understanding abilities of a 5 years old child (and that's worse with low level languages), and that's a big problem in informatic teaching.
Declarative programming approaches the problem differently: the human must not explain how to reach the solution, but instead to describe it, id est answers to the what, which is much more natural for us humans. The declarative paradigm consist in the explanation of the what.
HTML is a good example of declarative language: we describe the solution (the final structure of the web page). HTML is not an imperative language ; incidentally, if the final page depends on external parameters (user account for instance, to show his avatar on the page upright corner), you can't rely on HTML only. That's at this point that imperative languages intervene (javascript, php, python, java,…), to generate HTML from templates and the external parameters.
Without these languages, it would be necessary to have in memory all possible pages, ready to be used, which is not possible for most websites, and hardly manageable.
Logic programming programming
The logic paradigm is a subset of the declarativ paradgim. In other word, a logical language is a declarative language. In the other way, a declarative language is not necessarily logical (HTML for instance is not logical).
The logical paradigm stands on formal methods coming from mathematics and logic theory. It's with these tools that the solution description (the what) is told to the computer.
That's exactly to that language category to which ASP belongs.
To get an insight on concepts of logical programming, let's imagine a language that would allow us to explain the solution to the python program seen earlier (compute the integers between 1 and 100 that are divisble by 3) :
Well… then, all the numbers divisibles by 3, you know,
but between 1 and 100. And «numbers», yes, but not the one with comma, you know.
Yeah, decimal number, that's it.
This language, english, has two attractive properties : most english speaker would understand it, AND they would be able to reuse it to express the same problem, or a variation of it (divisible by 4, numbers from 1 to 200,… try yourself at home, you will see it's easy).
The problem, today in informatic, is that to create a program that would understand that language belongs to science-fiction. Except, and that's the object of that tutorial, we want to use our personal computer, not a supercomputer with a natural language search team.
So, let's try to make a language that our little computers may understand:
print x, so that: x is an integer, 1 < x < 100, x is divisible by 3.
That's understandable, simple and efficient ; it's logical programming ! That particular language is not implemented, admittedly (and ASP is little less high-level, i.e. close to natural language), but it's an example of expressive language. We can also verify that it's all about describing the solution.
The wikipedia page will tell you more about it.
Constraint programming principles
We can define constraint as a restriction on solutions. In other words, the constraint programming consist in add expressions that discard solutions, that would however be authorized.
It's an effective way to ensure that a property is respected in all solutions.
About or example on the numbers from 1 to 100 divisible by 3, we coan found some constraints: only integers, or must be divisble by 3, or must be lower than 100.
In reality, constraints are really natural in our natural languages.
"two players can't start at less than 5 meters from each others" would say a game designer.
"A taxon can't belong to two lineages" will tell the phylogeneticist.
"I can't put more than 2 milk packs on the back port of the shopping trolley", i say during shopping.
Anyway, it's often simpler to express a constraint instead of including the restriction in the answer generation itself (well, i will go shopping while keeping at most 2 milk pack on the back of my trolley).
Also, constraint is sometimes less costly. For instance, if i'm looking for my trolley in the shop, i will compare the one i see based of the souvenirs i have of it: well… this one has a milk pack on the back, that's maybe mine. But to do that, i will not enumerate all shared items: there is a pasta box, a toothbrush,…. Instead, i will use constraints: no, it's not this one, there is no chocolate bar.
In short, when we're looking for something, discard bad possibilities by finding a single difference or malformed information is often quicker than the enumeration of good points.
In general, a language allowing for constraint programming could be divided into 2 parts:
- define possible solutions (modeling of search space)
- forbids results that we are not interested in (constraint)
The first part is generation, where we yield the candidates for solutions. And, since the candidates are not all good enough, we need to filter them, which is done in second part, constraint application. (digression-culture: it's not the only use of constraints, but it's a subject for later)
Answer Set Programming is a logical language where constraints are fully parts of the language, as much as other declarations. However, the dichotomy between génération and constraint can be seen in a lot of ASP encodings/code, because developers intuitively get that two-parts scheme in their thinking.
Example of ASP code/encoding
Let's go back to our initial problem: printing to the screen all integers from 1 to 100 divisible by 3. In ASP, we could solve the problem that way:
#show solution(X): X=1..100, X\3=0.
We get the same structure as earlier: print solution(X) for X between 1 and 100, and X\3=0 that is the verification that X is multiple of 3. That's quite close to the precedent proposition.
At the end of the tutorial, you will be able to understand that code perfectly, and imagine other way to solve it.
Outillage
Where we finally do something ; altought not code
Many implementations of ASP exists, each with its unique approaches and features to solve more or less specific problems.
Pour ce tuto, nous allons utiliser la suite , un ensemble de logiciels In this tutorial, we will use the Potassco suite, a software collection that work around one idea: implements and use ASP. More particularly, we will use clingo.
(if you are motivated enough, and you are at ease, take another implementation ; in general there will be no major conceptual differences, but some implementations will behave really differently.
That said, following a tutorial with the right tools is probably the simplest and safest way to go. So, do as you want, but in doubt, use clingo and explore the other implementations later)
Clingo, in two (hundred) words and two parts
If you understand nothing to this section, no worry: that's just to pin correctly the concepts for informaticians. Read this anyway, there will be some simplifications in the middle.
Clingo is to ASP what CPython is to Python: a complex program that understand and apply the language side-effects.
Clingo is in reality composed of two parts: gringo and clasp (we can get them and use them independently).
Gringo is to ASP what the compiler of CPython is to Python, or what gcc is to C: a grammar and a routine set that compile the code to a extremely simplified language. (in the case of ASP, this simplified language is smodels, for Python it's bytecode, and for C it's assembly)
Clasp is to ASP what the CPython interpreter is to Python : a set of routines that understand the simplified language computed by the previous routines (gringo/compilateur) to apply the side-effects (memory and computations).
To be more precise about gringo and clasp, the first compile a program that follows the ASP grammar (and a little more, we will see that), and the second is a routine that, with the help of a heuristic, will seek for acceptable solutions (or stable models) in the compiled program. It will then print them in a human-readable way.
In ASP, we call grounding the part implemented by gringo, and solving the part implemented by clasp. Clingo is a program that take care of both grounding and solving in a single short.
From our user point of view, that's saved time, but we need to know that in order to understand the cost of some encodings. Also, in some case, we may want to handle the two independently to achieve some solving effects. It will be the subject of side-quests.
Installation
It is possible to run clingo in a browser. That's quite useful : there is nothing to install, it works out-of-the-box, no need to think.
Si vous voulez savoir comment ce bijoux technologique est possible, allez voir l'issue à propos, et mon exemple fonctionnel.