1. (a) Yes; we saw an example in class (lower half of page 9 of slides).

(b) No: If B is unamb., there is only one parse tree corresponding to
any given legal string in the language; there is no way for AB to introduce
additional trees corresponding to this string and make the grammar 
ambiguous.

2. This is a little bit tricky. In fact, we cannot do it using the 
Nest attribute that we have seen in class. To see the problem, consider 
the following:

   begin
   int X, Y;
   ...
   <block>1
   ...
   <block>2
   ...
   <block>3
   ...
   end

Suppose X is declared in each of <block>1, <block>2 and <block>3. This
is legal in standard languages (including C/C++ since this is just nesting
blocks that declare variables, not functions). But in this new scope rule
it should be illegal because X is declared a total of four times. 

To catch this condition, we will have to introduce a synthesized
attribute, call it NameCount, of <stmt>, <ds>, <block>, ..., which
gives us information about all the names declared inside them,
*including inside nested blocks and blocks nested inside those nested
blocks, etc.*. NameCount will be a set of elements of the following kind: 
(X, 2); that means that the name X is declared twice inside the given 
entity (either in nested blocks or non-nested blocks such as <block>1 and
<block>2 above).

Then, for example, we will have conditions such as the following:

  <stmt> ::= ...
            | <stmt>1 <stmt>2
              NameCount(<stmt>) <-- 
                     unionCount(NameCount(<stmt>1), NameCount(<stmt>2)
              Cond: ![\exists X: count(X, NameCount(<stmt>)) > 3]

That says that there is no X such that the associated count is greater
than 3 in NameCount(<stmt>).
Question: What is unionCount()? How do you define it?

3. What you have to do here is pass down a label value that is the label
to which control must be transferred if a given <stmt> turns out to
be a "break" stmt. We can also check that "break" is not used except 
inside a loop. (Note that <command> is the same as <stmt>

   <prog> ::=  <stmt>
               Labin(<stmt>) <-- 1
               BreakLab(<stmt>) <-- -1  // means "not in a loop"

  <stmt>  ::=  <stmt>1 <stmt>2
               BreakLab(<stmt>1) <-- BreakLab(<stmt>) 
               BreakLab(<stmt>2) <-- BreakLab(<stmt>) 
               ...
             | while <cond> do <stmt>1
               Labin(<stmt>1) <-- Labin(<stmt>)+2 // 2 labels needed for
                                            // code of loop
               BreakLab(<stmt>1) <-- Labin(<stmt>)+1
                               // this is the crucial rule; 
                           // Labin(<stmt>)+1 is the label at the end of
                           // this loop; so if inside <stmt>1 we come 
                           // across a break statement, we should jump to
                           // this label; so that is the value we pass in.
              | break;
                Code(<stmt>) <-- <(BR label(BreakLab(<stmt>)))>
                        // jump to the end of the innermost loop
                Cond: [BreakLab(<stmt>) != -1]
                        // but if BreakLab is -1, we are *not* in a loop!

4. [This problem is too complex for the midterm so you won't have anything 
this complex to deal with! But I wanted to include it so you can see
how different kinds of Lisp functions are defined.]

Consider a couple of examples to see what the problem means. Suppose 
S1 is (1 . 2); and S2 is (1 (2 . 3) 4) which, in dot notation is, 
(1 . ((2 . 3) . (4 . NIL))) In this case, this function should return
NIL because (1 . 2) doesn't appear in S2. On the other hand, if S2 had
been, say, (1 (1 . 2) 4), we should return T. 

Consider another example. Suppose S1 is (1 . 2) and S2 is 
((3 . 1) . (2 . 4)) Then we should return NIL because (1 . 2) does NOT
appear in S2 [even though 1 and 2 seem to appear "next to each other"
in S2].

The point is this: if S1 appears in S2, it must be either because it
is equal to S2 or it appears in car[S2] or in cdr[S2]. So it is
easy to define this function:

 isIn[S1, S2] =
      [ atom[S1] --> [ atom[S2] --> eq[S1, S2]; 
                      | isIn[S1, car[S2]] --> T; 
                      | T --> isIn[S1, cdr[S2]]; ]
      | atom[S2] --> NIL;
      | equal[S1, S2] --> T;
      | isIn[S1, car[S2]] --> T;
      | T --> isIn[S1, cdr[S2]]; ]

where equal[S1, S2] compares equality of two (atomic or non-atomic)
s-expressions:

  equal[S1, S2] =
       [ atom[S1] --> [ atom[S2] --> eq[S1, S2];
                      | T --> NIL;
                      ]
       | atom[S2] --> NIL;
       | equal[car[S1], car[S2]] --> equal[cdr[S1], cdr[S2]];
       | T --> NIL; ]

Another solution would be as follows:

 isIn[S1, S2] =
      [ equal[S1, S2] --> T;
      | atom[S2] --> NIL;
      | isIn[S1, car[S2]] --> T;
      | T --> isIn[S1, cdr[S2]]; ]


5. (This question uses a primitive, greater[S1,S2], which expects two numerica\
l
arguments and returns T if the first argument is greater than the second and
else, returns NIL.
Also, someone told me at the end of the class that we had not defined the
null[] function ... I thought we had. Anyway, it takes one argument and
returns NIL if the argument is not the atom NIL and returns T if the
argument is the atom NIL. So it never results in an error since the argument
is going to be either the atom NIL or it is not; there is no third possibility\
.)

There are a couple of different ways of defining maxList[]. The obvious
definition is as follows:

  maxList[L] =
    [ null[cdr[L]] --> car[L]; // only one element in L, so return that elemen\
t.
    | greater[car[L], maxList[cdr[L]]] --> car[L]; // car[L] is larger than ma\
xList[cdr[L]],
                 // so return car[L] since it is the largest in L
    | T --> maxList[cdr[L]]; // car[L] is not larger than maxList[cdr[L]], so
                // return maxList[cdr[L]] since it is larger than car[L]
    ]

That works but will be inefficient unless car[L] is larger than maxList[cdr[L]\
].
Why? Try to figure that out before reading further ...

it is inefficient because if car[L] is not larger than maxList[cdr[L]], we wil\
l end
up computing maxList[cdr[L]] twice; and since this is recursive, the inefficie\
ncy can be
exponential!

So can we come up with a better definition? It is not as obvious as in C or
Java (but that, to an extent, is because we are not used to *thinking* in Lisp\
 ...)
We will see the details after the midterm.