Steven Pemberton, Centre for Mathematics and Computer Science
ABC is a simple language for personal computing. Intended as an alternative to Basic, it has grown to be a powerful tool for expert users, too.
(First published in IEEE Software, Vol. 4, No. 1, January 1987)
ABC is a programming language being designed and implemented at the Centre for Mathematics and Computer Science. It started as an attempt at a suitable alternative to Basic for beginner programmers, so that it was still easy to learn, still interactive, but easier to use and offering program structure. It has developed into an interesting and pleasurable tool for beginners and experts alike. The box below describes why a language like ABC is needed.
ABC is being designed and implemented with an integrated programming environment. It was originally started in 1975 as a language for beginners. Although the project's emphasis has shifted from beginners to personal computing, the main design objectives have remained the same:
The language has been designed iteratively. The version described here is the fourth iteration. The first two versions were the work of Lambert Meertens and Leo Geurts of the Centre for Mathematics and Computer Science (then called the Mathematical Centre) in 1975-76 and 1977-79. They were definitionally simple, being easy to learn and easy to implement.
In the third iteration6, 7, designed in 1979-81 with the addition of Robert Dewar of New York University, it became conceptually simple. It is still easy to learn, by having few constructs — but it is also also easy to use because it has powerful constructs without the sorts of restrictions that professional programmers are trained to put up with but that a newcomer finds irritating, unreasonable, and silly.
Furthermore, this third version (which had a working title of B) was designed deliberately with the new generation of computers in mind by relegating machine efficiency to a lower priority than programmer efficiency.
It is surprising to realize how quickly recent developments in computer technology have caught up with us. Only a short time ago, we were telling people that we weren't considering implementing ABC on machines with less than 128K bytes of main store, and getting surprised reactions that we were considering such huge machines. Today, however, many PCs start at 128K bytes, and 512K bytes is quite usual.
We have now finished a final polishing of the language, based on five years' experience of using and teaching B, resulting in ABC.
One reason that ABC needs a lot of store is that it is not just a language but a complete programming environment.
Traditional computer use for programming involves not only learning the programming language but also a whole host of subsystems and their commands, such as the operating system's command language, the editor, and compilers, which are often completely separate and noncooperating.
ABC, on the other hand, always shows one face to the user, and it is not necessary to learn anything outside the ABC system. This means that ABC must be able to perform many tasks normally delegated to the operating system, or other subsystems, such as editors.
As an example of ABC's simplicity and power, consider the task of creating and maintaining a database of telephone numbers. (See the box below for brief definitions of commands and operators.) You first create an empty telephone list:
PUT {} IN tel
and then add a few numbers:
PUT 4133 IN tel["Leo"] PUT 4141 IN tel["Doug"] PUT 4166 IN tel["Paul"]
Now individual numbers can be looked up (italics are used throughout this article for output produced by ABC):
WRITE tel["Leo"] 4133
or the whole list can be written out
WRITE tel
{["Doug"]: 4141; ["Leo"]: 4133; ["Paul"]: 4166}
The names are kept sorted.
Of course, if the list becomes large, this sort of output becomes hard to read, so the list can be written more tidily with the following.
FOR name IN keys tel:
WRITE name, ":", tel[name] /
Doug: 4141
Leo: 4133
Paul: 4166
It is easy to find out which name belongs to a given number:
IF SOME name IN keys tel HAS tel[name] = 4133:
WRITE name
Leo
But if this is done often, it is easier to produce the inverse table:
PUT {} IN subscriber
FOR name IN keys tel:
PUT name IN subscriber[tel[name]]
WRITE subscriber[4133]
Leo
WRITE subscriber
{[4133]: "Leo"; [4141]: "Doug"; [4166]: "Paul"}
If you need to compute the inverse of a table often, then it easy to make a function to do it for you. Functions may return values of any type.
The telephone list is saved automatically, without any further action on your part. If you log out and come back later, it will still be there.
ABC has just two basic data types: numbers and text. It has just three ways to combine values: compounds, lists, and tables.
The seasoned computer user will be surprised by ABC's handling of numbers. First, following the maxim of no restrictions, numbers may be as large as you want (within the physical limits of the computer's memory). You may calculate 10200 as easily as 102. A Dutch newspaper recently dedicated a whole page to printing the value 2132049−1 (the largest prime then known), which had been calculated with the ABC program WRITE 2**132049−1 which — although it took a while to run — produced the final answer of more than 39,000 digits.
Second, when possible, numbers are always kept exact — even fractional numbers. Thus, as long as you use exactness-preserving operations like addition, subtraction, multiplication, and even division, a number is calculated exactly. Operations like taking the square root cannot produce an exact result in general and so result in an approximate number, rounded to some length.
Texts are strings of printable characters. Unlike many other languages, ABC has a full range of operations on texts such as joining them together, replicating them, and taking substrings. Just as with all types in ABC, there is no maximum size imposed on a text, nor is the size declared in advance.
As an example, look at the definition of a command to box a given text. The operator ^^ repeats a string, the operator # returns the size of a string, and the operator ^ joins two strings together. In a Write command, a / writes a new line.
HOW TO BOX message:
WRITE "*"^^(#message+4) /
WRITE "* "^message^" *" /
WRITE "*"^^(#message+4) /
BOX "Hello!"
**********
* Hello! *
**********
BOX "The ABC Programming Language"
********************************
* The ABC Programming Language *
********************************
Compounds are tuples or records as they are called in some other languages. They are collections of other values, and can be used, for instance, to represent points in a plane. The only operations are packing and unpacking the values:
PUT 0, 0 IN origin
packs the two values 0 and 0 into the one location origin. Similarly,
PUT center IN x, y
unpacks the location center into its two constituent parts and stores them in the locations x and y.
Fields don't have to be all of the same type:
PUT 14, "September", 1752 IN date
Lists are sorted collections of elements, again unrestricted in size. The elements of a list must all have the same type, but they may otherwise — and this is another surprise for the experienced programmer — be of any type. Thus, you may have lists of texts, numbers, compounds, lists of other lists, and so on.
Elements may be duplicated. Amongst other things, you can insert elements, delete elements, find out if an element is present, find the size of a list. This program uses a list of numbers and the sieve method to calculate primes:
HOW TO SIEVE TO n: \ name is SIEVE TO
PUT {2..n} IN set \ set to be sieved
WHILE set > {}: \ repeat indented part
PUT min set IN p \ smallest member
WRITE p
FOR m IN {1..floor (n/p)}: \ remove multiples of prime
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
A table (which was the data type used in the telephone list example at the beginning of this section) is a generalization of an array. It is a mapping from values of any one type onto values of any one other type. Standard programming languages only let you map contiguous integers (and sometimes a few other similar types) onto other types.
It surprises experienced programmers that ABC lets you use any type for the array indexes. But, whether you want mappings from texts to lists, or tables to numbers, or tables to other tables, all are possible.
As an example, consider a program to calculate the distance between pairs of points, that often gets the same pairs of points. One way of speeding this up is to use a memo function that remembers past values and doesn't recalculate them when asked for them again.
This example uses a table to store pairs of points already calculated and the distances between them. The operator keys returns as a list the set of indexes used so far in the table. In this example, this is all pairs of points stored in the table. The Share command causes a global variable to be used instead of a variable local to the command.
HOW TO DISTANCE a TO b IN r:
SHARE memo
IF {a; b} not.in keys memo:
PUT a, b IN (x, y), (x', y')
PUT root((x−x')**2 + (y−y')**2) IN memo[{a; b}]
PUT memo[{a; b}] IN r
PUT {} IN memo
DISTANCE (0, 0) TO (3, 4) IN dist1
DISTANCE (5, 2) TO (20, 10) IN dist2
DISTANCE (3, 4) TO (0, 0) IN dist3
WRITE dist1, dist2, dist3
5 17 5
WRITE memo
{[{(0, 0); (3, 4)}]: 5; [{(5, 2); (20, 10)}]: 17}
The two points are stored in the table as a list {a; b} instead of as a compound (a, b). This means they will be sorted, so that the order used in the parameters won't matter (as in first and third calls of Distance show).
Other surprises for the seasoned programmer that the newcomer will find unremarkable are in the Read command. This command is used to input a value from the user. In most traditional languages you can only read numbers and characters — and then only constants of these types. However, in ABC any type of value may be read, and any expression may be typed as input. This includes variables and functions.
Consider this example. The command
READ base EG 0causes the system to prompt the user for a value. The EG 0 says that it should be a number (in other words, it gives an example of what the input should be).
HOW TO VOLUME:
WRITE "Base: "
READ base EG 0
WRITE "Height: "
READ height EG 0
WRITE "Volume =", 3 round (base*height) /
PUT 10 IN r
VOLUME
Base: pi*r**2
Height: 10
Volume = 3141.593
As you can see, ABC has a small set of rather powerful data types. Most other languages supply you with low-level tools that you must then use to build your own high-level tools. ABC does it just the other way around: You get high-level tools that you can also use for low-level purposes. For instance:
The example ABC programs show that the data types are somewhat unusual but that the commands, or statements, are rather familiar. There are the usual input and output commands, the assignment command, If, While, and For commands, and so on.
Commands like If and While are well-known tools for structured programming. An unusual feature of ABC is program refinement. Refinements explicitly support the idea of stepwise refinement, a technique where you specify your program in a short, high-level form that gives a good overview of what the program does — in effect reducing it to a number of simpler related programs.
This high-level form is then refined by writing these lower level programs in the same manner until the lowest level is reached that can be expressed using commands of the programming language. For instance, the top level of a game- playing program might look like this:
INITIALIZE
PLAY.ONE.GAME
WHILE more.wanted:
PLAY.ONE.GAME
Then PLAY.ONE.GAME might look like this:
WHILE not.over:
DISPLAY.BOARD
GET.MOVE
IF not.over:
MAKE.MOVE
Further steps refine not.over, DISPLAY.BOARD, and so on.
Stepwise refinement is intended to make the process of writing a large program easier by splitting the task into several smaller, and therefore more manageable, subtasks. Surprisingly, although the technique has been around for more than a decade, very few programming languages explicitly support it.
Although subroutines can be used for stepwise refinement in other languages, they rarely are because of the execution overheads associated with calling a subroutine. By supplying a facility without these overheads, ABC encourages the use of stepwise refinement.
A good example of ABC's ease of use is that global variables are permanent in the sense that they remain not only while you work at the computer but even after switching it off and returning later. Thus, variables may be used instead of files in the traditional sense, so there is no need for extra file-handling facilities in the language.
Because ABC variables are dynamic, and unrestricted in size, using them instead of files causes no difficulties. Quite the reverse in fact, because you now can use the powerful data types, which give you random and even associative access to the contents, along with all their predefined operators.
As an example of these benefits, compare the following two programs in ABC and Pascal for finding the length of the longest line in a text file. In ABC:
PUT 0 IN longest
FOR line IN document:
PUT max{longest; #line} IN longest
WRITE longest
In Pascal:
program count(document, output);
var document: text;
c: char;
length, longest: integer;
begin
reset(document);
longest := 0;
while not eof(document)
do begin
length := 0;
while not eoln(document)
do begin
read(document, c);
length := length + 1
end;
readln(document);
if length > longest
then longest := length
end;
write(longest)
end.
These programs illustrate clearly how compact and readable ABC programs are. It is my experience that ABC programs are about a quarter or a fifth of the length of their equivalent Pascal or C programs. Examples include a 1000-line Pascal program that resulted in a 200- line ABC program, a 110-line Pascal cross-reference program that became a 24-line ABC program, and a 284-line Pascal program published in the November 1984 Byte that has an equivalent ABC program of only 24 lines.
The program-size ratio compared to Basic would be even greater in ABC's favor. This clearly has consequences for programmer efficiency, especially because programmer effort is proportional not to program length but to a power of program length. Brooks2 reports that this power is around 1.5, implying that ABC is something like an order of magnitude easier to use than traditional languages.
This seems to be borne out in practice: a program that you might expect to take a week of programming in a traditional language takes about an afternoon in ABC.
The other side of this coin is that, because of its higher level, ABC is no longer so straightforward to implement. And because it is interpreted, programs will not run as fast as equivalent programs in compiled languages.
However, new-generation personal computers are so powerful that they spend a large proportion of their time idle. This trade-off of computer time against programmer time is more than reasonable in view of this excess computational capacity: Most people would far rather spend less time programming in exchange for a slower program. This is part of the success of high-level languages over assembly language.
Furthermore, there are other trade-offs involved when comparing noninteractive languages with interactive ones, such as the absence of a translation phase in an interactive language. For example, in an interactive language, a change in a single line can be tried immediately without having to wait for the whole program to be recompiled.
Of course, the end user of a program cares about how fast a program runs, but not to the exclusion of all other factors, like the cost and the reliability of a program. Again, many people use programs written in higher-level languages, that run slower than if they had been written in assembler.
Comparing ABC with Basic on this score is another matter. Basic implementations tend to be slow anyway, yet many people are willing to accept this slowness in return for interactive access. For instance, Bentley3 reports that Basic on an (apparently large) personal computer he used ran at 100 instructions per second — even slower than the first commercially produced computers of the 1950's, which ran at 700 instructions per second!
Higher level commands like ABC's take more time individually, but fewer need to be executed to do the same job, and more work is done at the faster system level than with a lower level language. The combined effect depends on the application and on the mix of operations in a program.
Simple programs, which take little time anyway, and programs that consist only of simple numeric operations will generally run slower. A program to sum a thousand logarithms took one second in compiled Pascal, two seconds in interpreted Pascal, and nine seconds in ABC.
But more complicated tasks may well run faster in ABC than if they were coded in a lower-level language. For instance, the above program to find the longest line in a 1000-line file took 31 seconds in interpreted Pascal, 13 seconds in compiled Pascal, and five seconds in ABC.
However, even if a program in ABC runs slower than acceptable (for instance a commercial application that must run as fast as possible on a slow microcomputer), the programmer efficiency of ABC still makes it a good choice for the prototyping phase of a project.
While ABC was not specifically designed for educational use, it turns out to be well-suited for teaching. The availability of program-structuring and data-structuring facilities, including support for stepwise refinement, means that students are less likely to adopt bad habits.
More important, because of ABC's high level, a student can quickly become competent enough to produce useful programs rather than just trivial exercises.
ABC is being used in several European educational institutes of different levels and types, with enthusiastic responses. Teachers especially find the interactive elements of ABC useful, because many elementary syntax errors cannot be made in ABC, and because students are encouraged to try features for themselves rather than ask the teacher what to do. The teacher thus has more time to answer the less trivial questions.
Just as with Basic, any ABC command typed at the terminal is executed immediately. Thus, you may use all the features of ABC as a sort of high-grade calculator:
WRITE root 2 1.41421356237
Furthermore, since user-written programs are called in exactly the same way as built-in ABC commands, much of the need for a separate command language often found on computers disappears. Variables serve as files, and since programs are just the equivalent of subroutines in other languages, parameters can be passed to programs using the same parameter-passing mechanism. Systems that allow parameter passing usually do so with a completely different mechanism.
ABC's interactiveness also means that declarations are not used. Basic users usually perceive this as an advantage because it means less typing, while users of other languages, such as Pascal, accept declarations on the grounds that they let type inconsistencies and other similar errors be detected before the program is run, reducing the time taken to get a program correct.
ABC supplies the advantages of both by inferring the types of variables from how they are used (for instance, if you write a*2, a must be a number) and by checking that all such uses are consistent. Furthermore, inconsistencies are checked by the editor increasing the interactive feel of the language.4
One demand on an interactive language is that typing be minimized since so much time is spent at the keyboard. One solution to this (used by many interactive systems) is to use abbreviated commands, but this generally results in very cryptic-looking commands.
ABC solves this by having a dedicated editor that knows much about the syntax and semantics of ABC. As an example, consider the Write command. This is the second-most-used command in ABC (the first is Put), so when you type a "W" as first letter of a command, it is more than likely that you want a Write command. Thus, the moment you type a "W," the system immediately suggests the rest of the command to you and shows that it has one parameter:
W?RITE ?
If you want a Write, you press the tab key and the system positions the cursor so you can type in the expression you want to write:
WRITE ?
If you don't want a Write, but a While, you ignore the suggestion and type the next character, an "H." The system then changes the suggestion to match:
WH?ILE ?:
Suggestions also work for the commands you define yourself (such as Sieve To defined earlier).
The editor also knows about things like matching brackets and supplies them for you, so certain typical sorts of typing errors are not possible. These suggestions are just suggestions — you can still type letter for letter, ignoring the suggestions, and get the same result (assuming you make no typing mistakes!).
ABC uses indentation to indicate command nesting, so there is no need to bracket commands with Begin and End or similar command pairs. The editor knows about indentation and supplies it automatically.
Instead of a single-character cursor that most text editors have, the ABC system has a multicharacter focus, in the style of more modern text editors. However, the ABC focus is based on the syntax of ABC, and there are editor commands to move it according to the program structure.
Thanks to this focus, the editor doesn't need lots of commands to delete characters, words, and lines and to copy characters, words, and lines — just a few to move the focus and a few to specify the action on the focus, such as copying or deleting it.
The ABC editor is a central element of the ABC programming environment. When in ABC, you are always using the editor, even when typing data for Read commands. The ABC system is organized so the editor is used instead of many functions that would normally be performed by a separate command language, like deleting, copying and renaming files and directories, switching to other directories, deleting jobs, and so on.
The ABC system consists of workspaces each containing any number of documents. These documents are of several different types, such as programs, global variables, and text documents. It is possible to edit any document. Index documents list the program units, variables, and so on in a workspace. A global index lists the workspaces. The indexes are editable too: If you delete an entry in the list, the corresponding object disappears. Similarly, you can use the editor to copy or rename any entry.
There is also a document for each workspace, called the session record, where you can issue commands and run the programs in the workspace.
A feature of ABC's what-you-see-is-what-you-get philosophy is that you may edit the commands you have entered and executed in the session record. This causes the changed commands to be reexecuted as if you had typed the commands that way in the first place. For instance, if you had typed in the following commands
PUT 2 IN a PUT root a IN b WRITE b 1.41421356237
and then went back to the first command and changed the "2" to "10," the system displays
PUT 10 IN a PUT root a IN b WRITE b 3.16227766017
This is similar to how spreadsheet programs update their displays after changes.
The system also has an advanced undo mechanism. Any operation can be undone, and by repeatedly pressing the undo key, more and more can be undone, and redone again if you undo too much. Not only is this exceptionally useful when you delete the wrong section of a document but also when you delete the wrong variable or program.
Furthermore, it can be used in place of interrupt when running a program, since the return that started a command running can be undone, returning you to the state before it started running — thus stopping the command.
But how does ABC compare with other programming environments? When considering such a question, you have to take into account the aims and purposes of the language and whether it was designed with its environment. Many classical environments, such as C's Unix,5 bear the marks of being designed for interactive use but lack unity in their components.
For instance, with C, the standard editors know nothing about the language and don't interact with the error messages from the compiler, so they can't take you automatically to the lines in error. Other environments are built around languages not designed for interactive use, such as Pascal. While these make the language much nicer for the programmer to use, they can't take advantage of the unity of language and environment.
Smalltalk is a good example of language and environment designed together. Unlike most languages (and like ABC), it exists only in interactive implementations. It has many features desirable in an interactive system, such as a unified debugger — although the editor is very simple and knows nothing of the language, plus the language is harder to learn than ABC.
Part of the Centre for Mathematics and Computer Science's effort is to create ABC implementations. A pilot implementation ran for some time, and a new portable implementation for Unix machines has been distributed to several dozen sites (with more sites expected). A first implementation for the IBM PC and compatibles under MS-DOS is now available, and plans for other personal computers, such as the Macintosh and the Atari ST series, are well advanced.
The original implementation was written in 1981. It was explicitly designed as a pilot system to explore the language rather than produce a production system, so the priority was on implementation speed rather than execution speed. As a result it was produced by one person in two months. It was slower than desirable, but was still usable.
The current versions of the system 9 are aimed at wider use, and therefore speed and portability have become an issue. The system has also become more functional in the rewrite. Like the pilot system, they were written in C. They were produced by first modularizing the pilot system and then systematically replacing modules so we had a running ABC system at all times. They were produced in a year by a group of four.
Several interesting implementation techniques have been used to speed typical ABC programs. As an example, ABC values are implemented with pointers and reference counts so the cost of assigning a value to a variable is independent of the value's size: It is as cheap to copy a large list as it is to copy a number.
This means that there is a value size above which this method becomes cheaper than ordinary copying. This critical size is rather small, and, since ABC values easily become large, it is advantageous.
Furthermore, Put commands are typically the most- executed command in programs, and so it makes sense to choose a method that favors them. We have just finished the last polishing of the language based on the experience of using the language over the last few years and clearing up a few odd corners. We are now busy adapting the implementation to this revision. When that is complete, the language will be formally released with a book describing the language and its use.8
After that, work on the system will focus on the environment — for instance, to do for graphics and data entry what up to now we have done for programming.
The implementations run on larger machines running Unix (with at least 128K bytes of main store) and MS-DOS (with at least 256K bytes of main store). While not all the facilities of the environment described here are implemented in these releases (in particular, editing the session record), most are implemented. The rest will be implemented later. The MS-DOS implementation will be included free with the Addison-Wesley version of ABC Programmer's Handbook mentioned above, while the Unix implementation is available at cost by writing to the author.
1. Steven Pemberton, Examples of B, B
Newsletter, No. 2, CWI, Amsterdam, June 1984.
2. Fred P. Brooks, The Mythical Man Month,
Addison-Wesley, Reading, Mass., 1975.
3. Jon Bentley, "Programming Pearls," Comm.
ACM, Vol. 27, No. 3, Mar. 1984.
4. Lambert Meertens, "Incremental Polymorphic
Type-Checking in B", Proc. 10th ACM Symp. Princ. Programming
Languages, ACM, New York 1983, pp. 265-275.
5. Brian W. Kernighan and Rob Pike, The Unix
Programming Environment, Prentice-Hall, Englewood Cliffs, N.J., 1984.
6. Leo Geurts, "An Overview of the B Programming
Language," SIGPlan Notices, Vol. 17, No. 12, Dec. 1982.
7. Lambert Meertens and Steven Pemberton, "Description of B", SIGPlan
Notices, Vol. 20, No. 2, Feb. 1985.
8. Leo Geurts, Lambert Meertens, and Steven Pemberton,
The ABC
Programmer's Handbook, Addison-Wesley, Reading, Mass., 1987.
9. Lambert Meertens and Steven Pemberton, "An Implementation of the B Programming
Language", Report CS-N8406, CWI, Amsterdam, 1984.
Steven Pemberton works on the ABC project at CWI (Centre for Mathematics and Computer Science) in Amsterdam. His experience includes work in Pascal and Algol 68. His research interests include programming language design and implementation and programming methodology.
Pemberton has been a lecturer at Brighton Polytechnic in England and a member of research groups at Manchester University and Sussex University in England.
The author can be reached at Informatics AA, CWI, Postbus 4079, 1009 AB Amsterdam, The Netherlands.