| COMP 200 |
| Elements of Computer Science |
| Modeling and Abstraction |
|
|
|
When we write a program to solve a particular problem, we are in effect communicating our solution to a computer in terms of a set of instructions for it to carry out. The way we communicate with the computer is fashioned after the way we communicate with humans: that is we use "languages." The languages that computers "understand" are called computer languages. There are many computer languages, each of which is designed to use for some specific problem domain. Each language uses specific symbols and have specific rules, called syntax rules, on how these symbols should be put together. There are also rules that prescribe what each specific syntactic construct means; they are called semantic rules.
Examples
| Language | Syntax | Semantic |
| Scheme | (+ 4 7) | The sum of 4 and 7 |
| Java | 4 + 7 | |
| Excel | = 4 + 7 | |
| Scheme | (* (+ 2 3) 4) | First add 3 to 2, then multiply the result by 4. |
| Java | (2 + 3) * 4 | |
| Excel | = (2 + 3) * 4 |
In the above example, the arithmetic expressions in Scheme are said to be in prefix notation, i.e. the operator (+) precedes the operands (4 and 7), while the ones in Java and Excel are said to be in infix notation, i.e. the operator is in between the operands.
Writing a program to solve a problem entails:
We will learn how to program by focusing on modeling various problems at hand and building the resulting models using an appropriate programming constructs in the some appropriate language. The syntax and semantics of these constructs will be presented and explained as their needs arise.
Modeling is the process of building models. A model of something is some sort of representation of the “real” thing. For example, a street map is a model of a city. Architects make mock-ups of shopping malls that they are going to build. The law of supply and demand is a simple model of the economy. Abstract painters use colors to represent feelings. A model is something that is fundamentally “less” than the real thing that it represents, yet useful in helping solve the problem at hand. For example, a street map is more useful to some one who needs to find a particular address than an aerial photo of a city. An architect's foam mock-up is useful to the architect's client but is not so useful to the builder.
Essential to the modeling process is abstraction. Abstraction is the process of hiding the details and exposing only the essential features of a particular concept or object. Proper abstraction will result in a good model that helps solve the problem. Random addition and removal of features constitute another strategy for modeling, usually does not result in a good model to solve the given problem.
Computer Science is based on mathematics. A primary modeling tool is to use mathematical entities such as numbers, functions and sets to model problems. Since computers are originally designed to perform calculations, we illustrate the programming process with the following numerical example.
...The cheap taxi that is taking Jimmy the Geek from Charles DeGaulle to his hotel in downtown Paris has no air conditioning. Yet the air feels cool. Jimmy catches a glimpse of a billboard display the sign 15o. "Hmm, I wonder what temperature that is in Fahrenheit," he thinks to himself. Jimmy pulls out his Tablet PC and starts writing a program to convert Celsius into Fahrenheit...
We shall outdo Jimmy by writing such a temperature conversion program using:
Excel
Scheme, and
Java.
What does it take to write such a program?
First and foremost, it requires knowing the formula that converts Celsius to Fahrenheit, for without that knowledge, we cannot write the desired conversion program. The conversion formula is the mathematical model of the problem.
Second, it requires knowing how to express the model in a particular computer language. The result is a program. The computer program must closely represent the model in order for it to be correct and useful.
Third, it requires knowing how to test the code for correctness.
We use real numbers to represent the temperature readings in various temperature units. The formula expressing a temperature measurement F in Fahrenheit in terms of the measurement C in Celsius is:
F = 9/5 *C + 32
Here C is called the variable, and F is called a function of C.
At the foundation of mathematics is the notion of a function. A rigorous definition of a function is beyond the scope of this note. For our purpose, we can view a function as some sort of computation on elements in a set called the domain of the function, producing results that constitute a set called the range of the function. The elements in the domain are called the input parameters. The elements in the range are called the output results.
Notice that in describing what a function is, we have to use the notion of a set, which is also a key concept in the foundation of mathematics. Again, we will not rigorously define what a set is, but simply rely on our intuitive understanding that it represents a grouping of things.
We can use our favorite Excel tool and enter the formula with C replaced by 15, as shown below.
| A | B | |
| 1 | = 9/5 * 15 + 32 | |
| 2 |
As we enter the formula = 9/5 * 15 + 32 in the cell A1, Excel immediately displays the result: 59. The above is a program that solves the stated problem. It is an example of what is called a "constant" program.
What is good about this program is that it is simple, easy to understand, and most importantly it correctly solves the original problem. However, if we change slightly the problem to converting 17o Celsius to Fahrenheit, the program no longer is applicable. Intuitively, the problem has not really changed at all: the "real" problem is about converting a temperature measurement in Celsius to the corresponding value in Fahrenheit. What has changed is the value of the temperature measurement. The mathematical formula expressing the conversion process is an invariant: it does not change. The value of the variable C is a variant: something that can change arbitrarily. The above constant program fails to capture the variant/invariant nature of the mathematical formula, and as a result, cannot be used to solve the same conversion problem with a different temperature measurement.
What we want to do is to write a program that has an invariant part that corresponds to the formula and a variant part that allows entering arbitrary values for C.
We redesign our Excel spreadsheet to look as follows.
| A | B | C | |
| 1 | Input temperature in C: |
17 |
|
| 2 | Output temperature in F: | = 9/5 * B1 + 32 | |
| 3 |
In this solution, the user can enter any value for the temperature in Celsius in cell B1 and press Enter, and Excel will immediately compute the temperature in Fahrenheit. The formula in cell B2 refers to the value in cell B1 for the temperature. The number in cell B1 may change, it is variant; the formula in B2 is always the same, it is invariant. Therefore, this solution captures the mathematical formula more faithfully.
Aside: To ensure that the formula entered in cell B2 remain unchanged (and thus invariant), we can "lock" the spreadsheet and the cell B1 using the "locking" mechanism in Excel.
The Scheme solution that corresponds to the Excel constant program is written as follows.
(+ (* (/ 9 5) 15) 32)
We can enter the above expression in the Interactions pane of DrScheme and obtain the answer: 59.
As mentioned earlier, Scheme arithmetic expressions use the prefix notation enclosed in between a pair of matching parentheses. In general a Scheme arithmetic expression is either
a number, or has the form:
(op expression1 expression2)
where op stands for any arithmetic operator (e.g. +, -, *, etc) and expression1 and expression2 stand for any other Scheme expression that results in a number.
(To do: A few more examples of prefix expressions...)
To express a function such as the one defining the conversion from Celsius to Fahrenheit, Scheme (at the Beginner Level) uses a construct called define as in the following.
(define (Celsius2Fahrenheit c)
(+ (* (/ 9 5) c) 32))Type the above Scheme code in the Definitions pane of DrScheme and click the Run button.
Now, type (Celsius2Fahrenheit 15) in the Interactions pane and press Enter. What do you see?
The above define a Scheme function named Celcius2Fahrenheit that takes an input parameter named c, performs the conversion of c to Fahrenheit according to the conversion formula and returns the result. The prefix expression defining the formula to convert c to Fahrenheit is called the body of the function.
In general, we can define any function in Scheme using the syntax:
(define (function-name parameter-list)
(function-body))
In the above parameter-list denotes a list of zero or more parameter names, and function-body denotes any legal Scheme expression.
(To Do: More examples of Scheme functions here...)
© Dung X. Nguyen
Last revised 08/24/2008 09:03 PM