Some Design issues.
1. Recursion or not
Recursion: makes subprograms more useful and elegant especial when the underlying algorithm
is recursively defined but makes it necessary to provide run-time
supporting system that must update the Referencing Environment
2. Nesting or not (which has a lot to do with the Identifier Scope Rule)
Nesting: Static Scope rule is the norm
Makes program execution safer by protecting inner(nested subprograms) from
unauthorized accesses and
makes static analysis of the programs simpler and easier than otherwise.
3. Parameter Passing mechanisms.
4. Memory allocation for Local Names:
Deletion (automatic)
Retention (static)
A. Referencing Environment
Idea:
To grasp all memory locations that the program in execution havs access
at any given point in time during the execution of a program as they constantly change
each time a subprogram is called or returns.
Equivalently, all visible names during a program execution.
Conceptually it has two parts:
Local R.E. and
Nonlocal R.E.
1. Deciding the Local R.E. is straightforward.
It is the set of all local names of the currently active
one subprogram in execution.
2. Deciding the Nonlocal R.E. depends on the Scope rule being used:
Static Scope and
Dynamic Scope.
--------------------------------------------
Evaluation of Scope Rules
Static Scope:
1. Natural choice for block-structured languages especially for
those languages that allow nested subprograms such as
Pascal, ADA, and P/L-1 as access is controlled and prohibited
depending upon the textual containments of subprograms.
2. Local variables of a calling subprogram still get protection
from the called subprogram unless the called subprogram is the
static descendant subprogram (like the case of A() calling C())
3. Compile-time Static binding and static type checking are
possible.
4. Faster memory access for nonlocal variables.
5. Relatively easy to read programs.
6. More Extensive changes may be needed if scopes of names are to be
modified.
Dynamic Scope:
1. Possible choice when subprograms are NOT to be nested and Blocks
are not present and furthermore, the language is highly dynamic
and local variables of a subprogram are intended to be
visible to all other subprograms (or most of them, anyway)
that are subsequently to be called.
2. Binding a nonlocal, in general, must be delayed until
run-time, which is time-consuming.
As a result, no compile-time Static type checking.
3. All local variables are accessible to called subprograms
unless they are hidden by Redeclarations of called subprograms,
which may be good or bad.
4. Slower memory access and more difficult to read programs.
5. Can save parameters.
------------------------------------------------------
proc main();
proc A();
proc C();
proc D();
proc B();
proc E();
main() can call A() and B() but not C(), D() or E()
A() can call C(,) D(), or itself.
B() can call A(), E(), or itself.
C() can call A() or itself but not D(), nor B() nor E()
D() can call A(), C() or itself but nothing else.
EX: Static Scope
program Example;
var a, b: integer;
.....
procedure sub1;
var x, y: integer;
begin
// point-1:
L.R.E.=[x(sub1), y(sub1)]
N.R.E.=[a(example), b(example)]
end; {sub1}
procedure sub2;
var b,x: integer;
.....
procedure sub3;
var x: integer;
.....
// point-2
L.R.E.=[x(sub3)]
N.L.E.=[a(example), b(sub2)]
end {sub3}
begin {sub2}
// point-3
L.R.E.=[x(sub2), b(sub2)]
N.R.E.=[a(example)]
end; {sub2}
begin {example}
.....
// point-4
L.R.E.=[a(example), b(example)]
end {example}
------------------------------------------
EX: Dynamic Scope
Main called sub3 and sub3 called sub2 which called sub1.
void sub1()
{ int a,b; L.R.E. = [a(sub1), b(sub1)]
N.R.E. = [c(sub2), d(sub3), e(main)]
.....
point-1
} /* end of sub1
void sub2()
{ int b,c;
....
point-2 L.R.E. = [b(sub2), c(sub2)]
N.R.E. = [d(sub3), e(main)]
sub1();
} /* end of sub2
void sub3()
{ int b,d;
.....
point-3 L.R.E. = [b(sub3), d(sub3)]
N.R.E. = [c(main), e(main)]
sub2();
} /* end of sub3
void main()
{ int c,d,e;
.....
point-4 L.R.E. = [c(main), d(main), e(main)]
sub3();
} /* end of main()
B. Parameter passing
1. Three semantic modes
Regarding direction of passing between the Calling unit
and called unit.
a. In mode
b. Out mode
c. In-Out mode
Ada and Fortran90 allow programs to specify.
In mode: Actual argument's value is passed and formal parameter
is not to be altered, namely NOT to be assigned.
Out mode: Formal parameter's value is passed and formal parameters are NOT to be
referenced, only to be assigned.
In-Out mode: Both and no restrictions on either parameter.
2. Actual passing mechanisms
Pass-by-Value
Pass-by-Result
Pass-by-Value-Result
Pass-by-Reference
Pass-by-Name
a. Pass-by-Value
(1) The value of actual argument is used to initialize the
corresponding parameter which acts like a local variable.
(2) In-mode semantic is realized.
(3) 2 ways to implement
Actual data transfer (to new memory space)
safe, faster access by the called unit.
more memory space.
Access Path transfer (Pointer rather than actual value)
More like pass-by-reference
Dangerous for "Write Protection"
Less memory space when the actual argument is large like
an array.
(4) Used by many languages including C, C++, Ada, Pascal,
Java (for primitive data types), ALGOL60, Snobol
b. Pass-by-Result
(1) The value of the formal parameter is transferred to become
the new value of the corresponding actual argument which
must be a variable.
(2) Implementing the Out-mode semantic.
(3) 2 ways to implement just like Pass-by-Value.
Same tradeoffs including the problem of insuring that the initial
value of the actual argument is NOT used in the called unit
when the access path is transferred.
(4) Two Additional problems:
Actual argument collision.
Sub(P1, P1)
the final value of P1 is unpredictable at best.
Deciding the address of an actual argument
Sub(List[index])
when index is changed inside the called subprogram, Sub,
the address of List[index]) can be different depending on
when the address is decided, on call or on Return.
(5) Used by Ada for Out-mode parameters.
c. Pass-by-Value-Result (Pass-by-Copy)
(1) Value is copied from actual argument to formal parameter and
in the opposite direction as well.
(2) Implementing Inout-mode semantic.
(3) Share problems of both Pass-by-Value and Pass-by-Result.
(4) Free from aliasing (unlike Pass-by-Reference)
(5) Used by Fortran90 and Ada.
d. Pass-by-Reference
(1) Implementing Inout-mode semantic
(2) An adderss is passed to the called subprogram enabling
the called subprogram to share the actual argument with
the calling subprogram.
(3) Efficient both in time (Due to NO Copying needed)
and space (NO Duplicate memory space for copying).
By and large, the simplest method.
(4) Used by many languages including FORTRAN77, Pascal, C++,
Java (class objects, arrays), FORTRAN90
(5) Disadvantages
Access to actual argument itself may be slower due to indirect
addressing.
Aliasing: Harmful to Readability and Reliability.
EX: Subprogram Fun(First, Second)
a. Call Fun(X,X)
// Inside subprogram fun, the two different names,
// First and Second, represent the same memory address
// So, they become aliases.
b. Call Fun(L[K], L[M])
// If K and M happen to the same, then same result as above.
Subprogram Fun2(First, Second)
c. Call Fun2 (List[K], List)
// Inside the called subprogram, First and an element of
the array Second become aliases.
Subprogram Fun3(Param1)
d. Call Fun3 (NonLocal1)
// When inside the called subprogram, the given actual
argument is a visible non-local, then Param1 and
Nonlocal1 become aliases.
e. Pass-by-Name
(1) Delaying the actual binding of formal parameters to a value
or to an address until they are actually referenced or
assigned, by essentially substituting text of the argument
for the corresponding parameter.
(2) Implementing Inout-mode semantic
(3) Used initially in Algol60 along with Pass-by-Value.
No other language followed except SIMULA67
(4) Very slow as it is usually implemented by a parameterless
procedure called Thunks.
(5) Different outcomes:
If Actual argument is a scalar var: Same as Pass-by-Reference
If It is a constant expression: Same as Pass-by-Value
If it is an array element like A[K] or an expression that contains
a variable like X+Y, it is different from
any other methods yielding different unique results.
(6) Flexibility: A subprogram doing many different things.
EX: Jensen's Device (Algol procedure)
Real Procedure SUM(Exp,Index,L,U);
value L,U;
begin
real temp:=0;
for Index := L step 1 Until U
do temp := temp+Exp;
SUM := temp;
end;
Example calls:
SUM(A[i], i, 1, 100)
// A[1]+A[2]+A[3]+...+A[100]
SUM(A[K]*B[K], K, 1, 100)
// A[1]*B[1]+A[2]*B[2]+ ... +A[100]*B[100]
SUM(C[K,2], K, -100, -100)
// C[-100,2]+C[-99,2]+C[-98,2]+ ... +C[100,2]
(7) Inadequacy: Certain procedures may not work in some cases.
Subprogram Swap(A,B)
integer A,B,C
C=A
A=B
B=C
return
end
If above were implemented by Pass-by-Name, then following
call would not work:
Call Swap(K,List[K])
because this call will be turned into:
C=K
K=List[K]
List[K]=C
unless List[K] and K are the same
although "Call Swap(List[K],K)" may.
C. Parameters that are Subprogram Names (Parameter Subprograms)
(1) Idea: To have a procedure perform a variety of tasks
by calling a subprogram that is sent to it.
Some languages allow this:
Pascal, Fortran77, Fortran90, Algol68, C, C++ (by way of
function pointers only)
(2) Problems:
Need for checking type consistency of parameters of this parameter subprogram.
For this, parameter types of this subprogram need to be passed as arguments of
the subprogram call.
EX: Pascal
procedure integrate (function fun(X:real):real;
lower, upper:real; var result: real);
...
var val:real;
val := fun(lower);
...
end;
In this example, the Pascal compiler is able to check the type
consistency of the actual argument of the function fun() to be
called from above procedure integrate
(3) Issue: Deciding the referencing environment of the called subprogram. (Under Static Scope)
Three possibilities:
Shallow Binding (Not suitable for nested subprograms for Static Scope Rule)
The environment of the call statement that ENACTS
the passed subprogram. (more natural for dynamic scope)
Deep Binding (Choice)
The environment in which the passed subprogram is defined, which is consistent with
the normal binding in case of the Static Scope Rule.
Ad Hoc Binding (Not been used)
The environment of the call statement that passed the subprogram
as an actual argument, which can change depending upon where
(or in which subprogram) it happened.
Example (JavaScript)
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(); // calling the passed subprogram which is a parameter.
};
x = 1;
sub3();
};
In the above program, sub1 calls sub3
which calls sub4 by the call statement, sub4(sub2).
So, sub4() subsequently calls sub2().
The environment of the execution of sub2() in this case can be one of the following three:
1. that of sub4(): Shallow Binding.
x=4
2. that of sub1(): Deep Binding.
x=1
3. that of sub3(): Ad Hoc Binding.
x=3.
REF: Text, Section 9.6(pages 408-409)