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

CHAPTER 2

Examples of ABC

Introduction

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.

Two First Examples

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.

A Telephone List

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 ADD­NAME : 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?

A Guessing Game

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!

Some Common Data Structures

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.

Stacks

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

Sequences

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

Sets

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"}

Queues

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.)

Trees

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

Graphs

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

Numbers

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

Primes

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.

Recurring Fractions

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

Pi

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 k2/(2k+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

Polynomials

A polynomial is an expression such as 7x5-4x4+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 = x2+2x+1 and that (x+1)(x-1) = x2+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 x2 = 2, that is x2 - 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

Today

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

Sense and Sentence

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

An Oracle

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

Eliza

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.

A Simple Document Formatter

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.

A Cross-referencer

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.

Imitation

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.

Generating Sentences

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