The primary objective of every programming language is that of managing
the complexity of programs. Complexity management aids all aspects
of software development: it makes it easier for new programs to be
written faster, and it aslo makes it easier for older programs to be
maintained (by making it easier for people to understand the program). 

The primary tool for complexity reduction is abstraction: we abstract
oft-used "computation patterns" by more compact equivalents. We can trace
the use of abstractions even from the early days of compuers:

-- instead of cumbersome rewiring (which was the way to program the
   earliest computers), describe programs as a sequence of bit-patterns
   (i.e., machine instructions)

-- recognize the need to store values and manipulate them, and introduce
   hardware registers and higher level arithmetic operations into
   instruction sets; separate operations from operands

-- replace hard-to-remember machine instructions by assembly instructions

-- abstract repeated patterns in assembly instructions by macros

-- allow direct expression of higher level concepts such as compound types
   (such as records, arrays), loops, functions, etc into programs, which
   marks the birth of higher level programming languages

We have studied two kinds of abstractions so far:
   -- data abstractions:
         -- types and values
         -- variables and constants
   -- control abstractions (abstractions that involve changing the normal
              sequential execution of program code)
         -- if-then-else, switch
         -- loops
         -- procedures (this lecture)
         -- exceptions (future lectures)

Procedure Calls:
    Communication between the calling and the called procedures via
    parameters. Parameters are passed using different mechanisms. Parameter
    passing is the mechanism of substitution of formal parameters
    by actual parameters. Execution of the body of the procedures is the
    replacement of procedure invocation with procedure body
    Parameter passing mechanisms:
     Call-by-value : evaluate the actual parameters, assign them to
     corresponding formal parameters, execute the body of the procedure
      int p(int x) {
         x = x + 1 ;
         return x ;
       }
     with call-by-value, an expression y = p(5+3) is executed as follows:
       evaluate 5+3 = 8, call p with 8, assign 8 to x, increment x, return x
       which is assigned to y.

     Call-by-reference: evaluate actual parameters, which must have l-values
       assign these l-values to l-values of corresponding formal
       parameters, execute the body.
          int z = 8 ;
          y = p(z) ;
       after the call, y and z will both have value 9.
       Call-by-reference is explicit in C, whereas implicit in C++;
       for the above program, in C, one has to write it as
          int p (int *x) {
            *x = *x + 1 ;
             return *x ;
           }
           ...
           int z ;
           y = p (&z) ;

        Call-by-value-result: works like call by value bu in addition, 
        formal parameters are assigned to actual parameters at the end of
        procedure
        with call-by-value-result (which C doesn't support - hence the 
        following is pseudo-code),
         void p (int x, int y) {
           x = x + 1 ;
           y = y + 1 ;
         }
         ...
         int a = 3 ;
         p (a, a) ;
         after the call, a will have the value 4, whereas with
         cally-by-reference, a will have the value 5.
         the following is the equivalent of call-by-value-result call above:
            x = a ;
            y = a ;
            x = a ;
            x = x + 1 ;
            y = y + 1 ;
            a = x ;
            a = y ;
          thus, at the end, a = 4.


Semantics of Procedures
-------------------------

The semantics of procedure calls can be understood precisely in terms of
a substitution operation, where the procedure call is replaced by the
body of the procedure, after suitable preprocessing of the body (see below
for details).

Call-By-Value
--------------

Preprocessing: 
  a) create a block whose body is that of the procedure being called
  b) introduce declarations for each formal parameter, and intialize
     them with the values of the actual parameters
Inline: 
  Subsitute the block (obtained by the above preprocessing step)
  in the place of procedure invocation statement.

Example:
  int z;
  void p(int x) {
    z = 2*x;
  }
  main() {
    int y;
    p(y);
  }

  Replacing the invocation p(y) in the above manner yields the following
  main pogram:

  main() {
    int y;
    {   /* Created a new block corresponding to body of f */
      int x = y; /* Assign acual parameter to formal parameters */
      z = 2*x;   /* inline body of p as usual. */
    }


Fine print: We need to ensure that the variables declared in the body of the
procedure do not clash with the variable names visible at the invocation
point. If they do, the variables in the procedure body whould be renamed
to avoid the clash.


Call-By-Value-Result
----------------------

In addition to the preprocessing step in CBV, add assignment statements
to the end of the block that assigns formal parameter values to actual
parameters.

Example: For the above program, we wil get:
  main() {
    int y;
    {   /* Created a new block corresponding to body of f */
      int x = y; /* Assign acual parameter to formal parameters */
      z = 2*x;   /* inline body of p as usual. */
      y = x;     /* assign formal parameter value back to actual parameters */
    }

Call-By-Reference
------------------

Same as the steps for CBV, except that the variables introduced corresponding
to formal parameters will be references. With this change, the result of CBR
on the above example would be:

  main() {
    int y;
    {   /* Created a new block corresponding to body of f */
      int& x = y; /* Assign acual parameter to formal parameters */
      z = 2*x;   /* inline body of p as usual. */
    }
  }

Call-by-Name
-------------

Preprocessing: substitute formal parameters in the body of the procedure 
by actual parameter expressions. If any of the actual parameters have the 
same name as a local variable used in the called procedure body, then 
the local variable will first be renamed before the substitution.

Inline: Substitute the invocation expression with the modified procedure body.

Example: In the above example, we will get:

main() {
  int y;
  {
    z = 2*y;
  }
}


Macros
--------

Macros work very much like call-by-name parameter passing, and has some 
of its problems described below. In addition, macros suffer from the fact
they do not support the concept of local variables. This means that
possible name clashes between actual parameters and variables in the 
body of the macro will lead to unexpected results. For instance, 
given the macro:

#define sixtimes(y) { int z; z = 2*y; y = 3*z;}

and the program:

main() {
  int x = 5, z = 3;
  sixtimes(z);
}

After macro substitution, we get the program:
main() {
  int x = 5, z = 3;
  {
     int z;
     z = 2*z;
     z = 3*z;
  }
}
which is different from what we would have got with CBN parameter
passing. In particular, the name confusion between the local variable
z and the actual parameter z would have been avoided, leading to the
following result:

main() {
  int x = 5, z = 3;
  {
     int z1; /* local variable renamed to avoid clash with actual parameter */
     z1 = 2*z;
     z = 3*z1;
  }
}



Difficulties in Using Each of the Parameter Passing Mechanisms
----------------------------------------------------------------

CBV: Easiest to understand, no difficulties or unexpected results

CBVR: When the same parameter is passed in twice, the end result
      can differ depending on the order in which values are assigned
      back to actual parameters.

      int f(int x, int y) {
          x = 4;
          y = 5;
      }

      void g() {
         int z;
         f(z, z);
      }

      If assignment of formal parameter values to actual parameters
      (on completion of f) were performed left to right, then z would
      have a value of 5. If they were performed right to left, then
      z will be 4. 

      Otherwisely, relatively easy to understand.

CBR:  Aliasing can create problems. For instance, the procedure:
               int arev(int a[], int b[], int size) {
                   for (int i = 0; i < size; i++)
                       a[i] = b[size-i-1];
               }
      will normally copy b into a, while reversing the order of
      elements in b. For instance, if b is {1,2,3}, then a will be {3,2,1}.

      However, if a and b are the same, as in an invocation arev(c,c,4),
      the result is quite different. If c is {1,2,3,4} at the point of
      call, then its value on exit from arev will be {4,3,3,4}.

CBN:  CBN is probably the most complicated of the parameter passing
      mechanisms, and can be quite confusing in several situations:

      (a) if the actual parameter is an expression with side-effects:

          void f(int x) {
               int y = x;
               int z = x;
          }
          main() {
            int y = 0;
            f(y++);
          }
          Note that after a call to f, y's value will be 2 rather than 1.

      (b) if the same variable is used in multiple parameters:

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

          main() {
            int a[] = {1, 1, 0};
            int i = 2;
            swap(i, a[i]);
          }

          Intuitively, we expect i to be 0 and a to be {1, 1, 2} after
          the swap. However, the actual result when using CBN is different,
          as can be found by replacing the call to swap by the body of swap:
          i will be 0, and a will be {0, 1, 0}.

Macro: Macros share all of the problems associated with CBN. In addition,
       macro substitution does not perform renaming of local variables,
       leading to additional problems illustrated earlier.