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);
repeat
if atom(y) then return(false) endif;
if y.hd = x then return(true) endif;
y.tl -> y;
endrepeat
enddefine;
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 Built-in list processing functions included HD TL and CONS. Library
machine-coded functions were the following:
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.
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.
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:
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
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:
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:
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
The
class_save procedure was responsible for calling mark_and_trace for
all objects that the given object pointed to. E.g.
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.
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.
[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.
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
REP
SELA
SELB
TOHD The updater of HD - (SETCAR in LISP)
TOTL The updater of TL - (SETCDR in LISP)
EQUAL Recursive equality.
The Stantec Zebra
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
<< (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
A[i,j] := x
define funprod(f,g);
procedure(x);
f(g(x))
endprocedure
enddefine;
define funprod(f,g);
procedure(x,f,g);
f(g(x))
endprocedure(%f,g%)
enddefine;
define mark_and_trace(Obj);
unless marked(Obj) then
mark(Obj);
class_save(data_key(Obj))(Obj);
endunless enddefine;
procedure(L);
mark_and_trace(L.back);
mark_and_trace(L.front); endprocedure -> class_save(pair_key);
The Development of Multipop
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.