CSE 341 -- Practice Final

December 5, 1995


110 minutes, open book and notes, 85 points total

Your name:


  1. [2 points per subquestion -- 12 points total] What is the result of evaluating the following Lisp expressions? If there is more than one expression, assume that they are evaluted in order, but just give the result of evaluating the last one. If the expression will give an error when evaluated, say so.
    1. (+ (* 2 3) (+ 8 2))
      
      16

    2. (cadddr '(a b c d e))
      
      D

    3. (first (rest (rest '((a) (b) (c)) )))
      
      (C)

    4. (setf x '(1 2 3))
      (setf y '(4 5 6))
      (let ((x '(a b))
            (y '(x y z)))
         (append x y))
      
      (A B X Y Z)

    5. (mapcar #'(lambda (x) (cons x nil)) '(a b c))
      
      ((A) (B) (C))

    6. (setf x '(1 2 3))
      (setf y '(4 5 6))
      (let ((x '(a b))
            (y x))
         (append x y))
      
      (A B 1 2 3)

  2. [5 points per subquestion -- 15 points total] For this question you will need to write a similar function/method/rule in each of Lisp, Smalltalk, and Prolog.
    1. Write a Lisp function square that takes a list and returns a new list with each element squared. Here are some examples of using twice:
      (square '(1 2 3))    evaluates to    (1 4 9)
      (twice '())    evaluates to    NIL
      (twice '(4 3 1 2))   evaluates to   (16 9 1 4)
      

      You don't need to worry about an argument that isn't a list of integers.

      (defun  (s)
        (if (null s) nil 
            (cons (* (first s) (first s)) (twice (rest s)))))
      

    2. The class OrderedCollection in Smalltalk is an ordered collection of objects. Evaluating OrderedCollection new will make a new, empty instance of OrderedCollection. If c is an instance of OrderedCollection, evaluating c add: x will add an element x at the end of c. Write a square method for OrderedCollection that returns a new ordered collection with each element squared. For example, if c contains 1, 2, and 3, then c twice should return a new ordered collection consisting of 1,4,9. You can assume the collection contains only members which respond to the * operator.
      square
           | c |
         c := OrderedCollection new.
         self do: [:element | c add: (element * element)].
         ^ c
      

    3. Write a square rule in Prolog.
      square([],[]).
      square([X|Xs],[Sq|Ys]) :- Sq is X*X, square(Xs,Ys).
      

  3. [10 points] Suppose we have classes A, B, and C in Smalltalk. B is a subclass of A, and C is a subclass of B. Each contains a method m1, and another method m2, as follows: class A m1 Transcript show: 'm1 here in class A'. self m2. m2 Transcript show: 'm2 here in class A'. class B m1 Transcript show: 'm1 here in class B'. super m1. m2 Transcript show: 'm2 here in class B'. class C m1 Transcript show: 'm1 here in class C'. super m1. m2 Transcript show: 'm2 here in class C' What happens when you send the m1 message to an instance of A? To an instance of B? To an instance of C?

    When we send the message m1 to an instance of A,

    m1 here in class A
    m2 here in class A
    
    is printed. (Well, actually, they would be run together on the same line, since there isn't a carriage return, but I don't care whether you put that in your answer.)

    When we send the message m1 to an instance of B,

    m1 here in class B
    m1 here in class A
    m2 here in class B
    
    is printed.

    When we send the message m1 to an instance of C,

    m1 here in class C
    m1 here in class B
    m1 here in class A
    m2 here in class C
    
    is printed.

  4. [10 points] Suppose that you are writing a simulation in Smalltalk of the PC's in the PC Lab in Sieg 232. You have defined the following classes: (You would need other classes for a complete simulation, e.g. for the main memory, Ethernet board, keyboard, etc., but the above list is enough for this question.)
    1. Draw a diagram of a sensibly organized subclass hierarchy, starting with class Object, that includes all of the classes in the list.

      Object
         ElectronicDevice
            Computer
            DiskDrive
               HardDiskDrive
               FloppyDiskDrive
            CPU
               Pentium
            Monitor
      
      In other words, Computer and DiskDrive are both subclasses of ElectronicDevice, etc. Note in particular that for example DiskDrive is NOT a subclass of Computer -- a disk drive is a part of a computer, but a disk drive is not a kind of computer.

    2. The part-whole relation is usually represented in Smalltalk and other object-oriented language by making an instance (representing the whole) that includes instance variables that refer to the parts. What should the part-whole relations be among instances of the classes in the list? (Hint: if this question were about pinball games, part of your answer might be "An instance of PinBallGame has instance variables ball (an instance of Ball), and leftFlipper and rightFlipper (instances of Flipper).")

      An instance of Computer should have instance variables hardDisk, floppy, cpu, and monitor, which are instances of HardDiskDrive, FloppyDiskDrive, CPU, and Monitor respectively. In other words, a computer has as its parts a hard disk drive, a floppy disk drive, a CPU, and a monitor (plus some other stuff which wasn't listed in this question and so doesn't need to be part of your answer).

  5. [10 points] Suppose the standard Prolog definitions of append and member have been read in:
    
    append([],Ys,Ys).
    append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).
    
    member(X,[X|Xs]).
    member(X,[Y|Ys]) :- member(X,Ys).
    
    What answers are produced for the following goals? If there is more than one, give all of the answers. If at some point Prolog gets into an infinite search, say so.
    1. ?- member(A,[1,2,3]).
      
      A = 1 ;
      A = 2 ;
      A = 3 ;
      no
      

    2. ?- append(A,[B],[1,2,3]).
      
      A = [1,2], B = 3 ;
      no
      

    3. ?- member(A,[1,2,3,4]), member(A,[2,3,4,5,6]).
      
      A = 2 ;
      A = 3 ;
      A = 4 ;
      no
      

    4. ?- member(4,A), append(A,B,[1,2,3,4,5]).
      
      A = [1,2,3,4], B = [5] ;
      A = [1,2,3,4,5], B = [] ;
      
      [Prolog goes into an infinite search at this point]
      

    5. ?- append(A,B,[1,2,3,4,5]), member(4,A).
      
      A = [1,2,3,4], B = [5] ;
      A = [1,2,3,4,5], B = [] ;
      no
      

  6. [10 points] Suppose the definition of 'not' in Prolog given in the lecture notes has been read in, and also the standard definition of append.
    not(X) :- call(X), !, fail.
    not(X).
    
    append([],Ys,Ys).
    append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).
    
    
    What answers are produced for the following goals? If there is more than one, give all of the answers. If at some point Prolog gets into an infinite search, say so.
    1. ?- not(X=Y), X=3, Y=4.
      
      no
      
      

    2. ?- X=3, not(X=Y), Y=4.
      
      no
      

    3. ?- X=3, Y=4, not(X=Y).
      
      X = 3, Y = 4 ;
      no
      

    4. ?- append(X,Y,[1,2,1,2]), not(X=Y).
      
      X = [], Y = [1,2,1,2] ;
      X = [1], Y = [2,1,2] ;
      X = [1,2,1], Y = [2] ;
      X = [1,2,1,2], Y = [] ;
      no
      

    5. ?- not(append([1,2],[3,4,5],[1,2,3,4,5])).
      
      no
      

  7. [8 points] Consider the difference list version of the list flatten program given in the lecture notes:
    flatten(S,F) :-
      flatten_dl(S,F\[]).
    
    flatten_dl([],X\X).
    
    flatten_dl([X|Xs],Y\Z) :-
       flatten_dl(X,Y\T),
       flatten_dl(Xs,T\Z).
    
    flatten_dl(X,[X|Z]\Z).
    
    Suppose that one replaced the base case of the recursion with
    flatten_dl([],[]\[]).
    
    Indicate which of the following statements are true and which are false.

    In the answers I put in explanations -- you don't need these though in your answers.

    1. Since []\[] is a correct difference list representation of the empty list, the new program will continue to work correctly in all cases, but sometimes less efficiently.

      False. (It will fail in all cases except flattening an empty list.)

    2. Even though []\[] is not a correct difference list representation of the empty list, the new program will still work correctly on some cases.

      False. []\[] IS a correct difference list representation of the empty list.

    3. The new program will work correctly on all cases.

      False (see above).

    4. The new program will fail on all cases.

      False (see above).

    5. The new program will work on some cases but not all.

      True (see above).

    6. The term []\[] is a correct difference list representation of the empty list. However, the program's operation depends on flatten_dl leaving a variable at the end of the flattened list, so the new program won't always work correctly.

      True

    7. The new program includes a rule that is logically incorrect.

      False. All the rules are logically correct -- the new rule for the base case isn't general enough though.

    8. All the rules in the new program are logically correct, but the rules aren't general enough. Thus, given Prolog's closed world assumption, the new program will fail to flatten some lists.

      True (see above).

  8. [10 points] Consider the following two sequences of Lisp code. In each case say what value is returned when the final expression (clam 7) is evaluated. Explain your reasoning.

    Here is the first sequence:

    (setf x 4)
    (setf y 3)
    
    (defun clam (x)
       (squid))
    
    (defun squid ()
       (+ x 100))
    
    (clam 7)
    
    In this case 104 is returned. We evaluate (clam 7). This calls the clam function, binding x to 7 within the body of clam. In clam we call squid. The squid function evaluates (+ x 100). The variable x is not local to squid. Since it is lexically scoped, we find the global binding of x, which is 4, and return 104. Then 104 is returned from clam as well.

    Here is the second sequence -- the only difference from the first is that x and y are declared as dynamically scoped variables.

    (defvar x 4)
    (defvar y 3)
    
    (defun clam (x)
       (squid))
    
    (defun squid ()
       (+ x 100))
    
    (clam 7)
    
    In this case 107 is returned. We evaluate (clam 7). This calls the clam function, binding x to 7 within the body of clam. In clam we call squid. The squid function evaluates (+ x 100). The variable x is not local to squid. In this case, it is dynamically scoped. So we look up the calling stack, and find the binding in clam, which is 7, and return 107. Then 107 is returned from clam as well.