LECTURE 10
IMPLEMENTING
SUBPROGRAMS
CSE 325/CSE 425:
CONCEPTS OF
PROGRAMMING LANGUAGE
INSTRUCTOR: DR. F. A. FAISAL
CONTENT
• The General Semantics of Calls and
Returns
• Implementing “Simple” Subprograms
• Implementing Subprograms with Stack-
dynamic local variables
• Nested Subprograms
• Blocks
• Implementing Dynamic Scoping
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
THE GENERAL SEMANTICS
OF CALLS AND RETURNS
• General semantics of subprogram returns:
• Out mode and inout (if pass by value-result)
mode Parameters must have their values
returned
• Deallocation of stack-dynamic locals
• Restore the execution status
• Return control to the caller
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
(CONT.)
• 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, mode the functional value to a place
the caller can get it
• Restore the execution status of the caller
• Transfer control back to the caller
• Required storage:
• Status information, parameters, return address, return
value for functions, temporaries
(CONT.)
• Two separate parts: the actual code and the non-
code part (local variables and data that can
change)
• 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)
AN ACTIVATION RECORD FOR
“SIMPLE” SUBPROGRAMS
CODE AND ACTIVATION RECORDS
OF A PROGRAM WITH “SIMPLE ”
SUBPROGRAMS
• This activation record
consists of main, (A, B, C)
subprograms and suppose
the subprograms (if stored
in different file) then
compiled together by
linker.
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)
TYPICAL ACTIVATION RECORD
FOR A LANGUAGE WITH STACK-
DYNAMIC LOCAL VARIABLES
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
• Activation record instances reside on the run-time stack
• 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 execution
program unit.
EXAMPLE
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
(CONT.)
• Epilogue actions of the called:
• If there are passed-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
AN EXAMPLE WITHOUT RECURSION
AN EXAMPLE WITHOUT RECURSION
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 compiler at compile time.
AN EXAMPLE WITH
RECURSION
Activation record for factorial
STACKS FOR CALLS TO FACTORIAL
STACKS FOR
RETURNS FROM
FACTORIAL
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.
THANKS
