4 Names
How can literature work in translation? In some ways it’s surprising that an excellent book in one language can still be an excellent book in a completely different language. In fact, it is hard to find an example of a book that is genuinely untranslatable. I initially thought that Dr. Seuss’s The Cat in the Hat or James Joyce’s Finnegans Wake would be examples; but in fact there is a highly praised French translation of The Cat in the Hat, and a Chinese version of the first third of Finnegans Wake has been a surprise hit. In most cases there appears to be a core set of ideas, characters, and plot that can be rendered effectively into a language very different from the language in which it was originally written. Of course, there are likely to be some elements that work poorly in the new language, but there may occasionally be elements that work better in the new language due to happy accidents or the skill of the translator. For example, in the Asterix books, the (translated) English name Dogmatix is funnier than the French original Idefix. Both have the connotation of single-mindedness … but since this is the name of Asterix’s dog, the English version is appropriate in a way that the French version can’t match.*
There is a similar sense in which computation can happen in different models—in translation, if you like—while nevertheless retaining some of the same essential qualities. Those shared qualities can be the same effects or lack of effects, the same limits, and so forth, along with some untranslatable bits and/or happy accidents of improvement. In this chapter we redevelop our ideas about steps, but in a new way. The basic step of this new approach is to substitute a value in place of a name.
This chapter has more notation than any other. If you’re a person who is comfortable with mathematical notation or you like to play word substitution games, there’s probably nothing in here that will worry you. But if you’re not all that comfortable with the notation or the way the chapter goes, feel free to skip ahead at any point to the next chapter. You’ll be missing some of the “local flavor” of computing in this new approach, but you won’t miss anything fundamental.
What’s in a Name?
In everyday life, we usually don’t have too much trouble distinguishing a map from the terrain that the map describes. Usually the map is a different material: it’s printed on paper, or it’s a display on a mobile phone. Meanwhile, the actual terrain is land, roads, buildings. Usually the map is also a different scale: we might fit whole neighborhoods or cities into just a few inches, whereas the terrain of interest might well take up miles.
Just as we are usually not confused between the map and the terrain the map represents, we usually don’t get confused between names and what’s named. Our typical uses of names and quotation in speech or writing are usually not very complicated.
Computer science involves issues of names and naming to an extent that may be surprising. The naming systems turn out to be more elaborate than those used in ordinary language; in addition, the “material” or “stuff” of which names are made is often very similar to the “material” or “stuff” of what’s being named. In contrast to our everyday experience, in this domain there is a chronic risk of confusing map with terrain, or confusing the name with what’s named.
Let’s start with a simple case. Barack Obama is the name of a man. We can use the name as a kind of substitute for the man (see figure 4.1).
A name and the named person.
If we didn’t know his name, or didn’t want to use his name, but he was in the vicinity, we might point at him or use a roundabout construction like “that man standing over there” (see figure 4.2).
Gesturing instead of using a name.
In a written document like this one, we can use a picture as another kind of “naming” to indicate a particular person we’re talking about. In a sense, our picture is a name for Barack Obama, since we can’t actually include the real person in this book.
Here’s another example: the Arabic numeral 5, the Roman numeral V, and the hashmark consisting of four vertical marks crossed by a diagonal mark all represent the same number (see figure 4.3).
Three different names for five.
But they are all names for the number, rather than being the number. The number itself is some kind of abstract concept of “fiveness,” not the particular marking on the page with this shape: 5.
Even if Barack Obama is standing right next to us as we speak, we can’t express a statement like “Barack Obama was the first U.S. president who was raised in Hawaii” without using some kind of name. Instead of saying “Barack Obama” we could gesture at the man standing next to us, but that’s just a different kind of name. We can’t pick up the person physically and slot him into the opening phrase of the sentence: a physical human being is the wrong kind of entity to be in a sentence, just as the name “Barack Obama” is the wrong kind of entity to be tucked into bed with his wife at night.
Quoting
Let’s push the naming ideas one more level to distinguish between Barack Obama and “Barack Obama” (the quotes here are crucial). Consider these two correct sentences:
Barack Obama was the first U.S. president raised in Hawaii.
“Barack Obama” is twelve characters long.
and contrast them with these two structurally similar but incorrect sentences:
“Barack Obama” was the first U.S. president raised in Hawaii.
Barack Obama is twelve characters long.
Some people notice this kind of error and find it irritating. Structurally, the sentences are still acceptable: they are both still simple predicate sentences, we have just swapped the subjects. But the incorrect versions have mismatched meanings. The quotation vs. usage structure is wrong, and strictly speaking the sentences make no sense. The first one claims that a string of characters could serve as president, while the second claims that a person can be measured in terms of text.
Remember that we aren’t discussing these issues for grammatical purity: we’re going to further develop names vs. what-is-named to illuminate some important ideas of computer science. It’s tempting to push past this topic while waving our hands and saying, “everyone understands names.” But most people don’t really understand names—or at least they don’t understand names once the naming system is more complicated than everyday usage.
Our example sentences show the use and misuse of quoting. In principle, we can keep applying the quoting mechanism as long as we want. In practice, it’s only workable for a couple of levels when people are using languages like English to communicate with each other.
Computer scientists would call English and other similar languages natural languages. Although we’re starting with examples of quotation in English, we’ll soon shift to dealing with artificial languages. The artificial languages are simpler and more regular in their structure because they are deliberately constructed that way. The issues of naming and substitution may still seem a little tricky, but it’s important to be aware that natural languages have some additional complexity that we won’t try to tackle.
The following example already feels confusing and contrived to many readers:
‘“Barack Obama”’ is a way of quoting the name of Barack Obama by adding a double quote on each side: “Barack Obama.”
In this sentence, there are three occurrences of the same president’s name text, each a little different:
• The first occurrence of the president’s name is a nested quote: we are talking about how we can quote a name. This usage is unusual because we don’t often see quotes inside quotes, although it does sometimes occur for reasons other than contrived examples in books.
• The second occurrence is unquoted because it is a reference to the person (although it is embedded in a phrase, “the name of Barack Obama” …which effectively quotes it!).
• The third occurrence is another example of quoting the name.
Interestingly, this rather elaborate construction doesn’t actually depend in any way on whose name is being used. We could equally well have said something like
‘“George Bush”’ is a way of quoting the name of George Bush by adding a double quote on each side: “George Bush.”
The resulting sentence is equally true as long as we somehow substituted the exact same person’s name throughout.
An ordinary person’s thought process might simply move on from here to some other topic, but a mathematician or a computer scientist is likely to think that it might be handy to have a way of talking about these patterns. As a bonus, figuring out a way to express these common patterns and perform the substitution leads us into computation.
Leads us into computation? Where did that come from? Weren’t we just wandering down this path so we could be ultra-hyper-careful about what is a name vs. what is the stuff that’s being named?
Well, yes, but one view of computation is that it’s fundamentally about repeated renaming. We learned in previous chapters about “step-taking machinery” and a kind of mechanistic perspective on computation. In that approach, there’s some kind of a machine that just repeatedly takes a step. Computation is what happens when the machinery is operated according to a plan—what we called the program—and the operation of the machinery according to the program is the process.
But just as 5 and V are different but equally valid ways of referring to an underlying “fiveness,” there’s another, equally valid, view of computation that starts with a kind of renaming game. There are still steps to the computation, but now those steps are the simple renamings or substitutions that occur. The program is the text that we start with, and the process consists of the transformations of the text that happen while following the rules of the substitution game.
Sentence Patterns
Let’s take this complicated sentence that we previously mentioned:
‘“George Bush”’ is a way of quoting the name of George Bush by adding a double quote on each side: “George Bush.”
and start playing the substitution game on it. Our reward for going down this path is that we will invent our way into computation along the way.
The substitution game is like a kind of algebra with text. Recall that in high-school algebra a variable like x might occur several times in an equation. Perhaps x was the key answer we were trying to find, or perhaps it was just some intermediate answer that helped us on the way to the final answer. In our current context, looking at naming and named objects, we can think of a variable like x as a name for its value. For our complicated sentence, we’ll use x as a replacement for the name of a president and get the generalized pattern:
‘“x”’ is a way of quoting the name of x by adding a double quote on each side: “x.”
This sentence might be true in some sort of technical/philosophical way—but it doesn’t feel very useful, or make a lot of sense. That’s OK, because we were just trying to capture a pattern. This sentence isn’t really intended to be a meaningful sentence itself, it’s more like a sentence-generator: something we could use to produce the Barack-Obama-version and the George-Bush-version (and many others beside).
An alternative way of thinking about this new sentence is that it’s been freeze-dried like instant coffee. It needs to be reconstituted with the removed ingredient (the real text), just as instant coffee needs to be reconstituted with hot water. (If this analogy doesn’t work for you, just ignore it.)
It would be helpful to have some kind of a marker to warn the reader that this sentence needs to be reconstituted. Because of how we developed the sentence just now, we know the version with x’s isn’t really supposed to be understandable. But if we just ran across it somewhere in a book, we might not recognize it as a sentence-generating pattern. We might instead think that it was trying to express some deep philosophical insight about x, and waste time trying to understand it in those terms.
Lambda
Rather than invent a new kind of marker, we’ll use the same notation that computer scientists sometimes use in a similar situation, using the Greek letter lambda (λ). If we write “λx.” (pronounced “lambda ex dot”) in front of our pattern, it effectively means “in the following text, x is just a placeholder for something that will be supplied later.”
To get a handle on this new notation, let’s use it in really simple cases first. Let’s suppose that we want to capture a sentence pattern that just “doubles” a piece of text: so if we put in “blah” we get out “blahblah” and if we put in “Barack Obama” we get out “Barack ObamaBarack Obama.”
Here’s a doubling pattern, which delivers a new text containing two copies of the text we give it:
λx.xx
Let’s first say this out loud so it doesn’t seem alarming: “lambda ex dot ex ex.” Then let’s consider what it means. The dot divides this line into the body to the right of the dot, and the formal parameter to the left of the dot. The formal parameter (or just formal) tells us the placeholder name that gets substituted—in this case, x. The body tells us the text in which the substitution occurs—in this case, xx. The whole thing taken together—lambda, parameter, dot, body—is called an expression.
Figure 4.4 shows those parts labeled on the same expression.
The parts of an expression.
So we know that the x’s that occur in the body will be replaced by something else. What is substituted for x? Whatever is supplied to the expression. The expression doesn’t care exactly what the substitution is, it works pretty much the same way regardless of what’s supplied.
What does it mean to “supply” something? Well, you just write whatever you are supplying to the expression right after it. Here’s an example where we are supplying the letter a to our doubling expression:
λx.xx a
The stuff to the left of the space is just the exact same lambda-expression we wrote before. The stuff to the right of the space is just the letter a.
We’re usually more interested in the result of this kind of combination, rather than just writing the expression. We can draw a rough analogy by observing that it’s correct but unhelpful to say that (237 + 384) has the value (237 + 384). Most people are more interested in knowing that its (final, simplified) value is 621. We’ll introduce a right arrow “→” to indicate that the stuff on the left side of the arrow can be simplified or reduced to the stuff on the right side of the arrow.
λx.xx a → aa
Here’s another example:
λx.xx abc → abcabc
These first examples used only textual joining (sometimes called concatenation), where we put two pieces of text next to each other and treat them as a single piece of text afterward. This notation is also powerful enough to express arithmetic—although we won’t be concerned with exactly how to do that. Instead, we’ll just take advantage of our knowledge that it can be done to write some examples using simple arithmetic operations. For example, we can write a simple add-one expression (what computer scientists would call an incrementing function). It just adds one to whatever number it is given:
λx.(x + 1)
And then consider what the results are for a couple of uses of the function:
λx.(x + 1) 3 → 4
λx.(x + 1) 17 → 18
Finally, here’s an even simpler example, what computer scientists call an identity function: whatever you supply to it is also what comes out:
λx.x
Here’s an example of using the identity function:
λx.x 2 → 2
With this notation we can also say things like
λx.x “Barack Obama” → “Barack Obama”
We can see from these examples that this identity function doesn’t care whether it’s applied to numbers or pieces of text.
The amazing thing to keep in mind when learning about names is that the world of computation that’s reached via names is identical to the world of computation that we’ve already reached via steps. Whether you think of computation as programs running on machines or names being replaced by other names, it’s all the same “computingness” underneath.
Simple name substitution is generally pretty easy to understand. The next level of complexity in using names is often a little harder to grasp, so we’ll approach it from the angle of slightly silly humor.
* One reviewer of this book was unclear about why Dogmatix is a better name than Idefix, so I will spell it out: Dogmatix is a dog. Idefix is a chien. There is humor in the first coincidence but not in the second noncoincidence. I hope this explanation is helpful.