## Metaphors in computing science 2

In Metaphors in Computer Science 1, I discussed some metaphors used when thinking about various aspects of computing.  This is a continuation of that post.

### Metaphor: A program is a list of instructions.

• I discussed this metaphor in detail in the earlier post.
• Note particularly that the instructions can be in a natural or a programming language. (Is that a zeugma?)  Many writers would call instructions in a natural language an algorithm.
• I will continue to use “program” in the broader sense.

### Metaphor: A programming language is a language.

• This metaphor is a specific conceptual blend that associates the strings of symbols that constitute a program in a computer language with text in a natural language.
• The metaphor is based on some similarities between expressions in a programming language and expressions in a natural language.
• In both, the expressions have a meaning.
• Both natural and programming languages have specific rules for constructing well-formed expressions.
• This way of thinking ignores many deep differences between programming languages and natural languages. In particular, they don’t talk about the same things!
• The metaphor has been powerful in suggesting ways of thinking about computer programs, for example semantics (below) and ambiguity.

### Metaphor: A computer program is a list of statements

• A consequence of this metaphor is that a computer program is a list of symbols that can be stored in a computer’s memory.
• This metaphor comes with the assumption that if the program is written in accordance with the language’s rules, a computer can execute the program and perhaps produce an output.
• This is the profound discovery, probably by Alan Turing, that made the computer revolution possible. (You don’t have to have different physical machines to do different things.)
• You may want me to say more in the heading above: “A computer program is a list of statements in a programming language that satisfies the well-formedness requirements of the language.”  But the point of the metaphor is only that a program is a list of statements.  The metaphor is not intended to define the concept of “program”.

### Metaphor: A program in a computer language has meanings.

A program is intended to mean something to a human reader.

• Some languages are designed to be easily read by a human reader: Cobol, Basic, SQL.
• Their instructions look like English.
• The algorithm can nevertheless be difficult to understand.
• Some languages are written in a dense symbolic style.
• In many cases the style is an extension of the style of algebraic formulas: C, Fortran.
• Other languages are written in a notation not based on algebra:  Lisp, APL, Forth.
• The boundary between “easily read” and “dense symbolic” is a matter of opinion!

A program is intended to be executed by a computer.

• The execution always involves translation into intermediate languages.
• Most often the execution requires repeated translation into a succession of intermediate languages.
• Each translation requires the preservation of the intended meaning of the program.
• The preservation of intended meaning is what is usually called the semanticsof a programming language.
• In fact, the meaning of the program to a person could be called semantics, too.
• And the human semantics had better correspond in “meaning” to the machine semantics!
• The actual execution of the program requires successive changes in the state of the computer.
• By “state” I mean a list of the form of the electrical charges of each unit of memory in the computer.
• Or you can restrict it to the relevant units of memory, but spelling that out is horrifying to contemplate.
• The resulting state of the machine after the program is run is required to preserve the intended meaning as well as all the intermediate translations.
• Notice that the actual execution is a series of physical events.  You can describe the execution in English or in some notation, but that notation is not the actual execution.

#### References

Conceptual blend (Wikipedia)

Conceptual metaphors (Wikipedia)

Images and Metaphors (article in abstractmath)

Semantics in computer science (Wikipedia)

## Metaphors in computing science I

Michael Barr recently told me of a transcription of a talk by Edsger Dijkstra dissing the use of metaphors in teaching programming and advocating that every program be written together with a proof that it works.  This led me to think about the metaphors used in computing science, and that is what this post is about.  It is not a direct answer to what Dijkstra said.

We understand almost anything by using metaphors.  This is a broader sense of metaphor than that thing in English class where you had to say "my love is a red red rose" instead of "my love is like a red red rose".  Here I am talking about conceptual metaphors (see references at the end of the post).

### Metaphor: A program is a set of instructions

You can think of a program as a list of instructions that you can read and, if it is not very complicated, understand how to carry them out.  This metaphor comes from your experience with directions on how to do something (like directions from Google Maps or for assembling a toy).   In the case of a program, you can visualize doing what the program says to do and coming out with the expected output. This is one of the fundamental metaphors for programs.

Such a program may be informal text or it may be written in a computer language.

#### Example

A description of how to calculate $n!$ in English could be:  "Multiply the integers $1$ through $n$".  In Mathematica, you could define the factorial function this way:

fac[n_] := Apply[Times, Table[i, {i, 1, n}]]

This more or less directly copies the English definition, which could have been reworded as "Apply the Times function to the integers from $1$ to $n$ inclusive."  Mathematica programmers customarily use the abbreviation "@@" for Apply because it is more convenient:

Fac[n_]:=Times @@ Table[i, {i, 1, 6}]

As far as I know, C does not have list operations built in.  This simple program gives you the factorial function evaluated at $n$:

j=1;  for (i=2; i<=n; i++)   j=j*i; return j;

This does the calculation in a different way: it goes through the numbers $1, 2,\ldots,n$ and multiplies the result-so-far by the new number.  If you are old enough to remember Pascal or Basic, you will see that there you could use a DO loop to accomplish the same thing.

#### What this metaphor makes you think of

Every metaphor suggests both correct and incorrect ideas about the concept.

• If you think of a list of instructions, you typically think that you should carry out the instructions in order.  (If they are Ikea instructions, your experience may have taught you that you must carry out the instructions in order.)
• In fact, you don't have to "multiply the numbers from $1$ to $n$" in order at all: You could break the list of numbers into several lists and give each one to a different person to do, and they would give their answers to you and you would multiply them together.
• The instructions for calculating the factorial can be translated directly into Mathematica instructions, which does not specify an order.   When $n$ is large enough, Mathematica would in fact do something like the process of giving it to several different people (well, processors) to speed things up.
• I had hoped that Wolfram alpha would answer "720" if I wrote "multiply the numbers from $1$ to $6$" in its box, but it didn't work.  If it had worked, the instruction in English would not be translated at all. (Note added 7 July 2012:  Wolfram has repaired this.)
• The example program for C that I gave above explicitly multiplies the numbers together in order from little to big.  That is the way it is usually taught in class.  In fact, you could program a package for lists using pointers (a process taught in class!) and then use your package to write a C program that looks like the  "multiply the numbers from $1$ to $n$" approach.  I don't know much about C; a reader could probably tell me other better ways to do it.

So notice what happened:

• You can translate the "multiply the numbers from $1$ to $n$" directly into Mathematica.
•  For C, you have to write a program that implements multiplying the numbers from $1$ to $n$. Implementation in this sense doesn't seem to come up when we think about instruction sets for putting furniture together.  It is sort of like: Build a robot to insert & tighten all the screws.

Thus the concept of program in computing science comes with the idea of translating the program instruction set into another instruction set.

• The translation provided above for Mathematica resembles translating the instruction set into another language.
• The two translations I suggested for C (the program and the definition of a list package to be used in the translation) are not like translating from English to another language.  They involve a conceptual reconstruction of the set of instructions.

Similarly, a compiler translates a program in a computer language into machine code, which involves automated conceptual reconstruction on a vast scale.

#### Other metaphors

• C or Mathematica as like a natural language in some ways
• Compiling (or interpreting) as translation

Computing science has used other VIM's (Very Important Metaphors) that I need to write about later:

• Semantics (metaphor: meaning)
• Program as text – this allows you to treat the program as a mathematical object
• Program as machine, with states and actions like automata and Turing machines.
• Specification of a program.  You can regard  "the product of the numbers from $1$ to $n$" as a specification.  Notice that saying "the product" instead of "multiply" changes the metaphor from "instruction" to "specification".

#### References

Conceptual metaphors (Wikipedia)

Images and Metaphors (article in abstractmath)

Images and Metaphors for Sets (article in abstractmath)

Images and Metaphors for Functions (incomplete article in abstractmath)