CS 60, Assignment 9

Computer Science 60
Principles of Computer Science
Fall 2003

Assignment 9: All Prolog All The Time: Patterns, Grammars, and Hanoi!
Due Monday, November 3 by 11:59 PM

In this assignment you will explore some of the power of Prolog!

A few things to know about Prolog: First, you can turn the tracer on by typing trace. (The period is necessary.) You can turn off the tracer by typing notrace. (Remember the period!) A file, such as one called myfile.pl is loaded into Prolog by typing ['myfile.pl']. You can leave Prolog by typing halt. Finally, if Prolog is stuck thinking deeply and you want it to stop, push CONTROL-C.

Part 1: Pattern Matching in Prolog (15 Points)

Pattern matching is an important task in many applications such as cryptography and DNA sequencing. We'll encode a pattern as a list of items and we'll search for a pattern in another list called the "target". The rule find(Pattern, Target, Index) takes two lists Pattern and Target and a non-negative integer Index as input. This rule is true if and only if Pattern occurs inside list Target beginning at position Index. For example, here is a Prolog query and response:

      | ?- find([1, 2], [1, 2, 1, 2, 1], 0).
      yes

Notice that pattern [1, 2] occurs in target [1, 2, 1, 2, 1] beginning at position 0 of the target (that is, the very beginning of the target list).

    [1, 2, 1, 2, 1]
     ^
     |
     The pattern [1, 2] appears beginning right here at location 0.
     I'm looking for a 1 followed immediately by a 2 and I find it
     beginning here!

It also occurs again at position 2 of the target.

    [1, 2, 1, 2, 1]
           ^
           |
           The pattern [1, 2] appears beginning right here at location 2.

Thus, here's another Prolog query and response:

      | ?- find([1, 2], [1, 2, 1, 2, 1], 2).        
      yes

In fact, these are the only two occurences as indicated by the following Prolog query and response:

      | ?- find([1, 2], [1, 2, 1, 2, 1], X).   

      X = 0 ;
      X = 2 ;
      no

Write the rules for find. It might be handy to write some helper "functions" to make find easier. Submit your code in a file named part1.pl.

Part 2: Grammars in Prolog (35 Points)

In Assignment 7 you wrote a recursive descent parser in rex for the grammar below, which represents arithmetic expressions with addition and multiplication.

E -> T + E | T
T -> V * T | V
V -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

In this assignment, we won't ask for a parse tree, but we DO want to know if a particular input can be derived by the grammar. In other words, we just want to know if there EXISTS a parse tree for a given string. The neat thing is that we won't tell Prolog how to parse, we'll just tell it what a grammar is and what string we're interested in and ask: "Yo Prolog, can this string be parsed by the given grammar?"

Take a look at the file part2.pl in /cs/cs60/assignments/assignment9. It contains definitions of the grammar's non-terminals (they are called e, t, and v rather than E, T, and V, because Prolog considers anything begining with an uppercase letter to be an unbound variable), the grammar's terminals (digits 0 through 9 and + and *), and the rules of the grammar. In addition, a few helper definitions are given.

Your task is to write the heart of this program, which is a rule called solve. As described in class (on Tuesday, October 28), solve takes as input a sentential form and a list of symbols to parse and says "yes" if and only if the sentential form derives the list of symbols using a leftmost derivation for the grammar.

In particular, we plan to call solve with the sentential form comprising just the start variable and the list of symbols being just the list of symbols to parse. For example, here is some sample input and output:

| ?- solve([e], [1, +, 2, *, 3]).

yes
| ?- solve([e], [1, +]).

no
| ?- solve([e], [1, *, 2, 3]).

no

You should add the solve inference rules to the file part2.pl and submit that file. Keep your code simple and elegant and be sure to test it thoroughly before submitting it. This can be done using fewer than 10 new lines of Prolog code - if you are writing much more than that you are doing too much work!

Part 3: Towers of Hanoi (50 Points)

In this part of the assignment, you will write a Prolog program to solve the Towers of Hanoi puzzle. Please submit your solution in a file called part3.pl. You should carefully review the "fox, hare, and lettuce" solution that we wrote in class before embarking on this program. The big ideas in the two programs are very similar. Fortunately though, the Hanoi program is considerably shorter. (My solution is 20 lines of Prolog code, not including comments and spacing between rules.)

Your solution should specify valid moves in this puzzle and Prolog should use these rules to infer correct solutions to the puzzle. Here are the details:

The disks will be represented by positive integers. There will always be only three pegs but there may be any number of disks. The program must be able to handle an arbitrary number of disks.
A configuration of the puzzle will be represented by a list of three lists. The first list contains the disks (from smallest to largest) on peg 1, the second list contains the disks (from smallest to largest) on peg 2, and the third list contains the disks (from smallest to largest) on peg 3. For example, the list
```
    [ [1, 2], [3, 4], [] ]
  
```
represents disk 1 on top of disk 2 on peg 1, disk 3 on top of disk 4 on peg 2, and nothing on peg 3.
The initial configuration contains all disks on peg 1. For the case of four disks, for example, the initial configuration would be
```
    [ [1, 2, 3, 4], [], [] ]
  
```
The final configuration contains all disks on peg 3. For the case of four disks, for example, the final configuration would be
```
    [ [], [], [1, 2, 3, 4] ]
  
```
The number "12" represents moving the top disk on peg 1 to peg 2. Similarly, the number "13" represents moving the top disk on peg 1 to peg 3. The other possible moves are "21", "23", "31", and "32". You should write a set of Prolog rules called valid which take as input a configuration, the move number, and a new configuration. The rule evaluates to true if and only if it is a valid move to go from the first configuration to the new configuration via that move. For example, consider the following input and output assuming just three disks are being used:
```
    | ?- valid([ [1, 2, 3], [], [] ], 12, [ [2, 3], [1], [] ]).
    yes
  
```
This is valid because we went from the first configuration to the second configuration via move "12". Here's another example:
```
    | ?- valid([ [1, 2], [], [3] ], 12, [ [2], [], [1, 3] ]).
    no
  
```
In this case, it's possible to move from the first configuration to the second configuration, but not by move "12". Here's yet another example:
```
    | ?- valid([ [1 , 2], [], [3] ], 31, [ [3, 1, 2], [], [] ]).
    no
  
```
Although we did move a disk from peg 3 to peg 1 here, this move was invalid because disk 3 cannot be placed on top of disk 1.
Once you've written the six valid move rules, you're almost done! (Write these rules and test them before going on!) Now, you'll write a rule called hanoi which takes as input a configuration and a list of moves. hanoi says "yes" if and only if starting at that configuration and making the sequence of moves described in the list results in getting to the final configuration. Here's an example using three disks:
```
     | ?- hanoi([ [1], [2], [3] ], [23, 13]).
     yes
  
```
The answer here is "yes" because move "23" followed by "13" leaves us in the final configuration. Once this function is written, you can do the following:
```
    | ?- hanoi( [ [1, 2, 3], [], [] ], Solution).
    Solution = [12,13,21,13,12,31,12,31,21,23,12,13,21,13] 
  
```
(Your Prolog program may find a different solution. The solution found depends on the order in which the rules were defined. As long as your Prolog program finds a correct solution, that's fine!)
A few notes on this program:
- You'll need to use dynamic and assert in much the same way that we did in the "fox, hare, and lettuce" problem that we saw in class.
- If you run your hanoi search twice, it might succeed the first time and fail the second time! Why? Recall that as we discussed in class, the asserted facts are still present the second time (that is, the configurations are still marked as visited!). The easiest way to get around this is to exit Prolog, reenter it, and start again.

Last modified October 2003 by Ran Libeskind-Hadas

Computer Science 60 Principles of Computer Science Fall 2003

Assignment 9: All Prolog All The Time: Patterns, Grammars, and Hanoi! Due Monday, November 3 by 11:59 PM

Part 1: Pattern Matching in Prolog (15 Points)

Part 2: Grammars in Prolog (35 Points)

Part 3: Towers of Hanoi (50 Points)

Computer Science 60
Principles of Computer Science
Fall 2003

Assignment 9: All Prolog All The Time: Patterns, Grammars, and Hanoi!
Due Monday, November 3 by 11:59 PM