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?

- Do the simplest (base) cases first, without recursion.
- Recur only with a simpler case.
- Don't modify global variables or otherwise interfere with the correct operation of the calling routine.
- 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>