CPSC3750

! pronounced “cut” is a special goal in prolog which always succeeds. The purpose of cut, loosely speaking, is to freeze some of the choices made by the backtracking sytem so far. Cuts can therefore be used to increase the efficiency (time) of prolog programs. First we will see how the backtracking is affected by the use of cuts. Then we will give an example use of cuts to speed up prolog programs.

We will look at terms (the basic data structure) in prolog. All prolog data and prolog programs are stored as terms. A widely used term type is a list. We will look at several non-deterministic predicates over lists. Using the predicates on lists and their non-deterministic capabilities, we develop a program to do breadth first search (BFS) and a program to solve the n-queens problem. BFS is the basis for many search algorithms in AI such as $A^*$, IDA, $\alpha-\beta.

The starwars way Prolog stands for programming in logic. Prolog programs are specified as relations and rules around the relations defined by programming in logic. The programs can be queried to determine the veracity of facts or to infer new facts using the rules. The specification of the facts and rules will be illustrated using the STAR WARS family tree as per the end of episode 8 at the end of this post (obtained from google images).