Tuesday, April 24, 2007

Abstraction, analysis, and patterns

In previous pieces (see abstraction), I discussed abstraction in computer science and mathematics. It has been suggested that what I'm really after is not abstraction at all but analysis. There may be something to that.

I'm not completely comfortable with the term analysis because it carries with it a sense of dissection rather than the discovering of the essence of something. Here, for example are the relevant senses from Merriam-Webster.
1 : separation of a whole into its component parts

2 a : the identification or separation of ingredients of a substance b : a statement of the constituents of a mixture

3 [the branch of mathematics referred to as analysis].

4 a : an examination of a complex, its elements, and their relations b : a statement of such an analysis

The sense of analysis that comes closest to what I mean by abstraction is sense 4.

Interestingly enough, Dictionary.com again comes up with a relevant definition.
a method of studying the nature of something or of determining its essential features and their relations: the grammatical analysis of a sentence.
This sort of analysis is something like what we call systems analysis, i.e., the analyzing of a problem domain prior to attempting to find a system that will solve a problem for that domain.

I was unable to find a good definition of systems analysis. Most of them were much too concrete. Wikipedia, however, has this entry for problem domain analysis.
the process of creating a model describing the problem to be solved.
This says that analysis is the creation of a model for some domain. Although that's a reasonable way of putting it, this only raises the question of how we want to define model.
An abstract model (or conceptual model) is a theoretical construct that represents something, with a set of variables and a set of logical and quantitative relationships between them. (Wikipedia)

A description of observed behaviour, simplified by ignoring certain details. (Free online dictionary of computing)

a system of postulates, data, and inferences presented as a mathematical description of an entity or state of affairs; also : a computer simulation based on such a system < climate models > (Merriam-Webster)

a simplified representation of a system or phenomenon, as in the sciences or economics, with any hypotheses required to describe the system or explain the phenomenon, often mathematically. (Dictionary.com)

A representation of something, often idealised or modified to make it conceptually easier to understand. (Biology-Online.org)
The problem with these definitions is their emphasis on simplification rather than on finding the essential elements of the thing being modeled. Perhaps a reasonable definition of model is
a representation of something in a well-defined language.
I like this definition, although it may include virtually any explication. It implies a three-fold division: the thing being modeled, the conceptualization of the thing, i.e., the conceptual model, and the representation of the conceptual model in a well-defined language.

Debora pointed out that studying mathematics is good way to learn how to do modeling in this sense — at least the sort of mathematics that one does when learning how to solve word problems. In doing word problems one is asked to translate a problem statement expressed in English into mathematical equations — and then to solve those equations. In effect, one is asked to build a model. Of course this isn't doing mathematics so much as learning mathematical modeling techniques — and then being asked to solve the equations that result from expressing a problem in terms of those modeling techniques.

It would be useful to computer science students to teach them mathematics in this way, i.e., as a way to model problem domains. In most mathematics courses, the use of the mathematical tools for modeling purposes tends to be taught as an afterthought or as an exercise. It would be much more useful (at least to computer science students and to most non-mathematics students) to teach the subject as modeling tools rather than as formal mathematics.

It would be even better if the modeling aspect were taught separately from the solving of the equations. There are many systems available that can solve equations once they are generated. It would be useful to teach mathematics to non-mathematicians by using those systems. The goal of the course would be to teach students how to use a mathematical modeling language as a way to characterize a problem. Once a problem were characterized, the tool would use the equations to help one understand the problem from various perspectives.

This would mean, for example, teaching a course in system dynamics to computer science students rather than teaching a course in partial differential equations. System dynamics could be taught much earlier and with far fewer mathematical prerequisites than today's courses in partial differential equations.

Of course, those students who wanted to know how the system solved the equations or how to build a system dynamics modeling system would have to learn the necessary mathematics. But for most computer science students, it would be quite valuable to learn how to express relationships in terms of partial differential equations even if they relied on software to solve or simulate the effects of those equations. This is analogous to the way we teach programming languages. We teach all students how to write in a programming language. Only some students learn how to write compilers.

I think that if mathematics were taught that way it would in fact help computer science students learn how to think more abstractly. Each such mathematical modeling framework would be another tool they could use to understand a situation from one or another abstract perspective.

Certainly learning a modeling language or framework is not the same thing a creating one, which is the true joy of abstraction. But the more modeling languages or frameworks one knows, the better one is likely to do when asked to analyze and understand a new problem.

In software we have developed the notion of a design pattern, which is, in effect, an approach to a particular kind of design problem. In software, we have also created the notion of refactoring, which means to extract out a feature of software that is more general than the particular problem being solved and use a generic version of that feature. When these two notions are used together, one gets a particularly powerful form of abstraction and modeling. An example will probably help.

Recursion is a technique for processing recursive data structures such as tree-structured graphs. One writes software that operates on a node of the tree and then calls itself to operate on the subnodes of that node. Thus one has to write the processing part only once and use recursion to have those processing steps applied to all tree nodes. At one time recursion was considered a sophisticated technique. Now it is taught in lower division computer science classes.

Still, recursion is a powerful programming technique. But the recursive aspects of it can be factored out into what is known as a visitor pattern. A visitor pattern is a software structure that accepts as one of its two inputs a tree and as the other a chunk of software. The visitor pattern traverses the tree and applies the processing software to each node. In this way the recursiveness has been factored out of the processing software — which now need not worry about anything but the processing steps — and encoded separately in the visitor pattern. Even more generally a visitor pattern can be applied to any data structure. It need not be a tree.

In this way we have separated the concerns (which is a common phrase in software these days) of the processing code from the data structure traversal code. In doing so we have created the visitor pattern abstraction. It is this sort of abstraction that seems to be particularly common in software. The more one studies software, the more one is able to separate concerns. Each time one does that, one has created a new abstraction. Perhaps because software deals with such a broad range of subject matter, there seems to be no end to the ability of computer science people to find new abstractions.

There is even a theorem to this effect. In algorithm information theory, it is undecidable whether a particular Turing machine is the most compact representation of a given string. There may always be a more abstract representation.

And speaking of separating concerns, the notion described above of teaching mathematics as a modeling language separates the concern of mathematics as a way of characterizing a problem domain from mathematics as a way of solving equations. It would be worthwhile (to computer science students at least) to separate those concerns.


The Home Gift Warehouse said...

Blessed is the man that walketh not in the counsel of the ungodly, nor standeth in the way of sinners, nor sitteth in the seat of the scornful.
But his delight is in the law of the LORD; and in his law doth he meditate day and night.
And he shall be like a tree planted by the rivers of water, that bringeth forth his fruit in his season; his leaf also shall not wither; and whatsoever he doeth shall prosper.
The ungodly are not so: but are like the chaff which the wind driveth away.
Psalms 1:1-4

Anonymous said...

Dear Russ,

Try both analysis and synthesis as the basis of abstraction.

Design Patterns are a poor man's guide to abstraction. Have a look at David Harland's and Hamish Gunn's work from the late 70's to the mid 80's for some interesting insights to abstraction.

Just as a side comment, study Forth or Factor or even Smalltalk as areas that frequently use factoring or refactoring for solution creation.

yours sincerely

Bruce Rennie
(God's Own Country Downunder)