• Procedure and functions may be used interchangeably.
• In C/C++ only provide functions. Procedures are special function with return type void
• Pascal explicitly provides two different reserved words.
• History
  • Fortran IV didn't allow recursion
  • Fortran allocated storage for all the variables in subroutines (procedures) as well as the main program at compile time
  • For any given procedure, there is only a fixed amount of space available
  • You cannot have more than one outstanding call for a procedure
  • Algol-like languages separated instructions from the storage part of a procedure.
  • There is only one copy of the instructions, because the instructions don't change.
  • The storage on the other hand can be changed for different calls to the procedure
  • Template of the storage portion of the procedure is defined.
  • Whenever a procedure is called, storage for the procedure is created using the template and this copy is called the activation record (AR).
  • The AR is stored on a stack
• Procedures
  • has a name, body with possibly some local variables, possibly formal parameters, possibly a return value
  • difference between formal and actual parameters
    • void f(int x) { cout << x; }
  • main(){int z; z = 20; f(z);}
  • x is the formal parameter and z is the actual parameter
  • the formal parameter is used to define the function. The actual parameter or its value is used in the execution.
  • In C/C++, an explicit return statement is used to return a value
  • In Pascal, the function name is assigned the return value. Not necessarily a good choice. The function name cannot act as a true variable (confusion due to special case, destroys the orthogonality)
  • Orthogonality
    • We have two different sets of concepts which are independent of each other (orthogonal)
    • First set has m concepts and second set has n concepts, then we get m*n features. We only remember m+n concepts. Assume m=n=10. We got 100 features by remembering only 20.
    • Vi editor in UNIX
    • movements: h(left),j(down),k(up),l(right),w(word)
    • changes: d(delete), c(change), y(yank)
    • delete a word dw, change a word cw.
    • Generally, languages add exceptions. Let us say we have e number of exceptions.
    • How many features you get and how many things do you have to remember? Why?
    • m*n-e, m+n+e
    • Let us say we have a square function in Pascal. It can be assigned a value just like a variable. Assume a function called square
    • square := x*x;
    • square := x;
    • square := square*x; { not allowed }
    • A function called sum
    • sum := 0;
    • for I := 1 to 10 do
    • sum := sum + I;
  • Another problem is that we cannot use a limited goto through the return statement.
• Benefits of procedures page 154
• Parameter passing
  • Passing functions as parameters. see integrat.cpp
  • Value, reference, constant reference, value-result, name.
  • Passing by value and reference are well known. Passing by value passes a copy of the actual parameter and changes made to the copy are not reflected in the actual parameter. The reference passes the actual parameter and changes made in the function to this parameter are retained in the calling program.
  • void f1(int *ip){ *ip = 20;}
  • void f2(int& j){ j = 20;}
  • void f3(int j){ j = 20;}
  • f3 is a useless function. f2 and f1 achieve the same thing but f2 is easier to write because you don't have to dereference the parameter. Generally, playing with pointers is not desirable.
  • Parameter passing by constant reference. Same as passing by reference. But compiler forbids code that changes its value. Efficiency of passing by reference and safety of passing by value.
  • void f4(const int& j){ j = 20;} Compiler will not accept this. Why?
  • Passing by value result, has effect similar to passing by reference.
    • Passes a copy of the actual parameter and upon exit the contents of the copy are copied back into the actual parameter.
    • A C++ (C++ doesn't provide passing by value-result) equivalent will look like this
    • void f5(int& j){ j = 20;}
    • void main()
    • {
    • int x;
    • int y = x;
    • f5(y);
    • x = y;
    • }
    • What will happen if you try to swap the value of j and a[j];

void main()

{

int a[20], j;

j = 2; a[j] = 99;

swap(j,a[j]);

}

• If both the parameters two swap are passed by value/reference/const reference/value-result/name.
• Passing by name is of academic interest only. It was used in Algol-60.
• Before we look at the mechanism we have to know about lexical versus dynamic scoping rules
• Program in Figure 5.6
• At compile time all W can think about is the n that is available globally. Lexical scoping will bind n used in W to the global n.
• Dynamic scoping on the other hand will delay the binding till the execution time. In that case n accessed in W will be whatever n is being used in the calling program. When W is called from D, W will use the n from D. When W is called from main, it will use n from main program.
• Generally, we should avoid multiple bindings of the same name.
• Passing by name in Algol-60 works somewhat similar to macro expansion. The code for the procedure is copied in the calling program. Appropriate renaming of local variables as well as formal parameters is described on page 165.

• Returning values
• C and Pascal return by value. They don't allow returning of a struct/record. If the record is large you will need a large chunk of memory to store the return value temporarily.
• C++ allows you to return the struct/class by value as well as the usual C returning mechanism.
• C++ also allows you to return by reference as well as const reference.
• const list& operator =(const list& right)
• list l1, l2, l3;
• l1 = l2 = l3;
• The above assignment will not be possible if we didn't return the list.

• A little bit more about scoping
• C and Pascal expect you to declare variables at the beginning of a block
• { int n; ..................... n = 30; .......... }
• C++ makes it more flexible. Declaration can be delayed until the variable is used.
• {............ int n; n = 30; ...........}
• Improves readability. Because when we are reading n=30, we don't have to go back to the beginning of the block to find out the type of n.
• If you think that n=30 obviously implies that n is an integer, think again.
• C++ is not only object oriented but also a better C.
• In Pascal, the scoping is a bit more complicated because procedures can nest other procedures.
• In Fig. 5.9, scaninit doesn't have access to getch. This can be used to an advantage (information hiding) if used carefully. C/C++ do not allow procedure nesting like that.

• Midterm will include chapter 5. We will be only covering chapter 5 until page 190 upto but not including section 5.7.
• The instructions need not be copied for every new call of the function. But the storage needs to be copied.
• int factorial(int n){if(n == 1) return 1;
• return n*factorial(n-1);}
• Three different types of bindings from page 172
  • At compile time the variable scopes is resolved by creating a template for the AR. The location for the variable is not known but displacement from the beginning of AR is calculated. (page 185). The actual address is calculated at run-time as beginning of AR + displacement.
  • When a function is called the storage is allocated but we haven't stored any values
  • The actual values are bound during execution of various instructions.
• Activation trees: Similar to recursion trees that we looked at in COSC 2007.
• The difference between recursion tree and activation tree is that the recursion tree is only interested in the recursive calls.
• An example of Hanoi from blackboard and Figure 5.12.
• A general activation record is shown in Fig. 5.13
  • Control link: link to the calling procedure
  • Access link: Link to the procedure that has your non-local variables. In lexical scoping, it will be the procedure that lexically contains you.
  • Saved state: The state of the program when the call was made
  • values of parameters
  • space for storing the results
  • local variables
• Specifically, the AR for C is shown in Figure 5.19
  • First four slots make up the AR for the callee
  • First slot (incoming parameters are saved by the caller)
  • Second slot stores registers including the control link (C compilers generally don't use access link)
  • Fourth slot stores temporary calculations such as n-1 or (a+b)*c
  • The callee also need tp write the parameters of the function it calls (fifth slot not part of callee's AR)
• Algol-like languages use stacks for storing AR. The problem with stack is you can only delete from the top of the stack. This can be a problem in parallel programming.
• If you are going to have more than one active function at a time, you need a heap. Heap means the insertions and delettions can be done anywhere you want. (Pages 179-180)
• We have already seen that C doesn't use access control. Because the nested blocks are stored in the same AR

void f()

{

.

.

.

.

{

.

.

.

{

.

.

.

}

}

}

• Theoretically, each blocks is supposed to have a separate AR. But in practice, generally one AR is created for the entire function f
• We have four types of variables:
  • global
  • static
  • dynamic
  • local
  • First three need to be allocated at all times, they cannot be stored in activation record of any function. They are stored on a heap.
• Even though many books use factorial to explain recursion, they are a bad example of recursion.
  • If the recursion tree is a chain, don't use recursion
  • If the recursion tree has duplication, don't use recursion
• In many cases, the first (chain like rec. tree) corresponds to tail recursion.
• Fig 5.20 has tail recursion and compilers may optimize by eliminating the tail recursion as shown in Fig. 5.21.