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