7 Designing Functions for Mutually Recursive Data Definitions

Purpose The purpose of this lab is to practice your design skills in the context of mutually recursive data definitions.

Textbook references Part IV: Intertwined Data, especially The Commerce of XML

Note XML, JSON, and Amazon’s ION language are used for storing and transmitting data. Each of them is conceptually derived from Lisp’s S-expressions from the 1960s. Many languages provide "bindings" for these data languages, but few live up to the level of support for such languages in Lisp-like languages. Like everything in computer science, all of them go thru "teenage-heartbreak" love-hate cycles; only S-expressions have stayed around for 60 years.

Introduction

5 minutes

Review When you develop templates, the most important rule is this:

You need to have a template per data definition and every reference inside of a data definition deserves a corresponding reference in the template.

Data and Template

15 minutes

Goals Understanding data definitions and writing template for mutually recursive data

; A THDL is one of:

; - String

; - Number

; - Boolean

; - 'null

; - Array

; - Hash

; An Array is a [Listof THDL]

; This represents a collection of data, essentially a list

(define-struct hash (data))

; A Hash is a (make-hash HashContent)

; This represents a named set of data, similar to a structure

; A HashContent is a [Listof KeyValuePair]

; This represents the set of key-value pairs contained in a Hash

(define-struct kv-pair (key value))

; A KeyValuePair is a (make-kv-pair String THDL)

; This represents an entry into a Hash

Exercise 1 Develop some examples of a THDL.

Exercise 2 Write out the template for a THDL. Remember the guideline, One Function Per THDL Definition! Don’t forget to apply all templates on non-atomic data.

Now that you have the template, do you see why this is considered mutually recursive?

Writing functions on mutually recursive data

25 minutes

Exercise 3 Design the function render-data which consumes a THDL and renders it as String according to the following rules:

• Numbers are displayed as plain numbers

• Boolean are displayed as true or false

• 'null is displayed as null

• Strings are wrapped in double quotes (\")

• Arrays are wrapped in square brackets ([])

• Elements in Arrays are separated by a comma and a space

• Hashes are wrapped in curly brackets ({})

• Hashes’ keys are wrapped in double quotes

• Hashes’ key-value pairs are separated by a comma and a space

• KeyValuePairs’ keys and values are separated by a colon and a space

Your solution may or may not include trailing commas.

Hints and examples:

> (string-append "\"" "hello" "\"")

"\"hello\""

Given

(make-hash (list (make-kv-pair "foo" 12)

(make-kv-pair "bar" (list -12 'null))

(make-kv-pair "baz" (list "string" #true))))

Expected

"{\"foo\": 12, \"bar\": [-12, null, ], \"baz\": [\"string\", true, ], }"

Writing functions on Pokémon data

15 minutes

The Pokémon portal provides all kinds of helpful data about video game creatures known as Pokémon. Using our data representation, we can send requests to this portal and get back some real data to play around with.

Example Copy and paste this definition into drracket and hit "run":

(define CHESPIN (get-pokemon-data 650))

If you look at the value of CHESPIN, you will notice that many keys of the fields in the data response say "resource_uri" and come with a URI. Each of these keys comes with String that represents a URI. These URIs point to another THDL with information about this part of the pokémon description. Eventually we wish to replace these key-value pairs with their THDL descriptions.

Exercise 4 Design more-info. The function takes in a THDL on a Pokémon and a function from String to String. It replaces the "resource_uri" key-value pair with the key "more_info" and the value obtained by using the provided function to get data at the original "resource_uri" value.

The value next to "resource_uri" is guaranteed to be a String and a well-formed URI. If the value for a "resource_uri" key points to a Pokémon, that is, the string contains (hint string-contains?) the word "/pokemon/", there’s no need to fill in this information.

Exercise 5 Modify the function more-info so that if the replacement value for a "resource_uri" key points to a Pokémon, there’s no need to fill in this information any further.

Exercise 6 Once you have finished the precedinng exercise, you can apply more-info to the library-provided get-data function. This will take some time to run since it has to make a bunch of internet requests.

Note The "version1" API occasionally returns bad results. If this happens, add the line

(version 2)

to the beginning of your file. This version of the API is more reliable but returns larger, differently formatted data. If you have to switch, you need to modify your program in two ways:

• the key for references to other resources is "url" instead of "resource_uri", and

• the value specifies the full url, which means you can use get-url instead of get-data (but watch, this function doesn’t signal helpful errors.)

Since you programmed to a single point of control, this should of course be no problem for you :).

Code Review

25 minutes

The Teaching Assistants will pick two pairs who will explain a solution to their lab mates following the design recipe steps.

Before You Leave...

Just so you know, THDL is a data representation for the JSON data language, short for JavaScript Object Notation. The only difference between our THDL data and a JSON is that hashes are often referred to as "objects" and the usual internal representation (for example in Racket) is a hashtable, but we avoided this part.