The Actual Structure of a Program, Parameter Passing Mechanisms

Tom Kelliher, CS18

Feb. 19, 1996

Programs and Memory Models

Consider the program fragment:

main()
{
   int i = 500;
   int data[500];

   g(i, data);
}

void g(int a1, int a2[])
{
   int i;

   for (i = 0; i < a1; i++)
      a2[i] = 0;
}

Memory segment allocation --- what, where?

Static model?

Another fragment:

main()
{
   int i = 4;                 // 1
   cout << f(i) << endl;      // 2
   i++;                       // 3
   cout << f(i) << endl;      // 4
}

int f(int a1)
{
   if (a1 <= 1)               // 5
      return 1;               // 6
   else                       // 7
      return a1 * f(a1 - 1);  // 8
}

Static model?

Another fragment:

int i = 1;

main()
{
   int i = 2;              // 1

   f();                    // 2
   g();                    // 3
   cout << i << endl;      // 4
}

f()
{
   int i = 3;              // 5

   g();                    // 6
   cout << i << endl;      // 7
}

g()
{
   int i = 4;              // 8
   cout << i << endl;      // 9
   cout << ::i << endl;    // 10
}

The Stack Model

• Static items --- allocate in data segment
• Local items --- allocate on a stack (stack segment)
• Dynamic items --- allocate in heap

What's a stack?

Terminology:

• Push
• Pop
• Activation record

Contents of activation record:

1. Return address
2. Initialized actual arguments
3. Uninitialized locals
4. Return value
5. Stack bookkeeping info.

Idea:

1. Each time function called, activation pushed
2. Function executes (possibly causing further pushes)
3. Each time function returns, activation popped

Box trace examples of the last two code fragments

Box trace yourselves:

#include <iostream.h>

int BinSearch(const int A[], int First, int Last,
              int Value)
// ---------------------------------------------------------
// Searches the array elements A[First] through A[Last] 
// for Value by using a binary search.
// Precondition: 0 <= First, Last <= SIZE - 1, where
// SIZE is the maximum size of the array, and
// A[First] <= A[First+1] <= ... <= A[Last].
// Postcondition: If Value is in the array, returns
// the index of the array element that equals Value;
// otherwise returns -1.
// ---------------------------------------------------------
{
   if (First > Last)
      return -1;      // Value not in original array

   else
   {  // Invariant: If Value is in A, 
      //            A[First] <= Value <= A[Last]
      int Mid = (First + Last)/2;
      if (Value == A[Mid])
         return Mid;  // Value found at A[Mid]

      else if (Value < A[Mid])
         return BinSearch(A, First, Mid-1, Value);  // X

      else
         return BinSearch(A, Mid+1, Last, Value);   // Y
   }  // end else
}  // end BinSearch

Assume the array holds: 1, 5, 9, 12, 15, 21, 29, 31

Search for: 5, 13

Parameter Passing Mechanisms

From last week:

• Call-By-Value --- rvalue of expression passed
• Call-By-Reference --- lvalue of expression passed

Example:

int main()
{
   int i = 1;
   int j = 2;

   f(i, j);
}

void f(int& a, int b)
{
   a = 4;
   b = 5;
}

Box trace?