(Message inbox:395)
Reply-To: meyer@theory.lcs.mit.edu
Received: from theory.lcs.mit.edu by life.ai.mit.edu (4.1/AI-4.10) for boning@mtl.mit.edu id AA28610; Tue, 16 May 95 13:03:09 EDT
Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) 
	id AA20025; Tue, 16 May 95 13:03:05 EDT
From: meyer@theory.lcs.mit.edu (Albert R. Meyer)
Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) 
	id AA03107; Tue, 16 May 95 13:01:57 EDT
Date: Tue, 16 May 95 13:01:57 EDT
Message-Id: <199505161701.AA03107@stork.lcs.mit.edu>
To: 6001-teachers@ai.mit.edu
Subject: [adams@martigny.ai.mit.edu: Jeopardy]

DRAFT JEOPARDY FROM ADAMS.  HE PLANS TO SEND A REVISED VERSION SHORTLY.
Regards, A.
----------------------------
Date: Wed, 10 May 95 16:58:10 -0400
From: Stephen Adams <adams@martigny.ai.mit.edu>
To: meyer@martigny.ai.mit.edu, gjs@martigny.ai.mit.edu
Subject: Jeopardy

These are the questions that I made up for the last time I
did this:




			    6.001 Jeopardy
				   
			   8 December 1993
				   



				   
				People
				------

100.  The British Mathematician who gave his name to a kind of
      Universal Machine and a test for Intelligence

	Who is Alan Turing


200.  The logician who invented the lambda calculus

	Who is Alonzo Church


300.  The Stanford Professor, author of the unfinihsed series called
      ``The Art of Computer Programming''

	Who is Donald E Knuth


400.  The American logician who gave his name to a programming language
      and a way of re-organizing procedures.

	Who is Haskell B Curry


500.  The Austrain logician who gave his name to a way of encoding
      arbitrary strings of symbols as integers.

	Kurt G"odel

				   
				Terms
				-----

100.  The part of a conditional that is executed when the condition is
      true.

	What is a "Consequent"


200.  A prcoedure or test that returns a true or false value.

	What is a "Predicate"


300.  A procedure that takes a prcoedure as a parameter or returns a
      procedure as a result.

	What is a "Higher order procedure"


400.  A set of interface procedures used to separate levels in a
      system.

	What is an "Abstraction Barrier"


500.  This property of a combining form means that a result of the
      combining form is a valid input for the combining form.

	What is "Closure"



			      Write It!
			      ---------

100.  A procedure that returns the maximum of its three arguments

	(define (max3 a b c)
	  (define (max2 u v) (if (< u v) u v))
	  (max2 (max2 a b) c))


200.  An iterative procedure to count the number of symbols in a
      list.

	(define (count lst)
	  (define (count-iter lst n)
	    (cond
	      ((null? lst)   n)
	      ((symbol? (car list))  (count-iter (cdr lst) (1+ n)))
	      (else                  (count-iter (cdr lst) n)))))  
	 

300.  A predicate to tell if a list contains two or more copies of an
      element.

        (duplicates? '(1 2 3))   => #f
        (duplicates? '(2 1 3 1)) => #t

        (define (duplicates? lst)
          (cond ((null? lst)  #f)
        	((member (car lst) (cdr lst)) #t)
        	(else (duplicates? (cdr lst)))))


400.  Write a procedure to find the best item in a list, where
      goodness is measured by a procedure, and higer values of
      goodness are better

        (find-best (lambda(x) x)  '(1 7 2 8 3))  => 8

        (define (nearness-to x) (lambda (y) (- (abs (- x y)))))
        (find-best (nearness-to 5)  '(1 7 2 8 3))
               =>

        7 or 3 (both have same goodnesses)

          (define (find-best goodness lst)
            (define (search lst best-so-far)
              (cond ((null? lst)  best-so-far)
	            ((> (goodness (car lst))
	                (goodness best-so-far))
	             (search (cdr lst) (car lst)))
	            (else
	             (search (cdr lst) best-so-far))))
            (search (cdr lst) (car lst)))


500.  Code for environment diagram:

        (define u (lambda (n) (lambda () (set! n 1+ n) n)))

        (define v (u))

   
			       Puzzles
			       -------

100.  ((lambda (x)
        ((lambda (x)
          (+ x 2))
         (* x x)))
       7)                   => 51


200.  (map (lambda (p) (p 5 7))
           (list + - * <))

      => (12 -2 35 #t)

300.  (define (fold op e lst)
        (if (pair? lst)
            (op (car lst)
                (fold op e (cdr lst)))
            e))

      (define (foo a b) (fold cons b a))

       [foo = append]


400.   (define (count-leaves t)
         (if (atom? t)
             1
             (+ (count-leaves (car t))
                (count-leaves (cdr t)))))

       (count-leaves '(1 2 3))  =>  4

       (count-leaves (let ((shared (cons 1 2)))
                       (cons shared shared)))    =>  4

       (count-leaves (let ((s1 (cons 1 2)))
	               (let ((s2 (cons s1 s1)))
		          (cons s2 s2))))        =>  8

500. 
       (((lambda (r)
          (r (lambda (s) (s 1 2))
             (lambda (s) (s 3 4))))
         (lambda (u v) v))
        (lambda (u v) u))

       => 3

				   
				 Misc
				 ----

100.  What is this an example of?

         (define (make-pt x y) (cons x y))
         (define (pt-x p) (car p))
         (define (pt-y p) (cdr p))
         (define (pt-distance p)
           (define (sq x) (* x x))
           (sqrt (+ (sq (car p)) (sq (cdr p)))))

       Abstraction violation - should use accessors (pt-x instead of car etc.)


200.  What answers does this give?

        (let  ((x (amb -3 -2 -1 0 1 2 3)))
          (require (= (* x x) 4))
          x)

      => -2 and 2


300.  What questions should you ask about a new language?

        What are the primitives?
        What are the combining forms?
        What are the means for abstraction?


400.  What is the following expression transformed to?

        (cond ((> a b) (let ((f (- a b))) (* f f)))
              ((< a b) (- b a))
              (else    (* a b)))
      =>
         (if (> a b)
             ((lambda (f) (* f f))
              (- a b))
             (if (< a b)
                 (- b a)
                 (* a b)))


500.  Change the analyize procedure to accept the new derived form PUSH:

         (PUSH <item> <stack>)
      ==
         (set! <stack> (cons <item> <stack>))


Final Jeopardy:
     
          (apply map (cons list '((1 2 3) (4 5 6))))

       =>  ((1 4) (2 5) (3 6))




Rather use (apply map (cons list '((1 2 3) (4 5 6))))


----------------
Date: Wed, 10 May 95 17:00:03 -0400
From: Stephen Adams <adams@martigny.ai.mit.edu>
To: meyer@martigny.ai.mit.edu, gjs@martigny.ai.mit.edu
Subject: Jeopardy II

This is the email I sent out after using the previous
questions.

________________________________________________________________________

There are a couple of things wrong with the Jeopardy handout. These
are fixed below.

----------------------------------------------------------------------
IMPORTANT NOTE
--------------

It appears that I am not the only one who makes mistakes.  There is a
mistake in the Final Quiz handout.  Corrections will be available at
Thursday's lecture.
----------------------------------------------------------------------



 1. The `Write It!' 500 question was this environment diagram:

                                                      
        +-------------------------------------------------------------+
    GE: |                                                             |
        |  u:*                                         v:6            |
        |    |                                                        |
        +----|--------------------------------------------------------+
             | ^                               ^                       
             | |                               |                       
             | |                               |                       
             OO+                         (u 5) |                       
             |                           +------+           
           args: n                       |n:6   |<--+       
           body: (lambda()               +------+   |       
                   (set! n (1+ n))        ^         |((u 5))
                   n)                     |        +-------+
                                   P: OO--+     F: |       |
                                      |            +-------+
                                    args: ()                
                                    body: (set! n (1+ n))   
                                          n                 


    The code in the handout should read:


          (define u
            (lambda (n)
              (lambda ()
                (set! n (1+ n))
                n)))

          (define v ((u 5)))

    The call to (u 5) creates the frame with N in it, initializes N to 5
    and returns the procedure P.  This procedure is in turn applied to
    no arguments (frame F), causeing N to be incremented and returnin
    the new value of N.  This value, 6, is bund to v by the define.



 2. I forgot the code for the `Misc.' 500 question, and the definition
    of the tansformation in the handout is slightly different from the
    one on the overhead slide.

    The question: Change the analyze procedure to accept the new
    derived form PUSH:

	(PUSH <item> <stack>)
     ==
        (set! <stack> (cons <item> <stack>))

    First we create an abstraction for the new derived form:

	(define (push? thing)  (tagged-list? thing 'push))

	(define (push-item  push-exp) (list-ref push-exp 1))
	(define (push-stack push-exp) (list-ref push-exp 2))

    Next we create a transformer procedure:

    	(define (push->set! exp)
           (let ((stack  (push-stack exp))
	         (item   (push-item exp)))
	     `(set! ,stack (cons ,item ,stack))))

    Finally we stitch it into the analyze procedure:

     (define (analyse exp)
       (cond
         ((frotz? exp)  (analyze-frotz exp))
         ((blulp? exp)  (analyze-blulp exp))
	 ...
	 ((push? exp)   (analyze (push->set! exp))
	 ...)))


 3. The final Jeopardy example was very hard, and relied too much on
    the APPLY procedure available in the Scheme initial environment
    which takes a variable number of arguments.

    The variable number of arguments APPLY behaves like this

          (apply map list '((1 2 3)
                            (4 5 6)))
      =>  (apply map (cons list '((1 2 3)
                                  (4 5 6))))

    Now you can reason about the two-argument apply that you know and
    love :-)

       => (map list '(1 2 3) '(4 5 6))
       => (list (list 1 4) (list 2 5) (list 3 6))
       => ((1 4)
           (2 5)
           (3 6))

    If we wanted to represent a matrix as a list of rows we could use
    this trick to implement TRANSPOSE:

   	(define (transpose m) (apply map list m))


 4. There was a great variety of opinion on the answer to `Puzzles'
    400.  Remember that atom? can be defined as

	(define (atom? thing) (not (pair? thing)))

    so the end of list marker '() is an atom.  To figure out the rest
    you could use a box and pointer diagram.  Sharing causes things to
    be counted twice.


 5. In `Write It' 200 I forgot to call count-iter, so, baring the odd
    parenthesis, the correct solution has a extra line:

	(define (count lst)
	  (define (count-iter lst n)
	    (cond
	      ((null? lst)   n)
	      ((symbol? (car list))  (count-iter (cdr lst) (1+ n)))
	      (else                  (count-iter (cdr lst) n))))
	  (count-iter lst 0))
