In this module we continue to explore new, more complex, kinds of data definitions: structures, nested data, and self referential data. To assist us with designing functions that consume/produce these kinds of data we introduce constructor, destructor, and function templates. Finally, we discuss the different strategies used to design functions, and the relationship between strategies and certain kinds of data definitions.

  1. Define the term compound.
  2. Write a code example of compound data.
  3. Explain what define-struct does.
  4. List the four properties that define a value.
  5. Write code that uses a structure definition to create a new value.
  6. List the four questions used during the design of data definitions.
  7. List the three parts that make up a data definition.
  8. Write a constructor template.
  9. Explain what is a destructor template.
  10. Given a set of data definitions, write down their destructor templates.
  11. Explain the role of representation.
  12. Explain the role of interpretation.
  13. Explain the relationship between information and data.
  14. Use CamelCase for data definition names.
  15. Given a Scheme expression, write down the sequence of steps taken during evaluation.
  16. Given a function, write a contract.
  17. Given a function, write a purpose statement.
  18. Given a function, write the appropriate example.
  19. Given a Scheme function, identify the strategy used.
  20. Write a new function by composing existing functions.
  21. Explain structural decomposition.
  22. Use structural decomposition by writing a function that takes itemized, compound, or mixed data as input.
  23. Given a Scheme expression, write down the sequence of steps taken during evaluation.
  24. Explain what each step of the Design Recipe does.
  25. Write a program that uses the build-in function big-bang to create an animation.
  • DUE DATE: February 12th, 2015 @ 12:00pm (NOON)

Problem 1

Provide templates for the following data definitions 


(define-struct person (first last))
;; A Person is (make-person String String)
;; INTERP: holds the first and second name for a person

(define-struct affiliation (institution street-no street-name zip state country))
;; An Affiliation is (make-affiliation String Number String Number Symbol String)
;; INTERP: holds the name of the instituion, institution's streen number and 
;; street name, zip code state and country. 
;; State is given as a symbol of size 2, e.g. 'WA

(define-struct date (year month day))
;; A Date is (make-date Number Number Number) 
;; INTERP: represents a date as YYYY MM DD

(define-struct presentation (title author affiliation date))
;; A Presentation is (make-presentation Sring Person Affiliation Date) 
;; INTERP: represents a presentation (a talk) with a title, 
;; the name of the author, the author's affiliation and 
;; the date of the presentation

Problem 2

A Professor from another department asked for your help in order to write a program that will manipulate techincal publications.

A publication can be one of

  • Conference. These are paper that have been published at a conference. We would like to capture the following information for conference publications.
    • Title: this is the paper's title.
    • Author: the author's name. There can only be one author.
    • Conference Name: the name of the conference.
    • Location: the location of the conference, typically a city and country, e.g. "Seattle, USA"
    • Month: the first three letters of the month, e.g., Oct
    • Year: the 4-digit calendar year.
  • Journal. These are papers that have been published to a Journal. We would like to capture the following information for journal publications.
    • Title: this is the paper's title.
    • Author: the author's name. There can only be one author.
    • Journal Name: the name of the Journal.
    • Issue: the issue number of the Journal, typically a number, e.g., 26
    • Month: the first three letters of the month, e.g., Oct
    • Year: the 4-digit calendar year.
  • Technical Report. These are papers that have been published as technical reports. We would like to capture the following information for technical report publications.
    • Title: this is the paper's title.
    • Author: the author's name. There can only be one author.
    • TR-ID: an identifier for this technical report, typically a number, e.g., 3425
    • Institution: the name of the institution publishing the technical report.
    • Year: the 4-digit calendar year.

Author names come in two flavours. An author's name is one of

  • Full Name: consists of the author's first and last name.
  • Official Name: consists of the author's first, middle, last names and title.

Another student has started working on a program but they had to abandon the project. You are asked to pick up from where they left off. Here is the incomplete code 

 

;;; Data Definitions 
(define-struct official (first middle last title))
;; An OfficialName is (make-official String String String String)
;; INTERP: represents a person's official name with first, middle, last name
;;         and title.

;; Template

;;; Data Examples
(define JOHN-OFFICIAL (make-official "John" "D." "Doe" "PhD"))



(define-struct full (first last))
;; A FullName is a (make-full String String)
;; INTERP: represents a person's name with first and last name. 

;; Template

;;; Data Examples
(define JOHN-FULL (make-full "John" "Doe"))

;; An Author is one of
;; - OfficialName
;; - FullName
;; INTERP: represents the name of an author for a publication as either
;;         a full name (first and last) or an offical name (first, middle, last
;;         and title)

;; Template


;; A Year is a PosInt
;; WHERE: Year is a 4 digit number
;; INTERP: represents a calendar year. 

;; A Month is one of
;; - 'Jan
;; - 'Feb
;; - 'Mar
;; - 'Apr
;; - 'May
;; - 'Jun
;; - 'Jul
;; - 'Aug
;; - 'Sep
;; - 'Oct
;; - 'Nov
;; - 'Dec
;; INTERP: represents a month in a calendar year. 

;; Template


(define-struct conference (title author cname location month year))
;; A Conference is (make-conference String Author String String Month Year)
;; INTERP: represents a conference paper with title, author, conference name,
;;         conference location, month and year

;;; Data Examples
(define JOHN-FULL-CONF (make-conference "Anatomy of a mouse"
                                        JOHN-FULL
                                        "Animal Anatomy"
                                        "London, UK"
                                        'Jul
                                        2003))
(define JOHN-OFFICIAL-CONF (make-conference "Anatomy of a mouse"
                                            JOHN-OFFICIAL
                                            "Animal Anatomy"
                                            "London, UK"
                                            'Jul
                                            2003))


;; Template

;; An Issue is a PosInt
;; INTERP: represents a journal's issue number

(define-struct journal (title author jname issue month year))
;; A Journal is (make-journal String Author String Issue Month Year)
;; INTERP: represents a journal paper with title, author, journal name,
;;         month and year.

;;; Data Examples
(define JOHN-FULL-JOURNAL  (make-journal "Anatomy of a mouse"
                                         JOHN-FULL
                                         "Mouse Journal"
                                         23
                                         'Feb
                                         2002))

(define JOHN-OFFICIAL-JOURNAL  (make-journal "Anatomy of a mouse"
                                             JOHN-OFFICIAL
                                             "Mouse Journal"
                                             23
                                             'Feb
                                             2002))

;; Template:


(define-struct techreport (title author tr-id institution year))
;; A TechnicalReport is (make-techreport String Author PosInt String Year)
;; INTERP: represents a technical report with title, author,
;;         technical report id, institution name, month and year.


;;; Data Examples

(define JOHN-FULL-TR (make-techreport "Anatomy of a mouse"
                                      JOHN-FULL
                                      1234
                                      "Mouse University"
                                      2001))


(define JOHN-OFFICIAL-TR (make-techreport "Anatomy of a mouse"
                                          JOHN-OFFICIAL
                                          1234
                                          "Mouse University"
                                          2001))


;; Template

;; A Publication is one of
;; - Conference
;; - Journal
;; - TechnicalReport
;; INTERP: represents a publication as either a confrence, journal or
;;         technical report. 

;; Template

You are asked to

  1. Fill in the missing parts of the Data Definitions
  2. Design a function called tr->journal that will consume
    1. a technical report
    2. a journal's name
    3. a journal's issue
    4. the month
    5. the year
    and should return a new journal publication that has the same title and author as the technical report and the same journal issue, month and year as the values passed as arguments.
  3. Design a function called publication->image that consumes a publication and returns a formatted text image (see text/font and beside). All text in the images must have
    • font size 20
    • color black
    • font face #false
    • font family modern
    • not underlined
    • there must be a space after each period or comma
    Here are the specific formatting rules for each publication. The list is in the order that the corresponding information is to be printed out. See the examples at the end of the problem statement.
    • Conference Paper
      • The title must be enclosed in double quotes and followed by a period.
      • The author's name followed by a period.
      • The conference name in italics followed by a comma.
      • The conference location in italics followed by a period.
      • The three character month in bold followed by a comma.
      • The 4-digit year in bold followed by a period.
    • Journal Paper
      • The title must be enclosed in double quotes and followed by a period.
      • The author's name followed by a period.
      • The journal's name in italics followed by a comma.
      • The journal's issue in italics followed by a period.
      • The three character month in bold followed by a comma.
      • The 4-digit year in bold followed by a period.
    • Technical Report
      • The title must be enclosed in double quotes and followed by a period.
      • The author's name followed by a period.
      • The institution's name in italics followed by a comma.
      • The technical reports id number in italics followed by a period.
      • The 4-digit year in bold followed by a period.
    For the author's name, here are the specific formatting rules.
    • Full Name first name followed by a space followed by the last name
    • Official Name title followed by a space, followed by the first name followed by a space followed by the middle name followed by a space followed by the last name
    Here are some formatted samples.
    > (publication->image JOHN-FULL-CONF)
    john-full-conf
    > (publication->image JOHN-OFFICIAL-CONF)
    john-official-conf
    4. > (publication->image JOHN-FULL-JOURNAL)
    john-full-journal
    > (publication->image JOHN-OFFICIAL-JOURNAL)
    john-official-journal
    > (publication->image JOHN-FULL-TR)
    john-full-TR
    > (publication->image JOHN-OFFICIAL-TR)
    john-official-tr

Problem 3

A friend is trying to write a small game in DrRacket and is having problems designing two functions. The game is simple. There is a canvas 500 by 500 and a red circle. When we start the game the circle appears in the center of the canvas. The circle is solid red in color an has a radius of 20 points. The circle moves 10 points after each clock tick. When the game starts the circle moves upwards. The user can use the keyboard's arrow buttons (up, down, left, right) to make the circle change it's direction.

Here is the incomplete code 

 
(require 2htdp/universe)
(require 2htdp/image)


(define LEFT 'left)  
(define RIGHT 'right)
(define UP 'up)
(define DOWN 'down)

;; A Direction is one of
;; - LEFT
;; - RIGHT
;; - UP
;; - DOWN
;; INTERP: represents the direction of the moving ball

;; Template 
;; direction-fn: Direction -> ??? 
;;(define (direction-fn a-direction)
;;  (cond 
;;    [(symbol=? a-direction UP) ...]
;;    [(symbol=? a-direction DOWN) ...]
;;    [(symbol=? a-direction LEFT) ...]
;;    [(symbol=? a-direction RIGHT) ...]))
    


(define-struct world (location direction))
;; A World is (make-world Posn Direction)
;; INTERP: represents a ball on the canvas with a cartesian coordinate
;;         for location and a direction

;; Template 
;; world-fn: World -> ???
;;(define (world-fn w)
;;  ... (world-location w) ... 
;;  ... (direction-fn (world-direction w)) ...)


;;; Signature
;; change-direction: World KeyEvent -> World
;;; Purpose
;; Given the current world and a key-event return
;; a new update world if the user pressed up, down, left or right
;; arrow keys. If any other keys are pressed the world is unchanged.
(define (change-direction w key-event)
  (cond
    [(key=? key-event "up") (make-world (world-location w)
                                        'up)]
    [(key=? key-event "down") (make-world (world-location w)
                                          'down)]
    [(key=? key-event "left") (make-world (world-location w)
                                          'left)]
    [(key=? key-event "right") (make-world (world-location w)
                                           'right)]
    [else w]))

(define BG (empty-scene 500 500))


;;; Signature 
;; ball-draw: World -> Image 
;;; Purpose 
;; Given a world create the corresponding image with a red solid circle 
;; with radius 20 at the appropriate location found inside world. 

;;; Signature 
;; ball-move: World -> World 
;;; Purpose
;; Given a world return a new world that moves the circle 
;; 10 points in the direction specified by the input world. 


(define INIT-WORLD (make-world (make-posn 250 250) 'up))

;;(big-bang INIT-WORLD
;;          (on-tick ball-move 0.1)
;;          (on-draw ball-draw)
;;          (on-key change-direction))

You are asked to provide the functions

  1. ball-draw, which takes a wold and draws the circle on the 500 by 500 canvas,
  2. ball-move, which takes a world and returns a new world were the circle has moved 10 points in the direction specified by the input world.
Once you have the missing functions implemented and tested uncomment the call to big-bang and you should be able to play the game.

Problem 4

  1. Provide a data definition for a list of booleans (lob)
  2. Design the function lob-or that consumes a list of booleans and returns the result of logically or-ing all the elements of the list. For example 
    
;; (lob-or (cons #true (cons #false (cons #true empty)))) is equivalent to
;; (or #true #false #true)
(lob-or (cons #true (cons #false (cons #true empty))))   ;; returns #true
(lob-or (cons #false (cons #false (cons #false empty)))) ;; returns #false
  3. Design the function lob-and that consumes a list of booleans and returns the result of logically and-ing all the elements of the list. For example 
    
;; (lob-and (cons #true (cons #false (cons #true empty)))) is equivalent to 
;; (and #true #false #true)
(lob-and (cons #true (cons #false (cons #true empty)))) ;; returns #false
(lob-and (cons #true (cons #true (cons #true empty))))  ;; returns #true

Problem 5

  1. Provide the data definition for a list of strings (los)
  2. Design the function los-total-length that consumes a list of strings and returns the sum of the length of each element in the list. For example 
    
(los-total-length (cons "a" empty))             ;; returns 1
(los-total-length (cons "aa" (cons "a" empty))) ;; returns 3
  3. Design the function los-contains that consumes a list of strings string-list and a string s and returns true if s is in string-list, otherwise returns false.
  4. Design the function los-replace-first that consumes a list of strings string-list and two strings old and new and returns the string-list but with the first old replaced by new. For example 
     
(los-replace-first (cons "a" (cons "b" (cons "a" empty))) "a" "x") 
;; returns 
;; (cons "x" (cons "b" (cons "a" empty)))

(los-replace-first (cons "a" (cons "b" (cons "a" empty))) "c" "x") 
;; returns 
;; (cons "a" (cons "b" (cons "a" empty)))
  5. Design the function los-replace-all that consumes a list of strings string-list and two strings old and new and returns the string-list but with all old replaced by new. For example 
     
(los-replace-all (cons "a" (cons "b" (cons "a" empty))) "a" "x") 
;; returns 
;; (cons "x" (cons "b" (cons "x" empty)))

(los-replace-all (cons "a" (cons "b" (cons "a" empty))) "c" "x") 
;; returns 
;; (cons "a" (cons "b" (cons "a" empty)))

Problem 6

A friend is trying to write a small game but they are stuck at the moment and they are asking for your help. Here is what code they have so far 



;; a direction is one of 
;;  - 'up
;;  - 'down
;;  - 'left
;;  - 'right

(define-struct bullet [location radius direction speed])
;; A Bullet is (make-bullet Posn PosInt Direction PosInt)
;; INTERP: represents a bullet with its current location, 
;;         the bullet's radius, the bullet's direction and 
;;         the bullet's speed

they are asking for your help in order to

  1. Define a data definition for a list of bullets
  2. Design a function called bullets-draw that consumes a list of bullets and draws the bullets on a 800x500 canvas
  3. Design a function called bullets-move that consumes a list of bullets and returns a list of bullets but each bullet has been updated to move speed units in the direction specified by the field direction inside the bullet structure.