Exercises for Section 7.3

7.3.1

In Fig. 7.15 is a ML function main that computes Fibonacci numbers in a nonstandard way. Function fibO will compute the nth Fibonacci number for any n >= O. Nested within in is fib1, which computes the nth Fibonacci number on the assumption n >= 2, and nested within fib1 is fib2, which assumes n >= 4. Note that neither fib1 nor fib2 need to check for the basis cases. Show the stack of activation records that result from a call to main, up until the time that the first call (to fibO(1)) is about to return. Show the access link in each of the activation records on the stack.

fun main() {
    let
        fun fibO(n) 
            let
                fun fib1(n) =   
                    let
                        fun fib2(n) = fib1(n-l) + fib1(n-2)  
                    in
                        if n >= 4 then fib2(n)
                        else fibO(n-l) + fibO(n-2)  
                    end
            in
                if n >= 2 then fib1(n) else 1
            end  
    in
        fibO(4)  
    end ;

Figure 7.15: Nested functions computing Fibonacci numbers

Answer

activation tree:

activation stack when first call to fib0(1) is about to return:

7.3.2

Suppose that we implement the functions of Fig. 7.15 using a display. Show the display at the moment the first call to fibO(1) is about to return. Also, indicate the saved display entry in each of the activation records on the stack at that time. 

Answer