Lab 10: Tail Calls

Due by 11:59pm on Tuesday, August 5.

Starter Files

Download lab10.zip.

Topics

Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.


Tail Calls

When writing a recursive procedure, it's possible to write it in a tail recursive way, where all of the recursive calls are tail calls. A tail call occurs when a function calls another function as the last action of the current frame.

Consider this implementation of factorial that is not tail recursive:

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

The recursive call occurs in the last line, but it is not the last expression evaluated. After calling (factorial (- n 1)), the function still needs to multiply that result with n. The final expression that is evaluated is a call to the multiplication function, not factorial itself. Therefore, the recursive call is not a tail call.

Here's a visualization of the recursive process for computing (factorial 6) :

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

The interpreter first must reach the base case and only then can it begin to calculate the products in each of the earlier frames.

We can rewrite this function using a helper function that remembers the temporary product that we have calculated so far in each recursive step.

(define (factorial n)
  (define (fact-tail n result)
    (if (= n 0)
        result
        (fact-tail (- n 1) (* n result))))
  (fact-tail n 1))

fact-tail makes a single recursive call to fact-tail, and that recursive call is the last expression to be evaluated, so it is a tail call. Therefore, fact-tail is a tail recursive process.

Here's a visualization of the tail recursive process for computing (factorial 6):

(factorial 6)
(fact-tail 6 1)
(fact-tail 5 6)
(fact-tail 4 30)
(fact-tail 3 120)
(fact-tail 2 360)
(fact-tail 1 720)
(fact-tail 0 720)
720

The interpreter needed less steps to come up with the result, and it didn't need to re-visit the earlier frames to come up with the final product.

In this example, we've utilized a common strategy in implementing tail-recursive procedures which is to pass the result that we're building (e.g. a list, count, sum, product, etc.) as a argument to our procedure that gets changed across recursive calls. By doing this, we do not have to do any computation to build up the result after the recursive call in the current frame, instead any computation is done before the recursive call and the result is passed to the next frame to be modified further. Often, we do not have a parameter in our procedure that can store this result, but in these cases we can define a helper procedure with an extra parameter(s) and recurse on the helper. This is what we did in the factorial procedure above, with fact-tail having the extra parameter result.

Tail Call Optimization

When a recursive procedure is not written in a tail recursive way, the interpreter must have enough memory to store all of the previous recursive calls.

For example, a call to the (factorial 3) in the non tail-recursive version must keep the frames for all the numbers from 3 down to the base case, until it's finally able to calculate the intermediate products and forget those frames:

For non tail-recursive procedures, the number of active frames grows proportionally to the number of recursive calls. That may be fine for small inputs, but imagine calling factorial on a large number like 10000. The interpreter would need enough memory for all 1000 calls!

Fortunately, proper Scheme interpreters implement tail-call optimization as a requirement of the language specification. TCO ensures that tail recursive procedures can execute with a constant number of active frames, so programmers can call them on large inputs without fear of exceeding the available memory.

When the tail recursive factorial is run in an interpreter with tail-call optimization, the interpreter knows that it does not need to keep the previous frames around, so it never needs to store the whole stack of frames in memory:

Tail-call optimization can be implemented in a few ways:

  1. Instead of creating a new frame, the interpreter can just update the values of the relevant variables in the current frame (like n and result for the fact-tail procedure). It reuses the same frame for the entire calculation, constantly changing the bindings to match the next set of parameters.
  2. How our 61A Scheme interpreter works: The interpreter builds a new frame as usual, but then replaces the current frame with the new one. The old frame is still around, but the interpreter no longer has any way to get to it. When that happens, the Python interpreter does something clever: it recycles the old frame so that the next time a new frame is needed, the system simply allocates it out of recycled space. The technical term is that the old frame becomes "garbage", which the system "garbage collects" behind the programmer's back.

Tail Context

When trying to identify whether a given function call within the body of a function is a tail call, we look for whether the call expression is in tail context.

Given that each of the following expressions is the last expression in the body of the function, the following expressions are tail contexts:

  1. the second or third operand in an if expression
  2. any of the non-predicate sub-expressions in a cond expression (i.e. the second expression of each clause)
  3. the last operand in an and or an or expression
  4. the last operand in a begin expression's body
  5. the last operand in a let expression's body

For example, in the expression (begin (+ 2 3) (- 2 3) (* 2 3)), (* 2 3) is a tail call because it is the last operand expression to be evaluated.


Required Questions

Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

YouTube link

Q1: Exp

We want to implement the exp procedure. So, we write the following recursive procedure:

(define (exp-recursive b n)
  (if (= n 0)
      1
      (* b (exp-recursive b (- n 1)))))

Try to evaluate

(exp-recursive 2 (exp-recursive 2 10))

You will notice that it will cause a maximum recursion depth error. To fix this, we need to use tail recursion! Implement the exp procedure using tail recursion:

(define (exp b n)
  ;; Computes b^n.
  ;; b is any number, n must be a non-negative integer.
  (define (helper n so-far) ;; since b never changes, we can use the b from the outer function
    ;; YOUR CODE HERE
  (helper n 1)
)

Use Ok to test your code:

python3 ok -q exp

Q2: Last

Write a function last, which takes in a Scheme list of length 1 or more and returns the last element of the list. Make sure it is tail recursive!

(define (last s)
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q last

Q3: Swap

Write a tail-recursive function swap, which takes in a Scheme list s and returns a new Scheme list where every two elements in s are swapped.


(define (swap s)
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q swap

Q4: Concatenate

Write a tail-recursive function concatenate, which takes in s, a list of lists, and concatenates all the elements together into one list.

Hint: Recall the built-in append function

(define (concatenate s)
'YOUR-CODE-HERE
)

Use Ok to unlock and test your code:

python3 ok -q concatenate -u
python3 ok -q concatenate

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions. Correctly completing all questions is worth one point for regular section students and two points for mega section students.

If you are in regular section, be sure to fill out your TA's attendance form before you leave section. Attending lab section is worth one point for regular section students.

Optional Questions

Q5: Filter

Write a function filter, which takes in a predicate and a Scheme list and returns a Scheme list whose elements are the elements from the inputted Scheme list that satisfy the predicate.

Make sure filter is tail recursive!

Hint: Try writing the function iteratively in Python, then convert into a tail recursive Scheme function.

You will also find the built-in append function useful. append concatenates two Scheme lists, much like the + operator in Python.

(define (filter pred lst)
  'YOUR-CODE-HERE
)

Use Ok to unlock and test your code:

python3 ok -q filter -u
python3 ok -q filter