Lab 5 Abstraction in functions and data

Purpose: The purpose of this lab is to get some more practice recognizing similarities in function definitions and in data definitions and how to avoid them.

Abstracting constants into parameters

When we solve problems, we sometimes find that the solution to one problem looks a lot like the solution to another one. Check out the following functions and data definition. From now on we will leave out the definition for lists, and use the [List-of X] notation.

; A [List-of Number] is one of

;  – empty

;  – (cons Number [List-of Number])

; lon-add2 : [List-of Number] -> [List-of Number]

; Add two (2) to each element of the given list of numbers

(define (lon-add2 lon)

(cond [(empty? lon) '()]

[(cons? lon) (cons (+ (first lon) 2)

(lon-add2 (rest lon)))]))

; lon-add5 : [List-of Number] -> [List-of Number]

; Add five (5) to each element of the given list of numbers

(define (lon-add5 lon)

(cond [(empty? lon) '()]

[(cons? lon) (cons (+ (first lon) 5)

(lon-add5 (rest lon)))]))

Is it clear what each function does? Since these functions are almost identical you are hopefully asking "Why would you do that?!".

Sample Problem Design a function named lon-add-n that abstracts both of the functions above by taking an extra argument, which is the number to be added to each element.

; lon-add-n : [List-of Number] Number -> [List-of Number]

; Add n to each element of the given list

(check-expect (lon-add-n '() 3) '())

(check-expect (lon-add-n (list 1 4 6 2) 1/2)

(list 1.5 4.5 6.5 2.5))

(define (lon-add-n lon n)

(cond [(empty? lon) '()]

[(cons? lon) (cons (+ (first lon) n)

(lon-add-n (rest lon) n))]))

Sample Problem Rewrite both lon-add2 and lon-add5 using your more general function. Write a few tests for each to be sure they still work as expected.

Exercise 1 Design a function named starts-with-cat that consumes a [List-of String] and constructs a list of all the strings that start with "cat". For example, (starts-with-cat (list "oboe" "cataract" "ox" "catharsis")) would produce (list "cataract" "catharsis").

Exercise 2 Design a function named starts-with-dog that consumes a [List-of String] and constructs a list of all the strings that start with "dog".

Exercise 3 Design a function named starts-with that abstracts both of the functions above, taking an extra argument, which is the substring to be found in each element.

Note: to avoid "index out of range" errors you might want to ensure the prefix is shorter than the string you are checking against.

Exercise 4 Rewrite both starts-with-cat and starts-with-dog using your more general function. Write a few tests for each to be sure they still work as expected.

Exercise 5 Design a function contains-cat? that consumes a [List-of String] and determines whether that list contains the string "cat".

Exercise 6 Design a function contains-dog? that consumes a [List-of String] and determines whether that list contains the string "dog".

Exercise 7 Design a function contains? that abstracts both of the functions above, taking an extra argument, which is the string to check for in the list.

Exercise 8 Rewrite both contains-cat? and contains-dog? using your more general function. Write a few tests for each to be sure they still work as expected.

Abstracting Code into Data

In this series of problems, we’re going to reconsider the Finite State Machine problem from Assignment 4a. We’re building up to HtDP Exercise 230, but using the particular state machine from the homework.

The code for implementing a finite state machine on the homework was frustratingly repetitive: the nested conditionals and the duplicated checks for string equality all meant that if you needed to change the state machine, you’d need to rewrite the function from scratch. Surely we can do better!

Consider again the description of a FSM: (1) it’s a bunch of states, together with (2) a collection of rules describing the transitions between states. When a key is pressed, we needed to (3) look up the relevant state, (4) look up the relevant transition for that state, and then (5) switch states accordingly. We have datatypes now that let us describe a "bunch" of things – lists. So let’s start with the following data definitions:

; A StateName is one of

; - "START"

; - "G"

; - "O1"

; - "O2"

; - "D"

(define-struct transition [key next-state])

; A Transition is a structure:

;   (make-transition KeyEvent StateName)

; INTERPRETATION: If the given key is pressed, switch to the given named state.

(define-struct fsm-state [name rules])

; A FSMState is a structure:

;   (make-fsm-state StateName [List-of Transition])

; INTERPRETATION: A single state of a finite-state machine,

; with a name and a list of applicable rules.

; A FSM is a [List-of FSMState]

; INTERPRETATION: A complete finite state machine, that

; switches states in reaction to keystrokes

(define-struct world [cur-state fsm])

; A World is a structure

;   (make-world StateName FSM)

; INTERPRETATION: The full information needed for our world program:

; the rules for the finite state machine, and the current state of the machine

Exercise 9 These data definitions give us (1) and (2) above. Represent the FSM from Assignment 4a using this data. Hint:

(define START-state (make-fsm-state "START" (list (make-transition "g" "G"))))

...

(define FSM (list START-state G-state O1-state O2-state D-state))

Explain in English how your data represents the same information as your code did for the homework.

Exercise 10 Design a function state=?, that returns a boolean indicating if two given state names are equal.

Exercise 11 Design the following function, which is step (3) above:

; find-transitions-for : FSM StateName -> [List-of Transition]

(define (find-transitions-for fsm state)

...)

This function looks for the given named state in the given FSM, and returns the [List-of Transition] associated with that state. If the state is not found, then error. (This function handles the outer cond from your homework’s code.)

Exercise 12 Design the following function, which is step (4) above:

; find-transition : [List-of Transition] KeyEvent StateName -> StateName

(define (find-transition transitions key default)

...)

This function looks for the given key-event in the given transition list. If it finds the key, it returns the associated state name. If the key is not found, then return the given default state name. (This handles the "all other keys" cases in the inner conds in your code from your homework.)

Exercise 13 Design the key-handler function

; handle-key : World KeyEvent -> World

(define (handle-key world key)

...)

This function should tear apart the World into its component StateName and FSM. It should then use find-transitions-for to find the current state’s transitions, use find-transition with the given KeyEvent to find the new state, and then build up a new World with the results.

Combine this function with your drawing functions from the homework (which you’ll need to tweak slightly, to take a World instead of a String) to complete the new FSM simulation.

(define (run-fsm initial-state)

(big-bang (make-world initial-state FSM)

[to-draw your-new-drawing-function]

[on-key handle-key]))

Before You Go...

If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.