GeezerVisonThe World Wide Web, restored to 800 pixels of glory. | ||||||||
| Home|About|Gaming cabinet|Archives|How it works|Starter sites | ||||||||
GeezerVison is showing sicp.sourceacademy.org — 2 Building Abstractions with Data - SICP Comparison Edition
SICP — Scheme/JS
Structure and Interpretation of Computer Programs — Comparison Edition
Permalink copied!
2 Building Abstractions with Data
We now come to the decisive step of mathematical abstraction: we forget about what the symbols stand for. … [The mathematician] need not be idle; there are many operations which he may carry out with these symbols, without ever having to look at the things they stand for. We concentrated in chapter 1 on computational processes and on the role of procedures functions in program design. We saw how to use primitive data (numbers) and primitive operations (arithmetic operations), how to combine procedures functions to form compound procedures functions through composition, conditionals, and the use of parameters, and how to abstract procedures processes by using define. function declarations. We saw that a procedure function can be regarded as a pattern for the local evolution of a process, and we classified, reasoned about, and performed simple algorithmic analyses of some common patterns for processes as embodied in procedures. functions. We also saw that higher-order procedures functions enhance the power of our language by enabling us to manipulate, and thereby to reason in terms of, general methods of computation. This is much of the essence of programming. In this chapter we are going to look at more complex data. All the procedures functions in chapter 1 operate on simple numerical data, and simple data are not sufficient for many of the problems we wish to address using computation. Programs are typically designed to model complex phenomena, and more often than not one must construct computational objects that have several parts in order to model real-world phenomena that have several aspects. Thus, whereas our focus in chapter 1 was on building abstractions by combining procedures functions to form compound procedures, functions, we turn in this chapter to another key aspect of any programming language: the means it provides for building abstractions by combining data objects to form compound data. Why do we want compound data in a programming language? For the same reasons that we want compound procedures: functions: to elevate the conceptual level at which we can design our programs, to increase the modularity of our designs, and to enhance the expressive power of our language. Just as the ability to define procedures declare functions enables us to deal with processes at a higher conceptual level than that of the primitive operations of the language, the ability to construct compound data objects enables us to deal with data at a higher conceptual level than that of the primitive data objects of the language.
Consider the task of designing a system to perform
arithmetic with rational
numbers. We could imagine an operation
add-rat
add_rat
that takes two rational numbers and produces their sum. In terms of
simple data, a rational number can be thought of as two integers: a
numerator and a denominator. Thus, we could design a program in which
each rational number would be represented by two integers (a numerator
and a denominator) and where
add-rat
add_rat
would be implemented by two
procedures
functions
(one producing the numerator of the sum and one producing
the denominator). But this would be awkward, because we would then
need to explicitly keep track of which numerators corresponded to
which denominators. In a system intended to perform many operations
on many rational numbers, such bookkeeping details would clutter the
programs substantially, to say nothing of what they would do to our
minds. It would be much better if we could The use of compound data also enables us to increase the modularity of our programs. If we can manipulate rational numbers directly as objects in their own right, then we can separate the part of our program that deals with rational numbers per se from the details of how rational numbers may be represented as pairs of integers. The general technique of isolating the parts of a program that deal with how data objects are represented from the parts of a program that deal with how data objects are used is a powerful design methodology called data abstraction. We will see how data abstraction makes programs much easier to design, maintain, and modify.
The use of compound data leads to a real increase in the expressive power
of our programming language. Consider the idea of forming a
We begin this chapter by implementing the rational-number arithmetic system mentioned above. This will form the background for our discussion of compound data and data abstraction. As with compound procedures, functions, the main issue to be addressed is that of abstraction as a technique for coping with complexity, and we will see how data abstraction enables us to erect suitable abstraction barriers between different parts of a program.
We will see that the key to forming compound data is that a programming
language should provide some kind of We will then augment the representational power of our language by introducing symbolic expressions—data whose elementary parts can be arbitrary symbols rather than only numbers. We explore various alternatives for representing sets of objects. We will find that, just as a given numerical function can be computed by many different computational processes, there are many ways in which a given data structure can be represented in terms of simpler objects, and the choice of representation can have significant impact on the time and space requirements of processes that manipulate the data. We will investigate these ideas in the context of symbolic differentiation, the representation of sets, and the encoding of information. Next we will take up the problem of working with data that may be represented differently by different parts of a program. This leads to the need to implement generic operations, which must handle many different types of data. Maintaining modularity in the presence of generic operations requires more powerful abstraction barriers than can be erected with simple data abstraction alone. In particular, we introduce data-directed programming as a technique that allows individual data representations to be designed in isolation and then combined additively (i.e., without modification). To illustrate the power of this approach to system design, we close the chapter by applying what we have learned to the implementation of a package for performing symbolic arithmetic on polynomials, in which the coefficients of the polynomials can be integers, rational numbers, complex numbers, and even other polynomials.
[1]
a procedure,function,it is doubtful that we would ever even think of the possibility of defining an operation such as sum. Moreover, insofar as performing the summation is concerned, the details of how term may be constructed from more primitive operations are irrelevant.
2 Building Abstractions with Data
| ||||||||
| You are visitor 01402639 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |