Can anyone explain labelling in simple terms?

General
1

I’ve been reading as much as I can about Prolog, and keep seeing mentions of labelling as a way of improving your code. However, I can’t find a decent explanation of what it actually does.

For example, two excellent statckoverflow answers I saw (this one and this one) show examples of adding labelling to code to help find solutions, but neither of them explain what it’s actually doing.

The SWI-Prolog docs have the same issue. I’m sure it’s clear to the experts, but as a beginner, I can’t make head or tail of it.

Anyone able to explain? Thanks

1 Like
2

Do you have access to ChatGPT? Is so try this prompt.

For Prolog with constraints what does labeling do?

If you think the answer is good, post the completion here for others. :slightly_smiling_face:

The completion ChatGPT gave me (click triangle to expand)

In Prolog with constraints, labeling is a process that finds solutions for a constraint satisfaction problem by systematically exploring the search space.

Labeling is a built-in predicate in many Prolog systems that takes a list of variables as input and assigns values to them one at a time, in a depth-first manner. It starts with the leftmost variable and assigns the first value that satisfies all the constraints in the current context. It then moves on to the next variable and repeats the process until all variables have been assigned values. If at any point a variable cannot be assigned a value that satisfies the constraints, labeling backtracks to the previous variable and tries a different value.

The process of labeling is used in Prolog with constraints to find solutions to constraint satisfaction problems such as scheduling, planning, and optimization. By assigning values to variables in a systematic way, labeling explores the search space efficiently and finds solutions that satisfy all the constraints in the problem.

You might also be interested in the site by Markus Triska, specifically the sections starting with

3

This is because it would first have to explain how a constraint solver works. The assumption is that you shouldn’t know how it works as long as you can understand what it does. I don’t have an opinion on whether this is a safe assumption. I guess it depends.

But please understand that a constraint solver is not Prolog, this is a tool implemented on top of a Prolog.

4

Some people, notably on SO, seem to disagree :slight_smile:

In a nutshell, I’d say labeling is related to constraints. Constraints create relations between logical variables. After adding constraints, these variables may get concrete values immediately, e.g., A #= B + 1, A = 3, results in B=2. Given a set of variables with constraints, labeling assigns concrete values to all these variables. The default goal is typically to find a state where all variables are labeled as quickly as possible. For example, it may start assigning values to the variables with the smallest domain first. Alternatively, it may be given objectives such as maximizing some variable. These details all depend on the constraint system and the implementation and you’ll need to consult the documentation or code of the constraint system for more detail.

I guess that touches the fundamentals of most/all current declarative systems, whether we are talking constraint logic programming, ASP, SQL, … They promise a correct answer. Sometimes they promise termination. They often cannot make promises on resource (time, space) requirements for all problems that can be expressed. It is always hard to predict whether the system finds the best algorithm (e.g., query plan for databases) and whether that algorithm is good (fast) enough.

Still, constraint systems are great for many problems :slight_smile:

2 Likes
5

labeling/2 is specific to clpfd, which uses attributed variables.

In a nutshell, it can defer some operations on integers - which can sometimes aid efficiency, depending on the problem and the code.

I would not recommend, though, to dive into clpfd without firstly being comfortable with Prolog.

6

Thanks for the reply (and to everyone actually).

The ChatGPT answer wasn’t bad, but didn’t really clarify it enough for me. However, the explanation in Markus Triska’s video was brilliant. Whilst I don’t claim a deep understanding of labelling, I can see enough to see when and how you’d use it.

As it happens, I’ve been going through that site for a couple of weeks, and have learnt a lot. I just hadn’t got to that page yet :+1:

Thanks again

7

That is true. It is one of those answers that if you know the answer sounds good but until you know the answer it is just another of many puzzle pieces that just do not fit together.

One thing that helped me learn labeling better was to just remove it from the code and see what happens. Often the result is useless, doesn’t stop processing or help you learn, but every so often you find a constraint problem were removing the label does one thing that you can understand and putting it back does what is expected and you start to see that some of the puzzle pieces actually make sense in the situation.

8

Just to expand on this a bit.

When using CLP, one first defines the constraints on a final solution. In some cases, that’s all you need to do. But in general, some kind of further search is required. In some cases the constraint solver is too weak, or the constraints are insufficent, or there are multiple solutions. In any case, a labelling predicate will divide the original problem into sub-problems such that the barriers to finding a unique solution no longer apply. Backtracking can be used to find other solutions, e.g., by using findall/3.

A labelling predicate for an integer problem can be as simple as using between/3 to enumerate all the values in the domain of a constrained variable. (library(clpfd) provides many other options.)

3 Likes
9

Maybe it’s just me, but I find ChatGPT (and all the other GTP-based stuff out there) to be pretty useless. It produces very coherent, impressive-sounding rubbish! I’ve asked it questions on topics I know a lot about, and can see how badly it leads you astray, which makes me extremely suspicious of asking it about topics I don’t know much about.

Sure if you want to know the capital of China, or who won the Eurovision Song Contest in 1923, then it’s fine, but for questions with any depth, I find it very misleading.

1 Like
10

In my (very brief) experience, adding it sped up the code no end, so removing it just made things run more slowly.

Having seen that video on the n-queens problem, I feel I have some idea of what it’s doing now, although I’m no clearer as to why it’s called labelling, as it doesn’t seem to relate to how I’d understand that word. I guess I just need to play and read a lot more. With a basic understanding, I’ve more chance of being able to make sense of what I read.

Thanks again

11

Do you mind to expand your expansion! Specifically two points…

I’m a bit confused, as I thought that a lot of writing Prolog was setting your constraints. Maybe I’m misunderstanding the word, but if I see code like…

pred(L) :- length(L, 3).

…then I read that as a constraint on the list L to be of length 3. However, that’s nothing to do with CLP, that’s plain Prolog.

Please can you explain what you meant by “When using CLP, one first defines the constraints on a final solution”

Also, you said “a labelling predicate will divide the original problem into sub-problems.” From what I saw in that video, labelling ruled out potential solutions that didn’t fit the constraints. For example, in his first attempt to solve n-queens, he generated all possible solutions, then checked which ones worked. Obviously that meant checking a whole load of solutions that never had a chance of working.

If you watch the animation he shows (starts at 17:40), you see a load of queens in the first row, and it’s bashing away moving queens in the last columns, which is a waste of time as the presence of a queen in the first row of the second column means that the solution won’t work.

When he gets to labelling (from about 24:40), as soon as he places the first queen, it works out that there’s no point in placing the second queen in the first or second rows, and so skips a large number of potential solutions that won’t work.

If that’s a correct understanding (and please correct me if it isn’t), then I don’t see how this fits with the idea of splitting the problem into subproblems.

Thanks again for the reply. Hope you don’t mind my incessant questions, but I’d really like to understand this.

12

Yeah, I would take some of the content with a bit of salt, after all those are promotional videos for a specific library. Either way, how exactly the constraints are propagated is a very big topic. It will vary from library to library and from one specific problem to the next. You might also need to nudge the constraint solver in the right direction, and for that you need experience, probably.

Another topic would be, when a constraint solver doesn’t pick the best (?) strategy for a particular problem, is that a bug?

In relational databases you do end up seeing mysterious failures of the query planner, and sometimes you find mysterious workarounds, but proving that it is a bug is sometimes not trivial.

14

While one view is that Prolog is just a CLP language over the domain of Hebrand terms, more commonly (from https://en.wikipedia.org/wiki/Constraint_logic_programming)

Constraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. A constraint logic program is a logic program that contains constraints in the body of clauses.

So while you might view pred(L) :- length(L, 3). as a “constraint” that may not be a common understanding.

A library like clpfd extends the semantics of arithmetic over the finite domain of integers so, unlike standard Prolog, you can have integer expressions that contain variables expressing a true relation , e.g., X #= Y+1, that must be satisfied to yield a solution. (Some, like Markus, argue that’s the way arithmetic should always be done.) Also note that the SWIP library includes different CLP implementations over different domains, e.g., clpb over booleans, also with labeling/2, clpqr over rationals/reals, and others are available through add-on packs.

Why isn’t (arbitrarily) placing the first queen defining a sub-problem, since it only looks for solutions with that queen placement? A different sub-problem would involve placing the queen in a different position.

Also note:" it works out that there’s no point in placing the second queen" - it isn’t the labelling predicate that works this out, it’s the resultant constraint violation discovered by clpfd’s constraint propagation engine.

15

Using indomain/1, you can make a simple version of labeling/1:

labeling(Vars) :- maplist(indomain, Vars).

Sometimes labeling/1 is needed for outputting an answer (you might want to use random_labeling/2 for this), sometimes because there’s no way to progress in the computation without “arbitrarily” picking a value (labeling/2 allows various heuristics for picking the best value to instantiate).

1 Like
17

Thanks for the reply. Looks like I’m going to need to read those articles a bit more to get my head around the theory.

I guess it is! I just didn’t think of it that way. Thanks for pointing that out, makes a lot of sense.

Hmm, at the moment that doesn’t really clarify it for me, mainly as there is evidently a lot I need to understand about labelling, constraints and propagation.

Is there a simple way of clarifying what the constraint propagation does vs what the labelling does? I realise this is probably a very big question, but I think this is where I’m failing to grasp the basic ideas.

Thanks again for the help, I really appreciate all the replies.

18

Taking clpfd as an example, from the SWIP manual (https://www.swi-prolog.org/pldoc/man?section=clpfd):

Using CLP(FD) constraints to solve combinatorial tasks typically consists of two phases:

  1. Modeling. In this phase, all relevant constraints are stated.
  2. Search. In this phase, enumeration predicates are used to search for concrete solutions.

Labelling is Step 2. In the process of searching (dividing into sub-problems) it defines new constraints (e.g., place a queen) which triggers constraint propagation.

In addition to reading the referenced articles, I suggest you use the Prolog console to experiment with small examples, e.g.,

% without labelling
?- X #> 2, X #< 8.
X in 3..7.

% label to search for solutions:
?- X #> 2, X #< 8, label([X]).
X = 3 ;
X = 4 ;
X = 5 ;
X = 6 ;
X = 7.