Subprograms: CSC 4330/6330 9-1 12/10 Programming Language Concepts

9.
SUBPROGRAMS
CSc 4330/6330 Programming Language Concepts
9-1
12/10
General Subprogram Characteristics
Characteristics of subprograms: Each subprogram has a single entry point. The calling program unit is suspended during subprogram execution. Control returns to the caller when execution of the subprogram terminates. Coroutines and concurrent units are similar to subprograms, but do not have all these characteristics. Fortran subprograms can have multiple entries. Object-oriented languages have methods instead of (or in addition to) subprograms.
9-2
12/10
Basic Definitions
A subprogram definition describes the interface to a subprogram as well as the actions of the subprogram. A subprogram call is an explicit request that a subprogram be executed. A subprogram is active if it has been called but has not yet returned. A subprogram header, the first line of a definition, serves several purposes: Indicates (often by a special word) the beginning of a subprogram definition, and may indicate whether the subprogram is a procedure or a function. Provides a name for the subprogram. May optionally specify a list of parameters. Example of a Fortran subroutine header: Subroutine Adder(parameters) Example of an Ada procedure header: procedure Adder(parameters) Example of a Python function header: def adder(parameters): Example of a C function header: void adder(parameters)
9-3
12/10
Basic Definitions (Continued)
In Python, function definitions are executable:

if : def fun(): else: def fun():
Which version of fun is defined will be determined when the if statement is executed. Ruby has only methods, not ordinary subprograms. However, methods can be defined outside a class (in which case they belong to the Object class) and then called in the same way as a C or C++ function. Luas functions are first-class, meaning that they can be stored in data structures, passed as parameters, and returned from functions. All Lua functions are anonymous, although they can be defined using syntax that makes it appear that they have names:
function cube(x) return x * x * x end
An alternative syntax more accurately illustrates that Lua functions are nameless:
cube = function (x) return x * x * x end
9-4
12/10
Basic Definitions (Continued)
The parameter profile of a subprogram is the number, order, and types of its formal parameters. The protocol of a subprogram is its parameter profile plus, if it is a function, its return type. Subprograms can have declarations as well as definitions. The declaration of a subprogram provides its protocol but does not include its body. Subprogram declarations allow the compiler to perform static type checking when a call of a subprogram precedes the subprograms definition. Function declarations are called prototypes in C and C++. Such declarations are often placed in header files. Many languages do not require that subprograms be declared before they are called.
9-5
12/10
Parameters
There are two ways for a subprogram to gain access to data that it needs: Through nonlocal variables (declared elsewhere but visible in the subprogram) Through parameters Parameter passing is more flexible, since different data can easily be supplied each time the subprogram is called. Extensive access to nonlocals can hurt reliability. Making variables visible to a subprogram that needs them often ends up also making them visible where access is not needed. Parameters in a subprogram header are called formal parameters. A subprogram call specifies the name of the subprogram and a list of actual parameters to be bound to the subprograms formal parameters.
9-6
12/10
Parameters (Continued)
In nearly all languages, the correspondence between actual and formal parameters is done by position: The first actual parameter is bound to the first formal parameter and so forth. Such parameters are called positional parameters. Passing parameters by position is a good technique for relatively short parameter lists. When parameter lists are long, however, it is easy to make mistakes in the order of parameters in the list. One solution to this problem is to provide keyword parameters, in which names of formal parameters are explicitly connected with actual parameters. Python example:
sumer(length = my_length, list = my_array, sum = my_sum)
sumer has formal parameters named length, list, and sum. The advantage of keyword parameters is that they can appear in any order in the actual parameter list. The chief disadvantage is that the user of the subprogram must know the names of the formal parameters. In addition to keyword parameters, Ada, Fortran 95, and Python allow positional parameters. The two notations can be mixed in a single call:
sumer(my_length, sum = my_sum, list = my_array)
After a keyword parameter appears in the list, all remaining parameters must be specified by keyword as well.
9-7
12/10
In Python, Ruby, C++, Fortran 95, Ada, and PHP, formal parameters can have default values. A default value is used if the corresponding actual parameter is omitted. Python example:
def compute_pay(income, exemptions = 1, tax_rate) pay = compute_pay(20000.0, tax_rate = 0.15)
After an actual parameter is omitted, keyword notation must be used for all remaining parameters. C++ does not support keyword parameters, so the rules for default parameters are different. Default parameters must appear last. Once a default parameter is omitted in a call, all remaining formal parameters must have default values. C++ version of compute_pay:
float compute_pay(float income, float tax_rate, int exemptions = 1); pay = compute_pay(20000.0, 0.15);
9-8
12/10
C, C++, Perl, JavaScript, and Lua allow programmers to write subprograms that have a variable number of parameters. Subprograms with a variable number of parameters, such as Cs printf function, tend to be convenient but error-prone. C# allows a method to accept a variable number of parameters of the same type:
public void DisplayList(params int[] list) { foreach (int next in list) { Console.WriteLine("Next value {0}", next); } }
A call of DisplayList can pass either an array or a list of expressions:

int[] myList = {2, 4, 6, 8, 10, 12}; DisplayList(myList); DisplayList(2, 4, 3 * x - 1, 17);
In the second call, the compiler places the arguments in an array and passes the array to DisplayList.
9-9
12/10
Rubys parameters are complicated but highly flexible. A list of actual parameters begins with individual expressions, whose values are bound to the corresponding formal parameters. These expressions can be followed by a list of key => value pairs, which are placed in a hash. A reference to that hash is bound to the next formal parameter. A formal parameter preceded by an asterisk is called an array formal parameter. All remaining actual parameters are collected into an array, which is bound to this formal parameter. If the actual parameter that corresponds to the array formal parameter is an array, it must also be preceded by an asterisk. Example:
list = [2, 4, 6, 8] def tester(p1, p2, p3, *p4) end tester('first', 'mon' => 72, 'tue' => 68, 'wed' => 59, *list)
Values of testers formal parameters: p1 is 'first' p2 is {'mon' => 72, 'tue' => 68, 'wed' => 59} p3 is 2 p4 is [4, 6, 8]
9-10
12/10
Pythons parameters are similar to Rubys. The initial formal parameters correspond to individual actual parameters. If a formal parameter is preceded by an asterisk, it represents a tuple. This parameter receives all non-keyword actual parameters beyond those corresponding to the initial parameters. If the last formal parameter is preceded by two asterisks, it represents a dictionary. The corresponding actual parameters are key = value pairs. Example:
def funl(p1, p2, *p3, **p4): funl(2, 4, 6, 8, mon=68, tue=72, wed=77)
Values of fun1s formal parameters: p1 is 2 p2 is 4 p3 is (6, 8) p4 is {'mon': 68, 'tue': 72, 'wed': 77} In a Lua parameter list, three periods (...) indicates a variable number of parameters. These parameters can be treated as an array:
function multiply(...) local product = 1 for i, next in ipairs{...} do product = product * next end return product end
Alternatively, the parameters represented by ... can be assigned to a list of variables:

function doit(...) local a, b, c = ... end
The three periods may appear at the end of a list of named formal parameters.
9-11
12/10
Ruby Blocks
In Ruby, a block of statements can be passed to a method. The block is enclosed within braces or a do-end pair and placed on the same line as the method call, just after the call itself. Blocks can have formal parameters. which are listed between vertical bars. A block that has been passed to a subprogram is called with a yield statement, which consists of the word yield followed by a list of actual parameters. The value returned from a block (to the yield that called it) is the value of the last expression evaluated in the block. Blocks are often used to process the elements of a data structure, but they can be used with any method:
# A method to compute and yield Fibonacci numbers up to a # limit def fibonacci(last) first, second = 1, 1 while first <= last yield first first, second = second, first + second end end # Call fibonacci with a block to display the numbers puts "Fibonacci numbers less than 100 are:" fibonacci(100) {|num| print num, " "} puts # Output a newline # Call it again to sum the numbers and display the sum sum = 0 fibonacci(100) {|num| sum += num} puts "Sum of the Fibonacci numbers less than 100 is: #{sum}"
Output:
Fibonacci numbers less than 100 are: 1 1 2 3 5 8 13 21 34 55 89 Sum of the Fibonacci numbers less than 100 is: 232
A block is bound to the environment in which it is defined, including the local variables and the current object, regardless of where the block is called.
9-12
12/10
Procedures and Functions
There are two kinds of subprograms: procedures and functions. A procedure call is a statement, not an expression; it does not have a return value. A procedure can return results to its caller in two ways: By changing variables that are global to the procedure. By changing the values of parameters passed to the procedure. A function call returns a value. This value is returned to the calling code, effectively replacing the call itself. Some languages, including Fortran and Ada, provide both functions and procedures. The C-based languages have only functions. However, functions behave like procedures if their return type is void.
9-13
12/10
Design Issues for Subprograms
Subprograms are complex language features, so their design involves a lengthy list of issues: Are local variables statically or dynamically allocated? Can subprogram definitions appear in other subprogram definitions? What parameter-passing method or methods are used? Are the types of the actual parameters checked against the types of corresponding formal parameters? If subprograms can be passed as parameters and subprograms can be nested, what is the referencing environment of a passed subprogram? Can subprograms be overloaded? Can subprograms be generic?
9-14
12/10
Local Variables
Subprograms can define their own variables, called local variables. Local variables can be either static or stack-dynamic. In most contemporary imperative languages, local variables are stack-dynamic by default. In C and C++, local variables are stack-dynamic unless declared to be static. Ada subprograms and the methods of Java and C# have only stack-dynamic local variables. Fortran 95 implementors can choose whether local variables are to be static or stack-dynamic. Programmers can force local variables to be static by using Save. In Fortran 95, a subprogram can be explicitly specified to be recursive, in which case its local variables are stack-dynamic by default. Example of a Fortran recursive subroutine:
Recursive Subroutine Sub() Integer :: Count Save, Real :: Sum End Subroutine Sub
In Python, attempting to assign to a global variable from within a method causes a new local variable to be created with the same name. All local variables are stack-dynamic. All Lua variables are global unless declared local:
local sum
local declarations may appear in any block, including the body of a function.
9-15
12/10
Nested Subprograms
The idea of nesting subprograms originated with Algol 60. For years, the only languages that allowed nested subprograms were direct descendants of Algol 60, including Algol 68, Pascal, and Ada. The C-based languages do not support nesting, but some newer languages do, including JavaScript, Python, Ruby, and Lua.
9-16
12/10
Parameter-Passing Methods
Parameter-passing methods are ways in which parameters are transmitted to and/ or from called subprograms. Possible semantics for formal parameters: In mode: Data is received from the corresponding actual parameter. Out mode: Data is sent to the actual parameter. Inout mode: Data is both sent and received. Conceptual models of data transfer during parameter transmission: An actual value is copied (to the caller, to the callee, or both ways). An access path (usually a pointer or reference) is transmitted. Models of parameter passing when values are copied:
9-17
12/10
Pass-By-Value
Several models have been developed to implement the three basic parameter transmission modes. One implementation model for in-mode semantics is called pass-by-value. The value of the actual parameter is used to initialize the corresponding formal parameter, which then serves as a local variable. Pass-by-value is normally implemented by copy, since data accesses often are more efficient. Pass-by-value could be implemented by transmitting an access path, but that would require the language to protect the actual parameter from being changed. If copies are used, additional storage is required for the formal parameter, and the actual parameter must be copied into the formal parameter. The cost of the additional storage and copying can be high if the parameter is large. For scalars, however, pass-by-value is fast in terms of both linkage cost and access time.
9-18
12/10
Pass-By-Result
Pass-by-result is an implementation model for out-mode parameters. A pass-by-result formal parameter behaves like a local variable. Just before control returns to the caller, the parameters value is copied to the callers actual parameter. Pass-by-result requires that the actual parameter be a variable. Pass-by-result has the advantages and disadvantages of pass-by-value, plus some additional disadvantages. As with pass-by-value, the difficulty of implementing pass-by-result by transmitting only an access path usually results in it being implemented by data copy. It is important to ensure that the initial value of the actual parameter is not used in the called subprogram. Pass-by-result requires the extra storage and the copy operations that are required by pass-by-value.
9-19
12/10
Pass-By-Result (Continued)
An additional problem with the pass-by-result model is that there can be an actual parameter collision. Example:
sub(p1, p1);
sub might assign different values to the formal parameters. When sub returns, the order in which the formal parameters are copied to the actual parameters will determine the value of p1, potentially causing portability problems. An example using C# syntax:
void Fixer(out int x, out int y) { x = 17; y = 35; } Fixer(out a, out a);
The value of a after the call could be either 35 or 17. Yet another problem: The implementor may be able to choose whether to evaluate the address of the actual parameter at the time of the call or at the time of the return. Different choices could make programs nonportable. Another example using C# syntax:
void DoIt(out int x, out int index) { x = 17; index = 42; } sub = 21; DoIt(out list[sub], out sub);
The value 17 is assigned either to list[21] or list[42].
9-20
12/10
Pass-By-Value-Result
Pass-by-value-result is a combination of pass-by-value and pass-by-result. It is an implementation model for inout-mode parameters in which actual values are moved. With pass-by-value result, the value of the actual parameter is used to initialize the formal parameter, which then acts as a local variable. At subprogram termination, the value of the formal parameter is sent back to the actual parameter. Pass-by-value-result is sometimes called pass-by-copy because the actual parameter is copied to the formal parameter at subprogram entry and then copied back at subprogram termination. Disadvantages of pass-by-value-result: Like pass-by-value and pass-by-result, requires extra storage for parameters and time for copying values. Like pass-by-result, has problems associated with the order in which values are assigned to actual parameters.
9-21
12/10
Pass-By-Reference
Pass-by-reference is a second implementation model for inout-mode parameters. Pass-by-reference transmits an access path, usually just an address, to the called subprogram. Pass-by-reference allows the called subprogram to access the actual parameter in the caller. In effect, the actual parameter is shared with the called subprogram. The advantage of pass-by-reference is its time and space efficiency. Duplicate space is not required, nor is any copying. Disadvantages of pass-by-reference: Access to parameters will be slower because an additional level of indirect addressing is required. If only one-way communication to the called subprogram is required, inadvertent and erroneous changes may be made to the actual parameter. Aliases can be created, which are harmful to readability and thus to reliability. Ways in which aliases can be created when parameters are passed by reference: Collisions between actual parameters Collisions between array elements Collisions between array elements and whole arrays Collisions between formal parameters and nonlocal variables Example of a collision between actual parameters:
void fun(int& first, int& second); fun(total, total);
first and second will be aliases.
9-22
12/10
Pass-By-Reference (Continued)
Example of a collision between array elements:

fun(list[i], list[j]);
If i is equal to j, the formal parameters are aliases. Example of a collision between an array element and a whole array:
fun1(list[i], list);
fun1 can access all elements of list through the second parameter; it can access a single element of list through its first parameter. Example of a collision between a formal parameter and a nonlocal variable:
int global; int main() { sub(global); } void sub(int& param) { }
Inside sub, param and global are aliases. Aliasing can be avoided if pass-by-value-result is used instead of pass-by-reference. However, other problems sometimes occur instead.
9-23
12/10
Pass-By-Name
Pass-by-name is an inout-mode parameter transmission method that does not correspond to a single implementation model. With pass-by-name, the actual parameter is, in effect, textually substituted for each occurrence of the corresponding formal parameter. A pass-by-name formal parameter is bound to an access method at the time of the subprogram call, but the actual binding to a value or an address is delayed until the formal parameter is assigned or referenced. An Algol 60 function that uses pass-by-name for the j and Ej parameters:
real procedure Sum(j, lo, hi, Ej); value lo, hi; integer j, lo, hi; real Ej; begin real S; S := 0; for j := lo step 1 until hi do S := S + Ej; Sum := S end;
A sample call of Sum:

Sum(i, 1, n, x[i] * i)
Sum returns the result of summing x[i] * i for all i from 1 to n.
9-24
12/10
Implementing Parameter-Passing Methods
In most contemporary languages, parameter communication takes place through the run-time stack. Pass-by-value parameters have their values copied into stack locations. The stack locations then serve as storage for the corresponding formal parameters. Pass-by-result parameters are implemented as the opposite of pass-by-value. The values assigned to the pass-by-result actual parameters are placed in the stack, where they can be retrieved by the caller when the subprogram returns. Pass-by-value-result parameters can be implemented as a combination of passby-value and pass-by-result. The stack location for such a parameter is initialized by the call and is then used like a local variable in the called subprogram. Pass-by-reference parameters are perhaps the simplest to implement. Regardless of the type of the actual parameter, only its address must be placed on the stack. When a literal is passed by reference, the address of the literal is transmitted. If the actual parameter is an expression, the compiler must generate code to evaluate the expression just before control is transferred to the subprogram. The address of the memory cell containing the expressions value is put on the stack. The compiler must be sure to prevent the called subprogram from changing parameters that are literals or expressions. Access to a formal parameter in the called subprogram is by indirect addressing from the stack location containing the actual parameters address.
9-25
12/10
Implementing Parameter-Passing Methods (Continued)
Suppose that sub is called from main with the call sub(w, x, y, z), where w is passed by value, x is passed by result, y is passed by value-result, and z is passed by reference. Implementation of pass-by-value, -result, -value-result, and -reference, using the run-time stack:
A subtle but serious error can occur with pass-by-reference and pass-by-valueresult parameters if care is not taken in their implementation. The problem occurs if a program literal is passed to a subprogram that changes the value of its parameter. Changing the value of the literal may affect other parts of the program that use the same literal. This problem actually happened in many implementations of Fortran IV.
9-26
12/10
Parameter-Passing Methods of Some Common Languages
C uses pass-by-value, with pass-by-reference achieved by using pointers as parameters. C borrowed this approach from ALGOL 68. In C and C++, formal parameters can be const pointers, thereby protecting actual parameters from change. This allows pointer parameters to provide the efficiency of pass-by-reference with the one-way semantics of pass-by-value. In C++, reference types are often used for parameters. Reference parameters are implicitly dereferenced, and their semantics are pass-by-reference. C++ allows reference parameters to be declared const. Example:
void fun(const int& p1, int p2, int& p3) { }
p1 is pass-by-reference but cannot be changed within the function. p2 is pass-by-value. p3 is pass-by-reference. const parameters and in-mode parameters are not exactly alike. In most languages, an in-mode formal parameter can be assigned a new value; the value of the matching actual parameter is unchanged. const parameters cannot be assigned new values. Java parameters are passed by value. Although a Java method cannot assign to an object variable passed to it as a parameter, it can change the objects state.
9-27
12/10
Parameter-Passing Methods of Some Common Languages (Continued)
Ada provides three modes of parameter transmission, indicated by the reserved words in, out, and in out, where in is the default:
procedure Adder(A: in out Integer; B: in Integer; C: out Float)
In Ada, formal parameters declared to be out can be assigned but not referenced. in parameters can be referenced but not assigned. in out parameters can be both referenced and assigned. The Ada 83 language definition specifies that scalar parameters are to be passed by copy. In the case of formal parameters that are arrays or records, Ada 83 implementors were given the choice between pass-by-value-result and pass-by-reference. The two implementation methods can lead to different results: If pass-by-reference is used, it is possible that the actual parameter is also visible as a global, thereby creating an alias. If pass-by-value-result is used, aliasing is not possible. An additional problem is possible if the subprogram terminates via an exception. The actual parameter in the pass-by-value-result implementation will be unchanged. The pass-by-reference implementation may have changed the corresponding actual parameter before the exception occurred. Ada 83 programs that produce different results depending on how in out parameters are implemented are said to be erroneous. The rules for implementing parameter-passing are slightly different in Ada 95, but implementors are still allowed to choose between pass-by-copy and pass-byreference for arrays and records.
9-28
12/10
Parameter-Passing Methods of Some Common Languages (Continued)
Fortran 95s formal parameters can be declared to be in, out, or inout mode, using the Intent attribute:
Subroutine Adder(A, B, C) Integer, Intent(Inout) :: A Integer, Intent(In) :: B Integer, Intent(Out) :: C
The default parameter-passing method of C# is pass-by-value. Pass-by-reference can be specified in C# by preceding both a formal parameter and its corresponding actual parameter with ref:
void sumer(ref int oldSum, int newOne) { } sumer(ref sum, newValue);
C# supports out-mode parameters, which are pass-by-reference parameters that do not need initial values. PHPs parameter passing is similar to that of C#, except that either the actual parameter or the formal parameter can specify pass-by-reference. Pass-by-reference is specified by preceding one or both of the parameters with an ampersand. In Perl, all actual parameters are implicitly placed in a predefined array named @_. If the called subprogram changes an element of @_, that change is reflected in the corresponding actual parameter. Python and Ruby support pass-by-assignment, in which each actual parameter (a reference to an object) is assigned to the corresponding formal parameter. An actual parameter cannot be changed within a subprogram, but the object to which it refers can modified (if it is not immutable).
9-29
12/10
Type-Checking Parameters
Software reliability demands that the types of actual parameters be checked for consistency with the types of the corresponding formal parameters. Fortran 77 and original C did not require parameter type checking; most later languages require it. Perl, JavaScript, and PHP do not, however. In original C, neither the number of parameters nor their types were checked. In C89, whether or not type checking is done depends how formal parameters are declared. One technique comes from original C. The names of formal parameters are listed in parentheses and the type declarations for them follow:
double sin(x) double x; { }
No type checking is done when sin is called. In the following call, the fact that count has the wrong type will not be detected:
double value; int count; value = sin(count);
9-30
12/10
Type-Checking Parameters (Continued)
The alternative is called the prototype method, in which the types of formal parameters are included in the parameter list:
double sin(double x) { }
The call
value = sin(count);
will now work correctly. count has the wrong type, but it will be coerced to the proper type. If coercion is not possible or if the number of parameters is wrong, the compiler will detect the error. In C99 and C++, prototype form is required for all functions. However, type checking is not possible for functions whose prototype includes an ellipsis:
int printf(const char *format_string, ...);
A call of printf must include at least one parameter (a string), possibly followed by additional parameters. Codes embedded in the string describe the other parameters:
printf("The sum is %d\n", sum);
When pass-by-reference is used, as with C# ref parameters, the type of an actual parameter must match the type of the corresponding formal parameter. Languages that allow variables to store values of arbitrary types, such as Python and Ruby, do not type-check parameters.
9-31
12/10
Multidimensional Arrays as Parameters
Accessing a multidimensional array passed as a parameter requires the subprogram to use a mapping function. Building the mapping function can be tricky in languages that allow array parameters of unknown size. C and C++ allow one-dimensional array parameters of unknown size. However, a two-dimensional array parameter must have a fixed number of columns. Example:
void fun(int matrix[][10]) { } int main() { int mat[5][10]; fun(mat); }
Arrays in C and C++ are stored in row-major order, so the mapping function depends on the number of columns but not the number of rows. To simulate two-dimensional array parameters with an unknown number of columns, C and C++ programmers sometimes pass a pointer to the array along with the number of rows and columns in the array:
void fun(float *mat_ptr, int num_rows, int num_cols);
fun will use its own mapping function to access elements of the array. The following statement copies the value of x to the [row][col] element of the array:
*(mat_ptr + (row * num_cols) + col) = x;
9-32
12/10
Multidimensional Arrays as Parameters (Continued)
The resulting code is difficult to read and error-prone. Defining a macro that computes the storage-mapping function can help:
#define mat(r, c) (*(mat_ptr + ((r) * num_cols) + (c)))
Using the macro, the assignment to the [row][col] element can be written
mat(row, col) = x;
Ada allows the definition of an array type to omit index ranges; the result is an unconstrained array type. Those ranges are supplied later, when the type is used to declare variables. Example:
type Mat_Type is array (Integer range <>, Integer range <>) of Float; Mat_1: Mat_Type(1..100, 1..20);
In Ada, formal parameters can be unconstrained arrays. A subprogram with an unconstrained array parameter has access to the index range(s) of the actual parameter. Example of a function whose parameter is an unconstrained array:
function Sumer(Mat: in Mat_Type) return Float is Sum: Float := 0.0; begin for Row in Mat'range(1) loop for Col in Mat'range(2) loop Sum := Sum + Mat(Row, Col); end loop; end loop; return Sum; end Sumer;
The range attribute represents the range of values for the specified subscript.
9-33
12/10
In Fortran, array parameters must be declared after the subroutine header:

Subroutine Sub(Matrix, Rows, Cols, Result) Integer, Intent(In) :: Rows, Cols Real, Dimension(Rows, Cols), Intent(In) :: Matrix Real, Intent(Out) :: Result End Subroutine Sub
The subscript bounds are irrelevant for one-dimensional array parameters. But for multidimensional arrays, the bounds are used to build the storage-mapping function. In the case of Sub, the value of Rows is important, because Fortran stores arrays in column-major order.
9-34
12/10
In Java and C#, arrays are objects. Arrays are normally one-dimensional, but elements can be arrays. Each array contains a named constant (length in Java and Length in C#) that is set to the length of the array when the array object is created. The formal parameter for a two-dimensional array is declared with two sets of empty brackets. A Java example:
float sumer(float mat[][]) { float sum = 0.0f; for (int row = 0; row < mat.length; row++) { for (int col = 0; col < mat[row].length; col++) { sum += mat[row][col]; } } return sum; }
Each row of the array is a separate one-dimensional array. Rows are not required to have the same length.
9-35
12/10
Examples of Parameter Passing
C example:
void swap1(int a, int b) { int temp = a; a = b; b = temp; } swap1(c, d);
Actions of swap1:
a = c b = d temp = a a = b b = temp - Move first parameter value in - Move second parameter value in
Although a ends up with ds value and b ends up with cs value, the values of c and d are unchanged.
9-36
12/10
Examples of Parameter Passing (Continued)
C version of swap1 modified to achieve the effect of pass-by-reference:

void swap2(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } swap2(&c, &d);
The swap operation is successful this time: the values of c and d are interchanged. Actions of swap2:
a = &c b = &d temp = *a *a = *b *b = temp - Move first parameter address in - Move second parameter address in
C++ version of swap2, using reference parameters:

void swap2(int& a, int& b) { int temp = a; a = b; b = temp; }
Writing a swap method is not possible in Java, which has neither pointers nor C++-style references.
9-37
12/10
Ada-like swapping procedure that uses pass-by-value-result parameters:

procedure swap3(a: in out Integer, b: in out Integer) is temp: Integer; begin temp := a; a := b; b := temp; end swap3; swap3(c, d);
Actions of swap3:
addr_c = &c addr_d = &d a = *addr_c b = *addr_d temp = a a = b b = temp *addr_c = a *addr_d = b Move Move Move Move first parameter address in second parameter address in first parameter value in second parameter value in
- Move first parameter value out - Move second parameter value out
The procedure operates correctly. If the call is changed to

swap3(i, list[i]);
then the actions are

addr_i = &i addr_listi = &list[i] a = *addr_i b = *addr_listi temp = a a = b b = temp *addr_i = a *addr_listi = b Move Move Move Move first parameter address in second parameter address in first parameter value in second parameter value in
- Move first parameter value out - Move second parameter value out
Again, the procedure operates correctly, in this case because the addresses of the parameters are computed at the time of the call.
9-38
12/10
Pass-by-value-result is equivalent to pass-by-reference, except when aliasing is involved. Example of aliasing using C syntax:
int i = 3; /* i is a global variable */
void fun(int a, int b) { i = b; } int main() { int list[10]; list[i] = 5; fun(i, list[i]); }
If pass-by-reference is used, i and a are aliases. If pass-by-value-result is used, i and a are not aliases. Actions of fun, assuming pass-by-value-result:
addr_i = &i addr_listi = &list[i] a = *addr_i b = *addr_listi i = b *addr_i = a *addr_listi = b Move Move Move Move Sets Move Move first parameter address in second parameter address in first parameter value in second parameter value in i to 5 first parameter value out second parameter value out
The assignment to the global i in fun changes its value from 3 to 5, but the copy back of the first formal parameter sets it back to 3. If pass-by-reference is used, i remains 5. Because the address of the second parameter is computed when fun is called, any change to the global i has no effect on the address used to return the value of list[i].
9-39
12/10
Parameters That Are Subprograms
Some programming situations are most conveniently handled if subprogram names can be passed as parameters to other subprograms. One issue is the matter of checking parameters when the subprogram is called. In C and C++, functions cannot be passed as parameters, but pointers to functions can. Such a pointer can point only to functions with a specific protocol, which allows type checking when a function is later called through the pointer. Fortran 95 has a mechanism for providing parameter types for subprograms that are passed as parameters, and type checking must be performed when these subprograms are called. Ada 83 does not allow subprograms to be passed as parameters, although generic subprograms serve as a partial substitute. Ada 95 provides pointers to subprograms; these pointers can be passed as parameters and stored in variables.
9-40
12/10
Parameters That Are Subprograms (Continued)
In languages that allow nested subprograms, there is another issue: When a subprogram is passed as a parameter, what referencing environment should be used for executing the passed subprogram? Possibilities: The environment of the statement that calls the passed subprogram (shallow binding). The environment in which the passed subprogram was defined (deep binding). The environment of the call that passed the subprogram as an actual parameter (ad hoc binding). JavaScript example:
function sub1() { var x; function sub2() { alert(x); // Creates a dialog box with the value of x }; function sub3() { var x; x = 3; sub4(sub2); }; function sub4(subx) { var x; x = 4; subx(); }; x = 1; sub3(); };
The output of sub2 depends on the type of binding: Type of binding Shallow binding Deep binding Ad hoc binding x in sub2 is bound to x in sub4 sub1 sub3 Output 4 1 3
9-41
12/10
Parameters That Are Subprograms (Continued)
Ad hoc binding has never been used, because the environment in which the procedure appears as a parameter has no natural connection to the passed subprogram. Static-scoped languages with nested subprograms use deep binding. Shallow binding is not appropriate because of static binding of variables. Some dynamic-scoped languages use shallow binding.
9-42
12/10
Overloaded Subprograms
An overloaded subprogram is a subprogram that has the same name as another subprogram in the same scope. Each version of an overloaded subprogram must have a unique protocol: it must differ from other versions in the number, order, or types of its parameters, or in its return type if it is a function. The meaning of a call to an overloaded subprogram is determined by the actual parameter list (and possibly the type of the returned value). In languages such as C++, disambiguation of overloaded calls is greatly complicated by parameter coercions. If two or more subprograms have parameter profiles that can be matched through coercions, the compiler ranks them and chooses the best match. In Ada, two overloaded functions can have the same parameter profile, differing only in their return types. Example:
A, B: Integer; A := B + Fun(7);
Assume that there are two versions of Fun, both of which take an Integer parameter. The version that returns an Integer value will be called. Because C++, Java, and C# allow mixed-mode expressions, the return type of a function (or method) is not taken into account for overloading purposes. Overloaded subprograms that have default parameters can lead to ambiguous subprogram calls. C++ example:
void fun(float b = 0.0); void fun(); fun(); // Ambiguous
9-43
12/10
Generic Subprograms
One way to increase software reusability is to lessen the need to create different subprograms that implement the same algorithm on different types of data. A polymorphic subprogram will accept parameters of different types during different calls. Overloaded subprograms provide a kind of polymorphism called ad hoc polymorphism. However, there is no guarantee that subprograms with the same name behave similarly. Python and Ruby provide a more general kind of polymorphism. Since formal parameters do not have types, a subprogram will work for any type of actual parameter as long as operations performed on the parameter are defined. Parametric polymorphism is provided by a subprogram that takes generic parameters describing the types of the subprograms parameters. Different instantiations of the subprogram can be given different generic parameters. Parametrically polymorphic subprograms are often called generic subprograms. Both Ada and C++ provide a kind of compile-time parametric polymorphism. Java 5.0 and C# 2.0 also support parametric polymorphism but in a different way.
9-44
12/10
Generic Subprograms in Ada
Ada allows the creation of multiple versions of a program unit, with each version accepting parameters of different types. Program units of this sort are sometimes called generic units. Example of a generic sorting procedure in Ada:
generic type Index_Type is (<>); type Element_Type is (<>); type Vector is array (Index_Type range <>) of Element_Type; procedure Generic_Sort(List: in out Vector); procedure Generic_Sort(List: in out Vector) is Temp: Element_Type; begin for Top in List'First..Index_Type'Pred(List'Last) loop for Bottom in Index_Type'Succ(Top)..List'Last loop if List(Top) > List(Bottom) then Temp := List(Top); List(Top) := List(Bottom); List(Bottom) := Temp; end if; end loop; end loop; end Generic_Sort;
The declarations
type Index_Type is (<>); type Element_Type is (<>);
indicate that Index_Type and Element_Type must be discrete types.
9-45
12/10
Generic Subprograms in Ada (Continued)
A generic procedure is a template for an actual procedure; no code is generated by the compiler until it is instantiated. Example of instantiating a generic procedure:
procedure Integer_Sort is new Generic_Sort( Index_Type => Integer; Element_Type => Integer; Vector => Int_Array);
The original version of Generic_Sort works only for arrays whose elements belong to a discrete type. Generic_Sort can be made more general by including a comparison function among its generic parameters.
generic type Index_Type is (<>); type Element_Type is private; type Vector is array (Index_Type range <>) of Element_Type; with function "<"(X, Y: Element_Type) return Boolean; procedure Generic_Sort(List: in out Vector);
The declaration
type Element_Type is private;
indicates that Element_Type can be any type that supports assignment and equality testing.
9-46
12/10
Generic Subprograms in Ada (Continued)
Although Ada 83 does not allow subprograms to be passed as parameters, it is sometimes possible to get a similar effect by writing a generic subprogram that has another subprogram as a parameter. Example:
generic with function Fun(X: Float) return Float; procedure Integrate(Lowerbd: in Float; Upperbd: in Float; Result: out Float); procedure Integrate(Lowerbd: in Float; Upperbd: in Float; Result: out Float) is Funval: Float; begin Funval := Fun(Lowerbd); end Integrate;
An instantiation of Integrate:
procedure Integrate_Fun1 is new Integrate(Fun => Fun1);
9-47
12/10
Generic Functions in C++
Generic functions in C++ are called function templates. A function template looks like an ordinary function definition, except for an extra line at the beginning: template <template parameters> Each template parameter normally has one of the following forms and represents an unknown type: class identifier typename identifier A template parameter can also represent a data value or a class template. Example:
template <class Type> Type max(Type first, Type second) { return first > second ? first : second; }
The max template can be instantiated for any type for which the > operator is defined. If Type is int, the resulting function definition would be
int max(int first, int second) { return first > second ? first : second; }
9-48
12/10
Generic Functions in C++ (Continued)
Macros are an alternative to function templates. A max macro would have the following definition:
#define max(a, b) ((a) > (b) ? (a) : (b))
The max macro will accept parameters of any numeric type, but it does not always work correctly if called with a parameter that has a side effect. For example, the call
max(x++, y)
produces
((x++) > (y) ? (x++) : (y))
Whenever x is greater than y, x will be incremented twice. A C++ function template is implicitly instantiated when it is called or when its address is taken with the & operator. Example:
int a, b, c; char d, e, f; c = max(a, b); f = max(d, e);
max is instantiated twice, once for int parameters and once for char parameters.
9-49
12/10
Generic Functions in C++ (Continued)
The Ada generic sorting subprogram translated to C++:

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; } }
Some changes were necessary because C++ array subscripts are restricted to integers, with the lower bound fixed at zero. Example call of generic_sort:
float flt_list[100]; generic_sort(flt_list, 100);
9-50
12/10
Generic Methods in Java 5.0
Java 5.0 supports generic types and methods. Differences between Javas generic methods and generic subprograms in Ada and C++: Javas generic parameters must be classes. There is only one copy of the code for a Java generic method. Java allows restrictions (called bounds) on generic parameters. Example of a generic method:
public static <T> T doIt(T[] list) { }
The value of the type parameter T is inferred when doIt is called:

result = doIt(myList);
A version of doIt that uses a bound:

public static <T extends Comparable> T doIt(T[] list) { }
T must be a class that implements the Comparable interface (extends in this context can also mean implements). Generic methods can have more than one generic parameter.
9-51
12/10
Generic Methods in Java 5.0 (Continued)
A Java generic class has one or more type parameters. When the class is used, specific types are substituted for these parameters:
ArrayList<Integer> myArray = new ArrayList<Integer>();
Java 5.0 also supports wildcard types:

void printCollection(Collection<?> c) { for (Object e: c) { System.out.println(e); } }
The generic parameter is a collection of any (single) object type. Wildcard types can be bounded:
public void drawAll(ArrayList<? extends Shape> things){ }
9-52
12/10
Generic Methods in C# 2.0
Generic methods in C# 2.0 are similar to those in Java 5.0, except that wildcard types are not supported. Example of a generic method:
public static T DoIt<T>(T p1) { }
The value of the type parameter T can be specified when DoIt is called:
int myInt = DoIt<int>(17); string myStr = DoIt<string>("apples");
However, it can often be inferred by the compiler:

int myInt = DoIt(17); string myStr = DoIt("apples"); // Calls DoIt<int> // Calls DoIt<string>
9-53
12/10
Design Issues for Functions
Design issues that are specific to functions: Are side effects allowed? What types of values can be returned? How many values can be returned? Because of the problems of side effects when functions are called in expressions, parameters to functions should always be in-mode. Some languages (Ada, in particular) require function parameters to be in-mode. In most other languages, functions can have either pass-by-value or pass-by-reference parameters, allowing functions with side effects and aliasing. Most imperative programming languages restrict the types that can be returned by functions. C functions can return all types except arrays and functions. Returning pointers to arrays and functions is allowed, however. C++ also allows functions to return objects. Ada allows a function to return values of any single type. Python, Ruby, and Lua allow a subprogram to return values of arbitrary types. In most languages, only a single value can be returned from a function. Ruby allows a return statement to specify more than one expression. The return value is an array containing the values of all the expressions. Lua also allows multiple values in a return statement:
return 3, sum, index
The return values can be saved in variables by using multiple assignment:

a, b, c = fun()
9-54
12/10
User-Defined Overloaded Operators
Ada, C++, Python, and Ruby allow the programmer to overload operators. An Ada function that overloads * to compute the dot product of two arrays of equal length:
function "*"(A, B: in Vector_Type) return Integer is Sum: Integer := 0; begin for Index in A'range loop Sum := Sum + A(Index) * B(Index); end loop; return Sum; end "*";
Vector_Type is assumed to be an array type with Integer elements. Prototype for a C++ function that overloads * to compute the dot product:
int operator*(const vector& a, const vector& b);
9-55
12/10
Coroutines
A coroutine differs from a subprogram in several ways. Coroutines behave more like equals. Coroutines can have multiple entry points. Coroutines maintain their status between activations, so they must be historysensitive. Since control is often transferred to a coroutine at a point other than its beginning, the invocation of a coroutine is called a resume, not a call. A resume statement can be used both to start and to restart the execution of a coroutine. Like ordinary subprograms, only one coroutine can be executing at a given time. A coroutine may execute partially and then transfer control to another coroutine. When restarted, a coroutine resumes execution just after the statement it used to transfer control elsewhere. This sort of interleaved execution sequence is sometimes called quasi-concurrency. Typically, coroutines are created in an application by a program unit called the master unit, which is not a coroutine. When created, coroutines execute their initialization code and then return control to that master unit. After all related coroutines are constructed, the master program resumes one of the coroutines, and the coroutines then resume each other in some order.
9-56
12/10
Coroutines (Continued)
Example of interaction between coroutines named A and B, where the execution of A is started by the master unit:
An alternative execution sequence, where B is started by the master unit:
9-57
12/10
Coroutines (Continued)
Coroutines often have loops containing a resume. Example:
SIMULA 67 was the first high-level programming language to support coroutines. Among later languages, only Modula-2 and a few others allow coroutines. Lua is the only contemporary language that provides coroutines.
9-58
12/10

Subprograms: CSC 4330/6330 9-1 12/10 Programming Language Concepts

Uploaded by

Copyright:

Available Formats

Subprograms: CSC 4330/6330 9-1 12/10 Programming Language Concepts

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Subprograms: CSC 4330/6330 9-1 12/10 Programming Language Concepts

Uploaded by

Copyright:

Available Formats

9.

CSc 4330/6330 Programming Language Concepts

General Subprogram Characteristics

CSc 4330/6330 Programming Language Concepts

CSc 4330/6330 Programming Language Concepts

Basic Definitions (Continued)

In Python, function definitions are executable:

CSc 4330/6330 Programming Language Concepts

Basic Definitions (Continued)

CSc 4330/6330 Programming Language Concepts

CSc 4330/6330 Programming Language Concepts

CSc 4330/6330 Programming Language Concepts

CSc 4330/6330 Programming Language Concepts

A call of DisplayList can pass either an array or a list of expressions:

CSc 4330/6330 Programming Language Concepts

CSc 4330/6330 Programming Language Concepts

Alternatively, the parameters represented by ... can be assigned to a list of variables:

CSc 4330/6330 Programming Language Concepts

CSc 4330/6330 Programming Language Concepts

Procedures and Functions

CSc 4330/6330 Programming Language Concepts

Design Issues for Subprograms

CSc 4330/6330 Programming Language Concepts

CSc 4330/6330 Programming Language Concepts

CSc 4330/6330 Programming Language Concepts

CSc 4330/6330 Programming Language Concepts

CSc 4330/6330 Programming Language Concepts

CSc 4330/6330 Programming Language Concepts

The value 17 is assigned either to list[21] or list[42].

CSc 4330/6330 Programming Language Concepts

CSc 4330/6330 Programming Language Concepts

first and second will be aliases.

CSc 4330/6330 Programming Language Concepts

Example of a collision between array elements:

CSc 4330/6330 Programming Language Concepts

A sample call of Sum:

Sum returns the result of summing x[i] * i for all i from 1 to n.

CSc 4330/6330 Programming Language Concepts

Implementing Parameter-Passing Methods

CSc 4330/6330 Programming Language Concepts

Implementing Parameter-Passing Methods (Continued)

CSc 4330/6330 Programming Language Concepts

Parameter-Passing Methods of Some Common Languages

CSc 4330/6330 Programming Language Concepts

Parameter-Passing Methods of Some Common Languages (Continued)

CSc 4330/6330 Programming Language Concepts

Parameter-Passing Methods of Some Common Languages (Continued)

CSc 4330/6330 Programming Language Concepts

CSc 4330/6330 Programming Language Concepts

Type-Checking Parameters (Continued)

CSc 4330/6330 Programming Language Concepts

Multidimensional Arrays as Parameters

CSc 4330/6330 Programming Language Concepts

Multidimensional Arrays as Parameters (Continued)

CSc 4330/6330 Programming Language Concepts

Multidimensional Arrays as Parameters (Continued)

In Fortran, array parameters must be declared after the subroutine header:

CSc 4330/6330 Programming Language Concepts

Multidimensional Arrays as Parameters (Continued)