Introduction to Systematic Programming – Week 6

Previous Series Links:

Intro to “Introduction to Systematic Programming” Course

Introduction to Systematic Programming – Week 1

Introduction to Systematic Programming - Week 2

Introduction to Systematic Programming - Week 3

Introduction to Systematic Programming - Week 4

Introduction to Systematic Programming - Week 5

Week 6 is definitely when I’m starting to feel the burnout of MOOC. It seems to happen in all of my classes around now – I’ve been plugging along dutifully, but without the “pressure” of assigned class times, a professor checking in on my work, classmates who I converse with, I always seem to struggle about a month and a half into my online courses. Never fear, though, I made it through week 6 and I’m bringing to you, as always a thorough summary! Week 6 in Introduction to Systematic Program Design addresses the idea of Mutual Reference… Here we go!

Lesson 1: More Helpers & Mutual Helpers

At the start of this lesson, we’re reminded that the purpose of the HtDF recipe is to break your large, seemingly insurmountable problems down into smaller more manageable ones. This reminder makes more sense a moment later, because this week will explain how to not only break down problems, but datatypes and functions as well! The course instructor explains that although previously in the course we have always kept datatypes and functions whole, in week 6 we’re going to learn how to break them up, similar to how we’ve broken up all of our problems. We’re also informed that we’ll be learning a new kind of arbitrary sized data that is complete with its own integrated helpers.

Lesson 2: More Helpers – Function Composition

This lesson begins a large practice problem that spans several lessons – for that reason, my notes are a bit sparse here, because detailing every step of the practice problem just seems a touch redundant and uninteresting. ;)

In respect to the concept from Lesson 1 regarding breaking a function into multiple parts, this is a perfect example. When you consider a problem as broken down into smaller, internal problems, this is what’s known in HtDF as a Function Composition Problem (aka when there are two distinct operations on the data that is to be consumed). Apparently, this is incredibly easy to achieve, because, you guessed it, there’s a template for that! Racket has a Function Composition Template, which lesson 2 then walks us through the use of. Here’s a quick example: (define (arrange-images loi) (layout-images (sort-images loi)))

As you can see in the above, there are two functions built into one definition. After writing the definition, as always, we’re instructed to write our wish-list entries so nothing is forgotten. J

Lesson 3: Laying Out a List of Images

This lesson continues the example from the previous lesson. The most important thing that’s reviewed in this lesson is to make sure that your MATCHING check-expects pass after you write your function. Note: If the check-expects from an incomplete function fail.

Lesson 4: More Helpers – Operating on a List

Again, one nice and short tidbit from this lesson!

In the case of coding a function, when you need to operate on a list, you need to create a new helper function.

Yep, that’s it for lesson 4!

Lesson 5: More Helpers – Domain Knowledge Shift

This lesson has a very interesting focus – shifting knowledge areas in the midst of programming in Racket requires that you create helper functions. I know, what?! Let’s try this: “When changing from sorting images to comparing the size of an image, this is a domain knowledge shift.” So, in essence, when you’re doing something DIFFERENT with the items in your list, you make a new function. Granted, this is one of my least favorite things about this course, because I feel that it results in lots and lots of extra code, that could be more… compact?, I do understand that it breaks out the logic of programming and makes it easier for beginners. (Did I just say that? Does that mean I’m not a beginner anymore? Gosh I hope not! Haha.)

Additional Notes:

-          If you use an item repeatedly for testing, just make it a constant! It’s easier and helps avoid mistakes.

Lesson 6: More Helpers – Wrap Up

In theory, this is where the magic of helpers happens. Once you write your last helper function and run your code, all of your tests should magically pass, because your original function was just waiting for the helpers to be written!

No?

Well, then you should check your tests for mistakes first, because you might simply have a typo. If that’s not the issue, well, then, you have to debug your functions.

Also! Since this is the end of the “first half” of Week 6, there were some small wrap-up notes:

1. Remember all of these new helper rules that we learned this week! We’ll need them for later.
2. Don’t be afraid to utilize Macro Notion – Split work from main functions using helper rules and make your life easier!!

Lesson 7: List Abbreviations

I. Loved. This. Lesson.

Seriously, list writing in Racket so far has been an abomination! In this lesson, we’re instructed to move our language definition in Dr. Racket from “Basic Student Language” to “Basic Student Language with List Abbreviations.” Thank. Goodness.

What this means as far as programming is that when you write a list, you don’t need cons anymore!! Lists will now make sense!!! When writing a list, it can now be composed as such: (list “a” “b” “c”). SCORE!

However, it’s important to note that you still *can* use cons, and in some cases, it will make more sense. If you’re adding to a list, for example, you would still want to say:

(define L1 (list “b” “c”))
(cons “a” L1)

In order to produce: (list “a” “b” “c”).

The reason for this is if you try and use append, you need to input two LISTS, which will then produce one list with the elements of both of them.

Lesson 8: Mutually Recursive Data

Mutually recursive data is defined in Racket as data with two cycles in the type comment. This type is known as an arbitrary arity tree, as all of the elements are able to also contain sub-elements. This arbitrary quality means that the elements can be both arbitrary in both elements extending through width and height. Here’s an example of what I’m talking about:

In Racket, when building an arbitrary arity tree, you use…. Lists! (Shocking, right?)

For example, going from description of element to ListOfElement (cycle) is a mutual reference, which can be understood as an “arbitrary” cycle. So, when you go through a reference cycle, and the arrows return to the place where the reference cycle began, this is known as a “mutual reference,” because they point back to one another!

Lesson 9: Templating Mutual Recursion

One major tip here and that’s it!

Write your templates for mutually recursive datatypes together when writing your program. Why? It’s easier! Plain and simple. J

Lesson 10: Functions on Mutually Recursive Data – Part 1

When there are 2+ functions that operate on mutually recusirve data, you shouldn’t only write them together, but write them all right away, with the same examples, signature, and purpose!

Here’s an example:

(define (sum-data—element e) 0)
(define (sum-data—loe loe) 0)

When you’re doing this… don’t forget your base case examples and also remember to rename all of your mutually recursive and self-referencing calls right away. Both of these items will save you a *ton* of headache and heartache later. Promise.

Again… as always… REMEMBER TO TRUST THE NATURAL RECURSION.

Lesson 11: Functions on Mutually Recursive Data – Part 2

Two big takeaways here:

1. Your base case is where you reference cycles stop. (I thought this was very poignant, I didn’t ever think about it this way before, but it’s so true!)
2. Beware of naming conventions with two functions. Be clear and STAY ORGANIZED.

Lesson 12: Backtracking Search

Here’s one last function for the week using arbitrary arity trees…. Backtracking search!

What is that? It’s when you search a tree for an element with a given value/name. It’s important to remember here that the leaves of the tree are searched AFTER the ones above, so they’re  found “in” their parents. Backtracking search comes into play here because if you get to the end of a branch in your tree and don’t find the element you’re looking for (known as a “failing leaf”), you have to traverse BACK UP in the tree in order to go down a different branch, you can’t just jump around. This repeats through navigation of the entire tree, until you run out of branches and leaves!

Week 6 Summary

This week was ALL over the place, and as I mentioned, a hard one for me to simply get through. However, I think that overall the concepts are definitely manageable, and I’m looking forward to the last two weeks of class. Wish me luck!!

Questions/Comments?

Feel free to comment here on my blog, or find me on Twitter @DokiDara.

By Dara Monasch