Scope, Functions and Storage Management
Mitchell Chapter 7
Implementing Programming Languages
• In this chapter, storage management for block-structured languages is described by the run-time data structures that are used in a simple reference implementation.
• Association between names in programs and memory locations is a key aspect.
– Scope: allows two syntactically identical names to refer to different locations, or two different names to refer to the same location
– Function calls: require a new memory area to store function parameters and local variables
2
Reference Implementation
• An implementation of a language
• Designed to define the behavior of the language
• Need not be efficient
• Goal is to understand programming languages (not build a compiler)
– How blocks are implemented in most languages
– When storage needs to be allocated
– What kinds of data are stored on the run-time stack
– How executing programs access the data and location they need
– Simple and direct because goal is understanding programming language.
– Compiler books discuss more efficient methods
3
Block-Structured Languages
• Blocks
– A block is a region of program text, identified by begin and end markers, that may contain declarations local to this region.
• Nested blocks, local variables
– Example
{ int x = 2;
new variables declared in nested blocks
outer block
{ int y = 3; x = y+2;
} }
inner block
y is local variable (in inner block) x is global variable (in inner block)
• Storage management
– Enter block: allocate space for variables
– Exits block: some or all space may be deallocated
4
outer block
Block-Structured Languages
{ int x = 2;
{ int y = 3;
x = y+2;
} }
inner block
• Summary
– The above is C code. This chapter also uses Algol-like pseudo-
code and ML. (The ML is translated to OCaml on the slides.)
– A local variable is a variable declared in a block
– A global variable is a variable declared in an enclosing block.
– In this example, in the inner block, y is local and x is global.
– In the outer block, x is local and y is not visible.
5
Examples
• Blocks in common languages
–C {…}
– Algol begin … end – ML (OCaml) let … in …
• Two forms of blocks – In-line blocks
– Blocks associated with functions or procedures
• Current Topic
– block-based memory management, access to local variables, parameters, global variables
6
Kinds of Blocks (OCaml Examples)
• Simple in-line block let x=3 in
(x,x)
• Nested block let x=3 in
let y = 4 in (x,y)
• Functions and procedures let f x = x+3 in
f2
7
Kinds of Function Blocks (in OCaml)
• Functions with static scope (first-order functions)
• Functions as arguments and results (higher-order programming)
• Functions returned from nested scope (with pointers/references)
let x=3 in
let f z = x+z in f5
let h x = x+x in let compose f g =
(fun x -> g (f x)) in compose h h
let counter () = let c = ref 0 in
fun () ->
let v = !c in (c := v+1 ; v)
8
Simplified Machine Model
Registers Code Data
Stack
Program Counter
Environment Pointer
Heap
9
Registers
Simplified Machine Model
Code Data
This model separates code memory from data memory
Stack
Program Counter
Environment Pointer
PC stores address of current program instruction, normally incremented by 1 at each step of execution.
Heap
10
Interested in Memory Management Only
• Registers, Code segment, Program counter – Ignore registers
– Details of instruction set will not matter
• Data Segment
– Stack contains data related to block entry/exit
– Heap contains data of varying lifetime (e.g., the cells pointed to by references)
– Environment pointer points to current stack position • On block entry: add new activation record to stack
• On block exit: remove most recent activation record
• Activation record sometimes called a stack frame.
11
In-line Blocks – Data structure stored on run-time stack
• Activation record
– Contains space for local variables
• Example
{ int x=0; int y=x+1;
{ int z=(x+y)*(x-y); };
};
Push record with space for x, y Set values of x, y
Push record for inner block Set value of z
Pop record for inner block
Pop record for outer block
May need space for variables and intermediate results like (x+y), (x-y)
12
Activation Stack
Space for global variables
Space for x,y
Space for z
Space for global variables
Space for x,y
Space for global variables
Space for x,y
Space for global variables
{ int x=0; int y=x+1;
{ int z=(x+y)*(x-y); };
};
Note: stacks are drawn “upside down” (they grow downward).
13
{ int x=0; int y=x+1;
Activation Stack
Space for global variables
Space for x,y
Space for z Space for x+y Space for x-y
{ int z=(x+y)*(x-y); };
};
Stack with space for intermediate results in the inner block.
14
Scope and Lifetime
• Scope
– Region of program text where declaration is visible
• Lifetime
– Period of time when location is allocated to program
{ int x = … ;
{ inty=…;
{ intx=…; ….
}; };
};
– Inner declaration of x hides outer one.
– Called “hole in scope”
– Lifetime of outer x includes time when inner block is executed
– Lifetime 1 scope
– Lines indicate “contour model” of scope.
15
Blocks in ML: Standard ML vs. OCaml
• let … in … end in Standard ML (SML) forms one block.
• equivalent to {…;…} in C
SML:
let fun g(y) = y+3 fun h(z) = g(g(z))
in
h(3)
end
OCaml:
let g y = y+3 in let h z = g(g(z)) in h(3)
• In SML, g and h will be given values in the same activation record.
• In OCaml, each let … in … is a separate block, but compilers usually
can optimize to combine blocks.
• In SML and OCaml, …in… separates declarations from expressions. In
C, declarations and expressions can be mixed.
16
Activation Record for In-line Block
Control link
Local variables
Intermediate results
Control link
Local variables
Intermediate results
Environment Pointer
• Control link (Dynamic link)
– pointer to previous record on
stack
• Push record on stack:
– Set new control link to point to old
environment pointer
– Set environment pointer to new record
• Pop record off stack
– Follow control link of current record to reset environment pointer
Control links can be optimized away, but assume not for purpose of discussion.
17
Possible Optimizations
• Compiler can generate code for block entry that is tailored to the size of the activation record (which is known at compile time)
• Compiler can compute number of blocks between current block and location of a global variable and generate lookup code that avoids following pointer chains.
18
{ int x=0; int y=x+1;
Example
Control link
x
0
y
1
{ int z=(x+y)*(x-y); };
};
Control link
z
-1
x+y
1
x-y
-1
Push record with space for x, y Set values of x, y
Push record for inner block Set value of z
Pop record for inner block
Pop record for outer block
Environment Pointer
19
• Global and local variables
– x, y are local to outer block – z is local to inner block
– x, y are global to inner block – z is not visible in outer block
{ int x=0; int y=x+1;
{ int z=(x+y)*(x-y); };
};
Scoping Rules
• Static scope
– global refers to declaration in closest enclosing block
• Dynamic scope
– global refers to most recent activation record
Dynamic and static are the same until we consider function calls.
20
Functions and Procedures
• Syntax of procedures (Algol) and functions (C)
procedure P (
};
• Activation record must include space for: – parameters
– return address
– return value (an intermediate result)
– location to put return value on function exit
21
Activation Record for Function
• Return address
– Location of code to execute on
function return
• Return-result address
– Address in activation record of calling block to receive return value
• Parameters
– Locations to contain data from calling block
Control link
Return address
Return-result addr
Parameters
Local variables
Intermediate results
Environment Pointer
22
Activation Record for Function
• Return address
The control link points
Control link
Return address
Return-result addr
Parameters
Local variables
Intermediate results
– Location of code to execute on to an activation
function return
record (in the stack part of the data
• Return-result address memory).
Environment Pointer
Return result can go in the intermediate results section.
– Address in activation record of The return-result
code to execute (in
calling block to receive return
value
• Parameters The return address
points to the next
address points to some location in a previous activation
– Locations to contain data from
calling block
record.
the code memory).
23
Control link
Return address
Return-result addr
Parameters
Local variables
Intermediate results
Environment Pointer
Example
• Function
fact(n) = if n<= 1 then 1
else n * fact(n-1)
• Return-result address
– location to put the result of the
function evaluation fact(n)
• Parameter
– set to value of n when function is called
• Local variables – none
• Intermediate result – value of fact(n-1)
24
fact(k)
Function Call
fact(n) = if n<= 1 then 1 else n * fact(n-1)
Control link
Return address
Return-result addr
n
k
fact(n-1)
the return-result address of recursive call
Environment Pointer
25
fact(3)
Function Call
fact(n) = if n<= 1 then 1 else n * fact(n-1)
(Return address omitted)
Control link
Return-result addr
n
3
fact(n-1)
26
fact(3)
Function Call
fact(n) = if n<= 1 then 1 else n * fact(n-1)
(Return address omitted)
Control link
Return-result addr
n
3
fact(n-1)
fact(2)
Control link
Return-result addr
n
2
fact(n-1)
27
fact(3)
Function Call
fact(n) = if n<= 1 then 1 else n * fact(n-1)
(Return address omitted)
Control link
Return-result addr
n
fact(n-1)
3
fact(2)
Control link
Return-result addr
n
fact(1)
fact(n-1)
Return-result addr
2
Control link
n
1
fact(n-1)
28
fact(3)
Function Return
fact(n) = if n<= 1 then 1 else n * fact(n-1)
(Return address omitted)
Control link
Return-result addr
n
fact(n-1)
3
fact(2)
Control link
Return-result addr
n
2
fact(1)
fact(n-1)
1
Control link
Return-result addr
n
1
fact(n-1)
29
fact(3)
Function Return
fact(n) = if n<= 1 then 1 else n * fact(n-1)
(Return address omitted)
Control link
Return-result addr
n
3
fact(n-1)
fact(2)
Control link
Return-result addr
n
2
fact(n-1)
1
30
fact(3)
Function Return
fact(n) = if n<= 1 then 1 else n * fact(n-1)
(Return address omitted)
Control link
Return-result addr
n
3
fact(n-1)
2
fact(2)
Control link
Return-result addr
n
2
fact(n-1)
1
31
Function Return
fact(3)
Control link
Return-result addr
3 fact(n-1) 2
fact(n) = if n<= 1 then 1 else n * fact(n-1)
(Return address omitted)
n
3*2 is evaluated and returned
32
Topics for First-Order Functions
• Parameter passing
– use ML reference cells to describe pass-by-value, pass-by-
reference
• Access to global variables
– global variables are contained in an activation record higher
“up” the stack
• Tail recursion
– an optimization for certain recursive functions
33
proc p (int x, int y) {
if (x > y) then … else …;
…x := y*2+3; }…
p (z, 4*z+1);
• The identifiers x and y are formal parameters of the procedure p.
• The actual parameters in the call to p are z and 4*z+1.
• The way that actual parameters are evaluated and passed to the function depends on the kind of parameter-passing mechanism that is used (different for different languages).
Parameter Passing
34
ML Imperative Features
• General terminology: L-values and R-values
– Assignment y := x+3
• Identifier on left refers to location, called its L-value • Identifier on right refers to contents, called R-value
• Recall ML (OCaml) reference cells and assignment – Different types for location and contents
x : int
y : int ref !y
ref x
non-assignable integer value
location whose contents must be integer
the contents of cell y
expression creating new cell initialized to x
– ML form of assignment
y := x+3 place value of x+3 in location (cell) y
y := !y+3add3tocontentsofyandstoreinlocationy
35
Parameter Passing
• Pass-by-value
– Caller places R-value (contents) of actual parameter in activation
record
– Function cannot change value of caller’s variable
– Reduces aliasing (alias: two names refer to same location)
• Pass-by-reference
– Caller places L-value (address) of actual parameter in activation
record
– Function can assign to variable that is passed
36
Pseudo-code:
Example
OCaml:
let f (x : int ref) = (x:=!x+1; !x )in
let y = ref 0 in let z = f(y) in z + !y
let f (w : int) = (let x = ref w in
x := !x+1; !x) in let y = ref 0 in
let z = f(!y) in
z + !y
function f (x) = {x:=x+1;returnx };
var y : int = 0; f(y)+y;
37
pass-by- reference
pass-by-value
Access to Global Variables
• Two possible scoping conventions, recall:
– Static scope: global refers to declaration in closest enclosing
block
– Dynamic scope: global refers to most recent activation record
– As before, each let … in … is a separate block, but only at the top level. Inside function definitions a series of let … in … declarations in parentheses will be considered local variables of the function.
• Example
let x = 1 in
let g z = x + z in let f y =
(let x = y + 1 in g (y*x)) in
f3
Skeleton of Activation Stack
outer block f(3)
g(12)
Which x is used for expression x+z? 38
x
1
y
3
x
4
z
12
Access to Global Variables
Which x is used for expression x+z? • Dynamic Scope
Under dynamic scope, the identifier x in x+z will be interpreted as the one from the most recently created activation record, namely x=4.
How do we implement access to global variables?
Answer: follow the control link (which is also called a dynamic link).
x
1
let x = 1 in
let g z = x + z in let f y =
(let x = y + 1 in g (y*x)) in
f3
outer block f(3)
g(12)
y
3
x
4
z
12
39
Access to Global Variables
Which x is used for expression x+z? • Static Scope
Under static scope, the identifier x in x+z refers to the declaration of x from the closest enclosing program block, looking upward from the place that x+z appears in the program. Thus, x=1.
OCaml is static.
How do we implement access to global variables in this case?
x
1
let x = 1 in
let g z = x + z in let f y =
(let x = y + 1 in g (y*x)) in
f3
outer block f(3)
g(12)
y
3
x
4
z
12
40
Activation Record for Static Scope
Control link
Access link
Return address
Return-result addr
Parameters
Local variables
Intermediate results
Environment Pointer
• Control link
– Link to activation record of
previous (calling) block
• Access link
– Link to activation record of closest enclosing block in program text
• Difference
– Control link depends on dynamic behavior of program
– Access link depends on static form of program text
41
Control link
Access link
Return address
Return-result addr
Parameters
Local variables
Intermediate results
Environment Pointer
Access Links for Static Scope
• Access link
– The access link (also called a static link) of an activation record points to the activation record of the closest enclosing block in the program.
• Inline blocks
– In-line blocks do not need them; the control link points to the closest enclosing block.
• Functions
– The closest enclosing block is determined by where the function is declared, which is often different from the point where the function is called.
42
Static Scope with Access Links
control link
access link
x
1
let x = 1 in
let g z = x + z in
let f y =
(let x = y + 1 in
g (y*x)) in f3
outer block
43
Static Scope with Access Links
control link
access link
x
1
let x = 1 in
let g z = x + z in
let f y =
(let x = y + 1 in
g (y*x)) in f3
Use access link to find global variable:
outer block
control link
access link
g
…
– Access link is always set to frame of closest enclosing lexical block
Static Scope with Access Links
control link
access link
x
1
let x = 1 in
let g z = x + z in
let f y =
(let x = y + 1 in
g (y*x)) in f3
Use access link to find global variable:
outer block
control link
access link
g…
includes pointer to code
– Access link is always set to frame of closest enclosing lexical block
For declarations, access link and control link are the same.
Static Scope with Access Links
control link
access link
x
1
let x = 1 in
let g z = x + z in
let f y =
(let x = y + 1 in
g (y*x)) in f3
Use access link to find global variable:
outer block
control link
access link
g
…
control link
access link
f
…
– Access link is always set to frame of closest enclosing lexical block
Static Scope with Access Links
control link
access link
x
1
let x = 1 in
let g z = x + z in
let f y =
(let x = y + 1 in
g (y*x)) in f3
Use access link to find global variable:
outer block
control link
access link
g
…
control link
access link
f
…
control link
access link
y
3
x
4
– Access link is always set to frame of closest enclosing lexical block
– For function body, this is block that contains function declaration
f(3)
47
Static Scope with Access Links
control link
access link
x
1
let x = 1 in
let g z = x + z in
let f y =
(let x = y + 1 in
g (y*x)) in f3
Use access link to find global variable:
– Access link is always set to frame of closest enclosing lexical block
– For function body, this is block that contains function declaration
outer block
control link
access link
g
…
control link
access link
f
…
For f(3), the two
4
control link
f(3)
access link
y3
links are th
same because f is called right after it is defined
x
e
48
Static Scope with Access Links
control link
access link
x
1
let x = 1 in
let g z = x + z in
let f y =
(let x = y + 1 in
g (y*x)) in f3
Use access link to find global variable:
outer block
control link
access link
g
…
control link
access link
f
…
control link
access link
y
3
x
4
– Access link is always set to frame of closest enclosing lexical block
– For function body, this is block that contains function declaration
f(3)
g(12)
control link
access link
z
12
49
Static Scope with Access Links
control link
access link
x
1
let x = 1 in
let g z = x + z in
let f y =
(let x = y + 1 in
g (y*x)) in f3
Use access link to find global variable:
outer block
control link
access link
g
…
control link
access link
f
…
– Access link is always set to frame The compiler
f(3)
access link
of closest enclosing lexical block
y3 x4
control link access link z 12
– For function body, this is block out from
that contains function
declaration
g(12)
can figure this
control link
program text (g called from inside f)
50
Tail Recursion (First-Order Case)
• Function g makes a tail call to function f if
– Return value of function f is return value of g
• Example
tail call
not a tail call
• Optimization
– Can pop activation record on a tail call – Especially useful for recursive tail call
• next activation record has exactly same form
• A function f is tail recursive if all recursive calls in the body are tail calls to f.
let g x = if x>0 then f(x) else f(x)*2
51
Example: Calculate least power of 2 greater than y
Control link
Return-result addr
x
1
y
3
f(2*x,y)
f(1,3)
let rec f(x,y) = if x>y
then x
else f(2*x, y) in f(1,3) + 7
f(2,3)
Control link
Return-result addr
x
2
y
3
f(2*x,y)
f(4,3)
Control link
Return-result addr
x
4
y
3
f(2*x,y)
52
Example: Calculate least power of 2 greater than y
Control link
Return-result addr
x
1
y
3
f(2*x,y)
f(1,3)
let rec f(x,y) = if x>y
then x
else f(2*x, y) in f(1,3) + 7
• Optimization 1
– Setreturn-resultaddresstothe
return-result address of caller.
– Canwedothesamewiththecontrol link?
Yes, since the activation records are not needed after final result is determined and passed all the way up.
f(2,3)
Control link
Return-result addr
x
2
y
3
f(2*x,y)
f(4,3)
Control link
Return-result addr
x
4
y
3
f(2*x,y)
53
Example: Calculate least power of 2 greater than y
Control link
Return-result addr
x
1
y
3
f(2*x,y)
f(1,3)
• Optimization 2
– When 3rd call finishes, we can pop 3rd and 2nd activation records together.
– In fact, we can pop all three.
• Optimization 3
– The activation record for the first call is no longer needed when the second call begins; pop the first before allocating the second.
• Optimization 4
– Even better, don’t deallocate and reallocate, just reuse.
f(2,3)
Control link
Return-result addr
x
2
y
3
f(2*x,y)
f(4,3)
Control link
Return-result addr
x
4
y
3
f(2*x,y)
54
f(1,3)
f(2,3) f(4,3)
Tail Recursion Elimination
Control link
Return-result addr
x
1
y
3
f(2*x,y)
Control link
Return-result addr
x
2
y
3
f(2*x,y)
Control link
Return-result addr
x
4
y
3
f(2*x,y)
4
let rec f(x,y) = if x>y
then x
else f(2*x, y) in f(1,3) + 7
• Conclusion
– Tail recursive function equivalent to iterative loop
55
Tail Recursion and Iteration
f(1,3) f(2,3)
f(4,3)
Control link
Return-result addr
x
1
y
3
f(2*x,y)
Control link
Return-result addr
x
2
y
3
f(2*x,y)
Control link
Return-result addr
x
4
y
3
f(2*x,y)
4
let rec f(x,y) = if x>y
then x
else f(2*x, y) in f(1,3) + 7
initial value
fun g(y) = { x := 1;
while not(x>y) do x := 2*x;
return x; };
56
test
loop body
Higher-Order Functions
• A language has first-class functions if functions can be: – Declared within any scope
– Passed as arguments to other functions
– Returned as results of functions
• Need to maintain environment of function
• Simpler case
– Function passed as argument
– Need pointer to activation record “higher up” in stack
• More complicated second case
– Function returned as result of function call
– Need to keep activation record of returning function
57
let x = 4 in
let f(y) = x*y in
let g(h) = (let x = 7
in
h(3) + x) in g(f)
{ int x = 4;
{ int f(int y) {return x*y;}
{ int g(int®int h) { int x=7;
return h(3) + x;
Pass Function as Argument
There are two declarations of x.
Which one is used for each occurrence of x?
}
g(f); }}}
58
let x = 4 in
let f(y) = x*y in
let g(h) = (let x = 7
in
h(3) + x) in g(f)
{ int x = 4;
{ int f(int y) {return x*y;}
Pass Function as Argument
{ int g(int®int h) { int x=7;
There are two declarations of x.
When f is called inside
The body of f contains the global variable x.
This is the environment
of f. g(f);
}}}
}
return h(3) + x;
Which one is used for each occurrence of x? g (because f is the
value of parameter h), the value of x must be retrieved from the activation record of the outer block (static scope).
59
Static Scope for Function Argument
let x = 4 in
let f(y) = x*y in
let g(h) = (let x = 7
in g(f)
h(3) + x) in g(f)
h(3)
x is global; follow access link
x
4
Code for f
f
g
Code for g
access link
h
x
7
access link
y
3
x*y
??
y is local
60
Static Scope for Function Argument
let x = 4 in
let f(y) = x*y in
let g(h) = (let x = 7
in g(f)
x
4
Code for f
f
g
access link
h
x
7
h(3) + x) in g(f)
g can call different functions depending on
??
access link
Code for g
h(3)
3
y
value of h; can’t tell from program text what values h will get
How is access link for h(3) set?
x is global; follow access link
x * y
y is local
61
Static Scope for Function Argument
{ int x = 4;
{ int f(int y) {return x*y;}
{ int g(int®int h) {
int x=7;
return h(3) + x; }
x
4
Code for f
f
g
Code for g
access link
h
x
7
access link
y
3
g(f); }}}
g(f)
h(3)
??
y is local
x is global; follow access link
x*y
62
Closures
• With first-class functions and static scope, need a closure which is a pair:
– Pointer to function code
– Pointer to activation record (the environment of the function)
• Function value (when passed as a parameter) is a closure
• When a function represented by a closure is called,
– Allocate activation record for call (as always)
– Set the access link in the activation record using the environment pointer from the closure
• C and C++ do not support closures (because of implementation costs, though objects are like closures because they combine data with code for functions).
63
let x = 4 in
let f(y) = x*y in
let g(h) = (let x = 7
in
h(3) + x) in g(f)
Function Argument and Closures
Run-time stack with access links
x
4
Code for f
Code for g
64
let x = 4 in
let f(y) = x*y in
let g(h) = (let x = 7
in
h(3) + x) in g(f)
Function Argument and Closures
Run-time stack with access links
x
4
Code for f
access
link
f
Code for g
65
x
4
Code for f
access
link
f
access
link
g
Code for g
let x = 4 in
let f(y) = x*y in
let g(h) = (let x = 7
in
h(3) + x) in g(f)
Function Argument and Closures
Run-time stack with access links
66
let x = 4 in
let f(y) = x*y in
let g(h) = (let x = 7
in
h(3) + x) in g(f)
g(f)
Function Argument and Closures
Run-time stack with access links
x
4
Code for f
access
link
f
access
link
g
Code for g
access
link
h
x
7
67
let x = 4 in
let f(y) = x*y in
let g(h) =
Function Argument and Closures
Run-time stack with access links
x
4
Code for f
access
link
f
(let x = 7 in
h(3) + x) in g(f)
g(f) called from block where g is local.
access
link
g
Code for g
g(f)
access
link
h
x
7
set access link from first
element of closure
Follow code pointer for code to execute
68
let x = 4 in
let f(y) = x*y in
let g(h) = (let x = 7
in
h(3) + x) in g(f)
g(f)
Function Argument and Closures
Run-time stack with access links
x
4
Code for f
access
link
f
access
link
g
Code for g
access
link
h
x
7
f is global in the call g(f) so is accessed via an access link; f is passed as actual parameter for formal parameter h
69
let x = 4 in
let f(y) = x*y in
let g(h) = (let x = 7
in
h(3) + x) in g(f)
g(f) h(3)
Function Argument and Closures
Run-time stack with access links
x
4
Code for f
access
link
f
access
link
g
Code for g
access
link
h
x
7
access link set from closure
70
access
link
y
3
Function Argument and Closures
Run-time stack with access links
To execute h(3), follow
let x = 4 in
pointer to closure for h
x4
access link f
let f(y) = x*y in
(which provides code and
Code for f
letg(h)=
access link from declaration of f.)
(let x = 7 in
access
g(f) access link
h(3) + x) in g(f)
link g
Code for g
h
x
7
h(3)
access link set from closure
71
access
link
y
3
let x = 4 in
let f(y) = x*y in
let g(h) = (let x = 7
in
h(3) + x) in g(f)
x=4 is found here (global variable)
Function Argument and Closures
Run-time stack with access links
Body of f is x*y;
x
4
Code for f
access
link
f
access
link
g
Code for g
g(f)
h(3)
access link set
access
link
h
x
7
access
link
y
3
from closure
Body of f is x*y; y=3 is found here (local parameter)
72
Summary: Function Arguments
• Use closure to maintain a pointer to the static environment of a function body
• When called, set access link from closure
• All access links point “up” in stack
– May jump past activation records to find global variables – Still deallocate activation records using stack order
73
Return Function as Result
• Language Feature
– Functions that return “new” functions
– Need to maintain environment of function
• Example
fun compose(f,g) = (fn x => g(f x));
• Function “Created” Dynamically
– expression with free variables values are determined at run time
– function value is closure = áenv, codeñ
– The code pointer of this closure points to compiled code for “get function parameter x and then compute g(f(x))”.
74
Example: Return a Function with Private State
let mk_counter (init : int) = (let count = ref init in
let counter (inc : int) =
(count := !count + inc; !count)
in
counter) in
let c = mk_counter(1) in c(2) + c(2)
• The function counter is returned; the code for mk_counter builds it.
• Note that there is a parameter inc and a global variable count in the returned function.
75
Example: Return a Function with Private State
let mk_counter (init : int) = (let count = ref init in
let counter (inc : int) =
(count := !count + inc; !count)
in
counter) in
let c = mk_counter(1) in c(2) + c(2)
• Function to “make counter” returns a closure
• How is correct value of count determined in c(2) ?
76
Function Results and Closures
let mk_counter (init : int) = (let count = ref init in
let counter (inc : int) = (count := !count + inc; !count)
in counter) in
let c = mk_counter(1) in c(2) + c(2)
Code for mk_counter
Code for counter
77
Function Results and Closures
let mk_counter (init : int) = (let count = ref init in
let counter (inc : int) = (count := !count + inc; !count)
in counter) in
let c = mk_counter(1) in c(2) + c(2)
mk_c
Code for mk_counter
Code for counter
78
Function Results and Closures
let mk_counter (init : int) = (let count = ref init in
let counter (inc : int) = (count := !count + inc; !count)
in counter) in
let c = mk_counter(1) in c(2) + c(2)
mk_c
Code for mk_counter
access
c
Code for counter
79
Function Results and Closures
let mk_counter (init : int) = (let count = ref init in
let counter (inc : int) = (count := !count + inc; !count)
in counter) in
let c = mk_counter(1) in c(2) + c(2)
mk_counter(1)
1
mk_c
Code for mk_counter
access
c
access
init
1
count
counter
Code for counter
80
Function Results and Closures
let mk_counter (init : int) = (let count = ref init in
let counter (inc : int) = (count := !count + inc; !count)
in counter) in
let c = mk_counter(1) in c(2) + c(2)
mk_counter(1)
1
mk_c
Code for mk_counter
access
c
access
init
1
count
counter
Code for counter
81
Function Results and Closures
let mk_counter (init : int) = (let count = ref init in
let counter (inc : int) = (count := !count + inc; !count)
in counter) in
let c = mk_counter(1) in c(2) + c(2)
mk_counter(1)
c(2)
1
mk_c
Code for mk_counter
access
c
access
init
1
count
counter
access
inc
2
Code for counter
82
Function Results and Closures
let mk_counter (init : int) = (let count = ref init in
let counter (inc : int) = (count := !count + inc; !count)
in counter) in
let c = mk_counter(1) in c(2) + c(2)
mk_counter(1)
c(2)
Call changes cell value from 1 to 3
13
mk_c
Code for mk_counter
access
c
access
init
1
count
counter
access
inc
2
Code for counter
83
Summary of Example
• Closures are used to set the access pointer when a function returned from a nested scope is called.
• When functions are returned from nested scopes, activation record cannot be popped off the stack.
– Stack (last-in-first-out) order fails!
• Possible alternative “stack” implementation
– Forget about explicit deallocation
– Put activation records on heap
– Invoke garbage collector as needed
– May seem inefficient but not necessarily May only need to search reachable data
84
Summary of Scope Issues
• Block-structured languages use stack of activation records – Activation records contain parameters, local variables, …
– Also pointers to enclosing scope
• Several different parameter passing mechanisms
• Tail calls may be optimized
• Function parameters/results require closures
– Closure environment pointer used on function call
– Stack deallocation may fail if function returned from call – Closures not needed if functions not in nested blocks
85