with comments and some answers
5/4/97
50 minutes. Closed book, closed notes. Please write directly on the test booklet.
1 point per part except as noted. 28 points total.
Definitions. Give a short definition of each of the following terms:
Name three accepted "paradigms" of programming.
A programming language without variables or loops (circle one):
Briefly describe the difference between...
Given the following BNF grammar:
(2 pts.) Give a full parse tree for the sentence "the cat chases a dog". Use the space above and to the right. The question asked for a tree, not a derivation.
(2 pts.) The sentence "the dog sleeps" cannot be derived from the grammar as given. Make changes to the above grammar so that "the dog sleeps" can be derived, but so that no ungrammatical (in the usual sense) English sentences can then be derived. Mark directly on the grammar, which is repeated below for convenience. Take care not to derive sentences like "the dog sleeps the cat"!
(2 pts.) Give (pure) BNF which generates exactly the same 'decl's as the following EBNF:
<decl> ::= [<class>] <tp> <id> {',' <id>} ';'
<tp> ::= float | real
<class> ::= long | short
[], {}, and 'empty' (however written) are not pure BNF. One possibility:
<decl> ::= <class> <tp> <idlist> ';' | <tp> <idlist> ';'
<idist> ::= <id> | <id> ',' <idlist>
<tp>, <class> as before. It is not necessary to know what <id> is. A common error was to have <decl> as the repeating element; this can lead to multiple ';' and other errors.
(1 pt.) Suppose (cons X Y) has the value (a b c d). Give possible values for X and Y, or explain why this is not possible. Everyone got this.
Suppose (car X) has the value (a b c d). Give a possible value for X, or explain why there is no possible value. Everyone got this.
(1 pt.) Suppose (list X Y) has the value (a b c d). Give possible values for X and Y, or explain why this is not possible.
(4 pts.) Write a LISP function 'elim' which eliminates a given value from a list. The first argument is the value, and the second is assumed to be a list. Examples are shown to clarify how the function should work. Write your answer in the space to the right of the examples. Use a pure functional style.
(elim 'a '(b a c d a))
(b c d)
(elim 'a '(z q 40))
(z q 40)
(elim 'a '(1 (a) b z))
(1 (a) b z)
(elim '(a) '(1 (a) b z))
(1 b z)
(elim 'a '(a))
nil
(elim 'a nil)
nil
(defun elim (val L)
(cond ((null L) nil)
( (equal val (car L)) (elim val (cdr L)))
( t (cons (car L) (elim val (cdr L)))
)
)
Most common errors: bad base case, or used 'list' instead of 'cons' to construct the answer.
The following program is written in Pascal syntax (recall that 'writeln' is similar in effect to a C 'printf').
program ex; var x: integer; procedure p; beginwriteln(x); end; procedure q; var x: integer; begin x :=77; p; end; begin (* main *) x := 99; q; end.
Suppose lexical scope is used. What value, if any, does the program display when it runs? 77
Suppose dynamic scope is used. What value, if any, does the program display when it runs? 99
Mention three different examples of binding in C, and list them in order from earliest to latest. One should a really early binding, and one should be really late.
Examples were wanted, not definitions or categories. Also, the example needed to be reasonable concrete. Just saying "variables" is too vague. "int i;" is part way there, but best of all would be to write something like "the binding of type in the declaration 'int i;' " You could give examples of type bindings, address bindings, value bindings, function definitions, etc. Really early would include preprocessor value bindings, or actually any static binding such as type; really late might be run-time allocation of memory, or value bindings via assignment statements.
An interesting footnote is that the declaration "int i = 0; " is an early value binding if i is a global variable, but the assignment statement "i = 0;" for the exact same variable is very late. That's why a good answer should include some explanation or commentary.