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