Chapter 10

Implementing
Subprograms

Copyright © 2023 Pearson Education Ltd. All Rights Reserved.

Chapter 10 Topics

• The General Semantics of Calls and Returns

• Implementing “Simple” Subprograms
• Implementing Subprograms with Stack-Dynamic
Local Variables
– Local variables whose storage is allocated when a
subprogram is called and deallocated when the
subprogram returns
• Nested Subprograms

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-2

How it works

• On subprogram call:
– A stack frame (activation record) is pushed
onto the stack
– Frame holds local variables, return address,
parameters, and bookkeeping info
• During execution:
– Local variables are created and used as
needed
• On subprogram return:
– Stack frame is popped
– Local variables are automatically destroyed

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-3

The General Semantics of Calls and
Returns
• The subprogram call and return operations
of a language are together called its
subprogram linkage
• General semantics of calls to a subprogram
– Parameter passing methods
– Stack-dynamic allocation of local variables
– Save the execution status of calling program
– Transfer of control and arrange for the return
– If subprogram nesting is supported, access to
nonlocal variables must be arranged

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-4

Subroutine linkages

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-5

The General Semantics of Calls and
Returns

• General semantics of subprogram returns:

– In mode and inout mode parameters

must have their values returned
– Deallocation of stack-dynamic locals
– Restore the execution status
– Return control to the caller

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-6

Implementing “Simple” Subprograms

• Call Semantics:

- Save the execution status of the caller

- Pass the parameters
- Pass the return address to the called
- Transfer control to the called

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-7

Implementing “Simple” Subprograms
(continued)
• 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
– If it is a function, move the functional value to a
place the caller can get it
– Restore the execution status of the caller
– Transfer control back to the caller

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-8

Implementing “Simple” Subprograms
(continued)

• Required storage:
1. Status information about the call
– Holds information needed to manage the
subprogram call, such as bookkeeping data,
dynamic links, and control/status flags.

– Ensures that when the subprogram ends, the

program can return to the correct place and
restore the previous environment.

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-9

Implementing “Simple” Subprograms
(continued)

• Required storage:
– parameters,
• The values or references passed to the subprogram
by the caller.
• These are stored in the stack frame so the
subprogram can access its inputs.
– return address,
• The exact location in the caller’s code where
execution should resume after the subprogram
finishes.
• Stored so the program can correctly “go back” after
the subprogram call.

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-10

Implementing “Simple” Subprograms
(continued)

• Required storage:
– return value for functions
• If the subprogram is a function (returns a value),
space is reserved for storing its result, which is then
accessed by the caller after return.
– temporaries ( local variable)
• Temporary storage for variables declared within the
subprogram.

• Each call gets its own separate set, supporting

recursion and independent execution.

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-11

Implementing “Simple” Subprograms
(continued)

• Two separate parts: the actual code and the non-

code part (local variables and data that can
change- listed previous)
• The format, or layout, of the non-code part of an
executing subprogram is called an activation
record
• An activation record instance is a concrete
example of an activation record (the collection of
data for a particular subprogram activation)
• The activation record instance is the actual,
physical block of memory created on the stack for
a particular call

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-12

An Activation Record for “Simple”
Subprograms

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-13

Code and Activation Records of a
Program with “Simple” Subprograms

Main with three

subprogram A,B and
C
May be compiler at
different days
Linker( OS)
assembles them
together

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-14

Implementing Subprograms with
Stack-Dynamic Local Variables
• More complex activation record
– The compiler must generate code to cause
implicit allocation and deallocation of local
variables
– Recursion must be supported (adds the
possibility of multiple simultaneous activations
of a subprogram)

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-15

Typical Activation Record for a Language
with Stack-Dynamic Local Variables

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-16

Implementing Subprograms with Stack-
Dynamic Local Variables: Activation Record

• The activation record format is static, but its size

may be dynamic
• The dynamic link points to the top of an instance
of the activation record of the caller
• An activation record instance is dynamically
created when a subprogram is called

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-17

Implementing Subprograms with Stack-
Dynamic Local Variables: Activation Record

• The Environment Pointer (EP) must be maintained

by the run-time system. It always points at the
base of the activation record instance of the
currently executing program unit

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-18

An Example: C Function

void sub(float total, int part)

{
int list[5];
float sum;
…
}

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-19

Revised Semantic Call/Return Actions

• Caller Actions:
– Create an activation record instance
– Save the execution status of the current program unit
– Compute and pass the parameters
– Pass the return address to the called
– Transfer control to the called
• Prologue actions of the called:
– Save the old EP in the stack as the dynamic link and create
the new value
– Allocate local variables

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-20

Revised Semantic Call/Return Actions
(continued)

• Epilogue actions of the called:

– If there are pass-by-value-result or out-mode
parameters, the current values of those parameters are
moved to the corresponding actual parameters
– If the subprogram is a function, its value is moved to a
place accessible to the caller
– Restore the stack pointer by setting it to the value of the
current EP-1 and set the EP to the old dynamic link
– Restore the execution status of the caller
– Transfer control back to the caller

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-21

An Example Without Recursion

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

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-22

An Example Without Recursion

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-23

 Dynamic Chain and Local Offset
• The collection of dynamic links in the stack at a
given time is called the dynamic chain, or call
chain
• Local variables can be accessed by their offset
from the beginning of the activation record, whose
address is in the EP. This offset is called the
local_offset
• The local_offset of a local variable can be
determined by the compiler at compile time

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-24

Local off-set

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-25

An Example With Recursion

• The activation record used in the

previous example supports recursion
int factorial (int n) {
<-----------------------------1
if (n <= 1) return 1;
else return (n * factorial(n - 1));
<-----------------------------2
}
void main() {
int value;
value = factorial(3);
<-----------------------------3
}

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-26

Activation Record for factorial

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-27

Stacks for calls to factorial

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-28

Stacks for returns from factorial

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-29

Nested Subprograms
• Some non-C-based static-scoped languages
(e.g., Fortran 95+, Ada, Python, JavaScript, Ruby,
and Swift) use stack-dynamic local variables and
allow subprograms to be nested
• All variables that can be non-locally accessed
reside in some activation record instance in the
stack
• The process of locating a non-local reference:
1. Find the correct activation record instance
2. Determine the correct offset within that activation record
instance

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-30

Nested Subprograms

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-31

Locating a Non-local Reference

• Finding the offset is easy

• Finding the correct activation record
instance
– Static semantic rules guarantee that all non-
local variables that can be referenced have been
allocated in some activation record instance that
is on the stack when the reference is made

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-32

Static Scoping
• A static chain is a chain of static links that
connects certain activation record instances

• The static link in an activation record instance for

subprogram A points to one of the activation
record instances of A's static parent

• The static chain from an activation record instance

connects it to all of its static ancestors

• Static_depth is an integer associated with a static

scope whose value is the depth of nesting of that
scope

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-33

Static Scoping

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-34

Static Scoping (continued)

• The chain_offset or nesting_depth of a nonlocal

reference is the difference between the
static_depth of the reference and that of the scope
when it is declared

Chain offset= Static depth – declared scope

• A reference to a variable can be represented by the

pair:
(chain_offset, local_offset),
where local_offset is the offset in the activation
record of the variable being referenced

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-35

Static Scoping

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-36

Stack Contents at
Position 1

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-37

Stack Conte
nts at Position 1

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-38

Example PASCAL Program (continued)

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-39

Static Chain Maintenance

• At the call,
- The activation record instance must be built
- The dynamic link is just the old stack top pointer
- The static link must point to the most recent ari
of the static parent
- Two methods:
1. Search the dynamic chain
2. Treat subprogram calls and
definitions like variable references
and definitions

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-40

Evaluation of Static Chains

• Problems:
1. A nonlocal areference is slow if the
nesting depth is large
2. Time-critical code is difficult:
a. Costs of nonlocal references are
difficult to determine
b. Code changes can change the
nesting depth, and therefore the cost

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-41

Summary

• Subprogram linkage semantics requires

many action by the implementation
• Simple subprograms have relatively basic
actions
• Stack-dynamic languages are more
complex
• Subprograms with stack-dynamic local
variables and nested subprograms have two
components
– actual code
– activation record

Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-42

Summary (continued)

• Activation record instances contain formal

parameters and local variables among other
things
• Static chains are the primary method of
implementing accesses to non-local
variables in static-scoped languages with
nested subprograms
• Access to non-local variables in dynamic-
scoped languages can be implemented by
use of the dynamic chain or thru some
central variable table method
Copyright © 2023 Pearson Education Ltd. All Rights Reserved. 1-43