Communications of the ACM
From the president
Computer Science Revisited
ACM Past President and Google Inc. Vice President and Chief Internet Evangelist Vinton G. Cerf
In a recent column, I questioned whether there was any "science" in computer science. This provoked a great many responses that provided some very valuable perspective. To the degree that some aspects of computing are subject to analysis and modeling, it is fair to say there is a rigorous element of science in our field. Computability, analytical estimates of work to factor numbers, estimates of parsing complexity in languages, estimates of the precision of computations, computational costs of NP-complete problems, among others, fall into the category I call "analytic" in the sense we can say fairly strongly how computational cost grows with scale, for example. In recent conversations with Alan Kay, Edward Feigenbaum, Leonard Kleinrock, and Judea Pearl, I have come to believe that certain properties contribute to our ability to analyze and predict behaviors in software space.
Alan Kay spoke eloquently at a recent event honoring Judea Pearl's ACM Turing Award. Among the points that Alan made was the observation that computing is not static. Rather it is a dynamic process and often is best characterized as interactions among processes, especially in a networked environment. The challenge in understanding computational processes is managing the explosive state space arising from the interaction of processes with inputs, outputs, and with each other.
In a recent discussion with Edward Feigenbaum, he noted that models used in hardware analysis are more tractable than those used in software analysis because what is possible in the "physical" world necessarily constrains the search for solutions. Software systems are designed and analyzed in "logical" space, in which there is far less structure to exploit in the analysis. However, the enormous computing speeds possible today, combined with some structuring of the software design space, might allow deep and effective analyses of software as yet unavailable to mathematical methods or human thought. He recalled how very fast search, structured by some knowledge of chess, allowed IBM's Deep Blue to defeat the world's chess champion Kasparov. In one game, Deep Blue, exploring hundreds of millions of possibilities in the analysis of a move, found a brilliant solution path, probably never before seen, that led Kasparov to resign from the game and lose of the match.
Structure that constrains state spaces is sometimes conferred through abstraction. Here we get to another key observation about the potential for scientific approaches to computer science. To the degree that abstraction eliminates unimportant details and reveals structure, abstraction is a powerful analytical tool. It strikes me that Chaos theory illustrates this notion because patterns emerge in this theory despite the apparent randomness of the processes it seeks to analyze. If programs and algorithms are subject to suitable abstraction, it may be possible to model them with adequate but abstract fidelity so as to render the model analyzable. An example is found in queueing theory in which complex processes are modeled as networks of queues. The models are analytic under the right conditions. Kleinrock made enormous contributions to network design and analysis through the construction of queueing theoretic models. His most famous contribution was the recognition that the state space explosion could be tamed by his Independence assumption in which the statistics of the traffic flowing through the network were regenerated at each node using statistically identical but independent variables.
Modeling is a form of abstraction and is a powerful tool in the lexicon of computer science. This leads me to a final observation illustrated by Judea Pearl's brilliant lecture on the use of Bayesian analysis to draw conclusions from problems involving probabilities rather than fixed values. Pearl's theories of causal reasoning in conditional probabilities are often aided by graph-like models linking the various conditional statements in chains of cause and effect. The diagrams make it possible to construct analytic equations that characterize the problem and make the solution computable. It struck me that Pearl's use of diagrams had an analogue in Richard Feynman's diagrams of quantum interactions. These diagrams are abstractions of complex processes that aid our ability to analyze and make predictions about their behavior. Pearl's diagrams may prove as powerful for science (not only computer science) as Feynman's have for quantum physics and cosmology.
I have come away from this foray into computer 'science' with several conclusions. The first is there really is science to be found in computer science. The second is abstraction and modeling are key to making things analytic. The third is there is a lot of complex detail in computer programs and collections of interacting programs that has not admitted much in the way of abstraction or modeling, rendering these complex systems difficult to analyze. Finally, I believe our ability to understand and predict software behavior may rest in the invention of better high-level programming languages that allow details to be suppressed and models to emerge. I hope Alan Kay's speculation will lead to serious improvements in the way we design and program computer systems.
©2012 ACM 0001-0782/12/12
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.
Comments
Qi Qi
I hope that functional programming languages would address this need for computer software's modeling and analytics.
Edward Lowry
Vint Cerf suggested that I post this message that I sent him on 14Jan13.
To: Vinton G. Cerf, ACM President
Subject: Abstraction Obstructed for 40 years
In your December CACM message, you say "Structure that constrains
state spaces is sometimes conferred through abstraction".
Yes. In fact it leads to an enduring practical optimum structure for basic
building blocks of information that is somewhat analogous to round wheels,
vertical pillars, flat mirrors, etc.
Thoroughly abstracting out extraneous complexity is a convergent process.
There gets to be little left. Resistance to serious simplification has resulted in
a failure to notice that the process leads to convergence of language
semantics in six dimensions:
1. simplicity of expression
2. fluency of expression
3. generality of subject matter
4. flexibility of data structures
5. modularity of information building blocks
6. technological stability in its underlying design.
In many contexts bits are a compelling choice of information building
block, but working with bits at a conceptual level is usually too complicated.
We may ask: What is the structure of building blocks of information
that are designed for maximum "modularity"? That is, maximum
simplicity in the expression of rich computer applications expressed in
language that uses those building blocks in the data representations.
My analysis of the consequences of such thorough elimination of
extraneous complexity ("Toward Perfect Information
Microstructures" on my web site) leads to convergence toward an
enduring optimum structure for building blocks of information that
are designed to be easily arranged. They can be illustrated as follows:
[ for diagram, see http://users.rcn.com/eslowry/inexcuse.pdf ]
This shows how the age of a person could be represented. The
objects are flexible and their tinker-toy style connections make
them easily arranged conceptually. The upper left dot connects to
the first person in a set and its side connector connects to the
next person in the set of two. Those provide for iterating
through sets and easy reference to sets of objects using plural
expressions.
I doubt that there is any publicly visible effort now to provide language
technology for precise information in any of those six dimensions which
is as advanced as was being designed at IBM 40 years ago. The lapse
can be documented fairly solidly up to 37 years (see the attachment).
[Attachment not included here. ESL]
In 1982 it was practical for me or colleagues at Digital Equipment Corp
to enter a statement in a very general programming, data base, and
modeling language for computer execution such as:
6 = count every state where populatn of some city of it > 1000000
I doubt that anyone today has routine access to facilities where precise
language provides comparable fluency.
The IEEE-USA leadership has acknowledged the delay in simplification.
In a Position Statement: "Upgrading the National Airspace System (NAS)"
adopted by the IEEE-USA Board of Directors, 17 February 2012
See www.ieeeusa.org/policy/positions/NatlAirspaceSystem0212.pdf
The fifth recommendation includes:
"Currently, all safety-related software has been developed using
computer language technology that has poor simplicity of
expression, compared to what was designed in the early 1970s, and
implemented in the early 1980s, by leading computer vendors".
Students everywhere are routinely taught how to arrange pieces of information
by educators who are unaware of pieces of information that are well-designed
to be easily arranged. Few people seem to doubt that, but so far, it has appeared
to be a disruptive and inconvenient truth that gets little response.
I am hoping you will revise your third conclusion that "there is a lot of complex
detail in computer programs and collections of interacting programs that has not
admitted much in the way of abstraction ...". The programs have admitted much
more abstraction than software leaders have acknowledged.
Many people have incentives to make other people's lives complicated. They
have been highly effective in obstructing progress in simplification and
abstraction for 40 years -- producing many disasters. Leadership that is able
and willing to break that pattern is badly needed. There has been little
public candor about the potential for simplification for a long time. A little
candor from you could go a long way. If software leaders were to visibly
notice that the FAA is redeveloping the air traffic control system using
language technology that was obsolescent in the 1970s, some disasters
might be averted. There is background on my web site, and I can provide more.
Edward S. Lowry
Bedford Mass
781 276-4098
[email protected]
http://users.rcn.com.eslowry
Displaying all 2 comments