[SOLVED] 程序代写代做代考 scheme c/c++ Fortran compiler Java ada chain lec12

lec12

CS 314 Principles of Programming Languages

Prof. Zheng Zhang
Rutgers University

Lecture 12: Names, Scopes and Bindings

October 12, 2018

Review: Names, Scopes and Binding

2

• Denotes a programming language construct
• Has associated “attributes”

Examples: type, memory location, read/write permission, storage
class, access restrictions.

• Has a meaning
Examples: represents a semantic object, a type description, an
integer value, a function value, a memory address.

What’s in a name? — Each name “means” something!

3

• Compile time: during compilation process – static
(e.g.: macro expansion, type definition)

• Link time: separately compiled modules/files are joined together by
the linker (e.g: adding the standard library routines for I/O (stdio.h),
external variables)

• Run time: when program executes – dynamic

Review: Names, Bindings and Memory

Compiler needs bindings to know meaning of names during translation
(and execution).

Bindings – Association of a name with the thing it “names”
(e.g., a name and a memory location, a function name and its
“meaning”, a name and a value)

Review: How to Maintain Bindings

4

• Symbol table: maintained by compiler during compilation
• Referencing Environment: maintained by compiler-generated-code

during program execution

• How long do bindings last for a name hold in a program?
• What initiates a binding?
• What ends a binding?

Question:

Scope of a binding:
The part of program the in which the binding is active.

Review: Lexical Scope v.s. Dynamic Scope

5

• Non-local variables are associated with declarations at compile time
• Find the smallest block syntactically enclosing the reference and

containing a declaration of the variable

Lexical Scope

• Non-local variables are associated with declarations at run time
• Find the most recent, currently active run-time stack frame

containing a declaration of the variable

Dynamic Scope

Lexical Scope

6

A name that is introduced in a declaration is known in the scope in
which it is declared, and in each internally nested scope, unless it is
hidden by another declaration of the same name in one or more
nested scopes.

Closest scope rule

Scope Example

7

procedure P1(A1)
var X — local to P1
…
procedure P2(A2)

…
procedure P3(A3)

…
begin

… — body of P3
end
…

begin
… — body of P2

end
procedure P4(A4)

…
function F1(A5)

var X— local to F1
…

begin
… — body of F1

end
…

begin
… — body of P4

end
…

begin
… — body of P1

end

A1 X P2

A2 P3

A3

P4

A4 F1
A5 X

Scope Example

8

procedure P1(A1)
var X — local to P1
…
procedure P2(A2)

…
procedure P3(A3)

…
begin

… — body of P3
end
…

begin
… — body of P2

end
procedure P4(A4)

…
function F1(A5)

var X— local to F1
…

begin
… — body of F1

end
…

begin
… — body of P4

end
…

begin
… — body of P1

end

A1 X P2

A2 P3

A3

P4

A4 F1
A5 X

Scope Example

9

procedure P1(A1)
var X — local to P1
…
procedure P2(A2)

…
procedure P3(A3)

…
begin

… — body of P3
end
…

begin
… — body of P2

end
procedure P4(A4)

…
function F1(A5)

var X— local to F1
…

begin
… — body of F1

end
…

begin
… — body of P4

end
…

begin
… — body of P1

end

A1 X P2

A2 P3

A3

P4

A4 F1
A5 X

Scope Example

10

procedure P1(A1)
var X — local to P1
…
procedure P2(A2)

…
procedure P3(A3)

…
begin

… — body of P3
end
…

begin
… — body of P2

end
procedure P4(A4)

…
function F1(A5)

var X— local to F1
…

begin
… — body of F1

end
…

begin
… — body of P4

end
…

begin
… — body of P1

end

A1 X P2

A2 P3

A3

P4

A4 F1
A5 X

Scope Example

11

procedure P1(A1)
var X — local to P1
…
procedure P2(A2)

…
procedure P3(A3)

…
begin

… — body of P3
end
…

begin
… — body of P2

end
procedure P4(A4)

…
function F1(A5)

var X— local to F1
…

begin
… — body of F1

end
…

begin
… — body of P4

end
…

begin
… — body of P1

end

A1 X P2

A2 P3

A3

P4

A4 F1

A5 X

Scope Example

12

procedure P1(A1)
var X — local to P1
…
procedure P2(A2)

…
procedure P3(A3)

…
begin

… — body of P3
end
…

begin
… — body of P2

end
procedure P4(A4)

…
function F1(A5)

var X— local to F1
…

begin
… — body of F1

end
…

begin
… — body of P4

end
…

begin
… — body of P1

end

A1 X P2

A2 P3

A3

P4

A4 F1

A5 X

local to P1

local to F1

X local to F1
is hidden by
X local to F1

also called a
“hole”

Dynamic Scope

13

The “current” binding for a given name is the one encountered most
recently during execution, and not yet destroyed by returning from
its scope.

Depending on the Flow of Execution at Run Time

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

Dynamic Scope

14

L ⇒ D ⇒ W

Calling Chain:

The output is ?

Caller

D
Which “n”?

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}

D
end

Review: Program Memory Layout

15

• Static objects are given an absolute address
that is retained throughout the execution of
the program

• Stack objects are allocated and deallocated in
last-in, first-out order, usually in conjunction
with subroutine calls and returns

• Heap objects are allocated and deallocated at
any arbitrary time

stack

heap

static &
global

code

Procedure Activations

16

• Begins when control enters activation (call)
• Ends when control returns from call

Example:

Subroutine C

Subroutine B

Subroutine B

Subroutine A

procedure C:
D
procedure B:
if…then B else C
procedure A:
B
main program:
A

sp

Direction of
stack growth

(usually lower
addresses)

Calling chain: A ⇒ B ⇒ B ⇒ C ⇒ D

parameter
return value

return address

access link

caller FP

local variables

Subroutine D

Procedure Activations

17

• Run-time stack contains frames from main program & active procedure
• Each stack frame includes:

1. Pointer to stack frame of caller
(control link for stack maintenance and dynamic scoping)

2. Return address (within calling procedure)
3. Mechanism to find non-local variables (access link for lexical scoping)
4. Storage for parameters, local variables and final values
5. Other temporaries including intermediate values & saved register

parameter
return value

return address

access link

caller FP

local variables

Stack Frame
or

Activation Record Frame Pointer (FP)
or Activation Record

Pointer (ARP)

Usually stored in a register

Implementation of Lexical Scope and Dynamic Scope

18

• Non-local variables are associated with declarations at compile time
• Find the smallest block syntactically enclosing the reference and

containing a declaration of the variable
• Access link points to the most recently activated immediate lexical

ancestor

Lexical Scope

• Non-local variables are associated with declarations at run time
• Find the most recent, currently active run-time stack frame

containing a declaration of the variable
• Control link points to the caller

Dynamic Scope

Program
x, y: integer // declarations of x and y
Procedure B// declaration of B
y, z: real// declaration of y and z
begin
…
y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end

Procedure C// declaration of C
x: real
begin
…
call B // occurrence of B
end
begin
…
call C // occurrence of C
call B // occurrence of B
end

19

Calling chain: MAIN⇒ C ⇒ B ⇒ BControl linksAccess links

fp
main

o
o

x
y

C
o

o
x

B
o

o
y
z

B
o

o
y
z

Implementation of Lexical Scope and Dynamic Scope

Context of Procedures

20

Two contexts
• static placement in source code (same for each invocation)
• dynamic run-time stack context (different for each invocation)

Scope Rules:
Each variable reference must be associated with a single declaration.

Context of Procedures

21

Two choices:
1. Use static and dynamic context: lexical scope
2. Use dynamic context: dynamic scope

•Easier for variables declared locally: same for lexical and
dynamic scoping

•Harder for variables not declared locally: not same for lexical
and dynamic scoping

Access to Non-Local Data(Lexical Scoping)

22

1. Compile-time: How do we map a name into a (level, offset) pair?
We use a block structured symbol table (compile time)
– When we look up a name, we want to get the most recent declaration

for the name
– The declaration may be found in the current procedure or in any

ancestor procedure
2. Run-time: Given a (level, offset) pair, what’s the address?

– Two classical approaches:
⇒ access link (static link)
⇒ display

Two important steps

Compile-Time

23

Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).

Program
(1,1), (1,2): integer // declarations of x and y
Procedure (1,3)// declaration of B
(2,1), (2,2): real// declaration of y and z
begin
…
(2,1) = (1,1) + (2,2) // occurrences of y, x, and z
if (…) call (1,3) // occurrence of B
end
Procedure (1,4)// declaration of C
(2,1): real
begin
…
call (1,3) // occurrence of B
end
begin
…
call (1,4) // occurrence of C
call (1,3) // occurrence of B
end

Program
x, y: integer // declarations of x and y
Procedure B// declaration of B
y, z: real// declaration of y and z
begin
…
y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C// declaration of C
x: real
begin
…
call B // occurrence of B
end
begin
…
call C // occurrence of C
call B // occurrence of B
end

Runtime Access to Non-Local Data (Lexical Scoping)

24

• Assume current procedure level is k
• If k = l, it is a local variable
• If k > l, must find l’s activation record (stack frame)
⇒ follow k − l access link

• k < l cannot occurRuntime: To find the value specified by (l, o) 
Assume nested procedure has higher index than its parent procedure. Using access link:Access to Non-Local Data(Lexical Scoping): Access Link25• Each AR has a pointer to most recent AR of immediate lexical ancestor • Lexical ancestor does not need to be the callerUsing access links (static links) parameterregister save areareturn valuereturn addressaccess linkcaller’s ARPlocal variablesARPparameterregister save areareturn valuereturn addressaccess linkcaller’s ARPlocal variablesparameterregister save areareturn valuereturn addressaccess linkcaller’s ARPlocal variables Cost of access link is proportional to lexical distanceActivation RecordPointerlevel: plevel: p – 2level: p – 1Maintaining Access Links26• Calling level k + 1 procedure1.Pass the caller’s FP as access link2.The caller’s backward chain will work for lower levels • Calling procedure at level i ≤ k1.Find the caller’s link to level i – 1 and pass it to callee2.Its access link will work for lower levelsIf the callee procedure p is nested immediately within the caller procedure q, the access link for p points to the activation record of the most recent activation of q. Setting up access link (the caller does the job):Assuming current level is k:An Improvement: The Display27• table of access links for lower levels• lookup is index from known offset• takes slight amount of time at call• a single display or one per frameTo improve run-time access costs, use a display. Access with the display assume a value described by (l,o)• find slot as DP[l] in display pointer array• add offset to pointer from slot“Setting up the activation frame” now includes display manipulation.Access to Non – Local Data(Lexical Scoping): Display28• Global arrays of pointers to nameable array• Needed ARP is an array access awayUsing a displayARPparameterregister save areareturn valuereturn addresssaved ptrcaller’s ARPlocal variableslevel 0level 1level 2level 3Displayparameterregister save areareturn valuereturn addresssaved ptrcaller’s ARPlocal variablesparameterregister save areareturn valuereturn addresssaved ptrcaller’s ARPlocal variablesExample: reference to looks up p’s APR in display and add 16

Cost of access link is constant (APR + offset)

Display Management

29

Single global display:

On entry to a procedure at level i:
Save the level i display value
push FP into level i display slot

On return:
Restore the level i display value

parameter
register

save area
return value

return address
saved ptr

caller’s ARP
local variables

Procedures

30

• Modularize program structure
– Actual parameter: information passed from caller to callee (Argument)
– Formal parameter: local variable whose value (usually) is received from

caller
• Procedure declaration

– Procedure names, formal parameters, procedure body with formal local
declarations and statement lists, optional result type

Example: void translate(point *p, int dx)

Parameters

31

• Positional association: Arguments associated with formals one-by-one;
Example: C, Pascal, Java, Scheme

• Keyword association: formal/actual pairs; mix of positional and
keyword possible;
Example: Ada

procedure plot(x, y: in real; z: in boolean)
… plot (0.0, 0.0,z ⇒ true)
… plot (z ⇒ true, x ⇒ 0.0, y ⇒ 0.0)

Parameter Association

Parameter Passing Modes
• Pass-by-value: C/C++, Pascal, Java/C# (value types), Scheme
• Pass-by-result: Ada, Algol W
• Pass-by-value-result: Ada, Swift
• Pass-by-reference: Fortran, Pascal, C++, Ruby, ML

Pass-by-value

32

Advantage: Argument protected from changes in callee.
Disadvantage: Copying of values takes execution time and
space, especially for aggregate values (e.g.: structs, arrays)

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;
…
m := 5;
n := 3;
r(m, n);
write m,n;
end

Output:

5 3

Pass-by-reference

33

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k,j: integer)
begin
k := k + 1;
j := j + 2;
end r;

…
m := 5;
n := 3;
r(m, n);
write m, n;

end
Output: Advantage: more efficient than copying

Disadvantage: leads to aliasing, there are two or more
names for the storage location; hard to track side effects

6 5

Pass-by-result

34

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

…
m := 5;
n := 3;
r(m, n);
write m, n;

end

Output:

Program doesn’t compile or has runtime error

ERROR:
CANNOT USE PARAMETERS WHICH ARE UNINITIALIZED

Pass-by-result

35

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := 1;
j := 2;
end r;

…
m := 5;
n := 3;
r(m, n);
write m, n;

end

Output: ?

HERE IS A PROGRAM THAT WORKS

Pass-by-result

36

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := 1;
j := 2;
end r;

…
m := 5;
n := 3;
r(m, n);
write m, n;

end

Output: 1 2

HERE IS A PROGRAM THAT WORKS

Pass-by-result

37

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := 1;
j := 2;
end r;

…
m := 5;
n := 3;
r(m, m);
write m, n;

end

Output: 1 or 2 for m?

Problem: order of copy back makes a difference;
implementation dependent.

NOTE: CHANGE THE CALL

Pass-by-value-result

38

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

…
m := 5;
n := 3;
r(m, n);
write m, n;

end

Output: 6 5
Problem: order of copy back makes a difference;
implementation dependent.

39

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

…
/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], … c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 … 10 on entry
1 2 4 4 5 … 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF “c” IS ASSIGNED TO?

40

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

…
/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], … c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 … 10 on entry
1 2 4 4 5 … 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF “c” IS ASSIGNED TO?

41

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

…
/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], … c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 … 10 on entry
1 2 4 4 5 … 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF “c” IS ASSIGNED TO?

42

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

…
/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], … c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 … 10 on entry
1 2 4 4 5 … 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF “c” IS ASSIGNED TO?

Aliasing

43

Aliasing:

begin
j, k, m: integer;
procedure r(a, b: integer)
begin
b := 3;
m := m * a;
end
…
q(m, k);
q(j, j);
write y;
end

More than two ways to name the same object within a scope

Even without pointers, you can have aliasing through
(globalformal) and (formalformal) parameter passing.

formal/formal ALIAS PAIR
global/formal ALIAS PAIR

Comparison: by-value-result vs. by-reference

44

Actual parameters need to evaluate to L-values (addresses).

begin
y: integer;
procedure p(x: integer)
begin
x := x + 1
x := x + y
end
…
y := 2;
p(y);
write y;
end

Output:
• pass-by-reference: 6
• pass-by-value-result: 5

Note: by-value-result: Requires copying of parameter values (expansive for
aggregate values); does not have aliasing, but copy-back order dependence.

ref: x and y are ALIASED
val-res: x and y are NOT ALIASED

Next Lecture

45

• Read Scott, Chapter 9.1 – 9.3 (4th Edition) or Chapter 8.1 – 8.3
(3rd Edition), Chapter 11.1 – 11.3 (4th Edition)

Things to do:

Procedures

46

• Modularize program structure
– Actual parameter: information passed from caller to callee (Argument)
– Formal parameter: local variable whose value is received from caller

• Procedure declaration
– Procedure names, formal parameters, procedure body with formal local

declarations and statement lists, optional result type

Example: void translate(point *p, int dx)

Parameters

47

• Positional association: Arguments associated with formals one-by-one;
Example: C, Pascal, Java, Scheme

• Keyword association: formal/actual pairs; mix of positional and
keyword possible;
Example: Ada

procedure plot(x, y: in real; z: in boolean)
… plot (0.0, 0.0,z ⇒ true)
… plot (z ⇒ true, x ⇒ 0.0, y ⇒ 0.0)

Parameter Association

Parameter Passing Modes
• Pass-by-value: C/C++, Pascal, Java/C# (value types), Scheme
• Pass-by-result: Ada, Algol W
• Pass-by-value-result: Ada, Swift
• Pass-by-reference: Fortran, Pascal, C++, Ruby, ML

Pass-by-value

48

Advantage: Argument protected from changes in callee.
Disadvantage: Copying of values takes execution time and
space, especially for aggregate values (e.g.: structs, arrays)

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;
…
m := 5;
n := 3;
r(m, n);
write m,n;
end

Output:

5 3

Pass-by-reference

49

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k,j: integer)
begin
k := k + 1;
j := j + 2;
end r;

…
m := 5;
n := 3;
r(m, n);
write m, n;

end
Output: Advantage: more efficient than copying

Disadvantage: leads to aliasing, there are two or more
names for the storage location; hard to track side effects

6 5

Pass-by-result

50

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

…
m := 5;
n := 3;
r(m, n);
write m, n;

end

Output:

Program doesn’t compile or has runtime error

ERROR:
CANNOT USE PARAMETERS WHICH ARE UNINITIALIZED

Pass-by-result

51

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := 1;
j := 2;
end r;

…
m := 5;
n := 3;
r(m, n);
write m, n;

end

Output: ?

HERE IS A PROGRAM THAT WORKS

Pass-by-result

52

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := 1;
j := 2;
end r;

…
m := 5;
n := 3;
r(m, m);
write m, n;

end

Output: 1 or 2 for m?

Problem: order of copy back makes a difference;
implementation dependent.

HERE IS ANOTHER PROGRAM THAT WORKS

NOTE: CHANGE THE CALL

Pass-by-value-result

53

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

…
m := 5;
n := 3;
r(m, n);
write m, n;

end

Output: 6 5
Problem: order of copy back makes a difference;
implementation dependent.

54

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

…
/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], … c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 … 10 on entry
1 2 4 4 5 … 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF “c” IS ASSIGNED TO?

55

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

…
/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], … c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 … 10 on entry
1 2 4 4 5 … 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF “c” IS ASSIGNED TO?

56

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

…
/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], … c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 … 10 on entry
1 2 4 4 5 … 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF “c” IS ASSIGNED TO?

57

begin
c: array[1…10] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

…
/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], … c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 … 10 on entry
1 2 4 4 5 … 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF “c” IS ASSIGNED TO?

Aliasing

58

Aliasing:

begin
j, k, m: integer;
procedure r(a, b: integer)
begin
b := 3;
m := m * a;
end
…
q(m, k);
q(j, j);
write y;
end

More than two ways to name the same object within a scope

Even without pointers, you can have aliasing through
(globalformal) and (formalformal) parameter passing.

formal/formal ALIAS PAIR
global/formal ALIAS PAIR

Comparison: by-value-result vs. by-reference

59

Actual parameters need to evaluate to L-values (addresses).

begin
y: integer;
procedure p(x: integer)
begin
x := x + 1
x := x + y
end
…
y := 2;
p(y);
write y;
end

Output:
• pass-by-reference: 6
• pass-by-value-result: 5

Note: by-value-result: Requires copying of parameter values (expansive for
aggregate values); does not have aliasing, but copy-back order dependence.

ref: x and y are ALIASED
val-res: x and y are NOT ALIASED

Next Lecture

60

• Read Scott, Chapter 9.1 – 9.3 (4th Edition) or Chapter 8.1 – 8.3
(3rd Edition), Chapter 11.1 – 11.3 (4th Edition)

Things to do:

Look up Non-local Variable Reference

61

Access links and control links are used to look for non-local
variable references.

Static Scope:
Access link points to the stack frame of the most recently activated
lexically enclosing procedure

⇒ Non-local name binding is determined at compile time, and
implemented at run-time

Dynamic Scope:
Control link points to the stack frame of caller

⇒ Non-local name binding is determined and implemented at
run-time