CPSC 110: Weeks 9 and 10.

Introduction

Last week, I think I predicted that these couple weeks would be some of the hardest so far in the course, and I think I wasn’t far off. The lab and problem set for week 9 were especially difficult - it seemed to be very much a ‘it’s a matter of thinking’ type of problem. Generative search and this type of recursion are techniques I haven’t even touched outside of Racket, so I think the lack of experience definitely didn’t help, as well as my not understanding the problem half the time. Week 10’s work wasn’t much better - I’m still working through the lab and problem set as of now. However, I feel like Week 10 ‘clicks’ more than Week 9, but maybe that’s just because Week 9 had a large problem example instead of smaller, more digestible ones. However, going through the practise problems and solutions has been helping, and I’ve really learned that you cannot rush it - taking my time to work through problems fully has been a lot more helpful than trying to speedrun a couple easy check-expect cases.

As with every other CPSC 110 post, if you’re not doing the course or don’t have the very niche interest of tackling aforementioned generative recursion and accumulators, this is the part where you might want to go read one of my other posts. I promise there’s some interesting thoughts somewhere in my post history, so feel free to go check those out instead.

Notes - Week 9

This week covers generative recursion, and applies it to backtracking search, a method of search that generates all possible permutations of a problem in a tree before eliminating invalid ones.

• generative recursion differs from previous structural recursion => instead of taking a sub-piece of data as argument to next call, we now generate entirely new data to call
  • fractals are a good example of this => layering images onto each other
• use the HtDF recipe for generative recursion => instead of an empty case, we have a trivial case and a non-trivial generative case
  • generally nest images around other recursive cases, instead of only having a recursive expression
  • base case for generative recursive check-expect is the case that doesn’t recurse anymore => set a cutoff constant
    • next ones can be those that do recurse (generally one or two ‘steps’)
  • can use locals to avoid redundant competition (i.e. when multiple recursive areas or multiple of the same nonrecursive cases)
  • can re-call the recursive function => make sure to operate on the arguments (generally for side length)
• can’t count on type comment rules to determine that the recursion will end => halting problem
  • need to use our own proofs: three-part system of base case, reduction steps, and halting or termination argument
    • base case is the trivial question expression in the cond
    • reduction step is the, well, reduction of the expression argument
    • then use logic to state an argument that repeating the reduction will eventually reach the base case
• use lambda (λ) expressions to avoid having to create a whole local function => anonymous function
  • only use in place of expressions that will only be used once => like Python lambdas
  • ensure the body is easily understood and that the naming adds nothing to its comprehension
  • format: (λ (n) (> n 5)) where the n expression is the list of other expressions
• backtracking search is composed of several parts => structural recursion for the tree structure, and handling function composition
  • use the HtDF backtracking search template => use local functions to nest all required functions in a single expression
  • two main parts => the ’trivial’ or success case, and the subs, or the descendents case
  • descendents generally requires a couple helper functions => break the problem down into several smaller steps to solve with function composition, abstract builtins, or other methods

Notes - Week 10

Week 10 deels with accumulators, a new technique used to preserve context that’s often lost in recursive functions.

• structural recursion templates are very powerful => easy to abstract upon
  • however, cannot see ‘where’ they are in a data structure
  • cannot preserve past-touched data, or accumulate data to add to future computations
• context preserving accumulator => brings data from parent/child or keeps track of other values that need to stay constant within a sub-traversal
  • wrap the function body in a local expression and add a trampoline with a base accumulator
  • add an argument to the inner functions
  • the context preserving accumulator changes every step depending on the fn behaviour
  • add parameter to where it might be used in a function
• also introduces the concept of tail recursion => any recursion placed in the last expression position in function, not wrapped in anything
  • reduces the problem where many sub-expressions are created before reducing the answer
  • optimized in many languages, including Racket
  • instead of a context-preserving accumulator, now a result-so-far accumulator is introduced
    • represents the built-up information (such as the sum function)
    • generally used to produce tail-recursive functions instead of cons-ing infinitely
• third accumulator type is the worklist, where you consistently build onto a list that’s called each function iteration
  • run the mutually recursive list function on the todo worklist instead
    • take the first of the worklist and operate on it, then if using another accumulator attach to that
  • used often when operating on data with more than one graph cycle => arbitrary arity trees with tail-recursion
• general accumulator advice
  • when writing accumulators, ensure a base accumulator is set in the trampoline => empty, 0, depends on function behaviour
  • to debug accumulators, draw out an example of a call tree including the arguments and how they’re expected to be operated on

Conclusion

Only a couple modules left - though those might take a while to get through, given that they’re the last, and probably most difficult sections of the entire course. I foresee a lot of cross-module work, as well as more complex program design. I’m looking forward to tackling it, but a bit hesitant to find out what ‘graphs’ and ‘mutation’ are supposed to mean¹. I’m still on track to finishing CPSC 110 well before summer break, but I think I might have to take things a little slower given with how school’s going. Perhaps more consistent but less intense work with the course will be more effective, anyways?

I haven’t found the time to write a proper post in a while, but I think it’s high time I went back to more regular posts - I have a list of pretty viable ideas that I’d like to expand more on, and maybe a couple addendums and things to other posts that I might update. YK was started as half a joke, but I think it’s become more a place to swirl thoughts together and hypothesize about the very niche things I’m into. I don’t think my posting style’d fit in more micro-blog formats, so I plan on continuing to tend this digital garden (hey, am I trendy now?) for a very long time - and that means keeping my consistently posting schedule. I got a bit lax in the past month - while my very rigid posting schedule maybe wasn’t the best for quality in 2020, it did incentivize me to stick to it, and at least put something out. Anyways, I hope I’ll manage to edit up my latest post and have it up soon, and follow it up with a bunch of other thoughtchains. We’ll see².