Name: _________________________________________________________

Directions

Work alone. You may not discuss these problems or anything else related to this course with anyone except for the course staff between receiving this exam and class Monday.

Open book. You may use any books you want, lecture notes and slides, your notes, and problem sets. If you use anything other than the course books and notes, cite what you used.

Open computer. You may use a computer and any programming languages and environments you want for this exam. You are not required to use a computer (other than your own brain if you think it is one) to do well on this exam.

Answer well. Answer all 10 questions. Write your answers on this exam. You should not need more space than is provided to write good answers, but if you want more space you may attach extra sheets. If you do, make sure the answers are clearly marked.

The questions are not necessarily in order of increasing difficulty, so if you get stuck on one question you should continue on to the next question. There is no time limit on this exam, but it should not take more than a few hours to complete.

Full credit depends on the clarity and elegance of your answer, not just correctness. Your answers should be as short and simple as possible, but not simpler.

Objects and Environments

1. For Problem Set 6, Question 4, two common answers were given:

Answer A:

(define (make-professor name)
  (let ((super (make-lecturer name)))
    (lambda (message)
      (if (eq? message 'profess)
	    (lambda (self message)
	          (ask self 'say (list "It is intuitively obvious that"))
		  (ask self 'lecture message))
	      (get-method super message)))))

Answer B:

(define (make-professor name)
  (let ((super (make-lecturer name)))
    (lambda (message)
      (if (eq? message 'profess)
	    (lambda (self message)
	          (ask self 'say (list "It is intuitively obvious that"))
		  (ask self 'say message)
		  (ask self 'say (list "you should be taking notes")))
	    (get-method super message)))))

Note: The original question had stuff instead of message in (ask self 'say message). This was an unintended mistake.

(define (make-object name)
  (lambda (message)
    (case message
      ((class) (lambda (self) 'object))
      ((name) (lambda (self) name))
      (else no-method))))

(define (make-physical-object name)
  (let ((super (make-object name))
	(location null-place)) ; location set when we install
    (lambda (message) ; Normal actions
      (case message
	((class) (lambda (self) 'physical-object))
	((location) (lambda (self) location))
	(else (get-method super message))))))

(define (make-mobile-object name)
  (let ((super (make-physical-object name)))
    (lambda (message)
      (case message
	((class) (lambda (self) 'mobile-object))
	(else (get-method super message))))))

(define (make-person name)
  (let ((super (make-mobile-object name))
        (possessions '())  
	(restlessness 0.0))
    (lambda (message)
      (case message
	((class) (lambda (self) 'person))
	(else (get-method super message))))))

(define mystery

3. How many frames would be created when (make-mobile-object "bike") is evaluated? (Explain why each frame is generated. Recall that let is syntactic sugar for ((lambda (...) )).)

Computability

Input: A description of a Turing Machine and input tape.

Output: If executing the Turing Machine on the given input would ever repeat a machine configuration (the state of the finite state machine and the contents of the tape), output true. Otherwise, output false. That is, the output should be true if and only if executing the Turing Machine on the given input would encounter the same exact machine configuration more than once.

Input: A description of a Turing Machine and input tape.

Output: If executing the Turing Machine on the given input would ever repeat a finite state machine state, output true. Otherwise, output false. That is, the output should be true if and only if executing the Turing Machine on the given input would enter the same finite state machine state more than once.

Building Web Communities

    $result = executeQuery ("SELECT id FROM users");
    for ($i = 0; $i < mysql_num_rows ($result); $i++) {
        for ($j = 0; $j < mysql_num_rows ($result); $j++) {
           if ($i != $j) {
               $exists = executeQuery ("SELECT fromid FROM acquaints 
                                        WHERE fromid='$i' AND toid='$j'");
               if (mysql_num_rows ($exists) == 0) {
                 executeQuery ("INSERT INTO acquaints (fromid, toid)
                                VALUES ('$i', '$j')");
	       } } } }

She conducts experiments with communities containing 100 and 200 members and obtains these measurements:

Estimate how big a community Alyssa's new implementation can support. (As in PS7, assume that the only constraint on community size is that the mamximum query response time cannot exceed 60 seconds. State clearly any additional assumptions you need to make.)

Lambda Calculus