7 Solidifying what we’ve done
So far, we’ve seen a number of different ways of specifying the creation and behavior of the data we work with. At this point, it’s valuable to take a step back and consider all of the concepts we’ve seen.
7.1 Data Definitions
A data definition defines a classHere we mean “class” in the general sense of “a set of values,” not to be confused with the concept of a “class” as definied by the define-class form. of values by describing how instances of that data are constructed. In this book, we focus on particular new kind of value: objects, and data definitions will primarily define a class of objects. New kinds of objects are made with define-class, while instances of a class are made with a class constructor, written (new class-name% arg ...).
Data definitions can be built out of primitive data, such as Numbers, Strings, Images, etc., but also compound data can be represented with objects containing data. Data definitions can also be formed as the (possibly recursive) union of other data definitions. For example:
;; A ListofImage is one of: ;; - (new empty%) ;; - (new cons% Image ListofImage)
Data definitions may be parameterized, meaning a family of similar data definitions is simultaneously defined by use of variable parameters that range over other classes of values. For example:
;; A [Pair X Y] is one of: ;; - (new pair% X Y)
Here the Pair family of data definition is parameterized over classes of values X and Y.
7.2 Interface Definitions
Another way to define a class of values is by way of an interface definition. Unlike a data definition, which focuses on how data is represented, an interface defines a set of values by the operations that set of values support. Interfaces provide a means for defining a set of values independent of representation.
;; A [List X] implements ;; - empty : -> [List X] ;; Produce an empty list ;; - cons : X -> [List X] ;; Produce a list with the given element at the front. ;; - empty? : -> Boolean ;; Determine if this list is empty. ;; - length : -> Number ;; Count the elements in this list ;; ... and other methods ...
There are several important aspects of this interface defintion to
note. First, it lists all of the methods that can be used on an
[List X], along with their contracts and purpose statements.
Mere method names are not enough—
Of course, just like data defintions don’t have to be named, interface defintions don’t have to be named either. If you need to describe an interface just once, it’s fine to write the interface right there where you need it.
7.3 Contracts
Contracts describe the appropriate inputs and outputs of functions and methods. In the past, we’ve seen many contracts that refer to data defintions. In this class, we’ve also seen contracts that refer to interface defintions, like so:
;; [IList Number] -> [IList Number]
When describing the contract of a function or method, it’s almost always preferable to refer to an interface definition instead of a data defintion that commits to a specific representation.
7.4 Design Recipe
The fields of this object, accessed with accessor methods,
The methods of this object, accessed by calling them,
And the operations of the arguments, which are given by their interfaces.
For example, if a method takes an input a-list which is specified in the contract to be an IList, then we know that (send a-list empty?), (send a-list length), and so on.
7.5 Design Choices
Q: Which is considered a better design: a union with two variants, or a single variant with a Boolean field that indicates "which part of the union this data belongs to"? For example, is it better to have a live-zombie% and dead-zombie% class or a single zombie% class with a dead? field.
A: One of the themes of this and last semester is that once you
have settled on choice for the representation of information in your
program, the structure of your program follows the structure of that
data. We’ve trained you to systematically derive code structure from
data structure; there’s a recipe—
This is a long winded way of saying: there is no universal "right" answer to this question. It will depend on the larger context. That said, there are some important things to take into account for this particular question. It is much easier to add new variants to a union than it is to create Boolean values other than true and false. Good program design is often based on anticipating future requirements. If you think it’s possible that there might be some other kind of zombie down the road, the union design will be less painful to extend and maintain.
7.6 Exercises
7.6.1 JSON, Jr.
JSON (JavaScript Object Notation) is a lightweight data-interchange format. It is easy for humans to read and write; it is based on a subset of the JavaScript Programming Language. There are a large number of huge corpora of data available on the internets. In order to write programs that can make use of this data, you’ll need to design a data representation of JSON values.
A JSON value can take on the following forms:This definition is drawn directly from http://json.org/
An object is an unordered set of name/value pairs.
An array is an ordered collection of values.
A value can be a string, or a number, or true or false or null, or an object or an array. These structures can be nested.
This definition is written in the terminology of JSON, so don’t confuse a JSON object with an object in the class language. Likewise, don’t confuse JSON strings with class strings.
To start things off simply, let’s focus on a subset of JSON we’ll call “JSON, Jr.” which consists solely of strings and arrays. Using the notation of JSON, the following are examples of JSON, Jr. values:
"this is JSON, Jr."
[ "this is JSON", "Jr." ]
[ [], [ "So", "is" ], "this" ]
The first example is just a string. The second is an array of two JSON elements, which are both strings. The third is another array, but of three elements: the first is an array of zero elements, the second is an array of two strings, and the third is a string.
Design an object-based data representation for JSON, Jr values.
Design a method for counting the number of strings in a JSON, Jr. value.
7.6.2 JSON
Revise the program you developed in the previous problem to handle all of JSON.
Design the following methods for JSON values:
A method for counting the number of numbers in a JSON value.
A method for summing all the numbers in a JSON value.
A method for finding the length of the longest array in a JSON value.
A method for computing the nesting depth of a JSON value.
Design the following methods for JSON objects:
A method that works on JSON object values that takes a string and produces the JSON value associated with that string in the object, or false if no such value exists.
A method that counts the number of name/value pairs in an object.
A method that extends an object by adding a given name/value pair to an object.
A method that restricts an object by subtracting a given name/value pair from an object.
A method of computing the length of the array.
A method for indexing the ith element of an array.
A method for reversing an array.
Given a nesting depth, compute a random JSON value of at most that nesting depth. (It must be the case that if called repeatedly, eventual this function will produce a JSON value of exactly the given nesting depth, but it may not always produce a value nested so deep.)
Design an alternative data representation of JSON values that uses a subset of S-Expressions to model JSON values, which we’ll call JSEN (JSON S-Expression Notation).
Design a function for converting from a JSEN representation to the object representation of that value. Design a method for JSON values that produces their JSEN representation.