:::warning **Announcements** - `A1: Values` released Friday, due Thursday - Still solo, submission via Gradescope - Next help hours: (all L037) - Alexa 6:30-8:30pm tonight L037 - Grace 3-5pm Tuesday L037 - Results of `A0` AI policy poll ::: :::success **Agenda** - Avoiding redundant recursion (`bad-max`) - Big-O of recursive functions - Using `let` to avoid redundancy - Understanding natural recursion - Understanding accumulator pattern - Tail recursion, tail call optimization - Unit testing with RackUnit (if time) ::: # Using local bindings to avoid redundant computation # Avoiding redundant recursion (`bad-max`) ## Pair exercise: runtime :::success Consider this code and the recursive calls it makes. What is the asymptotic complexity in terms of space and time? Assume calls to `first`, `rest`, and `empty?` are O(1) runtime. Note: we'll assume we're given a list with at least 1 element. ::: ```racket (define (bad-max xs) (if (empty? (rest xs)) (first xs) ; A single element is the max (if (> (first xs) (bad-max (rest xs))) (first xs) (bad-max (rest xs))))) ``` :::spoiler Think, then click! Answer: this function is _quite bad_: rather than calling itself once on each recursive call, this implementation _makes an entire redundant recursive call_ whenever it is not at the base case. Since it makes 2 calls instead of 1, the number of recursive calls does not grow linearly but instead: ``` * / \ * * / \ / \ * * * * ``` The redundant calls form a binary tree structure with height proportional to the length of the list $n$. At each level of the tree, the size of next level is calculated by multiplying the size of the previous level by 2. This is 2, times 2, times 2, $n$ many times! This scales with $O(2^n)$, meaning this function is *exponential* instead of linear or even quadratic! ::: In class, we ran this code on these lists (`range` produces a list ranging between two values). Be careful running on `b` and `c` yourself! ``` (define a `(1 4 5 3 2)) (define b (range 0 1000000 1)) (define c (range 0 9000000 1)) ``` We can split "fixing" this `bad-max` implementation into several steps, each highlighting either a feature of ==good functional programming style== *or* an ==interesting language-level optimization==. First, let's just remove the _redundant_ recursion using a `let` binding (==good functional programming style==): ```racket ;; With natural recursion ;; Note: in class we called this m2 (define (max-nat xs) (if (empty? (rest xs)) (first xs) ; A single element is the max (let ((rest-max (max-nat (rest xs)))) (if (> (first xs) rest-max) (first xs) rest-max)))) ``` `max-nat`/`m2` alone is now *much* more efficient than `bad-max`! Each recursive call makes one more recursive call, rather than two. This is no longer a tree of recursive calls, so gets us back into the $O(n)$ runtime that is optimal for a linear maximum calculation! --- Next, we could also simplify our running example function to use a built-in Racket operator (another improvement that is just ==good functional programming style==): Racket has a built-in `max` function that returns the maximum of its arguments. We can thus simplify our running example to: ```racket ; Natural recursion, with max builtin ; In class, we called this m3 (define (max-nat-short xs) (if (empty? (rest xs)) (first xs) (max (first xs) (max-nat-short (rest xs))))) ``` ^ These two versions, `max-nat`/`m2` and `max-nat-short`/`m3`, both require *linear* time, but `max-nat-short`/`m3` is a bit cleaner style-wise. We could stop here, in terms of ==good functional programming style==: we have a concise function that runs in the optimal $O(n)$ runtime. However, we're going to work to improve this function even further! These further improvements rely on a new ==language-level optimization== that improves the **space efficiency** of many functional programs. --- :::success What is the *space* efficiency of `max-nat`/`m2` and `max-nat-short`/`m3`? ::: :::spoiler Think, then click! Both require linear *additional* space (not counting the space for the argument `xs`), for the local variables at each recursive call. As we discussed last class, these local variables are stored in the **call stack**, with one **call stack frame** per function call. ::: For `max-nat-short`, we need a new stack frame for every element of the list: ``` View of the function call stack (grows downward) --------------------------------- | max-nat-short | | xs = '(3 5 4) ; | | context for recursive call: | | (max 3 <result of rec call>) | <- after call, gets 5 --------------------------------- | max-nat-short | | xs = '(5 4) ; | | context for recursive call: | | (max 5 <result of rec call>) | <- after call, gets 4 --------------------------------- | max-nat-short | | xs = '(4) ; | | base case: (rest xs) is empty | | returns 4 | -> return 4 --------------------------------- ``` Note that the argument, `xs`, shrinks on every recursive call, while the returned value is first created at the base case, then updates (represents the result of more work) _after_ each recursive call, before being returned, as execution returns back up the stack. In general, _natural recursion_ shrinks the argument and grows (represents the result of more cumulative work) the result. For this specific function, we can visualize this as: ``` Natural recursion stack grows argument shrinks final result grows ↓ ↓↓↓↓ ↑↑↑↑ ; max with first ↓ ↓↓↓ ↑↑↑ ; max with first ↓ ↓↓ ↑↑ ; max with first ↓ ↓ ↑ ↓ base case base result ``` Natural recursion tends to be the most direct way to write recursive code, and often it's not a problem: if our data is not very large, extra stack frames are fine. However, sometimes we do need large input data, but we don't want a huge call stack! --- :::success What happens if we are trying to take the maximum of a very large list with `max-nat-short`? How does this compare to an imperative-style maximum calculation? ::: :::spoiler Think, then click! If our list is 1 million items, we need 1 million additional stack frames! Each stack frame has to store a decent amount of information (more information than a single integer element). This is substantially worse than an imperative implementation, that would just keep around a variable for the current max. For example, in Python: ``` def list_max(xs): curr = xs[0] for x in xs[1:]: if x > curr: curr = x return curr ``` ::: Can we make the functional, recursive version as efficient as the imperative version? Yes, if our language has a feature called *tail call optimization*, which Racket has! This is the ==language-level optimization== we'll cover in the rest of this class. To build up to this optimization, we'll use a trick we see more of as we go forward in this class: we'll add additional arguments to a recursive helper to track additional context. Often, this will be in an _accumulator_ style pattern. In the most efficient version of our `list-max` function, the key insight is that we can build a final result here by _starting_ at the beginning of the list (the input argument), rather than starting to build our result at at the base case with the base result. The _accumulator pattern_ lets us do just what we need here: we add an additional argument to the recursive function to track an _accumulator_ that grows (or represent more work) conceptually as the stack _grows_ (rather than as the stack shrinks). The accumulator starts simple at the first stack frame, and then includes more work as we recur and grow the stack. The base case can then just return the final accumulated result! We'll first show the accumulator pattern with an additional function: ```racket ;; With the accumulator pattern and tail recursion ;; Note we name the accumulator max-so-far (define (helper xs max-so-far) ; Note: here we'll update the base condition to check for empty (if (empty? xs) max-so-far (helper (rest xs) (max max-so-far (first xs))))) ; We still have the goal of writing a function with a ; single argument: it will wrap our helper, passing the ; right initial accumulator value (define (max-acc xs) (helper xs (first xs))) ``` We can conceptualize the accumulator pattern like this: ``` Accumulator pattern stack grows argument shrinks accumulator grows ↓ ↓↓↓↓ ↓ ↑↑↑↑↑ ↓ ↓↓↓ ↓↓ ↑↑↑↑↑ ↓ ↓↓ ↓↓↓ ↑↑↑↑↑ ↓ ↓ ↓↓↓↓ ↑↑↑↑↑ return ↓ base case final result final result ``` In the accumulator pattern, by the time we reach the base case, we *already have the final result*! For `max-acc`, this allows use to gain additional efficiency in terms of _space_, because of how Racket handles the stack frames themselves! This ==language-level optimization== is called **tail call optimization**. ## Tail recursion To understand this optimization, let's drawn the recursive stack for our `helper` with its accumulator: ``` View of the function call stack (grows downward) Efficient, *tail* recursion --------------------------------- | helper | | xs = '(1 3 2) ; first is 1 | | max-so-far = 1 | | return result of recursion | --------------------------------- | helper | | xs = '(3 2) ; first is 3 | | max-so-far = 1 | | return result of recursion | --------------------------------- | helper | | xs = '(2) ; first is 2 | | max-so-far = 3 | | return result of recursion | --------------------------------- | helper | | xs = '() | | max-so-far = 3 | | returns 3 | <- Base case, return max-so-far (accumulator) --------------------------------- ``` Notice that while we need an additional argument binding to track `max-so-far`, each stack frame no longer needs to track the context of needing to do addition work with the result of the recursive call (for `helper`, taking the pair-wise `max` between the `max-so-far` and the first element of the current list argument). Put another way: once each frame delegates work to a recursive call, the **only** bit of work it has left to do is pass the return result up! This is the key insight behind **tail call optimization**, which is an essential optimization for making functional programming efficient! In this optimization, the language implementation (the interpreter or the compiler, which we'll explore more as the semester goes on) _does not actually build new stack frames_. Instead, when a function is _tail recursive_, the implementation ==reuses the same stack frame== (just updating the arguments of each call). This makes a tail recursive function more similar to a loop with an accumulator in an imperative language. :::info :star: Student question: isn't this just imperative programming with more steps? Answer: in a sense, yes, but it allows us to write more concise functional code that is easier to analyze and arguably harder to "mess up"! At least for functional programmer fans, this is the "best of both worlds": clean functional style with loop-like efficiency. ::: Implementations of languages that encourage functional style programming all typically implement tail call optimization: Racket, OCaml, (usually) Rust, etc. Other languages, such as Java and C, do not necessarily have tail call optimizations implemented, though some compilers can choose to implement it. ## Tail position What makes a specific function tail recursive, such that we can apply this optimization? _Tail_ recursion is when the recursive call happens in the _tail_ position of the function. We can define the _tail_ position recursively: Tail position? - In `(define (f x1...xn) e)` or `(let (...) e)`, `e` is in the tail positions. - In `(if e1 e2 e3)`, `e2` and `e3` are in tail positions. - In `(cond (c1 e1) (c2 e2) (c3 e3))`, `e1`, `e2`, and `e3` are in tail positions. Counterexamples: - In `(+ 1 e)`, `e` is **not** in the tail position. - In `(if e1 e2 e3)`, `e1` is **not** in the tail position. Intuitively, a function definition is tail recursive if the recursive function call is the ==last thing that happens in the dynamic execution of the function==. --- # Group exercise Write a tail-recursive factorial using this common syntactic transformation: ```racket ; Common syntactic transformation to convert to tail call: ; - Add helper w/ an extra accumulator arg ; - Identify initial accumulator (prior base result becomes initial acc) ; - The base case returns the accumulator. ; - Recursive case calls in the tail position, applies to accumulator. (define (fact n) (if (= n 0) 1 (* n (fact (- n 1))))) ``` :::spoiler Think, then click! ```racket ; Tail-recursive factorial (define (fact-tail n) (letrec ((helper (lambda (n acc) (if (= n 0) acc (helper (- n 1) (* n acc)))))) (helper n 1))) ``` Note that here, we use the `letrec` form to refer to the identifier `helper` in its own definition! ::: A few important points: - This common syntactic transformation works when the operator we are applying to the accumulator is _commutative_. - When the operator is not commutative, we can still convert some functions to use efficient tail recursion via switching the function we are applying (often, to work in a different order). - A2: Functions will have more musing on this point. - While tail recursive functions usually use the accumulator pattern, not all functions that use an accumulator are tail recursive. We can use `letrec` to further clean up our list `max`, since the helper will never be used outside of the function. Note that combining `let` and recursion can be tricky: can a local binding refer to itself? `let` itself cannot, but another form can! Racket has another local binding construct for this reason: `letrec`. ```racket (define (max-acc xs) (letrec ([helper (lambda (xs max-so-far) (if (empty? xs) max-so-far (helper (rest xs) (max max-so-far (first xs)))))]) (helper xs (first xs)))) ``` # Tail recursive `reverse` :::warning We didn't get to these examples in Monday's class, but they may be useful in solving problem 9 on A1: Values. We'll talk more about this Thursday, but in the meantime, feel free to read ahead. ::: Next, we'll consider a case where rather than just being a *syntactic conversion* that improves space efficiency, we can use tail recursion to also change the *time efficiency* of a function. Let's consider writing a recursive function to `reverse` a list. ```racket (define (reverse lst) (if (empty? lst) empty (append (reverse (rest lst)) (list (first lst))))) ``` Unfortunately, while this implementation is straightforward to write, it's again too inefficient. :::success What's the `O(...)` **runtime** for this `reverse` for a list of length `n`? ::: Well, as we saw when we implemented `my-append`, `append` needs to recur through the length of its first argument. We are calling `append` on every call. If a list has 1,000 items, then in the first call we pass append a first arg with length 999, then the second call on with length 998, and so on... this is $O(n^2)$! We should be able to reverse a list in _linear_ time. We can instead use tail recursion: ```racket (define (reverse lst) (letrec ((helper (lambda (lst acc) (if (empty? lst) acc (helper (rest lst) (cons (first lst) acc)))))) (helper lst empty))) ``` - Helper uses an accumulator (acc) to store the reversed list. - To combine the current element with the acc, we still need to put the current element at the start of the list. However, since we now know the thing we're putting first is one element, we can use `cons` instead of `append`! We can now build the new list one `cons` cell at a time (cheap! constant time!) The intuition behind this implementation is that `helper` takes two arguments: the list itself, which shrinks on every recursive call, and a new argument for the accumulator `acc`, which starts empty and grows on each recursive call. The base case of the recursion can then just return the `acc`, which has accumulated the fully reversed list by the time we get to the end. # Testing with RackUnit In CS251, we are very concerned with the *meanings* of programs. This means we spend a lot of time thinking about expected outputs. So far, we've been checking for expected outputs by viewing results in the interaction pane, but this is somewhat tedious as we get to larger examples. :::success What would a better solution be? ::: Test cases! *Unit test* is a term across programming languages: it means a test for an isolated behavior of a piece of code ("unit" implying to test one unit). Moving forward, we'll use unit tests in Racket to check for expected behaviors. This is a very generalizable skill across different programming languages. Specifically, we'll use [RackUnit](https://docs.racket-lang.org/rackunit/). I encourage you to use this for A1: Values, and testing will be a larger component of future assignments moving forward (A2: Functions on). ```racket ; Use the unit testing library RackUnit (require rackunit) ; Our function-under-test (define (f x) (cons x empty)) ; check-equal? checks for equivalent values (check-equal? (f 0) '(0)) ; succeeds ; check-eq? check for identical values (the same heap location) ; This matters for cons cells, but not always for literals ;(check-eq? (f 0) '(0)) ; fails, copy of cons cell ; For functions that return booleans, good style to use: (check-true (odd? (first (f 1)))) (check-false (odd? (first (f 2)))) ``` :::warning - Moving forward, I encourage you to use tests over commented-out interaction code! :::