lec11
CS 314 Principles of Programming Languages
Prof. Zheng Zhang
Rutgers University
Lecture 11: Names, Scopes, and Binding
October 10, 2018
Class Information
2
• Project 1 posted (open at noon), due Tuesday 10/23 11:55 pm EDT.
• Midterm exam will be on 11/7 Wednesday, in class, closed-book.
• Project 2 will be released immediately after midterm exam.
• My office hour this week is changed to Thursday 4:00pm-5:00pm.
Project 1: overview
3
RISC
Machine Code
optimizer
Example: tinyL.out
RISC
machine code
Example:
optimize < tinyL.out
Output to stdout
… > opt.out
Optimizer
compiler
tinyL.program
tinyL.program
Example:
test1
Example:
compile test1
Output always
“tinyL.out”
Compiler
RISC
machine code run
Output
of execution
Example: run opt.out
Project 1: overview
4
RISC
Machine Code
optimizer
Example: tinyL.out
RISC
machine code
Example:
optimize < tinyL.out
Output to stdout
… > opt.out
Optimizer
compiler
tinyL.program
tinyL.program
Example:
test1
Example:
compile test1
Output always
“tinyL.out”
Compiler
RISC
machine code run
Output
of execution
Example: run opt.out
Project 1: overview
5
RISC
Machine Code
optimizer
Example: tinyL.out
RISC
machine code
Example:
optimize < tinyL.out
Output to stdout
… > opt.out
Optimizer
compiler
tinyL.program
tinyL.program
Example:
test1
Example:
compile test1
Output always
“tinyL.out”
Compiler
RISC
machine code run
Output
of execution
Example: run opt.out
Project 1 Part II: Constant Propagation
6
Constant Propagation: Substitute the values of known constants in
expressions at compile time. Fold multiple instructions into one if
necessary. The constant values might “propagate” and require
multiple passes of analysis.
Example:
Original Code
LOADI Ra #1
LOADI Rb #1
ADD Rc Ra Rb
LOADI Rd #2
LOADI Re #2
ADD Rf Re Rd
ADD Rg Rf Rc
After One Pass
LOADI Rc #2
LOADI Rf #4
ADD Rg Rc Rf
See project description for more details.
Project 1 Part II: Constant Propagation
7
Constant Propagation: Substitute the values of known constants in
expressions at compile time. Fold multiple instructions into one if
necessary. The constant values might “propagate” and require
multiple passes of analysis.
Example:
Original Code
LOADI Ra #1
LOADI Rb #1
ADD Rc Ra Rb
LOADI Rd #2
LOADI Re #2
ADD Rf Re Rd
ADD Rg Rf Rc
After One Pass
LOADI Rc #2
LOADI Rf #4
ADD Rg Rc Rf
See project description for more details.
Project 1 Part II: Constant Propagation
8
Constant Propagation: Substitute the values of known constants in
expressions at compile time. Fold multiple instructions into one if
necessary. The constant values might “propagate” and require
multiple passes of analysis.
Example:
Original Code
LOADI Ra #1
LOADI Rb #1
ADD Rc Ra Rb
LOADI Rd #2
LOADI Re #2
ADD Rf Re Rd
ADD Rg Rf Rc
After One Pass
LOADI Rc #2
LOADI Rf #4
ADD Rg Rc Rf
See project description for more details.
Is this good enough?
Project 1 Part II: Constant Propagation
9
Constant Propagation: Substitute the values of known constants in
expressions at compile time. Fold multiple instructions into one if
necessary. The constant values might “propagate” and require
multiple passes of analysis.
Example:
Original Code
LOADI Ra #1
LOADI Rb #1
ADD Rc Ra Rb
LOADI Rd #2
LOADI Re #2
ADD Rf Re Rd
ADD Rg Rf Rc
After One Pass
LOADI Rc #2
LOADI Rf #4
ADD Rg Rc Rf
See project description for more details.
After Another Pass
LOADI Rg #6
Names, Bindings, and Scope
10
What’s a name?
A name is a mnemonic character string used to represent something else.
Names, Bindings, and Scope
11
• 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 implementation, a memory address.
What’s in a name?
12
• 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
Names, Bindings, and Scope
Bindings – association of a name with the thing it “names”
Binding Time – Choices
13
• Early binding times — more efficient (faster) at run time
• Late binding times — more flexible (postpone binding decision
until more “information” is available)
• Examples of static binding (early):
– functions in C
– types in C
• Examples of dynamic binding (late):
– virtual methods in Java
– dynamic typing in Javascript, Scheme
Note: dynamic linking is somewhat in between static and dynamic
binding; the function signature has to be known (static), but the
implementation is linked and loaded at run time (dynamic).
How to Maintain Bindings
14
• Symbol table: maintained by compiler during compilation
names ⇒ attributes
• Referencing Environment:
maintained by compiler-generated-code during
program execution
names ⇒ memory locations
Scope Example
15
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
Nested Subroutines (Algol 60, Ada, Common Lisp, Python, ….)
local variable,
procedure def.
implementation
Scope Example
16
Nested Subroutines (Algol 60, Ada, Common Lisp, Python, ….)
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
Scope Example
17
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
Nested Subroutines (Algol 60, Ada, Common Lisp, Python, ….)
Scope Example
18
Nested Subroutines (Algol 60, Ada, Common Lisp, Python, ….)
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
Scope Example
19
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
Nested Subroutines (Algol 60, Ada, Common Lisp, Python, ….)
Scope Example
20
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
Nested Subroutines (Algol 60, Ada, Common Lisp, Python, ….)
Scope Example
21
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
Nested Subroutines (Algol 60, Ada, Common Lisp, Python, ….)
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
Lexical Scope
22
• 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
L ⇒ W
L ⇒ D ⇒ W
Calling Chain:
The output is ?
Lexical Scope
23
• 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
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
L ⇒ W
L ⇒ D ⇒ W
Calling Chain:
The output is ?
Lexical Scope
24
• 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
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
L ⇒ W
L ⇒ D ⇒ W
Calling Chain:
The output is ?
Lexical Scope
25
• 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
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
L ⇒ W
L ⇒ D ⇒ W
Calling Chain:
The output is ?
Which “n”?
Lexical Scope
26
• 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
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
L ⇒ W
L ⇒ D ⇒ W
Calling Chain:
The output is ?
Which “n”?
L
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
Lexical Scope
27
• 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
L ⇒ W
L ⇒ D ⇒ W
Calling Chain:
The output is ?
L
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
Lexical Scope
28
• 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
L ⇒ W
L ⇒ D ⇒ W
Calling Chain:
The output is ?
L
Caller
Lexical Scope
29
• 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
L ⇒ W
L ⇒ D ⇒ W
Calling Chain:
The output is ?
L
Which “n”?
L
Caller
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
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
30
• 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
L ⇒ W
L ⇒ D ⇒ W
Calling Chain:
The output is ?
Caller
L
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}
W;
D
end
Lexical Scope v.s. Dynamic Scope
31
• 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
Review: Program Memory Layout
32
• 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
33
• 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
34
• 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
Lexical Scoping and Dynamic Scoping Implementation
35
How do we look for non-local variables?
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
Lexical Scoping and Dynamic Scoping Implementation
36
How do we look for non-local variables?
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
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
Lexical Scoping and Dynamic Scoping Implementation
37
How do we look for non-local variables?
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
Lexical Scoping and Dynamic Scoping Implementation
38
How do we look for non-local variables?
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
Lexical Scoping and Dynamic Scoping Implementation
39
How do we look for non-local variables?
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
Lexical Scoping and Dynamic Scoping Example
40
Calling chain: MAIN⇒ C ⇒ B ⇒ B Control linksAccess links
fp
main
o
o
x
y
C
o
o
x
B
o
o
y
z
B
o
o
y
z
Look up Non – local Variable Reference
41
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
Access to Non-Local Data
42
• visible everywhere
• translated into a logical address at compile time
How does the code find non-local data at run-time?
Real globals:
Lexical scoping:
• view variables as (level, offset) pairs, (compile-time symbol table)
• use (level, offset) pair to get address by using chains of access link
(at run-time)
Dynamic scoping:
• variable names are preserved
• look-up of variable name uses chains of control links (at run-time)
Lexical Scoping
43
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
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
Lexical Scoping
44
Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).
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
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
Lexical Scoping
45
Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).
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
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
Lexical Scoping
46
Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).
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
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
Lexical Scoping
47
Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).
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
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
Lexical Scoping
48
Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).
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
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
Lexical Scoping
49
Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).
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
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
Lexical Scoping
50
Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).
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
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
Lexical Scoping
51
Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).
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
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
Lexical Scoping
52
Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).
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
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
Lexical Scoping
53
Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).
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
54
• Assume the nesting level of the statement is level 2
• Register r0 contains the current FP (frame pointer)
• (2, 1) and (2, 2) are local variables, so they are allocated in the
activation record that current FP points to.
(1, 1) is an non-local variable.
• Two new instructions:
LOAD Rx, Ry means Rx ← MEM(Ry)
STORE Rx, Ry means MEM(Rx) ← Ry
Access to Non-Local Data(Lexical Scoping)
What code do we need to generate for this statement:
(2,1) = (1,1) + (2,2)
What do we know?
Lexical Scoping
55
Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).
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
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
Review: Access to Non-Local Data(Lexical Scoping)
56
What code do we need to generate for statement (*)?
(2,1) = (1,1) + (2,2)
parameter
return value
return address
access link
caller FP
local variables
Low
High
parameter
return value
return address
access link
caller FP
local variables
Level 1
Level 2 —> Current Level
Frame Pointer
FP
Current
Frame Pointer
FP
Lexical Parent
Saved in r0
Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.
// offset of local variable (1,1) in frame
// offset of access link in frame (bytes)
// address of access link
// get access link
// address of local variable (1,1) in frame
// get content of variable (1,1)
// offset of local variable (2,2) in frame
// address of local variable (2,2)
// get content of variable (2, 2)
// (1,1) + (2,2)
// offset of local variable (2,1) in frame
// address of local variable (2,1)
// (2,1) = (1,1) + (2,2)
Access to Non-Local Data(Lexical Scoping)
57
What code do we need to generate for statement (*)?
(2,1) = (1,1) + (2,2)
(1,1) LOADI r1, #4
LOADI r2, #-4
ADD r3 r0 r2
LOAD r4 r3
ADD r5 r4 r1
LOAD r6 r5
(2,2) LOADI r7 #8
ADD r8 r0 r7
LOAD r9 r8
+ ADD r10 r6 r9
(2,1) LOADI r11 #4
ADD r12 r0 r11
= STORE r12 r10
parameter
return value
return address
access link
caller FP
local variables
Frame Pointer
FP
Low
High
parameter
return value
return address
access link
caller FP
local variables
Level 1
Level 2 —> Current Level
Frame Pointer
FP
Saved in r0
Current
Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.
// offset of local variable (1,1) in frame
// offset of access link in frame (bytes)
// address of access link
// get access link
// address of local variable (1,1) in frame
// get content of variable (1,1)
// offset of local variable (2,2) in frame
// address of local variable (2,2)
// get content of variable (2, 2)
// (1,1) + (2,2)
// offset of local variable (2,1) in frame
// address of local variable (2,1)
// (2,1) = (1,1) + (2,2)
Access to Non-Local Data(Lexical Scoping)
58
What code do we need to generate for statement (*)?
(2,1) = (1,1) + (2,2)
(1,1) LOADI r1, #4
LOADI r2, #-4
ADD r3 r0 r2
LOAD r4 r3
ADD r5 r4 r1
LOAD r6 r5
(2,2) LOADI r7 #8
ADD r8 r0 r7
LOAD r9 r8
+ ADD r10 r6 r9
(2,1) LOADI r11 #4
ADD r12 r0 r11
= STORE r12 r10
parameter
return value
return address
access link
caller FP
local
variables
Frame Pointer
FP
Low
High
parameter
return value
return address
access link
caller FP
local variables
Level 1
Level 2 —> Current Level
Frame Pointer
FP
Saved in r0
Current
Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.
// offset of local variable (1,1) in frame
// offset of access link in frame (bytes)
// address of access link
// get access link
// address of local variable (1,1) in frame
// get content of variable (1,1)
// offset of local variable (2,2) in frame
// address of local variable (2,2)
// get content of variable (2, 2)
// (1,1) + (2,2)
// offset of local variable (2,1) in frame
// address of local variable (2,1)
// (2,1) = (1,1) + (2,2)
Access to Non-Local Data(Lexical Scoping)
59
What code do we need to generate for statement (*)?
(2,1) = (1,1) + (2,2)
(1,1) LOADI r1, #4
LOADI r2, #-4
ADD r3 r0 r2
LOAD r4 r3
ADD r5 r4 r1
LOAD r6 r5
(2,2) LOADI r7 #8
ADD r8 r0 r7
LOAD r9 r8
+ ADD r10 r6 r9
(2,1) LOADI r11 #4
ADD r12 r0 r11
= STORE r12 r10
parameter
return value
return address
access link
caller FP
local
variables
Frame Pointer
FP
Low
High
parameter
return value
return address
access link
caller FP
local variables
Level 1
Level 2 —> Current Level
Frame Pointer
FP
Saved in r0
Current
Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.
// offset of local variable (1,1) in frame
// offset of access link in frame (bytes)
// address of access link
// get access link
// address of local variable (1,1) in frame
// get content of variable (1,1)
// offset of local variable (2,2) in frame
// address of local variable (2,2)
// get content of variable (2, 2)
// (1,1) + (2,2)
// offset of local variable (2,1) in frame
// address of local variable (2,1)
// (2,1) = (1,1) + (2,2)
Access to Non-Local Data(Lexical Scoping)
60
What code do we need to generate for statement (*)?
(2,1) = (1,1) + (2,2)
(1,1) LOADI r1, #4
LOADI r2, #-4
ADD r3 r0 r2
LOAD r4 r3
ADD r5 r4 r1
LOAD r6 r5
(2,2) LOADI r7 #8
ADD r8 r0 r7
LOAD r9 r8
+ ADD r10 r6 r9
(2,1) LOADI r11 #4
ADD r12 r0 r11
= STORE r12 r10
parameter
return value
return address
access link
caller FP
local variables
Frame Pointer
FP
Low
High
parameter
return value
return address
access link
caller FP
local variables
Level 1
Level 2 —> Current Level
Frame Pointer
FP
Saved in r0
Current
Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.
// offset of local variable (1,1) in frame
// offset of access link in frame (bytes)
// address of access link
// get access link, fp for frame at level 1
// address of local variable (1,1) in frame
// get content of variable (1,1)
// offset of local variable (2,2) in frame
// address of local variable (2,2)
// get content of variable (2, 2)
// (1,1) + (2,2)
// offset of local variable (2,1) in frame
// address of local variable (2,1)
// (2,1) = (1,1) + (2,2)
Access to Non-Local Data(Lexical Scoping)
61
What code do we need to generate for statement (*)?
(2,1) = (1,1) + (2,2)
(1,1) LOADI r1, #4
LOADI r2, #-4
ADD r3 r0 r2
LOAD r4 r3
ADD r5 r4 r1
LOAD r6 r5
(2,2) LOADI r7 #8
ADD r8 r0 r7
LOAD r9 r8
+ ADD r10 r6 r9
(2,1) LOADI r11 #4
ADD r12 r0 r11
= STORE r12 r10
parameter
return value
return address
access link
caller FP
local variables
Frame Pointer
FP
Low
High
parameter
return value
return address
access link
caller FP
local variables
Level 1
Level 2 —> Current Level
Frame Pointer
FP
Saved in r0
Current
Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.
Saved in r4
// offset of local variable (1,1) in frame
// offset of access link in frame (bytes)
// address of access link
// get access link, fp for frame at level 1
// address of local variable (1,1) in frame
// get content of variable (1,1)
// offset of local variable (2,2) in frame
// address of local variable (2,2)
// get content of variable (2, 2)
// (1,1) + (2,2)
// offset of local variable (2,1) in frame
// address of local variable (2,1)
// (2,1) = (1,1) + (2,2)
Access to Non-Local Data(Lexical Scoping)
62
What code do we need to generate for statement (*)?
(2,1) = (1,1) + (2,2)
(1,1) LOADI r1, #4
LOADI r2, #-4
ADD r3 r0 r2
LOAD r4 r3
ADD r5 r4 r1
LOAD r6 r5
(2,2) LOADI r7 #8
ADD r8 r0 r7
LOAD r9 r8
+ ADD r10 r6 r9
(2,1) LOADI r11 #4
ADD r12 r0 r11
= STORE r12 r10
parameter
return value
return address
access link
caller FP
local variables
Frame Pointer
FP
Low
High
parameter
return value
return address
access link
caller FP
local variables
Level 1
Level 2 —> Current Level
Frame Pointer
FP
Saved in r0
Current
Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.
Saved in r4
// offset of local variable (1,1) in frame
// offset of access link in frame (bytes)
// address of access link
// get access link, fp for frame at level 1
// address of local variable (1,1) in frame
// get content of variable (1,1)
// offset of local variable (2,2) in frame
// address of local variable (2,2)
// get content of variable (2, 2)
// (1,1) + (2,2)
// offset of local variable (2,1) in frame
// address of local variable (2,1)
// (2,1) = (1,1) + (2,2)
Access to Non-Local Data(Lexical Scoping)
63
What code do we need to generate for statement (*)?
(2,1) = (1,1) + (2,2)
(1,1) LOADI r1, #4
LOADI r2, #-4
ADD r3 r0 r2
LOAD r4 r3
ADD r5 r4 r1
LOAD r6 r5
(2,2) LOADI r7 #8
ADD r8 r0 r7
LOAD r9 r8
+ ADD r10 r6 r9
(2,1) LOADI r11 #4
ADD r12 r0 r11
= STORE r12 r10
parameter
return value
return address
access link
caller FP
local variables
Frame Pointer
FP
Low
High
parameter
return value
return address
access link
caller FP
local
variables
Level 1
Level 2 —> Current Level
Frame Pointer
FP
Saved in r0
Current
Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.
Saved in r4
Next Lecture
64
• Read Scott, Chapter 3.1 – 3.4, Chapter 9.1 – 9.3 (4th Edition) or
Chapter 8.1 – 8.3 (3rd Edition)
• Read ALSU, Chapter 7.1 – 7.3 (2nd Edition).
Things to do: