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> | <expr> <unary> | <binary> <expr> <expr>

   (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. In Java, objects are passed by __________.
   2. In Prolog, parameter transmission is by __________.
   3. In Haskell, parameter transmission is by __________.
       
      
3. (4 points) Briefly, distinguish among the following four kinds of subprogram: 
    
   
   • procedure
      
      
     
   • function
      
      
     
   • predicate
      
      
     
   • method
      




4. (4 points)  Do "functions" in C satisfy the standard definition of "function"? Briefly defend your answer.

 



5. (6 points) Briefly define each of the following  terms: 
    
   
   • overriding a function
      
      
     
     
   • overloading a function
      
      
     
     
   • a "class variable"
      
     
      
     
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 stack? That is, what does the program do that causes the stack to expand?
       
       
      
      
   2. When is storage allocated on the heap instead of the stack?
       
       
      
   3. When a "memory leak" occurs, does the lost storage come from the heap or from the stack? Why does this storage leak when the other doesn't?
       
       
      
7. (3 points) We discussed two garbage collection algorithms. Briefly describe the reference count 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. 
    
   
   • M
      
     
      
     
     
   • V
      
      
     
     
     
   • C
     
     
      
     
9. (6 points) Briefly define each of the following terms:
    
   
   • Scope of a name
      
      
     
     
     
   • Lexical scope
      
      
     
     
     
   • Constructor
      
      
     
     
     
     
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:

    male(X).     /* X is a male. */
    female(X).   /* X is a female. */
    child(X, Y). /* X is a child 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 capital 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's not 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 d)))
        
       
    3. (car '(()))
        
       
    4. (cdr '(a (b (c))))
        
       
    5. (cdr '(((a) b) c))
        
       
    6. (cdr '(()))
        
       
    7. (cons 'a '(b (c)))
        
       
    8. (cons '(a b) '(c d))
        
       
    9. (cons '() nil)
        
       
    10. (eq 'a 'A)
         
        
    11. (eq '(a b) '(a b))
         
        
    12. (cond  ((cdr '(a)) 1)  (t 2) )
         
        
    13. (null nil)
         
        
    14. (cons (car '(a b c)) (cdr '(a b c)))
         
        
    15. (list (car '(a b c)) (cdr '(a b c)))
         
        
14. (2 points) Write an expression that is equivalent to, but simpler than, (append (list a) b)
    
     
     
     
    
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. length "hello"
 

    2. map even [1..10]


    3. init [1..5]


    4. [x | x <- [1..5], even x]


    5. init "curry"


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


    7. :type even


    8. take 5 (iterate (2 *) 1)

 

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 keyboard shortcuts for Copy and Paste don't work.
        
       
    4. last has the same type as head.
        
       
    5. Functions are first-class objects.
        
       
    6. Functions can be overloaded.
        
       
    7. Functions can be defined at the prompt.
        
       
    8. If x is a variable, (x) has the same type as x.
        
       
18. (2 points) Haskell allows infinite lists. How is this possible?
     
    
    
     
    
19. (2 points) What is the meaning of the . (dot) operator in Haskell?
    
    
    
    
20. (2 points) Write, as one statement, an anonymous function that squares its one argument, then assigns the function to the variable sq.