Lab 18: Once More with Meaning

Implement this lab with the Intermediate Student Language with Lambda.

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!

Just Some Other Nonsense

In Lab 17: Oobleck you implemented operations on Shuffles, Duffles, Muzzles, and Muffs with no understanding of the meaning of those data definitions. Thankfully, the structural templates of operations on those data are effective regardless of the meaning of that data.

It turns out that Shuffles are equivalent to a data format known as JSON.

Ex 1: Don’t take our word for it: write in a comment two examples each of Shuffles, Duffles, Muzzles, and Muffs and their respective representations as JSON values.

; An Atom is one of:

; - Number

; - String

; Interp: Atomic JSON data.

(define ATOM0 "")

(define ATOM1 42)

(define ATOM2 "brightly, brightly, and with beauty")

;

(define-struct empty-asc ())

(define-struct asc-pair (key value rest))

; An Asc is one of:

; - (make-empty-asc)

; - (make-asc-pair String JSON Asc)

; Interp: Ascs represent associations between string keys and JSON values.

(define ASC0 (make-empty-asc))

(define ASC1 (make-asc-pair "foo" ATOM0 ASC0))

(define ASC2 (make-asc-pair "bar" ATOM1 ASC1))

(define ASC3 (make-asc-pair "baz" ASC1 ASC2))

;

; A JSON is one of:

; - Atom

; - Asc

; - [Listof JSON]

; Interp: A subset of the JavaScript Object Notation specification.

(define JSON0 '())

(define JSON1 (list ATOM0 ASC0))

(define JSON2 (list ASC1 ATOM2 ATOM1))

The structure of the data remains unchanged. The templates for operations over JSON are as follows:

; atom? : JSON -> Boolean

(define (atom? j) (or (string? j) (number? j)))

; asc? : JSON -> Boolean

(define (asc? j) (or (empty-asc? j) (asc-pair? j)))

; json-template : JSON -> ???

; The template for all operations over JSON.

(define (json-template j)

(cond [(atom? j) (atom-template j)]

[(asc? j) (asc-template j)]

[else (... (json-template (first j))

...

(json-template (rest j))

...)]))

; atom-template : Atom -> ???

; The template for all operations over Atoms.

(define (atom-template a)

(cond [(string? a) (... a ...)]

[(number? a) (... a ...)]))

; asc-template : Asc -> ???

; The template for all operations over Ascs.

(define (asc-template m)

(cond [(empty-asc? m) ...]

[(asc-pair? m) (... (asc-pair-key m)

...

(json-template (asc-pair-value m))

...

(asc-template (asc-pair-rest m))

...)]))

Remember our mantras for these templates: search through itemizations to find the proper case; destroy composites by tearing them apart. Each time we make progress (by finding the proper case or by pulling out smaller pieces of data) we hand the value over to its respective template.

As with Shuffles, we can easily turn JSON values into strings by following their templates. But the code below has a few bugs...

Ex 2: Copy intersperse from Lab 17: Oobleck and the functions {json,atom,asc}->string (below) into your defintions window. Fix the bugs in the code and any other mistakes (including those in signatures). Make all tests pass.

; atom->string : Atom -> String

; Convert the given atomic JSON value to a string.

(define (atom->string a)

(cond [(string? a) (append "\"" a "\"")]))

(check-expect (atom->string ATOM0) "\"\"")

(check-expect (atom->string ATOM1) "42")

(check-expect (atom->string ATOM2) "\"brightly, brightly, and with beauty\"")

; asc->string : Asc -> Number

; Convert the given JSON asc to a string.

(define (asc->string m)

(local [; asc->strings : Asc -> [Listof String]

; Convert each pair inside the asc to a string.

(define (asc->strings m)

(cond [(empty-asc? m) '()]

[else (cons (pair->string (asc-pair-key m) (asc-pair-key m))

(asc->strings (asc-pair-rest m)))]))

; pair->string : String JSON -> String

; Create a string representation of a key-value pair.

(define (pair->string k v)

(string-append "\"" k "\":" (json->string v)))]

(intersperse (asc->strings m) ", " "{" "}")))

(check-expect (asc->string ASC0) "{}")

(check-expect (asc->string ASC1) "{\"foo\":\"\"}")

(check-expect (asc->string ASC2) "{\"bar\":42, \"foo\":\"\"}")

(check-expect (asc->string ASC3)

"{\"baz\":{\"foo\":\"\"}, \"bar\":42, \"foo\":\"\"}")

; json->string : JSON -> String

; Convert the given JSON value into its string representation.

(define (json->string j)

(cond [(atom? j) (atom->string j)]

[(asc? j) (atom->string j)]

[else (intersperse (map json->string j) ", " "[" "]")]))

(check-expect (json->string JSON0) "[]")

(check-expect (json->string JSON1)

"[\"\", {}]")

(check-expect (json->string JSON2)

"[{\"foo\":\"\"}, \"brightly, brightly, and with beauty\", 42]")

Working with Ascs

Swap Head and Hands!

In the last lab, we designed a function muzzle-find such that if the Muzzle contains a Muzzle street with key in the oobleck field, it returns the Duffle in the tumble field (and #false otherwise).

Ex 3: Design the function asc-find that, given a Asc and a String key, returns the first JSON value associated with key or #false if no such key exists.

Note: To write a proper signature for asc-find, we need an itemization of either JSON values or #false. We need a data definition to represent the union of those values.

Ex 4: Design a data definition EitherFalseOrJSON for values that are either JSON or #false. Remember, to design a data definition you must give a template as well.

There are many functions like asc-find that we wish to write that may return one of two otherwise unassociated data types. Rather than littering our definitions with simple unions like EitherFalseOrJSON, we can

Ex 5: Design a data definition [Either X Y] that generalizes over any two-case itemizations. Put some thought into how the right-hand side of the two cond clauses should work, you may need to accept more than one argument in the either-template.

Ex 6: Design the function asc-remove that, given a Asc and a String key, returns a new Asc with all key/value assocciations with keys string=? to key removed.

Mapping Atoms in JSON

Swap Head and Hands!

Ex 7: Design the function json-add1 that given a JSON value, returns a new JSON value where each number has been incremented by 1 and each string has had "+1" appended to its end.

Hint: Per the template, you’ll need to design functions atom-add1 and asc-add1 to properly implement json-add1.

(check-expect (json-add1 JSON2) (list (make-asc-pair "foo" "+1" ASC0)

"brightly, brightly, and with beauty+1"

43))

(check-expect (json-add1 ATOM0) "+1")

(check-expect (json-add1 ATOM1) 43)

(check-expect (json-add1 ASC1) (make-asc-pair "foo" "+1" ASC0))

(check-expect (json-add1 ASC3)

(make-asc-pair "baz" (make-asc-pair "foo" "+1" ASC0)

(make-asc-pair "bar" 43

(make-asc-pair "foo" "+1" ASC0))))

Ex 8: Design the function json-no-numbers that given a JSON value, returns a new JSON value where each number has been converted to a string.

Hint: Per the template, you’ll need to design functions atom-no-numbers and asc-no-numbers to properly implement json-no-numbers.

(check-expect (json-no-numbers JSON2) (list ASC1 ATOM2 "42"))

(check-expect (json-no-numbers ATOM0) "")

(check-expect (json-no-numbers ATOM1) "42")

(check-expect (json-no-numbers ASC1) ASC1)

(check-expect (json-no-numbers ASC3)

(make-asc-pair "baz" ASC1 (make-asc-pair "bar" "42" ASC1)))

Ex 9: Design the following three functions, which map operations over the atomic values inside JSON values.

; json-atom-map : JSON (Number -> JSON) (String -> JSON) -> JSON

; Map nf and sf over the atomic values in the given JSON value.

(define (json-atom-map j nf sf) j) ; <- stub

; atom-map : Atom (Number -> JSON) (String -> JSON) -> JSON

; Map nf and sf over the given atomic value.

(define (atom-map a nf sf) a) ; <- stub

; asc-atom-map : Asc (Number -> JSON) (String -> JSON) -> Asc

; Map nf and sf over the atomic values inside m's values.

(define (atom-map m nf sf) m) ; <- stub

Ex 10: Define the functions json-add1/2 and json-no-numbers/2 in terms of the Atom mapping functions.

Filtering Ascs

Ex 11: Design a function foos-are-awful that, given a JSON value, returns a new JSON with any Asc key/value pair with the key "foo" removed.

(check-expect (foos-are-awful JSON1) JSON1)

(check-expect (foos-are-awful JSON2) (list ASC0 ATOM2 ATOM1))

(check-expect (foos-are-awful ASC2) (make-asc-pair "bar" ATOM1 ASC0))

(check-expect (foos-are-awful ASC3)

(make-asc-pair "baz" ASC0 (make-asc-pair "bar" ATOM1 ASC0)))

Ex 12: Design a function no-more-numbers that, given a JSON value, returns a new JSON with any Asc key/value pairs with numeric values removed.

(check-expect (no-more-numbers JSON1) JSON1)

(check-expect (no-more-numbers JSON2) JSON2)

(check-expect (no-more-numbers ASC2) ASC1)

(check-expect (no-more-numbers ASC3) (make-asc-pair "baz" ASC1 ASC1))

Ex 13: Design a function asc-filter-out that, given an Asc and a function remove? : String JSON -> Boolean, returns a new JSON with any Asc key/value pairs that satisfy remove? removed.

Hint: Per the template, you’ll need a function json-filter-out to properly design asc-filter-out.

Ex 14: Define the functions foos-are-awful/2 and no-more-numbers/2 in terms of asc-filter-out.