Introduction to Systematic Programming – Part 5

originally authored by dara monasch

in the event that you're just joining in, here's a guide to the rest of this series:

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

week 5 was an interesting mix of things i’ve learned in other programming classes/languages, and a strange bit of new items. we learned about arbitrary sized data, as well as working off of a list. i apologize for the delay in posting this week, but i was off in bermuda on vacation, so i wasn’t doing much work. ;)

lesson 1: intro to arbitrary sized data

the data we’ve been working with up until now in the course has been of a fixed size. arbitrary sized data represents data that is of an unknown amount, or something we just don’t know up front when we’re creating the program or function.

lesson 2: list mechanisms

the biggest question i had when we started talking about another data type was… how are we going to represent this one? the answer is that while you can use a compound data definition to represent arbitrary sized data, it is much easier to use… a list!

in dr. racket, lists are a primitive data type, in which “empty” is an empty list of anything. an example of this would be: (cons empty). for a list of one element, you would see (cons “flames” empty), where “flames” is the first element, and the rest of the list is empty. for a list of two elements, we would see (cons “leaves” (cons “flames” empty)) where leaves would be the first element, flames the second, and the rest of the list would remain empty.

this format of writing lists is referred to as “cons notation” where list values are formed only of values, not expressions. these values can be strings, images, numbers, naturals, anything except an expression.

the next question i would have, and i’m sure you do too, is how do you name your list?

it’s pretty intuitive, and you express it simply, as follows: (define list1 (cons “flames” empty)).

ok, so great. we can make these thrilling lists of arbitrary size… but how do we access the data once the list is created? again, pretty easy and intuitive!

(first list1) will give you the first item in your list

(rest list1) will give you the rest of your list

that’s all you need, right? … ok, ok, maybe you want to get the “rest” of the items separately? perhaps? that’s a bit more convoluted, unfortunately. here goes…

(first (rest list1)) will give you the second element in the list

(first (rest (rest list1))) will give you the third element

and so on and so forth.

you can also check if your list is empty with the following boolean expression:

(empty? list1)

lesson 3: a first list data definition

in order to iterate through arbitrary long lists, it’s important to understand the idea of recursion, or in this case, as the course presents it, “self-reference.” what frustrates me in this lesson of introduction to systematic programming, is that there is, in essence, no explanation of recursion or why it works, it’s just said multiple times to “trust the self-reference”. that’s very difficult for me to swallow because i don’t believe in working that way, but that’s all we’re given here, so that’s what i’m going to have to go with. here’s an example of a self-reference list definition in dr. racket:

;;listofstring is one of:
;; empty (this is the base case)
;; (cons string listofstring)
;; interp. as a list of strings

(define los1 empty)
(define los2 (cons “mcgill” empty))

#; (define fn-for-los los)
(cons [(empty? los) (…)))
[else
… (first los) ;string
(fn-for-los (rest los))])) ;listofstring (you’re “trusting the self-reference” here)

aaannnnddd that’s all you get from lesson 3!

lesson 4: a first function operating on list

please follow along with this as a continuation with the listofstring example from lesson 3

;;listofstring -> boolean
;;produces true if los includes “ubc”
(define (contains-ubc? los) false) ;stub
(check-expect (contains-ubc? empty) false)
(check-expect (contains-ubc? (cons “mcgill” empty)) false)
(check-expect (contains-ubc? (cons “ubc” empty) true)
(check-expect (contains-ubc? (cons “mcgill” (cons “ubc” empty))) true)

it’s important to note that the check-expects for this half-explained function check the base case of the list, which is empty, another false case, a case in which the first value is true, and also one in which the true value is embedded within other values in the list.

lesson 5: revising the recipe for lists

this lesson is really a compilation of quick tips relating to lists, so we’ll treat it as such here for clarity’s sake…

1. arbitrary is not random, it simply means the amount is unknown at the onset of program creation.
2. self-reference is necessary in order to review arbitrary amounts
   1. you also must need a base case, which is detailed on the “data definitions” page for lists
   2. examples should include your base case, and your self-reference cases, as i mentioned in the last lesson.
   3. when writing your template rules, the appropriate addition when using a list is “self-reference (rest los) is listofstring”, as a general example.
   4. again, it’s reiterated about 43 times in this lesson to simply “trust the natural recursion”. so… do that.

lesson 6: designing with lists

this lesson walks the class through an example pattern for working through lists, aka, a practice problem!

;;data definitions
listofnumber is one of
- empty
- (cons number listofnumber)
;;interp. each # as an owl weight in oz
(define (lon1 empty)
(define lon2 (cons 60 (cons 42 empty)))
#; (define fn-for-lon lon)
[cons [(empty? lon)(…)]
[else
(…(first lon
(fn-for-lon rest lon))]))

;;templates list

-  one of 2 cases
-  atomic distinct: empty
-  compound: (cons number listofnumber)
-  self-reference: (rest lon) is listofnumber

;;functions
;;listofnumber -> number
;;produce sum (weight of owls) in a consumed list
(check-expect (sum empty) 0)
(check-expect (sum (cons 60 empty)) (+60 0))
(check-expect (sum (cons 60 (cons 42 empty) (+ 60 (+ 42 0)))

when you’re working with the natural self-reference, a tip that’s given at this point is to “think about what to do with the result of the natural recursion, not the rest of this list”. in this way, you can kind of blind yourself to how the recursion works, and simply focus on what to do with the result it produces. again, i don’t really like or agree with this method of teaching recursion, but i suppose it serves its purpose here.

lesson 7: position in list templates

this lesson solely exists in order to provide the following table that you can use to compute the results or holes in your recursive functions.

lesson 8: the reference rule part 1

arbitrary data allows us to handle data that has different kinds of related parts… as with two data definitions. what does this mean? it means that not only can you have primitive items as your list elements, you can also have structs, which hold more than one value within them. this is understood as a “reference relationship”, which refers to a non-primitive data type, which is defined *within the program*. you can utilize these data types with reference: (first los). this produces a “natural helper”.

lesson 9: the reference rule part 2

this lesson was a short example on why it’s important to create your examples before your data definitions. the reasoning behind this is that your examples will help you write your functions and data definitions more quickly and easily!

lesson 10: the reference rule part 3

this lesson delves deeper into the idea of a natural helper. natural helpers in your templates mean that you should take the complicated portion of the function you’re creating, and move it to a separate, helper function. that’s it! the main point here is… make things less complicated, not more!

lesson 11: natural numbers

did you know that there are an arbitrary number of natural numbers? yeah, i never thought about that either, but it’s true!

this means that you can….

add1 - which is a function that takes a natural number and adds 1 to it

sub1 - which is a function that takes a natural number and takes one from it

basically you can step up or down with natural numbers, using these simple functions, without having to write your own!

week 5 summary

this week truly isn’t so bad. the worst part is the fake learning of recursion, which, while it annoys me, it’s not so difficult the way it’s being presented here. we’re learning to make lists of things and traverse/access them, which, truly, is very useful!