The Early Development of POP

How I came to create POP-1

In 1960 I went to Manchester University as a research student in the Mathematics Department. There my nose was pointed in the direction of Category Theory by Walter Ledermann, my first supervisor. However I was enticed away from such abstract studies when I made the acquaintance of the Manchester Atlas computer, a machine considered to be so powerful that `it could do anything', as I was told in response to my query to one of its designers (I don't recall whom) when I asked whether it could drive a motor-car. We are wiser now, both in knowing that more power than the weedy 1 MIP of the Atlas is needed for vision, and in knowing that human performance in that particular task is so woefully inadequate that any new technology for personal transport must be greatly less perilous than the man+motor-car combination.

Given my infatuation with the Atlas and my particular perch in the tree of knowledge, my thoughts turned to the application of computing to mathematical reasoning. Firstly I tried to write an assembly language program to solve some hoary wordy problems of group theory. Then I took a course in Mathematical Logic from Robin Gandy, in which he described the Beth Tree method for formal deduction, and I turned my attention to implementing logic.

Initially I tried using the Compiler Compiler on the Atlas (That is THE Compiler Compiler, of which YACC is Yet Another development - The Atlas was in many ways the first of the modern machines being possessed of a virtual memory, and 128 B-lines (or index registers as they are called in the US)). This allowed me to define beautiful but evanescent data structures to represent terms in Predicate Calculus. Alas they were built on the stack - fine for a simple non-optimising compiler, which used them to toss off code - but as soon as the syntax routine which built the structure exited, the terms vanished in the twinkling of an eye. From that I learned that you do not build your data-structures on the stack if you are want them to outlive the procedure that created them, as you are bound to want to do for serious symbolic programming.

My eyes were opened to a better way of doing things by the Oxford Summer School on Non-Numerical programming, held in 1964. There I heard Christopher Strachey talk about CPL, there was an exposition of LISP, and a description of packages of Algol procedures to do list processing. From this latter I think I took the idea that perpetuating the names of instruction fields in an IBM antique was an odd way to express list operations, and that head and tail were much more descriptive. Also I learned about how to use a stack to evaluate expressions, and about garbage collection in LISP. This showed me the way round the problem that I had had with the Compiler Compiler - that the main working store for a symbol-processing language should not be the stack but should be what is now called a heap, under the control of a garbage collector.

By this time I had moved from Manchester to Leeds University, where the computing equipment was at the time less grand, consisting as it did of one Ferranti Pegasus. This was a valve (US vacuum tube) machine, with a drum of some 8192 39-bit words, and a ``main memory'' of 56 words implemented with nickel delay lines and offering `instant access' every one third of a millisecond. The drum was 'paged' into these 56 words - but the user had to program this explicitly. An added bonus on the Leeds machine was the magnetic tape drive, which had a buffer memory the same size as the main memory, and could be used as a kind of 'instant access' drum.

There was an implementation of LISP on the Pegasus, but it seemed to me that that language must suffer performance problems, since the program was held as linked lists on the drum. Thus to fetch a LISP instruction would take one drum revolution (20ms) I believe. It seemed to me that keeping a reverse Polish sequence of instructions in consecutive storage locations would overcome the problems of locality that seemed inevitable with interpreted LISP. I was of course right, and the problem still exists. LISP machines are not engines for interpreting list structures, but use sequential code, for the same reasons, though of course speeds are scaled up by the odd few orders of magnitude.

Thus I was led to trying to provide LISP capability, written in reverse Polish form. Originally I seem to have referred to this as `LISP' but at some point I started talking of `COWSEL' for COntrolled Working Space Language. It was not a very exciting name, as was to be pointed out to me later. Nor was it a very distinctive one.

The flavour of this language can be gauged from the following sample, taken from a print-out of the time (annotation is 1994).

*F   MEM                    Start to define a function called MEM
*L2  X.Y                    It has two parameters (L is for lambda).
*W                          It has no other "working" local variables
*D   MEM                    Start of the body of the definition.
Y.ATOM.THEN *Q0 END         Empty list? If so, return 0 (for false)
Y.HD.X.EQUAL.THEN *Q1 END   Head of the list = x? If so, return 1 (true).
Y.TL -> Y.REPEAT.END        Iterate (cheaper than recursion).
The corresponding modern definition in POP-11 is:
define mem(x,y);
    if atom(y) then  return(false) endif;
    if y.hd = x then return(true) endif; -> y;

The letters prefixed by an asterisk are the only symbols that had a special action at compile time. *Q, of course, is quote. In particular, THEN, was not treated specially by the compiler, in effect it was a built in procedure that simply ran through the interpreted code until it found the next END code. Since function definitions were limited in size by the requirement that they fit into a small area of the 56 words of fast store, this posed no insufferable overhead.

The built in procedures were written in (numeric) machine code for the Pegasus, Some seem to have been 'hard-wired' into the assembly code for the COWSEL system. Some were mixed in with user-generated code. These had a format *B . Here was an integer which specified where the code was to go on the drum (allocation of drum space was manual apart from list-cells). Arithmetic was, I think, carried out on positive numbers only.

Built-in list processing functions included HD TL and CONS. Library machine-coded functions were the following:

REPEAT      Provided explicit tail recursion by jumping back to the start
            of the function
SP          Print n spaces, as in POP-11
NL          Print n new lines, as in POP-11
+           Add       two  integers
-           Subtract  two  integers
TOHD        The updater of HD - (SETCAR in LISP)
TOTL        The updater of TL - (SETCDR in LISP)
EQUAL       Recursive equality.

Only positive integers were available, since the sign bit was used as a tag.

The concept of the updater as an integral component of a procedure was yet to come - it was introduced into POP-2 as a result of the influence of Peter Landin and Christopher Strachey.

The Stantec Zebra

After I had been a year at Leeds, the University acquired a KDF9 computer. This was thought to be so precious that the old friendly arrangement with the Pegasus was thrown over, and programs were run in batch by operators. After perhaps two months of trying to convert my software to run in this `improved' environment I decided that I was not cut out for batch - my mind is far too imprecise to get programs right first time or even 10th. I have never subsequently used batch mode operation. Instead I begged the use of the Stantec Zebra from Dr Orde Smithe, the director of the Computer Lab. at the Bradford Institute of Technology. This was a singular machine - the best characterisation I can give it is that it was user micro-coded, at least in the sense that every bit in the function part of the order-code operated a gate in the mill (Or CPU as it is pompously known in the United States). Since the machine had been first designed, core-store and transistors had been invented, and the Bradford machine had benefited from these innovations, although the core-store was treated rather like a no-wait drum. Unlike the Pegasus, where instructions were obeyed from the 56 word main memory, in the Zebra they were obeyed straight off the drum. The effect of this was that if one wanted a fast program, when writing a jump instruction one had to find somewhere to jump to on another track of the drum just a little ahead of the current instruction, rather like those video games that teenagers are so good at. Thus one had quite a layout problem to optimise a program. My basic identifier read loop for Cowsel could be executed in half a drum revolution, so I had two copies on each half of the drum, and was able to read tape at 200 characters per second (for which I was accused of endangering the poor tape reader, which normally ran at 100 cps.) At either speed the reader had to stop the tape between characters, being a high speed Elliot device, and so it was rather noisy.

Language evolution at Bradford was not great - I just got up to speed when I left for Edinburgh. However I replaced the single letter 'keywords' like *F by underlined reserved words - the flexowriter machines allowed underscoring of letters, and were intended for writing Algol.

Here, without underscored reserved words, but otherwise unaltered is the definition of member for Zebra Cowsel.

function member
lambda x y
comment Is x a member of list y;
define      y atom then *0 end
            y hd x equal then *1 end
            y tl -> y repeat up

Note the introduction of comments, and the termination of the function definition by the reserved word up. Note also that function applications and variable pushes were not distinguished by syntactic form in which they occurred, as in POP-2 or POP-11, but by the properties of the identifier, so that they were rather like operators in POP11.

Much heavily used data was held in the 1024 words core-store, including the stack, which was automatically pushed onto drum if necessary. I do not recall where list-cells resided, though I think it was on the drum. While I have the code for the implementation, I am not easily able to understand it now - the moral is, always comment your code liberally!

In the spring of 1965 Donald Michie came and gave a talk at Leeds. At the same time he was doing a survey on interest in non-numerical computing in the UK. He invited me to come and give a talk at Edinburgh. I tucked myself in a coach behind one of British Railways new diesel locomotives, which failed at Newcastle, and had to be replaced by one of the few remaining steam locomotives (an A4 Pacific I like to believe, but I couldn't be sure). I well remember my first sight of Edinburgh as I emerged from Waverley Station - the sense of verticality of the city, as though one had emerged into a gorge. Making my way to Donald's Experimental Programming Unit, I was told that I was expected a week later. However everybody was very hospitable, and I was introduced to the group, including Rod Burstall, Jim Doran. Margaret Pithie, Jean Hayes (now Jean Michie), Roger Chambers. Evenings appeared to be one long party, and I felt I had finally made it into the 60's.

Rod, at some point then or during the next weekend, expressed interest in having me come and work - if he could persuade Donald that it was a good idea. It seems that he did, and I was very happy to come - I was not being a great success as an assistant lecturer in Mathematics at Leeds.

And now I have a denial to make, although as Garret Mattingly [8] warns us about that inventive Welshman David Gywnn, there are stories that no amount of rebuttal can quash. Having accepted a post at the EPU, I set off to travel from Leeds to Edinburgh in a craft of my own construction. Now, while I have become quite proficient in the art of navigation, it must be admitted that proficiency in the shipwright's craft seems to have eluded me. The belief that any bug can be eliminated at any stage may be valid in the domain of interactive computing, but must remain anathema in more concrete domains of engineering. However I cheerfully set off, down the Aire and Calder Navigation to the Humber. I caught the ebb on that very tidal estuary and was carried almost to Kingston upon Hull. Thence, some tides later, I set off into that stern environment the North Sea. One night, as is its wont, that body of water betook itself into something of a turmoil, and morning found me very much afloat, but with both the daggerboards of my little sailing catamaran snapped off. Alas, one cannot do a quick edit, a little incremental compilation to up the scantlings, and proceed according to plan when one is some nautical miles North East of Scarborough Head. So the offer of assistance from a passing trawler - a species of vessel whose economic doom was yet to be manifest - was welcome. I was transferred to the larger vessel with no damage to my person and am here to tell the tale, but the fate of my craft was far otherwise - she would not tow, and could not be lifted and was destroyed in the attempt. Now for the rebuttal - while sundry goods and chattels of mine were lost in this shipwreck, it in not the case that a nearly complete Ph.D. thesis was left washing around in the North Sea. My only claim to an original contribution in that respect is that I must have been one of the earliest of that clan who are known, in this land I now inhabit, as `computer bums'.

The Experimental Programming Unit had obtained the money to buy a computer of its own, and had opted for an Elliott 4120 (q.v.). However it was not yet available, and for the first few months I used an Elliott 803 at a place called SMAC. The Unit was supposed to be using Algol 60 as its language, and during this period I did some work on equality inference in group theory, using Algol on the 803, which was a serial computer, but otherwise quite modern.

I had to mount a little rebellion to do any more work on COWSEL - and this did not start until our 4120 was installed, which was early in 1966 I believe. The currently accepted doctrine in the EPU was that Algol 60 was the best language to work in. A number of people had written Algol procedures to do basic list-processing operations. However I was convinced that the only way to provide a truly functional language was to employ a garbage collector. And, I argued, it was impossible to extend an implementation of Algol to permit garbage collection, since the compiler did not preserve enough information at run-time to allow us to do so. In particular it would not be possible to distinguish between pointers to the heap and other data on the stack. This seems to be a problem that people fail to appreciate even now, if one is to judge by the failure to provide proper garbage collection in some C implementations of AI languages.

With this argument as back-up I did a little clandestine implementation of COWSEL. Since the 4120 possessed a console typewriter, which was an expensive IBM golfball to boot rather than a crummy teletype, it seemed an obvious step to permit input to be typed in on this device, as well as via the paper tape readers. I realise now that I was exhibiting a classic syndrome of AI workers - diverting my efforts to tool building rather than to implementing intelligence. However, since this machine was much easier to program than anything I had worked with before (except the Atlas), I soon made enough progress to be able to interest Rod Burstall in what I was doing. Rod then arranged for me to give a little demonstration to Donald Michie, in which I seem to recall that he asked me to implement a little procedure on-line, and which I was readily able to do. Donald rapidly became enthusiastic about the language, but expressed the opinion that Cowsel was not a good name. He said that it was boring and anyway nothing to to with cows. He also made some sensible changes in the reserved words, in particular EXIT instead of END (the POP-11 equivalent is return; endif). END was used to terminate a function definition.

I resisted changing the language name, but found myself out-manouevered - I was presented with a fait-accompli when I came back to Edinburgh after a short holiday. From now it was called POP, which, it was explained to me, stood for 'Package for Online Programming'

The name "Cowsel" was used in the first EPU-R-12 description of the language, dated 21 April 1966, at which time the implementation was working on the 4120. The name POP-1 was used in EPU-R-17.

Rod immediately started using the language and came up with some new ideas. These were mostly based on the use of macros - a textual macro language was being used by Strachey's group in Oxford as part of the implementation of CPL. However Rod suggested that we could employ an item-based macro, which would simply be a function which was executed as soon as its name was read by the itemiser (In the compiler literature this is called a tokeniser). This macro could then read whatever tokens followed it on the input stream. It could produce results by assigning a list to a global variable INSTREAM. The compiler would take input items from INSTREAM if it were a non-empty list.

Using this macro capability, which Rod persuaded me to implement, he was able to graft a syntax analyser into POP-1. This was activated by a macro called, somewhat confusingly, REVPOL. This would read and parse an item sequence terminated by the item ESCAPOL. The square bracket notation for constant lists was introduced at this point, and Rod invented the technique of converting stacked items into a list. Thus his syntax analyser would allow one to write:

<< (1+2), a*b, f(g(1,2)), << a,(b+c)>>,"ab">>
Which is equivalent to the modern:
[% 1+2, a*b,  f(g(1,2)),  [% a, (b+c) %], "ab" %]

The development of POP-2

As we have seen in the previous section, by July 1966 we had a language, POP-1, which bears a strong but superficial resemblance to today's POP-11. However the resemblance was indeed superficial. The garbage collector only collected list cells. There were no floating point numbers, no user defined record classes. It does not appear that procedure-valued local variables were possible, though of course procedures could be redefined.

At this point Rod and I decided that we wanted to redesign the language from the ground up. In this enterprise Rod could be thought of as the theorist and I could be thought of as the implementer.

We would put in arrays and floating point numbers, because we felt that we might want to do robotic kinds of things. We would provide a garbage collector that could handle multi-word items, including function bodies.

While POP-1 had been interpreted, we discovered that the 4120 instruction set, designed by a team led by Tony Hoare, was capable of supporting a compiled code - we took a bit of time to discover this because the crucial stack PUSH and POP instructions we called, somewhat cryptically, MVE and MVB, and at first we had not read their specifications carefully. However the 4120 architecture was excellent for our purposes, and much better than the ICL 1900 machine. Apart from the MVE and MVB instructions, which provided the operations equivalent to sysPUSH and sysPOP on the POP-11 VM, there was (most unusually) an indirect subroutine call JIL, which provided the eqivalent of a sysCALL for a variable restricted to having a procedure value, and of course formed the basis of the capability of redefining procedures incrementally.

In addition the machine provided an `extracode' capability. On the Atlas, extracodes were provided by ROM, and appeared as an extension of the order-code. On the 4120 extracodes we in effect subroutine calls that were vectored through a set of memory locations. Part of the function code of the extra-code determined which memory location the extra-code was vectored through, and the user could set the vector values to define his own extra-codes (although many were reserved by Elliott for their own purposes, and some indeed became bound to firmware in the 4130). We used the extracodes to provide operations necessary for POP, the benefit being primarily that we could call them using a single word instruction. Extracodes were provided to call a procedure held in a variable not restricted to procedure values, to call the updater of a procedure and to do a backward jump. This latter was necessary because we had to check for stack violations and also to allow a user process to be suspended in the MultiPOP timesharing system.

The 4120 was designed to be a cheap machine, which meant having a rather restricted set of registers. There was an `accumulator', the M register, in which all fixed point arithmetic was done. There was a `reserve register' R which acted as a B-line for indexed access to data. This doubled as the stack pointer in MVE and MVB instructions. The program counter, or S register, was restricted in size to 17 bits, of which the least significant bit was used to access half-words. All of the instructions that formed the target code of the POP compiler were 1 word instructions.

The shortage of machine registers made one important decision for us. We were concerned whether to implement lexical variables, in the manner of Algol 60, or whether to continue to employ the POP-1 technology whereby the current value of a variable having a given name was stored in a fixed location, as in POP-11 variables declared with vars. (These are now called special variables in Common Lisp). We opted for retaining the POP-1 approach because we were using the R-register as stack-pointer, and so lexicals would have been very inefficient, since there was no other quick means of indexed access. Of course if stack use were manifest at compile time, one could have used a computed index relative to the R-register, but we wanted to preserve the `open stack', partly because of we needed to write certain functionals like newarray which returned functions which take a variable number of arguments - something that still cannot be done in more recent languages like ML where stack use is manifest to the compiler. The other advantage we saw to the POP-1 way of doing things was that the current values of variables were available to the user on an error - in those days popready was the default function to be called on an error, and this meant that variables had the values that they had taken in the innermost function call.

The idea of a 'left hand value' of an expression (i.e. what happened when an expression was the target of an assignment statement as in

    A[i,j] := x

in Algol.) was impressed on us by the work on CPL. We were however strongly influenced by the idea of a functional language, of which Peter Landin was the outstanding exponent in the UK, and so treated the updating of expressions by introducing a modified functional approach - any function could in principle have an associated UPDATER function.

We saw the need to have functions created dynamically. Originally I felt that making the compiler available as a function would be all that was needed - so we did indeed provide the POPVAL function. However Rod argued the case for an alternative intensional capability. CPL was providing closures, in which relevant parts of the environment of a function were bundled up with it if it was returned as the result of a procedure. Readers will be familiar with the problem. Consider the function product procedure defined below:

define funprod(f,g);

The result of a call of funprod is the inner anonymous procedure. However the variables f and g are free in this procedure, and they should have the values that they had when funprod was called. To a weary implementer with a small target machine, the thought of having to provide the apparatus to find the free variables in a procedure body, and arrange for them to be given values before that body was executed, seemed too much. The requirement was clear - somehow the values at the time of invocation of the outer procedure had to be attached to the inner procedure. The obvious hack was to make them parameters of the inner procedure and generate a short segment of code that would push them on the stack before calling the inner procedure. The syntax we developed to indicate this has survived into POP-11:

define funprod(f,g);

We called this operation `partial application'. In a sense this is a misnomer, since in the lambda calculus this is just ordinary application. [In the lambda calculus functions only take 1 argument, and functions that are conventionally thought of as having multiple arguments are usually treated by successive applications. Thus (+ 2) denotes the function ``add two'', and (+ 2 3) in the lambda calculus means apply the function + 2 to the argument 3 (obtaining 5).] I.e. (+ 2 3) is syntactic sugar for ((+ 2) 3). The lambda calculus (+ 2) is in fact the POP-11 nonop+(%2%) - courtesy of the commutativity of addition.

This technique for avoiding the use of free variables is now dignified with the name of ``Transforming Lambda Expressions into Supercombinators". An algorithm for performing the transformation is well known, see [10] Chapter 13. Of course we expected people to do it manually.

In POP-1 we had used tag bits to distinguish between integers and other objects. This was extended in POP-2 to allow us to distinguish between integers, very short floats, and other objects. Since the 4120 was a word-addressed machine, it made sense to have the tag bits be at the top end of the word, so that pointers could be used unchanged. The 24 bit word meant that the top bits were, in those days, insignificant for addressing, and fortunately they were simply ignored by the hardware. We wanted integers to be represented normally, so that a POP integer was just a restricted kind of machine integer. Thus we were led to use the top 3 bits of the word to indicate type and sign. 000 and 111 indicated positive and negative integers. 01X indicated a pointer 001 and 110 indicated a short float. The floating point precision of short floats was very limited - about equivalent to log tables I seem to recall.

In extending the storage control to handle multi-word blocks of store my initial proposal was to divide the store into what I called `cages'. Each cage would contain only one class of data-object. The idea was that one had a `zoo' of data-objects. The zoo consisted of cages, and one knew what kind of animal (data-object) was in a cage by looking at the label on the cage. Since the cages were to be all of the same size 2^n words say, and aligned on store boundaries of address k2^n, the cage to which an item belonged could be determined by shifting the item address down n bits. A given data-class might occupy more than one cage, but a table-lookup on the cage-bits would give the actual data-class of an object.

However the zoo approach would have been complicated to implement, and on a visit to the University of Aberdeen, Michael Foster told me of the system he was currently using for the Absys development. This was to employ an extra key-word at the beginning of every data-object to indicate its type. I believe that he subsequently decided to use the caged system, but I thought that the key-word, pointing to a key-cell was the best for our purposes: it was simple to implement, and did not leave us with lots of partially filled cages. Since we were anxious to provide user-defined record classes, each of which would have required the setting up of a cage, it seemed that the saving of the key-word would be more than counterbalanced by the existence of unused space in cages.

In later years, when we had a larger 4130 system, we were forced into a semi-caged implementation because the machine architecture placed addressing restrictions on certain classes of item. In particular the 15-bit direct address field meant that the references that held variable values had to be located within the first 32k words.

Most of the class-attributes now associated with keys were not part of POP-2. Two that are of interest, although they were not accessible to the user were the save and relocate procedures. The save procedure was used during the mark phase of the garbage collector, which in essence was

 define mark_and_trace(Obj);
    unless marked(Obj) then
    endunless enddefine; 

The class_save procedure was responsible for calling mark_and_trace for all objects that the given object pointed to. E.g.

  mark_and_trace(L.front); endprocedure -> class_save(pair_key);

would specify how to save pairs.

Many garbage collections only did a mark_and_trace followed by chaining up un-marked objects into free-lists. Each small block size had its own free-list, and there was one free list for big blocks of all sizes. However after a given number of garbage collections a storage collapse (compaction) was performed, since otherwise free store could become fragmented that the machine could not find a block of the right size for a given allocation call. A relocation map was built up by examining the heap, and this was used in conjunction with procedures which I shall call here class_move procedures to relocate the store.

One interesting feature of this garbage collector is that there were pointers in the machine code generated by the compiler, and these had to be found. This was not too difficult, given the restricted range of virtual machine instructions and the fact that jumps within procedure bodies were relative and so did not have be updated. Thus we simply wrote class_save and class_move procedures for the key associated with functions.

Our treatment of arrays was stongly influenced by the functional propaganda of Peter Landin. While we could not make them completely functional - we needed to be able to update them in constant time, whereas a constructive redefinition would be O(n) on the number of entries (In the 70's Gerry Schwartz pointed out that if arrays were represented as trees, then a constructive redefinition would be O(\log n).). However we made arrays be POP functions (called procedures in POP-11), with an eye to the benifits of not specifying how they were stored, so that sparse arrays could be efficiently represented.

Another Landin influence on us was in the definition of dynamic lists, which were our version of what he called streams. While these can be more elegantly treated in lazy languages like Miranda, and I think that Landin's ideas may well have called for a lazy treatment if they were taken literally, the approach we developed is very usable, although for some reason people seem to avoid it in the very places where it is most valuable. For instance, dynamic lists allow people to write a parser that is functional, rather than depending on side-effects of the token-reader. Such a functional parser is much easier to test out. However it must be admitted that I am as much a culprit as anybody else in not making the best use of them.

An early example of new thinking that arose around POP-2 is Michie's Memo Functions [9]. In various forms, `memoising' is a fruitful idea in software, where it plays something of the same role as casheing in hardware. Heavy use of the functional capabilities of POP also featured in the question answering system developed by Pat Ambler and Rod Burstall, in which they treated relations as functions which produced sets of values. As well as using this for doing relational operations involved in query answering, they applied the same code to parsing the input and generating the output - it was just a question of supplying the right functional parameters.

The Development of Multipop

Before I arrived at Edinburgh Donald Michie had visited Project Mac and had been very impressed with what he saw. He and John Collins had formulated a `Minimac' project for the EPU, which was intended to provide a time-sharing service for a limited number of users (4 I think) based on swapping them entirely in and out from small discs. This project came to grief when Elliott were unable get the discs which they had manufactured under licence to work. In this crisis, I was able to offer an alternative - we could provide a time-sharing system based on POP-2. Users would simply share the core-store of the 4120, which could be expanded by spending the money we were unable to spend on the discs.

This proposal seemed workable. Some of the software which was under development for Minimac, in particular the handler for the multi-RS232 lines could be salvaged for use on the new system. The problem remained of how we could make POP into a multi-process language. This was solved on a rather ad-hoc basis. Clearly each user could be given his own stack space, and swapping between users would involve switching the stack pointers (then as now there were two stacks occupying the one storage block and operating in opposite directions). A user's own variables, non-lexical as they might be, presented no problem, since they were disjoint from anybody else's - we were not trying to provide a general multi-process capability.

System variables presented a different problem, since each user had to have his own copy of them - it wouldn't do for Mr. A to get his hands on Ms. B's output channel. This problem was treated by arranging for of the system variables to be held in a contiguous block of store. Each user had a `shadow' of this block of store. To start up a user's process his shadow block of system variables was copied into the actual space occupied by the system variables, This included his auxiliary stack pointer. The user stack pointer and S register were then restored from the user-record, thus causing his process to start running. This process was reversed when a user was suspended. A process could be suspended on procedure entry or backward jump - one of the tests conducted on those occasions being to check whether the users time slot had expired. Naturally, processes were also suspended if they tried to input from or output to a peripheral which was in a non-ready state.

Multipop had a single heap that was shared among all the users. Users could book their timeshared use of the machine in advance. In their booking they would specify their store requirements. The garbage collector measured the store used by each user - essentially it traced from each user base record. It zeroed a count before it started saving from a user base record, and then every time it discovered an unmarked store block it added the size of that block to the count. Thus the store use by a user could be measured. Users in excess of their quota were said to be `joyriding' - their processes would be killed by the computer operator's setting of a hand-key if the machine appeared to be labouring under an excessive press of users. Such labouring manifested itself in the form of repeated garbage-collections.

The rate of store turn-over for a user was not monitored so that programs which turned store over at a great rate were not penalised, although of course they cost everybody time, because the whole system stopped for a garbage collection.

Our 4100 machine, apart from being upgraded to a 4130 with 2microsecond core-store and hardware floating point (!) had acquired two 4MB disc drives. For this we implemented what must be the crudest file store ever. Each user was allocated one or more disc tracks. He could ask MultiPOP for a character repeater to read from the disc, specifying track and beginning sector number. A user could read from any place on the disc. To write, he could ask MultiPop for a character consumer, again specifying track and sector, although he could only write to his own tracks. This system was somewhat susceptible to the vagaries of human memory, and somebody soon wrote a program called EASYFILE which allowed one to keep a directory of the files on ones track.

We did write a more conventional time sharing system, Multipop 70, which made use of the memory protection hardware of the 4130. However this suffered from performance problems, since users were swapped to and from rather slow discs, and it was never popular.

The original Multipop68 continued in use until the mid-70's, when a DEC-10 machine became available. It supported quite a lot of pioneering work, including Burstall and Darlington's original investigation of languages based on recursion equations, and program transformations, Boyer and Moores' work on program proving, and the Versatile Assembly Program, which demonstrated the integration of vision and touch in assembly.

While I think it is accurate to describe me as the architect of the MultiPop system, it is certain that it would never have become the reliable tool that served the Edinburgh AI community for several years were it not for the labours of Ray Dunn, who meticulously eliminated the bugs from the wobbly prototype that I had produced, systematically rewriting the code until none of mine remained, enhancing the performance on all fronts as he did so. The vital device routines, including the terminal handler which is so critical for the comfort of users, and so difficult to get right, and the disc-handler with its real-time queues, were crafted by David Pullen.

David afterwards implemented MultiPop 70. The limited success of this system was no fault of his, but rather derived from the inadequate hardware base on which we were building.

All of us who worked in the EPU owe a debt of gratitude to Donald Michie, whose vision, energy and enthusiasm set up a superb environment in which to work, and in which we were led by somebody who was actively making contributions to knowledge at the same time as shouldering a considerable administrative load.

Source Material

The technological development of POP was less well chronicled in the the literature than, in retrospect, it should have been. I have in my possession copies of the pre-Edinburgh implementations, and the manuals of the machines. The Edinburgh and related developments can be charted through internal memos, some of which are listed below.

[1] J.G.P.Barnes and R.J.Popplestone [1968] `POP-2 in POP-2' Property of the University of Edinburgh Round Table, Department of Machine Intelligence and Perception. [This is a program which may still exist]

[2] J.G.P.Barnes [1968] 'System 4 POP-2 compiler-internal conventions, Research memorandum MIP-R-41. Edinburgh: Department of Machine Intelligence and Perception.

[3] R.M.Burstall \& R.J.Popplestone [1968] The POP-2 Reference Manual. Machine Intelligence 2, pp 207-246 (eds. E.Dale and D.Michie). Edinburgh: Edinburgh University Press.

[4] R.M.Burstall, J.S.Collins and R.J.Popplestone [1968] The POP-2 Papers, Edinburgh University Press.

[5] R.D.Dunn. [1970] `POP-2/4100 Users' Manual' Department of Machine Intelligence and Perception, Edinburgh University.

[6] Elcock,E.W.,Foster,J.M., Gray,P.M.D., McGregor,J.J., and Murray,A.M. [1971] ABSET. A programming language based on sets; motivation and examples. Machine Intelligence 6,pp.467-490 (eds. B.Meltzer and D.Michie). Edinburgh: Edinburgh University Press.

[7] Landin,P.J. (1966) The next 700 programming languages. Comm.A.C.M., 9, 157-166

[8] Garrett Mattingly [1959] The Defeat of the Spanish Armada, Jonathan Cape.

[9] Michie,D. [1968], Memo functions and Machine Learning, Nature, 218 19-22.

[10] Simon L.Peyton Jones [1987] The Implementation of Functional Programming Languages, (C.A.R.Hoare Series Editor), Prentice-Hall.

[11] D.J.S.Pullin [1967] `A Plain Man's Guide to Multi-POP implementation. Mini-MAC Report No.2. Edinburgh: Department of Machine Intelligence and Perception.