Discussion 12: Tail Recursion, Macros
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:
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:
- Instead of creating a new frame, the interpreter can just update
the values of the relevant variables in the current frame (like
n
andresult
for thefact-tail
procedure). It reuses the same frame for the entire calculation, constantly changing the bindings to match the next set of parameters. - 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:
- the second or third operand in an
if
expression - any of the non-predicate sub-expressions in a
cond
expression (i.e. the second expression of each clause) - the last operand in an
and
or anor
expression - the last operand in a
begin
expression's body - 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)))))
(define (question-b x y)
(if (= x 0) y
(question-b (- x 1) (+ y x))))
(define (question-c x y)
(if (> x y)
(question-c (- y 1) x)
(question-c (+ x 10) y)))
(define (question-d n)
(if (question-d n)
(question-d (- n 1))
(question-d (+ n 10))))
(define (question-e n)
(cond ((<= n 1) 1)
((question-e (- n 1)) (question-e (- n 2)))
(else (begin (print 2) (question-e (- n 3))))))
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). Run in 61A Codescm> (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!
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 calledmake_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.
Run in 61A CodeQ5: (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:
condition
: a string that will evaluate to a truth-y or false-y valuetrue_result
: a string that will be evaluated and returned ifcondition
is truth-yfalse_result
: a string that will be evaluated and returned ifcondition
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.
Run in 61A CodeHint: You can write a one-line if statement with the following syntax:
value_when_true
ifcondition
elsevalue_when_false
Hint: Using f-Strings might make this problem easier too!
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)
b) Fill in the following blank:
scm> __________________
3
c) Fill in the following blank:
scm> __________________
(a (b 1) c)
d) Fill in the following blank:
scm> __________________
(a 3 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))
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..
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.
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:
condition
: a quoted expression which will evaluate to the condition in our if expressionif-true
: a quoted expression which will evaluate to the value we want to return if trueif-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
Run in 61A Code
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:
- Evaluate operator
- Apply operator to unevaluated operands
- 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
:
- 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.
- The return value gets
eval
ed at the very end, after the entire return expression is constructed. This means that we no longer have to calleval
on the return value of ourif-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
Run in 61A Code