Spring 2000, CSE 428: Test 1

Spring 2000, CSE 428: Solution of test 1

Question 1

For each of the following strings, say whether or not they can be derived from the grammar
1. ^^bool can be derived
2. int^bool cannot be derived
3. int^*bool cannot be derived
4. int*^bool can be derived
The grammar has two kinds of ambiguities. One is related to the associativity of *: int * int * int can be generated with two different trees. The other is related to the priority between * and ^: ^ int * int can be generated with two different trees.

One possible unambiguous grammar for the same language is the following:

    Type ::= Type * A | A
    A    ::= ^A | B
    B    ::= int | bool | (Type)

The above grammar enforces left-associativity for * and the precedence of ^ over *.

Question 2

The grammar should be enriched by adding a production Exp ::= ~Exp. Hence:

   Exp ::=  Num | Ide | Exp Op Exp | ~Exp | let Ide = Num in Exp end | (Exp)

We can assume that an expression of the form ~e is represented by a tree which has operator ~ in the root and e represented in the left subtree. The interpreter eval for such language should then be changed as follows (the only modifications are in the "op" case)

   int eval(tree* t, environment* r){
          node* n = t->get_root();
          string ty = n->get_type();
          switch (ty) {
            case "num": 
               return n->get_value();
            case "ide": 
               return r->lookup(n->get_ide());
            case "op" : {  
               int k1 = eval(t->get_left(), r); 
               string op = n->get_op();
               if (op=="~")
                  return -k1;
               else {
                  int k2 = eval(t->get_right(), r); 
                  switch (n->get_op()) {
                     case "+": 
                        return k1 + k2;
                     case "*": 
                        return k1 * k2;
                     case "-": 
                        return k1 - k2;
                     case "/": 
                        return k1 / k2;
                  }
               }
            } 
            case "dec": {  
               string x = n->get_ide();
               int k = t->get_left()->get_root()->get_value();
               environment* r1 = r->add(x,k);
               return eval(t->get_right(), r1);                   
            }    
          }
   }

Question 3

Call by value: 3
Call by reference: 6
Call by value-result: 3

Question 4

The result of
```
    x > 0 implies (x = 1 or x > 1 or 1/x > 1)
```
is always true, in fact, it is:
1. true if x < 0 or x = 0, because ( x > 0 ) is false
2. true if x > 0, because either x = 1 is true, or x > 1 is true, or 1/x > 1 is true
Note in particular that, thanks to the strictness of "implies", the expressions never gives error.
1. call by value cannot be used, because the semantics would be strict
2. call by value-result cannot be used, because the parameter needs to be a variable.
3. call by reference cannot be used, for the same reason. (In some languages it is allowed to pass generic expressions, but then the parameter is evaluated at the moment of the call, like in call by value.)
4. call by name is the only one that can be used
```
   bool implies(bool name e1, bool name e2){
      if (!e1) 
         return true;
      else 
         return e2;
  }
```

Question 5

1. Under static scope the procedure call prints 0 and then returns
2. Under dynamic scope the procedure call prints -1 and then returns

      caller                      block where
      of p                        p is defined
                  p    I
        ^   ------------------      ^ 
     CL |___|_               |      | 
            |                |      |
            ------------------      |
            |               _|______| SL
            |                |
            ------------------
        |-->|        -----   |<-----|----| 
        |   |      x | 1 |   |      |    |           
        |   |        -----   |      |    |
        |   |      y | 0 |   |      |    |
        |   |        -----   |      |    |
     CL |   ------------------      |    |
        |                           |    |
        |         q    I            |    |
        |   ------------------      |    |
        |___|_               |      |    | 
            |                |      |    |
            ------------------      |    |
            |               _|______| SL |
            |                |           |
            ------------------           |
        |-->|                |<-----|    |
        |   |                |      |    |
        |   |                |      |    |
     CL |   ------------------      |    |
        |                           |    |
        |          r   I            |    |
        |   ------------------      |    | 
        |___|_               |      |    |
            |                |      |    |
            ------------------      |    | 
            |               _|______| SL |
            |                |           |
            ------------------           |
        |-->|        -----   |           |
        |   |      x | 0 |   |           |
        |   |        -----   |           |
     CL |   ------------------           |
        |                                | 
        |          q    II               |
        |   ------------------           |
        |___|_               |           |
            |                |           |
            ------------------           |
            |               _|___________| SL 
            |                |
            ------------------
            |                |
            |                |
            |                |
            ------------------      

    CL = Control Link
    SL = Static  Link

Question 6

There is some memory leak: the locations allocated by makelist() are never deallocated. There is no dangling reference.
There is some memory leak, for the same reason as before (the assignment l = NULL as no effect wrt deallocation). There is no dangling reference.
There is no memory leak: the instruction delete(l) activates the list destructor, which deallocates all the elements of the list pointed by l. There is no dangling reference after p returns (the pointer l is deallocated).
There is no memory leak: when p returns, l is deallocated and this causes the activation of the list destructor. (Note that this is different from the situation in which l is a pointer to list). There is no dangling reference.
There is no memory leak: the list starting from l is deallocated. There is a dangling reference: the field next of the element pointed by m is now dangling.