Exam #2

CS152 | Fall 2008

Exam Rules

Work the problems in an order that maximizes your score.
You may use any books, notes, files, web sites of your choice, except as noted below.
You may NOT communicate with anyone during the exam.
You may NOT open any programs or web sites that allow communication with someone else. No messenger, chat, email, discussion forum, etc.
I will randomly inspect laptops. If I inspect yours, you need take the hands off the keyboard immediately.

1. [10 points] Write a SL4 function power(a, n) that computes the power aⁿ. Combine with this main function in a program problem1.sl4.

main() {
  print(power(2, 10));
  return 0;
}

Put your answer into a file problem1.sl4

2. [8 points] Describe what you did to run the program in problem 1. (If you didn't solve problem 1, describe how you ran it when you provided a bogus implementation of power such as the one given below.

Put your answer into a file problem2.txt

3. [15 points] Modify the SL4 compiler so that it translates the ^ operator into a call of the power function. (You may assume that the power function is defined in the same program.) For example, the following program should work:

power(a, n) {
  // your answer to problem 1 or just something bogus like
  return a * a * n;
}

main() {
  print(2 ^ 10);
  return 0;
}

For simplicity, give ^ the same precedence as * and /.

Hint: Look for the translation of the Operator objects. When the compiler is ready to generate code, check for a ^ and call

il.append(factory.createInvoke(className, "power", ...))

Submit your modified SL4.scala

4. [12 points] Consider this recursive definition of a Prolog predicate contains that checks whether the list X contains the list Y:

contains(X, Y) :- append(Y, _, X).
contains([_ | X], Y) :- contains(X, Y).

Consider the query contains([s,o,s],[o,o]).

a) Unify the query with the head of the first clause. What substitution do you get? (This is pretty trivial. I am just checking that you know what a substitution is.)

b) Now apply the substitution to the body of the clause. What goal do you get?

c) Why does that goal fail?

d) Unify the query with the head of the second clause. What substitution do you get?

e) Now apply the substitution to the body of the clause. What goal do you get?

f) What happens next in the Prolog interpreter?

Put your answer in a file problem4.txt

5. [10 points] The SOS Game is played as follows: The board consists of a row of n squares, initially empty. Players take turns selecting an empty square and writing either an S or an O in it. The player who first succeeds in completing SOS in consecutive squares wins the game. A player who fills the last square without completing SOS loses.

We will model the board as a list of atoms e (empty), s, and o. Your task is to write a Prolog procedure flipmove(X, Y) that is true when X and Y are lists with identical elements, except that in one position X has an e and Y has an s or o. For example,

flipmove([e, s, o, e, s], X).
X = [s, s, o, e, s] ;
X = [o, s, o, e, s] ;
X = [e, s, o, s, s] ;
X = [e, s, o, o, s] ;
fail.

Put the answer to this and the next problem into a file sos.pl

6. [15 points] Given the predicates defined in problems 4 and 5, define a predicate move(X, Y) for listing the legal moves from position X to position Y. You can only move if you haven't lost already. For a move to be legal,Ymust contain an empty square or SOS. For example,

move([e, s, o, e, s], X).
X = [s, s, o, e, s] ;
X = [o, s, o, e, s] ;
X = [e, s, o, s, s] ;
X = [e, s, o, o, s] ;
fail.

move([e, s, o, s, e], X).
fail.

move([e, s, s, o, o], X).
fail.

move([s, s, s, e, s], X).
X = [s, s, s, o, s] ;
fail.
% Note that [s, s, s, s, s] is not in the result.

Zip the files problem1.sl4, problem2.txt, SL4.scala, problem4.txt, sos.plinto a ex2_lastname_firstname.zip, substituting your own name (duh). Upload to eCampus.