Chapter 9 Subprograms

Subprograms
Introduction
Fundamentals of Subprogams
Design Issues for Subprograms
Local Referencing Environments
Parameter-Passing Methods
Parameters That Are Subprogram Names
Overloaded Subprograms
Generic Subprograms
Separate Compilation
Design Issues for Functions
Accessing Nonlocal Environments
User-Defined Overloaded Operators

Subprograms
Introduction
    Babbage 1840's -- reusing collections of instruction cards
    Abstraction of details
Fundamentals of Subprogams
    General Subprogram Characteristics
        1.  single entry
        2.  calling program suspended
        3.  control returns to caller
    Basic Definitions
        subprogram definition : describes the actions of the 
               subprogram abstraction
        subprogram call : explicit request for execution
        active : begun exectuion but not complete
        subprogram header : 1st line of definition.  Indicates 
           type of syntactic unit; provides name for unit; may 
           supply list of parameters
    Parameters
        formal parameters:  those in subprogram header (dummy 
                             variables)
        actual parameters:  those in subprogram call
            positional
            keyword : need to know names of formulas

SUMER (LENGTH = > MY_ LENGTH,
    LIST =>  MY ARRAY,
    SUM => MY_SUM) ;

        Ada:  default values for formal parameters
        C: number of actual parameters need not match number of 
                  formal parameters

    Procedures and Functions
        procedures produce results by: 
            changing globals
            through formal parameters
        functions modeled after math functions -- ideally
            modify neither globals nor formals
            result replaces call
    
Design Issues for Subprograms
1.  What parameter passing methods are provided
2.  Are paprmeter types checked?
3.  Are local variables static or dynamic?
4.  What is referencing environment of a subprogram passed as 
     parameter?
5. Are parameter types in passed subprograms
    checked?
6.  Can subprogram definitions be nested?
7.  Can subprograms be overloaded?
8.  Are subprograms allowed to be generic?
9.  Is separate compilation supported?

Local Referencing Environments
    local variables:  variables declared inside subprograms
    If local variables are stack-dynamic:

   - Advantages:
       a. Support for recursion
       b. Storage for locals is shared among some
            subprograms

   - Disadvantages:
       a. Allocation/deallocation time
       b. Indirect addressing
       c. Subprograms cannot be history sensitive


 - Static locals are the opposite


 - Language Examples:

     1. FORTRAN 77 and 90 - most are static, but 
         the implementor can choose either 
         (User can force static with SAVE)

     2. C - both (variables declared to be static are)
         (default is stack dynamic)

    3. Pascal, Java, and Ada - dynamic only


Parameter-Passing Methods
    Semantic Models of Parameter Passing
        in
        out
        in out
   - Conceptual Models of Transfer:

       1. Physically move a value

       2. Move an access path

    Implementation Models of Parameter Passing
        Pass by Value
            additional storage needed for formal
            physical movement
        Pass by Result
            problem with sub(p1,p1)
        Pass by Value-Result
            problem extra storage
            also early exit
        Pass by Reference
            slower because uses address
            aliases
            inadvertant changes if only one-way needed
            constant 10
           5. Pass-by-name  (multiple mode)

        - By textual substitution
    
        - Formals are bound to an access method at the
           time of the call, but actual binding to a value
           or address takes place at the time of a 
           reference or assignment
    
         - Purpose: flexibility of late binding
     
         - Resulting semantics:
      
           - If actual is a scalar variable, 
              it is pass-by-reference
           - If actual is a constant expression,
              it is pass-by-value
           - If actual is an array element,
              it is like nothing else
              e.g. 
                    procedure sub1(x: int; y: int);
            begin
            x := 1;
            y := 2;
            x := 2;
            y := 3;
            end;


procedure BigSub;
    integer Global;
    integer array List [1:2};
    procedure Sub (Param);
        integer Param;
        begin
        Param := 3;
        Global := Global + 1;
        Param := 5
        end;
    begin
    List[1] := 2;
    List[2] :=2;
    Global := 1;
    Sub (List[Global]);
    end;

        normal swap procedure won't work: e.g.,  swap(a[i], i)
        advantage of flexibility
        disadvantage of confusion

    Parameter Passing Methods of the Major Languages
      1. FORTRAN
         - Before 77, pass-by-reference
         - 77 - scalar variables are often passed by 
            value-result
     2. ALGOL 60
         - Pass-by-name is default; pass-by-value is
           optional
      3. ALGOL W
          - Pass-by-value-result
      4. C
          - Pass-by-value

      5. Pascal and Modula-2
          - Default is pass-by-value; pass-by-reference
             is optional

      6. C++
           - Like C, but also allows reference type 
             parameters, which provide the efficiency of
             pass-by-reference with in-mode semantics

      7. Ada
          - All three semantic modes are available
          - If out, it cannot be referenced
          - If in, it cannot be assigned
      8. Java
          - Like C++, except only references

    Type-Checking Parameters
        Fortran 77 and C  no checking
        Pascal, FORTRAN90, Java and Ada do
        ANSI C and C++: choice is made by the user
    Implementing Parameter-Passing Methods
        parameter passing takes place through run-time stack
        pass by value  values copied into stack locations
        pass by result opposite
        value-result a combination of above
        reference passes address..for safety pass copy of 
                   constants
        thunks -- run-time resident code for every occurrence
        Ada simple in out and in are pass by copy
            complex given choice  may result in different results
            erroneous  depends on implementation method

    Design Considerations
        What about large arrays that are not to be modified?
        What about functional side effects?
        Efficiency
        One-way or two-way

Parameters That Are Subprogram Names
    Pass both name and description of subprogram parameters
    Ada disallows passing of subprograms -- generics instead
    Java does not allow method names to be passed
        as parameters
    C and C++ - pass pointers to functions; 
        parameters can be type checked


Problem of referencing environment
Possibilities:
       a. It is that of the subprogram that enacted it
           - Shallow binding

       b. It is that of the subprogram that declared it
           - Deep binding

       c. It is that of the subprogram that passed it
           - Ad hoc binding
             (Has never been used)  

procedure Sub1;
    procedure Sub2;
    ...
    end;
    procedure Sub3;
    ...
       call Sub4(Sub2);
    ...
    end;
    procedure Sub4(SubX);
    ...
        call SubX;
    end;
Sub3;
...
end;


    Referencing environment for Sub2 when called from Sub4 could 
    be:
1.  Sub4 --  Shallow binding
2.  Sub1 --  Deep binding
3.  Sub3 -- Never been used

Usually dynamic languages use shallow and block structured use 
        deep


Overloaded Subprograms
    subprogram has same name as another subprogram in same 
           referencing environment
    every instance must be unique in terms of its formal 
            parameters
    C++ and Ada have overloaded subprograms 
    built-in, and users can write their own overloaded 
    subprograms 

procedure Main is
    type Float_Vector is array (Integer range <>) of Float;
    type Int_Vector is array (Integer range <>) of Integer;
    ...
    procedure Sort (Float_List : in out Float_Vector;
            Lower_Bound  : in Integer;
            Upper_Bound : in Integer)  is
    ...
    end Sort;
    procedure Sort (Int_List : in out Int_Vector;
            Lower_Bound  : in Integer;
            Upper_Bound : in Integer)  is
    ...
    end Sort;


- A generic or polymorphic subprogram is one that
    takes parameters of different types on different
    activations

 - Overloaded subprograms provide ad hoc 
    polymorphism

 - A subprogram that takes a generic parameter that
   is used in a type expression that describes the 
   type of the parameters of the subprogram 
   provides parametric polymorphism
 
 - Examples of parametric polymorphism

   1. Ada
      - Types, subscript ranges, constant values, etc.,
        can be generic in Ada subprograms and 
         packages   
generic
type element is private;
type Index is (<>);
type Vector is array (Index) of Element;
procedure Generic_Sort (List) : in out Vector ) is
    Temp : Element;
    Lower_Bound : List'First;
    Upper_Bound : List'Range;
    Index_1: List'Range;
    Index_2 : List'Range;
    Outer_limit : List'Range;
    Inner_Begin : List'Range;
    begin
    Outer_Limit : Upper_Bound - 1;
    for Index_1 in Lower_Bound .. Outer_Limit loop
        Inner_Begin := Index_1 + 1;
        for Index_2 in Inner_Begin .. Upper_Bound loop
            if List(Index_1) > List(Index>2) then
                temp := List(Index_1);
                List(Index_1) := List(Index_2);
                List (Index_2) := Temp;
            end if;
        end loop; -- for Index_1
    end Loop; -- for Index_2
end Generic_Sort;


C++ template functions are instantiated implicitly
   when the function is named in a call or when its
   address is taken with the & operator

 - Another example:

template <class Type>
void generic_sort(Type list[], int len) {
  int top, bottom;
  Type temp;
  for (top = 0; top < len - 2; top++)
    for (bottom = top + 1; bottom < len - 1;
         bottom++) {
      if (list[top] > list[bottom]) {
        temp = list [top];
        list[top] = list[bottom];
        list[bottom] = temp;
       }  //** end of for (bottom = ...
 }  //** end of generic_sort


 - Example use:

float flt_list[100]; 
...
generic_sort(flt_list, 100); // Implicit 
                             // instantiation
Neither C# nor Java support – but may soon

Separate Compilation
    distinguished from independent which means needs no 
            information
        independent not checked for consistency
    need some kind of separate interface to do checking
    
Design Issues for Functions
1.  Are side effects allowed?
2.  What types of values can be returned?

    Functional Side Effects 
        parameters to functions should always be one-way
        (Aa can only have in parameters)
        shouldn't be able to address non-locals
        None of the popular languages do prevent this

    Types of Returned Values
        Pascal and FORTRAN only simple types
        C  any type but arrays and functions and you can use 
             pointers for this
       Ada can return any type
        C++ and Java - like C, but also allow classes to
         be returned
        

Accessing Nonlocal Environments
    nonlocal visible but not locally declared
    global visible in all units
        static scoping provides too much access
        program structure may capitalize on this to detriment of 
         engineering

    FORTRAN COMMON Blocks-- overlay of shared storage
        used because cannot nest subprograms and only way to 
         access external data
    STATIC SCOPING

    External Declarations and Modules
        Ada and Modula-2 use static scoping to share data
        also provide method to access only what data is needed
        with Module Name allows access to data and variables in Ada
        C  no nesting -- use variables which are external to allow 
             access
     Dynmaic scoping

User-Defined Overloaded Operators
    Allowed in C++ and Ada
    Increases reliance on programmer checking
Coroutines

 - A coroutine is a subprogram that has multiple
 entries and controls them itself

   - Also called symmetric control

 - A coroutine call is named a resume

 - The first resume of a coroutine is to its beginning, 
    but subsequent calls enter at the point just after
    the last executed statement in the coroutine

 - Typically, coroutines repeatedly resume each
    other, possibly forever

 - Coroutines provide quasiconcurrent execution of
    program units (the coroutines)
 
 - Their execution is interleaved, but not 
    overlapped