6.001 Spring 98 -- Microquizzes

		      Microquiz for May 1, 1998


1) Write a simple register machine controller that reads a sequence of
integers, stopping when it reads a negative number, and returns the
maxiumum number seen in the sequence.



2) What are the contracts for EV-DISPATCH and APPLY-DISPATCH in the
explicit control evaluator (the register machine implementation of our
evaluator).

		   MASSACHVSETTS INSTITVTE OF TECHNOLOGY
	 Department of Electrical Engineering and Computer Science
	 6.001 -- Structure and Interpretation of Computer Programs

			 Microquiz -- 17 April 1998



    1.  State the Halting Theorem.



    2. In Java, a class may have at most one superclass.  But it has a
    mechanism that provides some of the power of multiple
    superclasses.  what is this mechansism called?



    3. In the textbook's discussion of the evaluator, what is meant by
    a "derived expression"?

		   MASSACHVSETTS INSTITVTE OF TECHNOLOGY
	 Department of Electrical Engineering and Computer Science
	 6.001 -- Structure and Interpretation of Computer Programs

			 Microquiz -- 10 April 1998



   1. On Tuesday, Sussman talked about "Amorphous Computing".
   Previously, Miller showed examples of the kind of concurrency that
   occurs in systems like banking.  The most important difference between
   the banking-type systems and the biological-type systems is:



   2.  The basic EVAL-APPLY cycle is as follows:



	EVAL takes a ____________ and a ____________.


	  EVAL transforms these into a ____________ and a ____________, 
	  which it passes to APPLY.


	APPLY takes a ____________ and a ____________.


	  APPLY transforms these into a ____________ and a ____________,
	  which it passes to EVAL.



   3.  The mystical formula "(Y F) = (F (Y F))" describes:

       a. A way to protect computers from evil spells.

       b. That the "Y" operator yields a fixed point of its argument.

       c. A way to interlock side effects on shared state in a concurrent
	  system. 

       d. A clever recipe for Church's Curry.

			   6.001 Microquiz
			Date:  Friday, April 3


Note: The questions on this quiz are somewhat more difficult than on
previous Microquizzes.  We're putting them here to illustrate the
level of difficulty you ought to expect on Quiz 2.

	       ****************************************

The following procedure returns a list of all the
distinct elements in a given list.  That is, each element
appears only once in the result list, no matter how many times it
appeared in the argument list.

(define (remove-duplicates list)
  (cond ((null? lst) '())
        ((null? (member (car list) (cdr list)))
         (cons (car list)
               (remove-duplicates (cdr list))))
        (else (remove-duplicates (cdr list)))))

1. Write the analogous procedure that removes duplicates from a stream.

2. Given a stream S and an element x, show how to use stream-filter to
remove all occurrences of x from S.


3. Using the idea of (2), write an alternative procedure to remove
duplicates from a stream.

4. Compare (2) vs. (3) as methods for removing duplicates from a
stream. Hint: Think about infinite streams.

5.  Give all possible values of x that can result from executing

(define x 10)
(parallel-execute (lambda () (set! x (* x x)))
                  (lambda () (set! x (* x x x))))

Which of these possibilities remain if we instead use serialized procedures:

(define x 10)
(define s (make-serializer))
(parallel-execute (s (lambda () (set! x (* x x))))
                  (s (lambda () (set! x (* x x x)))))

			   6.001 Microquiz #7
		     Date:  Friday 20 March 1998



Suppose we want to have a procedure that behaves as a counter

(c) --> 0
(c) --> 1

together with a procedure reset that resets the counter to 0:

(c) --> 2
(reset) --> OK
(c) --> 0
(c) --> 1
....

The idea is that c and reset should share some local state, but that
no other procedures should be able to access this state.  Draw an
environment diagram that illustrates this situation.  (Assume the
local state variable is called count.)





Now show how to define the procedures c and reset.

			   6.001 Microquiz
		     Date:  Friday 13 March 1998


_______________________________
Name   (section number)

THIS IS A CLOSED BOOK QUIZ, NO NOTES ALLOWED.  IT SHOULD TAKE NO MORE THAN
5 MINUTES TO COMPLETE.

1.  Write a procedure, PREVIOUS?, of one argument that returns #F the
first time it is called and then returns #T if it is called with the
same argument it was called with the last time.  The procedure must be
self-contained (i.e. no global variables allowed).  For example:

==> (define previous? ...)
==> (previous? 3)  => #F
==> (previous? 4)  => #F
==> (previous? 4)  => #T




2,   Draw a box-and-pointer diagram to explain the following behavior:

(define x '(a b c))
(set-cdr! x x)
(car x)    => A
(length x) => infinite loop



3. For each of the following, say whether it best describes patents or
copyrights:

- they primarily protect originality, not novelty

- they protect processes but not mathematical algorithms

- They restrict other people from using things, even if the other
  people came up with the same things completely independently.

		 6.001 Not-so-micro-quiz, Friday March 6

Here is a sample of the range and kinds of problems to anticipate on
next week's quiz (although most of the actual quiz problems will
concern the handout, while the problems here do not).

1. Draw the box-and-pointer structure that results from evaluating
each of the following expressions, and say how the result would be
printed by the Lisp interpreter

     a.   (cons '(a b c) '(d e))

     b.   (list '(a b c) '(d e))

     c.   (append '(a b c) '(d e))



2. We said in lecture that procedures in Scheme have "first-class
citizenship".  What does that mean?



3.  Write a procedure fringe that "flattens" a tree into a list of its
atoms, e.g.,

(fringe '((a b (3)) ((d e))))  --->   (a b 3 d e)



4. Define a procedure REVERSE that takes a list as argument and
returns a list of the same elements in reverse order:

(reverse (list 1 4 9 16 25))  ---> (25 16 9 4 1)

Your procedure should generate an iterative process.  In terms of the
length of the list, what is the order of growth in time (number of
steps) and space (number of deferred operations) for the process
generated by this procedure?



5.  The basic fact that makes Diffie-Hellman key agreement a powerful

technique is that ________________________________________ can be computed

much faster than ___________________________________________




6. Write a procedure CENSOR that, given a symbol and a list, returns
the list with all occurrences of the symbol replaced by the symbol **,
e.g.

(censor 'MIT '(MIT dear MIT my heart belongs (to MIT)))

;Value: (** dear ** my heart belongs (to MIT))


7.  Write a procedure deep-censor that is similar to censor, but which
replaces the given symbol at any level of a tree, e.g.,

(deep-censor 'MIT 
             '((MIT) (dear MIT) my (heart) (belongs (to MIT))))

;Value: ((**) (dear **) my (heart) (belongs (to **)))


8. Let F and G be two one-argument functions.  The composition
F after G is defined to be the function x --> f(g(x)).
Define a procedure COMPOSE that implements composition.  For
example, if INC is a procedure that adds 1 to its argument,

((compose square inc) 6)
;Value: 49


9. Louis Reasoner had a great deal of difficulty doing problem set 2.
His code ran very slowly, even with small primes, and he never was
able to encrypt anything when the primes were large.
Louis called his
friend Eva Lu Ator over to help.  When they examined Louis's code, they
find that he has rewritten the EXPMOD procedure to use an
explicit multiplication, rather than calling SQUARE:

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (* (expmod base (/ exp 2) m)
                       (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))
"I don't see what difference that could make," says Louis.  "I
do."  says Eva.  "By writing the procedure like that, you have
transformed the Theta(log n) process into a Theta(n) process."
Explain.

6.001 Microquiz, Friday February 27


1. Using MAP, FILTER, and/or ACCUMULATE write

   a) LENGTH, a procedure that takes a list as input and returns the number
of elements in the list

   b) MAX-TREE, a procedure that takes as input a list of lists (i.e. a
tree) of numbers and returns the largest number



2. What are the values of the following expressions:

   a) (eq? 'A 'A)


   b) (eq? 'a (car '(a b)))


   c) (cdr (list 'a 'b 'c))


   d) (cons '(1 2) '(3 4))



3. State three reasons that the designers of PICS cite for their argument
that it supports "controls without censorship."  Do you agree or disagree?

			  6.001 MicroQuiz #3


Date: 20 Feburary 1998

Name:___________________________________
			       (Section)




1. In the space provided below, write a simple procedure that returns
the sum of a list of numbers.





2. In the space provided below, write a simple procedure that returns
the sum of all the numerical leaf nodes of a tree of CONS pairs.



3. Which of the folowing is true?  Circle the correct answer.

     That the Solar System is chaotic means:

     A. The planets will fly off or fall into the Sun someday.

     B. Any method we use to predict future planetary 
	positions will accrue too much error to be useful 
        if we try to predict too far into the future.

     C. Spacetime in the vicinity of the Sun has a fractal 
	nature at the Planck scale.

     D. Elvis has been seen wiggling his hips behind the Moon.

6.001 Microquiz, Friday February 13


1. The basic reason that Diffie-Hellman key exchange works is that
 can be computed vastly more quickly than .  (Fill in
the blanks:


blank1:


blank2:


2. What is the value of the expression

    (((bop-funs +) square cube) 2)

if we defined BOP-FUNS, SQUARE, and CUBE as follows?

    (define bop-funs
      (lambda (bop)
        (lambda (f g)
          (lambda (x)
            (bop (f x) (g x))))))

    (define (square x) (* x x))

    (define (cube x) (* x x x))

(Hint: Use the substitution model)


3.  Here is a procedure that computes the sum of the values of a
function over an interval:


(define (sum f a b)
  (if (> a b)
      0
      (+ (f a)
         (sum f (+ a 1) b))))


(a) Does this procedure generate a recursive process or an interative
process?


(b) Write a different implementation of SUM that generates the other
kind of process (do it on the reverse side of this sheet).

6.001 Microquiz, Friday February 6


1. List the four kinds of Scheme expressions.



2. Write a Scheme procedure, named TRIPLE-ABS, that takes one number as
input and returns as its value three times the absolute value of the input.
 You may use any of Scheme's constants and special forms, plus the
primitive operations named +, -, *, /, >, <, =, <=, >=, zero?, positive?,
negative?



3. What is the value of the expression (or does it produce an error):
   (+ ((LAMBDA (x y) (if (> x y) x y)) 10 12) 7)



4. To find the value of a COMBINATION,
   a. first find the values of ....
   b. then APPLY the value of the ... to the ...



5. Describe in English the value of the following expression (use fewer than
30 words):
   (LAMBDA (x y) (+ (* x x) (* y y)))