Subprograms
Programming Language Pragmatics
CMSC 331
1
Fundamentals of Subprograms
Each subprogram has a single entry point
The calling program is suspended during execution of the called subprogram
Control always returns to the caller when the called subprogram’s execution
terminates
Func_A
{
…
call B();
…
call B();
…
}
Func_B
{
…
…
}
Func_C
{
…
call B();
…
call B();
…
}
2
Terminologies
int Adder(int a, int b);
…
int Adder(int a, int b)
{ return a+b; }
…
void main()
{
int x;
x = Adder(30, 20);
}
with return values: functions
without return values: procedures
formal parameters
real parameters
caller
callee
3
Subprogram Syntax in Different Languages
Declaration of procedure
Ada:
C/C++:
procedure Adder(…)
void Adder(…)
Binding actual/formal parameters
 Most languages use positional parameters
 Some support keyword parameters
sum(length=> my_length, list=> my_list);
Advantage: specify the parameters in any order
4
Default Values of Parameters
Support absent actual parameters in Ada
function compute_pay(income: float; exemptions:
:=1; tax_rate: float) return float;
integer
answer:= compute_pay( 2000.0, tax_rate=> 0.15);
Default parameters must appear last in C++
float compute_pay(income: float, tax_rate: float,
exemptions:
integer :=1);
answer:= compute_pay( 2000.0, 0.15);
5
Variable Numbers of Parameters
In C:
printf(“x=%d %d\n”, a, b);
Define a function with variable number of parameters
 “…” indicates anonymous parameters
#include <varargs.h>
void myTrace(const char *fmt, ...) {
va_list ap; // declare variable list
va_start(ap, fmt); // init it to fmt
int sum = 0;
for( int i = 0 ; i < n100; i++ ) {
// get an arg. Whose type is known, here we’ll assume int
int arg = va_arg( listPointer, int );
printf( " The %dth arg is %d\n", i, arg );
if (arg == 0) return();
sum += arg;
}
}
6
Parameters
in most languages, parameters are positional
 Ada also provides keyword parameters:
AddEntry(dbase -> cds, new_entry -> mine);
advantage: don’t have to remember parameter order
disadvantage: do have to remember parameter names
Ada and C/C++ allow for default values for parameters
C/C++ & Java allow for optional parameters (specify with …)
public static double average(double... values) {
double sum = 0;
for (double v : values) { sum += v; }
return sum / values.length;
}
System.out.println( average(3.2, 3.6) );
System.out.println( average(1, 2, 4, 5, 8) );
 if multiple parameters, optional parameter must be rightmost WHY?
7
Parameter Passing Methods
How to pass data


Into the function for computation
Out from the function after the computation
Many models





Pass-by-value
Pass-by-result
Pass-by-value-result
Pass-by-reference
Pass-by-Name
8
Parameter passing
can be characterized by the direction of information flow
in mode:
out mode:
inout mode:
pass by-value
pass by-result
pass by-value-result, by-reference, by-name
by-value (in mode)
 parameter is treated as local variable, initialized to argument value
advantage:
safe (function manipulates a copy of the argument)
disadvantage: time & space required for copying
used in ALGOL 60, ALGOL 68
default method in C++, Pascal, Modula-2
only method in C (and, technically, in Java)
9
Pass-by-value
The value of the actual parameter is used to initialize the formal parameter,
which then acts as a local variable
 Actual/formal parameters are stored in different places
 Extra storage, expensive for large objects
int x = 7;
int y = 10;
Before:
void func1(int •a, int •b)
{
x=7
a = 15;
y = 10
b = a+b;
}
void main()
{
func1 (x, y);
printf(“ x= %d y= %d \n”, x, y);
a=7
}
b = 10
After:
global
data
x=7
y = 10
main
func
1
a = 15
b = 25
10
Parameter passing (cont.)
by-result (out mode)
 parameter is treated as local variable, no initialization
 when function terminates, value of parameter is passed back to argument
potential problems:
ReadValues(x, x);
Update(list[GLOBAL]);
by-value-result (inout mode)
 combination of by-value and by-result methods
 treated as local variable, initialized to argument, passed back when done
same potential problems as by-result
used in ALGOL-W, later versions of FORTRAN
11
Pass-by-result
No initialization, at the end of the function call, pass the value of formal
parameter to its corresponding actual parameter
 Actual/formal parameters are stored in different places
 Extra storage, expensive for large objects
int x = 7;
int y = 10;
Before:
void func1(int •a, int •b)
{
x=7
a = 15;
y = 10
b = 18;
}
void main()
{
func1 (x, y);
printf(“ x= %d y= %d \n”, x, y);
a
}
b
After:
global
data
x = 15
y = 18
main
func
1
a = 15
b = 18
12
Pass-by-value-result
Combine pass-by-value and pass-by-result
int x = 7;
int y = 10;
void func1(int •a, int •b)
{
a = 15;
Before:
b = a+b;
x=7
}
void main()
y = 10
{
func1 (x, y);
printf(“ x= %d y= %d \n”, x, y);
}
a=7
b = 10
After:
global
data
x = 15
y = 25
main
func
1
a = 15
b = 25
13
Parameter passing (cont.)
by-reference (inout mode)
 instead of passing a value, pass an access path (i.e., reference to argument)
advantage:
time and space efficient
disadvantage: slower access to values (must dereference), alias confusion
void IncrementBoth(int & x, int & y)
{
x++;
y++;
}
int a = 5;
IncrementBoth(a, a);
requires care in implementation: arguments must be l-values (i.e., variables)
used in early FORTRAN
can specify in C++, Pascal, Modula-2
Java objects look like by-reference
14
Pass-by-reference
Pass the address instead of the real value
 Space efficient, one address no matter how large the object is
 Data is modified directly
int x = 7;
int y = 10;
void func1(int •a, int •b)
{
Before:
a = 15;
x=7
b = a + b;
y = 10
}
void main()
{
func1 (x, y);
printf(“ x= %d y= %d \n”, x, y);
}
a
b
After:
global
data
x = 15
y = 25
main
func
1
a
b
15
Parameter passing (cont.)
by-name (inout mode)
 argument is textually substituted for parameter
 form of the argument dictates behavior
if argument is a:
variable  by-reference
constant  by-value
array element or expression  ???
real procedure SUM(real ADDER, int INDEX, int LENGTH);
begin
real TEMPSUM := 0;
for INDEX := 1 step 1 until LENGTH do
TEMPSUM := TEMPSUM + ADDER;
SUM := TEMPSUM;
end;
SUM(X, I, 100)
SUM(A[I], I, 100)
SUM[A[I]*A[I], I, 100)



100 * X
A[1] + . . . + A[100]
A[1]2 + . . . + A[100]2
 flexible but tricky – used in ALGOL 60, replaced with by-reference in ALGOL 68
16
More About Parameter Collision
Parameter collision creates alias
 A memory location may be accessed using more than one variable names
Other possible parameter collisions
 int x; func( int a) { … a… x…} main() { call func(x); }
 when i == j,
func(int a, int b) { … a… b…} main() { call func(list[i], list[j]); }
17
Parameter Collision
The order to evaluate parameters may affect results
 Left-to-right: x=22
 Right-to-left: x=15
int x = 7;
int y = 10;
void func1(int •a, int •b)
{
a = 15;
b = a+b;
}
void main()
{
func1 (x, x);
printf(“ x= %d \n”, x);
}
Before:
After:
x=7
global
data
?
x=
main
a=7
b=7
func
1
a = 15
b = 22
18
Parameter Passing in Major Languages
Java:
 Pass-by-value, pass-by-reference emulated through passing copies of references
C
 Pass-by-value, pass-by-reference
C++
 Reference type parameters are implicitly dereferenced
Pascal, Modula-2
 Pass-by-value (default), pass-by-reference
Ada
 In and out keywords
ALGOL 68
 Pass-by-name
19
Example
What is the result ?
int x = 1;
int y = 2;
void func1(int •a, int •b)
{
a = x+b;
b = a+x+y;
}
void main()
{
func1 ( x, y );
printf(“x=%d y=%d \n”, x, y);
}
 call by value
 call by value-result
 call by reference
x= ? y = ?
x= ? y = ?
x= ? y = ?
20
Type Checking Parameters
Considered very important for reliability
Fortran 77, original C: None
Pascal, Fortran 90, Java, and Ada: always required
ANSI C, C++: choice is made by the user
 Prototypes
Relatively new languages Perl, Javascript, and PhP don’t require type
checking
21
Design Considerations
Two important considerations
 Efficiency
 One-way or two-way data transfer
But the above considerations are in conflict
 Good programming suggest limited access to variables, which means one-way
whenever possible
 But pass-by-reference is more efficient to pass structures of significant size
 Example: array parameter
22
Parameters that are Subprogram Names
It is sometimes convenient to pass subprogram names as parameters
Issues:
1. Are parameter types checked?
2. What is the correct referencing environment for a subprogram that was sent as a
parameter?
23
In Different Languages
C and C++
 functions cannot be passed as parameters but pointers to functions can be passed
 Parameters can be type checked
int f1(int a, int b) {…}
int f2(int a, int b, int c) {…}
int g( int (*fx)(int, int)) { …fx(20,20) … }
int main ()
{
… g(f1)…
// ok
… g0f2)…
// wrong
}
24
Implementing subprograms
 some info about a subprogram is independent of invocation
e.g., constants, instructions
 can store in static code segment
 some info is dependent upon the particular invocation
e.g., return value, parameters, local variables (?)
 must store an activation record for each invocation
Activation Record

local variables may be allocated when
local variables
subprogram is called, or wait until
parameters
declarations are reached (stack-dynamic)
static link
dynamic link
return address
25
Run-time stack
when a subroutine is called, an instance of its activation record is pushed
program MAIN;
var a : integer;
procedure P1;
begin
print a;
end; {of P1}
procedure P2;
var a : integer;
begin
a := 0;
P1;
end; {of P2}
begin
a := 7;
P2;
end. {of MAIN}
P2
a = ?
M A IN c a lle d
a = ?
s ta tic
d y n a m ic
re tu rn
a = 7
P 2 c a lle d
P1
s ta tic
d y n a m ic
re tu rn
P2
a = 0
s ta tic
d y n a m ic
re tu rn
a = 7
P 1 c a lle d
when accessing a non-local variable
• follow static links for static scoping
• follow dynamic links for dynamic scoping
26
Run-time stack (cont.)
when a subroutine terminates, its activation record is popped (LIFO behavior)
program MAIN;
var a : integer;
procedure P1;
begin
print a;
end; {of P1}
procedure P2;
var a : integer;
begin
a := 0;
P1;
end; {of P2}
begin
a := 7;
P2;
end. {of MAIN}
P1
s ta tic
d y n a m ic
re tu rn
P2
a = 0
s ta tic
d y n a m ic
re tu rn
a = 7
P 1 c a lle d
P2
a = ?
s ta tic
d y n a m ic
re tu rn
a = 7
a = 7
P 1 te rm in a te s
P 2 te rm in a te s
when the last activation record is popped,
control returns to the operating system
27
Run-time stack (cont.)
note: the same subroutine may be called from different points in the program
program MAIN;
var a : integer;
procedure P1;
begin
print a;
end; {of P1}
procedure P2;
var a : integer;
begin
a := 0;
P1;
end; {of P2}
begin
a := 7;
P2;
P1;
end. {of MAIN}
P1
s ta tic
d y n a m ic
re tu rn
P2
a = 0
s ta tic
d y n a m ic
re tu rn
a = 7
1 s t c a ll to P 1
P1
s ta tic
d y n a m ic
re tu rn
a = 7
2 n d c a ll to P 1
 using dynamic scoping, the same variable in a subroutine
may refer to a different addresses at different times
28
In-class exercise
run-time stack?
output using static scoping?
output using dynamic scoping?
program MAIN;
var a : integer;
procedure P1(x : integer);
procedure P3;
begin
print x, a;
end; {of P3}
begin
P3;
end; {of P1}
procedure P2;
var a : integer;
begin
a := 0;
P1(a+1);
end; {of P2}
begin
a := 7;
P1(10);
P2;
end. {of MAIN}
29
Optimizing scoping
naïve implementation:
 if variable is not local, follow chain of static/dynamic links until found
in reality, can implement static scoping more efficiently (displays)
 block nesting is known at compile-time, so can determine number of links that must
be traversed to reach desired variable
 can also determine the offset within the activation record for that variable
 can build separate data structure that provides immediate access
can’t predetermine # links or offset for dynamic scoping
 subroutine may be called from different points in the same program
 can’t even perform type checking statically
WHY NOT?
30
Overloaded Subprograms
An overloaded subprogram is one that
 has the same name as another subprogram
 in the same referencing environment
 Every version of an overloaded subprogram has a unique protocol
C++, Java, C#, and Ada include predefined overloaded subprograms
In Ada, the return type of an overloaded function can be used to
disambiguate calls (thus two overloaded functions can have the same
parameters)
Ada, Java, C++, and C# allow users to write multiple versions of
subprograms with the same name
31
Overloaded Subprogram Example
int f1(int a, int b)
{…}
int f1(int a, int b, int c)
{…}
int f2(int a, int b)
{
int f1(int a, int b); // ok ?
}
32
Generic Subprograms
 Using overloaded subprograms, no need to create different
subprogram names for the same algorithm working on different data
types
 Sort an integer array ?
 Sort a linked list ?
 Sort a float array ?
But we still need to write different implementation code
Can use a more general abstraction mechanism
 Generic subprogram
 A generic or polymorphic subprogram takes parameters of different types on
different activations
33
Terms
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
34
Examples of
Parametric Polymorphism: C++
template <class Type>
Type max(Type first, Type second) {
return (first > second) ? first : second;
}
The above template can be instantiated for any type for which operator > is
defined
int max (int first, int second) {
return (first > second)? first : second;
}
35
Coroutines
A special kind of subprogram
A coroutine is a subprogram that has multiple entries and controls them itself
 resume-statement
 Coroutines provide quasi-concurrent execution of program units (the
coroutines); their execution is interleaved, but not overlapped
Different from multi-thread execution model
 Symmetric control: caller and called coroutines are on a more equal basis
Different from caller/callee execution model
36
Example
37
Coroutines with Loops
38
Design Issues for Functions
Are side effects allowed?

Parameters should always be in-mode to reduce side effect (like Ada)
What types of return values are allowed?





Most imperative languages restrict the return types
C allows any type except arrays and functions
C++ is like C but also allows user-defined types
Ada allows any type
Java and C# do not have functions but methods can have any type
39
Conditionals & loops
early control structures were tied closely to machine architecture
e.g., FORTRAN arithmetic if: based on IBM 704 instruction
10
20
30
40
IF (expression)
code to execute
GO TO 40
code to execute
GO TO 40
code to execute
. . .
10, 20, 30
if expression < 0
if expression = 0
if expression > 0
later languages focused more on abstraction and machine independence
some languages provide counter-controlled loops
e.g., in Pascal:
for i := 1 to 100 do
begin
. . .
end;
 counter-controlled loops tend to be more efficient than logic-controlled
 C/C++ and Java don't have counter-controlled loops (for is syntactic sugar for while)
40
Branching
unconditional branching (i.e., GOTO statement) is very dangerous
 leads to spaghetti code, raises tricky questions w.r.t. scope and lifetime
what happens when you jump out of a function/block?
what happens when you jump into a function/block?
what happens when you jump into the middle of a control structure?
most languages that allow GOTO’s restrict their use
 in C/C++, can’t jump into another function
can jump into a block, but not past declarations
void foo() {
. . .
goto label2;
. . .
label1:
string str;
. . .
label2:
goto label1;
branch
}
// illegal: skips declaration of str
// legal: str’s lifetime ends before
41
Branching (cont.)
why provide GOTO’s at all? (Java doesn’t)
 backward compatibility
 some argue for its use in specific cases (e.g., jump out of deeply nested loops)
C/C++ and Java provide statements for more controlled loop branching
 break: causes termination of a loop
while (true) {
num = input.nextInt();
if (num < 0) break;
sum += num;
}
 continue: causes control to pass to the loop test
while (inputKey != ’Q’) {
if (keyPressed()) {
inputKey = GetInput();
continue;
}
. . .
}
42
Procedural control
any implementation method for subprograms is based on the semantics of
subprogram linkage (call & return)
in general, a subprogram call involves:
1. save execution status of the calling program unit
2. parameter passing
3. pass return address to subprogram
4. transfer control to subprogram
possibly: allocate local variables, provide access to non-locals
in general, a subprogram return involves:
1.
2.
3.
4.
if out-mode parameters or return value, pass back value(s)
deallocate parameters, local variables
restore non-local variable environment
transfer control to the calling program unit
43
Parameters in Java
parameter passing is by-value, but looks like by-reference for objects
 recall, Java objects are implemented as pointers to dynamic data
public void messWith(ArrayList<String> lst)
{
lst.add(”okay”);
. . .
lst = new ArrayList();
}
ArrayList<String> words = new ArrayList<String>(5);
messWith(words);
words
size = 0
capacity = 5
when pass an object, by-value makes a copy (here, copies the pointer)
pointer copy provides access to data fields, can change
but, can’t move the original
44
Polymorphism
in C/C++ & Java, can have different functions/methods with the same name
 overloaded functions/methods must have different parameters to distinguish
public double doStuff(String str) { … }
public double doStuff(int x) { … }
// OK since param type is different
public int doStuff(String str) { … }
// not OK, since only return differs
in C++, can overload operators for new classes
bool Date::operator==(const Date & d1, const Date & d2) {
return (d1.day == d2.day &&
d1.month == d2.month &&
d1.year == d2.year);
}
 overloaded operators are NOT allowed in Java
RISKS?
45
References/Resources
http://www.cs.purdue.edu/homes/sbarakat/cs456/ch9-2up.pdf
http://www.cs.pitt.edu/~zhangyt/teaching/cs1621/Chapter09.ppt
Descargar

Abstraction