Recall from lecture that Scheme supports tail-call optimization. The example we used was factorial (shown in both Python and Scheme):
def fact(n): if n == 0: return 1 return n * fact(n - 1) (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 return total
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 total 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?
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.
To sum it up (with vocabulary!), here is the quote from lecture: "A procedure call that has not yet returned is active. Some procedure calls are tail calls. A Scheme interpreter should support an unbounded number of active tail calls."
A tail call is a call expression in a tail context:
For the following procedures, decide whether each is tail-call optimized. Do not run the procedures (they may not work)!
Check the recursive calls in tail positions (there might be multiple). Is it in a tail context? In other words, does the last recursive call need to return to the caller because there is still more work to be done with it?
List what each of the tail-calls are to help decide of they are optimized.
(define (question-a x) (if (= x 0) 0 (+ x (question-a (- x 1)))))
The tail call is a "+." This is not optimized, because a recursive call is an argument to the call to "+."
(define (question-b x y) (if (= x 0) y (question-b (- x 1) (+ y x))))
Tail-call to question-b. It is in sub-expression 3 in a tail context if expression.
(define (question-c x y) (if (= x y) #t (if (< x y) #f (or (question-c (- x 1) (- y 2)) #f))))
Does not have a tail-call. (question-c would need to be called outside of the or statement or in the last sub-expression.)
(define (question-d x y) (cond ((= x y) #t) ((< x y) #f) (else (or #f (question-d (- x 1) (- y 2))))))
There is a tail-call to question-d because it is the last sub-expression in a tail context or statement.
(define (question-e x y) (if (> x y) (question-e (- y 1) x) (question-e (+ x 10) y)))
Both recursive calls are tail-calls. But infinite loop! So please don't do this.
(define (question-f n) (if (question-f n) (question-f (- n 1)) (question-f (+ n 10))))
The 2 recursive calls in the non-predicate sub-expressions are tail-calls.
Write a function last, which takes in a Scheme list and returns the last element of the list. Make sure it is tail recursive!
(define (last s)
(if (null? (cdr s)) (car s) (last (cdr s))))
Write the tail recursive version of a function that returns the nth fibonacci number. It might be beneficial to try writing a normal recursive solution and/or a iterative Python version first.
(define (fib n)
(define (fib-iter k prev curr) (if (= k n) curr (fib-iter (+ k 1) curr (+ curr prev)))) (if (= n 1) 0 (fib-iter 2 0 1)))
Write a tail-recursive function reverse that takes in a Scheme list a returns a reversed copy. Hint: use a helper function!
(define (reverse-iter lst)
(reverse-iter nil lst)) (define (reverse-iter sofar rest) (if (null? rest) sofar (reverse-iter (cons (car rest) sofar) (cdr rest))))
Write a tail-recursive function that inserts number n into a sorted list of numbers, s. Hint: Use the built-in scheme function append
(define (insert n s)
(define (insert-help s so-far) (cond ((null? s) so-far) ((< n (car s)) (append so-far (cons n s))) (else (insert-help (cdr s) (append so-far (list (car s)))))) (insert-help s nil))
Remember the for loop? (We really hope so.) The object that the for loop iterates over is required to be an iterable!
for elem in iterable: # do something
for loops only work with iterables, and that means that the object you want to use a for loop on must implement the iterable interface. In particular, a for loop makes use of two methods: __iter__ and __next__. In other words, an object that implements the iterable interface must implement an __iter__ method that returns an object that implements the __next__ method.
This object that implements the __next__ method is called an iterator. While the iterator interface also requires that the object implement the __next__ and __iter__ methods, it does not require the __iter__ method to return a new object.
Here is an example of a class definition for an object that implements the iterator interface:
class AnIterator(object): def __init__(self): self.current = 0 def __next__(self): if self.current > 5: raise StopIteration self.current += 1 return self.current def __iter__(self): return self
Let's go ahead and try out our new toy.
>>> for i in AnIterator(): ... print(i) ... 1 2 3 4 5
This is somewhat equivalent to running:
t = AnIterator() t = t.__iter__() try: while True: print(t.__next__()) except StopIteration as e: pass
Try running each of the given iterators in a for loop. Why does each work or not work?
class IteratorA(object): def __init__(self): self.start = 5 def __next__(self): if self.start == 100: raise StopIteration self.start += 5 return self.start def __iter__(self): return self
No problem, this is a beautiful iterator.
class IteratorB(object): def __init__(self): self.start = 5 def __iter__(self): return self
Oh no! Where is __next__? This fails to implement the iterator interface because calling __iter__ doesn't return something that has a __next__ method.
class IteratorC(object): def __init__(self): self.start = 5 def __next__(self): if self.start == 10: raise StopIteration self.start += 1 return self.start
This also fails to implement the iterator interface. Without the __iter__ method, the for loop will error. The for loop needs to call __iter__ first because some objects might not implement the __next__ method themselves, but calling __iter__ will return an object that does.
class IteratorD(object): def __init__(self): self.start = 1 def __next__(self): self.start += 1 return self.start def __iter__(self): return self
Watch out on this one. The amount of output might scare you.
This is an infinite sequence! Sequences like these are the reason iterators are useful. Because iterators delay computation, we can use a finite amount of memory to represent an infinitely long sequence.
For one of the above iterators that works, try this:
>>> i = IteratorA() >>> for item in i: ... print(item)
>>> for item in i: ... print(item)
With that in mind, try writing an iterator that "restarts" every time it is run through a for loop.
>>> i = IteratorRestart(2, 7) >>> for item in i: ... print(item) # should print 2 to 7 >>> for item in i: ... print(item) # should still print 2 to 7
class IteratorRestart(object): def __init__(self, start, end): self.start = start self.end = end self.current = start def __next__(self): if self.current > self.end: raise StopIteration self.current += 1 def __iter__(self): self.current = self.start return self
Write an iterator that takes a string as input:
>>> s = Str("hello") >>> for char in s: ... print(char) ... h e l l o
class Str: def __init__(self, str): self.str = str def __iter__(self): return self.str.__iter__()
That works (why?), but just kidding.
class Str: def __init__(self, str): self.str = str self.i = -1 def __next__(self): if self.i >= len(self.str): raise StopIteration self.i += 1 return self.str[self.i] def __iter__(self): return self
A generator is a special type of iterator that can be written using a yield statement:
def <generator_function>(): <somevariable> = <something> while <predicate>: yield <something> <increment variable>
A generator function can also be run through a for loop:
def generator(): i = 0 while i < 6: yield i i += 1 for i in generator(): print(i)
To better figure out what is happening, try this:
def generator(): print("Starting here") i = 0 while i < 6: print("Before yield") yield i print("After yield") i += 1 >>> g = generator() >>> g ___ # what is this thing? >>> g.__iter__() ___ >>> g.__next__() ___ >>> g.__next__() ____
Trace through the code and make sure you know where and why each statement is printed.
You might have noticed from the Iterators section that the Iterator defined without a __next__ method failed to run in the for loop. However, this is not always the case.
class IterGen(object): def __init__(self): self.start = 5 def __iter__(self): while self.start < 10: self.start += 1 yield self.start for i in IterGen(): print(i)
Think for a moment about why that works.
Okay, I'll tell you.
The for loop only expects the object returned by __iter__ to have a __next__ method, and the __iter__ method is a generator function in this case. Therefore, when __iter__ is called, it returns a generator object, which you can call __next__ on.
Write a generator that counts down to 0.
Write it in both ways: using a generator function on its own, and within the __iter__ method of a class.
def countdown(n): """ >>> for number in countdown(5): ... print(number) ... 5 4 3 2 1 0 """
while n >= 0: yield n n = n - 1
def __init__(self, cur): self.cur = cur def __iter__(self): while self.cur > 0: yield self.cur self.cur -= 1
Like in the iterator section, write a generator that outputs each character of a string.
def char_gen(str): """ >>> for char in char_gen("hello"): ... print(char) ... h e l l o """
i = 0 while i < len(str): yield str[i] i += 1
Write a generator that outputs the hailstone sequence from homework 1.
def hailstone(n): """ >>> for num in hailstone(10): ... print(num) ... 10 5 16 8 4 2 1 """
i = n while i > 1: yield i if i % 2 == 0: i //= 2 else: i = i*3 + 1 yield i
And now you know how for loops work! Or more importantly, you have become a better computer scientist.