General Prolog Concept Questions

General
1

Hi, I am studying for a Final in my programming class. Two of the things we have to be familiar regarding Prolog are:

  • State-space problem solving
  • Backtracking, derivation trees

I tried Googling these things, but the information is lacking. I have posted my position of each of these below. Is anyone able to add to/correct my understanding?

State-space problem solving involved a beginning state, a goal state, and however many states between.

Backtracking derivation trees will try to find the first legal “route” or option to solve the problem. If a condition is true, it will continue to the next condition. If it is false, it will try another condition.

Are these correct understandings to some extent? If I were to ask you what each meant, what would you say?

2

At a high level, this seems about right. However, backtracking can use more complex strategies, such as breadth-first or iterative deepening. Also, there are many ways of organizing a state space.

Prolog’s default strategy is to traverse the state space with depth-first backtracking. SWI-Prolog recently added tabling, which can sometimes avoid infinite recursions. It also has attributed variables, which can transform generate-and-test into an interleaving of testing and generating. And if none of these work for you, it’s not difficult to program other strategies in Prolog (most textbooks show a variety of these).