Chapter 5
Procedure Activations
过程活动要点
参数传递机制
宏扩展
PROCEDURES（ 过程 ）
When a procedure is called,the body is
executed,Each execution of the body is
called an activation of the body.
Two forms of procedures:
functions
Functions extend the built-in operators of a
language.
procedures
Procedures extend the built-in actions or statements.
ELEMENTS OF A PROCEDURE
过程的要素
A procedure declaration makes explicit
the elements or parts of a procedure:
procedure name（过程名）,a name for the
declared procedure
formal parameters（形式参数）,placeholders
for actual parameters
result type（返回值类型）,which is optional
procedure body（过程体）,consisting of local
declarations and a statement
THE ELEMENTS OF A FUNCTION
A COMPLETE PASCAL PROGRAM WITH
TWO FUNCTIONS,SQUARE AND AREA
带函数参数
BENEFITS OF PROCEDURES
The user of a procedure needs to know
what a procedure does,not how the
procedure works.
The benefits of procedures include the
following:
– Procedure abstraction（过程抽象）
– Implementation hiding（实现隐藏）
– Modular programs（模块化编程）
– Libraries（库）
PARAMETER-PASSING METHODS
参数传递机制
Parameter passing refers to the
matching of actuals（实际参数）
with formals（形式参数） when a
procedure call occurs.
Possible interpretations of a procedure
call like P(A[i]) include the following:
– Call-by-value（值传递）
Pass the value of A[i].
– Call-by-reference（引用传递）
Pass the location of A[i].
– Call-by-value-result（值结果传递）
actuals are initially copied into the formals and the
formals are eventually copied back the the actuals.
– Call-by-name（名字传递）
Pass the text A[i] itself,while avoiding ``name
clashes.''
CALL-BY-VALUE（值传递）
Under call-by-value,a formal
parameter corresponds to the
value of an actual parameter,Call-
by-value is the primary parameter-
passing method in C and Pascal.
传递了实际参数的一个副本给形参。
Example:
procedure muchAdo(x,y,T);
var z,T;
begin
z,= x; x,= y; y,= z;
end
A call muchAdo(a,b) has the following effect:
x,= a; { pass the value of a to x }
y,= b; { pass the value of b to y }
z,= x; x,= y; y,= z; { a and b are unchanged }
The program segment does not change a or b,though
the values of x and y are indeed exchanged.
如果想用此方法来交换两个数的值可能达不到目的。
CALL-BY-REFERENCE
Under call-by-reference,a formal
parameter becomes a synonym for
the the location of an actual
parameter.
传实际参数的地址给形参，形参成了该地址的同义词。
Example:
procedure swap(var x,y,integer);
var z,integer;
begin
z,= x; x,= y; y,= z;
end
A call swap(i,A[i]) is implemented as follows:
make the location of x the same as that of i;
make the location of y the same as that of A[i];
z,= x; x,= y; y,= z;
If i is 2 and A[2] is 99,the effect of these statements
is
z,= 2; i,= 99; A[2],= z;
Thus,these assignments exchange the values of i and
A[2].
The only parameter-passing method in C
is call-by-value; however,the effect of
call-by-reference can be achieved using
pointers.
Example:
void swapc(int *px,int *py) {
int z;
z = *px; *px = *py; *py = z;
}
A call swapc(&a,&b) is implemented as follows:
px = &a;
py = &b;
z = *px;
*px = *py;
*py = z;
These assignments exchange the values of a and b.
CALL-BY-VALUE-RESULT
值结果传递
Call-by-value-result is also known as
copy-in/copy-out（传入 /传出机制）
because (1.) the actuals are initially
copied into the formals and (2.) the
formals are finally copied back to the
actuals.
进入时传值，退出反馈结果值结果传递机制举例 —— Ada
Ada,for example,supports three kinds of
parameters:
– in parameters,corresponding to value parameters.
– out parameters,corresponding to just the copy-
out phase of call-by-value-result.
– in out parameters,corresponding to either
reference parameters or value-result parameters,
at the discretion of the implementation.
Legal Ada programs are expected to have
the same effect under call-by-reference
and copy-in/copy-out.
CALL-BY-VALUE-RESULT
值结果传递同时传递了值和地址！
BY-VALUE-RESULT vs,BY-REFERENCE
值结果传递与引用传递的比较
CALL-BY-NAME名字传递
Call-by-name and call-by-value were the
two parameterpassing methods in Algol
60,The rules for call-by-name were
carefully specified to get lexical scope:
Actual parameters are textually substituted
for the formals,Possible name conflicts
between names in the actuals and local
names in the procedure body are avoided by
renaming the locals in the body.
The resulting procedure body is substituted
for the call,Possible conflicts between
nonlocals in the procedure body and locals at
the point of call are avoided by renaming the
locals at the point of call.
begin integer x; x,= 1;
procedure P(y)
integer x; x,= 2; print(y);
end P;
P(x)
end
Call-by-name,print 1
Call-by-name can be used to parameterize
a procedure to handle a diverse range of
applications.
integer procedure SIGMA (integer x,j,n);
begin
integer s;
s,= 0;
for j:=1 until n do s,= s+x;
return s;
end
SIGMA(A[I],I,10) = A[1]+A[2]+ ······ +A[10]
SIGMA(A[I]*B[I],I,10) =
A[1]*B[1]+A[2]*B[2]+ ······ +A[10]*A[10]
MACRO EXPANSION（宏扩展）
If a procedure body is simply copied
or substituted at the point of call,
we get dynamic scope.
A macro processor does the
following:
– Actual parameters are textually substituted
for the formals.
– The resulting procedure body is textually
substituted for the call.
Using macro expansion for the call
W,
procedure D;
var n,char; begin n,= 'D'; W end;
will become
procedure D;
var n,char; begin n,= 'D'; writeln(n) end;
MACRO EXPANSION AND
DYNAMIC SCOPE宏扩展和动态作用域
The occurrence of n in writeln(n) is
``captured'' by the declaration of n
in procedure D,The output of the
macro-expanded program will be
the same as that under dynamic
scope.
MACRO EXPANSION IN C
C use a macro preprocessor to support language
extensions such as named constants and file inclusion.
#define <identifier> <token-sequence> //定义常量
#define <identifier> ( <identifier-list> ) <token-squence>
//定义函数
#define TABLESiZE 100
int table [TABLESiZE];
#define ABSDiFF(a,b) ((a) > (b)? (a) – (b),(b) – (a))
X = ABSDiFF(8,5); // x = 3
X = ((8) > (5)? (8) – (5),(5) – (8));
#define ABSDiFF(a,b) ((a) > (b)? (a) – (b),(b) – (a))
Why not just
#define ABSDiFF(a,b) (a > b? a – b,b – a)
X = ABSDiFF(6,7 – 3);
X = (6 > 7 – 3? 6 – 7 – 3? 7 – 3– 6 ); // x = – 4
PROCEDURE ACTIVATION
过程调用
The lifetime of an activation begins when
control enters the activation and ends
when control returns from the
activation.
The flow of control between activations
can be depicted by a tree,called
activation tree（活动树）,
Data needed for an activation of a
procedure is collected in a record called
activation record （过程活动记录） or
frame or stack frame.
PROCEDURE ACTIVATION
ACTIVATION TREE活动树
ACTIVATION RECORDS 过程活动记录
AN EXAMPLE
TAIL-RECURSION尾递归
When the last statement executed in the
body of a procedure is a recursive call,
the call is said to be tail recursive,A
procedure as a whole is tail recursive if
all its recursive calls are tail recursive.
Tail-recursive calls can be eliminated and
replaced by control flow within the
procedure,thereby avoiding the
overhead of a call.
尾递归可用过程内的控制流消除，从而避免额外开销。
A tail-recursive binary search
procedure尾递归举例 —— 折半查找过程
AN EXECUTION OF THE RECURSIVE
BINARY SEARCH PROGRAM
查找 55
A non-recursive binary search
procedure非递归折半查找
AN EXECUTION
An Illustration of nonlocal
access within nested procedures
STACKS SNAPSHOTS
Display Elements,Indexed by
Nesting Depth,Point to Visible
Blocks
Block structure can also be implemented
by displays,where a display is an array
d of pointers to activation records,
indexed by lexical nesting depth.
Array element d[i] is maintained so that it
points to the most recent activation of
the block at nesting depth i.
Procedure Activations
过程活动要点
参数传递机制
宏扩展
PROCEDURES（ 过程 ）
When a procedure is called,the body is
executed,Each execution of the body is
called an activation of the body.
Two forms of procedures:
functions
Functions extend the built-in operators of a
language.
procedures
Procedures extend the built-in actions or statements.
ELEMENTS OF A PROCEDURE
过程的要素
A procedure declaration makes explicit
the elements or parts of a procedure:
procedure name（过程名）,a name for the
declared procedure
formal parameters（形式参数）,placeholders
for actual parameters
result type（返回值类型）,which is optional
procedure body（过程体）,consisting of local
declarations and a statement
THE ELEMENTS OF A FUNCTION
A COMPLETE PASCAL PROGRAM WITH
TWO FUNCTIONS,SQUARE AND AREA
带函数参数
BENEFITS OF PROCEDURES
The user of a procedure needs to know
what a procedure does,not how the
procedure works.
The benefits of procedures include the
following:
– Procedure abstraction（过程抽象）
– Implementation hiding（实现隐藏）
– Modular programs（模块化编程）
– Libraries（库）
PARAMETER-PASSING METHODS
参数传递机制
Parameter passing refers to the
matching of actuals（实际参数）
with formals（形式参数） when a
procedure call occurs.
Possible interpretations of a procedure
call like P(A[i]) include the following:
– Call-by-value（值传递）
Pass the value of A[i].
– Call-by-reference（引用传递）
Pass the location of A[i].
– Call-by-value-result（值结果传递）
actuals are initially copied into the formals and the
formals are eventually copied back the the actuals.
– Call-by-name（名字传递）
Pass the text A[i] itself,while avoiding ``name
clashes.''
CALL-BY-VALUE（值传递）
Under call-by-value,a formal
parameter corresponds to the
value of an actual parameter,Call-
by-value is the primary parameter-
passing method in C and Pascal.
传递了实际参数的一个副本给形参。
Example:
procedure muchAdo(x,y,T);
var z,T;
begin
z,= x; x,= y; y,= z;
end
A call muchAdo(a,b) has the following effect:
x,= a; { pass the value of a to x }
y,= b; { pass the value of b to y }
z,= x; x,= y; y,= z; { a and b are unchanged }
The program segment does not change a or b,though
the values of x and y are indeed exchanged.
如果想用此方法来交换两个数的值可能达不到目的。
CALL-BY-REFERENCE
Under call-by-reference,a formal
parameter becomes a synonym for
the the location of an actual
parameter.
传实际参数的地址给形参，形参成了该地址的同义词。
Example:
procedure swap(var x,y,integer);
var z,integer;
begin
z,= x; x,= y; y,= z;
end
A call swap(i,A[i]) is implemented as follows:
make the location of x the same as that of i;
make the location of y the same as that of A[i];
z,= x; x,= y; y,= z;
If i is 2 and A[2] is 99,the effect of these statements
is
z,= 2; i,= 99; A[2],= z;
Thus,these assignments exchange the values of i and
A[2].
The only parameter-passing method in C
is call-by-value; however,the effect of
call-by-reference can be achieved using
pointers.
Example:
void swapc(int *px,int *py) {
int z;
z = *px; *px = *py; *py = z;
}
A call swapc(&a,&b) is implemented as follows:
px = &a;
py = &b;
z = *px;
*px = *py;
*py = z;
These assignments exchange the values of a and b.
CALL-BY-VALUE-RESULT
值结果传递
Call-by-value-result is also known as
copy-in/copy-out（传入 /传出机制）
because (1.) the actuals are initially
copied into the formals and (2.) the
formals are finally copied back to the
actuals.
进入时传值，退出反馈结果值结果传递机制举例 —— Ada
Ada,for example,supports three kinds of
parameters:
– in parameters,corresponding to value parameters.
– out parameters,corresponding to just the copy-
out phase of call-by-value-result.
– in out parameters,corresponding to either
reference parameters or value-result parameters,
at the discretion of the implementation.
Legal Ada programs are expected to have
the same effect under call-by-reference
and copy-in/copy-out.
CALL-BY-VALUE-RESULT
值结果传递同时传递了值和地址！
BY-VALUE-RESULT vs,BY-REFERENCE
值结果传递与引用传递的比较
CALL-BY-NAME名字传递
Call-by-name and call-by-value were the
two parameterpassing methods in Algol
60,The rules for call-by-name were
carefully specified to get lexical scope:
Actual parameters are textually substituted
for the formals,Possible name conflicts
between names in the actuals and local
names in the procedure body are avoided by
renaming the locals in the body.
The resulting procedure body is substituted
for the call,Possible conflicts between
nonlocals in the procedure body and locals at
the point of call are avoided by renaming the
locals at the point of call.
begin integer x; x,= 1;
procedure P(y)
integer x; x,= 2; print(y);
end P;
P(x)
end
Call-by-name,print 1
Call-by-name can be used to parameterize
a procedure to handle a diverse range of
applications.
integer procedure SIGMA (integer x,j,n);
begin
integer s;
s,= 0;
for j:=1 until n do s,= s+x;
return s;
end
SIGMA(A[I],I,10) = A[1]+A[2]+ ······ +A[10]
SIGMA(A[I]*B[I],I,10) =
A[1]*B[1]+A[2]*B[2]+ ······ +A[10]*A[10]
MACRO EXPANSION（宏扩展）
If a procedure body is simply copied
or substituted at the point of call,
we get dynamic scope.
A macro processor does the
following:
– Actual parameters are textually substituted
for the formals.
– The resulting procedure body is textually
substituted for the call.
Using macro expansion for the call
W,
procedure D;
var n,char; begin n,= 'D'; W end;
will become
procedure D;
var n,char; begin n,= 'D'; writeln(n) end;
MACRO EXPANSION AND
DYNAMIC SCOPE宏扩展和动态作用域
The occurrence of n in writeln(n) is
``captured'' by the declaration of n
in procedure D,The output of the
macro-expanded program will be
the same as that under dynamic
scope.
MACRO EXPANSION IN C
C use a macro preprocessor to support language
extensions such as named constants and file inclusion.
#define <identifier> <token-sequence> //定义常量
#define <identifier> ( <identifier-list> ) <token-squence>
//定义函数
#define TABLESiZE 100
int table [TABLESiZE];
#define ABSDiFF(a,b) ((a) > (b)? (a) – (b),(b) – (a))
X = ABSDiFF(8,5); // x = 3
X = ((8) > (5)? (8) – (5),(5) – (8));
#define ABSDiFF(a,b) ((a) > (b)? (a) – (b),(b) – (a))
Why not just
#define ABSDiFF(a,b) (a > b? a – b,b – a)
X = ABSDiFF(6,7 – 3);
X = (6 > 7 – 3? 6 – 7 – 3? 7 – 3– 6 ); // x = – 4
PROCEDURE ACTIVATION
过程调用
The lifetime of an activation begins when
control enters the activation and ends
when control returns from the
activation.
The flow of control between activations
can be depicted by a tree,called
activation tree（活动树）,
Data needed for an activation of a
procedure is collected in a record called
activation record （过程活动记录） or
frame or stack frame.
PROCEDURE ACTIVATION
ACTIVATION TREE活动树
ACTIVATION RECORDS 过程活动记录
AN EXAMPLE
TAIL-RECURSION尾递归
When the last statement executed in the
body of a procedure is a recursive call,
the call is said to be tail recursive,A
procedure as a whole is tail recursive if
all its recursive calls are tail recursive.
Tail-recursive calls can be eliminated and
replaced by control flow within the
procedure,thereby avoiding the
overhead of a call.
尾递归可用过程内的控制流消除，从而避免额外开销。
A tail-recursive binary search
procedure尾递归举例 —— 折半查找过程
AN EXECUTION OF THE RECURSIVE
BINARY SEARCH PROGRAM
查找 55
A non-recursive binary search
procedure非递归折半查找
AN EXECUTION
An Illustration of nonlocal
access within nested procedures
STACKS SNAPSHOTS
Display Elements,Indexed by
Nesting Depth,Point to Visible
Blocks
Block structure can also be implemented
by displays,where a display is an array
d of pointers to activation records,
indexed by lexical nesting depth.
Array element d[i] is maintained so that it
points to the most recent activation of
the block at nesting depth i.
