CSE 341 -- Programming Languages

Autumn 2003

Department of Computer Science and Engineering, University of Washington

Steve Tanimoto (instructor)

Assignment 3

Version 1.01 of 19 October. (Adjustments since Version 1.0 are shown in [brackets] and apply only to Part II.)

Macros and Machines 

Due date and time: Part I: Monday, October 20, 2003 (hardcopy at the beginning of class); Part II: Wednesday, October 22, at 11:59PM, (web-based turn-in).


 

Title: Macros and Machines.

Purposes: Learning more of Common Lisp's constructs, mastering macros, and gaining familiarity with Turing Machine simulation.

Instructions: Read pages 73-100 in Symbols, Programs, Interaction.
 

Part I (Individual Work)

Do the following exercises: Scoring for this part: 3 points each for parts A, E, and F; 7 points each for parts B, C, and D. Total: 30 points.

 

Part II (Group Work)

Groupings for this assignment have been made by the INFACT group-formation algorithm, using any preference information you have entered in INFACT for who you want to work with. (You'll have another opportunity to express your preferences before the next group assignment.)
Each group should create and turn in one solution to the problem. Create an implementation of a simulator for a Turing Machine that recognizes palindromes over the alphabet {A, D, M}. Your tape alphabet should include these plus the following three additional symbols: {^, $, Blank}.
Unlike some Lisp assignments, in this one you are encouraged to use global variables for certain parts of the program. In particular, use the following symbols for the purposes indicated. Note that the asterisks are part of the symbol names. (It is a common practice to spell the symbol names for global variables this way.) 
*tape*    (Holding a list that represents the Turing Machine's tape)
*current-state*  (Holding a symbol that is the name of the current state)
*head-position* (Holding an integer that indicates which position
                 of the tape is currently being looked at.
                 In this problem, we will assume that we never need
                 to extend the tape to the left of the input area,
                 and so the position will always be 0 or greater.)
You should represent the tape as a list of (Lisp) symbols, each of which represents a symbol from the Turing Machine's tape alphabet. Here are some specific functions to include in your implementation: 
(move new-state tape-head-action output-symbol)
  This should cause (a) the current state to be changed to the value
  of NEW-STATE, (b) the value of OUTPUT-SYMBOL to be written to
  the tape at the current position, unless that value is NO-CHANGE,
  in which case the tape is not changed, and (c) either the head is
  moved LEFT relative to the tape, or RIGHT relative to the tape,
  or the machine halts with a REJECT message or it halts with an
  ACCEPT message.

(palindrome-next) 
  This function should use the current state and the current tape
  symbol to make a move (by calling MOVE).  You may implement this 
  function using nested COND forms.

(run)
  This function should initialize the tape, initialize the current
  state and the head position, and then it should repeatedly call
  PALINDROME-NEXT until either a halt (with accept or reject) is
  performed in the MOVE function, or some limit (let's make it 50)
  number of iterations has been performed.
  After each cycle, your RUN function should show the current state
  of the computation by printing out the current state of the
  Turing Machine, the tape, and where the head is on the tape.
Test your simulator on the example palindrome given in Turing Machine Example 3 in the lecture slides on Turing Completeness. [Do this using your RUN function.] [Prepare] a non-palindrome and show what your Turing Machine simulator does with that, too. [Do this using a second function, RUN2, for setting up and running the Turing Machine. The TM input for this should be ^MAD$.]
Scoring for Part II: This program is worth up to 15 points for each group member. Each member of the group will normally receive the same score. Note that points will be deducted for (a) spelling errors in the names of the required functions, because the automatic grading scripts will not work on misspelled function names, and (b) bad style. Good style involves: indentation of expressions according to improve readability; documentation either with documentation strings, comments or both; avoidance of global variables except to keep track of system state or Turing machine components such as the finite control, tape, tape position, etc. Here is a transcript of a run using GCL of the instructor's solution to the problem.