Project V

Due Date: Friday December 5th, noon

In this project you will write small programs in Scheme and in Prolog to familiarize you with the functional and logic programming paradigms.

Please note that this project has two parts.

Scheme

Dominoes are small rectangular game tiles with dots embossed at both ends. They are used to play a variety of games involving patterns on a tabletop. A standard “double-six” domino set has 28 tiles: one for each possible pair of values from (0.0) to (6.6). In general, a “double-N” domino set would consist of (N+1)(N+2)/2 tiles.

One possible pattern to make with dominos is a loop, in which the tiles are laid in a circle, end-to-end, with identical numbers of spots on all adjacent ends. In a double-two domino set, with six tiles, ((0 . 0) (0 . 1) (1 . 1) (1 . 2) (2 . 2) (2 . 0)) is a domino loop.

You are to write a program in Scheme that prints all domino loops in a double-N domino set. Specifically, you are to flesh out the following program:

    (define domino-loops (lambda (n)
       (filter loop? (permutations (dominoes n)))))

    (define filter (lambda (f L)
      ; return list of those elements in L which pass through filter f
      (if (null? L) L
        (let ((N (f (car L))))
          (if (null? N) (filter f (cdr L))
            (cons N (filter f (cdr L))))))))
The expression (domino-loops 2) would evaluate to
(((2 . 2) (2 . 1) (1 . 1) (1 . 0) (0 . 0) (0 . 2))
 ((2 . 2) (2 . 0) (0 . 0) (0 . 1) (1 . 1) (1 . 2))
 ((2 . 1) (1 . 1) (1 . 0) (0 . 0) (0 . 2) (2 . 2))
 ((2 . 0) (0 . 0) (0 . 1) (1 . 1) (1 . 2) (2 . 2))
 ((1 . 2) (2 . 2) (2 . 0) (0 . 0) (0 . 1) (1 . 1))
 ((1 . 1) (1 . 2) (2 . 2) (2 . 0) (0 . 0) (0 . 1))
 ((1 . 1) (1 . 0) (0 . 0) (0 . 2) (2 . 2) (2 . 1))
 ((1 . 0) (0 . 0) (0 . 2) (2 . 2) (2 . 1) (1 . 1))
 ((0 . 2) (2 . 2) (2 . 1) (1 . 1) (1 . 0) (0 . 0))
 ((0 . 1) (1 . 1) (1 . 2) (2 . 2) (2 . 0) (0 . 0))
 ((0 . 0) (0 . 2) (2 . 2) (2 . 1) (1 . 1) (1 . 0))
 ((0 . 0) (0 . 1) (1 . 1) (1 . 2) (2 . 2) (2 . 0)))
(NB: order in this list doesn't matter. If your code prints the loops in a different order that's fine.) For larger values of N, where N is even, the number of loops grows exponentially. Note, however, that there are no domino loops when N is odd. (Proof left as an extra-credit exercise.)

There are many possible ways to write your program. Perhaps the simplest (but not the fastest) is to generate all permutations of a list of the tiles in the domino set, and check to see which are loops. You are required to adopt this approach, as described in more detail below. You are encouraged, for extra credit, to find a more efficient solution. Note that the number of permutations of a double-N domino set is ((N+1)(N+2)/2)!. For N=6 (the standard number), this is about 3.05x1029. Clearly you can't afford to construct a data structure of that size. My own (slow) solution to the assignment generates the double-2 loops quite quickly. It takes a couple minutes to determine that there are no double-3 loops. When asked for double-4 loops it thrashes. (For what it's worth, my version of dominoes is 10 lines long; permutations is 17 lines long; loop? is 16 lines long. More elegant versions may be possible. Your mileage may also vary depending on algorithm and on coding and indentation style.)

Required (slow) solution

You must begin with the code shown above. We will test the three sub-functions individually, giving partial credit for the ones that work correctly:

Important: you are required to use only the functional features of Scheme; functions with an exclamation point in their names (e.g. set!) and input/output mechanisms other than load and the regular read-eval-print loop are not allowed. (You may find imperative features useful for debugging. That's ok, but get them out of your code before you hand anything in.)

Tools

We will be using the GNU Scheme interpreter, guile. When it starts up, it simply prints a prompt:

    guile>
You can then enter expressions to be evaluated. You will want to keep your code in a file. If you name it dominoes.sc, you can then type
    guile> (load "dominoes.sc")
Guile will respond with (), indicating that load returned an empty list, after which you'll be able to use functions defined in file ``dominoes.sc'' just as if you had defined them from the command line.

Note that guile prints the guile> prompt at the beginning of each line; you just type the parenthesized expression. Also note that you can re-load a modified file as often as you like; you don't have to quit guile and re-start it every time you fix a bug. To exit the interpreter, type control-D at the prompt.

if you type something into guile and it responds with an elipsis (...), that means the expression you entered is incomplete (though correct so far), and guile is waiting for you to enter the rest of it.

If guile falls into an infinite loop, or if you accidentally ask it to do something that's going to take exponential time, you can interrupt it with control-C.

Guile supports command completion and command-line editing, much as you may be used to in the shell. To enable this feature, put the following code in a file named .guile in your home directory:

    ;; -*- scheme -*-
    (cond
     ((equal? (getenv "TERM") "dumb")
      ;;; emacs
      )
     (#t
      (catch
       'misc-error
       (lambda ()
         (use-modules (ice-9 readline))
         (activate-readline))
       (lambda (key . args)
         #t))))
Don't worry if you don't understand how this works; just include it verbatim.

Guile can also be used inside emacs. To enable this, put the following code in the .emacs file in your home directory:

    (setq scheme-program-name "guile")
    (setq xscheme-process-command-line scheme-program-name)
Then type “M-x run-scheme RET” in emacs. For further information see the on-line documentation for Scheme mode in emacs.

For questions on Scheme itself, refer to the Fourth Revised Report on the Programming Language Scheme. Scheme has been standardized at version 5 (see ACM SIGPLAN Notices, Sept. 1998), but our version of guile is still R4.

Extensive resources, including a guile reference manual (which among other things documents the built-in debugger) is available at the guile home page. (Note: the navigation buttons for the reference manual are a little confusing. If clicking on an item doesn't get you what you expect, try the “next” button.)

Extra Credit

Create a fast version of domino-loops that executes in time proportional to the number of loops, not the number of permutations.

Prolog

There is a famous proven conjecture in graph theory that any map divided into countries can be colored with 4 colors such that no two adjacent countries have the same color. We'll call this the "no same colors share a border" rule. We are going to write a Prolog program that produces all such colorings using red, yellow, blue, and green., for the Atlantic Coast (NJ, NY, PA, VA, MD, DE, SC, NC, GA, FL), and New England (MA, NH, VT, ME, RI, CT) regions of the United States.

Generate and Test

A standard paradigm for Prolog programs is called generate and test. This means that we write a Prolog program (i.e., a set of rules) that searches a space of possible solutions, generates a candidate solution, and then tests that this candidate has the right properties to be an acceptable solution of our problem (as we saw in the naive sorting example used in class). The backtracking execution of Prolog allows us to do this in a very simple, but not always efficient, fashion.

Required (slow) solution

You should begin by encoding the adjacency relation among the US states mentioned above. Note that adjacency is a symmetric relation, which means if NJ is adjacent to NY, then NY is adjacent to NJ. You do not need two Prolog facts for each adjacency and should avoid this.

Write a coloring program, which if given a list of states, will return a valid coloring. A coloring is a list of state/color pairs. Use the naive approach of generating a coloring for an entire list of states and then checking that this coloring is valid for all adjacencies. Call this predicate valid_coloring(Statelist, Coloring).

Hints

You may find the use of not and the use of member useful. Our solution has a total of 9 rules (and uses not and member) in addition to the facts. Chapter 11 of the class text should provide a sufficient introduction to the language.

You will want to use the consult and reconsult primitives. Put your program in one file. Read the program into the interpreter using consult. If you change your program, read it again using reconsult (this will over-ride the earlier definitions of your rules).

Sample Session

Here is a prolog session from a solution to the problem. Your solution should behave similarly.

?- valid_coloring([nj,ny,pa,md],C).

C = [(nj,red),(ny,yellow),(pa,blue),(md,red)];

C = [(nj,red),(ny,yellow),(pa,blue),(md,yellow)];

If you continue to hit ; you will see more colorings. Note that due to the inefficiency of the naive algorithm, it make take a very long time to return a valid coloring for all the states encoded. A smart solution, however, should be able to return a valid coloring in reasonable time.

Extra Credit

Write a smarter map coloring program that is more efficient than the naive approach. Here you should only color a state with a color, if you can show none of its neighbors has this color. Call this predicate smart_coloring(Statelist, Coloring).

DUE DATE:

Friday December 5th, noon.

As with the compiler assignments, use the TURN_IN script. Put your write-up in a README.txt or README.pdf file in the directory in which you run the script. Be sure to include a description of any features of your code that the TA might not immediately notice.