# Topics

Tail Recursion Minilecture Video

Recall from lecture that Scheme supports tail-call optimization. The example we used was factorial (shown in both Python and Scheme):
``````# Python
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)

# Scheme
(define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))))``````

Notice that in this version of `factorial`, the return expressions both use recursive calls, and then use the values for more "work." In other words, the current frame needs to sit around, waiting for the recursive call to return with a value. Then the current frame can use that value to calculate the final answer.

As an example, consider a call to `fact(5)` (Shown with Scheme below). We make a new frame for the call, and in carrying out the body of the function, we hit the recursive case, where we want to multiply 5 by the return value of the call to `fact(4)`. Then we want to return this product as the answer to `fact(5)`. However, before calculating this product, we must wait for the call to `fact(4)`. The current frame stays while it waits. This is true for every successive recursive call, so by calling `fact(5)`, at one point we will have the frame of `fact(5)` as well as the frames of `fact(4)`, `fact(3)`, `fact(2)`, and `fact(1)`, all waiting for `fact(0)`.

``````(fact 5)
(* 5 (fact 4))
(* 5 (* 4 (fact 3)))
(* 5 (* 4 (* 3 (fact 2))))
(* 5 (* 4 (* 3 (* 2 (fact 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (fact 0))))))
(* 5 (* 4 (* 3 (* 2 (* 1 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (* 3 2)))
(* 5 (* 4 6))
(* 5 24)
120``````

Keeping all these frames around wastes a lot of space, so our goal is to come up with an implementation of factorial that uses a constant amount of space. We notice that in Python we can do this with a while loop:

``````def fact_while(n):
total = 1
while n > 0:
total = total * n
n = n - 1

However, Scheme doesn't have `for` and `while` constructs. No problem! Everything that can be written with while and `for` loops and also be written recursively. Instead of a variable, we introduce a new parameter to keep track of the total.

``````def fact(n):
def fact_optimized(n, total):
if n == 0:
return fact_optimized(n - 1, total * n)
return fact_optimized(n, 1)

(define (fact n)
(define (fact-optimized n total)
(if (= n 0)
total
(fact-optimized (- n 1) (* total n))))
(fact-optimized n 1))``````

Why is this better? Consider calling `fact(n)` on based on this definition:

``````(fact 5)
(fact-optimized 5   1)
(fact-optimized 4   5)
(fact-optimized 3  20)
(fact-optimized 2  60)
(fact-optimized 1 120)
(fact-optimized 0 120)
120``````

Because Scheme supports tail-call optimization (note that Python does not), it knows when it no longer needs to keep around frames because there is no further calculation to do. Looking at the last line in `fact_optimized`, we notice that it returns the same thing that the recursive call does, no more work required. Scheme realizes that there is no reason to keep around a frame that has no work left to do, so it just has the return of the recursive call return directly to whatever called the current frame.

Therefore the last line in `fact_optimized` is a tail-call.

Macros Minilecture Video

So far we've been able to define our own procedures in Scheme using the `define` special form. When we call these procedures, we have to follow the rules for evaluating call expressions, which involve evaluating all the operands.

We know that special form expressions do not follow the evaluation rules of call expressions. Instead, each special form has its own rules of evaluation, which may include not evaluating all the operands. Wouldn't it be cool if we could define our own special forms where we decide which operands are evaluated? Consider the following example where we attempt to write a function that evaluates a given expression twice:

``````scm> (define (twice f) (begin f f))
twice
scm> (twice (print 'woof))
woof``````

Since `twice` is a regular procedure, a call to `twice` will follow the same rules of evaluation as regular call expressions; first we evaluate the operator and then we evaluate the operands. That means that `woof` was printed when we evaluated the operand `(print 'woof)`. Inside the body of `twice`, the name `f` is bound to the value `undefined`, so the expression `(begin f f)` does nothing at all!

The problem here is clear: we need to prevent the given expression from evaluating until we're inside the body of the procedure. This is where the `define-macro` special form, which has identical syntax to the regular `define` form, comes in:

``````scm> (define-macro (twice f) (list 'begin f f))
twice``````

`define-macro` allows us to define what's known as a `macro`, which is simply a way for us to combine unevaluated input expressions together into another expression. When we call macros, the operands are not evaluated, but rather are treated as Scheme data. This means that any operands that are call expressions or special form expression are treated like lists.

If we call `(twice (print 'woof))`, `f` will actually be bound to the list `(print 'woof)` instead of the value `undefined`. Inside the body of `define-macro`, we can insert these expressions into a larger Scheme expression. In our case, we would want a `begin` expression that looks like the following:

``(begin (print 'woof) (print 'woof))``

As Scheme data, this expression is really just a list containing three elements: `begin` and `(print 'woof)` twice, which is exactly what `(list 'begin f f)` returns. Now, when we call `twice`, this list is evaluated as an expression and `(print 'woof)` is evaluated twice.

``````scm> (twice (print 'woof))
woof
woof``````

To recap, macros are called similarly to regular procedures, but the rules for evaluating them are different. We evaluated lambda procedures in the following way:

• Evaluate operator
• Evaluate operands
• Apply operator to operands, evaluating the body of the procedure

However, the rules for evaluating calls to macro procedures are:

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

# Questions

### Q1: WWSD: Macros

One thing to keep in mind when doing this question, builtins get rendered as such:

``````scm> +
#[+]
scm> list
#[list]``````

If evaluating an expression causes an error, type `SchemeError`. If nothing is displayed, type `Nothing`.

Use Ok to test your knowledge with the following "What Would Scheme Display?" questions:

``python3 ok -q wwsd-macros -u``
``````scm> +
______#[+]
scm> list
______#[list]
scm> (define-macro (f x) (car x))
______f
scm> (f (2 3 4)) ; type SchemeError for error, or Nothing for nothing
______2
scm> (f (+ 2 3))
______#[+]
scm> (define x 2000)
______x
scm> (f (x y z))
______2000
scm> (f (list 2 3 4))
______#[list]
scm> (f (quote (2 3 4)))
______SchemeError
scm> (define quote 7000)
______quote
scm> (f (quote (2 3 4)))
______7000``````
``````scm> (define-macro (g x) (+ x 2))
______g
scm> (g 2)
______4
scm> (g (+ 2 3))
______SchemeError
scm> (define-macro (h x) (list '+ x 2))
______h
scm> (h (+ 2 3))
______7``````
``````scm> (define-macro (if-else-5 condition consequent) `(if ,condition ,consequent 5))
______if-else-5
scm> (if-else-5 #t 2)
______2
scm> (if-else-5 #f 3)
______5
scm> (if-else-5 #t (/ 1 0))
______SchemeError
scm> (if-else-5 #f (/ 1 0))
______5
scm> (if-else-5 (= 1 1) 2)
______2``````

### Q2: Replicate

Write a tail-recursive function that returns a list with `x` repeated `n` times.

``````scm> (tail-replicate 3 10)
(3 3 3 3 3 3 3 3 3 3)
scm> (tail-replicate 5 0)
()
scm> (tail-replicate 100 5)
(100 100 100 100 100)``````
``````(define (tail-replicate x n)
(define (helper n so-far)
(if (= n 0) so-far
(helper (- n 1) (cons x so-far))))
(helper n '()))``````

Use Ok to test your code:

``python3 ok -q tail-replicate``

### Q3: Scheme def

Implement `def`, which simulates a python `def` statement, allowing you to write code like `(def f(x y) (+ x y))`.

The above expression should create a function with parameters `x` and `y`, and body `(+ x y)`, then bind it to the name `f` in the current frame.

Note: the previous is equivalent to `(def f (x y) (+ x y))`.

Hint: We strongly suggest doing the WWPD questions on macros first as understanding the rules of macro evaluation is key in writing macros.

``````
(define-macro (def func args body)
`(define ,func (lambda ,args ,body)))``````

Use Ok to test your code:

``python3 ok -q scheme-def``

### Q4: Repeatedly Cube

Implement the following function, which cubes the given value `x` some number `n` times, based on the given skeleton.

For information on how to use let, see the scheme spec or ask a member of course staff.

``````(define (repeatedly-cube n x)
(if (zero? n)
x
(let
((y (repeatedly-cube (- n 1) x)))            (* y y y))))``````

Use Ok to test your code:

``python3 ok -q repeatedly-cube``