CSE305                  Problem Set 5 Answer Key                Fall 2007

   (1) Using storage object diagrams, show the execution of:

void main() {
        int x, y, *p, **q;
        x = 5;
        y = x+3;
        p = &x;
        q = &p;   //now:

x->3418          y->3420         p->2310           q->2312
  [ 5 ]            [ 8 ]          [3418]            [2310]

        (**q) = y + x;

**q as lvalue = q fetch fetch = 2310 fetch = 3418, so this stores 13 at 3418.

x->3418          y->3420         p->2310           q->2312
 [ 13 ]            [ 8 ]          [3418]            [2310]

        (*q) = &y;

*q as lvalue is 2310.  So location 2310 gets assigned the binding address of y.

x->3418          y->3420         p->2310           q->2312
 [ 13 ]            [ 8 ]           [3420]            [2310]

The net effect is that p has silently been made to point at y, not x.

        (**q) = y - x;

So this becomes an assignment to y, not to x as in the first statement!

x->3418          y->3420         p->2310           q->2312
 [ 13 ]           [ -5 ]          [3420]            [2310]

        printf("Final value of y is %d\n",y);
}
Final value of y is -5.


(2)

\begin{verbatim}
with Ada.integer_text_io; use Ada.integer_text_io;
with text_io; use text_io;                       #include <stdio.h>
procedure G is                                   /*Global variables*/
   x: integer := 2;                              int x = 2;
   z: integer := 4;                              int z = 4;

   function A(y: integer) return integer is      int A(int y)
      x: integer := 10;                          {
   begin                                            int x = 10;
      return x + y + z;                             return x + y + z;
   end A;                                        }

   function B(y,z: integer) return integer is    int B(int y, int z)
   begin                                         {
      x := 8;                                       x = 8;
      return A(x + y + z);                          return A(x + y + z);
   end B;                                        }

   procedure M is                                void main()
      y: integer := 1;                           {
      z: integer := 3;                              int y = 1;
   begin                                            int z = 3;
      put("B(x+y,z) = "); put(B(x+y,z));            printf("B(x+y,z) = %d ",
      put(" and x = "); put(x); new_line;                   B(x+y,z));
   end M;                                           printf("and x = %d\n",x);
begin  --of G                                    }
   M;
end G;                                           /* end-of-file */
\end{verbatim}


(a) In A: A.x, A.y, G.z
    In B: G.x, B.y, B.z
    In M: G.x, M.y, M.z  

Note that there is no difference between a parameter and a local
variable in this regard.

(b) Growing frames downward (so top of stack is bottom of page):

--------------------------
Global: x->[ 2// 8 ], z->[ 4 ]
--------------------------
Main:   y->[ 1 ], z->[ 3 ]    "x" follows SL to Global.  So x+y = z = 3
Calls B(3,3)
--------------------------
B(3,3): y->[ 3 ], z->[ 3 ]    "x" follows SL to Global.  So "x = 8;"
                              rewrites Global.x to 8.  So x+y+z = 14.
Call A(14)
--------------------------
A(14):  y->[ 14 ], x->[ 10 ]  "z" follows SL to G.z, *not* DL to B.Z! 
                              So x + y + z = 28, which is returned.
Return value: 28
--------------------------

At this point, the frame for A is popped and it returns 28 to B,
whose frame then gets popped returning the same value to Main.
The stack then has just:


--------------------------
Global: x->[ 8 ], z->[ 4 ]
--------------------------
Main:   y->[ 1 ], z->[ 3 ]    "x" follows SL to Global.  So now x = 8 here.
Print "B(x+y,z) = 28", and
then report "x = 8".
--------------------------

                                 






----------------------------------------------------------------------------
Bonus: here's a stack-language trace:
   (2) Trace: x 3 store pop y 7 z x fetch 6 - store * z fetch + store pop

x 3 store pop
...
...[x]
...[x][3]
...[3]
...

x->3418 (say)    y->3420     z->3422
  [ 3 ]            [ ? ]       [ ? ]

y 7 z x fetch 6

...[y]
...[y][7]
...[y][7][z]
...[y][7][z][x]
...[y][7][z][3]
...[y][7][z][3][6]

-

...[y][7][z][-3]       //recall that it's [2nd]-[top], not [top]-[2nd]

store                  //recall this leaves the stored value atop the stack

...[y][7][-3]     now: x->3418 (say)    y->3420     z->3422
                         [ 3 ]            [ ? ]      [ -3 ]
*
...[y][-21]

z fetch

...[y][-21][-3]       //OK to shortcut some of this.

+

[y][-24]

...store pop: stack empty and

x->3418 (say)    y->3420     z->3422
  [ 3 ]          [ -24 ]      [ -3 ]



   (3) Translate into our stack language, after int x,y,*p,*q:

        x = 33;
        y = 2*x + 1;
        q = &y;
        p = &x;

        q = p;
        *q = y+(x++);
        y = (*p) + (*q);

x 33 store pop
y 2 x fetch * 1 + store pop
q y store pop             //no "y fetch"!
p x store pop
q p fetch store pop       //NB: Similar code to "x = y;"---pointer assignment
                          //is treated the same as ordinary assignment!
q fetch y fetch (translate x++) + store pop
y p fetch fetch q fetch fetch + store pop

It is AOK for you to substitute "x fetch x x fetch 1 + store pop" from the
handout for "translate x++", or to use a shortcut such as "x postinc" with
the understanding that this leaves the previous value of x atop the stack.
If you postulate that "inc" pops x off the stack while incrementing x, then
"x postinc" = "x fetch x inc", while "x preinc" = "x inc x fetch".
Any of these forms are fine, so long as you make the difference between
"x++" and "++x" clear here and leave a /value/ (not "x") atop the stack
for the subsequent binary + to work on.