Programming Languages
2nd edition
Tucker and Noonan
Chapter 9
It is better to have 100 functions operate on one data
structure than 10 functions on 10 data
A. Perlis
Basic Terminology
Function Call and Return
Parameter Passing Mechanisms
Activation Records
Recursive Functions
Run Time Stack
9.1 Basic Terminology
• Value-returning functions:
– known as “non-void functions/methods” in
– called from within an expression; e.g.,
x = (b*b - sqrt(4*a*c))/2*a
• Non-value-returning functions:
– known as “procedures” in Ada, “subroutines” in
Fortran, “void functions/methods” in C/C++/Java
– called from a separate statement; e.g.,
strcpy(s1, s2);
9.2 Function Call and Return
Fig 9.1 :
Example C/C++
int h, i;
void B(int w) {
int j, k;
i = 2*w;
w = w+1;
void A(int x, int y) {
bool i, j;
int main() {
int a, b;
h = 5; a = 3; b = 2;
A(a, b);
9.3 Parameters
• Definitions
– An argument is an expression that appears in
a function call.
– A parameter is an identifier that appears in a
function declaration.
• E.g., in Figure 9.1
– The call A(a, b) has arguments a and b.
– The function declaration A has parameters x
and y.
Parameter-Argument Matching
• Usually by number and by position.
– i.e., any call to A must have two arguments, and they
must match the corresponding parameters’ types.
• Exceptions:
– Python: parameters aren’t typed
– Perl - parameters aren’t declared in a function
header. Instead, parameters are stored in an array
@_, and are accessed using an array index.
– Ada - arguments and parameters can be linked by
name; e.g., the call A(y=>b, x=>a) is the same as
9.4 Parameter Passing
By value
By reference
By value-result
By result
By name
Pass by Value
• Compute the value of the argument at the
time of the call and assign that value to the
• e.g., in the call A(a, b) in Fig. 9.1, a and b
are passed by value. So the values of
parameters x and y become 3 and 2,
respectively when the call begins.
Pass by Value
• Pass by value doesn’t allow the called
function to modify an argument’s value in
the caller’s environment.
• Technically, all arguments in C and Java
are passed by value.
• But references can be passed to allow
argument values to be modified.
Simulating Pass by Reference in
Compute the
address of the
argument at the
time of the call
and assign it to
the parameter.
int h, i;
void B(int* w) {
int j, k;
i = 2*(*w);
*w = *w+1;
void A(int* x, int* y) {
bool i, j;
int main() {
int a, b;
h = 5; a = 3; b = 2;
A(&a, &b);
Pass By Reference
• Pass by reference means the memory
address of the argument is copied to the
corresponding parameter so the
parameter is an indirect reference (a
pointer) to the actual argument.
• Assignments to the parameter affect the
value of the argument directly, rather
than a copy of the value. This is an
example of a side effect.
Pass By Reference
• In languages like C++ that support both
value and reference parameters, there
must be a way to indicate which is which.
– In C++, this is done by preceding the
parameter name in the function definition
with an ampersand (&) if the parameter is a
reference parameter. Otherwise, it is a
value parameter.
Pass by Value-Result and Result
• Pass by value-result: Pass by value at the
time of the call and copy the result back to
the argument at the end of the call.
– E.g., Ada’s in out parameter can be
implemented as value-result.
– Value-result is often called copy-in-copy-out.
• Pass by result: Copy the final value of the
parameter out to the argument at the end
of the function call.
• Reference and value-result are the
same, except when aliasing occurs.
• Aliasing:refer to the same variable by two
names; e.g.,
– the same variable is both passed and
globally referenced from the called function,
– the same variable is passed to two different
parameters using a parameter method other
than pass by value.
– Having two pointers to the same location
Example of Effect
void f (int& x, int&y)
x = x + 1;
y = y + 1;
f(a,b) versus f(a,a)
Procedure f (x, y: in out
Integer) is
x = x + 1;
y = y + 1;
end f;
f(a,b) versus f(a,a)
Pass by Name
• Textually substitute the argument for every
instance of its corresponding parameter in
the function body.
– Originated with Algol 60, but was dropped by
Algol’s successors -- Pascal, Ada, Modula.
– Exemplifies late binding, since evaluation of
the argument is delayed until its occurrence in
the function body is actually executed.
– Associated with lazy evaluation in functional
languages (see, e.g., Haskell discussion in
Chapter 14).
Example from Algol
procedure swap(a, b);
integer a, b; // declare parameter types
begin integer t; // declare local variable
t = a;
// t = i (3)
a = b;
// i = a[i] (1)
b = t; // a[i] = i (1)
Consider the call swap(i, a[i])
where i = 3 and a =
result: a[1] = 1; i = 1
9 4 -1 1 14
Side Effects
• Some methods of parameter passing cause
side effects, in this case meaning a change
to the non-local environment.
– Call by value is “safe” – there are no side
– Pass by reference can cause side effects.
• Side effects may compromise readability
and reliability.
– Example: p = (y*x) + f(x, y)*z;
– If y is a reference parameter results could
depend on the operand evaluation order
Implementing Functions
Activation Records
The Run-time Stack
9.5 Activation Records
• A block of information associated with
each function call, which includes:
Parameters and local variables
Return address
Saved registers
Temporary variables
Return value (if any)
Static link - to the function’s static parent
• Static link reflects static scope rules
• Dynamic link - to the activation record of the
Static & Dynamic Links
• Static link: points to the bottom of the Activation
Record (AR) of the static parent; used to resolve
non-local references.
– Needed in languages that allow nested function
definitions (Pascal, Algol, Ada, Java’s inner
classes) and for languages that have global
variables or nested blocks.
• Dynamic link: points the top of the AR of the calling
function; used to reset the runtime stack
– In dynamically scoped languages (if there were
any) it could also be used to resolve non-local
Simplified structure of a Called Method’s Stack Frame
Other values
(return address,
saved register
values, space for
storage and
return values)
will also be
allocated in the
stack frame.
Activation Record Stack
• Activation records are created when a function
(or block) is called and deleted when the
function returns to its caller (based on a
template prepared by the compiler)
• The stack is a natural structure for storing the
activation records (sometimes called stack
• The AR at the top of the stack contains
information about the currently executing
Types of Data Storage
• Static – permanent allocation (e.g., h
and i in the sample program)
• Stack: (stack-dynamic allocation)
• Heap: storage allocated/deallocated in a
less predictable order (dynamic
memory allocation)
More about this in the next chapter
Why Stacks?
• Early languages did not use this approach – all
data needed for a function’s activation was
allocated statically at compile time.
• Result: Only one set of locations for each
– One set of locations for parameters
– One set of locations for local variables,
– One set of locations for return addresses,
– Etc.
• What about recursive functions?
9.6 Recursive Functions
• A function that can call itself, either directly
or indirectly, is a recursive function; e.g.,
int factorial (int n) {
if (n < 2)
return 1;
else return n*factorial(n-1);
9.6 Recursive Functions
• When the first call is made, create an
activation record to hold its information
• Each recursive call from the else will
cause another activation record to be
else return n*factorial(n-1);
Recursive self-call
9.7 Run Time Stack
• The run-time stack is a stack of activation
records reflecting function call and return status.
• When a function call is made, the runtime system
– Allocates space for the stack frame (activation
– Stores argument values (if any) in the frame
– Stores the return address
– Stores a pointer to the static memory (the
static link) or enclosing scope.
– Stores a pointer to the stack frame of the
calling method (the dynamic link.)
Simple Example
• Consider the call factorial(3).
• This places one activation record onto the stack
and generates a second call factorial(2).
• This call generates the call factorial(1), so that
the stack gains three activation records.
• Another call, say factorial (6), would require
6 ARs. With static storage allocation (no
stack), there is only one AR per function, so
recursion isn’t supported.
Recursive Function Call
int factorial (int n) {
if (n < 2)
return 1;
else return n*factorial(n-1);
Stack Activity for factorial(3)
Fig. 9.7
Link fields represented by blank entries
First call
Second call
Third call
returns 1
Second call
First call
returns 2*1=2 returns 3*2=6
Stacks for Non-Recursive
• Consider the program
from Figure 9.1: main
calls A, A calls B
• The stack grows and
shrinks based on the
dynamic calling
• On the next slide, we see
the stack when B is
• As each function
finishes, its AR is popped
from the stack.
int h, i;
void B(int w) {
int j, k;
i = 2*w;
w = w+1;
void A(int x, int y) {
bool i, j;
int main() {
int a, b;
h = 5; a = 3; b = 2;
A(a, b);
Run-Time Stack with Stack Frames for Method Invocations
Figure 9.8
(Note: h shouldn’t be undefined; it is initialized when a & b are)
Three versions
of the stack: one after
main() is called but before it calls A,
one after A is called, one after B is
called. Consider lifetime and scope.
Any variable not in current activation
record must be in static memory to
be in scope.
Passing an Argument
by Reference Example
Suppose, in our sample
program, w had been a
reference parameter. Now,
when A calls B and passes in h
as a parameter, the address of
h is copied onto the stack. The
statement w = w + 1 will
change the actual value of h.
Static v Dynamic Scoping
• Static links implement static scoping (nested
– In statically scoped languages, when B
assigns to i, the reference is to the global i
• Dynamic scoping is based on the calling
sequence, shown in the dynamic linkage.
– In dynamically scoped languages, when B
assigns to i, the reference would be to the i
defined in A (most recent in calling chain)
• In either case the links allow a function to refer
to non-local variables.
Clite Concrete Grammar:
Functions and Globals (new elements underlined)
Progr  { Type Identifier FunctionOrGlobal} MainFunction
Type  int | boolean | float | char | void
FunctionOrGlobal  ( Parameters ) { Declarations
Statements } |Global
Parameters  [ Parameter { , Parameter } ]
Global  { , Identifier } ;
MainFunction  int main ( ) { Declarations Statements }
Concrete Syntax Continued
Statement  ; | Block | Assignment | IfStatement |
WhileStatement | CallStatement |
CallStatement  Call ;
ReturnStatement  return Expression ;
Factor  Identifier | Literal | ( Expression ) | Call
Call  Identifier ( Arguments )
Arguments  [ Expression { , Expression } ]
Create More
a dictionary:
myD = {}
myD[4568] = 37
myD[34] = 789
myD[100] = 3498
myD[1] = 98
myD[9876] = 348
myD[678] = 3
More Python
View contents
of dictionary:
• Notice that the keys are not ordered and are
also not in the same sequence that they were
– >>> myD
– {1: 98, 34: 789, 100: 3498, 678: 3,
9876: 348, 4568: 37}
• View keys only:
– >>> myD.keys()
– [1, 34, 100, 678, 9876, 4568]
Sort the Dictionary
• Sort the dictionary by key order:
• >>> sorted(myD.items())
• [(1, 98), (34, 789), (100, 3498),
(678, 3), (4568, 37), (9876, 348)]
Sort the Dictionary
• Create a list containing the dictionary keyvalue pairs, sorted by key: (This is no
longer a dictionary)
>>> newList = sorted(myD.items())
>>> newList
[(1, 98), (34, 789), (100, 3498),
(678, 3), (4568, 37), (9876,
>>> newList[4]
(4568, 37)
If the dictionary value is a
• Index like a two-dimensional array to get
one list item.
• >>> box = {}
• >>> box[36] = [2, 'cat', 3.5]
• >>> box
• {36: [2, 'cat', 3.5]}
• >>> box[36][1]
• 'cat'

Programming Languages Chapter 2: Syntax