Chapter 7
Runtime Environments
• Relationships between names and data objects
• As execution proceeds, the same name can denote different data
objects
• Procedures, variables, etc.
• Execution of a procedure -> activiation of the procedure
• Data objects (variables) within an activitaions
• The same procedure may have several activations alive at the same
time (e.g. recursive)
Procedure
• Definition: a declaration associates an
Idetifier with statements
– The id is a procedure name
– The body is statements
– Optional parameters
• Formal parameters (definition)
• Actual parameters (arguments)
– Local variables
– References to global scope
Activation Tree: Procedure
executions
• Each node represents an activation of procedure
• The root represents the activation of the main
program
• The node for a is the parent of the node for b, if
and only if control flows from a to b and
• The node for a is to the left of the node b if and
only if the lifetime of a occurs before the life time
of b
• (show examples in fig 7.2, 7.3)
Control Stack for Activation Tree
• Depth first traversal that starts from the
root
• We can use stack to keep track of live
procedure activations
• Can be extended to the stack storage-
allocation technique (C or Pascal)
• (show figure 7.4 and the current control
and activation life s, q(1,9), q(1,3) and
1(2,3)
The Scope of a Declaration
• Declaration a syntactic construct
associating information with a name
• Scope rules determine which declarations
of a name applies when the name
appears in the program
– Local
– None-local
– Special, static, volatile, final etc..
Name Bindings
• Data object is a storage location that can hold
values
• Name storage value
• Programming language,
– environment is a function that maps a name to a
storage location
– State is a function that maps a storage location to the
value
– L-value (name), l-value to r-value
• Binding is the dynamic counterpart of a
declaration
Name Bindings
Static Notion Dynamic Notion
Defintion of a Activation of the
procedure procedure
Declaration of a Bindings of the
name name
Scope of a decl Lifetime of a
binding
Storage organization
• Runtime Storage can be subdevided as
follows:
– The generated target code
– Data object
– Control stack (keep track of procedure
activitation)
Storage organization
Code
Static Data
Stack
data objects’ life in activations of procedure)
Heap
(other DOs,e.g dynamic mem allocation)
Activation Record
• A contiguous block of storage for
maintaining info during a procedure
activation
Returned value
Actual parameters
Optional control link
Optional access link (none-local)
Saved machine status
Local data
temporaries
Storage Allocation Strategies
• Static allocation lays out storage for all
Data objects during compile time
• Stack allocation manages the run-time
storage as a stack
• Heap allocation allocates and deallocates
stoages as needed at runtime from heap
area
• Watchout for a dangling reference
(garbage collections)
Parameter passing
• Call by value
– A formal parameter is treated just like a local
name. Its storage is in the activation record of
the called procedure
– The caller evaluates the actual parameter and
place the r-value in the storage for the formals
• Call by reference
• Copy-Restore
Parameter passing
• Call by reference
– If an actual parameter is a name or
expression having L-value, then that l-value
itself is passed
– However, if it is not (e.g. a+b or 2) that has no
l-value, then expression is evaluated in the
new location and its address is passed.
Parameter passing
• Copy-Restore: Hybird between call-by-
value and call-by-ref (copy in, copy out)
– Actual parms evaluated, its r-value is passed
and l-value of the actuals are determined
– When the called procedure is done, r-value of
the formals are copied back to the l-value of
the actuals