程序代写代做代考 interpreter C chain CS 320 : Functions

CS 320 : Functions
Marco Gaboardi MSC 116 gaboardi@bu.edu

Announcements
• Interpreterpart3dueSunday
(last programming assignment)
• LastTheoryAssignmentduethe10th (deadline extension)

Parsing and semantic analysis
static
dynamic
© 2015 Elsevier, Inc. All rights reserved.

Today plan
• MoreonFunctions

Functions

header
let rec subprog(x:int)= let n=5 in
…
formal parameter definition
callee/called caller
Terminology
…
let z=5.6 in … subprog(z) …
function call
actual parameter
local symbol/variable
1-6

Language for basic stack manipulations with local variables definitions and functions
…
::= push | add | sub | mul | div
| neg | rem | swap | let | end | bind
| fun | funEnd |return |call

Language for basic stack manipulations with local variables definitions and functions
Name of the function
fun
Formal parameter
Keyword to mark where a function declaration begins.

Language for basic stack manipulations with local variables definitions and functions
funEnd
Keyword to mark where a function declaration ends.

Language for basic stack manipulations with local variables definitions and functions
return
Keyword to mark when a function needs to return a value.

Language for basic stack manipulations with local variables definitions and functions
call
Keyword to mark when a function needs to be called.

When a return expression is evaluated, the function stops execution. When c
e y
p o
restore the environment to the environment that existed prior to the fun d
e pr
function completed by execution the last expression in the function’s co
be restored to what the stack was at the point of the call. Additionally
stack frame the function pushed onto the restored stack (the stack at th
Language for basic stack manipulations
Please note that background color and indentation is used only to im
would consist of code within colored background.
with local variables definitions and functions
6.1.1 Example 1
input
fun identity x push x
return funEnd
push identity push 1
call
quit
Actual parameter
1 ! return value of calling identity and passing in x as an argument :unit: ! result of declaring identity
!
stack 1
:unit:
6.1.2 Example 2

What are the design considerations for functions?
We need to think about:
• parameter passing
• parameters returning
• variables: local vs global
• scope of variables
• nesting of subprograms
• referencing environment

Parameter Passing
Parameter passing methods are ways in which parameters are transmitted to and from sub programs.
• Semantic Models of Parameter Passing
• Implementation Models for these semantic models

Semantic Modes of Parameter Passing
1-15

How to transfer a value •We have different ways to provide
access to a value to a subprogram
• Physically move a value
• An access path is transmitted (e.g.
pointer or reference)
•These are orthogonal to the mode of the parameters
1-16

TopHat Q15-Q18

Implementation Models
Techniques used for parameter passing :
• Call by Value (In mode)
• Call by Result (Out mode)
• Call by Value-Result (In-out mode)
• Call by Reference (In-out mode)

Pass-by-Value (In Mode)
• The value of the actual parameter is used to initialized the corresponding formal parameter
• Normally implemented by copying
• Can be implemented by transmitting an access path but then one need to enforce write protection.
1-19

Pass-by-Result (Out Mode)
• When a parameter is passed by result, no value is transmitted to the subprogram;
-the corresponding formal parameter acts as a local variable;
-its value is transmitted to caller’s actual parameter when control is returned to the caller, by physical move
1-20

Pass-by-Value-Result (inout Mode)
• A combination of pass-by-value and
pass-by-result
• Actual values are copied in both directions.
• Formal parameters have local storage 1-21

Pass-by-Reference (Inout Mode)
• Pass an access path to the value
• Passing process is efficient (no copying and no duplicated storage)
• Slower accesses (compared to pass-by-value) to formal parameters
• Potentials for unwanted side effects (collisions)
• Unwanted aliases (access broadened)
1-22

Pass-by-Name (Inout Mode)
• By textual substitution
• Formal parameters are bound to an access method at the time of the call, but actual binding to a value or address takes place at the time of a reference or assignment
1-23

Implementing Parameter-Passing Methods
• In most languages parameter communication takes place
through the run-time stack (more in the future)
• Pass-by-value parameters have their values copied into
stack locations.
• Pass-by-reference are the simplest to implement; only an
address is placed in the stack
• In Pass-by-result the caller reads from the stack the final value of the parameter before the stack of the callee is disposed
1-24

Implementing Parameter-Passing Methods
Function header: void sub(int a, int b, int c, int d) Function call: sub(w, x, y, z)
(pass w by value, x by result, y by value-result, z by reference)
1-25

Simple Functions
Let assume that “simple” subprograms cannot be nested and that have only static local variables.
How a subprogram is executed? How can we implement the call-return procedure?
function sub1(…){ …
};
function sub2(…){ …
Sub1(…)
};
function sub3(…){ …
Sub2(…)
};

Function call
Call Semantics:
• Save the execution status of the caller
• In mode and inout mode parameters must be provided
• Pass the return address to the called subprogram
• Transfer control to the called subprogram

Function return
Return Semantics:
• If pass-by-value-result or out mode parameters are used, move the current values of those parameters to their corresponding actual parameters
• Restore the execution status of the caller • Transfer control back to the caller

Activation Records for Simple Functions
•We need to store some information to guarantee the correct execution of the subprogram. This constitutes the activation record of the subprogram.
Local Variables
Parameters
Return Address

Information we need to store
• An activation record instance is a concrete example of an activation record (the collection of data for a particular subprogram activation)
• The activation record contains the non-code information that we need for the execution of the program.

Implementing Simple Functions: Activation Record
• The activation record format is static
• An activation record instance is dynamically created
when a subprogram is called
• An activation record instance is dynamically deallocated when a subprogram returns
• Activation record instances reside on the run-time stack
For each activation record instance we need to maintain an Environment Pointer (EP) pointing at the base of the instance and used to deallocating it.

Example: Activation Records stack for Simple Functions
function sub1(…){ …
};
function sub2(…){ …
Sub1(…)
};
function sub3(…){ …
Sub2(…)
};

Example: Activation Records stack for Simple Functions
function sub1(…){ …
};
function sub2(…){ …
Sub1(…)
};
function sub3(…){ …
Sub2(…)
};
call to sub3()

Example: Activation Records stack for Simple Functions
function sub1(…){ …
};
function sub2(…){ …
Sub1(…)
};
function sub3(…){ …
Sub2(…)
};
Local Variables
Parameters
Return Address
Sub3
call to sub3()

Example: Activation Records stack for Simple Functions
Sub1
Sub2
Sub3
function sub1(…){ …
};
function sub2(…){ …
Sub1(…)
};
function sub3(…){ …
Sub2(…)
};
Local Variables
Parameters
Return Address
Local Variables
Parameters
Return Address
Local Variables
Parameters
Return Address
call to sub3()

Example: Activation Records stack for Simple Functions
function sub1(…){ …
};
function sub2(…){ …
Sub1(…)
};
function sub3(…){ …
Sub2(…)
};
call to sub3()

TopHat Q6-Q10

Local variables
•Variables whose scope is usually the body of the subprogram in which they are defined
•They can be static or stack-dynamic
•A subprogram can use variables that are heap-dynamic but these usually do not count as local.
1-54

Local variables
let plus2 = fun x->
let y = 2 in x + y
Here y is a local variable to the function plus2

Local variables?
What is the value of y here?
let y = 2 in
let plus2 = fun x-> x + y in plus2 (plus2 4)
How about y here? Is it local?
And here?

push identity
:unit: ! result of third binding
push x
call quit
1 ! return value of calling identity and passing in x as an argument :unit: ! result of binding x
:unit: ! result of declaring identity
Local variables?
6.1.4 Example 4
input
push x push 3 bind
fun addX arg push x
push arg
add
return funEnd
push x push 5 bind
push a push 3 bind
push addX push a
call quit
!
stack 6
:unit: :unit: :unit: :unit:
What is the value of x here?
6 ! result of function call

Subprograms with stack-dynamic variables

Implementing Subprograms with Stack-Dynamic Local Variables: Activation Record
• The activation record format is static, but its size may be dynamic to deal with stack-dynamic variables.
• We need a dynamic link pointing to the base of the instance of the activation record of the caller – this will help us deallocate the activation record instance when it has dynamic size.
• The collection of dynamic links in the stack at a given time is called the dynamic chain, or call chain

Function Calls for General Programs • General semantics of calls to a subprogram
• In mode and inout mode parameters must be provided
• Stack-dynamic allocation of local variables
• Save the execution status of the calling program
• Transfer of control to the subprogram and arrange for the return
• If subprogram nesting is supported, access to nonlocal variables must be arranged through a static link (we will see this next time).

Function Returns for General Programs • General semantics of subprogram returns:
• Out mode and inout mode parameters must have their values returned
• Deallocation of stack-dynamic local variables
• Restore the execution status
• Return control to the caller
1-61

Typical Activation Record for a Language with Stack-Dynamic Local Variables
Local Variables
Parameters
Dynamic Link
Return Address

Example in C
void sub(float total, int part) {
int list[5]; float sum;
…
sum
list[4]
list[3]
list[2]
list[1]
list[0] part
total
Local Variable
Local Variable
Local Variable
Local Variable
Local Variable
Local Variable
Parameter
Parameter
Dynamic Link
Return Address
}
1-63

Example
void fun1(float r)
{
int s, t;
…
fun2(s); } …
void fun2(int x) { int y;
…
fun3(y); } …
void fun3(int q) { } …
void main() { float p;
…
fun1(p);
…
}
p

Example
void fun1(float r)
{
int s, t;
…
fun2(s); } …
void fun2(int x) { int y;
…
fun3(y); } …
void fun3(int q) { } …
void main() { float p;
…
fun1(p);
…
}
main
Local Variable p

Example
void fun1(float r)
{
int s, t;
…
fun2(s); } …
void fun2(int x) { int y;
…
fun3(y); } …
void fun3(int q) { } …
void main() { float p;
…
fun1(p);
… }
main
Local Variable p

Example
void fun1(float r)
{
int s, t;
…
fun2(s); } …
void fun2(int x) { int y;
…
fun3(y); } …
void fun3(int q) { } …
void main() { float p;
…
fun1(p);
…
}
Local Variable
Local Variable
Parameter
Dynamic Link
Return to main
Local Variable
fun1
t s r
main p

Example
void fun1(float r)
{
int s, t;
…
fun2(s);
} …
void fun2(int x) { int y;
…
fun3(y); } …
void fun3(int q) { } …
void main() { float p;
…
fun1(p);
…
}
Local Variable
Local Variable
Parameter
Dynamic Link
Return to main
Local Variable
fun1
t s r
main p

Example
void fun1(float r)
{
int s, t;
…
fun2(s); } …
void fun2(int x) { int y;
…
fun3(y); } …
void fun3(int q) { } …
void main() { float p;
…
fun1(p);
…
}
Local Variable
Parameter
Dynamic Link
Return to fun1
Local Variable
Local Variable
Parameter
Dynamic Link
Return to main
Local Variable
fun2
y x
t s r
fun1
main p

Example
void fun1(float r)
{
int s, t;
…
fun2(s); } …
void fun2(int x) { int y;
…
fun3(y);
} …
void fun3(int q) { } …
void main() { float p;
…
fun1(p);
…
}
Local Variable
Parameter
Dynamic Link
Return to fun1
Local Variable
Local Variable
Parameter
Dynamic Link
Return to main
Local Variable
fun2
y x
t s r
fun1
main p

Example
q
y x
t s r
Parameter
Dynamic Link
Return to fun2
Local Variable
Parameter
Dynamic Link
Return to fun1
Local Variable
Local Variable
Parameter
Dynamic Link
Return to main
Local Variable
void fun1(float r)
{
int s, t;
…
fun2(s); } …
void fun2(int x) { int y;
…
fun3(y); } …
void fun3(int q) {
} …
void main() { float p;
…
fun1(p);
…
}
fun3
fun2
fun1
main p

Example
void fun1(float r)
{
int s, t;
…
fun2(s); } …
void fun2(int x) { int y;
…
fun3(y);
} …
void fun3(int q) { } …
void main() { float p;
…
fun1(p);
…
}
Local Variable
Parameter
Dynamic Link
Return to fun1
Local Variable
Local Variable
Parameter
Dynamic Link
Return to main
Local Variable
fun2
y x
t s r
fun1
main p

Example
void fun1(float r)
{
int s, t;
…
fun2(s);
} …
void fun2(int x) { int y;
…
fun3(y); } …
void fun3(int q) { } …
void main() { float p;
…
fun1(p);
…
}
Local Variable
Local Variable
Parameter
Dynamic Link
Return to main
Local Variable
fun1
t s r
main p

Example
void fun1(float r)
{
int s, t;
…
fun2(s); } …
void fun2(int x) { int y;
…
fun3(y); } …
void fun3(int q) { } …
void main() { float p;
…
fun1(p);
… }
main
Local Variable p

TopHat Q11-Q12

Passing functions as arguments

Local variables when passing a function?
What is the value of y here?
let y = 2 in
let plus2 = fun x-> x + y in plus2 (plus2 4)
How about y here? Is it local?
And here?

Closures
• A closure is a pair consisting of the function code p and its
referencing environment m: (p,m)
• It is similar to a configuration but where p is the code of a function.
• The referencing environment is needed to provide values to the variables when the function (subprogram) can be called from an arbitrary place in the program
• Closures are needed if a (function (subprogram) can access variables in nesting scopes and it can be called from anywhere
• A static-scope language that does not permit nested subprograms doesn’t need closures

Example of closure
let y = 2 in
let plus2 = fun x-> x + y in plus2 (plus2 4)
What is the closure that will be created here?
(fun x-> x + y / y=2)

bind
:unit: ! result of function declaration
push identity
push x
call
quit
1 ! return value of calling identity and passing in x as an argument
:unit: ! result of binding x
:unit: ! result of declaring identity
Local variables?
6.1.4 Example 4
input
push x push 3 bind
fun addX arg push x
push arg
add
return funEnd
push x push 5 bind
push a push 3 bind
push addX push a
call quit
6 ! result of function call :unit: ! result of third binding
stack
(fun arg -> push x; push 6
:unit: :unit:
! a:urngit:; add; return / x=3) :unit:
What is the closure that will be created here?
:unit: ! result of second binding

Closures vs Scope
let y = 2 in
let plus2 = fun x-> x + y in plus2 (plus2 4)
We said that we need a closure to find the value of y.
(fun x-> x + y in plus2 (plus2 4) / y=2)
What are we assuming here about the scope of y?

Tips for interpreter part 3:Language for basic stack manipulations with local variables definitions and functions
• Since in our interpreter we want to pass functions as arguments to other functions, when you encounter a function declaration you should construct a closure:
1) the name of the function
2) the name of the formal parameter 3) the code in the function body
4) the current environment
(Notice that 3 and 4 constitute the function code.)
type value = …
|CLOSURE of(name * name *(command list) * (name*value)list)

Tips for interpreter part 3:Language for basic stack manipulations with local variables definitions and functions
How do we call a function?
1. Check if fun_name is bound to a closure.
2. Checkifargisavalueoranameboundtoa
value (including closures for functions).
3. If both yes, then we can execute the body of the function – otherwise error.
4. We have to execute it in the environment we have in the closure with an additional binding between the formal parameter and the value of the actual (arg).
5. We also need to execute it using a new stack
push fun_name push arg
call

Tips for interpreter part 3:Language for basic stack manipulations with local variables definitions and functions
Preparing for function evaluation (step 4)
We have to execute the code in the environment we have in the closure with an additional binding between the formal parameter and the value of the actual (arg).
push fun_name push arg
call
We have to use the environment in the closure.

Tips for interpreter part 3:Language for basic stack manipulations with local variables definitions and functions
What to do when the function terminates?
1. Restoretheprevious environment
2. Restorethepreviousstack
3. Pushontherestoredstackthe last element on the function stack
4. Resumetheexecutionfrom after the call instruction
…
… funEnd

Tips for interpreter part 3:Language for basic stack manipulations with local variables definitions and functions
What to do when the function terminates with a return?
1. Immediatelystoptheexecution
2. Restorethepreviousenvironment
3. Restorethepreviousstack
4. Pushontherestoredstackthe last element on the function stack
5. Resumetheexecutionfromafter the call instruction
…
… return

Related Posts