CPSC 110: Weeks 7 and 8.

Introduction

A couple weeks ago, I predicted that my CPSC 110 sprint was probably going to peter out, and would you look at that - I was somewhat right. A combination of school restarting, lots of homework to catch up on, and a general procrastination of writing anything all led to me sort of conveniently forgetting to go through a couple videos a day. It was also convenient that these couple of modules are starting to pick up in difficulty, and are generally the points where people start crying for help on the Piazza (or so I’ve been told). All in all, I’d definitely put off writing notes for the last few modules I’ve completed until today, so I suppose here’s a good place to start.

Local expressions and the section on one-of types were surprisingly comprehensible - I’ve always admired how systematically this course builds on past material, but I suppose there’s a reason why the course name is ‘Systematic Program Design’. Week 8’s module on built-in abstractions was also relatively easy to understand - drawing on past experience with similar functions and styles in Python and especially Javascript definitely helped.

I think I’ve said this something like five times before, but as always, you’ll probably be very confused and disinterested in the contents of this article unless you’re taking CPSC 110, or somehow have stumbled upon this in the interest of learning Racket (it’s an experience). I’ve put up the notes for the rest of the course up til this point in the posts preceding, so if you are indeed interested, check those out.

Notes - Week 7

Week 7 discusses two one-of types (the cross product table), and local expressions.

• when a function’s arguments have more than one type with one-of type comments, use cross product table to determine which cases to handle
  • design function based on model of function instead
  • create a table with the one of possibilities for type a horizontally, and possibilities for type b vertically
    • will have a box per case, which you can fill in with the desired behaviour for each case
    • often, can condense boxes that are next to each other and have the same behaviour (#t/#f cases)
    • collect into a (cond) expression
  • helps with determining what to test => at least one per case in the (cond)
• with more difficult behaviours => remember to keep natural recursion
  • even if this is a branching statement, keep in one (cond) QA pair
  • keep self-reference applying to the rest of the list (if it’s one)
• we’ve graduated to ISL => intermediate student language
  • one of its new feature is local expressions => function and variable definitions within a larger definition
• local expressions nest into another definition => (local [(define x a)] (expression))
  • any number of function or variable definitions are allowed => override any definitions outside of the local at top level
  • expression is evaluated to produce the result of the local
  • these local variables do not exist outside of the local => lexical scoping
    • definitions that exist at the top level are in the global scope
    • scope contours show where functions and variables are defined and redefined => like nesting boxes that only take the most specific one
    • definitions reference the innermost enclosing box => defaulting to top level
• to evaluate local functions, use a method of renaming and lifting
  • combining all the rules previously learned => first start by substituting variables outside local as normal
  • then rename all local’s references to a program-unique name
  • then lift the renamed definition into top level / global scope
  • then replace the local with a body expression
  • then replace any renamed definitions within the local with their values
• local expressions are used to encapsulate the ugly mutual reference functions, as well as prevent recomputing in recursive functions
  • encapsulation helps avoid practically, naming problems, and helps decomplicate the rest of the program
    • wrap the two mutually referential functions into a local definition, and run only one of the functions in the local expression (single)
    • delete all tests that reference the other definition (list), and rename the rest of the lists
    • can pre-encapsulate within the template, moving the same two function templates within a data definition’s template
  • in recursive functions, the time to evaluate a function rapidly increases => exponential
    • to avoid this, we wrap recursive function calls that are repeated in a local definition
    • look for the closest expression that wraps the function calls, and replace with pre-computed values => only compute these once, saving time
    • rename each of the function calls to the local definitions

Notes - Week 8

This week deals with using Racket’s built-in abstract functions and creating your own. (Starting to get into things that are more closely related to what you stereotypically think of as functional programming.)

• abstraction helps reduce the amount of repetition in code, especially from templates that are very similar to each other
  • use function definitions to plug into other generalized function => more abstract fns
• basic example of abstraction => take several functions that are very similar, and make one generalized function that takes only the differing points as arguments
  • because most functions are directly based off templates => not much change between functions if same types and signature
  • add the check-expects for each function to the generalized function check-expects
  • add each argument to the check-expects and each function
  • edit the body of each function to make a call to the generalized function with its specialized predicate / differing points
  • purpose can just generalize to the main function
  • called higher-order functions => fns that call other functions
• signature and type notation is now changing => type inference
  • look at each argument => if it’s a function that can apply to any types, instead of denoting the types that it uses, use abstract letters like X and Y
    • each function needs to be in parentheses => something like (X => Boolean)
  • look at argument functions that take in the same types, or produce the same types
  • also, can now use the (listof X) shorthand to avoid having to produce a data definition for the lists
• Racket also has a large number of built-in abstract functions:
  • check the type to input and the type to output, then find the corresponding function in the list below ⇓
  • build-list: Natural => (listof X)
  • filter: (listof X) => (listof X)
  • map: (listof X) => (listof Y)
  • andmap: (listof X) => Boolean
  • foldr (and foldl): (listof X) => Y
    • call with a function, a base case, and a list to operate on => similar to the list template
  • can use these to form larger functions without all the template work
• closures => when a function requires access to a parameter part of the larger function => use local
  • for example, in a function with arguments x and fn1, where fn1 needs access to x
  • only passes one argument => unlike writing your own fold function where you have to pass all arguments
• produce your own fold functions from the template => abstract with each base case and function argument as an argument
  • in functions that you pass, then have to specify with all arguments of struct members
  • forex: fn1 that operates on an image takes two arguments now, not one like in closures
  • generally compose your own local functions to use in the fold function
  • can check like most other functions => just copy paste the check-expects over, wrapping functions as needed in local expressions

Conclusion

As of writing this conclusion, I’ve actually managed to go through module 9 as well, so we’ll see if I can manage to publish those notes soon as well. I can definitely see the course starting to ramp up in difficulty, but I think the design problems are a nice challenge, aside from the mundanity that can sometimes be trying to write check-expects and follow templates to a T. As I look back on each module, I’m surprised to see how clear everything actually is - the first time round, everything certainly seemed a lot more difficult. I guess I’ve just found that it really is impossible to try to rush through things, even the dull humdrum of copy-pasting stubs and templates and such. I’m excited to see what the later couple weeks have in store, especially in terms of this magic they call ‘functional programming’.

I’m also looking forward to making some more good progress before summer break, and seeing when I can finish the bulk of the course. I have several more modules left, but after that, I think I can start devoting more time to completing more start-to-end problems and tackling the practise finals from past years. Hopefully, I’ll be able to finish up the course by June, though I genuinely don’t know what else’ll come up with school. I think I’ve generally settled on challenging in September instead of the summer, which should give me some more time to prepare, and might hopefully lift a bit of the courseload (if I do manage to pass the challenge) in my first semester. I think I’m well on track to this, and I’m happy to start applying some of the more fun theoretical techniques to problems.