Lab 17: Oobleck
Implement this lab with the Intermediate Student Language.
Make sure you follow The Style we use for the {B,I,A}SL{,+} languages in this class.
Choose the initial Head and Hands, and get started!
Royal Magicians
; A Shuffle is one of: ; - Duffle ; - Muzzle ; - Muff ; ; A Duffle is one of: ; - Number ; - String ; (define-struct muzzle-town ()) (define-struct muzzle-street (oobleck tumble down)) ; A Muzzle is one of: ; - (make-muzzle-town) ; - (make-muzzle-street String Shuffle Muzzle) ; ; A Muff is a [Listof Shuffle].
The interpretation is omitted intentionally. Since we don’t know anything about the meaning of this data, we must operate on Shuffles based on the structure alone. To do that, we’ll use templates.
If your partner hands you a Shuffle, you’ve got one of three things. To deal with that Shuffle, you need to know which of those three things you have! Any function you write has to know the same.
We can distinguish Muff from other Shuffles with list?. We can implement duffle? and muzzle? to succinctly distinguish Duffles from Muzzles.
Ex 1: Implement duffle? : Shuffle -> Boolean, which returns #true only if the given Shuffle is a Duffle.
Ex 2: Implement muzzle? : Shuffle -> Boolean, which returns #true only if the given Shuffle is a Muzzle.
Ex 3: How much testing is too much testing? Is it necessary to look through a Muzzle to ensure that its oobleck is a String to distinguish it from other Shuffles? Does your answer change if we modified the signature of muzzle? to accept Any value?
Well-named predicates help keep functions on Shuffles intelligible.
Search and Destroy
; muff? : Shuffle -> Boolean ; Is the given Shuffle a Muff? (define muff? list?) ; shuffle-template : Shuffle -> ??? ; The form of every structural operation over Shuffles. (define (shuffle-template s) (cond [(duffle? s) (duffle-template s)] [(muzzle? s) (muzzle-template s)] [(muff? s) (muff-template s)]))
In Shuffles, as in all itemizations, we search through the possible cases with cond to figure out what to do with the Shuffle at hand. We then refer each case to the proper template for more specific handling, signaling where helper functions should appear in our code.
Ex 4: Duffles are itemizations as well. Define duffle-template, the form that all functions that operate on Duffles.
; duffle-template : Duffle -> ???
The muff-template is the standard List template we’ve written time and time again. We have one of the two possible cases of the [Listof Shuffle] itemization.
If we find '() we’ll have to return something. What we return is entirely output-specific, so omitted from the template.
If we find a composite cons cell, we destroy it by tearing it apart. The smaller pieces are passed off to their respective templates for specific handling, signaling where helper functions should appear in our code.
; muff-template : Muff -> ??? ; The form of all functions that operate on Muffs. (define (muff-template m) (cond [(empty? m) ...] [(cons? m) (... (shuffle-template (first m)) ... (muff-template (rest m)) ...)]))
Ex 5: Why don’t we pass '() Muffs to the empty-template? Put another way, is there anything you can express with an application (handle-empty ’()) of type handle-empty : ’() -> X that you can’t express by a plain value type of type X?
Ex 6: Write down the template for all operations that consume a Muzzle. Be sure to include explicit applications of any necessary templates.
Working on Muzzles
Swap Head and Hands!
Ex 7: Design a function count-streets that returns the number of Muzzle streets in a given Muzzle.
Hint: Make sure you check all the places a Muzzle can be found inside a Muzzle, it may require a helper function shuffle-streets.
(define MUZ0 (make-muzzle-town)) (define MUZ1 (make-muzzle-street "foo" 42 MUZ0)) (define MUZ2 (make-muzzle-street "bar" MUZ1 MUZ1)) (check-expect (count-streets MUZ0) 0) (check-expect (count-streets MUZ1) 1) (check-expect (count-streets MUZ2) 3)
Ex 8: Design a function muzzle-find that is given a Muzzle and a string key. If the Muzzle contains a Muzzle street with key in the oobleck field, it returns the Duffle in the tumble field. Otherwise, muzzle-find returns #false.
(check-expect (muzzle-find MUZ0 "foo") #false) (check-expect (muzzle-find MUZ1 "bar") #false) (check-expect (muzzle-find MUZ2 "foo") 42) (check-expect (muzzle-find MUZ2 "bar") MUZ1)
Visualizing Shuffles
Swap Head and Hands!
To get a better view of Shuffles, let’s convert them to strings. Duffles are easy.
Ex 9: Design a function duffle->string that turns any Duffle into a string. If the Duffle is a string already, wrap it in quotes: "\"rah\"". If the Duffle is a number, just convert it to a string.
(check-expect (duffle->string "foo") "\"foo\"") (check-expect (duffle->string 42) "42")
Muzzles, Muffs, and Shuffles are mutually recursive, so we’ll need to design these together.
Ex 10: Copy the muzzle-template, muff-template, and shuffle-templates into the bottom of your definitions window. Rename these definitions muzzle->string, muff->string, and shuffle->string. Write down the proper signature and purpose statements.
Copy in this helper function:
; intersperse : [Listof String] String String String -> String ; Join the given strings into a single string delimited by delim, ; surrounded by open and close. (define (intersperse los delim open close) (local [; prepend-all : [Listof String] String -> String ; Join the given strings into a single string prepended by delim (define (prepend-all los delim) (cond [(empty? los) close] [else (string-append delim (first los) (prepend-all (rest los) delim))]))] (cond [(empty? los) (string-append open close)] [else (string-append open (first los) (prepend-all (rest los) delim))]))) (check-expect (intersperse '() "delimiter!" "first" "last") "firstlast") (check-expect (intersperse '() "" "" "") "") (check-expect (intersperse '("1" "2" "3") "" "" "") "123") (check-expect (intersperse '("1" "2" "3") " " "" "") "1 2 3") (check-expect (intersperse '("1" "2" "3") "," "[" "]") "[1,2,3]")
Ex 11: Design the function muff->string that returns a string representating the given Muff. The elements should be delimited by "," and surrounded by square braces "[...]".
Hint: You will not be able to pass these tests until you’ve finished exercises 12, 13, and 14.
Ex 12: Design a function muzzle->strings that returns a list of strings representating the given Muzzle. Each Muzzle street should be converted into a single string, where the oobleck and tumble fields are seperated with a colon ":", and each oobleck wrapped in quotes.
(check-expect (muzzle->strings MUZ0) '()) (check-expect (muzzle->strings MUZ1) '("\"foo\":42")) (check-expect (muzzle->strings MUZ2) '("\"bar\":{\"foo\":42\"}" "\"foo\":42"))
Ex 13: Design the function muzzle->string that returns a string representating the given Shuffle. You should be able to implement it easily with muzzle->strings and intersperse.
Ex 14: Design the function shuffle->string that returns a string representating the given Shuffle.