程序代写代做代考 data structure c++ compiler chain ocaml C go Scope, Functions and Storage Management

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
– Exit 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

{ 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
18

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.
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 () begin
end;
function f() {

};
• 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
…
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
…
control link
f(3)
access link
y3
For f(3), the two links
are the same because f is called right after it is defined
x4
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 is always set to frame of closest enclosing lexical block
f(3)
access link
y3 x4
g(12) control link access link z 12
The compiler can figure this out
– For function body, this is block from program text
that contains function
declaration
(g called from inside f)
50

Another Example
x
3
let x = 3 in let w = 1 in
w
1
let f y = w+x+y in let x = 4 in
let g z = f (x*z) in let x = 5 in
let w = g x in
w Access links are red.
Control links are black.
f
…
x
4
g
…
x
5
w
51

Another Example
x
3
let x = 3 in let w = 1 in
w
1
let f y = w+x+y in let x = 4 in
let g z = f (x*z) in let x = 5 in
let w = g x in
w Access links are red.
Control link
f
…
x
4
g
…
x
5
s are black.
Follow access link to find the value of x for function call (g x). Value is 5.
w
52

Another Example
x
3
let x = 3 in let w = 1 in
let f y = w+x+y in let x = 4 in
let g z = f (x*z) in let x = 5 in
let w = g x in
w Access links are red.
Control links are black.
Return-result addr links are green.
Note that access and control links point to a block and return-result links point to a single location in a block.
(g 5)
w
1
f
…
x
4
g
…
x
5
w
return-result addr
z
5
x*z
20
f (x*z)
24
53

Another Example
x
3
let x = 3 in let w = 1 in
let f y = w+x+y in let x = 4 in
let g z = f (x*z) in let x = 5 in
let w = g x in
w
1
f
…
x
4
g
…
x
5
w Access links are red.
w
return-result addr
z5 x*z 20 f (x*z) 24
Follow access link
Control links are black.
to find the value of x used in
Return-result addr links are
(g 5)
green.
expression x*z. Value is 4, and
Note that access and control
thus x*z is 20.
links point to a block and return-result links point to a single location in a block.
54

Another Example
x
3
let x = 3 in let w = 1 in
let f y = w+x+y in let x = 4 in
let g z = f (x*z) in let x = 5 in
let w = g x in
w Access links are red.
Control links are black.
Return-result addr links are green.
Note that access and control links point to a block and return-result links point to a single location in a block.
(g 5)
(f 20)
55
w
1
f
…
x
4
g
…
x
5
w
return-result addr
z
5
x*z
20
f (x*z)
24
return-result addr
y
20

Another Example
x
3
let x = 3 in let w = 1 in
let f y = w+x+y in let x = 4 in
let g z = f (x*z) in let x = 5 in
let w = g x in
w
1
f
…
x
4
g
…
w Access links are red.
w
return-result addr
z5 x*z 20 f (x*z) 24
green.
expression w+x+y. Must follow 3 links
Follow access links
Control links are black.
to find the values of w and x used in
Return-result addr links are
(g 5)
(f 20)
Note that access and control
to get to x.
links point to a block and return-result links point to a single location in a block.
56
x
return-result addr
5
y
20

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.
letgx=ifx>0thenfx else(fx)*2
57

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
58

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
59

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
60

(f 1 3)
Tail Recursion Elimination
(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
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
61

(f 1 3)
(f 2 3)
(f 4 3)
Tail Recursion and Iteration
Control link
Return-result addr
x
1
y
3
f(2*x) y
4
Control link
Return-result addr
x
2
y
3
f(2*x) y
4
Control link
Return-result addr
x
4
y
3
f(2*x) y
letrecfxy = 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; };
62
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
63

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
66

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
67

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
68

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).
69

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
70

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
71

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
72

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
74

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
75

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
76
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
77
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)
78

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
79

Return Function as Result
• Language Feature
– Functions that return “new” functions
– Need to maintain environment of function
• Example
letcomposefg =(funx->g(fx))
• Function “Created” Dynamically
– expression with free variables values are determined at run time
– function value is closure = áenv, codeñ
– The code pointer of this closure points to compiled code for “get function parameter x and then compute g(f(x))”.
80

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.
81

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) ?
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_c
Code for mk_counter
access
c
Code for counter
85

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
90

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
91

Related Posts