CSE 428, Spring 99: Solutions of Midterm 1

Exercise 1

The grammar is not ambiguous. In fact, all the productions are distinguished by the first token generated, except for the production of <Stat_list> (which, in principle, could cause an ambiguity problem with associativity) and for the 2nd and 3rd productions of <Statement (which, in principle, could cause a dangling-else ambiguity). However, the associativity problem is avoided by making "unguarded" recursion (i.e. derivation of <Stat_list>) only at the right of ";", and the dangling-else ambiguity is avoided by having an "end" at the end of the <Stat_list> in the 2nd production.
";" is enforced to be right-associative.
- (a) No
- (b) Yes
- (c) No
- (d) Yes

Exercise 2

With the given semantic specification, nand is non-strict. In fact, whenever the first operand results false, the second is not evaluated.
- false if x < 0 (both operands of the top-level nand are true)
- true if x = 0 (the first operand is false)
- true if x > 0 (the first operand is false)
- (a) We need call-by-name. In fact, with call-by-value we get a strict semantics (because the operands, i.e. the actual parameters, are evaluated before executing the body of the function). Call-by-reference and call-by-value-result are out of question because the actual parameters must be variables (so we could not pass, for instance, the expression x < 0). Only call-by-name allows to pass expressions and to delay evaluation until needed during the execution of the body of the function.
- (b) In Pascal-like:
```
function nand(name x,y:boolean):boolean;
   begin
   if not x 
      then nand := true
      else if not y 
              then nand := true
              else nand := false
   end;
```
  In C-like (using the fact that || is non-strict):
```
int nand(name int x,y){
    return (!x)||(!y);
}
```

Exercise 3

In Pascal:

function sum_list(l:list):integer;
   begin
   if isempty(l) 
      then sum_list := 0
      else sum_list := head(l) + sum_list(tail(l))
   end;

In C:

int sum_list(list l){
    if (isempty(l))
       return 0;
    else 
       return head(l) + sum_list(tail(l));       
}

It is not tail recursive: in the else-branch, after the recursive call, we need to perform the sum.

Exercise 4

- (a) the output is 2
- (b) the output is 1



caller of p        p I           A.R. where p is declared
        ^   ------------------      ^ 
     CL |___|_               |      | 
            |                |      |
            ------------------      |
            |               _|______| SL
            |                |
            ------------------
        |-->|        -----   |<-|---|----| 
        |   |      x | 1 |   |  |   |    |           
        |   |        -----   |  |   |    |
        |   |      y | 2 |   |  |   |    |
        |   |        -----   |  |   |    |
     CL |   ------------------  |   |    |
        |                       |   |    |
        |          q I          |   |    |
        |   ------------------  |   |    |
        |___|_               |  |   |    | 
            |                |  |   |    |
            ------------------  |   |    |
            |               _|__|SL |    |
            |                |      |    |
            ------------------      |    |
        |-->|        -----   |      |    |
        |   |      y | 1 |   |      |    |
        |   |        -----   |      |    |
     CL |   ------------------      |    |
        |                           |    |
        |          r I              |    |
        |   ------------------      |    | 
        |___|_               |      |    |
            |                |      |    |
            ------------------      |    | 
            |               _|______| SL |
            |                |           |
            ------------------           |
        |-->|        -----   |           |
        |   |      x | 2 |   |           |
        |   |        -----   |           |
     CL |   ------------------           |
        |                                | 
        |          Q II                  |
        |   ------------------           |
        |___|_               |           |
            |                |           |
            ------------------           |
            |               _|___________| SL 
            |                |
            ------------------
            |        -----   |
            |      y | 2 |   |
            |        -----   |
            ------------------      

    CL = Control Link
    SL = Static  Link

Exercise 5

- (a) It is possible. For instance, foo1 might leave p dangling to the heap and foo2 might use the same heap location (still pointed by p) for a dynamic allocation on another pointer. Examples of foo1 and foo2 which might produce such situation are:
```
foo1(){
   int *q;
   q = new int;
   *q = 5;
   p = q;
   delete(q);
}

foo2(){
   int *r;
   r = new int;   
   *r = 6;
   delete(r);
}
```
- (b) It is still possible. For instance, foo1 might leave p dangling to the stack and foo2 might use the same stack location (still pointed by p) for allocating some local variable. Examples of foo1 and foo2 which might produce such situation are:
```
foo1(){
   int x;
   x = 5;
   p = &x;
}

foo2(){
   int y;
   y = 6;
}
```
Note: I run the above program on Unix, with the g++ compiler, and I obtained indeed as output first 5 and then 6 in both cases (a) and (b).
Another way in which foo2 can change the value of *p is by using pointer arithmetic: foo2 might assign to a local pointer exactly the location pointed by p and then change its value.

- (a) It is possible also in Pascal. The corresponding Pascal declarations for foo1 and foo2 shown in 1(a) might give (depending on the system) the same results (first output 5 and then 6).
- (b) This case is not possible in Pascal: dangling pointers are confined to the heap, and pointer arithmetic is not allowed. Hence the only way to create a new access to a location pointed by a dangling pointer is via an instruction "new".