CSC 8310 -- Final Exam
Section 001: Tuesday & Thursday 4:30 to 5:45pm in Mendel G30
Section 002: Thursday 6:15 to 8:45 in Mendel G30
Spring 2000, Villanova University                           Name: _________________________________

  1. Consider the following BNF: 
        <digit>  ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
    <unary>  ::= + | -
    <binary> ::= * | /
    <expr>   ::= <digit> | <unary> <expr> | <expr> <expr> <binary>

    (4 points) Which of the following things are valid <expr>s? Write "yes" for each valid <expr>, "no" for each expression that is not a <expr>.
     

    1. 2 + 3 *
       
    2. + 2 3 *
       
    3. 2 3 / - 4 /
       
    4. - 2 3 4 / /

    (2 points) Write a valid <expr> that is exactly seven symbols long.


     

  2. (3 points) How are parameters passed? (Fill in the blanks.)
    1. What language passes parameters by unification? __________.
    2. What language passes parameters by pattern matching? __________.
    3. In Java, what parameters are passed by value? __________.
       

  3. (4 points) Name each of the following kinds of subprograms:: 
     


  4. (4 points)  When you send a message to an object in an O-O language, how does the language choose a method to execute?

    5.  




  5. (6 points) Briefly define each of the following terms: 
     
  6. (6 points) In most languages, storage for the values of variables can be allocated either on the stack or on the heap.
     
    1. When is storage allocated on the heap? That is, what does the program do that gets memory from the heap?
       
       

    2. When is storage allocated on the stack instead of the heap?
       
       

    3. Name the two problems that typically arise in a language like C or C++ where the programmer, rather than the language, is responsible for storage allocation.
       
       

  7. (3 points) We discussed two garbage collection algorithms. Briefly describe the mark-and-sweep algorithm and mention one disadvantage of this algorithm..
     
     
     
     


     
     
  8. (6 points) The Design Pattern you used in the Magic Forest animated applet was the MVC pattern. Briefly name each of the three parts (M, V, and C) and tell what their responsibilities are. 
     
  9. (6 points) Briefly define each of the following terms:
     
  10. (8 points) Unification is an essential operation in Prolog. For each of the following, tell (1) whether the two expressions can be unified, and (2) if so, what values are given to each of the variables. (Note: pay careful attention to case.)
     
    1. f(x, y) = g(5, 7)
       
       
    2. mother(John, dick) = mother(jack, Richard)
       
       
    3. mother(Tom, dick) = mother(dick, Harry)
       
       
    4. me = grandpaw(me, Myself)
       
       
  11. (6 points) In Prolog, assume you have a number of facts of the form: 
    son(X, Y).          /* X is the son of Y. */
daughter(X, Y).     /* X is the daughter of Y. */
parent(X, Y).       /* X is a parent of Y. */

    Write Prolog rules (exactly one each) for: 

    mother(X, Y).       /* X is the mother of Y. */




grandmother(X, Y).  /* X is the mother of a parent of Y. */




sibling(X, Y).      /* X and Y have the same mother and the same father. */

     


  12. (4 points) In Prolog,  
    1. If a name begins with a lowercase letter, it denotes a __________.  
    2. A "predicate" consists of one or more __________(one word).  
    3. The "don't care" variable is written as __________.  
    4. If you want a string to have the value "He isn't here", the way you would write this string in Prolog is ____________________.  
       
  13. (10 points) What will be the result of evaluating each of the following Lisp functions?
     
    1. (car '(a (b (c))))
       
    2. (car '(((a) b) c))
       
    3. (car '(()))
       
    4. (cdr '(a b c))
       
    5. (cdr '((a b) (c d)))
       
    6. (cdr '(()))
       
    7. (cons 'a '((b) c))
       
    8. (cons '(a b) '(c d))
       
    9. (cons '() '())
       
    10. (eq nil ())
       
    11. (eq '(a b) '(a b))
       
    12. (cond  ((cons 'a 'b) 'a)  (t 'b) )
       
    13. (null (null ()))
       
    14. (cons (car '(a b c)) (cdr '(b a c)))
       
    15. (append (list 'a) '(list b c))
       
  14. (2 points) Write a cond expression that is equivalent to, but simpler than,
            (cond ((atom a) x) ((null a) x) (t y))

     
     
  15. (4 points) (Fill in the blanks) In Lisp, one technique for writing a complicated function is to:
    Start the function body with a __________, test for __________, do something with the __________, and recur with the __________.
     
  16. (8 points) What will be the result of executing each of the following Haskell 98 commands?

     
    1. take 5 [2, 3..]

    2. filter even [1..10]

    3. [x | x <- [1..5]]

    4. [(x,y) | x <- [1, 2], y <- [1..2]]

    5. break (== 'c') "abracadabra"

    6. map f [1..5] where f = (3 -)

    7. 2 : "abc"

    8. f [1..3] where f x@(y:z) = (x, y, z)


  17. (8 points) True or false. In Haskell...
    1. (x `mod` y) means the same as (mod x y)
       
    2. All elements of a tuple must be the same type.
       
    3. The menu commands for Copy and Paste don't work.
       
    4. last has the same type as init.
       
    5. Functions can be defined at the prompt.
       
    6. Functions cannot be overloaded.
       
    7. The elements of a list must all have the same type.
       
    8. If x is a variable, (x) has the same type as x.
       

  18. (2 points) What is the meaning of :: in Haskell?
     
     

  19. (2 points) Haskell is supposed to be "strongly typed," yet you seldom have to declare the types of your variables. How is this possible?

    20.  
     

  20. (2 points) Write an expression that, given a list ilist of integers, returns a new list containing the nonnegative integers of ilist.