Please keep all answers brief and to the point. Illegible answers will be counted as wrong. None of the questions ask for examples.


General Questions

1. (6 points) Consider the following BNF grammar:
   

   <thing> ::= <x> y
<x> ::= a | b | c | <x> * <thing>

   
   Which of the following satisfy the definition of <thing>? (Write "yes" or "no" for each.)
   
   
   1. x y
      
      
   2. a x b y
      
      
   3. a * b y
      
      
   4. a y * b y
      
      
   5. y * x y
      
      
   6. b * c * a y y
   
   
   
   
2. (5 points) True or false:
   
   
   1. "Structured programming" emphasized ease of reading programs rather than ease of writing programs.
      
      
   2. Recursion was introduced by the programming language Algol 60.
      
      
   3. "Platform independence" was one of Algol 60's main design goals.
      
      
   4. "Platform independence" is one of Java's main design goals.
      
      
   5. "Garbage collection" refers to reclaiming storage that was allocated on the stack.
      
      
      
3. (4 points) What two programming paradigms (not specific languages) both claim the title of "Fifth Generation"?
   
   
   
   
   
4. (2 points) Name one improvement in programming language syntax that has occurred after Algol 60.
   
   
   
   
   
   

LISP Questions

1. (24 points) What is the result of each of the following expressions?
   
   
   1. (CAR '(A B C) )


   2. (CAR '((A) (B) (C)) )


   3. (CAR '(() ()) )


   4. (CDR '(A (B)) )


   5. (CDR '(() ()) )


   6. (CONS '() '(A B) )


   7. (APPEND '(A ()) '(B ()) )


   8. (LIST '(A B) '(C D) )


   9. (CAAR '((A B) (C D)) )


   10. (CADR '((A B) (C D)) )


   11. (CDAR '((A B) (C D)) )


   12. (CDDR '((A B) (C D)) )


       
2. (5 points) When writing functions in LISP: If the function is at all complicated, start by calling ________________. Do the _____________________ first; this usually involves testing for ________________________. Most recursive functions involve doing something with the __________ and recurring with the __________.
   
   
3. (4 points) Given the following function definition:

       (defun puzzle (a lat) 
           (cond ((null lat) ())
           ((eq a (car lat)) (puzzle a (cdr lat)))
           (t (cons (car lat) (puzzle a (cdr lat)))) ) ) 

   what is the result of the following function calls?

       (puzzle 'a '(a b r a c a d a b r a) )
   
   
       (puzzle 'a '(a (a b) b (b a) a) )
        

   
   
4. (4 points) Given the following function definition:

       (defun confuse (L1 L2)
           (cond
           (null L1) L2)
           (T (confuse (cdr L1) (cons (car L1) L2))) ) )

   what is the result of the following function calls?

       (confuse '((A) B) '(C (D)))
   
    
       (confuse '(A (B)) '((C) D))
   
   
   

5. (5 points) True or false?
   
   
   1. cdr is faster than cons.
      
      
   2. (EQ () ()) is a legal function call.
      
      
   3. LISP predicates return either T or NIL.
      
      
   4. NIL is a list.
      
      
   5. If none of its conditions is met, COND evaluates to NIL.
      
      
      
      

ML Questions

1. (4 points) Write an ML boolean function odd that returns true if its integer parameter is odd, and false otherwise.
   
   
   
   
   
   
   
   
2. (6 points) Express each of the following ML types in words:
   
   
   1. string list



   2. int -> real



   3. ((int * int) * real)




3. (4 points) Use the formal ML notation for types to describe the type of each of the following expressions (that is, write the type the way ML would show it):
   
   
   1. #"a"



   2. not



   3. round



   4. [#"a"]



      
      
4. (10 points) Write the name (or symbol) of the function that does each of the following:
   
   
   1. The remainder of an integer division.
      
      
      
   2. Returns true if two strings are equal.
      
      
      
   3. Concatenates two strings.
      
      
      
   4. Concatenates all the strings in a list
      
      
      
   5. Convert a list of characters to a string.
      
      
      
      
5. (4 points) Given the following function definition:

       fun confound x [] = [x]
       |   confound x (y::ys) = y::(confound x ys); 

   what is the result of the following function calls?

       confound 1 [2];
   
   
       confound 1 [2,3,4];
   
        

6. (4 points) Given the following function definition:

       fun bamboozle [] = []
       |   bamboozle (x::xs) = (bamboozle xs) @ [x]; 

   what is the result of the following function calls?

       bamboozle [1,2];
   
   
       bamboozle [1,2,3,4];
   
   
   

7. (4 points) Given the following function definition:

       fun mapkin L = map (fn x => x mod 2 = 0) L; 

   what is the result of the following function calls?

       mapkin [1,2,3];
   
   
       mapkin [~2, ~1, 0, 1, 2];
   
   
   
   
    

8. (5 points) True or false:
   
   
   1. In ML, anonymous functions cannot be recursive.
      
      
   2. ML is strongly typed.
      
      
   3. Elements of a list must all be the same type.
      
      
   4. To compile expressions in a file, use the load function.
      
      
   5. Currying combines multiple arguments into a single argument.

Feel free to use the rest of this space as scratch paper.