Saturday, February 23, 2008

Herbert Simon, Sciences of the Artificial

Simon includes in this book (MIT Press, 1969) some early remarks on the importance of representation in problem solving and design. He uses as a motivating example the game of "number scrabble", in which players alternately take digits from the collection {1,2,3,4,5,6,7,8,9}, seeking to secure three digits whose sum is 15. Simon notes that this game is isomorphic to tic-tac-toe: if the digits are arranged thus,
4 9 2
3 5 7
8 1 6
the triples whose sum is 9 are exactly the rows, columns, and diagonals that constitute wins in tic-tac-toe. Thus a change of representation for the game allows players of number scrabble to engage their preexisting knowledge of how to play tic-tac-toe. Though Simon doesn't make the connection explicit, the context of this discussion suggests that he might also have been thinking that the re-represented game engages spatial reasoning abilities that the original game does not.

Simon calls for further work on representations: "This view can be extended to all of problem solving: solving a problem simply means representing it so as to make the solution transparent. If the problem solving could actually be organized in these terms, the issue of representation would indeed become central. But even if it cannot-- if this is too exaggerated a view-- a deeper understanding of how representations are created and how they contribute to the solution of problems will become an essential component in the future theory of design. ... We have only a sketchy and incomplete knowledge of the different ways in which problems can be represented and much less knowledge of the significance of the differences. ... But even though our classification is incomplete, and perhaps superficial, we can begin to build a theory of the properties of these representations. (pp. 77-79)

Robert Rosen, Life Itself

In this book (Columbia University Press, 1991) theoretical biologist Robert Rosen describes a conception of modeling that is closely related to the framework of representational systems described here. His Figure 3H.2, here,

connects a "natural" system, N, with a "formal" system, F, by encoding and decoding maps, in such a way that the composite map 2+3+4 agrees with the map 1 within N. This is a horizontal presentation of the same relationships I've shown vertically, linking a target domain and a representation domain.

Friday, February 22, 2008

Layering and Branching

Representations form natural layered structures, with the representation of one system being the target domain of another, and so, as shown schematically here:

A common family of layers in computational representations connects entities in some target domain with numbers, the numbers with collections of bits, and the bits with physical structures of some kind. Here's an elaborated example of this, starting with sticks, in a target domain at the top:

This diagram shows branching, as well as layering: for a given target domain there can be more than one possible representation domain. For example, numbers can be represented by elements of a data type (double) in a language like C, or by voltages in an analog machine. Elements in a data type can be represented by blocks of bits, and bits can be represented by very different physical structures, like magnetic cores, at left, or circuits with more than one pattern of circulation of current, at right.

The usefulness of representations is greatly increased by these two kinds of structure, layering and branching. Layering means that representations often can be devised and thought about without knowing or caring about most of the layers in a structure. Thus I can use numbers in a program without knowing or caring how the bits used to represent the numbers are implemented.

Branching works with layering to create vital flexibility. In my career the actual representation of bits has changed completely, from magnetic cores to nests of tiny transistors, but as a programmer this change affects me only secondarily, through improvements in cost and performance. The investments in software I and many others made were not lost, even as the hardware structures used to represent them changed utterly.

Although this example doesn't show it, there is upward branching as well as downward branching. Upward branching shows up when the same representation domain is used with more than one target domain. Clearly, lots of things can be represented by numbers with addition as a combining operation, for example. Thus upward branching signifies multiple use of representations. Mathematical (and computational) structures get much of their usefulness from the fact that they can be used to represent lots of different things.

Layering and the Organization of Disciplines

Looking at bundles of layered structures one sees a tree with branches (or roots) at top and bottom:

The branches at the top radiate into all the corners of human endeavor, from management to chemistry, and beyond. The roots of the tree extend into the wide variety of physical structures that are used, way down at the bottom of all the layered structures, to implement the representations above them. The traditional discipline of computer science focuses on the structures in the trunk of the tree, largely independent of the branches above, that distinguish different applications, and at the same time largely independent of the roots below, that distinguish various possible technologies of implementation.

Mathematics also inhabits this middle zone, studying structures that are largely independent of their applications, above, and certainly independent of the layers below. Indeed, mathematics is different from computer science, or vice versa, largely in the demand in computer science that its representational structures actually be implemented, that is, that they be grounded, or at least groundable, in physical structures.

(Telecommunications is also in the trunk along with computer science and mathematics. A good part of this field concerns communication in a way that is disconnected from the content of communications, as worked out in layers above the communication system, and from the implementation, worked out in layers below, where it is worked out that a system is built from electric wires, or from optical fibers, or from radio transmitters and receivers.)

The fact that the disciplines can be sorted out in this way, by reference to layered representational systems, does not mean that there are important advantages in doing so. The success of tight collaborations between computer scientists and scientists in other disciplines, like those that have led to the explosion of computational biology, suggests the value of understanding multiple layers at the same time, in devising new and more useful representations. Looking down from traditional computer science, there have also been important gains in blurring the traditional software-hardware boundary, in devising implementations that are sensitive to attributes of programming languages, and vice versa.

Donald Campbell, in his "Ethnocentrism of the disciplines and the fishscale model of omniscience", 1969, showed how very simple organizational processes lead to disciplines withdrawing from boundary areas. Computer science may stand to gain even more than other disciplines from fighting this tendency, and actively developing its boundary areas.

Fun with Theory of Measurement

Suppose we have three sticks, and we want to know whether the first two, when stuck together end to end, are longer or shorter than the third. We all know that we can measure the first two sticks, add the numbers we get, and compare the sum to the number we get when we measure the third stick. Would it be possible to measure length in such a way that when we combine the lengths of the first two sticks we would multiply instead of adding?

The answer is, yes, it is possible. This picture shows the unusual kind of ruler we would use:

This shows how it works:
Notice that the null stick has length 1 with this ruler. A little thought shows that this must be true: the null stick is the identity for putting sticks together, and so its measure must be the identity for the operation we use for putting lengths together.

Now that you see you can use multiplication rather than addition to combine lengths, do you think we could use subtraction?

The answer is that we can't. Putting sticks together is commutative, where comparison is concerned: it doesn't matter which stick we start with when putting them together. But subtraction is not commutative. So we can't use subtraction to represent putting sticks together.

Sunday, February 17, 2008

Representation and Cost

The point of a representational system is to move work from the target domain into the representation domain, where it can be done more easily, or more accurately, or better in some other way. I'll refer to the complex of issues that arise here (speed, effort, etc.) under the general heading of cost.

Mackinlay's thesis, cited in the previous post, distinguished two aspects of representations, expressiveness and effectiveness, in a way that illustrates the importance of cost. Expressiveness refers to the logical adequacy of something in a representation domain to capture the structure of a target domain. Mackinlay and Genesereth provide a nice example of an expressiveness failure, pointing out that the relation nested-within between closed contours in a diagram can't be used in general to represent contiguity of geographic regions like states or provinces, because nested-within is transitive, and contiguity is not. So expressiveness is a mathematical constraint on representational systems.

Effectiveness, on the other hand, refers to the ease and accuracy with which a human judge can extract correct answers from a visualization (the kind of representational system Mackinlay addressed.) This diagram shows three bar graphs that might be used to represent the fuel economy of two cars, as in the example in the last post:

The three representations are equally expressive: in each the yellow bar is longer than the red bar. But the representations differ considerably in effectiveness: human viewers find it easy to compare the lengths of bars when the bars are parallel and base-aligned, and only chart A has these attributes.

We can generalize the considerations in effectiveness to a much broader range of situations, including ones in which human perceptual judgments play no or little role. In many situations where computational representations are used, crucial operations in the representation domain are carried out automatically, and the relevant considerations in evaluating the representational system center on the cost of carrying out the operations by machine. The value of the representational system may hinge on how rapidly the needed operations can be carried out, and whether or not adequate memory is available, on a machine with an acceptable price.

Cost of creation, maintenance, and use.

Another kind of generalization considers costs beyond those incurred in using a representational system to answer some particular question. A system that provides fine answers at low cost will not be useful if is very expensive to create, and if this first cost cannot be amortized over enough usage. Thus in many situations the cost of creating a representational system for a given problem or family of problems will be an important consideration, motivating improvements in the technology of creating representational systems such as programming languages that can more easily be applied in connection with various target domains.

Another practical problem with computational representations is maintenance, the work required to modify a representational system so that it continues to support a shifting portfolio of work in a target domain that also shifts over time. Famously, the cost of maintenance commonly exceeds the cost of initial creation for many computational representational systems.

Cognitive dimensions analysis, as developed by Green, Petre, Blackwell, and others (see, provides useful insight into the aspects of representations that determine costs of creation and maintenance, and I'll return to this subject below, when discussing the role of programming languages in representational systems.

Approximation and cost.

In the introductory post I said that the results obtained by moving work into the representation domain have to agree with those that would have been obtained by staying in the target domain. That's not quite true. The results only have to be "good enough", or "close enough", or "approximately correct". But what do these criteria really mean?

The crux is that the cost of the path to an ultimate result in the target domain that detours through the representation domain has to be less than that of the cheapest available path that stays in the target domain. The results obtained from the work in the representation domain are "good enough" just when the incremental costs, of all kinds, associated with any difference between these results and those that would have been obtained by staying in the target domain, are less than the savings realized by moving work into the representation domain.

For example, suppose in the situation with the log and the chasm that we aren't able to measure the log and chasm with complete accuracy (as will always be the case.) Using measurement, and moving the work of comparing the log and chasm into the representation domain of numbers, is nevertheless worthwhile, as long as the inaccuracy doesn't increase by much the probability of an expensive failure, when we act on the results of the measurement process, in placing or not placing the log across the chasm. How much error is acceptable? Depends on the many practicalities of the situation: Are there other logs available if we drop one into the chasm? How soon do we need the bridge? There's the further consideration that we can often tell whether measurement error is likely to matter, when we see the results: if the log measures much longer than the chasm, we don't worry about small errors.

These multiple practicalities suggest that we can't expect too much from a purely formal treatment of the "correctness" of a representational system. It's clearly much too strong a condition that the mappings from input to result in the target domain, and from input into the representation domain, over to a result in the representation domain, and then back into the target domain, strictly commute, in the parlance of category theory, though category theory may provide some useful insight. I'll return to category theory in a later post.

Saturday, February 9, 2008

Getting started

The mantra of this blog is, "computational systems are representational systems".

The aim is to provide a view of what computer science is all about. We computer scientists haven't been very good at explaining the intellectual basis of our field, and this may be one of the reasons we are struggling to interest students, and potential collaborators, in our field, even while the importance of computing in all aspects of life is growing by leaps and bounds.

I've been developing the representational view of computing for a while now, giving talks and having encouraging conversations with folks at conferences, and the blog is a way to spread the ideas around, and get feedback, pending the Big Paper, which of course will be available "real soon now." If you want to read more, while the blog takes shape, you can find some notes, and a link to a talk kindly recorded by the folks at the University of Toronto Faculty of Information Studies, on my website, (what's there are earlier versions of the ideas.)

Why do we need to work on what computer science is about? Jeanette Wing's influential paper on "computational thinking", and follow-on activities (see sets out the challenges. After a stimulating conference session on enrollment problems in CS at Microsoft Research a couple of years ago, one of the participants stood up at the closing to express enthusiasm, saying something like, "It's been great talking about how we can communicate better... we all need to get the word out about the key ideas in the field...", and then caught himself in midstream, "... but I'm not sure we know what they are!" In one of my favorite books, "Python Programming: An Introduction to Computer Science", John Zelle says, "[T]he fundamental question of computer science, is 'What can be computed?'" I don't agree! This question gets at little or nothing of why computer science is so important to all kinds of people doing all kinds of things. The importance of computing is what we need to explain.

Computational systems are representational systems.

Computational systems are important because they are used to represent all kinds of things people care about, and representations are really useful. Further, computational representations have a number of properties that make them especially useful.

So, what is a representational system? There's some theory of representation that we can draw on, best developed in the case of measurement systems, a special case. For theory of measurement see the three volume Foundations of Measurement, by Krantz et al., recently reissued in paperback; for the broader theory of representations, see papers by Mackinlay and Genesereth, including Mackinlay, J. D. (1986) Automating the Design of Graphical Presentations of Relational Information. ACM Transactions on Graphics, 5(2, April), 110-141.

A representational system consists of a target domain, in which there is something we want to accomplish, and a representation domain, with mappings connecting them. The point of representation is that we map work in the target domain into work in the representation domain, where it can be done more easily, or faster, or better in some other way. Then the results are mapped back to the target domain, where we need them.

The kind of representational system that’s best understood is measurement systems. You’ve been using them all your life, but if you are like most people you’ve never thought about how, let alone why, they work. Let’s look at an example.

Suppose we have some logs, and a chasm we want to bridge. We need to know whether one of the logs is long enough to bridge the chasm. We could answer this question by picking up the log, moving it over the chasm, and seeing whether it reaches the other side. This involves actual work: picking up the log, and moving it. The work could be hard, if the log is heavy, and it could be dangerous, if the chasm is deep. We might need to rig up some kind of derrick to swing the log over the chasm. It would be bad to go to all this trouble and then find that the log is too short.

We all know that there’s a way to avoid this possibility. We measure the log, and we measure the chasm, and we compare the measurements. If the number we get when we measure the log is bigger than the number get when measure the chasm, then the log will reach.

In this example, the target domain contains the logs and the chasm. The representation domain is numbers: when we measure the length of something we get a number.

Our question in the target domain is “Will this log reach across the chasm?” We map the question “Will this log reach across the chasm?” onto a question in the representation domain: “Is this number bigger than that one?” Finally, we map the answer we get in the representation domain, yes or no, onto an answer in the target domain, also yes or no (that mapping is easy.) Here’s a diagram showing all this:

The gain from doing all this (which we would normally do almost without thinking) is big. We don’t have to move the log!

For this or any other measurement system to work, the answer we get when we map our question into the representation domain, and then map the answer back to the target domain, has to be the same as the answer we would have gotten if we had done the work to answer the original question in the target domain. After all, how would we feel if we measured the log and the chasm, decided that the log was longer than the chasm, did all the work to swing the log across, and found out that it didn’t reach? The measurement systems we all rely on always do work, and if they appear not to, we assume we made a mistake of some kind, like not pulling the tape measure tight when we used it to measure something.

Measurement is interesting, and exceedingly important, but we are after even bigger game. Measurement systems are representational systems in which the representation domain is a fairly simple mathematical structure, like numbers. But in many representational systems the representation domain isn’t a simple mathematical structure, or a mathematical structure of any kind. For example, consider a simple bar chart, used to represent the fuel economy of cars. Here’s a diagram of this representational system:

Here the representation domain isn’t a mathematical structure, it’s marks on a piece of paper, or a pattern of colored dots on a computer screen.

In the representational systems we'll mainly be concerned with, the representation domain is neither simple mathematical structures, nor marks on paper (though patterns of dots on a computer screen come in around the edges.) Rather, our representational domains will contain computational stuff, whose nature will become clearer as we discuss it. Computational stuff has wonderful properties, so wonderful that computational representations are in use in virtually every sphere of human endeavor. As stressed earlier, the whole point of having a representation is to be able to do something more easily, or cheaper, or faster, or better in some way, and computational representations often have huge advantages over others.

Like the advantages of measurement, the advantages of computational representations often go unnoticed, even when we use them. Here are a few examples.

• If I create a computational representation of something, someone can access that representation, and use it to do work, on the other side of the world, incredibly quickly, and at incredibly little cost.

• Computational representations can easily be accessed in other times, as well as in other places. That is, they are easy and cheap to store and retrieve. The contents of all the books in all the libraries in the world can be stored in computers that fit in two standard shipping containers, each 20x8x8 feet; see

• Many operations on computational representations can be automated, meaning that they can be carried out by a machine, rather than a person. This often offers huge advantages in speed, accuracy, and cost.