CS 461
Subroutines and Control Abstraction Tail Recursion
Exception Handling
Yanling Wang
Computer Science and Engineering Penn State University
Carnegie Mellon
1
Outline
¢ This Lecture – Activation Record and Tail Recursion ¢ This Lecture – Exception Handling
Carnegie Mellon
2
TAIL RECURSION
Carnegie Mellon
3
Review of Storage Layout
High address
Carnegie Mellon
Stack
Free space
Heap
Static data
Code
Low address
4
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
5
Stack Frame (Activation Record)
A stack frame contains:
• Local variables
• Temporaries
• Return values
• Bookkeeping info
• Arguments (to the callee)
Carnegie Mellon
arguments
temporaries
locals
misc bookkeeping
return addr
6
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
7
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
8
…
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
9
…
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
10
…
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
11
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
12
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–;);
}
}
13
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
14
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
15
Tail-Recursive Functions to Loops
Tail-recursive
int fact(int n, int prev ) {
if ( n == 1 ) return prev ;
else return fact(n-1, prev*n);
}
Loops
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 code
In most functional languages (e.g., Scheme, Ocaml), the compiler automatically generate code as efficient as the loop version
Carnegie Mellon
16
EXCEPTION HANDLING
Carnegie Mellon
17
Exceptions
So far, we assumed each function will run from start to its return points
But a program also needs to handle exceptions: ¢ Out of memory
¢ Divide by zero
¢ File not found
¢...
Carnegie Mellon
18
18
Workaround in C language
¢ Return a special value (e.g., NULL) when a real value cannot be computed
¢ Return an explicit ”status” to indicate if an exception happens
¢ Rely on the caller to pass in the exception handling code (e.g., via function pointer)
Exception handling is not enforced (error-prone) Clutter up the program, especially for normal cases
Carnegie Mellon
19
19
Exception Handling
A language feature that
¢ Isolate error-checking code
¢ Direct execution to a handler when appropriate
Define exceptions?
How does exception change control flow?
Carnegie Mellon
20
20
Defining Exceptions Pre-defined exceptions
¢ e.g., divide by zero, out-of-bound array access In Object-Oriented Language
¢ Typically, defined as subclass from exception class (i.e., in C++, inherit from exception class)
Carnegie Mellon
class MyException:public exception {
virtual const char* what() const throw()
{
return "My exception happened";
}
} myex;
21
21
Throwing Exceptions Pre-defined exceptions
¢ Automatically generated
User-defined exceptions
¢ Generated by “throw” keyword
Carnegie Mellon
int foo () {
...
throw myex;
...
}
22
22
Catching Exceptions
Carnegie Mellon
try {
.. code that might throw exceptions ..
}
catch (Exception1 e1) {.. handling code ..}
catch (Exception2 e2) {.. handling code ..}
...
23
23
Catching Exceptions - finally
Some languages (i.e. Java) uses finally to clean up resources.
Carnegie Mellon
try {
.. code that might throw exceptions ..
}
catch (Exception1 e1) {.. handling code ..}
catch (Exception2 e2) {.. handling code ..}
...
finally {.. this code always executes,
e.g. cleanup routine ..}
24
24
Catching Exceptions - RAII
Some languages (i.e. C++ and .Net languages such as C#)
• Resource Acquisition Is Initialization
• Clean up is done is object destructor
• Automatically called when object is going out of scope
Carnegie Mellon
try {
.. code that might throw exceptions ..
}
catch (Exception1 e1) {.. handling code ..}
catch (Exception2 e2) {.. handling code ..}
...
25
25
The “Replacement” Semantics
Carnegie Mellon
int foo () {
...
try { ...
throw new myException(10);
... // this is replaced with handling code
} catch (myException e) {
.. Handling code ...
}
... }
26
26
Exception Propagation
current frame
A
Carnegie Mellon
If no handler is found
If no handler is found
control flow continues after the handler in C
The exception mechanism needs to
B
C
D
properly follow calling sequences to Stack with Frames properly “exit” functions (e.g., restore
registers, destroy frame)
27
27
Exception Implementation When encounter an exception at pc:
¢ Go through handlers associated with pc in sequence
¢ Each handler either executes (when exception matches) or re-throws the exception for next handler
¢ If exception not handled, use a function-level handler: exit the function properly and re-throw the exception
¢ Now, pc is in the caller, and repeat the first bullet in the caller
Carnegie Mellon
28
28