Discussion 12: Tail Recursion, Macros

This is an online worksheet that you can work on during discussions and tutorials. Your work is not graded and you do not need to submit anything.

Discussion 12 Vitamin

To encourage everyone to watch or attend discussion orientation, we have created small discussion vitamins. Each vitamin you complete will give you an extra credit point towards the course. Please answer all of the questions in this form by Thursday at 11:59 PM.

Tail Recursion

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.

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:

Example Tree

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:

Example Tree

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.

Questions

Q1: Is Tail Call

For each of the following procedures, identify whether it contains a recursive call in a tail context. Also indicate if it uses a constant number of active frames.
(define (question-a x)
  (if (= x 0) 0
      (+ x (question-a (- x 1)))))
In the recursive case, the last expression that is evaluated is a call to +. Therefore, the recursive call is not in tail context, and each of the frames remain active. This procedure uses a number of active frames proportional to the input x.
(define (question-b x y)
  (if (= x 0) y
      (question-b (- x 1) (+ y x))))
The recursive call is the third operand in the if expression, so it is in tail context. This means that the last expression that will be evaluated in the body of this procedure is the recursive procedure call, so this procedure can be run with a constant number of active frames.
(define (question-c x y)
  (if (> x y)
      (question-c (- y 1) x)
      (question-c (+ x 10) y)))
The recursive calls are the second and third operands of the if expression. Only one of these calls is actually evaluated, and whichever one it is will be the last expression evaluated in the body of the procedure. This procedure therefore can be run with a constant number of active frames.

Note that if you actually try and evaluate this procedure, it will never terminate. But at least it won't crash from hitting max recursion depth!

(define (question-d n)
  (if (question-d n)
      (question-d (- n 1))
      (question-d (+ n 10))))
The second and third recursive calls are in tail context, but the first is not. Since not all the recursive calls are tail calls, this procedure requires active frames for all of the recursive calls.

Additionally, this question will actually lead to infinite recursion because the if condition will never reach a base case!

(define (question-e n)
  (cond ((<= n 1) 1)
        ((question-e (- n 1)) (question-e (- n 2)))
        (else (begin (print 2) (question-e (- n 3))))))
The second and third recursive calls are the second expressions in a clause, so they are in tail context. However, the first recursive call is not in tail context. Since not all recursive calls are tail calls, this procedure is not tail recursive and does not use a constant number of active frames.

Q2: Sum

Write a tail recursive function that takes in a Scheme list and returns the numerical sum of all values in the list. You can assume that the list contains only numbers (no nested lists). Your Answer
Run in 61A Code
Solution
(define (sum lst)
(define (sum-sofar lst current-sum) (if (null? lst) current-sum (sum-sofar (cdr lst) (+ (car lst) current-sum)))) (sum-sofar lst 0)
)
; ALTERNATE SOLUTION (define (sum lst) (cond ((null? lst) 0) ((null? (cdr lst)) (car lst)) (else (sum (cons (+ (car lst) (car (cdr lst))) (cdr (cdr lst))))) ) )
scm> (sum '(1 2 3))
6
scm> (sum '(10 -3 4))
11

Q3: (Tutorial) Reverse

Write a tail-recursive function reverse that takes in a Scheme list a returns a reversed copy. Hint: use a helper function!

Your Answer
Run in 61A Code
Solution
(define (reverse lst)
(define (reverse-tail sofar rest) (if (null? rest) sofar (reverse-tail (cons (car rest) sofar) (cdr rest)))) (reverse-tail nil lst)
)
scm> (reverse '(1 2 3))
(3 2 1)
scm> (reverse '(0 9 1 2))
(2 1 9 0)

Python "Macros"

Imagine if we wanted to write a function in Python that would create and evaluate the following line of code:

[<expr> for i in range(5)]

Where we could pass in any arbitrary expression <expr>, that would then be evaluated 5 times and have the results listed. This is the kind of problem that macros were made for!

A macro is a procedure that operates on unevaluated code. In the example above, <expr> is not necessarily an object, but could be any piece of code, such as print("Hello"), [j ** 2 for j in range(i)], or i >= 5. For these expressions it is important to our problem statement that they not be evaluated until after they have been inserted into our list comprehension, either because they have side effects that will be apparent in the global frame, or because they depend on i in some way (there can be other reasons too!). So, we need a procedure that, instead of manipulating objects, manipulates code itself. This is where macros come in.

Unfortunately for us, Python does not have the ability to make true macros. Let's see what happens if we try to solve this problem with a traditional function.

def list_5(expr):
	return [expr for i  in range(5)]

>>> lst = list_5(print(10))
10
>>> lst
[None, None, None, None, None]

This isn't quite what we want. Because of Python evaluation rules, instead of evaluating a list of 5 print(10) statements, our expr was evaluated before the function was ever called, meaning 10 was only printed once.

The issue here is order of evaluation---we don't want our expression parameter to be evaluated until after it is inserted into our list comprehension. Even though we don't have the ability to make real macros when writing Python, we can write a function in the spirit of macros by returning a string representing the return expression, and evaluating this string after it has been returned.

def list_5(expr):
	return f"[{expr} for i  in range(5)]"

>>> lst = eval(list_5("print(10)"))
10
10
10
10
10
>>> lst
[None, None, None, None, None]

Now we see the number 10 printed 5 times as a side effect of our function, just like we want! We circumvented Python's evaluate-operands-before-evaluating-function body rule by passing in our desired expression as a string. Then, after we constructed our list comprehension in string form and we've returned it, we used the eval function to force evaluation of the output after the last step in the execution of this function. We were able to write code that took code as a parameter and restructured it in the form of new code!

Although this is a cool hack we can do with Python, its usage is unfortunately rather limited. The eval function will throw a SyntaxError if it is passed any compound'' blocks such as if: ..., while: ..., for: ..., etc. (this does not include list comprehensions, or one-line if-statements such as 1 if a > b else 0.)

Q4: Make Lambda Python

Write a "macro" in Python called make_lambda that takes in two parameters: params, a string containing a comma-separated list of variable names; and body, a Python expression in string form, and returns a string that, when evaluated, will return a lambda function that takes params as its parameters and body as its body.

A string with an f (which is called an f-String) is like a quasiquoted expression in Scheme, and anything in that string in braces will be treated as though it has been unquoted. Try to write make_lambda using this syntax!

For an example of f-Strings, the following two pieces of code are equivalent:

>>> x = 2
>>> "The value of x is: " + x
'The value of x is 2'
>>> f"The value of x is {x}"
'The value of x is 2'

Hint: Try constructing the string that would define the lambda, and return that.

Your Answer
Run in 61A Code
Solution
def make_lambda(params, body):
    """
    >>> f = eval(make_lambda("x, y", "x + y"))
    >>> f
    <function <lambda>>
    >>> f(1, 2)
    3
    >>> g = eval(make_lambda("a, b, c", "c if a > b else -c"))
    >>> g(1, 2, 3)
    -3
    >>> eval(make_lambda("f, x, y", "f(x, y)"))(f, 1, 2)
    3
    """
return f"lambda {params}: {body}"

Q5: (Tutorial) If Macro Python

In Homework 1 you implemented an "If function" that functioned differently from an if statement. It was different because it did not short circuit in evaluating its operands! In this problem, we will write a "macro" in Python called if_macro that takes in three arguments:

  1. condition: a string that will evaluate to a truth-y or false-y value
  2. true_result: a string that will be evaluated and returned if condition is truth-y
  3. false_result: a string that will be evaluated and returned if condition is false-y.

and returns a string that, when evaluated, will return the result of this if function.

if_macro should only evaluate true_result if condition is truth-y, and will only evaluate false_result if condition is false-y.

Hint: You can write a one-line if statement with the following syntax: value_when_true if condition else value_when_false

Hint: Using f-Strings might make this problem easier too!

Your Answer
Run in 61A Code
Solution
def if_macro(condition, true_result, false_result):
    """
    >>> eval(if_macro("True", "3", "4"))
    3
    >>> eval(if_macro("0", "'if true'", "'if false'"))
    'if false'
    >>> eval(if_macro("1", "print('true')", "print('false')"))
    true
    >>> eval(if_macro("print('condition')", "print('true_result')", "print('false_result')"))
    condition
    false_result
    """
return f"{true_result} if {condition} else {false_result}"

Quasiquoting

scm> (define a 1)
a
scm> '(cons a nil)
(cons a nil)

Recall that the quote special form prevents the Scheme interpreter from executing a following expression. We saw that this helps us create complex lists more easily than repeatedly calling cons or trying to get the structure right with list. It seems like this form would come in handy if we are trying to construct complex Scheme expressions with many nested lists.

Consider that we rewrite the twice macro as follows:

(define-macro (twice f)
  '(begin f f))

This seems like it would have the same effect, but since the quote form prevents any evaluation, the resulting expression we create would actually be (begin f f), which is not what we want.

The quasiquote allows us to construct literal lists in a similar way as quote, but also lets us specify if any sub-expression within the list should be evaluated.

At first glance, the quasiquote (which can be invoked with the backtick ` or the quasiquote special form) behaves exactly the same as ' or quote. However, using quasiquotes gives you the ability to unquote (which can be invoked with the comma , or the unquote special form). This removes an expression from the quoted context, evaluates it, and places it back in.

scm> `(cons a nil)
(cons a nil)
scm> `(cons ,a nil)
(cons 1 nil)

By combining quasiquotes and unquoting, we can often save ourselves a lot of trouble when building macro expressions.

Questions

Q6: Writing Quasiquote Expressions

Given that the following code has been executed in your Scheme environment:

scm> (define a +)
a
scm> (define b 1)
b
scm> (define c 2)
c

Write out the expressions using quasiquote, unquote, a, b, c, and parentheses to fill in the blanks that would lead to each of the following being displayed:

For example,

scm> ___________
(a b c)

Answer:

`(a b c)

a) Fill in the following blank:

scm> __________________
(a 1 c)
`(a ,b c)

b) Fill in the following blank:

scm> __________________
3
(a b c)

c) Fill in the following blank:

scm> __________________
(a (b 1) c)
`(a (b ,b) c)

d) Fill in the following blank:

scm> __________________
(a 3 c)
`(a ,(a b c) c)

Additional Practice Now, let the following be defined:

scm> (define condition '(= 1 1))
condition
scm> (define if-true '(print 3))
if-true
scm> (define if-false '(print 5))
if-false

Write the Scheme expression using the variables condition, if-true, and if-false along with quasiquoting, that would evaluate to the following:

scm> ________________________
(if (= 1 1) (print 3) (print 5))
`(if ,condition ,if-true ,if-false)

Q7: (Tutorial) If Macro Scheme

Now let's try to write out the if macro in Scheme! There are quite a few similarities between Python and Scheme, but we do have to make a few adjustments when converting our code over to Scheme. We'll start out by writing a Scheme function using the define form we use for normal functions.

Discuss the following questions with your tutorial group regarding how we can write out a Scheme if-function similar to our Python one:

In the Python If macro, we returned a string that, when evaluated, would execute an if statement with the correct parameters. In Scheme, we won't return a string, but rather we'll return something else that represents an unevaluated expression. What type wil we return for Scheme? Here, what "type" refers to what data type -- i.e. function, list, integer, string, etc..

Scheme lists

In the Python If macro, our parameters were all strings representing the condition, return value if true, and return value if false. What type will each of our parameters be in Scheme? Give an example of an acceptable parameter for the condition.

Strings, or the quoted versions of each of our operands. I.e. for condition, we can pass in '(= 1 1)

Let's start writing this out!

Write a function if-function using the define form (not the define-macro form), which will take in the following parameters:

  1. condition : a quoted expression which will evaluate to the condition in our if expression
  2. if-true : a quoted expression which will evaluate to the value we want to return if true
  3. if-false : a quoted expression which will evaluate to the value we want to return if false

and returns a Scheme list representing the expression that, when evaluated, will evaluate to the result of our if expression.

Here are some doctests to show this:

scm> (if-function '(= 0 0) '2 '3)
(if (= 0 0) 2 3)
scm> (eval (if-function '(= 0 0) '2 '3))
2
scm> (if-function '(= 1 0) '(print 3) '(print 5))
(if (= 1 0) (print 3) (print 5))
scm> (eval (if-function '(= 1 0) '(print 3) '(print 5)))
5
Your Answer
Run in 61A Code
Solution
(define (if-function condition if-true if-false)
`(if ,condition ,if-true ,if-false)
)

That felt a bit overly complicated just to create a function that emulates the if special form. We had to quote parameters, and we had to do an extra call to eval at the end to actually get our answer. To make things easier, we can use the define-macro special form to simplify this process.

As a reminder, the define-macro form changes the order of evaluation to be:

  1. Evaluate operator
  2. Apply operator to unevaluated operands
  3. Evaluate the expression returned by the macro in the frame it was called in.

As a comparison, here are differences between define-macro and define:

  1. The operands are not evaluated immediately. Instead, we can think of the operands as being quoted, similar to what we did in the previous part.
  2. The return value gets evaled at the very end, after the entire return expression is constructed. This means that we no longer have to call eval on the return value of our if-function.

Now, use the define-macro special form to define a macro, if-macro, that will have functionality shown by the following doctests (notice how the operands are no longer quoted, and that the final eval is gone):

scm> (if-macro (= 0 0) 2 3)
2
scm> (if-macro (= 1 0) (print 3) (print 5))
5
Your Answer
Run in 61A Code
Solution
(define-macro (if-macro condition if-true if-false)
`(if ,condition ,if-true ,if-false)
)