Prolog 3 - Effective Prolog

• Generate and test
• Switch between declaratative and procedural thinking
• Picking with select
• Debugging with writeln
• Use is to Evaluate Arithmetic
• Avoid infinite searches
• Pick a good data representation
• Know the standard library

Generate and Test

• With some predicates, all variables are “in or out”

  append(X, Y, [john, mary, pat]).

• With others, only some of the variables can be used for output.

  factorial(3, X) => X = 6
  factorial(X, 6) => fail

• Generate-and-test idiom: Generate a list of candidate solutions, then plug in and collect the answers

  solvefac(N,M) :- numlist(1, M, L), member(N, L), factorial(N, M).

• numlist(A, B, L) yields the list of numbers [A, A+1, ..., B]

Declarative and Procedural Thinking

• H :- B1, B2, ..., Bn means “If B1, B2, ..., Bn are true, then H is true”
• That's declarative thinking
• Procedural thinking: To solve H, solve B1, then B2, then ... Bn
• Accurate in Prolog because rules are processed left-to-right
• Procedural thinking works well when each Bi produces outputs that Bi+1 needs

• solvefac(N,M) :- numlist(1, M, L), member(N, L), factorial(N, M).

  • Generate a number between 1 and N
  • Plug it into factorial
• Sometimes—but not always—procedural thinking is easier

Picking with select

• select(X, A, R) picks an element X from A and sets R to the remainder
• Wait, that's procedural thinking. select(X, A, R) is true if X is a member of A and R is the rest, that is,

  select(X, A, R) :- append(U, [X | V], A), append(U, V, R).

• Useful to pick an element from a set and recursively process the remainder.

• perm([], []).
  perm(A, B) :- select(X, A, R), perm(R, S), B = [X | S].

• Sample run:

  perm([1,2,3],X).
  X = [1, 2, 3] ;
  X = [1, 3, 2] ;
  X = [2, 1, 3] ;
  X = [2, 3, 1] ;
  X = [3, 1, 2] ;
  X = [3, 2, 1] ;
  fail

• Can simplify to

  perm(A, [X|Xs]) :- select(X, A, R), perm(R, Xs).

Debugging with writeln

• writeln(X) prints X and succeeds.
• Add it to a rule, and it prints something, usually for debugging purposes, then continues
• Example: My original version of perm was

  perm([], []).
  perm(A, B) :- select(X, A, R), select(X, B, R).

• It yields all permutations, but some twice:

  perm([1,2,3],X).
  X = [1, 2, 3] ;
  X = [2, 1, 3] ;
  X = [2, 3, 1] ;
  X = [2, 1, 3] ;
  X = [1, 2, 3] ;
  X = [1, 3, 2] ;
  X = [3, 1, 2] ;
  X = [1, 3, 2] ;
  X = [1, 2, 3] ;
  fail.

• Use writeln to find out why:

  perm(A, B) :- select(X, A, R), writeln(R), select(X, B, R).

Use is to Evaluate Arithmetic

• By default, arithmetic expressions (and all other expressions) are unevaluated.
• N + 1 is internally represented as add(N, 1).
• Example: Naive implementation of numlist:

  numlist(A, B, []) :- A > B.
  numlist(A, B, [A|Xs]) :- A =< B, numlst(A + 1, B, Xs).

• Doesn't work:

  numlist(1, 10, X).
  X = [1, 1+1, 1+1+1, 1+1+1+1, ...]

• Remedy: Force computation of A + 1 with is

  numlist(A, B, [A|Xs]) :- A =< B, A1 is A + 1, numlist(A1, B, Xs).

Avoid Infinite Searches

• Prolog will search all solutions
• Easy to get stack overflow
• Example: Game of Nim

  It is very easy to check whether T at least one less than F

• My first attempt:

  move(F, T) :- append(T, [o], S), append(S, _, F).

  • Part 1: T is one o less than S
  • Part 2: F is even longer

• It works...kind of

  - move([o,o,o,o,o],Y).
  Y = [] ;
  Y = [o] ;
  Y = [o, o] ;
  Y = [o, o, o] ;
  Y = [o, o, o, o] ;
  Stack overflow

• Part 1 has infinitely many solutions, and they are all attempted.
• Remedy 1: Reorder

  move(F, T) :- append(S, _, F), append(T, [o], S).

• Remedy 2: Think harder

  move(F, T) :- append(T, [o|_], F).

• Note: This is only the first half of move.

Pick a Good Data Representation

• Example: Game is played with a set of 10 dice.
• List of 10 dice? [4, 3, 2, 2, 3, 6, 6, 5, 6, 2]
• Sort by value? [2, 2, 2, 3, 3, 4, 5, 6, 6, 6]
• Use a map, i.e. list of pairs (value, count)? [[1, 0], [2, 3], [3, 2], [4, 1], [5, 1], [6, 3]]
• Use a frequency table? [0, 3, 2, 1, 1, 3]
• Depends on game moves (flipping, taking away dice, etc.)

Know The Standard Library

• Don't spend time coding what is already there
• http://gollem.science.uva.nl/SWI-Prolog/Manual/libpl.html
• Lists: append, select, delete, reverse, flatten, sumlist, max_list, etc.
• Ordered sets: O(n) member, intersection, union, subtract
• Associations: maps
• Accumulate results: findall, bagof, setof
• ?X: either input or output, +X: input only, -X: output only

Lab

• Check into eCampus in the usual way
• Scribe puts in report
• Buddy puts in comment with scribe's name

Step 1: The Thirty-One Game

1. Consider the following game:

   The Thirty-one Game. (Geoffrey Mott-Smith (1954)) From a deck of cards, take the Ace, 2, 3, 4, 5, and 6 of each suit. These 24 cards are laid out face up on a table. The players alternate turning over cards and the sum of the turned over cards is computed as play progresses. Each Ace counts as one. The player who first makes the sum go above 31 loses.

   Describe three different representation for the game state.

Step 2: Computing the State Value

1. We will use the following representation of the game state: A list of six integers between 0 and 3, indicating the number of aces, twos, threes, etc. that have been turned over. At the beginning, the game state is [0,0,0,0,0,0]. After an ace and two threes are flipped over, the state is [1,0,2,0,0,0].

   We need to compute the value of a game state. If it is over 31, that state is losing.

   In Java, this would simply be

   for (int i = 0; i < state.length; i++) value += (i + 1) * state[i];

   But in Prolog, we don't have loops, so we need to have a recursive helper.

   value(L, N) :- value(L, 1, N).

   (You can overload a function name if it has different arity.) Implement the helper function:

   value([], _, 0).
   value([X|Xs], S, N) :- P is X * S, ..., ..., N is + P + ...

   What is your implementation?

2. How do you compute the value of [1,0,2,0,0,0]?

Step 3: Computing Possible Flips

1. When you flip a card, the number of turned card increases, but it can be at most 4. The legal flips are

   flip(0, 1).
   flip(1, 2).
   flip(2, 3).
   flip(3, 4).

   Now we want to express game state changes that involve legal flips, from [A X B] to [A Y B], where A and B are sublists and flip(X, Y) is true. Of course, that is sloppy notation which won't work in Prolog. How do you write that F is a list that starts with a list A, then has a single element X and is followed by a list B? (You need to use append.)

2. Now implement flipmove(F, T), to indicate that it is possible to change the state F to the state T by flipping.

   flipmove(F, T) :- append(...), flip(X, Y), append(...).

3. What are all possible moves from the state [0, 1, 2, 3, 0, 0]?

Step 4: Winning the Game

1. As with the Nim game in the last lab, we want move(F, T) to indicate that it is legal to move from F to T, that is, the move is possible, and the resulting value is < 32. What is your definition of move(F, T)?
2. What are all legal moves from the state [3, 2, 3, 3, 0, 0]?
3. As before, we define

   win(X) :- move(X,Y), not(win(Y)).

   What happens when you run

   win([0,0,0,0,0,0]).

   You may have to wait a while for the answer.

4. Ok, that is nice. But what move should you make? Write a predicate next(X, Y) indicating that it is legal to move from X to Y, and Y doesn't make the other player win. (It is really easy.)
5. What is the next move you should make when you start with the initial position [0,0,0,0,0,0]?
6. Play with your buddy. You get to use Prolog, and your buddy has to figure out moves by hand. That's not fair. You get to start. That's really not fair. Record how you trounce your buddy.