CS计算机代考程序代写 compiler One of Four Title Slide Options

One of Four Title Slide Options

Because learning changes everything.®

From Bits and Gates to C and Beyond

Functions

Chapter 14

© 2019 McGraw-Hill Education. All rights reserved. Authorized only for instructor use in the classroom.
No reproduction or further distribution permitted without the prior written consent of McGraw-Hill Education.

Function: Unit of Modularity

A C function is a parameterized subcomponent of a program.
• Computes a particular value, or performs a particular task.
• Invoked (called) from other functions as needed, then returns a value (and

control) to the caller.
• Same concept as the subroutine in Chapter 8.
• A function may be recursive — may call itself.
• A function has its own local variables.

A C program is a collection of functions.
• Program begins executing in the main function.
• main may call other functions, which may call others, etc. — control

eventually returns to main to end the program.

Simple Function: Performs a Task

In this example, we want the function to do something for us.
It does not need any information passed in, and it does not return any
information.

void PrintBanner();

int main(void) {
PrintBanner();
printf(“A simple C program.\n”);
PrintBanner();

}

void PrintBanner() {
printf(“========================\n”);

}

Function declaration: Tells the
compiler what the function looks like.

Function call: Transfers control
to the function and waits for return.

Function definition: The code that
executes when the function is called.

Simple Function: Computes a Value

In this example, we give the function some data and ask it to compute
something based on that data.

int Factorial(int n);

int main(void) {
int number, answer;
printf(“Enter a number: “);
scanf(“%d”, &number);
answer = Factorial(number);
printf(“%d! = %d\n”, number, answer);

}

int Factorial(int n) {
int result = 1;
for (int i=1; i <= n; i++) result = result * i; return result; } 4 Function declaration: Takes an integer input value and returns an integer. Function call: An expression. The value number is provided as input. The value returns is the expression's value. Function definition: The input value becomes a variable (n). The return statement is used to return the computed value. © McGraw-Hill Education Function Declaration The function declaration, also called a function prototype, is used to tell the compiler useful information about the function. int Factorial(int n); Return type: Can be any legal C type. If no return value, type is void. Name: Follows the same rules as variable names. Names are always global, must be unique within the program. In this book, will capitalize to easily distinguish from variable names. Parameters: Must specify the types of values that are passed as inputs. May optional specify names (but these are essentially ignored by compiler). If no input values, leave empty () or use (void). 5 return type name parameters © McGraw-Hill Education Function Call A function call is an expression. Just like any other expression, it represents a value and can be combined with other expressions, etc. The value of the expression is the value returned by the function. x = 5 + Factorial(f + g); 6 Expression is evaluated, and value is passed to the function. When function returns, its value is used as part of the larger expression. A function call can appear anywhere an expression can be used. © McGraw-Hill Education Function Definition A function definition specifies the code to be executed when the function is called. This is also called the function's implementation. int Factorial(int n) { int result = 1; for (int i=1; i <= n; i++) result = result * i; return result; } 7 Return type, name, and parameter types must match declaration. Parameter names do not have to match. Parameter is a local variable that is initialized to the value passed in. Scope = function definition. Return statement must include an expression that matches the return type of the function. If void return type, no expression specified. Definition is enclosed in braces. Declare local variables. Scope = function definition. © McGraw-Hill Education Using Functions in a Program #include

double AreaOfCircle(double radius);

int main(void){
double inner, outer;
double areaOfRing;

printf(“Inner radius: “);
scanf(“%lf”, &inner);
printf(“Outer radius: “);
scanf(“%lf”, &outer);

areaOfRing = AreaOfCircle(outer) – AreaOfCircle(inner);
printf(“Area = %f\n”, areaOfRing);

}

double AreaOfCircle(double radius) {
const double pi = 3.14159265;
return pi * radius * radius;

}

Functions must be declared before they
can be called. Generally, put all
declarations at the top of the program.

Generally define main first, and
then other functions. Reader of
program will want to start where
the program starts.

Implementing Functions

Each function needs space for its local variables and other state.
Where should it be allocated?
Option 1: Compiler allocates a memory space for each function.
• Does not allow recursion — local variables would be overwritten.
• Allocates memory for functions that may not be called.

Option 2: Program allocates space on a run-time stack.
• Allocates space as each function is called; space is deallocated when function

returns. Only uses the space that is needed.
• Allows recursion — each function invocation gets its own set of locals.
• Stack’s LIFO behavior matches the call-return action of functions.

Push/Pop Stack Frames

Implementation using LC-3 Instructions

Note: The approach of using a run-time stack is common to all processors,
not just the LC-3. While the specific instructions will be different, the concepts are
the same for different ISAs.

Three places where instructions are needed:
• Caller function — pass arguments, transfer control to callee,

use return value when control is given back
• Callee function — preamble to save state and allocate local variables
• End of callee function — return statements deallocates local variables

and restores state before returning to caller

LC-3 Activation Record

The structure of a function’s activation record is shown below.
As an example, the NoName function has two parameters (a and b) and
three local variables (w, x, and y).

int NoName(int a, int b) {
int w, x, y;
…

}

y
x
w

dynamic link
return address

return value
a
b

bookkeeping

locals

args

Name Type Offset Scope

a
b
w
x
y

int
int
int
int
int

4
5
0
-1
-2

NoName
NoName
NoName
NoName
NoName

LC-3 Activation Record

Local variables (if any) are allocated in stack order. R5 is the frame pointer, and
points to the highest address of the local variable area.
The dynamic link is the saved frame pointer
from the caller function. This allows us to
restore the caller’s state when we return.
The return address is the location of
the next instruction in the caller.
This is a saved version of R7, so
that this function can make
other function calls (JSR).
The return value will be placed above the
argument values that were pushed by the
caller.
The parameters (arguments) are pushed by
the caller before the call. The names are known
only by the callee, but the values are provided by the caller.

y
x
w

dynamic link
return address

return value
a
b

bookkeeping

locals

args

Caller Function

Consider this statement in the Watt function:
w = Volt(w, 10);

To execute the statement, we need to pass two values to the Volt
function, call the Volt function, get the return value, and store it to w.

At the time of the call, the stack frame (activation record) for Watt is
currently at the top of the run-time stack.

• R6 is the stack pointer — it points to the top address on the stack.

• R5 is the frame pointer — it points to the local variables of the current
function (Watt).

Caller Function: Push the Arguments

To pass the arguments to a function, the
caller pushes them onto the run-time
stack. It pushes the arguments in right-
to-left order.

; Volt(w, 10)
AND R0, R0, #0 ; push 10
ADD R0, R0, #10
ADD R6, R6, #-1
STR R0, R6, #0
LDR R0, R5, #0 ; push w
ADD R6, R6, #-1
STR R0, R6, #0

For this illustration, we show that w has a
value of 25.

q
r
w
dyn link
ret addr
ret val
a

25
10
25

xFD00

new R6

Caller Function: Transfer Control to the Callee

Now that the values are on the stack, we use JSR to transfer control to
the callee function (Volt). For our purposes we assume that the
subroutine has a label that matches the function name.

JSR Volt

We use JSR instead of BR or JMP so that the return address will be saved in R7.
The callee can use RET to give control back to the caller.

Caller Function: Using the Return Value

When the caller resumes, the return value is
on the top of the stack, above the locations
where the arguments were pushed.
The caller will then (a) pop the return value,
and (b) pop the arguments.
Then the return value is used as directed by
the caller (in this case, store to w).

LDR R0, R6, #0 ; pop return value
ADD R6, R6, #1
ADD R6, R6, #2 ; pop arguments
; w = Volt(…);
STR R0, R5, #0 ; store to w

ret val
q
r
w
dyn link
ret addr
ret val
a

217
25
10
217

R6
R5

Caller: Complete Code

; w = Volt(w,10);

AND R0, R0, #0 ; push 10
ADD R0, R0, #10
ADD R6, R6, #-1
STR R0, R6, #0
LDR R0, R5, #0 ; push w
ADD R6, R6, #-
STR R0, R6, #0

JSR Volt ; call function

LDR R0, R6, #0 ; pop return value
ADD R6, R6, #1
ADD R6, R6, #2 ; pop arguments
STR R0, R5, #0 ; store r.v. to w

At this point, the processor will start
executing the Volt subroutine.
But that code does not belong here.
We will show the callee code next.

When callee returns, execution
will resume here.

Callee Code: Preamble

When the callee function begins,
the arguments are on the stack,
and R5 points to the caller’s local
variables.
We need to allocate and fill in the
rest of the callee function’s activation
record. And we need to set R5 to point
to this function’s local variables.
We call this the preamble code.
It is executed at the beginning of every
function. The results are shown by
“new R5” and “new R6”.

m
k
dyn link
ret addr
ret val
q
r
w
dyn link
ret addr
ret val
a

xFCFB
x3100

25
10
25

xFD00

new R6
new R5

Callee Code: Preamble

Volt ADD R6, R6, #-1 ; push r.v.
; save return address
ADD R6, R6, #-1 ; push R7
STR R7, R6, #0
; save caller’s frame ptr
ADD R6, R6, #-1 ; push R5
STR R5, R6, #0
; set R5 to callee locals
ADD R5, R6, #-1
; push space for locals
ADD R6, R6, #-2

After generating code for the preamble, the
compiler will start generating code for the
statements in the function definition.

m
k
dyn link
ret addr
ret val
q
r
w
dyn link
ret addr
ret val
a

xFCFB
x3100

25
10
25

xFD00

new R6
new R5

Callee Code: return

To execute the return statement, the
function must:
(a) evaluate the return expression
(b) store the value to the return value
(c) pop (deallocate) local variables
(d) restore caller’s frame pointer and

return address
(e) return to the caller, with the return

value left on the top of stack

m
k
dyn link
ret addr
ret val
q
r
w
dyn link
ret addr
ret val
a

-43
217

xFCFB
x3100
217
25
10
25

xFD00

R6
R5

new R6

new R5

Callee Code: return

; return k;

LDR R0, R5, #0 ; k
STR R0, R5, #3 ; -> ret value
ADD R6, R6, #2 ; pop locals
; restore caller’s frame ptr
LDR R5, R6, #0
ADD R6, R6, #1
; restore return address
LDR R7, R6, #0
ADD R6, R6, #1
; return to caller
RET

m
k
dyn link
ret addr
ret val
q
r
w
dyn link
ret addr
ret val
a

-43
217

xFCFB
x3100
217
25
10
25

xFD00

R6
R5

new R6

new R5

Summary: Caller Code

1. Push argument values, from right to left.

; evaluate argument, assume it’s in R0
ADD R6, R6, #-1 ; push
STR R0, R6, #0
; repeat as necessary

2. Call function.

JSR function

3. Pop return value from stack, save in a register.

LDR R0, R6, #0 ; doesn’t have to be R0
ADD R6, R6, #1 ; assuming a one-word return value

4. Pop arguments from stack.

ADD R6, R6, #___ ; depends on what was pushed in part 1

Summary: Callee Code – Preamble

1. Push space for return value.

ADD R6, R6, #-1 ; assume one-word return value

2. Push return address.

ADD R6, R6, #-1
STR R7, R6, #0

3. Push dynamic link.

ADD R6, R6, #-1
STR R5, R6, #0

4. Set new dynamic link.

ADD R5, R6, #-1

5. Push space for local variables.

ADD R6, R6, #-___ ; depends on local variables

Value depends on type of return value.
If no return value, instruction is not needed.

Summary: Callee Code – Return

1. Evaluate return value and store into activation record.
; evaluate argument, assume it’s in R0
STR R0, R5, #3

2. Pop local variables.
ADD R6, R6, #___ ; depends on local variables

3. Pop/restore dynamic link.
LDR R5, R6, #0
STR R6, R6, #1

4. Pop/restore return address.
LDR R7, R6, #0
STR R6, R6, #1

5. Return to caller.
RET ; or JMP R7

Problem Solving: Using Functions

Two ways in which functions “emerge” from the top-down program design
methodology:
1. Modularity — each high-level block in a flowchart is a candidate for a

function.

• Natural division point for the program.

• Focused on one subtask and its interface with the other subtasks.
Programmer can concentrate on a subproblem.

2. Reuse — when the same task is done in multiple places.

• Programmer can write once, debug in one place, but use the code in
multiple places.

Problem 1: Convert input characters to upper-case

Problem 1: Implementation in C

char ToUpper(char input); // function declaration

int main(void) { // main function calls toUpper
char echo = ‘A’; // character typed by user
char upcase; // converted to upper-case
printf(“Type input: “);
while (echo != ‘\n’) {

scanf(“%c”, &echo);
upcase = ToUpper(echo); // function call
printf(“%c”, upcase);

}
}

// function implementation
char ToUpper(char inchar) {

char outchar; // will convert and return output character
if (‘a’ <= inchar && inchar <= 'z') outchar = inchar - ('a' - 'A'); else outchar = inchar; return outchar; } 28 © McGraw-Hill Education Problem 2: Pythagorean Triples Compute all values of a, b, and c, such that 𝑎𝑎2 + 𝑏𝑏2 = 𝑐𝑐2 and c is no larger than a value provided by the user. Have to compute the square of an integer three times in the same expression. if (a*a + b*b == c*c) ... Instead of writing a*a, b*b, and c*c, abstract the operation into a function Squared(x). if (Squared(a) + Squared(b) == Squared(c)) ... The code better matches the abstraction level of the problem. 29 Because learning changes everything.® www.mheducation.com © 2019 McGraw-Hill Education. All rights reserved. Authorized only for instructor use in the classroom. No reproduction or further distribution permitted without the prior written consent of McGraw-Hill Education. From Bits and Gates to C and Beyond Function: Unit of Modularity Simple Function: Performs a Task Simple Function: Computes a Value Function Declaration Function Call Function Definition Using Functions in a Program Implementing Functions Push/Pop Stack Frames Implementation using LC-3 Instructions LC-3 Activation Record LC-3 Activation Record Caller Function Caller Function: Push the Arguments Caller Function: Transfer Control to the Callee Caller Function: Using the Return Value Caller: Complete Code Callee Code: Preamble Callee Code: Preamble Callee Code: return Callee Code: return Summary: Caller Code Summary: Callee Code - Preamble Summary: Callee Code - Return Problem Solving: Using Functions Problem 1: Convert input characters to upper-case Problem 1: Implementation in C Problem 2: Pythagorean Triples End of Main Content

Related Posts