CS 461
Subroutines and Control Abstraction Activation Record and Tail Recursion
Yanling Wang
Computer Science and Engineering Penn State University
Carnegie Mellon
1
Outline
¢ Last Lecture – Parameter Passing Mode
§ Call-By-Value-Result (Ada’s in out parameter)
§ Call-By-Sharing (Call-By-Value in Java/Python where value is a reference)
§ Call-By-Value/Sharing (C array’s value is a reference/pointer to the array)
¢ This Lecture – Activation Record and Tail Recursion
Carnegie Mellon
2
Call-By-Value-Return (In-Out)
Calling mechanism
¢ Arguments are evaluated to their values
¢ Memory or registers allocated for arguments on AR
¢ Argument values stored in AR
¢ Before callee returns, AR values copied back to
actual arguments
¢ AR destroyed when callee returns
Carnegie Mellon
3
3
Call-By-Value-Return (with aliasing)
with Ada.Integer_Text_IO;
procedure f2 is
function set(I1, I2:in out Integer) return Integer is
begin
I1 := I1 + 1;
I2 := I2 + 2;
return I1 + I2;
end set;
nums: Array (0..1) of Integer := (0, 10);
i1, i2:Integer;
y:Integer;
begin
Ada.Integer_Text_IO.Get(i1);
Ada.Integer_Text_IO.Get(i2);
y := set(nums(i1), nums(i2));
end f2;
Carnegie Mellon
4
Call-By-Reference (with aliasing in C++)
#include
int set(int &I1, int &I2) {
I1 = I1 + 1;
I2 = I2 + 2;
return I1 + I2;
}
int main() {
int nums[2] = {0, 10};
int i1;
int i2;
std::cin >> i1;
std::cin >> i2;
int y = set(nums[i1], nums[i2]);
return 0;
}
Carnegie Mellon
5
C: Use pointer to simulate call-by-reference
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
return; }
int main() {
int x = 3;
int y = 4;
swap(&x, &y);
return 0;
}
Carnegie Mellon
6
Java: Call-By-Value / Call-By-Sharing
¢ Java uses call-by-value
§ Primitive values are always call-by-value
§ Primitive.java
§ Objects are call-by-value but the value is essentially a pointer
(reference) to the objects.
§ You can’t change the pointer to point to a different object location. (WithObject2.java)
§ You can use this pointer to change the content of the object it is pointing to. (WithObject.java)
Carnegie Mellon
7
Primitive.java – Call-By-Value
public class Primitive {
public static void main(String[] args) {
int x = 3;
int y = 4;
swap(x, y);
}
public static void swap(int a, int b) {
} }
int temp = a;
a = b;
b = temp;
Doesn’t swap!
Carnegie Mellon
8
WithObject.java – Call-By-Sharing (Value is a pointer/reference)
public class WithObject {
public static void main(String[] args) {
Wrapper x = new Wrapper(3);
Wrapper y = new Wrapper(4);
swap(x, y);
}
public static void swap(Wrapper a, Wrapper b) {
} }
class Wrapper {
public int value;
}
int temp = a.value;
a.value = b.value;
b.value = temp;
Does swap!
public Wrapper(int value){ this.value = value;}
Carnegie Mellon
9
WithObject2.java – Call-By-Sharing (Value is a pointer/reference)
public class WithObject2 {
public static void main(String[] args) {
Wrapper x = new Wrapper(3);
Wrapper y = new Wrapper(4);
swap(x, y);
}
public static void swap(Wrapper a, Wrapper b) {
} }
class Wrapper {
public int value;
}
Wrapper temp = a;
a = b;
b = temp;
Doesn’t swap!
public Wrapper(int value){ this.value = value;}
Carnegie Mellon
10
Call-By-Value/Call-By-Sharing in Python
¢ Python is similar to Java § Call by value
§ But all values are references(pointers) to objects § Primitive Objects/Immutable objects:
§ Not much difference between call-by-value vs. call-by-sharing.
§ Can not modify the objects even if you have its reference § Mutable Objects:
§ modify the object through the reference (affects caller)
§ vs.
§ modify the reference to refer to a different object (doesn’t affect the caller because reference is a value copied to the AR)
Carnegie Mellon
11
Python Example ¢ Example:
§ lst.sort() (list method that modifies the list through the refrence lst)
§ vs.
§ lst = sorted(lst) (build-in function that creates a new sorted list)
¢ Within a function
§ Operations that modify an object through the reference can impact
the caller
§ lst.sort()
§ lst.append(1)
§ Operations make the formal parameters refer to a newly created object doesn’t have effect on the caller
§ lst = sorted(lst) § lst = lst + [1]
§ …
12
Carnegie Mellon
Python Example — appending list3.py list4.py
Carnegie Mellon
t = []
def appendlist(lst, v):
lst.append(v)
return lst
t1 = appendlist(t, 1)
t = []
def appendlist(lst, v):
lst = lst + [v]
return lst
t1 = appendlist(t, 1)
13
C and Arrays
¢ In C, arrays are passed to functions as the address to its 0th element.
§ Modify the content of the array through the pointer will affect the caller.
§ Modify the pointer to point to something new will not affect the caller.
Carnegie Mellon
14
C Array Example:
#include
void swap(int arr[]) {
int temp = arr[0];
arr[0] = arr[1];
arr[1] = temp;
}
void swap1(int arr[]) {
int *temp = malloc(sizeof(int) * 2);
temp[0] = arr[1];
temp[1] = arr[0];
arr = temp;
}
int main() {
int nums[2] = {1, 2};
swap(nums);
swap1(nums);
return 0;
}
Carnegie Mellon
15
TAIL RECURSION
Carnegie Mellon
16
Review of Storage Layout
High address
Carnegie Mellon
Stack
Free space
Heap
Static data
Code
Low address
17
Support for Functions
Carnegie Mellon
int fact(int n) {
int tmp = 0;
if n==1 return 1;
else
{tmp = n-1;
return n*fact(tmp);}
}
fact
fact
fact
During execution, each function call has one frame (activation record) on the stack
18
1 9
Carnegie Mellon
Stack Frame (Activation
Record)
A stack frame contains:
• Local variables
• Temporaries
• Return values
• Bookkeeping info
• Arguments (to the callee)
arguments
temporaries
locals
misc bookkeeping
return addr
19
Stack Frame (Activation Record)
Carnegie Mellon
int fact(int n) {
int tmp = 0;
if n==1
return 1;
else {
tmp = n-1;
return n*fact(tmp);
}
}
Local tmp
Previous fp
Return Addr
Para. n = 1
Local tmp
Previous fp
Return Addr
Para. n = 2
Calling fact(2) in main
Frame of fact(1)
Frame of fact(2)
Frame of main
20
Carnegie Mellon
int fact(int n) {
int tmp = 0;
if n==1
return 1;
else {
tmp = n-1;
return n*fact(tmp); W}hat happens for fact(100)?
}
Consumes memory
Para. n = 98
Local tmp
Previous fp
Return Addr
Para. n = 99
Local tmp
Previous fp
Return Addr
Para. n = 100
Wastes time on calling sequence
Frame of fact(99)
Frame
of fact(100)
Frame of main
21
…
Carnegie Mellon
int fact(int n) {
int tmp = 0;
if n==1
return 1;
else {
tmp = n-1;
return n*fact(tmp);
}
}
Para. n = 98
Local tmp
Previous fp
Return Addr
Para. n = 99
Local tmp
Previous fp
Return Addr
Para. n = 100
Can we destroy the frame of fact(100) before going into fact(99)?
Frame of fact(99)
Frame
of fact(100)
Frame of main
22
…
A Different Implementation
Carnegie Mellon
int fact(int n, int prev ) {
if ( n == 1 ) return prev ;
else return fact(n-1, prev*n);
}
Para. n = 98
Para. prev = 9900
Previous fp
Return Addr
Para. n = 99
Para. prev= 100 Previous fp
Return Addr
Para. n = 100
Para. prev = 1
Can we destroy the frame of fact(100) before going into fact(99)?
Frame of fact(99)
Frame
of fact(100)
Frame of main
23
…
A Different Implementation
Carnegie Mellon
int fact(int n, int prev ) {
if ( n == 1 ) return prev ;
else return fact(n-1, prev*n);
}
Can we destroy the frame of fact(100) before going into fact(99)?
Previous fp
Return Addr
Para. n
Para. prev
What change enables the
more efficient implementation?
Reused frame
24
Tail-Recursive Functions
Recursion only occur at the end of a function: no computation after recursive call
int fact(int n, int prev ) {
if ( n == 1 ) return prev ;
else return fact(n-1, prev*n);
}
The current activation record before recursive call is useless!
Carnegie Mellon
25
Tail-Recursive Functions Tail-recursive functions are equivalent to loops
Carnegie Mellon
int fact(int n, int prev ) {
if ( n == 1 ) return prev ;
else return fact(n-1, prev*n);
}
int fact(int n, int prev ) {
while (true) {
if ( n == 1 ) return prev ;
else {prev = prev*n; n–;);
}
}
26
Is this function tail recursive?
int search(int[] a, int k, int fst, int lst) {
if ( fst == lst ) return (a[fst]==k?fst:-1);
int m = (fst + lst)/2;
if (k <= a[m]) return search(a, k, fst, m);
else return search(a, k, m+1, lst);
}
Carnegie Mellon
27
Loop version
int binSearch(int[] a, int k, int fst, int lst) {
while (true) {
if ( fst == lst ) return (a[fst]==k?fst:-1);
int m = (fst + lst)/2;
if (k <= a[m]) lst = m;
else fst = m+1;
} }
Carnegie Mellon
28
Tail-Recursive Functions to Loops
Tail-recursive
Loops
int fact(int n, int prev ) {
if ( n == 1 ) return prev ;
else return fact(n-1, prev*n);
}
int fact(int n, int prev ) {
while (true) {
if ( n == 1 ) return prev ;
else {prev = prev*n; n--;);
}}
In C and Java, the loop version is more efficient, though some compilers will automatically generate more efficient c
In most functional languages (e.g., Scheme, Ocaml),
the compiler automatically generate code as efficient as the loop version
Carnegie Mellon
29