The Socio-Technical Beginnings of APL
Eugene McDonnell

Abstract

This paper gives some of the history of implementations of APL, and concentrates on the system aspects of these implementations, paying special attention to the evolution of the workspace concept, the time-sharing scheduling strategy, and the handling of the terminal. It contrasts the development of APL with the development of other time-sharing systems which were being built at the same time.

Introduction

We have grown so accustomed to using APL at terminals of time-sharing systems that it is possible to forget that there is no inherent necessity in the way we use it. It is such a fortunate marriage, however, that it may be useful to tell something of the circumstances that led to it.
 

Early time-sharing systems and APL

It is worth pointing out that the timesharing system developed under Kinslow [4] was not the first system under which the APL group tried to put the Abrams-Breed interpreter. There was a system called M44, the first IBM experiment with a virtual-memory machine, being developed at their T.J. Watson Research Laboratory. The APL group at Research naturally thought of using this when they were looking for a home for the interpreter. However, they ran into a disastrous limitation — the M44 system took seven bits from the terminal communicating with it and passed six of them on to the application program. When the APL group asked if they could have all seven bits passed along, they were turned down with the explanation that “this is against the M44 design philosophy”.

Somewhat reluctantly, the APL group decided to investigate the suitability of the TSM system, being developed by a group fifteen miles away, at another IBM laboratory in Yorktown Heights, called the Mohansic Laboratory. The TSM system was perfectly happy to give the application program complete control over what was sent in, including all seven bits from the terminal, and thus the Iverson group decided to use it for the implementation. The TSM system, after a shaky beginning, had settled down into a reasonably usable system by late 1965, and was able to support about twenty terminals on a modified IBM 7090, the 7093. Furthermore, remote access to this system was possible, so that people were able to dial into it from all over the country, using the IBM tie-lines. Iverson and Falkoff were teaching at that time at the IBM Systems Research Institute in New York City (forty miles away), and were able to use the implementation (called IVSYS) on TSM in their classes. This led to a broad dissemination of Iverson notation, since people came to the Systems Research Institute from all parts of IBM.

It was just at this time, however, that IBM had become extremely interested in time sharing as a commercial venture, because MIT and Bell Laboratories had decided that IBM’s brand-new System/360 was not the best vehicle for their next generation of timesharing systems, and had decided instead to order computers for this purpose from General Electric. Since these were very prestigious institutions, it became a matter of great importance in IBM to show that IBM did have competence in the area of programming computers to do time sharing. A time-sharing group was formed, and the people who had been at work in Mohansic on the TSM system became the nucleus of it, later to be joined by several hundred more. Part of this nucleus was dedicated to keeping the 7093 TSM system running.

At the same time, Ken Iverson was just completing his book Elementary Functions [5]. One part of the publication effort was an answer book to the problems. His son Eric was preparing this, using IVSYS on TSM to verify the answers. The manager of the new time-sharing activity at Mohansic (which came to be called TSS), needing people to work on the design and implementation of the product, decided that he would terminate the 7093 TSM service and reassign those people to the new 360-based effort. This was resisted unsuccessfully by many of the people who were working on TSM. It was also resisted by Ken Iverson, who protested that his work depended on the continuing availability of TSM. The result was that the termination of TSM was delayed for thirty days in order to allow Ken’s answer book to be completed. During that time all the costs of running the 7093 were paid for by Iverson’s project.

It now was clear to the Iverson group that they needed somehow to transfer their work to the new generation of IBM equipment. They obtained access to a 360/50 which had been installed at Research, with two small disks (2311’s). Also, because of a general interest in time sharing around Research, there was an adequate supply of terminals to draw upon, either the older 1050’s or the newer 2741’s. There was, however, one important difficulty in that no communications controller was available to them; a time-sharing system couldn’t function very well without one of these!

At this point, something happened that was to have the greatest significance for APL. The Chairman of the IBM World Trade Corporation — Arthur K. (Dick) Watson, son of Thomas J. Watson, Sr. — was an alumnus and board member of the Hotchkiss School. While on a visit to Hotchkiss, Dick Watson saw students using a time-sharing terminal connected to a computer at Dartmouth College. He was dismayed to learn that the computer at Dartmouth was a GE computer, not one of IBM’s. This was, of course, the original BASIC system, developed at Dartmouth in the mid-1960’s [6]. Watson came back to his office and ordered that something be done to see that the Hotchkiss students were able to use an IBM computer in the same way that they were using the GE computer. Nervous staff members scampered through IBM, looking for the right thing to use in competing with the GE equipment. The first thing they found was a product called QUIKTRAN. This was a system which permitted remote-terminal entry of FORTRAN card images for subsequent compilation and execution. It was sometimes known as SLOWTRAN, and was not the most reliable system ever built. The terminals it used had rectangular type boxes which it jiggled periodically during processing, so that the user would know that the system hadn’t collapsed. The Hotchkiss people were unimpressed with QUIKTRAN, and the IBM staff people had to find something else.

It was then that Dick Watson heard of the system called IVSYS that had been used at the Systems Research Institute and which many people there had thought was a very convenient, user-oriented system. This information probably came from that fine man John McPherson, a vice-president of IBM and Director of the Systems Research Institute. He had attracted Ken Iverson and Adin Falkoff to the faculty of the Institute, was a constant promoter of the use of Iverson notation, and was also the only vice-president of IBM who had an APL terminal in his office. (Although now retired, he continues his interest in and association with APL, and has an APL terminal in his home.)

The reports of the capabilities of IVSYS on TSM were so glowing that Dick Watson used his influence, and soon there was the promise of the delivery of a 2702 communications controller. This arrived without any cables, and it took a good deal of phoning before the cables were finally discovered in a warehouse in Poughkeepsie, whereupon Larry Breed hopped in his Rover 2000 to make the 50-mile trip up the Taconic Parkway to pick them up and bring them back to Research.

The implementors (who by now included Dick Lathwell) were racing against a time limit in order to get a working system. A class in system design, using APL, had been scheduled for the beginning of November at the NASA Goddard Center near Washington, and it was critical that Iverson and Falkoff have a working system to use in teaching the class. It was a very close race. In order to use the Research system from Goddard, it was necessary that the appropriate telephone-company data sets be available. However, the telephone company serving Goddard was unable to provide these, so ten 103A2 data sets were taken by car 250 miles from Yorktown Heights to Goddard by a friendly member of the Research maintenance staff.

On the weekend before the class was to start, the 2702 failed dramatically, and it took two days to locate the expert, who fixed the trouble (a bad clock card) in ten minutes. Furthermore, the system-residence file was accidentally erased, and Dick Lathwell learned very quickly how to generate the host operating system (DOS) and to do something never done before — install APL! On top of that, a catastrophic error developed in the APL supervisor while Roger Moore, who had implemented it, was away in Europe. Dick Lathwell then had to learn the code for the multiplexor channel as well. Falkoff, who was at Goddard, kept calling Breed and Lathwell at Research every ten minutes to see whether it was yet possible to connect to the system. Finally, at eight in the morning of November 11, just as the first class was to begin, it was possible to test a terminal connection. It took a lot of confidence on Falkoff and Iverson’s part in the capabilities of Breed, Moore, and Lathwell to allow them to undertake that class.
 

Performance of two early time-sharing systems

A visitor to IBM’s Yorktown Heights, N.Y could have seen early versions of two different time-sharing systems. The large machine room in the Research Laboratory contained a model-360/67, with 2 megabytes of memory and several 2301 fast drums used for paging, which was being used as a test site for the development of TSS. Across the hall from this room was a much smaller room, containing a 360/50, with 256 kilobytes of memory, using two of IBM’s smallest disks, the 2311, for all external storage. This was being used to deliver an experimental service which used the acronym APL.

It is instructive to contrast the two systems. The number of people at work on TSS was in the hundreds; the group at work on APL never exceeded ten people. TSS was a key project in IBM, and enormous material resources were expended on it; on the other hand, every scrap of resource used in the development of APL had to be scavenged or fought for. At one time a single 2311 disk pack meant the difference between having to shut down the service or allowing it to continue. Nevertheless, despite the disparity in the number of people at work on the two projects, and in the material resources available to each, the giant TSS project was in trouble, whereas the minuscule APL project was bounding from success to success like a chamois on the crags of the Alps.

The TSS project was late in its schedules. The system was unreliable, not being able to stay up more than an hour at a time. It was a struggle to get one terminal supported, then another struggle to get two terminals supported. Terminal-by-terminal its capacity moved slowly upward, each new terminal supported being cause for celebration. The response time was abysmally slow, with minutes going by between input and reaction. The command language, which took a complete book to describe, turned out to be unusable; it had to be thrown away and a new one, equally big, was designed from scratch.

The APL system, on the other hand, began by supporting 30 terminals, with a subsecond reaction time for more than 97% of all inputs. It went from supporting 30 terminals to supporting 64 merely by adding equipment and increasing the size of certain tables in memory, maintaining the same subsecond reaction time for 97% of all inputs. Starting from a scheduled uptime of only six hours a day, it went effortlessly to a schedule that eventually went seven days a week, sixteen hours a day during the week and continuously over the weekend. The system commands in APL were a mere handful, and error messages that could be given were listed on a single sheet of paper.

The APL system was so reliable that a special rule had to be made by IBM to allow it to run unattended. No other IBM system had been so trustworthy that anyone had thought of doing this. It was usually over the weekends that the system ran unattended. To emphasize the point that a new dimension in computer systems had arrived, the APL-machine-room lights were turned off when the system was running like this, so passers-by would look into a darkened room and see just the lights on the console blinking.
 

The workspace concept

One of the features of the TSM system, the first time-sharing host for IVSYS, the predecessor of APL, was that the user’s active body of work could be given a name and stored in a common file with the work of other users. Furthermore, any user could obtain access to the work files of any other user, if that user permitted it to happen. When people used IVSYS, the typical method of operation for a new user was to load the IVSYS file, perform some work with it and then, in order to save it, rename the file (using TSM’s command language) and save the whole collection; the next time the work was wanted, the user would load the new file in place of IVSYS. This crude but effective technique was the precursor of the workspace and library concepts of APL, just as the command language of TSM was the rough precursor of the system commands of APL. Even the sign-off message of TSM was taken over intact to become the familiar sign-off message of the APL system.

Not enough has been written about how effective and how necessary were the ideas of the workspace and of sharing work in the interactive environment of APL. The workspace acts as a convenient unit of programs and data, and provides very effective name isolation, so that a user can have many different kinds of work available in an APL system, and yet not have to worry about naming conflicts. Most importantly, as we shall see, the uniform size of workspaces played a very important role in making APL’s superior performance possible. In addition, by providing to the interpreter a private area where the user’s requests for work could be performed, it made possible the establishment of programming conventions that allowed effective time-sharing to be done without requiring relocation or virtual-memory hardware.

In the discussions that led MIT to decide not to use the System/360 for the successor to their first-generation time-sharing system, CTSS (a contemporary of IBM’s TSM), the MIT designers made clear that virtual memory was an integral part of their computer plans. The IBM point of view was presented to them personally by one of the chief architects of System/360, Gene Amdahl, who made the same argument in print:

The penalty Amdahl mentions may be as high as 20% on current machines; that is, a sequence of instructions run with relocation off will run as much as 20% slower when relocation is turned on. Although Amdahl, along with Gerrit Blaauw and John Cocke, had helped design the relocation feature for the 360/67, he mistrusted the virtual-memory concept and laid down a rule which I have come to call Amdahl’s law: The larger the difference between virtual memory and real memory, the worse the performance of the system. His simulations showed that a system which used programming conventions rather than hardware for relocation could be written without suffering any greater multiprogramming queuing delays and thus, since it would not suffer the hardware relocation penalty, would run as much as 20% faster. His arguments did not prevail, and not only did the TSS project go forward using the 360/67, but eventually the entire line of large IBM computers acquired virtual-memory hardware, beginning with the System 370/158 and 168.

The relevance of all this to the history of APL is that APL fully justified Amdahl’s claim that efficient programming techniques could be used with System/360 to permit these machines to do effective time sharing. It is probably safe to say that no more effective time-sharing systems have been built than those which run APL. It is remarkable that even today, when almost the entire population of large IBM and IBM-compatible machine users have begun to use operating systems which require relocation, there are still APL systems which run on these machines without the aid of relocation or virtual memory. For example, the I.P. Sharp APL system runs on a pair of 4-megabyte Amdahl V6-II computers in Toronto, using the relatively primitive Sharp-DOS operating system, and runs, of course, unrelocated. This means that if the same APL interpreter were to run on the same machinery, but under a virtual-memory operating system such as VM or MVS, it would run as much as 20% slower. APL was able to do an effective job of software relocation for several reasons, but the fact that the monolithic workspace was the unit of interpretation is probably the most important of these.
 

APL’s scheduler

In a time-sharing system, the key to good performance lies in the way the external storage devices are used. Here the contrast between the TSS and APL systems was most remarkable. On TSS, one could look through the glass windows of the disk devices and watch the motion of the arms. These jerked rapidly back and forth, swooping over wide areas of the disk faces, with the appearance of someone in the grip of St. Vitus’ dance. On the APL disks, one arm would be moving quite regularly, like the escapement mechanism of a clock, as it went from one track to the adjacent track, then to the next track, and so on, over fifty or so tracks in several seconds, and then retracted to the beginning and started the cycle over again. Sometimes the total excursion was more, sometimes less; it was so regular that an experienced person like Roger Moore, who was principally responsible for the APL supervisor, could tell how many users were signed on by watching it.

The reason for the behavior of the disks on the TSS system is that “demand paging’ was being used to manage the computers memory, and the level of technology at the time was such that this was one of the least efficient ways of managing computer memory. I won’t go into the details of demand paging, or discuss the virtual-memory question at all, other than to say that the question of how best to manage computer memory in a multiprogramming environment is still being discussed today.

The APL scheduler gained much of its effectiveness from its simplicity, and its simplicity derived from the fixed-size workspace (which was initially 36,000 bytes, or slightly less than one 2311 cylinder, in size). The scheduler was designed by Larry Breed and Roger Moore, and implemented by Moore. It had three components, each completely unaware of the other two. One scheduled the swap channel for writes, one scheduled it for reads, and one scheduled the computer. The memory of the computer included a certain number of areas of contiguous memory, each large enough to accommodate a workspace; these areas were called slots. The swap-write component of the scheduler looked to see if the swap channel was idle. If it was, and if there wasn’t an unused slot, it chose the active workspace in one of the slots to be written out. The one it chose was either a workspace which had finished execution, or whose time slice had ended, or, if there were none of these, the one that had been in the memory longest. It chose the cylinder where this workspace was to be written by finding the vacant cylinder closest to or at the current position of the disk arm. More often than not, the disk arm was already positioned at a vacant cylinder, as a result of the action of the next part of the scheduler to be described, the swap-read component. If there was an unused slot already in memory, it didn’t bother creating another one.

The second part of the scheduler, the swap-read part, also did nothing if the swap channel was busy. If it was idle, however, it tried to find a workspace on the swap disk that should be brought in. Half of the time, it went first through those workspaces which were associated with a user who had an unserviced input, and only if it found none of these would it search out a workspace representing a swapped-out user who was currently in a compute-bound state. On every other excursion of the disk arm, it would play no favorites. The way it chose which workspace to read was quite simple. It merely looked for the workspace satisfying its criteria (recent input, or any, depending on the kind of excursion it was on) which was closest to the current position of the disk arm. This was often the workspace on the next adjacent cylinder, and thus the disk-arm motion was minimal. The swap-read part of the scheduler, having chosen which workspace to read in, ended its job, and the computer-dispatcher portion took over. Note that the swap-read and swap-write portions worked in complete harmony with each other, but completely unaware of each other’s existence — there was no direct communication between them.

The computer-dispatcher part of the scheduler had a very simple job. It simply moved a pointer in a cyclic fashion from one slot to the next eligible slot, indicating which workspace was to be the target for the interpreter when next the interpreter was entered. That’s all there was to it, and a more harmonious or smoother-working scheduling technique has not come to my attention.
 

Terminal handling

Although the swap-disk scheduler was the key component of the supervisory system as far as overall system performance is concerned, the user at the terminal was just as much concerned with superficial aspects of the terminal handling in forming judgments about how well the system was performing.

One clever feature of this early APL was the way in which the character used to indicate the presence of a system command, namely the right parenthesis, was also used to distinguish what kind of terminal the user was at. On the TSS system, a separate bank of telephone numbers had to be set up for each kind of terminal that the installation wanted to support, because different terminals used different transmission codes for the characters.

This considerably complicated the burden on the user, who had to be aware of this difference, and remember as many telephone numbers as there were terminal types. Roger Moore’s multiplexor code took a different approach, which made the user’s burden as light as possible. It simply assumed that the terminal type was ambiguous until the first character of the initial transmission came in. The transmission code for the right-parenthesis character was different for each terminal type that was supported (the 1050, and the EBCDIC- and correspondence-coded 2741’s), so the first character had to be one of three codes. If it was none of them, the input was ignored, and a fresh input awaited. If it was one of the three possible codes, the terminal type was then known. Thus the APL system needed only one telephone number for all of its telephones.

Among other things the first APL system did to keep terminal users happy, was to allow computing to go on concurrently with printing of the output. Furthermore, Breed and Moore spent large amounts of time fine-tuning the terminal-handling part of the system, to give the minimum number of idles at the end of a line of type, so that the printing element was no sooner back at the left margin than typing immediately began for the next line.

One of the most characteristic conveniences of the system is the cue chosen for the user to make a new entry. On other systems being developed at this time, this user cue varied from one kind of character sequence to another: on one system a question mark would be printed, on another, a rather long-winded time stamp, on another, the word “READY”. In keeping with its general policy of informing the user as briefly as possible, the signal APL uses to indicate that output display has finished, or that computer processing is over, is succinct indeed. No printing characters appear at all: six spaces are sent, moving the cursor or printing element to the right, and the keyboard is unlocked for a new input. To me, that six-space cue is one of the key items in APL’s elegance. Larry Breed recalls that it was Ken Iverson who suggested it.
 

Conclusion

Eventually the TSS project got straightened out, so that by 1970 or so it was able to do useful work. This was after it had been shown conclusively that demand paging was a failure, given the currently available storage technology, and people were beginning to discuss the notion of “working set”. It was, however, a costly experience.

The key difference between the TSS and the APL projects, that made the great early success of APL possible, and the initial failure of TSS inevitable, was that the TSS implementers were attempting to push the technology beyond the limits of the possible, and they didn’t realize this when they started. On the other hand, the APL implementers had modelled their design beforehand, and furthermore had an intelligent understanding of the limited capabilities of the equipment available to them. They managed to extract from this equipment all that it was capable of delivering, but understood that there were limits to the possible.

Acknowledgments

I would like to thank Larry Breed of IBM; Paul Berry, Dick Lathwell, and Roger Moore, of I.P. Sharp Associates; and Al Rose of STSC Inc., for supplying me with many of the details of the early implementation.

________________________________

This paper was presented at a meeting celebrating the tenth anniversary of commercial use of APL in Scandinavia, held in September 1979 in Tivoli Gardens, Copenhagen, Denmark.
 

References

First appeared in APL Quote-Quad, Volume 10, Number 2, 1979-12.