Module 02

Last updated: Fri, 23 Jan 2015 17:43:09 -0500

Goals
• Understand how to combine existing data definitions to form either compound data, or itemization data (or both).

• Understand how the "shape" of a compound or itemization data definitions dictates the shape of a function that processes that kind of data (via the template).

• Understand the difference between the function composition design strategy versus the data decomposition strategy, and how to write functions of each kind.

In-class
1. Representing Time: Use BSL to implement these exercises. For some of the exercises, the remainder and quotient functions may be useful.
• Come up with a data definition named Time that represents the number of seconds ellapsed since (the last) midnight. Then implement the following functions:

 ; time+ : Time Time -> Time ; Increments t1 by t2 amount of time ; STRATEGY: ? (define (time+ t1 t2) ...) ; time- : Time Time -> Time ; Decrements t1 by t2 amount of time ; STRATEGY: ? (define (time- t1 t2) ...)
• Implement the following function, where Time.v2 can be either equivalent to your previous Time data definition or a completely new data definition:
 ; time->string : Time.v2 -> String ; Converts time t to a string in the 24-hour format HH:MM:SS. ; STRATEGY: ? (define (time->string t) ...)

• Did a particular time representation make it easier to write some of the functions and harder to write some others?

• Can you think of any other Time representations? How does it affect your function implementations?

2. Luggage Scanner: Come up with a solution to the luggage scanner problem.

In-class exercise 1 solution:

As Fred Brooks points out, representation is the essence of programming [MythicalManMonth].
Thus in this course, we focus on data design first, and use it to guide the rest of our program. Exercise 1’s goal is to explore how different data definitions affect the code in different ways, for the scenario of time representation.
 ; Time Data Definition 1: ; A Time is a Natural, representing seconds since midnight.
The first representation is similar to Unix time and makes time+ and time- trivial to implement. time->string is much more complicated however, requiring several remainder and quotient operations.
 ; Time Data Definition 2: (define HOURS/DAY 24) (define MINS/HOUR 60) (define SECS/MIN 60) ; An Hours is a Natural in the interval [0,HOURS/DAY) ; A Minutes is a Natural in the interval [0,MINS/HOUR) ; A Seconds is a Natural in the interval [0,SECS/MIN) ; ; A Time is a (make-time Hours Minutes Seconds) ; Interp: represents a time of day, in 24hr format (define-struct time (hr min sec))
With the second representation, time->string is much simpler and can be implemented with calls to number->string and string-append. But now time+ and time- are much more complicated.
A third representation could be:
 ; Time Data Definition 3: ; A Time is a String, representing a time of day, ; WHERE: the string has the format: HH:MM:SS, ; where HH is a number in [0,24) representing hours ;       MM is a number in [0,60) representing minutes ;   and SS is a number in [0,60) representing seconds
With this third representation, time->string can just return its input immediately. But the other functions now require first parsing the string before performing the desired computation. This extra complexity is much more burdensome than the slight benefit gained, so this third representation is likely not a great choice in most situations.

Problem Set 02