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> x <x>
<x> ::= a | b | c | <thing> * <thing>

   
   Which of the following satisfy the definition of <thing>? (Write "yes" or "no" for each.)
   
   
   1. x
      
      
   2. a x b
      
      
   3. a * b x c
      
      
   4. a x b * c
      
      
   5. a x b x c
      
      
   6. a * b x c * d
   
   
   
   
2. (5 points) True or false:
   
   
   1. Smalltalk was the first object-oriented language.
      
      
   2. A programming language that supports recursion uses a heap to allocate local variables.
      
      
   3. FORTRAN was successful primarily because it was so efficient.
      
      
   4. Java's "access modifiers" (public, protected, private) help specify the scope of names.
      
      
   5. "Garbage collection" refers to reclaiming storage that was allocated on the heap.
      
      
      
3. (2 points) What language first introduced the notion of a "Virtual Machine"?
   
   
   
   
4. (2 points) In Perl, constructs such as [a-zA-Z]* and C(A|D)+R are called ____________________________________ .
   
   
   
   
5. (2 points) The acronym "ASL" stands for ____________________________________ .
   
   
   
   

LISP Questions

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


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


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


   4. (CDR '(A B C) )


   5. (CDR '(A (B)) )


   6. (CDR '(() ()) )


   7. (CONS '() '(A B) )


   8. (CONS '(()) '((A) (B)) )


   9. (APPEND '(A ()) '(B ()) )


   10. (APPEND '((A) (B)) '(()) )


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


   12. (LIST 'A '(B) '((C)) )


   13. (CAAR '((A (B (C)))) )


   14. (CADR '((A (B (C)))) )


   15. (CDAR '((A (B (C)))) )


   16. (CDDR '((A (B (C)))) )


       
2. (6 points) Briefly tell what arguments are required by DEFUN:
   
   
   
   
   
   
   
   
   
   
3. (6 points) Briefly tell what arguments are required by COND:
   
   
   
   
   
   
   
   
   
   
   
4. (4 points) Given the following function definition:

       (defun enigma (L)
           (cond
           ((null (cdr L)) ())
           (t (cons (car L) (enigma (cdr L)))) ) ) 

   what is the result of the following function calls?

       (enigma '(a b c) )
   
   
       (enigma '((a) (b c)) )
        

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

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

   what is the result of the following function calls?

       (unclear '((a) b) '((c) d) )
   
    
       (unclear '(a (b)) '(c d) )
   
   
   

6. (5 points) True or false?
   
   
   1. () is an atom.
      
      
   2. The value returned by (MEMBER 'B '(A B C)) is implementation-dependent.
      
      
   3. ATOM tests whether its single argument is an atom.
      
      
   4. LIST tests whether its single argument is a list.
      
      
   5. If none of its conditions is met, COND evaluates to NIL.
      
      
      
      

ML Questions

1. (2 points) How do you write the don't care variable in ML?
   
   
   
2. (4 points) Write an ML boolean function odd that returns true if its integer parameter is odd, and false otherwise.
   
   
   
   
   
   
   
   
3. (5 points) Express each of the following ML types in words:
   
   
   1. bool list



   2. ('a * 'a)



   3. ('a * 'b)



   4. char -> string



   5. char -> string -> int




4. (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"]



      
5. (8 points) Write the name (or symbol) of the function that does each of the following:
   
   
   1. Computes the logical "or" of two boolean variables.
      
      
      
   2. Negates (returns the negative) of a numeric value.
      
      
      
   3. Returns true if two strings are unequal.
      
      
      
   4. Return the number of characters in a string.
      
      
      
   5. Convert an uppercase character to lowercase.
      
      
      
   6. Returns the first element of a list.
      
      
      
   7. Returns a new list with the first N elements of the given list removed.
      
      
      
   8. Returns the second element of a tuple.
      
      
      
      
6. (4 points) Given the following function definition:

       fun confuse [] = []
       |   confuse (x::y::rest) = (x, y)::(confuse rest); 

   what is the result of the following function calls?

       confuse [1,2,3,4];
   
   
       confuse [[5, 6], [7, 8]];
   
        

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

       fun bumble [] = []
       |   bumble [x] = [x]
       |   bumble (x::y::rest) = y::(bumble (x::rest)); 

   what is the result of the following function calls?

       bumble [1,2,3,4];
   
   
       bumble [1,2,3,4,5];
   
   
   

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

       fun mappit L = map (fn x => Int.max (x, 0)) L; 

   what is the result of the following function calls?

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

9. (2 points) In order to be able to say isUpper ch instead of Char.isUpper ch, what command would you give to ML?
   
   
   
   
10. (5 points) True or false:
    
    
    1. All functions in ML take one parameter.
       
       
    2. Symbolic identifiers in ML cannot contain digits.
       
       
    3. Elements of a tuple must all be the same type.
       
       
    4. (f o g)x gives the same result as g(f(x)).
       
       
    5. Currying combines multiple arguments into a single argument.

Scratch paper (OK to tear off; don't need to hand it in)