How does unification algorithm actually work?

Question

I have this Prolog code:

bar(b).
bar(c).
baz(c).

This query:

bar(X), baz(X).

returns X = c

If I have this program, which is a little bit different:

bar(c).
bar(b).
baz(c).

On the same query

bar(X), baz(X).

why does it return

X = c;
false

The semicolon means there is a choicepoint, and another choice is being tried (which is "bar(b)"). The "false" means that the 2nd choice failed, leaving you with one answer. Can see the choicepoint using e.g. swi-prolog.org/pldoc/man?predicate=gtrace/0 There are many ways to prevent choicepoints, once the program has some discernable logic. — brebs
– brebs, Commented Mar 5, 2022 at 12:43
@brebs In the first example why isn't there another choice tried ? — Alex
– Alex, Commented Mar 5, 2022 at 13:20
Prolog goes through the code in vertical order. In the first example, b was first, but b fails with the baz(X) constraint, so Prolog back-tracked to the 2nd bar choice. There was no 3rd choice for bar, hence no choicepoint. An easy way to remove this choicepoint is to use baz_bar(c), i.e. combine the constraints. — brebs
– brebs, Commented Mar 5, 2022 at 13:29

slago · Accepted Answer · 2022-03-13 03:14:41Z

4

The computation performed by Prolog to answer a query can be represented as a tree. Prolog searches this tree using a depth-first strategy, automatically backtracking when it encounters a failure node (or when the user presses the key ';' to get an alternate answer).

During the search, clauses are used in the order they are declared in the program (from the first to the last).

At the end of the search, Prolog displays false only if the last node visited in the tree is a failure node.

So, to understand why Prolog behaves differently in the two indicated cases, you can compare the search trees that Prolog explores in each of them:

First case:

Second case:

edited Mar 13, 2022 at 3:14

answered Mar 5, 2022 at 13:18

slago

5,5532 gold badges14 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Alex Over a year ago

In the first case is b analized first because the first fact is bar(b), and in the second one is c analized first because the first fact is bar(c) ?

slago Over a year ago

@Alex Yes! But beyond that, the first query ends up displaying an answer (since the last node visited in the first tree is a success node), while the second one ends up displaying false (since the last node visited in the second tree is a failure node).

Collectives™ on Stack Overflow

How does unification algorithm actually work?

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related