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



Name:_______________________    Student ID:_______________


1. (5 minutes).  The English sentence "Colorless green
ideas sleep furiously." is valid syntactically, but is
complete nonsense semantically.  Write a Scheme expression
that has the same property.


2.  Consider the following two predicates:

c_keyword(auto).		c_keyword_x(auto) :- !.
c_keyword(break).		c_keyword_x(break) :- !. 
c_keyword(case).		c_keyword_x(case) :- !.  
...				...                    

2a (5 minutes).  Give a sample top-level call to
c_keyword/1 whose behavior would change if it used
c_keyword_x/1 instead, and explain why the behaviors
differ.

2b (5 minutes).  A disadvantage of the above approach is
that we have to list all the C keywords twice.  Rewrite the
predicates so that the C keywords need to appear only once
in the Prolog source code.  Do not change the
externally-visible behavior of the predicates.


3 (15 minutes).  Consider the following DCG rule, taken
from the solution to Homework 1:

access_to_object(C, C2) -->
    [access],
    general_access_modifier(C1, [*|C2]),
    nonarray_type(C, C1).

Translate this rule to an ordinary Prolog rule, without
using DCG notation.  Give an example call to the Prolog
predicate that you've defined.  Your call should be
something that might arise during the successful evaluation
of ada2c_type/2.




4.  The following deliberately-obscure C program has a
single runtime error, but otherwise it is a valid program.

   int main (void)
   {
     struct main { int main; } main;

     {
       {
	 enum { main = 0 };
	 if (main)
	   return main;
       }
       main.main = 1;
       goto main;
     }

     {
     main:
       {
	 struct main main = main;
	 return &main.main - &main.main;
       }
     }
   }

4a (5 minutes): How many different names are in this
program?  For each name, identify where it is defined, and
where it is used.

4b (10 minutes): Given that this is a valid C program
(except for the runtime error), describe the scope rules
for the C features used in this example, explaining in
general how a C compiler can disambiguate multiple names
that have the same identifier.

4c (5 minutes): What is the runtime error in the above
program?


5.  This problem asks you to write some Scheme procedures.
Your solutions can assume that the arguments to each
procedure have the proper form: i.e., procedures need not
check for errors.

Consider the following part of the Homework 2 solution:

(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)
	   '())
	  (else
	   (apply f obj1 objs)))))

5a (5 minutes).  Write a simpler function map1bt that acts
just like mapbt, except it accepts exactly two arguments (a
function and a binary tree) instead of accepting two or
more arguments.

5b (15 minutes).  Write an implementation of map1bt in
Ocaml.  Use an idiomatic translation, not a literal one.
What type does your Ocaml function have?

5c (15 minutes).  Suppose we have the opposite problem: we
have a binary tree of procedures, and want to apply each of
them to an object, yielding a binary tree of results, one
for each procedure.  That is, we want to define a procedure
btmap such that, for example:

  (btmap
    (cons (cons list real?)
	  (cons (cons '() integer?)
		(cons (cons sin cos) -)))
    0.5)

yields:

  (((0.5) . #t)
   (() . #f)
   (0.479425538604203 . 0.8775825618903728) . -0.5)

btmap always takes two arguments: the first is a binary
tree of procedures (i.e., containing only pairs,
procedures, and the empty list, and without any cycles),
such that each procedure accepts a single argument; and the
second is an arbitrary object, which will be passed to each
of the procedures.

Write an implementation of btmap in Scheme.  You may use
any of the standard Scheme builtin procedures, and you may
also use the map1bt procedure as specified above.  Your
implementation should be as short and elegant as possible.
5d (5 minutes).  Suppose you had the further problem of
generalizing btmap so that it could handle ingrown binary
trees of procedures.  How would you go about this?

5e (10 minutes).  Suppose you have two binary trees: the
first one "tp" is a tree of procedures (like the argument
to btmap), and the second one "to" is a tree of objects
(like the argument to mapbt1) each of which is neither a
pair nor the empty list.  Write a Scheme procedure
(maptrees tp to) that applies each of the procedures to
each of the objects, and produces a tree containing all of
the results.  The top part of the tree should have the same
structure as the tree of procedures, and each subtree under
the top part should have the same structure as the tree of
objects.  For example:

  (maptrees (list - (cons '() +) sin) '(1 () (2 . 3)))

should return

  ((-1 () (-2 . -3))
   (() 1 () (2 . 3))
   (0.8414709848078965 ()
    (0.9092974268256817 . 0.1411200080598672)))

Your solution can assume the existence of solutions for the
map1bt and btmap functions described above.