COMS W4115
Programming Languages and Translators
Lecture 19: Procedures
April 6, 2015

Lecture Outline

1. Procedures
2. Parameter-passing mechanisms
3. Evaluation strategies
4. Storage-allocation strategies
5. Activation trees and records

1. Procedures

• A procedure P in a programming language is a collection of statements that defines a parameterized computation. An invocation of P is called an activation of P.
• We use the term actual parameters to denote the parameters used in a call of a procedure.
• We use the term formal parameters to denote the parameters used in the definition of a procedure.
• We will often call a procedure that returns a value a function. (C uses the term function for procedure as well.)
• The type of the function return_type f(arg1_type a, arg2_type b) can be denoted by the type expression
   arg1_type x arg2_type → return_type
• Some language and translator design issues for procedures:
• Choice of parameter-passing mechanism
• Storage allocation for local variables: static or dynamic
• Can procedure declarations nest
• Can procedures be passed as parameters, returned as values
• Can procedure names be overloaded
• Generic procedures, ones whose computations can be done on different types
• Does language have closures (encapsulations of procedures with their runtime context)

2. Parameter-Passing Mechanisms

• Programming languages differ in how the values of parameters are passed to called procedures.
• Call by value
• Here the actual parameter is evaluated if it is an expression or copied if it is a variable. The r-value is placed in the location belonging to the corresponding formal parameter of the called procedure.
• C and Java use call by value. C leaves the order in which the parameters are evaluated unspecified; Java evaluates the parameters left to right.
• "swap" example from C
• Consider the following C program fragment

      int a = 1, b = 2;
      swap(a, b);
      printf("a = %d, b = %d\n", a, b);
    

where the function swap is defined as

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

This code does not work: it outputs a = 1, b = 2.


• Now consider the same program fragment with swap(&a, &b) in place of swap(a, b) and with swap defined as

      void swap(int *px, int *py) {
        int temp;
        temp = *px;
        *px = *py;
        *py = temp;
      }
    

This code works: it outputs a = 2, b = 1.


• Call by reference
• Here the address of the actual parameter is passed to the callee as the value of the corresponding formal parameter.
• If the parameter is an expression, the expression is evaluated and its value is stored in a new location before the call. The address of that location is passed.
• Useful for passing large parameters to procedures.
• Used for reference parameters in C++. In C++, the swap function can be written with reference parameters as

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

In the body, x and y are int's, not pointers to int's. The call is now just swap(a,b).


• Call by name
• A call-by-name parameter is re-evaluated in the caller's referencing environment each time it is used. The effect is as though the called procedure is textually expanded at the point of the call with each actual parameter substituted for the corresponding formal parameter at every occurrence in the body of the procedure. Local names in the called procedure may need to be renamed to keep them distinct.
• Used in Algol 60.
• Also used at compile time by macros in the C preprocessor.
• Example: Consider the macro definition in C
#define max(a, b) ((a) > (b) ? (a) : (b))
The C statement
x = max(p+q, r*s);
will be replaced by the statement
x = ((p+q) > (r*s) ? (p+q) : (r*s);

3. Evaluation Strategies for the Arguments of a Procedure

• An evaluation strategy defines when and in what order the parameters to a procedure are evaluated.
• In call-by-value evaluation, all parameters are evaluated before applying the procedure. C functions use call-by-value evaluation.
• In normal-order evaluation, parameters are evaluated after applying the procedure, and then only if the result is needed to complete the evaluation of the procedure. Normal-order evaluation is used with macros and call-by-name parameters. Haskell uses a memoized version of call by name called call by need.

4. Storage-Allocation Strategies

• Static allocation
• Storage for all data objects is laid out at compile time.
• Names are bound to storage as a program is compiled.
• Static allocation was used in early versions of Fortran.
• Recursion is restricted.
• Size of all data objects must be known at compile time.
• No dynamic data structures can be supported.
• Stack allocation
• Run-time storage is organized as a stack.
• Activation records (ARs) are pushed and popped on the stack as activations of procedures begin and end.
• Typical kinds of data appearing in an activation record:

                 Actual parameters
                 Returned values
                 Control link
                 Access link
                 Saved machine status
                 Local data
                 Temporaries
  

• Storage for the locals in each call is contained in the AR for that call.
• Used by C and Java.
• Heap allocation
  • Storage is allocated and deallocated as needed at run time from a data area called a heap.
  • Necessary when data outlives the call to the procedure that created it.
  • Also needed when the values of local names must be retained after an activation ends.

5. Activation Trees and Records

• Consider the following C program for Euclid's algorithm.

#include <stdio.h>
int x, y;
int gcd(int u, int v) {
   if (v == 0)
      return u;
   else
      return gcd(v, u%v);
}

int main(void) {
   scanf("%d%d", &x, &y);
   printf("%d\n", gcd(x, y));
   return 0;
}

• A tree, called an activation tree, can be used to represent the procedure calls made during an execution of gcd because the lifetimes of the procedure activations are nested.
• Note that:
• The sequence of procedure calls corresponds to a preorder traversal of the tree.
• The sequence of returns corresponds to a postorder travseral.
• The path from the root to a node N shows the activations that are live at the time N is executing.
• Procedure calls and returns are managed by a control stack.
• On each procedure call, an activation record for that procedure is pushed on the stack. The activation record for each procedure call contains the information needed to manage the execution of that procedure call. When the call returns, that activation record is popped from the stack.

6. Practice Problems

1. Using the SDDs in Fig. 6.19, 6.36, and 6.37 in ALSU for expressions, if-statements, and booleans, construct a parse tree for the statement if ( x < 10 && x > 20 || x != y ) x = 30; and show the values of all the attributes computed at each node in the parse tree. What is the three-address code that is generated for this statement?
2. For the C-program in Section 5, draw the activation trees for the procedure calls made during the execution of
1. gcd(2, 5)
2. gcd(36, 48)

7. Reading

• ALSU, Sections 6.9, 7.1, 7.2