POP-2(ID:298/pop002)The first true functional languagefor Package for Online Programming Robin Popplestone, Edinburgh Psychology Unit, 1967 Based on a REVPOL function in the MULTIPOP operating system rather than a true descendant of COWSEL per se. The first of the "true" POPs, with reverse polish notation, streams, closures, and first class functions. (incorporating many of Landin's ideas from ISWIM) Places People: Related languages
References: Aims The following are the main design objectives for the POP-2 language: (i) The language should allow convenient manipulation of a variety of data structures and give powerful facilities for defining new functions over them. (ii) The language should be suitable for taking advantage of on-line use at a console, i.e. it should allow immediate execution of statements and should have a sufficiently simple syntax to avoid frequent typing errors. (iii) A compiler and operating system should be easy to write and should not occupy much storage. (iv) The elementary features of the language should be easy to learn and use. (v) The language should be sufficiently self-consistent and economical in structure to allow it to incorporate new facilities when extensions are desired. In attaining these objectives certain other desirable features of programming languages had to be relegated to secondary importance: (vi) Fast arithmetical facilities on integer and real numbers. (vii) Fast subscripting of arrays. (viii) A wide variety of elegant syntactic forms. Naturally whether (iii) or (vi) and (vii) are attained is to a considerable extent a matter of implementation. Extract: Main features Main features The following main features are provided. Roughly analogous features of some other programming languages are mentioned in brackets as a guide: (i) Variables (cf. ALGOL but no types at compile time). (ii) Constants (cf. ALGOL numeric and string constants, lisp atoms and list constants). (iii) Expressions and statements (cf. ALGOL). (iv) Assignment (cf. ALGOL, also CPL left-hand functions). (v) Conditionals, jumps and labels (cf. ALGOL but restrictions on jumps and labels). (vi) Functions (cf. ALGOL procedures but no call by name, cf. CPL and iswim for full manipulation of functions). (vii) Arrays (cf. ALGOL; cf. CPL for full manipulation of arrays). (viii) Records (cf. COBOL, PL/I, Wirth-Hoare ALGOL records, CPL nodes). (ix) Words (cf. lisp atoms). (x) Lists (cf. lisp, ipl-V). (xi) Macros. (xii) Use of compiler during running (cf. LISP, TRAC, Formula ALGOL). (xiii) Immediate execution (cf. JOSS, TRAC). Extract: Acknowledgments Acknowledgments This language is a development of R. J. Popplestone's 'POP-1' programming language (see the paper in this volume). The debt to the ALGOL, LISP, CPL and ISWIM programming languages should be obvious. We are indebted to a number of people in this department and elsewhere for helpful discussion and criticism, to Dr David Park who contributed to discussion of the storage control scheme and to Mrs Margaret Pithie and Miss Eleanor Kerse who typed this report. Mr M. Healy kindly pointed out a number of errors and obscurities in a draft. The work has been undertaken on a grant from the Science Research Council under the supervision of Dr D. Michie, whose encouragement has been invaluable. in "Machine Intelligence 2", Dale, Ella and Michie, Donald (Eds) Oliver and Boyd, Edinburgh 1968. Proceedings of the Second Annual Machine Intelligence Workshop, University of Edinburgh, September 1966. view details in "Machine Intelligence 2", Dale, Ella and Michie, Donald (Eds) Oliver and Boyd, Edinburgh 1968. Proceedings of the Second Annual Machine Intelligence Workshop, University of Edinburgh, September 1966. view details in "Machine Intelligence 2", Dale, Ella and Michie, Donald (Eds) Oliver and Boyd, Edinburgh 1968. Proceedings of the Second Annual Machine Intelligence Workshop, University of Edinburgh, September 1966. view details Introduction Pop-2 (Burstall & Popplestone, 1968) represents a fairly far-reaching revision, extension and systematization of the author's Pop-1 (Popplestone, 1968). The thoughts expressed here consequently represent a point of view elaborated jointly with my co-designer of Pop-2, Dr R. M. Burstall. Extract: Aims Aims Pop-2 is a language to be implemented on real machines, using modest resources of manpower. An implementation of the language must be possible which permits large problems to be tackled. This implementation must not be too inefficient in its use of machine time, or too profligate in its use of store. The language must also take into account such properties of real machines as overwritable store-that is to say it must not be a purely constructive language: it must allow assignment. Pop-2 handles a large range of structures such as list cells (cf. Lisp), functions (cf. Cpl) and records (called beads in Aed). Efficiency is important here-LISP is perfectly general, but its representation of such structures in list-cells is inefficient in its use of store. Bearing in mind the need for a wide range of structures, the concepts should be as few and simple as possible. An example of this simplification is that such apparently diverse things as Algol procedures, Algol arrays, binary operators, and Aed 'components' can all be represented in a natural fashion as POP-2 functions. Functions in Pop-2 differ in their semantic properties, and in the syntactic properties of their names, but they are all the same in essence: not only are they all handled in the machine as da structures, but they constitute a single class of data structure. This brings us to the subject of items. Anything which can be the value of a variable is an item. All item have certain fundamental rights. 1. All items can be the actual parameters of functions 2. All items can be returned as results of fiinctions 3. All items can be the subject of assignment statements 4. All items can be tested for equality. Equality does not, however, follow the usual mathematical axioms, e.g. cons(2,3)^cons(2,3), where cons is the Lisp list-cell constructor. The impracticability of providing a computed version of mathematical equality is clear if one considers the case of functions. Nevertheless, care is taken in the definition of the language to make sure that the meaning of the equality is clearly defined. It corresponds to the Lisp 'eq', or the concept of equal address in mechanistic terms. It should be noted where existing languages fail to provide an adequate 'item's charter of rights': Algol arrays cannot be returned as results of procedures. Aed components cannot act as parameters of procedures. Certain consequences follow from the charter of rights given above. Thus in POP-2 we can say sqrt-~pig; and later discover that ~1~(144) has the value 12. It should be noted also that certain words and symbols in Pop-2 are not the names of items. Thus, while +, log, cons, are the names of items, ), then, and goto, are not. Statement labels are not items: i.e. 'computed gotos' are not permissible. The same effect can be obtained by exploiting the freedom to assign to functions. The role of non-item words is syntactic. A consequence of clause 2 of the items' charter of rights is that Pop-2 requires a more general form of storagc control than is provided by a stack or push-down store. In fact a generalized form of the Lisp scheme is provided. An Algol array can be placed on a stack precisely because it cannot survive the activation of the procedure or block in which it occurs. This has a profound effect on the class of problems which it is possible to tackle in a natural way using Pop-2. An important corollary is that the space occupied by the code which represents functions is itself under the general storage control scheme. The syntax of the language should be neat, unobtrusive and simple, rather than elaborate. Additional semantic power should not be locked away from the user by syntactic devices. Thus a Pop-2 array is created by applying a function newarray to a description list, and assigning the result to a variable, none of which operations involves any new syntax. Pop-2 is designed for on-line use. The language features which reflect this are (1) the ability to have expressions executed immediately, and (2) the limited block structure of the language. A POP-2 program tends to be a sequence of independent function deibitions, which can be redefined independently. Extract: Item Item Items are simple or compound. This distinction is made for practical reasons: a simple item is an economical quantity of information to move around a machine, a compound item is not. Thus the limit to what is to be regarded as a simple item has been set with an eye to the amount of information that can be put in one word of a machine. Items are classified into types. The words item class and type are synono-mom. It is possible to determine the type of any item at any time. Except in the case of functions, it is not possible to restrict the range of variables to any particular type of item. This means that type checking must be done dynamically, that is to say, all functions must check that they have been supplied with appropriate arguments. This leads to reduced efficiency. The other reason for attaching types to variables is to permit errors to be discovered at compile-time. The conceptual type structure of the programmer is very much finer than the type structure of languages like Algol. Thus when we say 'let s be the speed of the vehicle v' or 'let w be the weight of the house h', s, v, w, and h, are, at one level, of different type, and a language that fully mirrored the thought processes of the human would allow this distinction to be made. Thus it is felt that if Pop-2 were to have type restrictions on variables at all then it must have a type structure extendable by the user. However, type structure is not simple. For instance, it is meaningful to say 'let w be the weight of the vehicle v' but it is not meaningful to say 'let s be speed of the house K. Thus any extended type structure would be too complex to put in what is conceived of as essentially a simple language. Not only would it be too complex, it could be too cramping. One could not define a function MAPLISTto apply any function to all members of any list if one had to specify the types of its arguments. Indeed, the ability to write 'metaphorical programs' where a set of functions for, say, performing a search procedure can be used with widely differing types of object being searched for, is very important in machine intelligence. Thus on the one hand, Burstall's (1968) program for fact retrieval uses one set of functions for both syntax analysis and deduction, while on the other hand the Graph Traverser, an Algol program (Doran and Michie, 1966) is handicapped by operating solely on rectangular arrays. Numbers, integer and real, are simple. For reasons of efiiciency the tmth values true and false are represented as the numbers 1 and 0 respectively, and as such are simple. There are also operations which allow numbers to be treated as bit-patterns. Type conversion between integer and real items is performed automatically at run-time. Compound items can be thought of mechanistically as pointers to areas of store. Certain standard compound items are provided. These include Extract: List cells List cells List cells and operations of the Lisp type are provided. There are, however, a class of entities, which are variously called streams or files, the processing of which is sequential, and which it is desirable to handle in a manner analogous to the manner in which lists are handled. It is not practicable to convert these things into lists because of the prohibitive amount of store they would occupy. Landin (1966) proposed a representation in terms of functions without sidc effects. In Pop-2 a more efficient solution is provided: dynamic 1ists.These are lists of the Lisp type, except that the last cell in the list contains a function. There are operations hd and tl on dynamic lists, which, like car and cdr of lisp, select respectively the first member and the remainder of the list. When the last cell of a dynamic list is reached, the resident function is applied to no arguments, and the result is taken to be the next member of the list. The list is terminated when the function produces termin as its result. In this case true is written into the first position in the last cell. The function null which tests for the emptyness of a list, returns the result true when it is given a list cell with true in its first position and a function in its second. As an example, supposefis a function to read a character off an input tape. The statement fntolist(f)->x; using the standard function fntolist, will set x to be a dynamic list built from F. The function count defined by function count x; vars n; O+n; loop: if null(x) then n exit if hd(x) = hd(tl(x)) then n+i+n close tl(x)-+x; goto loop END which counts the number of pairs of identical adjacent characters on the input tape, is only fractionally more convenient than the same function written using F directly, but the gain increases with the complexity of the operations being performed. Extract: Words Words System routines are available for converting sequences of symbols into data cells called words. These contain the first eight characters of the word. Characters are converted into words according to the conventions of the POP-2 compiler. Thus CAT ), +, and ++ are words. Quotes are used to distinguish words from identsers e.g. "cat" denotes the word cat while cat denotes the current value of an identifier cat. Words are standardized. That is to say, on construction of a word, a check is made to see whether a word having the same sequence of letters has been encountered before, and if so the previous incarnation is used. Constant words are guoted in program, and "dog"="dog" always produces true, because of this standardization. There is a function meaning on words which asso. ciates an item with a word (similar to the property list of a Lisp atom). "CHIEN"+MEANING ("DOG"). This function allows one to construct an updateable dictionary, the cntrics of which are undefined until assignment is first made to them. This examplc of assignment is analogous to x+hd(y). Users may themselves define classes of compound items. Records Records are data cells with a number of components fixed over a record class. Thus the class of list cells is a record class each member of which has two components, namely, HD and tl. The amount of information in each component of a record is specified in a description list, which is handed to the function recordfns which is used to create a record class. The description list for list-cells would be [0 0], O in a description list being used to indicate a component which can be a full compound item. The result of recordfns is a number of functions for manipulating the records of the class being defined. Thus the class of Iist-cells would be defined by recordfns("list", 1000, [0 0])-j-back->front->dest->cons; where front and back are car and cdr in Lisp, and dest is a function that 'explodes' a list-cell into its components. Extract: Strips Strips Strips are cells with a number of components which is variable over a class of strips. The components of a strip are all of the same size, and are accessed by a subscripting function associated with each strip class. Thus, if s is a strip, w is an integer and subscr is a subscripting function for the class of strips to which s belongs, then subscr(n,s) produces item n of s. Arrays are functions which have strips attached to them as work-space. The way in which this attachment is performed will be described in the section on functions. There seems to be a need for classes of objects with properties intermediate between strips and records. These would have the variable size of strips, and the different component types of records. Thus, a record of a person might have a selector-subscriptor namechar, such that namechar(i,p) took the ~'th character of the name of the person P. Extract: Functions Functions Functions are compound items, and as such are the values of variables. lambda X; X*X end-square; (for lambda notation see Landin, 1966) assigns that function which takes x onto its square to the variable square. A 'sugared' version of this is FUNCTION SQUARE X; X*X END Binary operations like + ? <>(<>is the infixed version of concatenate as applied to lists) are identifiers which are the names of functions. These identifiers are recognized by the compiler as naming infixed operations. The modifier nonop causes them to be treated as normal functions, e.g. nonoi' + -*¦ prod; causes the value of prod to be set to the multiplication functio~l Note that only the semantic, not the syntactic, content of * passes to prod in this assignment, so that to apply the new function we must say prod(x,y). If we had wished prod to be an infix, we would have proceeded as follows: VARS OPERATION 3 PROD; NONOP * - now x prod Y=x* y gives the value true. The numeral in this declaration sets the precedence. Some functions have a meaning when used to the right of an assignment arrow. Thus 4-+~(3,2) is meaningful if a is an array, or ~~-+hd(l); if l is a list. Every function has a component called its updater. Suppose we are keeping records of people in lists, giving details of their ages and sexes. Thus: [Socrates male 24361 or [satan male 100000]. One can define the functions age and sex on these records. Thus: function sex x; hd(tl(x)) END Everyone who has an age has birthdays. According to Malleus Maleficarum (Institoris, 1948), Satan, for reasons which need not detain us here, needs to change his sex frequently. The functions age and sex as defined above will not perform this updating operation. However the statement lambda x y; x+hd(tl(y)) end+updater(sex); will change the updater component of sex in such a way that if we say [SATAN MALE 100000]-+~; then later "female"-+sex(p); will update the record P as required. There are two methods of creating new functions dynamically. One is pop val, which is a function which compiles program, in the form of a list. The other is partial application. Suppose that f is a function of n arguments: we may 'partially apply' it to an argument list of only m elements by writing f( % x,, x,, . . . . x, %). The result is a new function ofn-rn arguments, obtained by 'freezing' the values of the last m arguments to the values possessed by x,, x,,.... x, at the time of the partial application. Thus suppose dist is a function for finding the distanc? between pairs of places, and Edinburgh is a place, then dist(% Edinburgh %) is a function for finding the distance of a place from Edinburgh, and we would be at liberty to assign it, e.g. dist( % Edinburgh %) +mileage. mileage(london) now gives 380. The following illustrates the use of partial application in defining a functional. Suppose zero is a function for finding one zero of a function. Consider the function inverse defined by function inverse f; auxinverse(% f %) END where auxinverseIs the function defined by function auxinverse y f; zero(lambda x; y?f(x) end) END Then, leaving aside the niceties of numerical analysis, inverse is a functional which takes a function of one argument over the reals onto its inverse. Thus inverse(sin) is arcsin. This is deduced as follows: according to the definitions inverse (sin) is auxinverse( % sin %), that is, ~~xin ~erse with F 'frozen' to sin, that is a function with the same result as lambda y; zero(lambda X; y?sin(x) end) end Given Y, the result of this function will be that x for which Y?sin(x) = 0, that is that x for which sin(x) = y, that is arcsin(y). The above definition of inverse will seem unnecessarily complicated on first reading. Could f not be a non-local of auxinverse and the partial application be dispensed with? If this were so, when we came to evaluate arcsin the value of F might have been changed, for instance by another application of inverse to, say, log. However, with the partial application in place, if we say inverse(log)+exp, then arcsin and exp are two functions which are obtained from auxinverse by freezing f to the values sin and log respectively. Landin (1966) uses an equivalent scheme. The frozen formal parameters of Pop-2 correspond to the environment part of his closures. While his method, as embodied in Cpl, is syntactically more elegant, partial application technique of POP-2 is perhaps more flexible, because the user can decide which variables are to be frozen. Extract: Future Developments Future Developments Now that an implementation of Pop-2 is available on a machine (an Elliott 4120) it is time to consider the future. There are three lines of development. The first is to make extensions to the language to make use of backing store and to make more efficient use of machine time. The second is to build a library of functions to be used as building bricks of intelligent programs. The increased power that partial application gives Pop-2 is very important here. In languages like Algol, one can write learning programs: it is difficult to write learning procedures. This is because the only memory that a procedure can have to itself is in the form of 'own' variables. Since these have only one incarnation, the learning mechanism enshrined in a procedure can only be used in one sub-problem of the whole problem. In Pop-2 on the other hand, a learning mechanism encoded in a function can be attached to data concerned with many sub-problems by partial application. Arrays may be regarded as rote-learning functions, a point of view implicit in the 'memo function' concept proposed by Michie (1968). One can write in POP-2 a function which one might call, by analogy with newarray, newinterp. newinterp() produces a function called an interpolator. Suppose we are studying devices called tripistors. These pass a current that depends on the applied voltage. If we say newinterp()+-tripistor; we have a function which we can teach to represent tripistor behaviour. Suppose we have observed that a tripistor passes a current of 10 amps when 1 volt is applied, and 0 amps when 0 volts are applied, then this information is conveyed by the statements: IO-s-tripistor(I); O-+tripistor(O); If we now ask for tripistor(0.5) the machine produces the estimate of 5, by linear interpolation. As further information is fed in so better interpolations will be possible. Meanwhile, in another part of the program, the same interpolation mechanisms have been learning the behaviour of livertrons. When these lessons have been adequately learnt, they can be applied in predicting the behaviour of a circuit containing both tripistors and livertrons. Finally, as Pop-1 was used to develop Pop-2, so POP-2 will be used to develop its successor. What sort of language will this be? One can regard existing algorithmic languages including Pop-2 as being imperative. They are used to describe the solution to a problem. The next generation of languages will be indicative. They will be used to describe a problem. Both kinds of language have been used by logicians: the lambda calculus is their imperative language, the predicate or functional calculus the indicative languages. Algorithms for interpreting these languages are known - e.g. the resolution principle for the functional calculus. Let us consider the following statements in Bnf-which can be regarded as an indicative language: We can regard this as a 'sugared' version of the following statements in functional calculus. 'dx (isnp(X) < = > (3 y (isnounO) and X= [the] <> y))) isnoun([cat]) and isnoun([dog]) In order to use resolution, these have to be rewritten in conjunctive normal form. Leaving out the = > of the < = > we get: *(1) not(iSNOUN<») or not ([the] <> y = x) or isnp(x) (2) isnoun([cat]) (3) isnoun([dog]) These statements can be used analytically or generatively. To use them I analytically, suppose it is conjectured that isnp([the] <> [cat]), i.e. that [the] < > [cat] is a nounphrase. Then one adds the denial of this statement to 1-3 and asks for a contradiction. (4)nOt(ISNP([THE] <> [CAT])) Resolving (4) with (1) gives (5) ~O~(ISNOUN(~)) Or~o~([THE] <> y=[the] <> [cat]) Resolving (5) with (2) gives (6)~o~([THE] <> [cat]=[the] <> [cat]) a contradiction, by resolution with x=x ? an equality axiom. To use (1)-(3) generatively one need only deny the existence of a noun-phrase. (4a) not(isNp(x)) Resolving (3) with (1) gives (5a) not([THE] <> [dog] = x) or isnp(x) Resolving (5) with x = x gives (6a) isnp([the] <> [dog]) a contradiction with (4a), and an instance of a nounphrase. While the deduction process in such an indicative language is algorithmic, the choice of deductions to be made is not. Foster, in this volume, proposes a method whereby a user of such a system could control the direction of deductions. With sufficiently rigid control one would have an imperative language. Work at Edinburgh would be concerned with a heuristically controlled system. The study of imperative systems viewed as highly constrained indicative systems seems important to the understanding of milder heuristic constraints. Extract: Acknowledgements The research described in this paper is sponsored by the Science Research Council. I am particularly in debt to my colleague Dr R.M.Burstal1 for his many helpful suggestions and criticisms. in Machine Intelligence 3 (ed) Michie, Donald Department of Machine Intelligence and Perception, University of Edinburgh, Edinburgh University Press, 1968 view details in Machine Intelligence 3 (ed) Michie, Donald Department of Machine Intelligence and Perception, University of Edinburgh, Edinburgh University Press, 1968 view details intelligence laboratories. The Edinburgh machine intelligence group here defines its research and development philosophy in reply to questions put by Japanese robot engineers. Extract: Which language do you use Q) Which language do you use in robot research, FORTRAN, ALGOL, PL/l , Assembler, LISP or other list processing language? What would be the features of robot-oriented languages? A) We use POP-2. The nearer a programming language is to a fully general mathematical notation, the more open-ended its structure, and the more flexibly adapted to conversational use, then the better the language for robot research. We feel that an ideal robot-oriented language would be one that dealt in relations as well as functions, and would have deductive and inductive capabilities. Extract: Multipop Q) How does your robot communicate with the digital computer ? A) The robot communicates with the computer as a peripheral of the Multi-POP time-sharing system, running on an ICL 4130 computer. Communication is via transfers of single 8-bit bytes. The output byte is decoded as a command to sample the picture or drive the motors. The input byte contains the state of the bump detectors and brightness of the picture point. When the satellite is installed, communication will be via a high-speed link with the ICL 4130. The robot will be interfaced to the satellite, essentially as it is now to the ICL 41 30. in The Computer Journal 14(1) 1971 view details in The Computer Journal 14(1) 1971 view details in Computers & Automation 21(6B), 30 Aug 1972 view details The exact number of all the programming languages still in use, and those which are no longer used, is unknown. Zemanek calls the abundance of programming languages and their many dialects a "language Babel". When a new programming language is developed, only its name is known at first and it takes a while before publications about it appear. For some languages, the only relevant literature stays inside the individual companies; some are reported on in papers and magazines; and only a few, such as ALGOL, BASIC, COBOL, FORTRAN, and PL/1, become known to a wider public through various text- and handbooks. The situation surrounding the application of these languages in many computer centers is a similar one. There are differing opinions on the concept "programming languages". What is called a programming language by some may be termed a program, a processor, or a generator by others. Since there are no sharp borderlines in the field of programming languages, works were considered here which deal with machine languages, assemblers, autocoders, syntax and compilers, processors and generators, as well as with general higher programming languages. The bibliography contains some 2,700 titles of books, magazines and essays for around 300 programming languages. However, as shown by the "Overview of Existing Programming Languages", there are more than 300 such languages. The "Overview" lists a total of 676 programming languages, but this is certainly incomplete. One author ' has already announced the "next 700 programming languages"; it is to be hoped the many users may be spared such a great variety for reasons of compatibility. The graphic representations (illustrations 1 & 2) show the development and proportion of the most widely-used programming languages, as measured by the number of publications listed here and by the number of computer manufacturers and software firms who have implemented the language in question. The illustrations show FORTRAN to be in the lead at the present time. PL/1 is advancing rapidly, although PL/1 compilers are not yet seen very often outside of IBM. Some experts believe PL/1 will replace even the widely-used languages such as FORTRAN, COBOL, and ALGOL.4) If this does occur, it will surely take some time - as shown by the chronological diagram (illustration 2) . It would be desirable from the user's point of view to reduce this language confusion down to the most advantageous languages. Those languages still maintained should incorporate the special facets and advantages of the otherwise superfluous languages. Obviously such demands are not in the interests of computer production firms, especially when one considers that a FORTRAN program can be executed on nearly all third-generation computers. The titles in this bibliography are organized alphabetically according to programming language, and within a language chronologically and again alphabetically within a given year. Preceding the first programming language in the alphabet, literature is listed on several languages, as are general papers on programming languages and on the theory of formal languages (AAA). As far as possible, the most of titles are based on autopsy. However, the bibliographical description of sone titles will not satisfy bibliography-documentation demands, since they are based on inaccurate information in various sources. Translation titles whose original titles could not be found through bibliographical research were not included. ' In view of the fact that nany libraries do not have the quoted papers, all magazine essays should have been listed with the volume, the year, issue number and the complete number of pages (e.g. pp. 721-783), so that interlibrary loans could take place with fast reader service. Unfortunately, these data were not always found. It is hoped that this bibliography will help the electronic data processing expert, and those who wish to select the appropriate programming language from the many available, to find a way through the language Babel. We wish to offer special thanks to Mr. Klaus G. Saur and the staff of Verlag Dokumentation for their publishing work. Graz / Austria, May, 1973 in Computers & Automation 21(6B), 30 Aug 1972 view details in [ACM] ACM Computing Surveys (CSUR) 6(3) September 1974 view details External link: Online copy in The Computer Journal 19(3) 1976 view details in The Computer Journal 19(3) 1976 view details in The Computer Journal 19(3) 1976 view details An exact definition of the scope of an own variable has not yet evolved. This paper shows that an assumption that the scope of an own variable does not extend beyond the scope of the name of the owning proce dure solves many of the problems and leads to a clearer understanding of their true nature. They are equivalent to additional parameters which have been frozen to local generators. in The Computer Journal 19(3) 1976 view details Design of an Interactive Functional Language During the period 1966-1971 I, together with R.M.Burstall, designed and implemented the POP-2 quasi-functional language. Below is a fragment of POP-2, which finds the sum of members of a list. FUNCTION SUM L; IF NULL(L) THEN 0 ELSE HD(L) + SUM(TL(L)) CLOSE END The user could load her program, or load an individual function and call SUM interactively: SUM([1 2 3]) => The machine would respond: ** 6 For comparision: Modern Functional Languages Concepts embodied in POP-2 included: Higher order capabilities based on partial instantiation: A proper, higher order, functional language must allow us both to pass functions as arguments to other functions and to return them as results. Doing this correctly requires a proper treatment of non-local (or free ) variables. The principle that free variables in a function body can be correctly implemented by making them parameters of the function and then "partially applying" the modified function to the actual values was introduced by us; later expressed in the Lambda Calculus formalism, this came to be known as `lambda lifting'. (Today, the more correct term "partial instantiation" is used. It should be noted the techniques for handling non-local variables described in most textbooks on programming languages are restricted to supporting passing functions as parameters and not returning them as results. So much of the world has not really caught up with the '60's in this respect.) This issue is explained in the POP-2 primer, 1971, by Burstall and Collins: The obvious but incorrect definition of twice is: function twice f; lambda x; f(f(x)) end end; This will not work, because the value of f is local to twice and will hence be available only during the execution of twice. Partial application enables us to 'freeze in' the value of f into the definition of the lambda expression. To do this, the definition of becomes function twice f; lambda x f; f(f(x)) end (% f %) end; Garbage collection and pointer safety: Users could not create an invalid pointer, because POP-2 was one of the first language systems to introduce a (necessarily compacting) garbage collector for all datatypes of the language, including machine-code blocks. This employed a method-suite (of fixed layout) contained in key-cells common to all members of a given datatype. Certain data-class common operations, such as printing were also supported by indirecting through this method-suite, and a user-definable slot was left, although this was little exploited. (Garbage collection was of course originally developed for LISP, so most of the computing world, which relies on error-prone manual methods of deallocating store, still has not caught up with the '50's). Incremental compilation for interactive computing: The time taken to recompile and relink a program can be a major impediment to the development of complex programs, particularly in the 1960's. On the other hand, the then conventional approach of an interpreter made for slow execution. POP-2 supported incremental compilation, allowing a user to correct a single function definition and recompile just that. Support of abstraction: A functional language provides a natural abstraction mechanism, with implementation hiding being performed by closures. The danger is that in adding bells and whistles we will destroy abstraction (e.g. pattern matching in ML). The view of mutable store provided by POP-2 preserves the concept of the function as being the chief vehicle of abstraction, while giving a view of mutable store by providing an updater component of a function. It is certainly a better approach from the point of view of abstraction to the provision of special constructs for a left hand value which are to be found in C,Pascal, etc.. Continuations: The support of the preservation of a state of a computation as a first-class object was added to POP-2 in 1971. Certain implementation aspects Acknowledgements Aspects of the storage control scheme scheme were due to Michael Foster, currently at the RSRE and were used in the Aberdeen system ABSYS. The design of the order code of the 4130 computer, by C.A.R.Hoare et.al. facilitated all aspects of the system. Of course Burstall and I drew on the work of Church, Curry, Mc Carthy, Landin and Strachey and the various designers of Algol 60. Crucial work on implementation was done by Ray Dunn, Dave Pullin, Malcolm Atkinson Robert Rae and others. John Collins wrote the primer and designed the MiniMac system which we drew on for device handling routines. Donald Michie had the vision to set up the framework in which all this happened and guide us in our efforts; certain aspects of the work are due to him. Work originally implemented in POP-2 includes: The Boyer-Moore theorem prover. This is a program for proving properties of pure LISP programs. The Boyer-Moore search algorithm. Structure sharing in predicate logic: precursor studies to the development of the Prolog language. The Burstall-Darlington program transformation system. The Hope language. Michie's Function memoisation: by remembering argument-value pairs, time efficiency of a function can be enhanced, even to change of complexity class. Memoisation is most naturally and conveniently implemented in a higher order language like POP-2. in The Computer Journal 19(3) 1976 view details 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); 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 . 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 REP SELA SELB 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" %] Extract: The development of POP-2 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); procedure(x); f(g(x)) endprocedure enddefine; 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); procedure(x,f,g); f(g(x)) endprocedure(%f,g%) enddefine; 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 mark(Obj); class_save(data_key(Obj))(Obj); endunless enddefine; The class_save procedure was responsible for calling mark_and_trace for all objects that the given object pointed to. E.g. procedure(L); mark_and_trace(L.back); 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. Extract: The development of MultiPOP 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. in The Computer Journal 19(3) 1976 view details in Formal Aspects of Computing 13(3-5) July 2002 view details |