Lab 6 Spot The Difference

Purpose: To practice abstracting similarities in functions and data.

Quote, Unquote, Quasiquote, and List

Exercise 1 Write the following expressions using only cons and '() (in other words, don’t use list or quote):

• (cons (list 1 2) (list 3 4))

• '((make-posn 5 6) 4 "a" b)

• `(a b c ,(+ 1 2) '(a b c (+ 1 2)))

Check your answers with a staff member before moving on to the next section.

Following the template

Following the correct template is an important part of designing clean, readable code. Contrary to popular opinion we don’t make you write templates to make your life more difficult. Writing proper templates and using them correctly will actually make it much easier to write code that is functionally correct as well as code that is easier to debug and change at a later date.

Consider the following data definitions:

; An AddressBook is one of:

; - '()

; - (cons Record AddressBook)

(define-struct record [first last phone add])

; A Record is a (make-record String String Nat Address)

; - where first is the first name of the person this record is about

; - last is the last name of the person this record is about

; - phone is the phone number of the person this record is about

; - and add is the address of the person this record is about

(define-struct address [num st city state zip])

; An Address is a (make-address Nat String String String Zip)

; - where num is the street number of the address

; - st is the street name of the address

; - city is the name of the city this address is in

; - state is the name of the state this address is in

; - and zip is the zipcode of the city this address is in

(define-struct zipcode [a b c d e])

; A Zip is a (make-zipcode Digit Digit Digit Digit Digit)

; - where a is the first digit in the zipcode

; - b is the second digit in the zipcode

; - c is the third digit in the zipcode

; - d is the fourth digit in the zipcode

; - and e is the fifth digit in the zipcode

; A Digit is a Nat in the range [0,9]

Exercise 2 Write the templates for the above data definitions. How many templates will you need? Remember to ask yourself the questions on the design recipe page of the course website. These will guide you to the correct templates.

Exercise 3 Define some examples of each of the above data definitions (these will come in handy when you write functions that take in these types of data).

Exercise 4 Design the function update-zip-for-all which takes an AddressBook and a Digit and returns an AddressBook where each address in the list has had the last digit of its zip code changed to the given digit. How many functions will you need? HINT: How many templates did you write in the previous exercise?

Consider the following data definitions:

(define-struct snake [segments dir])

; A Snake is a (make-snake ListOfSegs Direction)

; - where segments is the list of segments of the snake

; - and dir is the direction the snake is going

; A ListOfSegs is one of:

; - '()

; - (cons Segment ListOfSegs)

; A Segment is a (make-posn Number Number)

; - where x is the x-coordinate of the segment

; - and y is the y-coordinate of the segment

; A Direction is one of:

; - 'up

; - 'down

; - 'left

; - 'right

Exercise 5 Write the templates for the above data definitions. How many templates will you need? Remember to ask yourself the questions on the design recipe page of the course website. These will guide you to the correct templates.

Exercise 6 Define some examples of each of the above data definitions (these will come in handy when you write functions that take in these types of data).

Exercise 7 Design the function shift-snake which takes in a Snake and shifts every segment in the direction it is going. Note that this is different from how we moved the snake in lecture. We are not just adding a new head and popping off the last element. We are shifting EVERY segment in the given direction. How many functions will you need? HINT: How many templates did you write in the previous exercise? Remember that you can write helper functions that take in more than one argument.

Abstracting Functions

Exercise 8 Design the function move-posn-up which takes in a Posn and produces a Posn with the same x-coordinate but with a y-coordinate that is 1 less than the input Posn.

Exercise 9 Design the function move-posn-down which takes in a Posn and produces a Posn with the same x-coordinate but with a y-coordinate that is 1 more than the input Posn.

Exercise 10 Abstract move-posn-up and move-posn-down into one function named move-posn-y. Remember to follow the steps outlined above and don’t forget to redefine your previous functions using your abstraction.

Exercise 11 Design the function prefix-with-hello which takes in a ListOfStrings and prefixes each string in the list with "hello". As a reminder the data definition for a ListOfStrings has been provided below.

; A ListOfStrings is one of:

; - '()

; - (cons String ListOfStrings)

Exercise 12 Design the function prefix-with-goodbye which takes in a ListOfStrings and prefixes each string in the list with "goodbye".

Exercise 13 Abstract prefix-with-hello and prefix-with-goodbye into one function named prefix-with. Remember to follow the steps outlined above and don’t forget to redefine your previous functions using your abstraction.

Functions in Functions

Exercise 14 Design the function all-smaller? which takes a list of numbers and a number and returns a Boolean indicating whether every number in the list is smaller than the given number.

Exercise 15 Design the function all-bigger? which takes a list of numbers and a number and returns a Boolean indicating whether every number in the list is biger than the given number.

Exercise 16 Abstract all-smaller? and all-bigger? into one function named all-compare?. Remember to follow the steps outlined above and don’t forget to redefine your previous functions using your abstraction.

Exercise 17 Design the function any-smaller? which takes a list of numbers and a number and returns a Boolean indicating whether at least one number in the list is smaller than the given number.

Exercise 18 Abstract any-smaller? and all-compare?. Remember to follow the steps outlined above and don’t forget to redefine your previous functions using your abstraction. WARNING: The boolean operators and and or are not quite functions (they are macros which are something we don’t cover in this course) so you will have to define your own boolean operators if you want to pass them into your function.

Abstracting Data

Just like functions, we can abstract data definitions to avoid writing duplicate code. Here’s an example:

; A ListOfStrings is one of:

; - '()

; - (cons String ListOfStrings)

; A ListOfNumbers is one of:

; - '()

; - (cons Number ListOfNumbers)

These two data definitions are remarkably similar. Aren’t you tired of writing list data definitions all over the place? Let’s abstract! We will follow many of the same steps as we do when abstracting functions.

Step 1: Spot the differences

Step 2: Make the differences parameters

To abstract we take out these differences and make them "parameters" to our data definition. We call this abstracted data definition a parametric data definition and we denote it with square brackets to show that we need to plug in a value for the parameter.

; A [ListOf X] is one of:

; - '()

; - (cons X [ListOf X])

Step 3: Rewrite the old data definitions

Now we can rewrite our old data definitions in a much more concise way by plugging in the appropriate value for X (the "parameter" of our data definition).

; A ListOfStrings is a [ListOf String]

; A ListOfNumbers is a [ListOf Number]

Now you try! Consider the following data definitions:

; A MaybeNumber is one of:

; - #false

; - Number

; A MaybePosn is one of:

; - #false

; - Posn

Exercise 19 Abstract MaybeNumber and MaybePosn into one data definition. Don’t forget to rewrite the old data definitions using your abstraction.

Let’s do it again! Here’s some more data definitions:

(define-struct thing [a b c])

; A StringThing is a (make-thing String Number String)

; A SymbolThing is a (make-thing Symbol String Symbol)

Exercise 20 Abstract StringThing and SymbolThing into one data definition. BEWARE: There is more than one difference here! Don’t forget to make ALL the differences parameters of your abstracted data definition. Give the parameters different names because if they are all named X you won’t know which is which (and neither will we).