Modeling and Abstraction

[an error occurred while processing this directive] [an error occurred while processing this directive] Modeling and Abstraction

COMP 200

Elements of Computer Science

Program Design

Read section 2.5 of HTDP.

Fundamental questions to ask when designing a program:

What are the variants?
What are the invariants?
What are the data the program is to process?
How can the program be decomposed into smaller components, and how to put these smaller component together to solve the original problem?

These questions are to be asked continually throughout the whole design process.

Design Recipe

A Scheme program consists of one or more functions. Each function should have the following:

Contract: specify the domain and range of the function
Header: specify the spelling of the function name and its input parameters.
Purpose: describe what the functions is supposed to compute and return as a result.
Examples: specify a few examples that illustrate the behavior of the function on different sets of input.
Definition: write the code the function
Tests: test the correctness of the function by running the examples.

Case study:

Refer to the movie theater example in section 3.1 of HTDP.

Ask the fundamental questions:

What are the variants?
- The movie ticket can vary arbitrarily.
What are the invariants?
- A few numbers such as 120, 5, .10, 15, 180, .04 are arbitrary constants.
- Invariably, a change in ticket price triggers a change in attendance, which triggers a change in revenue and cost and thus the profit. This invariant behavior of the system is subtle and hard to identify sometime.
What are the data the program is to process?
- Numbers representing the ticket price, attendance, revenue and cost.
- The problem is to take in a ticket price and compute the corresponding profit, which is also a number.
How can the program be decomposed into smaller components, and how to put these smaller component together to solve the original problem?
- For many problems, this can be hard to identify at first. For this problem, as discussed in the above, there are pieces such as attendance, revenue and cost, that seem to be an integral part of the problem.
- Knowing how to compute them should help compute the profit, which is the goal of the problem.

Apply the Design Recipe

As discussed in the above analysis, the problem is to write a function that takes in a ticket price as input and produces the corresponding profit. So let's apply the design recipe to code this function. (We will do this interactively in class.)

This is what the function looks like after going through the design recipe.

;; Contract: profit : number  ->  number
;;
;; Header: (define (profit ticket-price) ...)
;;
;; Purpose: (profit tp) computes and returns the profit as the difference between revenue and costs
;; at some given ticket-price tp.
;;
;; Examples  (TO DO):
;; (profit 5) = ?
;; (profit 4.9) = ?
;; (profit 4.8) = ?
;; (profit 4) = ?
;;
;; Definition: this is the real code.
(define (profit ticket-price) 
  (- (revenue ticket-price) (cost ticket-price)))
;;
;; Tests (TO DO)
(= (profit 5) ?)
(= (profit 4.9) ?)
(= (profit 4.8) ?)
(= (profit 4) ?)

Note that in the above, the Examples section and the Tests section are incomplete. We need to work out by hand the listed examples in order to completely fill out the Examples and Tests section. In working out the examples by hand, we should gain some deeper understanding of the problem and use that knowledge to solve the problem. Let's do this together in class.

Click here to download the EXCEL spreadsheet that solves the problem.

If we try to run the above program, we will get a few error message. One main reason is that the computer does not know what revenue and cost are. We need to apply the design recipe to write the code for revenue and cost as well. We will do this interactively in class.

Top down Design

What we have done in the above design process is to start "from the top" with the function representing the solution to the problem, then work down to the final details to obtain the final solution. This is called "top down" design. This design process is very popular and for all practical purposes, will suffice for our class.

Conditionals

Problem 1: The following is the labbie pay rate at the CS Department.

$10 for labbies with less than one year of experience
$11 for labbies with a year or more of experience.

Write a function that produces the pay rate given the number of years of experience.

The main data in this problem are numbers representing the years of experience. It is partitioned into two parts:

less than one year
greater or equal to one year.

To process this data, we need to have a way to check for the range in which the input data belongs. In Scheme, we use what is called a "cond."

Last revised 08/26/2007 12:00 AM

Maintained by the professor; see contact information on the course home page