PLI Tutorial 8
Runtime Environments 

(Lm.n refers to Louden, Exercise m.n.)

Louden, Exercises 7.3, 7.4, 7.5, 7.7, 7.11, 7.15 (ignoring pass by name),
7.16 (similarly).

1. (L7.3) Draw a possible organisation for the runtime environment of the 
C program of Figure 4.1 (p. 148) after the second call of function 
factor(), given the input string "(2)".

2. (L7.4) Draw the stack of activation records for the following Pascal 
program, showing the control and access links, after the second call to 
procedure c().  Describe how the variable x is accessed from within c().

program env;
  procedure a;
    var x: integer;
    procedure b;
      procedure c;
      begin x := 2; b; end;
    begin (* b *) c; end;
  begin (* a *) b; end;
begin (* env *) a; end.

3. (L7.5) Draw the stack of activation records for the following Pascal 
program
(a) After the call to a in the first call of p.
(b) After the call to a in the second cal of p.
(c) What does the program print and why?

program closureEx(output);
  var x: integer;

  procedure one;
  begin writeln(x); end;
  
  procedure p(procedure a);
  begin a; end;
 
  procedure q;
    var x: integer;
    procedure two;
    begin writeln(x); end;
  begin (* q *)
    x := 2; p(one); p(two);
  end;

begin (* closureEx *)
  x := 1; q;
end.

4. (L7.7) To perofrm completely static allocation, a Fortran 77 compiler 
needs to estimate the maximum number of temporaries required for any 
expression evaluation in a program.  Devise a method for estimating the 
number of temporaries required to evaluate an expression by defining an 
attribute grammar or, equivalently, by defining a function to traverse the 
expression tree.  Assume that expressions are evaluated from left to right 
and that every left subexpression must be saved in a temporary.  (These 
are strong assumptions.)

5. (L7.11) Consider the following procedure in C syntax:

void f(char c, char s[10], double r)
{ int *x;
  int y[5];
  ...
}

(a) Using the standard C parameeter passing conventions, and assuming the 
data sizes integer = 2 bytes, char = 1 byte, double = 8 byutes, address = 
4 bytes, determine the offsets from the fp of the following, using the 
activation record structure described in Chapter 6: (i) c, (ii) s[7], 
(iii) y[2].
(b) Repeat (a) assuming all parameters are passed by value (including 
arrays).
(c) Repeat (a) assuming all parameters are passed by reference.

6. (L7.15) Give the output of the following program (in C syntax) using 
the parameter-passing methods value, value-result and reference:

#include <stdio.h>
int i = 0;

void p(int x, int y)
{ x += 1;
  i += 1;
  y += 1;
}

int main()
{ int a[2] = {1,1};
  p(a[i],a[i]);
  printf("%d %d\n",a[0],a[1]);
  return 0;
}

7. (L7.16)  Give the output of the following program (in C syntax) using 
the parameter-passing methods value, value-result and reference:

#include <stdio.h>
int i = 0;

void swap(int x, int y)
{ x = x + y;
  y = x - y;
  x = x - y;
}

int main()
{ int a[3] = {1,2,0};
  swap(i,a[i]);
  printf("%d %d %d %d\n"),i,a[0[,a[1], a[2])l
  return 0;
}

7. (L, Section 7.4.3)  Describe the difference between internal 
and external fragmentation,  Which form can occur with the heap management 
scheme described in this section?  How does the scheme attempt to avoid
the other form.  Illustrate with examples.  Modify the scheme to use 
best fit instead of first fit?  What effect would you expect this to have
on fragmentation?  On speed of allocation?  Modify the scheme to include
"previous block" pointers in an attempt to speed up block release.  What
other consequences does such a change have?