A conversation made of strings

The night shift in the last chapter left a question open: which country shook most often? The answer sits in the seventh field of the catalog, and it is text, not a number: “125 km SE of Petropavlovsk-Kamchatsky, Russia”. The country is the piece after the last comma. To cut it out, you need to handle text as confidently as a list of numbers.

We’ll cut out the country in the first section and then build a conversation partner out of strings. In 1966 a program that had nothing but a set of templates talked with people so well that they told it about their families and their fears. We’ll write our own in five steps, and it will give the same four replies the original gave in 1966. By the end of the chapter you’ll be able to talk to it. Last of all we’ll answer the course’s first big question: how does a program print itself?

The country after the comma

A string is a sequence of characters, and everything you know about lists works on it: length, indices from zero, negative indices, slices, the in test, a loop over the items. The items of a string are single characters, which are themselves strings of length one.

For strings, in can do more than for lists: it finds any substring, a piece that runs without gaps. And split cuts a string at a separator and returns a list of the pieces. The last piece is the country. We could instead find the position of the last comma and take a slice after it, but that road hides a trap.

The method rfind searches for a substring from the end and returns its position, or −1 if it finds nothing. The Carlsberg Ridge in the Indian Ocean has no comma, comma is −1, and the slice place[1:] quietly bites off the first letter. No error, wrong answer. Without a comma, split returns a list of one string, and the last piece is the whole name. Remember: the −1 from find and rfind doesn’t mean “nothing.” It is a perfectly good index, the index of the last character.

Now we can count quakes by country. We have no dictionaries yet. In the last chapter the magnitude counters lived in one list, and the magnitude itself served as the index; a country can’t be turned into an index, so we’ll keep two parallel lists, one of names and one of numbers.

Indonesia leads by a long way: 1,883 quakes in eleven years. Italy, where earthquakes keep making the news, got 19, and our method missed one more, recorded as “central Italy”, with no comma. Data in the wild is full of inconsistencies like this: in our catalog more than one row in four, 5,231 of 19,073, has no comma at all, mostly quakes out at sea, where there is no country to name.

The last line of the program keeps the table straight. After the colon inside the braces of an f-string you can give the width of the field as well as the number of decimal places: :<10 means ten characters aligned left, :>5 five aligned right. And '#' * 31 repeats a string the way [0] * 36 repeated a list, which gives the bars.

The method index looks for an item’s position in a list, walking it from the start every time. With eight countries that costs nothing. If we wanted to count all 337 different pieces after the last comma (countries, states, stretches of ocean), two parallel lists would no longer do. We’ll come back to that at the end of the chapter.

Cambridge, 1966: a doctor made of templates

The replies have no question marks. The user wasn’t allowed to type one either: on MIT’s time-sharing system a question mark deleted the line. Under each line of the table is the word our own ELIZA will catch and the reply it will give. There is no understanding in the third reply: the program found the word “my,” took the rest of the sentence and swapped the pronouns, “my” for “your,” “me” for “you.” The person does everything else, filling in the meaning. We need five skills to reproduce these four replies: bring text to one form, find keywords in it, turn “I” into “you,” build a reply from a template and keep a conversation going.

Step 1. A string can’t be changed

People type “I feel,” “i feel” or “I FEEL!!!” and expect the program to understand them all the same way. The first thing ELIZA does is bring the sentence to lower case and cut the punctuation off its ends. Strings have the methods lower and strip for that. Watch what becomes of the original string.

lower didn’t change s: it built a new string and returned it. All string methods work this way: lower, upper, strip, replace. An attempt to replace a single letter ends in an error: strings, like numbers and tuples, are immutable. To “change” a string, you build a new one and move the name onto it: s = s.lower(). After the lists of the last chapter, which changed in place and got us into trouble, this comes as a relief. Nobody can spoil a string that two names point to.

Try find in the microscope as it stands: “me” turns up at position 2, inside “Sometimes.” A word that isn’t there gives −1. Try strip on a string with the exclamation mark in the middle: strip trims only the ends. And look closely at split() without an argument: it cuts at any run of spaces, however long, and throws away the empty pieces. It is the usual way to break a sentence into words.

Step 2. Keywords

Next, ELIZA has to spot a word in the sentence that it has a reply for. The rules are handy to keep as a list of “key, reply” tuples, like the catalog records of the last chapter. Order matters: the first rule that fits wins, so the more specific rules go higher up.

A key only has to match the beginning of a word: “mother” also fits “mothers” and “mother’s.” Words change their endings, and searching for the start of a word is the simplest way around that. The last reply shows the catch, though: “smother” contains “mother,” and ELIZA asks about the family of someone who was complaining about their friends.

The cure is to look for the key at the start of a word. Every word in the sentence has a space before it except the first, so we put a space before the first one too and search for " " + key. Then “ mother” is found in “ my mother phones”, but not in “ my friends smother”. The method find returns the index where the substring it found begins: we’ll need the key’s position in step 4.

Step 3. I and you

The most striking thing about ELIZA is the third reply of the 1966 conversation, where “Well, my boyfriend made me come here” comes back as “Your boyfriend made you come here.” The pronouns have to be swapped: “I” for “you,” “my” for “your,” “me” for “you,” and back again. The first tool that comes to mind is the method replace, which replaces one substring with another.

Two traps at once. First, replace doesn’t know where words end: “i” sits inside “think,” “it,” “is,” “time” and “visit,” and out come “thyounk”, “yout” and “vyousyout”. Second, the replacements run one after another: “me” became “you,” and the next line turned that “you,” along with the one that was there from the start, into “me.” Both pronouns came out as “me,” like the botched swap of tea and coffee in Chapter 2.

One technique gets around both traps: cut the sentence into words with split, decide once for each word what to replace it with, using a table of swaps, and put the words back together. Gluing them back together is the job of the method join: you call it on the separator string, and it glues a list of strings, inserting the separator between them.

The notation " ".join(words) looks inside out at first: we’re gluing a list, yet we call the method on a space. The logic goes like this. Only strings can be glued, so the method belongs to a string, the one that goes between the pieces, be it a space, a hyphen or the empty string. split and join undo each other. Now it’s your turn.

Step 4. Templates

The reply “Your boyfriend made you come here” is built from two parts: the word “Your,” which the rule knows, and the rest of the sentence after the key “my,” which came from the person and went through the mirror. A slice cuts out the rest: if the key was found at position pos, the rest begins after it. The reply template is a string with a hole, {}, and the method format fills it in.

Here is how to read the slice text[pos + 1 + len(key):]. Position pos holds the space before the key, pos + 1 the key’s first letter, and len(key) letters later the key ends. Everything after that is the rest; strip(" ,") trims the spaces off it, and a comma too, should the person put one after the key. Calling repr(rest) showed the rest in quotes, so you can see where it begins and ends. We’ll come back to this function at the end of the chapter: a program that prints itself rests on it.

format is the older brother of the f-strings from Chapter 2. The difference is when the holes get filled. An f-string is evaluated at once, on the line of the program where it is written, from the variables that exist at that moment. A string for format can be written in advance, put into the list of rules and filled in later, when a sentence arrives. That is what ELIZA’s rules need. Inside the braces format understands the same instructions as f-strings: "{:>8}".format(3.5) aligns the number to the right in eight positions.

One detail of the original remains. Each ELIZA rule had several templates, and the program used them in turn so as not to repeat itself. We’ll do the same: for every rule we’ll remember how many times it has fired and take template number turn % len(replies), round and round. Nearly all our templates come straight from the DOCTOR script printed at the end of Weizenbaum’s paper. Type a sentence into the widget below and follow how ELIZA takes it apart.

Try to break ELIZA; it isn’t hard. “I want a new job” turns into a reply straight out of the 1966 script: “What would it mean to you if you got a new job?” But “I want you to listen to me,” given the same template, comes back as “What would it mean to you if you got i to listen to you?” In English one word, “you,” does the work of both “I” and “me,” and our table always makes it “i”. And the pair of “am” and “are,” which mends “I am tired,” wrecks “My parents are angry”: ELIZA replies “Your parents am angry?” Weizenbaum’s script turned “am” into “are” but never the other way round, and patched the damage with further rules. You can keep refining the rules forever, and none of it adds any understanding.

Step 5. The conversation

All that remains is to put everything together and add the conversation loop: input reads a line, answer replies, and the word “bye” ends the talk. The rules from the table above go into the RULES block.

Sixty lines, and not a shred of knowledge about the world. You can run the program right in the cell, and the server will ask for your lines in a box under the code, but it is easier to talk in the window below. It takes the program from the cell, with all your edits.

After a few lines you can see how it is done: the replies repeat, and a sentence without keywords gets a stock “Please go on.” And yet for the first few minutes the conversation draws you in. That frightened Weizenbaum.

The tendency to credit a program with understanding it doesn’t have is called the ELIZA effect. It hasn’t gone away as programs grew smarter. Today’s language models are built quite differently: they have no table of rules and learn to continue text from an enormous number of examples. How a machine learns what nobody taught it is the subject of Chapter 63, and you can build a small language model from scratch in the Sprout course on this site. Weizenbaum’s question remains: what stands behind a machine’s words?

Workshop: cleaning up text

ELIZA rests on three skills: bringing text to one form, cutting it into words and gluing it back together. You need them wherever a program reads what people wrote, from a search box to sorting through product reviews. The workshop has three tasks, and the first is about palindromes.

A palindrome is a phrase that reads the same in both directions: “A man, a plan, a canal: Panama!” It was made up by the British wordplay enthusiast Leigh Mercer and appeared in the journal Notes and Queries in 1948. It reads the same only if you ignore the spaces, the punctuation and the capitals. So the first job is to keep nothing but the letters.

A slice with step −1 reverses a string. The method isalpha tells you whether a character is a letter; there are also isdigit, for a digit, and isalnum, for a letter or a digit. We build the string letters one character at a time, and letters += ch builds a new string every time, since the old one can’t be changed. On a thousand characters the cost is invisible. On a million it’s better to collect the characters in a list and glue them together at the end with "".join(...).

Strings and lists are related: both are sequences, and len, indices, slices, in and loops work the same way on both. But a list can be changed and a string can’t, and a list holds anything while a string holds only characters. Even in behaves differently: in a list it looks for an item, in a string for a substring. Turning one into the other is easy: list("cat") gives ['c', 'a', 't'], and "".join puts it back.

The second task comes from any sign-up form. People type their names any old way: in capitals, with extra spaces, all in lower case. The method capitalize makes the first letter of a string a capital and the rest lower case, and title capitalizes the first letter of every word.

The third task is counting words. You might think strings already have a method for it, count, which counts occurrences of a substring. But it finds “war” inside “toward” and “reward,” and misses “War” with a capital.

A program that prints itself

In Chapter 0 you ran a two-line program that prints its own text, character for character:

Back then we promised to explain how it works. Now we have everything we need except two details: the function repr and the old way of filling templates with the % sign.

A string and how it is written

Every string has two faces. The first is what it is: the characters that print prints. The second is how it is written in Python code: in quotes, with special characters such as a newline spelled out with a backslash. The second face is what the function repr gives you; the name is short for “representation.”

print(s) showed two lines of text: the \n inside the string is a single character, a newline. But repr(s) returned a string you can paste into a program, with quotes at both ends and with \n as two characters, a backslash and the letter n. Python chose single quotes because there are double ones inside. That is why the lengths differ: 32 characters in the string and 35 in its written form. The representation of a string is its source code.

The second tool is the % operator for strings, the oldest way of filling templates in Python; it came from the printf function of the C language. A template string has holes in it: %s means “put the value in as text,” %r means “put in its repr.” To get a percent sign itself into the result, you write it twice: %%.

Taking the quine apart

The first line of the program puts into s a string of 20 characters: s = %r, a newline and print(s %% s). It is a template of the whole program, with a single hole where the string literal goes. The second line fills the template with the template itself: s % s. Two rules of the % operator do the rest.

• The hole %r is replaced by repr(s), that is, the string s as it is written on the first line of the program: in single quotes, with \n as two characters and with two percent signs. The first line of the output becomes s = 's = %r\nprint(s %% s)', a copy of the first line of the program.
• %% outside a hole turns into a single %. The newline character itself prints as a line break, and the second line of the output is print(s % s), a copy of the program’s second line.

So the program doesn’t contain itself in full; that is impossible, since it would have to be longer than itself. It contains a template of itself with one place left empty, and a rule for filling that place. The place is filled with the same template in its written form, through repr. The template describes the program, and the repr of the template describes the piece of the program where the template is written down.

The same quine can be written with newer tools. The version with format is an almost word-for-word translation: the hole {!r} means “put in the repr of the argument.”

With an f-string the quine looks different. An f-string is evaluated at once and can’t be set aside as a template, so here the string s holds the whole second line of the program, and that line prints “s = ”, then repr(s), then a newline and s itself. On the first line \\n is written with a double backslash: inside the string it has to stay two characters, a backslash and the letter n.

Check that you’ve understood how it works: put some baggage of your own into a quine.

What next

To find out how many times “war” occurs in War and Peace, one line is enough: words.count("war"), and a moment later you have the answer, 292. But which words of the novel are the most frequent? For that you have to count every word. With what we have so far, the only way is the one we used for the countries: a list of the different words and a parallel list of counters. Here is how it fares on the first 10,000, 20,000, 40,000 and 80,000 words.

Every doubling of the text makes the count nearly three times slower. The culprits are in and index: to find out whether a word has come up before, Python walks the whole list of known words, and that list grows with the text. On the whole novel, more than 560,000 words with over 20,000 different ones, the count would take about ten seconds, all the time the sandbox gives a program; on a library of a hundred novels, hours. We need a structure that goes from a word straight to its counter without looking through the others. It is called a dictionary, and with it the whole novel is counted faster than you can blink. In Chapter 8 we’ll use it to count letters, as the inventors of the telegraph did, and find out why the letter E in Morse code is a single dot.