“Difference Between Dates” Case Study
© 1994 M. J. Clancy and M. C. Linn
Problem / Write and test a Scheme program to compute how many days are spanned by two given days. The program will include a function called days-spanned-by that returns the number of days between and including its two inputs. The inputs to days-spanned-by represent dates in 1994 (a non-leap year); each input is a two-word sentence whose first word is a month name and whose second word is a legal date in the month. Assume that the first input date is earlier than the second.In solving this problem, it helps to remember the short poem:
Thirty days hath September,
April, June, and November.
All the rest have thirty-one,
Excepting February alone,
Which has four and twenty-four
Till leap year gives it one day more.
(Anonymous)
The table below lists some sample calls to days-spanned-by and the desired return values.
expression / desired return value(days-spanned-by '(january 3) '(january 9)) / 7
(days-spanned-by '(january 30) '(february 2)) / 4
(days-spanned-by '(june 7) '(august 25)) / 80
(days-spanned-by '(january 1) '(december 31)) / 365
Exercises / 1.(Analysis) Determine the number of days between January 20 and February 5.
2.(Analysis) Determine the number of days between January 20 and December 5.
3.(Reflection) What was different, if anything, about the way you determined the answer to exercise 1 as compared to exercise 2?If you used two different approaches to find the two answers, explain the circumstances under which you would use each approach.
4.(Analysis) Give two days that span an interval of 20 days.
5.(Analysis) Give two days that span an interval of 200 days.
6.(Reflection) What was different, if anything, about the way you determined the answer to exercise 4 as compared to exercise 5? If you used two different approaches to find the two answers, explain the circumstances under which you would use each approach.
Preparation / The reader should have experience with defining his or her own Scheme functions and constants, with the use of conditional expressions in Scheme (if and cond), and with the use of sentences and functions for constructing and accessing parts of them.A design based on a procedure for solving the problem by hand
How do programmers design problem solutions? / Figuring out how to solve a problem by hand usually provides ideas for the design of Scheme functions to solve the problem.How can the difference between two dates be computed by hand? / Working through the examples in the problem statement by hand suggests three different situations: dates in the same month, dates in consecutive months, and dates in non-consecutive months.
Dates in the same month
To compute the interval between two dates in the same month, for instance, between January 3 and January 9, we merely subtract the date in the first month from the date in the second month and add 1. We add 1 because both the days are to be included in the returned value. Thus the interval from January 3 through January 9 spans (9–3)+1 = 7 days.
Dates in consecutive months
To compute the interval between two dates in consecutive months, like January 30 and February 2, we determine the number of days remaining in the first month and add that to the date in the second month. Thus the interval from January 30 to February 2 spans January 30 and 31 (two days) plus February 1 and 2 (two more days).
Dates in non-consecutive months
To compute the interval between dates in non-consecutive months, we can determine the number of days in all the months between the two given months, add that to the days remaining in the first month, and add that sum to the date in the second month. The interval from June 7 and August 25 includes 31 days for all of July, 24 days from June 7 to June 30, and 25 days in August, a total of 80 days.
Stop and Help / Draw diagrams that represent the intervals between June 7 and June 25, between June 7 and July 25, and between January 30 and December 5.
How is the algorithm represented in pseudocode? / A commonly-used technique for designing a computer program is stepwise refinement, that is, rewriting a solution step by step, adding more detail at each step. It is useful to give descriptive names to data as soon as possible, so we do this in our first step, calling the dates earlier-date and later-date.
return the number of days
between earlier-date and later-date.
Our initial description is in semi-English, semi-Scheme. This intermediate representation between a programming language and a natural language is called pseudocode. We then add a level of refinement, again in pseudocode, that reflects the three situations mentioned above:
if the months for the two dates are the same,
then …
otherwise if the months for the two dates are consecutive, then …
otherwise …
Each “…” in the pseudocode represents the computation for the corresponding situation. We choose not to write the details down yet to avoid getting bogged down in detail.
How are the three situations represented in Scheme? / The pseudocode solution combining these three situations can be represented as a cond in Scheme. The tests to see what situation exists and the computations for the three situations can be represented as functions. Choosing good names for the functions helps to manage details, and produces Scheme code that is almost as understandable as the pseudocode algorithm:; Return the number of days spanned by earlier-date and
; later-date. Earlier-date and later-date both represent
; dates in 1994, with earlier-date being the earlier of the two.
(define (days-spanned-by earlier-date later-date)
(cond
((same-month? earlier-date later-date)
(same-month-span earlier-date later-date) )
((consecutive-months? earlier-date later-date)
(consec-months-days-spanned-by earlier-date later-date) )
(else
(general-days-spanned earlier-date later-date) ) ) )
The code includes a comment describing the purpose of the function and the assumptions made about the inputs. Same-month? and consecutive-months? are predicate functions, as indicated by the question mark at the end of their names; they return true or false, and thus can be used as the first half of a cond’s condition-value pair. The three …-span functions will return the number of days between the two dates in the more restricted situations just described.
Stop and help / Write the comments for each of the five functions same-month?,consecutive-months?, same-month-span, consec-months-days-spanned-by, and general-days-spanned-by.Here we have used the five functions before even thinking about how to write them. We have merely specified what they do, which is really all that’s needed in order to use the functions. Stepwise refinement typically involves repeating the following steps:
a.determining a value that is to be computed,
b.naming a function that computes it and deciding on its arguments,
c.using the function, and finally
d.designing the body of the function.
What is left to do? / We started by thinking about the problem as being made of various cases. This allowed us to begin by providing an outline of the problem. We refined that high-level outline using pseudocode, until we were able to write a Scheme function. This process allowed us to make headway on the problem without getting caught up in the details of each piece. We will reapply some of these techniques, such as stepwise refinement, as we continue to work on the problem.The new problem is to design the five functions. Ideally, each new problem is easier to solve than the original problem. We call this “dividing and conquering”.
Stop and consider / Has breaking one task into five subtasks complicated the solution or simplified it?Stop and predict / Think about the functions yet to be designed. Which of them seems hardest to design? Which seems easiest? How are they similar? Does the solution you worked out by hand help you in figuring out how they might be coded?
How is same-month? coded in Scheme? / We start with same-month?, since it will probably be easiest to code. Recall from the problem statement that a date is a two-word sentence. The first word is the month and the second word is a day within the month. Thus two dates have the same month if they have the same first word.
Stop and predict / Write the same-month? function.
Why use specially-defined access functions to access components of a date? / One might devise a solution that accesses the months by using function first directly. The code will be clearer, however, if accessing functions are used to refer to the two components of a date. Accessing functions name the corresponding pieces of the sentence, making it easier to understand what is being accessed in a given section of code. Thus we will provide a function called month-name to retrieve the month name from the date, and another called date-in-month to retrieve the date in the month.
Accessing functions also localize the details of how a particular piece of data—in this case, a date—is represented. This makes it easier to reuse code, by making the code that calls the accessing function less dependent on the Scheme representation of the data. For example, if some future assignment requires the use of dates in a slightly different format, the only functions that will have to change will be the month-name and date-in-month functions; everything else should work unchanged.
The same-month? function is then coded as follows:
; Return true if date1 and date2
; are dates in the same month,
; and false otherwise.
; Date1 and date2 both represent
; dates in 1994.
(define (same-month? date1 date2)
(equal?
(month-name date1)
(month-name date2) ) )
The dates don’t need to be in a particular relationship for same-month? to work, so we use date1 and date2 to name its arguments rather than earlier-date and later-date.
How is consecutive-months? coded? / Next we work on consecutive-months?. One way to code this is as an eleven-way test:; Return true if date1 is in the month that
; immediately precedes the month date2 is in,
; and false otherwise.
(define (consecutive-months? date1 date2)
(or
(and (equal (month-name date1) 'january)
(equal (month-name date2) 'february))
(and (equal (month-name date1) 'february)
(equal (month-name date2) 'march)
… ) ) )
Stop and help / How many lines of code does this function have?Stop and consider / What do you think of this function? Explain.
What’s wrong with this code? / This code is much too complicated—too “brute force”. What’s needed instead is something hat handles months in a general way rather than check each case separately. The function merely should check if the second date is in the month immediately after the first; this shouldn’t require much work.
How can consecutive-months? be coded more simply? / Another way to say that months are consecutive is to say that the second month is “one month after” the first. With month numbers instead of month names, we could merely check that the second month number is equal to the first plus 1. This suggests a simplifying intermediate step: translating a month name to a month number.
Stop and predict / Why is this simpler?
A month-number function that returned the number corresponding to a month name—1 for January, 2 for February, and so on—could be used in a much shorter consecutive-months?as follows:
; Return true if date1 is in the month that
; immediately precedes the month date2 is in,
; and false otherwise.
(define (consecutive-months? date1 date2)
(=
(month-number (month-name date2))
(+ 1 (month-number (month-name date1))) ) )
The month-number function can be coded as a twelve-clause cond:
(define (month-number month)
(cond
((equal? month 'january) 1)
((equal? month 'february) 2)
… ) )
An additional advantage of this design is that the month-number function is more likely to be useful in other applications involving dates.
A better way in Scheme is to represent the months in data—a list—rather than in the program code of function consecutive-months, and to use built-in functions that return information about a list.How can this code be tested? / The code to check for consecutive months is relatively complicated compared to same-month?. It makes sense to type it in and test it before going on, both to make sure we haven’t made any design errors and to give ourselves a bit of encouragement for having completed part of the problem. (We should probably test same-month? at the same time.) This piecewise testing of code is called incremental development.
Testing consecutive-months? requires testing month-number as well: we need to verify month-number returns the correct value for each month, and we must test that consecutive-months? uses the result correctly. Errors to test for include logic errors that result from confusion on the programmer’s part, as well as simple typing errors.
The only way to ensure that no errors appear in the large cond appearing in month-number is to provide arguments for which each condition succeed at least once. Thus at least twelve calls to month-number are necessary.
Once month-number has been tested, we turn to consecutive-months? and same-month?. Fewer tests are necessary for these functions; for instance, we get as much information from the call
(consecutive-months? '(march 1) '(april 13))
as from the call
(consecutive-months? '(april 1) '(may 13))
Stop and help / Why does one of the two calls just given provide no more information about the correctness of consecutive-months than the other call?We will need to test negativeas well as positive results, that is, with dates that aren’t in the same or consecutive months as well as those that are. Most people overlook such tests (preferring to think positively?). Experienced programmers also test functions with extreme values as well as typicalvalues, since programmers often make mistakes handling the boundaries of a set of data. The definition of “extreme value” depends on the situation. Two obvious extreme values for months are January and December, so we should be sure to test same-month? and consecutive-months? on dates in those months.
Stop and help / Produce a comprehensive set of function calls to test the code just written, and explain the evidence that each call provides for the purpose of convincing someone that the code works correctly.How is same-month-span coded? / We continue the design, going on to same-month-span. The pseudocode for this was given at the beginning of the narrative. Here’s the code:
(define (same-month-span earlier-date later-date)
(+ 1 (- (date-in-month date2) (date-in-month date1))) )
Stop and help / Design test cases for the function same-month-span. Categorize them as extreme or typical.How is consec-month-span coded? / Next comes consec-month-span. This requires some refinement. What’s needed, according to the procedure for computing the result by hand, is a way to find how many days are left in the first month. This is the number of days in the month, minus the date of the month, plus 1.
A function that returns the number of days in a given month can use a twelve-way test, similar to the code in month-number. We’ll call this function days-in-month. Recycling the month-number code in this way saves time. In general, it is also good to design functions whose purpose is similar to have similar code as well; the correctness of one of the functions provides some evidence of the correctness of the other.
Stop and help / Write days-in-month.Days-in-month is used in days-remaining as follows:
; Return the number of days remaining in the
; month of the given date, including the current
; day.
(define (days-remaining date)
(+ 1 (- (days-in-month (month-name date))
(date-in-month date) )) )
Following the previously designed pseudocode, we code consec-month-span as follows:
; Return the difference in days between earlier-date
; and later-date, which represent dates in consecutive
; months of 1994.
(define (consec-month-span earlier-date later-date)
(+ (days-remaining earlier-date)
(date-in-month later-date) ) )