UCLA Computer Science 131 (Spring 2004) Section 2 midterm
100 minutes total, open book, open notes



Name:__________________________    Student ID:_________________________


1 (5 minutes).  Of the languages C++, Ocaml, Prolog, and Scheme, which
is the most likely to have implementations where programs execute
quickly?  List the languages in rough order of expected runtime
efficiency, and briefly justify your ordering.

2 (5 minutes).  Is a DCG rule a Horn clause?  Explain why or why not.


3 (5 minutes).  Does the following C function have well-defined behavior
regardless of the value of x?  If so, explain the behavior; if not,
explain why not.

int f (int x) { return -x == ~x + 1; }


4 (10 minutes).  In C and C++, parentheses are required around the test
expression of an if-statement (e.g., "if (x == 3) x++;"), but not
around the returned-value expression of an return statement (e.g.,
"return x++;").  Why are the parentheses necessary in the former but
not the latter?  Give an example of what would go wrong if parentheses
were not required around the former.

5 (10 minutes).  An identifier is said to have "discontiguous scope" if
the locations where it is visible are not all adjacent to each other
in the text of the program.  Give an example of discontiguous scope in
Scheme; or, if it's not possible, explain why not.  Similarly, give an
example in Prolog (or explain why you can't).


6 (10 minutes).  Translate the following Scheme function to Ocaml.  Style
counts here, so please use an idiomatic rather than a literal translation.

(define (all-pairs? list)
  (or (null? list)
      (and (pair? (car list))
	   (all-pairs? (cdr list)))))

7 (15 minutes).  Consider the following section of code in the sample
solution for Homework 1:

id([id(X) | C], C) --> [id(X)], {\+ c_keyword(X)}.

c_keyword(auto).
c_keyword(break).
c_keyword(case).
...

Suppose the grammar rule was rewritten as follows:

id([id(X) | C], C) --> {\+ c_keyword(X)}, [id(X)].

What would go wrong, and why?  Give an example use of the Prolog "id"
predicate that illustrates the problem.


8.  Consider the following code, taken from the sample solution for
Homework 2:

(define (mapbt f obj1 . objs)
  (let mapit ((obj1 obj1) (objs objs))
    (cond ((pair? obj1)
	   (cons (mapit (car obj1) (map car objs))
		 (mapit (cdr obj1) (map cdr objs))))
	  ((null? obj1) '())
	  (#t (apply f obj1 objs)))))

8a (5 minutes).  Is mapbt tail-recursive?  If so, why?  If not, why not?

8b (5 minutes).  Suppose id is the identity function (lambda (x) x).
If bt is a binary tree, what is the difference (in the caller's point
of view) between (id bt) and (mapbt id bt)?  Give an example use that
illustrates the difference.

8c (10 minutes).  Suppose we remove the line "((null? obj1) '())" from
the definition of mapbt.  How will this change the behavior of mapbt?
Give an example use that illustrates the change in behavior.


9 (20 minutes).  For each of the following Scheme top-level
expressions, give the simplest possible expression that has the same
external behavior whenever the original expression has well-defined
behavior.  Your simplifications may use side effects, and may use any
of the predefined Scheme procedures or special forms.  For the purpose
of this question, an expression is "simpler" if it has fewer tokens,
where tokens are as described in R5RS section 7.1.1.  If the
expression cannot be simplified, say so.

(not not)
(lambda (x) (if x x (not x)))
(cons cons '())
(lambda (x) (cons 1 (cons 2 (cons x '()))))
((lambda (x) (x x)) symbol?)
(let ((y (lambda (y) y))) (let ((y (lambda (x) y))) (y 10)))
(lambda (x) (if (car x) (cdr x) (car x)))
(lambda (x) (call/cc (lambda (k) (x k))))
(lambda (f x) (let g ((x x))
	        (if (null? x) x (cons (f (car x)) (g (cdr x))))))
(letrec ((p (lambda (f) (f p)))) (p (lambda (x) x)))