CSC 8310 Linguistics of Programming Languages
Dr. David Matuszek
Fall 1997, Villanova University             Name:_____________________________________

First Quiz

1. (6 points) What is the result of each of the following calls?

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

B. (CDR '((A B) (C D)) )      ((C D))

C. (CONS '(A B) '(C D))      ((A B) C D)

D. (EQ '(A B) '(A B) )      Undefined.

E. (EQ NIL () )      T

F. (ATOM ( ) )      T


2. (2 points) In Lisp, which values are considered to be "true" and which "false"?
NIL is false; anything else is true.

3. (4 points) Write a function (NOT X) which returns true if X is false, and false if X is true. (You may use any other built-in Lisp functions that you know--you aren't restricted to the basic set.)

        (DEFUN NOT (X)
           (NULL X) )

4. (4 points) What is the general approach (not necessarily just in Lisp) to writing a recursive function?

  1. Do the simplest (base) cases first, without recursion.
  2. Recur only with a simpler case.
  3. Don't modify global variables or otherwise interfere with the correct operation of the calling routine.
  4. Don't attempt to trace through the recursion in order to understand it.

5. (4 points) Let's define a "real number" to consist of an optional sign, some digits, a decimal point, and some more digits. You can omit digits before the decimal point, or after the decimal point, but not both. Write the BNF for this (hint: start by defining "digit.")

    <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
    <sign> ::= + | - |
    <digits> ::= <digit> | <digits> <digit>
    <real number> ::= <sign> <digits> . <digits>
                    | <sign> <digits> .
                    | <sign> . <digits>