Lecture: 3 Date: Jan 10, 2008 Union data definitions Recursive (self-referential) data definitions ==== Q: What is the difference between information and data? We use data to /represent/ information on a computer. Q: What is a /class of data/? A: The collection of all data which we can interpret as a certain kind of information. So information is encoded into data and data is interpreted to obtain the information it represents. What kind of information might we care about for a book? (Let's say we're writing software for a library). - Title - Author - ISBN - Genre ... Q: How do we want to represent this information? A: This information is made up of other information, so in Scheme we'd use a structure, in Java we'd use a class. Q: How do we want to represent each of the pieces of data contained in a book? +---------------+ | Book | +---------------+ | String title | | String author | <-- simplification; we can extend later. | int isbn | <-- again, maybe this is a simplification of reality. | String genre | +---------------+ This defines a class of data-- how we represent book information IN GENERAL. We can interpret any instance of this class of data as a book. Define this class of data in Scheme: ;; A Book is a ?? (define-struct book ??) Define this class of data in Java: class Book { String title; String author; int isbn; String genre; // Constructor ... } A library doesn't just have books. It has book, CDs, DVDs, etc. +------------+ +-------+ +-------+ | Book | | CD | | DVD | +------------+ +-------+ +-------+ | ... | | ... | | ... | But we'd like to consider all of these to be library items. Q: How can we encode this-- a library item is a book, CD, or DVD? A: With a Union. Q: In Scheme? A: ;; A LibraryItem is one of: ;; - a Book ;; - a CD ;; - a DVD Q: With diagrams? A: An "inheritance" arrow (is-a). +----------------------+ | ILibraryItem | +----------------------+ / \ / \ / \ --- --- --- | | | +------------+ +-------+ +-------+ | Book | | CD | | DVD | +------------+ +-------+ +-------+ | ... | | ... | | ... | Q: In Java? A: // Purpose: to represent library items. interface ILibraryItem {} // Purpose: to represent library books. class Book implements ILibraryItem { ... } ... ** Remember, for every class definition, write a purpose statement for the class. ** Q: How can we create an instance of a library item? A: ILibraryItem htdp = new Book("HtDP", "Felleisen, et. al.", 1234, "S&M"); Notice that we wrote the type of htdp as ILibraryItem and not Book. We could have written Book, but it wouldn't be clear that this is an instance of the library item class of data. We want to write the most general type we can. Q: What's a type? A: A class defines a type and an interface defines a type. There are also primitive types (like int). So every class is a type, but not every type is a class. Q from audience: Can you have a class with no fields? A: Yes. Q: When would you want a class with no fields? ... crickets ... Consider this scenario: HtDP, ed. 2 comes out but they got rid of lists. What could you do? Make you own. Let's (for now) just think of lists of numbers (LoN): ;; A LoN is one of: ;; - empty ;; - (cons Number LoN) But cons and empty have gone away. But what is a cons? It's just a thing with two parts (a first and a rest). We can use a structure. ;; A Cons is a (make-cons Number LoN). (define-struct cons (first rest)) What about empty? It's like a structure with no fields. ;; An MT is a (make-mt). (define-struct mt ()) Q: How would you write '(1 2 3)? A: (make-cons 1 (make-cons 2 (make-cons 3 (make-mt)))) Now, let's do lists of integers in Java: // Purpose: to represent a list of numbers. interface ILoN {} // Purpose: to represent the empty ("mt", get it?) list of numbers. class MTLoN { MTLoN () {} } // Purpose: to represent a cons of a number and a list of numbers. class ConsLoN { int first; ILoN rest; ConsLoN(int first, ILoN rest) { this.first = first; this.rest = rest; } } Q: How would you write '(1 2 3)? A: ILoN ls = new ConsLoN(1, new ConsLoN(2, new ConsLoN(3, new MTLoN()))); Now let's talk about shapes. Suppose we have circles and squares and we want both to be considered shapes: +----------+ | IShape | +----------+ ^ ^ | | +------------+ +----------+ | Circle | | Square | +------------+ +----------+ | Posn loc | | Posn loc | | int radius | | int size | +------------+ +----------+ Q: What could we do with images? A: Overlay them. Let's make a new kind of shape: the shape that results from overlaying two shapes. +----------+ | IShape | +----------+ / \ --- | -------- | | | +------------+ ...Circle, Square | Combo | +------------+ | ???? | Q: What are the fields for Combo? A: top, bottom (abbrev. bot.) Q: What is top? bottom? A: a shape, IShape +----------+ | IShape | +----------+ / \ --- | -------- | | | +------------+ ...Circle, Square | Combo | +------------+ | IShape top | | IShape bot | +------------+ Q: Are we done? A: No, needs containment arrows (has-a): +----------+ -------->| IShape | | +----------+ | / \ | --- | | | -------- | | | | | +------------+ ...Circle, Square | | Combo | | +------------+ |-| IShape top | \-| IShape bot | +------------+ Note the recursion in the data definition here, and that the arrow is just like the recursive data definition arrow we used in Scheme. Let's return to yesterday's data definitions: Radio shows and Ads. +--------------+ | RS | +--------------+ | String title | --| Ad ad | | | int length | | +--------------+ | | +--------------+ +->| Ad | +--------------+ | String title | | int length | | ... | +--------------+ We simplified this data definition to make it so that every show has just one ad. Now that we've seen how to do recursive (self-referential) unions, which is what we need to represent lists, let's remove that simplification and consider radio shows with an arbitrary (zero or more) number of ads. Draw the data diagrams for this. Q: How can we represent an arbitrary number of things? A: Lists. Lists of Ads, specifically. +--------------+ | RS | +--------------+ | String title | +-| ILoAd ads | | | int length | | +--------------+ | | +------------+ +--->| ILoAd |<-------+ +------------+ | / \ | --- | | | --------- | | | | +--------+ +------------+ | | MTLoAd | | ConsLoAd | | +--------+ +------------+ | | Ad first | | | ILoAd rest |-+ +------------+ Q: How do write this in Java? // Purpose: to represent an arbitrary number of ads. interface ILoAd {} // Purpose: to represent the empty list of ads. class MTLoAd implements ILoAd { // No fields // Constructor MTLoAd() {} } ** Interpolation ** Q: What is the difference between an interface and a class with no fields? A: Interfaces represent (for now) unions. You cannot create an instance of a union directly-- you must create an instance of a variant of that union. That is, you can't write: ILoAd ad = new ILoAd(...); There is no constructor for ILoAd... it is not a class. But you can do: ILoAd ad1 = new MTLoAd(); ILoAd ad2 = new ConsLoAd(new Ad(...), new MTLoAd()); So a class with no field still has a constructor, and instances can be created directly. Q: When does a class definition need to use "implements"? A: When it is a variant in a union, Or: when its diagram has an inheritance arrow from it to an interface. ** End of interpolation ** // Purpose: to represent the cons of an ad and a list of ads. class ConsLoAd implements ILoAd { ... } // Purpose: to represent a radio show. class RS ?? { ... } Q: Do we need "implements" for RS? A: No, it has no inheritance arrows (it is not a variant of a union). // Purpose: to represent a radio show. class RS { String title; ILoAd ads; int length; ... }