The ABC Programmer's Handbook by Leo Geurts, Lambert Meertens, and Steven Pemberton

This chapter gives a number of examples of ABC commands and programs. It is through examples that the advantages of ABC become really clear: that ABC programs are concise, clear and understandable.

The examples in this chapter have been written for clarity, rather than, for instance, efficiency. This reflects one of the aims of ABC, namely to reduce programming time and let the computer do the work. Shorter, clearer programs are easier to program, easier to get right, and easier to change.

The examples often build on previous examples. In particular, the commands and functions from the section on common data-structures are used a lot by later examples.

Several versions of some examples are given in order to demonstrate different programming styles, or to show the effect that different choices of data-structures have.

To start with we shall give a couple of simple examples. The first, although simple in ABC, would actually demand a lot of programming in another language. It is an especially useful first example since it uses all 5 ABC types.

To maintain a telephone list, you can use an ABC table such as:

{["Ann"]: 9768; ["Mary"]: 6458}

To create this table, you start off with an empty table, and add the numbers
to it (`>>>`

is the prompt for an immediate
command):

>>> PUT {} IN phone >>> PUT 6458 IN phone["Mary"] >>> PUT 9768 IN phone["Ann"]

or, in one command:

>>> PUT {["Mary"]: 6458; ["Ann"]: 9768} IN phone

Looking up someone's number, or changing it, or adding someone else to the list is easy:

```
>>> WRITE phone["Mary"]
6458
>>> PUT 7754 IN phone["John"]
>>> PUT 6348 IN phone["Ann"]
```

You may even write the whole list:

```
>>> WRITE phone
{["Ann"]: 6348; ["John"]: 7754; ["Mary"]: 6458}
```

Note that the entries are printed in alphabetic order. For starting the list, it can be more convenient to have a piece of program to help:

HOW TO ADD TO t: READ NAME WHILE name > "": WRITE "Number: " READ t[name] EG 0 READ NAME READ NAME: WRITE "Name: " READ name RAW

Using this command, you can fill a table `tel`

by
just typing the names and the numbers:

```
>>> PUT {} IN tel
>>> ADD TO tel
Name: John
Number: 7754
Name: Mary
Number: 6458
Name: Ann
Number: 6348
Name:
>>>
```

To find out who is in the list, you can use the function `keys`

:

```
>>> WRITE keys tel
{"Ann"; "John"; "Mary"}
```

If you want to know if there is somebody in `tel`

with, say, the number 6348, you can use a so-called quantification:

```
>>> IF SOME name IN keys tel HAS tel[name] = 6348:
WRITE name
Ann
```

If this happens very often, it may be useful to construct the inverse table,
in which you can directly look up the name belonging to a telephone number.
Assuming there are no people sharing the same number, the inverse table `user`

can be built this way:

>>> PUT {} IN user >>> FOR name IN keys tel: PUT name IN user[tel[name]]

and then

```
>>> WRITE user[6348]
Ann
```

though it would be more useful to make these commands into a function to calculate the inverse table:

HOW TO RETURN inverse t: PUT {} IN inv FOR name IN keys t: PUT name IN inv[t[name]] RETURN inv

and then use it like this:

```
>>> PUT inverse tel IN user
>>> WRITE user
{[6348]: "Ann"; [6458]: "Mary"; [7754]: "John"}
```

For printing the table in a neat way you can define this command `PRINT TEL`

:

HOW TO PRINT TEL t: FOR k IN keys t: WRITE k, ":", t[k] /

```
>>> PRINT TEL tel
Ann: 6348
John: 7754
Mary: 6458
```

The `/`

in the `WRITE`

command writes a newline (note that there is no comma before it). `WRITE`

writes a space between adjacent values, unless they
are both texts. So there is a space between the colon and the number, but none
between the name and the colon.

To line the columns up, you can use the text operator `<<`

, specifying the width that you want:

HOW TO PRINT TEL t: FOR k IN keys t: WRITE k^":" << 10, t[k] /

```
>>> PRINT TEL tel
Ann: 6348
John: 7754
Mary: 6458
```

To print the table as it would be printed in a telephone book, with dots, you can extend the name with a number of dots, and then trim to the width of the column:

HOW TO PRINT TEL t: FOR k IN keys t: WRITE (k ^ "."^^20) | 20, t[k] /

```
>>> PRINT TEL tel
Ann.................. 6348
John................. 7754
Mary................. 6458
```

Note that you shouldn't use the expression

k^("."^^(20-#k))

even though it would appear to mean the same. The difference is that if
`k`

is longer than twenty characters, `20-#k`

is negative, which would cause `^^`

to give an error. With the version given, all that would
happen is that `k`

would be truncated.

The new command could also be used for the inverse table `user`

, but it makes the assumption that the keys of the
table are texts, by using the operator ^ on the keys. In our case, the keys of
user are numbers. We can make the command work with any kind of table by
converting each key to a text before using it. This works even if the key is
already a text. There are two ways to turn a value into a text: by using one of
the operators <<, >> or ><, such as ```
k
<< 1
```

(the 1 gives the minimum width: it comes out wider if it has
to), or by using a conversion, like `"`k`"`

.

You'll also notice a space between the dots and the telephone number in the
above output from `PRINT TEL`

. This is because, as we
said, `WRITE`

writes a space between adjacent values,
unless they are both texts. So if we also convert `t[k]`

to a text, we won't get that space:

HOW TO PRINT TEL t: FOR k IN keys t: WRITE ("`k`" ^ "."^^20) | 20, "`t[k]`" /

```
>>> PRINT TEL tel
Ann.................6348
John................7754
Mary................6458
```

```
>>> PRINT TEL user
6348................Ann
6458................Mary
7754................John
```

But what if the telephone list does contain people who share the same number? In this case, the inverse table will have to be from numbers to lists of names. Here is a function that calculates such an inverse table:

HOW TO RETURN inverse table: PUT {} IN inv FOR name IN keys table: ADD NAME RETURN inv ADD NAME: IF table[name] not.in keys inv: PUT {} IN inv[table[name]] INSERT name IN inv[table[name]]

The difference with the previous version is contained in the refinement
`ADDNAME`

: before, we just stored the name with the
number, but now we must store the name in a list. To do this we first have to
check that a list has already been started for that number, since you may not
insert an item in a non-existent list.

Actually, this sequence is going to occur so often in this chapter, that it is better if we make a separate command of it:

HOW TO SAVE item IN table AT key: IF key not.in keys table: PUT {} IN table[key] INSERT item IN table[key]

Now inverse looks like this:

HOW TO RETURN inverse table: PUT {} IN inv FOR name IN keys table: SAVE name IN inv AT table[name] RETURN inv

```
>>> PUT 6348 IN tel["Sue"]
>>> PUT inverse tel IN users
>>> WRITE users[6348]
{"Ann"; "Sue"}
```

Finally, let us now treat the more realistic case where not only people
share telephones, but people may also have more than one telephone. The
telephone list must now hold for each name a list of numbers. So first we must
change `ADD TO`

to accept multiple numbers:

HOW TO ADD TO t: ASK NAME WHILE name > "": WRITE "Number: " READ no EG 0 SAVE no IN t AT name ASK NAME ASK NAME: WRITE "Name: " READ name RAW

```
>>> PUT {} IN tel
>>> ADD TO tel
Name: John
Number: 7754
Name: Mary
Number: 6458
Name: Mary
Number: 7754
Name: Ann
Number: 6348
Name: Sue
Number: 6348
Name:
```

```
>>> PRINT TEL tel
Ann.................{6348}
John................{7754}
Mary................{6458; 7754}
Sue.................{6348}
```

Now we must redefine `inverse`

so that it can handle
the new table. This just involves adding one more line to handle each number
for a person rather than just one number:

HOW TO RETURN inverse t: PUT {} IN inv FOR name IN keys t: FOR number IN t[name]: SAVE name IN inv AT number RETURN inv

```
>>> PRINT TEL inverse tel
6348................{"Ann"; "Sue"}
6458................{"Mary"}
7754................{"John"; "Mary"}
```

This version of `inverse`

restores a nice property
that the very first version had, but that the second didn't: applying `inverse`

twice to a table gives you the original table
back:

```
>>> PRINT TEL inverse inverse tel
Ann.................{6348}
John................{7754}
Mary................{6458; 7754}
Sue.................{6348}
```

Of course, telephone numbers are not always pure numbers. They may contain
hyphens, brackets, words, or other non-digit characters, like `020-5929333`

or `WHI-1212x300`

. To
support this, you have to use texts instead of numbers for the telephone
numbers. As an exercise, which single line of which how-to in the last part of
this section would need to be changed to do this?

Here is a simple guessing game. To make it interesting it uses the function choice, which given any text, list or table will return a random element of it:

>>> WRITE choice {1..10} 7 >>> WRITE choice {1..10} 3 >>> WRITE choice {"yes"; "no"; "maybe"} no

HOW TO GUESS: PUT choice {0..99} IN number WRITE "Guess my number from 0 to 99: " READ guess EG 0 WHILE guess <> number: SELECT: guess < number: WRITE "Try higher: " guess > number: WRITE "Try lower: " READ guess EG 0 WRITE "Yes! Well done" /

>>> GUESS Guess my number from 0 to 99: 50 Try lower: 25 Try lower: 15 Try higher: 20 Try lower: 17 Try higher: 19 Yes! Well done

Here is the complement game: the computer guesses the number. It works by
keeping the list of numbers that the answer must lie in (initially `{0..99}`

). Then as each guess is high or low, the range is
restricted accordingly (for instance, if 50 is too low, the list becomes `{51..99}`

). If the list ever becomes empty, the player must
have given the wrong answer at some stage.

HOW TO PLAY: WRITE "Think of a number from 0 to 99," WRITE " and press [return]: " READ return RAW PUT {0..99} IN range WHILE range <> {}: TRY range

HOW TO TRY range: PUT choice range IN guess WRITE "Is it `guess`? " READ reply RAW SELECT: reply|1 = "y": PUT {} IN range WRITE "Good" / reply|1 = "h": PUT {min range..guess-1} IN range reply|1 = "l": PUT {guess+1..max range} IN range ELSE: WRITE "Please reply y(es), h(igh) or l(ow)" / IF range = {} AND reply|1 <> "y": WRITE "Cheat!" /

>>> PLAY Think of a number from 0 to 99, and press [return]: Is it 17? no Please reply y(es), h(igh) or l(ow) Is it 33? l Is it 53? h Is it 45? l Is it 50? y Good

>>> PLAY Think of a number from 0 to 99, and press [return]: Is it 93? l Is it 96? h Is it 94? h Cheat!

Each programming language has its own style and idioms. People who have used other programming languages sometimes unnecessarily use techniques from those other languages when programming in ABC. For instance, when using a stack, they keep both the stack, and the index of its top element. Here then are a few examples of how you use some of the standard data-structures in ABC.

You can represent a stack using a table, with integers as the keys and the
elements of the stack as items. You don't need to keep a separate index to the
top item because you can always use the ABC `#`

operator to find out the size of the stack.

Emptying or initialising a stack is easy:

HOW TO EMPTY stack: PUT {} IN stack

To add an item you can use the following command:

HOW TO PUSH item ON stack: PUT item IN stack[#stack+1]

Here it is in use:

>>> EMPTY numbers >>> PUSH 123 ON numbers >>> WRITE numbers {[1]: 123} >>> PUSH 321 ON numbers >>> WRITE numbers {[1]: 123; [2]: 321}

You can access the top item of the stack with the following function:

HOW TO RETURN top stack: RETURN stack[#stack]

and pop the top element with this command:

HOW TO POP stack INTO item: PUT stack[#stack] IN item DELETE stack[#stack]

Here is an example using these commands, a command to replace the top two elements of a stack with their sum:

HOW TO ADD stack: POP stack INTO right POP stack INTO left PUSH left+right ON stack

and then a use of this command:

```
>>> EMPTY numbers
>>> PUSH 123 ON numbers
>>> PUSH 321 ON numbers
>>> ADD numbers
>>> WRITE top numbers
444
```

Note that because functions in ABC cannot have side-effects, you can only use a function to pop a stack by returning both the popped element and the stack:

HOW TO RETURN popped stack: PUT stack[#stack] IN item DELETE stack[#stack] RETURN item, stack

Using this, `ADD`

would look like this:

HOW TO ADD stack: PUT popped stack IN right, stack PUT popped stack IN left, stack PUSH left+right ON stack

ABC's lists are sorted, and that is often what you need, or at least it makes no difference to your program whether they are sorted or not. However, sometimes you need to store an unsorted sequence of items. The standard way to do this in ABC is to store each item in a table whose keys are ascending integers.

So the empty sequence, just like the empty stack, is an empty table {}. Appending an item to a sequence uses the same idea as for stacks:

HOW TO APPEND item TO sequence: PUT item IN sequence[#sequence+1]

This method of adding items to the end of a sequence only works if items are not removed, or are removed only from the end. If this is not the case, then you have to use this version:

HOW TO APPEND item TO sequence: PUT item IN sequence[next] next: SELECT: #sequence = 0: RETURN 1 ELSE: RETURN 1 + max keys sequence

As an example, suppose you want to write a `HELP`

command that gives help on various topics. Each help message can be stored as a
sequence of lines that can be displayed with this command:

HOW TO DISPLAY message: FOR line IN message: WRITE line /

Each message can then be stored in a table with the topics as keys. To add a help message for some new topic, you can use the following command:

HOW TO ADD HELP FOR topic: SHARE help PUT {} IN help[topic] WRITE "Type lines of help. " WRITE "Finish with a '.' alone on a line." / READ line RAW WHILE line <> ".": APPEND line TO help[topic] READ line RAW

So that finally, the help command can look like this:

HOW TO HELP topic: SHARE help SELECT: topic in keys help: DISPLAY help[topic] ELSE: WRITE "Sorry, I can't help with that" /

although we could make it a bit more useful for the user by adding the ability to list what topics are available:

HOW TO HELP topic: SHARE help SELECT: topic in keys help: DISPLAY help[topic] ELSE: WRITE "Sorry, I can't help with that. " WRITE "These are the topics I know: " / LIST keys help

This uses the following command to print a list neatly:

HOW TO LIST l: PUT "" IN separator FOR item IN l: WRITE separator, item<<1 PUT ", " IN separator WRITE /

>>> LIST {1..5} 1, 2, 3, 4, 5 >>> LIST {"READ"; "WRITE"; "PUT"} PUT, READ, WRITE

This method of writing the separating comma may seem a bit unusual at first,
but is preferable to the alternatives, where rather than just traversing the
list, you have to index each item separately with `item`

, and include a test:

HOW TO LIST l: FOR i IN {1..#l}: WRITE l item i << 1 IF i <> #l: WRITE ", " WRITE /

or

HOW TO LIST l: FOR i IN {1..#l-1}: WRITE l item i << 1, ", " IF #l > 0: WRITE l item #l WRITE /

or

HOW TO LIST l: IF #l > 0: WRITE l item 1 FOR i IN {2..#l}: WRITE ", ", l item i << 1 WRITE /

Don't be misled by false feelings of 'efficiency' here: regardless of the
size of the value involved, the cost of a `PUT`

command
is always the same, and it is one of the cheapest commands there is in ABC
(`PASS`

is cheaper). Similarly, a `FOR`

command over a list is (not surprisingly) about half
the cost of a `FOR`

over a range and then indexing.

Where output is involved, it is often better to use a function than a command to format a structure on a single line:

HOW TO RETURN listed l: PUT "", "" IN separator, result FOR item IN l: PUT result^separator^(item<<1) IN result PUT ", " IN separator RETURN result

Now it can be mixed with other output in a single write:

>>> WRITE listed {1..3} 1, 2, 3 >>> WRITE "(", listed {1..3}, ")" (1, 2, 3)

Many of ABC's standard operators and functions are defined in two versions, a monadic one (with one operand) and a dyadic one (with two operands), where the monadic version is defined in terms of the dyadic one. This is an obvious candidate for this treatment: the dyadic version can also take the separator:

HOW TO RETURN separator listed l: PUT "", "" IN sep, result FOR item IN l: PUT result^sep^(item<<1) IN result PUT separator IN sep RETURN result

and then the monadic version can be defined as:

HOW TO RETURN listed l: RETURN ", " listed l

These can then be used for all sorts of different purposes (note that they work for tables and texts, as well as lists):

```
>>> WRITE listed phone
6348, 7754, 6458
```

```
>>> WRITE listed keys phone
Ann, John, Mary
```

```
>>> WRITE "." listed "Divorce"
D.i.v.o.r.c.e
```

ABC's lists are nearly sets. The difference is that they may contain more than one occurrence of an item (which makes them what are called bags or multisets). Using lists to represent sets, you can use the following command to add an item to a set:

HOW TO INCLUDE element IN set: IF element not.in set: INSERT element IN set

The following functions return the union, intersection and difference of two sets:

HOW TO RETURN a with b: FOR item IN b: INCLUDE item IN a RETURN a

```
>>> WRITE {1..4} with {3..6}
{1; 2; 3; 4; 5; 6}
```

HOW TO RETURN a common.with b: FOR item IN a: IF item not.in b: REMOVE item FROM a RETURN a

```
>>> WRITE {1..4} common.with {3..6}
{3; 4}
```

HOW TO RETURN a less b: FOR item IN a: IF item in b: REMOVE item FROM a RETURN a

```
>>> WRITE {1..4} less {3..6}
{1; 2}
```

If you have a list, possibly with duplicated entries, or a table (or even a
text), and you want to convert it to a set, you can let `with`

do all the work:

HOW TO RETURN set t: RETURN {} with t

```
>>> WRITE set "Mississippi"
{"M"; "i"; "p"; "s"}
```

Finally, here is a function to calculate the power set of a set, that is, the set of all subsets of a set, though it actually works on any train (i.e, text, list, or table):

HOW TO RETURN powerset s: PUT {{}} IN pset FOR item IN s: FOR set IN pset: INCLUDE set with {item} IN pset RETURN pset

```
>>> FOR s IN powerset "ABC":
WRITE s /
{}
{"A"}
{"A"; "B"}
{"A"; "B"; "C"}
{"A"; "C"}
{"B"}
{"B"; "C"}
{"C"}
```

It is a temptation when coming from another language to use sequences to implement queues, and use a technique such as linear search to insert an item in the queue at the right place. However, since ABC's lists are already sorted, you can use them instead, storing the item along with the value that determines its place in the queue.

For instance, suppose you have a queue of tasks to be performed at given times, where the times are given as the number of seconds since midnight. You can insert an item in the queue like this:

INSERT time, task IN queue

Selecting the first task to be executed can then be done with the following:

HOW TO TAKE thing FROM queue: PUT queue item 1 IN thing REMOVE thing FROM queue

invoked with

TAKE time, task FROM queue

You can use `min queue`

instead of queue item 1 if
you want, since it means the same thing for lists.

Here is an example of the use of these commands, a rather unrealistic simulation of a metro train station. People enter the station at random intervals between 0 and 10 seconds. Trains leave at intervals of 10 minutes (600 seconds). The program prints how many people are on each train as it leaves:

HOW TO SIMULATE: PUT 0, {} IN time, tasks NEW TRAIN NEW PERSON WHILE tasks <> {}: PROCESS TASK PROCESS TASK: TAKE time, task FROM tasks SELECT: task = "train": WRITE "Time `time`: `people` passengers" / PUT 0 IN people NEW TRAIN task = "person": PUT people+1 IN people NEW PERSON NEW TRAIN: INSERT time+600, "train" IN tasks NEW PERSON: INSERT time+random*10, "person" IN tasks

```
>>> SIMULATE
Time 600: 117 passengers
Time 1200: 125 passengers
Time 1800: 113 passengers
Time 2400: 120 passengers
*** Interrupted
>>>
```

(Since this command never terminates, it would go on and on producing results. To stop such a command, you have to interrupt it, and that is the reason for the last line in the output above. How you interrupt a command is explained in chapter 3, Using ABC.)

The absence of a pointer type in ABC would seem to suggest that data-structures like trees cannot be created. In fact, thanks to tables, they can, and with certain advantages, not least of which is the ease of printing a table.

A tree can be represented in ABC as a table of nodes. It is relatively unimportant what the keys of such a table are; this example uses numbers. Each node then consists of an indication of what kind of node it is (here we will use texts), and a sequence of numbers. These numbers are the keys of the sub-trees of this node.

To add a node to the tree you use the same technique as with stacks and sequences. In fact, the tree can be seen as a sequence of nodes, where you also use the sequence numbers:

HOW TO ADD NODE n TO tree GIVING p: PUT #tree, n IN p, tree[#tree]

(The use of `#tree`

as the index just has the effect
that the first element is stored at key 0, the second at 1, and so on.)

To show the use of tables in this way, here is a small program to convert simple arithmetic expressions into trees, a typical example for pointers. For example, the tree for a*2+b*2 can be represented as the following table, starting from node 6:

{[0]: ("a", {}); [1]: ("2", {}); [2]: ("*", {[1]: 0; [2]: 1}); [3]: ("b", {}); [4]: ("2", {}); [5]: ("*", {[1]: 3; [2]: 4}); [6]: ("+", {[1]: 2; [2]: 5}) }

The following can be used to display a returned tree:

HOW TO DISPLAY TREE t, n: WRITE "Top node is", n / FOR i IN keys t: WRITE i, ": " PUT t[i] IN type, nodes WRITE type, " " listed nodes /

(Function `listed`

is in section HOW TO RETURN listed l.) The text
of the expression to be compiled is passed over as parameter, and the resulting
tree and the index of its top-most node is returned:

HOW TO RETURN compiled expression: SHARE tree, line PUT {}, expression IN tree, line EXPRESSION node RETURN tree, node

The expression is parsed using what is known as recursive-descent: `EXPRESSION`

invokes `TERM`

to parse
a sub-expression; next.char returns the first character of the expression and
`SKIP`

`CHAR`

trims off the
first character from the expression.

HOW TO EXPRESSION x: SHARE tree TERM x WHILE next.char in {"+"; "-"}: PUT next.char IN op SKIP CHAR TERM y ADD NODE (op, {[1]: x; [2]: y}) TO tree GIVING x

HOW TO RETURN next.char: SHARE line RETURN line|1

HOW TO SKIP CHAR: SHARE line PUT line@2 IN line

`TERM`

is very similar to `EXPRESSION`

. `OPERAND`

recognises a
single letter or digit as operand to a sub-expression.

HOW TO TERM x: SHARE tree OPERAND x WHILE next.char in {"*"; "/"}: PUT next.char IN op SKIP CHAR OPERAND y ADD NODE (op, {[1]: x; [2]: y}) TO tree GIVING x

HOW TO OPERAND x: SHARE tree SELECT: next.char in {"a".."z"; "0".."9"}: ADD NODE (next.char, {}) TO tree GIVING x ELSE: WRITE "Error at:", next.char / PUT -1 IN x SKIP CHAR

```
>>> DISPLAY TREE compiled "a*2+b*2"
Top node is 6
0 : a
1 : 2
2 : * 0 1
3 : b
4 : 2
5 : * 3 4
6 : + 2 5
```

As an example of traversing such a tree, here is a function to evaluate a parsed expression:

HOW TO RETURN value (tree, node): SHARE memory PUT tree[node] IN type, operands SELECT: type in keys memory: RETURN memory[type] type in {"0".."9"}: RETURN #{"1"..type} type = "+": RETURN left+right type = "-": RETURN left-right type = "*": RETURN left*right type = "/": RETURN left/right ELSE: WRITE "*** `type` has no value" / RETURN 0 left: RETURN value (tree, (operands item 1)) right: RETURN value (tree, (operands item 2))

Note the expression `#{"1"..type}`

. This converts a
digit character into its numeric value. For instance, if type = "3", then `{"1"..type}`

is `{"1";"2";"3"}`

,
whose size is 3. Similarly, `{"1".."0"}`

is `{}`

, whose size is 0.

```
>>> PUT {} IN memory
>>> PUT 3, 4 IN memory["a"], memory["b"]
>>> WRITE value compiled "a*2+b*2"
14
```

We mean here the mathematical concept of a graph -also called a relation- and not the plotting of functions. A graph is an extension of a tree, where each node may refer to any other node in the graph.

You can represent a graph using the same idea as with trees. Each node can be a key in a table. The associated item of the table can then be a set of nodes.

As a concrete example, take a group of people, and the information of who
can contact whom within that group. For instance, `contacts["Doris"] = {"Bessy"; "Kevin"}`

means that Doris can
contact Bessy and Kevin (but not necessarily the other way round). Here is a
command to display such a graph (function `listed`

is
in section HOW TO RETURN listed
l.):

HOW TO SHOW graph: FOR node IN keys graph: WRITE node, ": ", listed graph[node] /

```
>>> PUT {} IN contacts
>>> PUT {"Emily"; "Kevin"} IN contacts["Doris"]
>>> PUT {"Emily"} IN contacts["Kevin"]
>>> PUT {"Bessy"} IN contacts["Emily"]
>>> SHOW contacts
Doris: Emily, Kevin
Emily: Bessy
Kevin: Emily
```

Here is a function that returns the sub-graph of all people contactable, directly or indirectly, from a given root person (which is a process sometimes called garbage-collection). This is a mark and sweep version:

HOW TO RETURN graph reachable.from root: PUT {root}, {root} IN accessible, to.do COLLECT REACHABLES ELIMINATE UNREACHABLES RETURN graph COLLECT REACHABLES: WHILE to.do > {}: PUT to.do item 1 IN node REMOVE node FROM to.do TREAT NODE TREAT NODE: IF node in keys graph: FOR n IN graph[node]: IF n not.in accessible: INSERT n IN accessible INSERT n IN to.do ELIMINATE UNREACHABLES: FOR node IN keys graph: IF node not.in accessible: DELETE graph[node]

Here is a copy version. It also takes advantage of the how-to's `with`

, `less`

, and `TAKE`

defined earlier:

HOW TO RETURN graph reachable.from root: PUT {root}, {} IN to.do, new WHILE to.do > {}: TAKE node FROM to.do TREAT NODE RETURN new TREAT NODE: IF node in keys graph: PUT graph[node] IN new[node] PUT to.do with new.nodes IN to.do new.nodes: RETURN new[node] less keys new

```
>>> SHOW contacts reachable.from "Kevin"
Emily: Bessy
Kevin: Emily
```

The product of two graphs is the graph where `a`

is
connected to `c`

, if `a`

is
connected to `b`

in the first graph, and `b`

is connected to `c`

in the
second:

HOW TO RETURN g1 prod g2: PUT {} IN product FOR a IN keys g1: FOR b IN g1[a]: IF b in keys g2: PUT product.a with g2[b] IN product[a] RETURN product product.a: IF a in keys product: RETURN product[a] RETURN {}

For instance, take this graph showing the parents of a group of people:

```
>>> SHOW parents
Anne: John, Margaret
John: Gladys, James
Margaret: Alice, George
Mark: John, Margaret
```

The product of this graph with itself gives the graph of grandparents:

```
>>> SHOW parents prod parents
Anne: Alice, George, Gladys, James
Mark: Alice, George, Gladys, James
```

Actually, the telephone list in the first example of this chapter can be
seen as a graph, and furthermore, the function `inverse`

defined there inverts any graph. The inverse of the
parents graph is the children graph:

```
>>> SHOW inverse parents
Alice: Margaret
George: Margaret
Gladys: John
James: John
John: Anne, Mark
Margaret: Anne, Mark
```

A useful operation on a graph is to calculate its closure. A closure of a
graph is a graph with the same nodes as the original graph, but where each node
refers to all nodes reachable from the node in the original. The closure of the
contacts graph, for example, is the graph where each node refers to all
contactable nodes, whether directly or indirectly. Here we use the function
`with`

we defined earlier for sets:

HOW TO RETURN closure a: FOR i IN keys a: FOR j IN keys a: IF i in a[j]: PUT a[i] with a[j] IN a[j] RETURN a

To understand how this works, the crucial insight is that after each step of
`FOR i`

, the value of the closure graph under
construction is such that, for each node j, a[j] is the list of nodes directly
or indirectly reachable from j using as contacts only nodes that are at most
i.

>>> SHOW closure contacts Doris: Bessy, Emily, Kevin Emily: Bessy Kevin: Bessy, Emily >>> SHOW closure(contacts reachable.from "Kevin") Emily: Bessy Kevin: Bessy, Emily

The closure of the parents graph shows all the ancestors for each person:

```
>>> SHOW closure parents
Anne: Alice, George, Gladys, James, John, Margaret
John: Gladys, James
Margaret: Alice, George
Mark: Alice, George, Gladys, James, John, Margaret
```

The children of your parents are you and your siblings. So the product of the parents and the children graphs gives the siblings:

```
>>> SHOW parents prod (inverse parents)
Anne: Anne, Mark
John: John
Margaret: Margaret
Mark: Anne, Mark
```

On the other hand, the parents of your children are you and your partner(s), so the product of the children and parents graphs shows who have produced offspring together:

```
>>> SHOW (inverse parents) prod parents
Alice: Alice, George
George: Alice, George
Gladys: Gladys, James
James: Gladys, James
John: John, Margaret
Margaret: John, Margaret
```

ABC's numbers have two unusual properties: they are calculated exactly for most operations, and they may have unbounded length.

Here is a program that uses a list of numbers and the sieve method to calculate primes. It works by taking the set of numbers from 2 to n, then taking the smallest (2). This is a prime. All multiples of this are removed from the list, and then the next smallest (3) is taken, and the same process repeated, and so on.

HOW TO SIEVE TO n: PUT {2..n} IN set WHILE set > {}: PUT min set IN p REMOVE p FROM set WRITE p REMOVE MULTIPLES REMOVE MULTIPLES: FOR m IN {p..floor(n/p)}: IF m*p in set: REMOVE m*p FROM set

```
>>> SIEVE TO 50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
```

Another way to do this is to use the set functions defined earlier, and make it a function:

HOW TO RETURN primes n: IF n < 2: RETURN {} PUT {2..n} IN set FOR p IN primes floor root n: PUT set less multiples IN set RETURN set multiples: RETURN p times {p..floor(n/p)}

This uses a function that takes a set of numbers and returns the set with all elements multiplied by a given factor:

HOW TO RETURN f times s: PUT {} IN res FOR i IN s: INSERT f*i IN res RETURN res

>>> WRITE 2 times {1..5} {2; 4; 6; 8; 10} >>> WRITE primes 45 {2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43}

Notice the use of recursion in the definition of `primes`

:

FOR p IN primes floor root 10

For instance, to calculate the primes to 1000, it first calculates the primes to 31 (that is, floor root 1000), and removes all multiples of these from the list {2..1000}. While this may seem like a lot of extra work, in fact it results in slightly less work than using

FOR p IN {2..floor root n}

since the body of the `FOR`

is executed fewer
times.

The following function can be used to print an exact number out exactly: if it is a fraction, then the fraction is printed either exactly or as a recurring decimal.

It works in the same way that you would do it by hand: by calculating the next digit of the fraction and the remainder then left. With the remainder it saves the position of the digit, so that when the same remainder occurs again, the end of the repeating part has been reached. Then the beginning of the repeated part is the index that was saved with the repeated remainder.

The expression `x mod 1`

returns the fractional part
of `x`

. For instance:

```
>>> WRITE pi mod 1
0.141592653589793
```

HOW TO RETURN rep x: PUT "`floor x`.", 10*(x mod 1), {} IN t, x, index IF x = 0: RETURN t|#t-1 it was a whole number WHILE x not.in keys index: PUT #t IN index[x] PUT t^"`floor x`", 10*(x mod 1) IN t, x RETURN t|index[x] ^ recurring.part recurring.part: IF x = 0: RETURN "" \non-recurring fraction RETURN "[" ^ t@index[x]+1 ^ "]"

```
>>> WRITE rep(22/7)
3.[142857]
```

```
>>> FOR i IN {1..15}:
WRITE i, ": ", rep (1/i) /
1 : 1
2 : 0.5
3 : 0.[3]
4 : 0.25
5 : 0.2
6 : 0.1[6]
7 : 0.[142857]
8 : 0.125
9 : 0.[1]
10 : 0.1
11 : 0.[09]
12 : 0.08[3]
13 : 0.[076923]
14 : 0.0[714285]
15 : 0.0[6]
```

Actually, this function also works for approximate numbers:

```
>>> WRITE rep pi
3.14159265358979322702026593105983920395374298095703125
```

but, by the very nature of approximate numbers, only so many of these digits are accurate. That is to say, the number printed is the closest to the real value of pi that could be attained using an approximate number, and this number diverges at some point from the real value of pi

Approximate numbers are the only place where the behaviour of ABC varies between machines, since ABC uses the numeric representation of the machine to represent them, and so you get a different accuracy on different machines. The following command works out what base is used for approximate arithmetic (nowadays that is usually 2, and sometimes 16), and how many digits accuracy in that base are used. It then gives this as the approximate number of decimal digits accuracy.

To understand how it works, imagine that approximate numbers are to base ten, with three digits accuracy. Starting from 2, the command first keeps doubling until it reaches a number that adding 1 to doesn't alter. In our fictitious case, it would try 1, 2, 4, 8,... 512, and stop at 1024, which is only representable as 1020, since there are only three significant digits, and adding 1 to 1020 still gives 1020.

Then starting at 2 again, it keeps doubling until adding it to the original number gives a different number. For 1020 this is 8 or 16, depending on whether the result of the addition gets rounded up or truncated. In either case the result is 1030. The difference between this and the original number, in our case 1030 - 1020 = 10, is the base.

Once you have that, it is then fairly simple to determine the number of significant digits:

HOW TO CALCULATE ACCURACY: CALCULATE BASE CALCULATE DIGITS CALCULATE BASE: PUT ~2 IN a WHILE a+1-a-1 = ~0: PUT a+a IN a PUT ~0, ~2 IN base, b WHILE base = ~0: PUT a+b-a, b+b IN base, b WRITE "Base =", base / CALCULATE DIGITS: PUT 1, base IN sig, b WHILE b+1-b-1 = ~0: PUT sig+1, b*base IN sig, b WRITE "Significant digits =", sig / IF base <> 10: WRITE "This is about `decimal` decimal digits" / decimal: RETURN 1 round ((sig-1)/(base log 10))

Here is its output when run on the machine used for this book:

```
>>> CALCULATE ACCURACY
Base = 2
Significant digits = 56
This is about 16.6 decimal digits
```

This means that only the first 16 digits of the above output for `pi`

are useful:

```
>>> WRITE rep (16 round pi)
3.1415926535897932
```

ABC's unbounded numbers allow you to use the following algorithm to calculate the number pi exactly with as many digits as you like. A language with 32 bit integers would only produce the first 5 digits before getting overflow. The ABC program just goes on churning out digits until you interrupt it.

The program works by repeatedly refining a so-called continued fraction that
represents pi. The first approximation is 4/1, the second is 4/(1+1/3), which
is 12/4. In the next, the 3 is replaced by 3+4/5, and in the next after that,
the 5 is replaced by 5+9/7 and so on, so that each part of the fraction is
`k`^{2}/(2`k`+1+...) for k = 0, 1, 2, ... .

In the program, `a/b`

represents one approximation
of the fraction, and `a'/b'`

the next. If there are any
leading digits in common, then these are printed, and the next approximation is
calculated.

HOW TO PI: PUT 2, 4, 1, 12, 4 IN k, a, b, a', b' WHILE 1=1: NEXT APPROXIMATION PRINT COMMON DIGITS NEXT APPROXIMATION: PUT k**2, 2*k+1, k+1 IN p, q, k PUT a', b', p*a+q*a', p*b+q*b' IN a, b, a', b' PRINT COMMON DIGITS: PUT floor(a/b), floor(a'/b') IN d, d' WHILE d = d': WRITE d<<1 PUT 10*(a mod b), 10*(a' mod b') IN a, a' PUT floor(a/b), floor(a'/b') IN d, d'

```
>>> PI
314159265358979323846264338327950288419716939937510582097494459230781640628620899
*** Interrupted
```

A polynomial is an expression such as 7x^{5}-4x^{4}+3x-1 and
can be represented in ABC as a table with the powers as keys and the
coefficients as items:

{[5]: 7; [4]: -4; [1]: 3; [0]: -1}

Given this representation, it is then easy to define the sum of two polynomials:

HOW TO RETURN a plus b: FOR q IN keys b: SELECT: q in keys a: PUT a[q]+b[q] IN a[q] ELSE: PUT b[q] IN a[q] RETURN normalised a

The function `normalised`

removes all zero items:

HOW TO RETURN normalised poly: FOR k IN keys poly: IF poly[k] = 0: DELETE poly[k] RETURN poly

The difference of two polynomials is similar:

HOW TO RETURN a minus b: FOR q IN keys b: SELECT: q in keys a: PUT a[q]-b[q] IN a[q] ELSE: PUT -b[q] IN a[q] RETURN normalised a

For the product of two polynomials, you don't have to use
`normalised`

, since `plus`

always returns a normalised
result:

HOW TO RETURN a times b: PUT {} IN prod FOR p IN keys a: FOR q IN keys b: PUT prod plus {[p+q]: a[p]*b[q]} IN prod RETURN prod

The n-th power of polynomial a:

HOW TO RETURN a power n: CHECK n >= 0 AND n mod 1 = 0 \Positive and integer SELECT: n = 0: RETURN {[0]: 1} n = 1: RETURN a n mod 2 = 0: PUT a power (n/2) IN b RETURN b times b ELSE: RETURN (a power (n-1)) times a

As an example of the use of polynomials, here is the fifth line of Pascal's triangle:

```
>>> WRITE {[1]: 1; [0]: 1} power 4
{[0]: 1; [1]: 4; [2]: 6; [3]: 4; [4]: 1}
```

Here is a simple command to print the result more prettily. Note the method in the for command for traversing the items in reverse order:

HOW TO PRINT POLY poly: IF #poly = 0: WRITE 0 FOR i IN {-#poly..-1}: PUT -i IN p PUT (keys poly) item p IN power PUT poly item p IN coef IF p <> #poly OR coef < 0: WRITE plus.minus[sign coef] IF abs coef <> 1 OR power = 0: WRITE abs coef<<1 IF power > 0: WRITE "x" IF power > 1: WRITE power<<1 WRITE / plus.minus: RETURN {[1]: " + "; [0]: ""; [-1]: " - "}

```
>>> PRINT POLY {[1]: 1; [0]: 1} power 4
x4 + 4x3 + 6x2 + 4x + 1
```

To simplify typing polynomials in, we can do the following:

```
>>> PUT {[1]: 1} IN x
>>> PUT {[0]: 1} IN one
>>> PRINT POLY (x plus one) power 4
x4 + 4x3 + 6x2 + 4x + 1
```

As another example, we know from school that (x+1)^{2} =
x^{2}+2x+1 and that (x+1)(x-1) = x^{2}+1:

>>> PRINT POLY (x plus one) power 2 x2 + 2x + 1 >>> PRINT POLY (x plus one) times (x minus one) x2 - 1

Now some more operations on polynomials. The derivative:

HOW TO RETURN derivative a: PUT {} IN result FOR p IN keys a: IF p <> 0: PUT p*a[p] IN result[p-1] RETURN result

The integral is similar. Strictly speaking, you also have to give an initial constant, but that can be added in separately.

HOW TO RETURN integral a: PUT {} IN result FOR p IN keys a: PUT a[p]/(p+1) IN result[p+1] RETURN result

It will be useful to be able to convert a number to a constant polynomial:

HOW TO RETURN constant c: RETURN normalised {[0]: c}

Here is a function that evaluates a polynomial when its variable has value x

HOW TO RETURN a at x: PUT 0 IN s FOR p IN keys a: PUT s+a[p]*x**p IN s RETURN s

Finally, a function to find a zero of a polynomial, that is a value for its
variable such that the value of the polynomial is approximately zero. The
parameters `u`

and `v`

are
lower and upper limits of where the result must lie; `eps`

gives the accuracy to use: `1e-5`

means 5 decimal digits.

HOW TO RETURN a zero (u, v, eps): \ find a zero of polynomial a, u < zero <= v PUT a at u, a at v IN au, av CHECK sign au <> sign av \ check zero in the range IF au > av: PUT u, v IN v, u WHILE abs (u-v) > abs (eps*u): PUT ~(u+v)/2 IN mid SELECT: a at mid < 0: PUT mid IN u ELSE: PUT mid IN v RETURN v

For instance, to find the square root of two using this function, we have to
solve x^{2} = 2, that is x^{2} - 2 = 0:

>>> PUT (x power 2) minus constant 2 IN p >>> PUT p zero (0, 2, 1e-5) IN r >>> WRITE r, r**2 1.414215087890625 2.000004314817488 >>> PUT p zero (0, 2, 1e-10) IN r >>> WRITE r, r**2 1.414213562384248 2.000000000031545 >>> WRITE root 2, (root 2)**2 1.414213562373095 2.000000000000000

(What would happen if you tried to find the square root of -1?)

However, this function for finding a zero is very primitive. For instance that last example needs 34 iterations to get to the result. Isaac Newton devised a much faster function, using the derivative:

HOW TO RETURN a newton.zero (guess, eps): PUT derivative a IN a' PUT guess, guess - (a at guess)/(a' at guess) IN x, x' WHILE abs(x-x') > abs(eps*x): PUT x', x' - (a at x')/(a' at x') IN x, x' RETURN x'

This only needs 4 iterations for a minimum of 10 digits of precision, but actually gets even more in those 4 iterations:

```
>>> PUT p newton.zero (2, 1e-10) IN r
>>> WRITE r, r**2
1.414213562373095 2.000000000000000
```

Now for a larger example using these operations. Gravitational acceleration is 9.80665 metres per second squared, downwards:

>>> PUT constant -9.80665 IN g

If you propel a ball into the air from the ground with an initial vertical velocity of 10 metres per second, then the velocity at any time is expressed by

>>> PUT (integral g) plus constant 10 IN velocity

so the velocity in metres per second after 1 second is

```
>>> WRITE velocity at 1
0.19335
```

The height of the ball above the ground at any time, in metres, is given by

```
>>> PUT integral velocity IN height
>>> PRINT POLY height
- 4.903325x2 + 10x
```

so the height after 1 second is

```
>>> WRITE height at 1
5.096675
```

How high does the ball go? Well, that is its height when its velocity is zero:

>>> PUT velocity zero(0, 100, 1e-5) IN zero.v.time >>> WRITE zero.v.time 1.0197103023529 >>> WRITE height at zero.v.time 5.09858106471834

When does it hit the ground again? When the height is zero:

```
>>> WRITE height zero(1, 100, 1e-5)
2.03942465782165
```

which is what you would expect, namely that it takes twice as long to reach the ground as it does to reach its highest point.

What is its velocity when its height is 3 metres? The time it is at 3 metres is when height = 3, or in other words, when height - 3 = 0:

```
>>> PUT height minus constant 3 IN h3
>>> PUT h3 zero (0, 1, 1e-5) IN t3
>>> WRITE t3
0.365507125854492
```

and so its velocity at this time is:

```
>>> WRITE velocity at t3
6.41559954423904
```

The function `now`

supplies the date and time as a series of six numbers, year, month
(1-12), day (1-31), hour (0-23), minute (0-59), and second (0-59.9999..., with
accuracy of that delivered by the operating system):

```
>>> WRITE now
(2002, 2, 5, 13, 27, 25.474663)
```

Here is a function to return the day of the week today:

HOW TO RETURN today: PUT now IN (year, month, day, hour, minute, second) RETURN day.name[(day.in.year-dominic) mod 7]^"day" dominic: PUT floor(year/100) IN century RETURN 7-((year+(floor(year/4))-century+(floor(century/4))-1-leap) mod 7) leap: IF (year mod 4 = 0 AND year mod 100 <> 0) OR year mod 400 = 0: RETURN 1 RETURN 0 day.in.year: PUT {[2]: 28+leap} IN length FOR i IN {1; 3; 5; 7; 8; 10; 12}: PUT 31 IN length[i] FOR i IN {4; 6; 9; 11}: PUT 30 IN length[i] PUT day IN total FOR m IN {1..month-1}: PUT total+length[m] IN total RETURN total day.name: RETURN split "Sun Mon Tues Wednes Thurs Fri Satur"

```
>>> WRITE today
Wednesday
```

Here are some examples of the use of texts in ABC.

This example appears to answer questions with 'yes' or 'no' with some
consistency. In fact all it does is output 'yes' if the number of n's in the
question is even, and 'no' otherwise. It uses the dyadic version of the
operator `#`

, which returns the number of times the
first parameter occurs in the second:

HOW TO ORACLE: READ qn RAW WHILE qn <> "": WRITE answer[("n"#qn) mod 2] / READ qn RAW answer: RETURN {[0]: "Yes"; [1]: "No"}

>>> ORACLE Can I ask you a question? Yes Are you happy? Yes Are you unhappy? No Will it rain tomorrow? No So I can expect sun? Yes And will it stay fine? Yes For the whole week? Yes

A well known program in the history of computing is 'Eliza' written originally by Joseph Weizenbaum, but since then much imitated by others. It tries to play the role of a psychotherapist: it asks you a question, you reply, it then makes some comment based on your reply, to which you should make some other reply, and so on. It bases its replies only on the structure of your sentence, or on any keywords it can recognise in the sentence. In other words it makes no attempt to 'understand' the sentence.

This is a simplified version. It only works with keywords, though it could
easily enough be beefed up to start recognising some sentence structures. Here
is an example of its output; the input lines are preceded by a `>`

', the rest, in italics, come from Eliza:

Hello, I'm Eliza. Tell me about yourself. (Type "Bye" to finish) > I'm featuring you in a book Me? > Yes, I thought you'd be surprised You seem very sure of yourself > No, I wasn't sure what you'd say Why not? > Because I was not sure how you would react Not at all? > I had some vague idea of course Tell me about your problems > With thousands of people reading this? What a question! ...

Let's change the subject > What shall we talk about? You don't have to ask that! > That's true What are your interests? > I work a lot with computers Oh computers! They're so stupid! > I was afraid you might say that Tell me about your fears ...

Though this looks quite reasonable, sometimes it can make a real fool of itself by producing a completely unsuitable answer, or by repeating a question you just answered.

The program works by taking each sentence, converting it to lower-case using
the ABC function `lower:`

```
>>> WRITE lower "The moon in June"
the moon in june
```

and then splitting it into a sequence of words using the ABC function `split`

:

```
>>> WRITE split lower "The moon in June":
{[1]: "the"; [2]: "moon"; [3]: "in"; [4]: "june"}
```

It then looks to see if the sentence is one of a small number of simple sentences it knows about (such as 'Yes'), for which it has a number of standard answers ('Can you be a bit more specific?'). This is done with a table whose keys are the simple sentences, and whose items are lists of texts.

If that fails, it looks to see if any of the words in the sentence are 'important' keywords that it can use to get you to further expand on, such as 'love', 'fear' or 'family' ('Tell me about your mother'). This is done with a table of words to lists of texts.

Failing this, it looks to see if your sentence was a question (whether it contains a question mark), and if so gives a canned remark (like 'Why do you ask?').

Then it tries with some less important keywords that it can pick up on (like 'never': 'Never is putting it a bit strong isn't it?').

Finally, being unable to get any hints from the sentence at all, it tries to change the subject, again with a canned 'starter' line (such as 'Tell me about your family').

As you can see, it uses no knowledge about the past conversation, and so quickly gets boring, but it is a fun example. Here is the program:

HOW TO TALK WITH ELIZA: GREET LISTEN WHILE lower remark <> "bye": WRITE reply remark / LISTEN WRITE "Thank you for talking to me. Bye." / GREET: WRITE "Hello, I'm Eliza. Tell me about yourself." / WRITE "(Type ""Bye"" to finish)" / LISTEN: WRITE "> " READ remark RAW

The function `reply`

returns a reply to a remark. It
uses five shared permanent data-structures, which it imports with the `SHARE`

command:

HOW TO RETURN reply remark: SHARE simple, keywords, answers, lesser, starters PUT split lower remark IN sentence SELECT: sentence in keys simple: RETURN choice simple[sentence] SOME word IN sentence HAS word in keys keywords: RETURN choice keywords[word] "?" in remark: RETURN choice answers SOME word IN sentence HAS word in keys lesser: RETURN choice lesser[word] ELSE: RETURN choice starters

You might try programming this in another language, to see how it compares in length.

By the way, notice that `simple`

is a table whose
keys are tables. When first learning ABC it seems unlikely that such a
combination would ever occur, but in fact applications do occur quite
naturally.

The function `split`

makes it very easy to make a
simple document formatter. For instance with the `HELP`

command earlier, you could type in your lines of help, and let the system worry
about filling lines out as fully as possible. This also makes it easier to
change help messages: you don't have to worry about the layout of lines.

The formatter works by buffering words up in an output line. If the next word would make the line too long, the output line is written. Additionally, the output line is written if an input line is empty. This gives a simple paragraph facility.

HOW TO FORMAT doc IN width: PUT "" IN output FOR line IN doc: IF line = "": PARAGRAPH FOR word IN split line: SELECT: output = "": PUT word IN output word.fits: PUT output^" "^word IN output ELSE: FLUSH FULL LINE PUT word IN output FLUSH PART LINE word.fits: REPORT #output+#word < width: PARAGRAPH: FLUSH PART LINE WRITE / FLUSH PART LINE: WRITE output / PUT "" IN output FLUSH FULL LINE: WRITE output /

```
>>> FOR nr IN keys paragraph: WRITE nr, paragraph[nr] /
1 The formatter works
2 by buffering words up in an output line.
3 If the next word would make the line too long,
4 the output line is written.
5 Additionally, the output line is written
6 if an input line is empty.
7
8 This gives a simple paragraph facility.
```

```
>>> FORMAT paragraph IN 40
The formatter works by buffering words
up in an output line. If the next word
would make the line too long, the output
line is written. Additionally, the
output line is written if an input line
is empty.
This gives a simple paragraph facility.
```

If a document is always going to be used as a sequence of words, then it is
worth storing the document not as lines, but as words. For instance, going back
to the help example in section HOW
TO ADD HELP FOR topic in the command `ADD HELP FOR`

instead of saying

APPEND line TO help[topic]

saying

APPEND split line TO help[topic]

In that way `split`

gets used only when the document
is created, and not each time the document is used.

`FORMAT`

is another possible contender for being a
function instead of a command. The advantage is that you can then store the
result in a location for later use, you can enquire how many lines are in the
result, and so on. The only major difference is that instead of using `WRITE`

each time we produce a new output line, we save it in
the result document:

HOW TO RETURN width formatted doc: PUT {}, "" IN result, output FOR line IN doc: IF line = "": PARAGRAPH FOR word IN split line: SELECT: output = "": PUT word IN output word.fits: PUT output^" "^word IN output ELSE: FLUSH FULL LINE PUT word IN output FLUSH PART LINE RETURN result word.fits: REPORT #output+#word < width PARAGRAPH: FLUSH PART LINE PUT "" IN result[#result+1] FLUSH PART LINE: PUT output IN result[#result+1] PUT "" IN output FLUSH FULL LINE: PUT output IN result[#result+1]

```
>>> DISPLAY 50 formatted paragraph
The formatter works by buffering words up in an
output line. If the next word would make the line
too long, the output line is written.
Additionally, the output line is written if an
input line is empty.
This gives a simple paragraph facility.
```

(`DISPLAY`

is in section HOW TO DISPLAY message.)

Finally, let's consider additionally filling each output line with extra
spaces so that each full output line spans the width exactly. We can do that by
replacing the `PUT`

in ```
FLUSH FULL
LINE
```

by an invocation of the function filled:

PUT width filled output IN result[#result+1]

What `filled`

has to do is put extra spaces between
some words. The total extra space that has to be created is `width-#line`

, and this has to be shared between the words on
the line. However, this is seldom a whole number of spaces between each word,
so for each gap we have to convert the number of spaces to an integer.

If we are distributing the extra spaces from left to right and we use `floor`

to convert to integer, the extra spaces will tend to
gather at the right hand end; similarly if we use `ceiling`

they will tend to gather at the left hand end. If
we use `round`

on the other hand, they will be
distributed fairly evenly over the line.

HOW TO RETURN width filled line: PUT "" IN out PUT width-#line, split line IN space, words FOR w IN {1..#words}: PUT " "^^fill IN gap PUT out^(words item w)^gap IN out PUT space-(#gap-1) IN space RETURN out fill: IF w = #words: RETURN 0 \last word of the line RETURN 1+round(space/(#words-w))

```
>>> DISPLAY 40 formatted paragraph
The formatter works by buffering words
up in an output line. If the next word
would make the line too long, the output
line is written. Additionally, the
output line is written if an input line
is empty.
This gives a simple paragraph facility.
```

This example takes a document represented as a sequence of lines, and
returns a cross-reference index of the document: for each word in the document,
the list of lines that the word appears on. It splits each line into words, and
then stores the line number in a table under each word (`SAVE`

from section HOW TO SAVE item IN table AT key is used here), as is `listed`

from section HOW TO RETURN listed l.):

HOW TO RETURN index document: PUT {} IN index FOR line.number IN keys document: TREAT LINE RETURN index TREAT LINE: FOR word IN split document[line.number]: SAVE line.number IN index AT word

HOW TO OUTPUT index: FOR word IN keys index: WRITE word<<10, listed index[word] /

```
>>> FOR k IN keys poem:
WRITE k, poem[k] /
1 I've never seen a purple cow
2 I hope I never see one
3 but I can tell you anyhow
4 I'd rather see than be one
```

```
>>> OUTPUT index poem
I 2, 2, 3
I'd 4
I've 1
a 1
anyhow 3
be 4
but 3
can 3
cow 1
hope 2
never 1, 2
one 2, 4
purple 1
rather 4
see 2, 4
seen 1
tell 3
than 4
you 3
```

HOW TO RETURN index doc: PUT {} IN index FOR number IN keys doc: FOR word IN doc[number]: SAVE number IN index AT word RETURN index

The surprising thing is, this function is exactly the same (apart from the
names used) as the function `inverse`

in the telephone
list example in section HOW TO
RETURN inverse t. Why? Well think of an entry in the document as a
telephone number (the line number) and a list of people who use that number
(the list of words on that line). What we want to produce from a
cross-reference is the inverse: for each name (word) the list of telephone
numbers for that person (the list of line numbers that word appears on).

You'll notice that the list of words in the index begins with the words
starting with a capital letter. This is because the capital letters come before
the lower-case letters in the character set. The way to produce the list so
that the case of letters does not affect the sorting order, is to store the
lower-case version of the word along with the word itself, and alter `OUTPUT`

to ignore the extra word:

HOW TO RETURN index doc: PUT {} IN index FOR number IN keys doc: FOR word IN split doc[number]: SAVE number IN index AT lower word, word RETURN index

HOW TO OUTPUT index: FOR lword, word IN keys index: WRITE word<<10, listed index[lword, word]/

```
>>> OUTPUT index poem
a 1
anyhow 3
be 4
but 3
can 3
cow 1
hope 2
I 2, 2, 3
I'd 4
I've 1
never 1, 2
one 2, 4
purple 1
rather 4
see 2, 4
seen 1
tell 3
than 4
you 3
```

The index of this book was produced using a similar ABC program.

This program takes a document in any language and analyses it by recording all pairs of letters, or triplets, or quadruplets etc., depending on a parameter, that occur in the text. It then produces a randomly generated new text based on the old one by only using those tuples recorded. The nice thing is that the new text bears some resemblance to the old one, while being complete nonsense.

To do this, it uses a table to store for each group of n - 1 characters
those characters that can follow the group. So for instance, in the phrase
'taking three as the subject to reason about', using groups of two letters, the
group "re" can be followed by "a" and "e" (from 'three' and 'reason'), so in
this case `followers["re"]`

will be `{"a"; "e"}`

. Similarly, ```
followers["
t"]
```

would be `{"a"; "h"; "h"; "o"}`

.

HOW TO IMITATE document USING n TUPLES: GENERATE IMITATION FROM n analysed document

HOW TO RETURN n analysed document: PUT " "^^(n-1), {} IN group, followers FOR line IN document: ANALYSE LINE RETURN followers ANALYSE LINE: \ Treating end of line as a space FOR character IN line^" ": SAVE character IN followers AT group UPDATE group WITH character

HOW TO UPDATE group WITH character: PUT (group^character)@2 IN group

(`SAVE`

is in section HOW TO SAVE item IN table AT key ). A new text is generated
from this table by choosing a random start with `choice`

and choosing a random follower for that group. This
follower character is written, and the new group is constructed from the old
group and the new character:

HOW TO GENERATE IMITATION FROM followers: PUT choice keys followers IN group WHILE group in keys followers: GENERATE ONE CHARACTER WRITE / GENERATE ONE CHARACTER: PUT choice followers[group] IN character WRITE character UPDATE group WITH character

Here are some examples of its output with n = 1, 2, 3, 4, 5, using as document the first paragraph of this section: With n=1:

xuwoosr.,eimtotrr t uTxhd eleo dteaeesaebsen aesbetedenst en tt auyarl hecyeesiedtrtrr nai.rotudto,r taa reigni oniee tugnlaouns odi esgpnt ooeot asp peonii n xa cnihels xtateenle Tteeadn trtltuneohrh dd,h rnsh eounisne

With n=2:

The led oring paketesew ord sinecusirdext thin e bairs, las It rs omed pewhing os or be ran tenets, occ. by ce blys gra a ol olyse. bamer, tuproge thiny ts ones r oleply te adedor le omerorakese t tuce w indonon

With n=3:

The thilets programete none te being inguage old or quadruples old onsed occur that the ne, old nice the recor the onses recordin pairs, old onew to this a theneram text bears, whin thending onew text.

With n=4:

The nice thing one, while being those text in thing all pairs of lets, or quadruplets, or quadruplets etc., depending is the tuples it based one by on analyses it based one, while by only using on a rand analyses resemblanguage analyses recorded.

With n=5:

The new text in any language and analyses it by recording is that the old one by only using all pairs of letters, or quadruples recording those tuples recording on a parameter, that the old on a parameter, that then produces a text bears some resemblance thing on then program takes a randomly generated new text in any language and analyses it by only using all pairs of letters, or triplete nonsense.

You can also generate sentences using groups of words rather than characters. Most of the program is the same, the main difference is appending words to the group. A group is most easily held as a sequence of words. Appending a word then looks like this:

HOW TO APPEND WORD w TO group: FOR k IN keys group: PUT group[k] IN group[k-1] PUT w IN group[max keys group] DELETE group[min keys group]

The words are moved up so that groups containing the same words have the same keys and so are identical. Here is a small sample of output using n=3, on a draft of this chapter as input:

To add a node to the end of the number of dots, and then splitting it into words using the same item (which makes them what are called bags or multisets ). Using lists to represent them. The following functions return the union, intersection and difference of two letters, the group "re" can be represented as a sequence of numbers. These numbers are the keys of the words in the sequence is either defined in another entry in the sentence is one of a sequence only works with keywords, though it could easily enough be beefed up to start recognising some sentence structures.

Here is a simple program that generates random sentences from a template, a grammar. The grammar consists of a table, mapping words to lists of sequences of words. Each of these sequences is an alternative definition for the word being defined. Each word in the sequence is either defined in another entry in the table, or otherwise is to be treated literally.

For instance, suppose a sentence was defined as 'I love GIRL', and GIRL was defined as 'Mary' or 'Anne', and none of the other words was defined. Then we would have the following table:

{["Sentence"]: {{[1]: "I"; [2]: "love"; [3]: "GIRL"}}; ["GIRL"]: {{[1]: "Mary"}; {[1]: "Anne"}} }

This is difficult to read, so here's a command to display it more readably
(this uses `listed`

from section HOW TO RETURN listed l again):

HOW TO DISPLAY GRAMMAR g: FOR defined.word IN keys g: WRITE defined.word, ":" / FOR alternative IN g[defined.word] WRITE " ", " " listed alternative /

```
>>> DISPLAY GRAMMAR loves
GIRL:
Mary
Anne
Sentence:
I love GIRL
```

A slightly more involved grammar is:

```
>>> DISPLAY GRAMMAR a.loves.b
BOY:
Mark
David
GIRL:
Hannah
Anne
Sentence:
BOY loves GIRL
GIRL loves BOY
```

To input a grammar, you could use the following command:

HOW TO INPUT grammar: PROMPT "Define: " FOR term WHILE term <> "": DEFINITION PROMPT "Define: " FOR term DEFINITION: PROMPT "Alternative: " FOR alt WHILE alt <> "": SAVE split alt IN grammar AT term PROMPT "Alternative: " FOR alt

(`SAVE`

is in section HOW TO SAVE item IN table AT key ) `INPUT`

uses the following:

HOW TO PROMPT p FOR t: WRITE p READ t RAW

Now given a grammar, here is the command to generate a random sentence from it:

HOW TO GENERATE thing FROM sentences: SELECT: thing in keys sentences: FOR word IN choice sentences[thing]: GENERATE word FROM sentences ELSE: WRITE thing, " "

```
>>> FOR i IN {1..4}:
GENERATE "Sentence" FROM a.loves.b
WRITE /
Hannah loves David
Anne loves Mark
Hannah loves David
David loves Anne
```

The quality of the generated sentences depends entirely on the grammar. For instance, here is the basis of a grammar to produce paranoid ramblings:

```
>>> DISPLAY GRAMMAR paranoid
<Sentence>:
<person> <opines> <something>
<person> thinks that I am <property>
I <opine> <something>
you think that I am <property>
<activity>:
dancing
eating
...
<object>:
<person>
life
my friends
...
<opine>:
despise
hate
...
<opines>:
despises
hates
...
<person>:
my sister
the man next door
...
<property>:
stupid
ugly
...
<something>:
<activity>
<activity> with <person>
<object>
```

and so on. Here is some output using this grammar:

```
>>> FOR i IN {1..10}:
GENERATE "<Sentence>" FROM paranoid
WRITE /
the man next door hates me
my girlfriend hates computers
you think that I am stupid
I despise eating
I am jealous of other people
you think that I am boring
everybody hates walking with my girlfriend
my father thinks that I am ugly
my sister likes computers
I despise my opinions
```

Since earlier we produced a program that imitated a psychotherapist, we can
combine the two: first we need to change `GENERATE`

to
a function that returns the generated sentence:

HOW TO RETURN sentences generated thing: SELECT: thing in keys sentences: PUT "" IN words FOR word IN choice sentences[thing]: ADD PHRASE RETURN stripped words ELSE: RETURN thing ADD PHRASE: PUT words^" "^(sentences generated word) IN words

Now we can write a how-to that lets Eliza and our paranoid talk together to their hearts' content:

HOW TO SESSION patient: WHILE 1=1: PUT patient generated "<Sentence>" IN r WRITE "> ", r/ WRITE reply r/

```
>>> SESSION paranoid
> you think that I am stupid
Do you think stupidity is a good trait, or a bad one?
> my mother hates jogging
And your father?
> you think that I am ugly
Me?
> my girlfriend thinks that I am stupid
How do you get on together?
> my father loves kissing with my girlfriend
Tell me more about your family
> I like relationships
What are your interests?
> you think that I am boring
Boredom is only in the mind
...
```

The ABC Programmer's Handbook by Leo Geurts, Lambert Meertens, and Steven Pemberton

Copyright © 1990, 2002, Leo Geurts, Lambert Meertens, and Steven Pemberton. All rights reserved.