POP-2
Encyclopedia
POP-2, often referred to as POP2 was a programming language
developed around 1970 from the earlier language POP-1 (originally named COWSEL
) by Robin Popplestone
and Rod Burstall
at the University of Edinburgh
. It drew roots from many sources: the languages LISP
and ALGOL 60
, and theoretical ideas from Landin
. It used an incremental compiler
, which gave it some of the flexibility of an interpreted language
, including allowing new function definitions at run time and modification of function definitions while a program was running (both of which are features of dynamic compilation
), without the overhead of an interpreted language. It has been described as 'The first true functional language' at
HOPL, the History of Programming Languages web site.
a := 3;
one wrote
3 -> a;
The reason for this was that the language had explicit notion of an operand stack
; thus, the previous assignment could be written as two separate statements:
3;
which evaluated the value 3 and left it on the stack, and
-> a;
which popped the top value off the stack and assigned it to the variable 'a'. Similarly, the function call
f(x, y, z);
could be written as
x, y, z; f;
(commas and semicolons being largely interchangeable) or even
x, y, z.f;
or
(x, y, z).f;
There were no special language constructs for creating arrays or record structures as they are commonly understood: instead, these were created with the aid of special builtin functions, e.g. newarray (for arrays that could contain any type of item) and newanyarray for creating restricted types of items.
Thus, array element and record field accessors were simply special cases of a doublet function: this was a function that had another function attached as its updater, which was called on the receiving side of an assignment. Thus, if the variable a contained an array, then
3 -> a(4);
was equivalent to
updater(a)(3, 4);
the builtin function updater returning the updater of the doublet. Of course, updater was itself a doublet and could be used to change the updater component of a doublet.
Because of the stack-based paradigm, there was no need to distinguish between statements and expressions; thus, the two constructs
if a > b then
c -> e
else
d -> e
close;
and
if a > b then
c
else
d
close -> e;
were equivalent (note the use of close as endif hadn't been invented yet).
Variables could hold values of any type, including functions, which were first-class objects. Thus, the following constructs
function max x y; if x > y then x else y close end;
and
vars max;
lambda x y; if x > y then x else y close end -> max;
were equivalent.
An interesting operation on functions was partial application, (sometimes referred to as "currying
"). In partial application some number of the rightmost arguments of the function (which would be the last ones placed on the stack before the function is involved) were frozen to given values, to produce a new function of fewer arguments, which is a closure
of the original function. For instance, consider a function for computing general second-degree polynomials:
function poly2 x a b c; a * x * x + b * x + c end;
This could be bound, for instance as
vars less1squared;
poly2(% 1, -2, 1 %) -> less1squared;
such that the expression
less1squared(3)
applies the closure of poly2 with three arguments frozen, to the argument 3, returning the square of (3 - 1), which is 4. The application of the partially applied function causes the frozen values (in this case 1, -2, 1) to be added to whatever is already on the stack (in this case 3), after which the original function poly2 is invoked. It then uses the top four items on the stack, producing the same result as
poly2(3, 1, -2, 1)
i.e.
1*3*3 + (-2)*3 + 1
At middle 1970s POP-2 was ported on BESM-6 (POPLAN System).
Later versions were implemented for Modula One, PDP-10
, ICL 1900 series
(running the George operating system). Julian Davies, in Edinburgh, implemented an extended version of POP-2, which he called POP-10 on the PDP-10 computer running TOPS-10
. This was the first dialect of POP-2 that treated case as significant in identifier names, used lower case for most system identifiers, and supported long identifiers with more than 8 characters.
Shortly after that, a new implementation known as WPOP (for WonderPop) was implemented by Robert Rae and Allan Ramsay in Edinburgh, on a research-council funded project. That version introduced caged address spaces, some compile-time syntactic typing (e.g. for integers and reals) as well as some pattern matching constructs for use with a variety of data-structures.
In parallel with that Steve Hardy at Sussex University implemented a subset of POP-2, which he called POP-11
which ran on a DEC
PDP-11/40 computer. It was originally designed to run on the DEC operating system RSX-11D, in time-shared mode for teaching, but that caused so many problems that an early version of Unix
was installed and used instead. That version was written in Unix assembler, and code was incrementally compiled to an intermediate byte code which was interpreted. That port was completed around 1976 and as a result Pop-11 was used in several places for teaching. In order to support its teaching function many of the syntactic features of POP-2 were modified, e.g. replacing function ... end with define ... enddefine and adding a wider variety of looping constructs with closing brackets to match their opening brackets instead of the use of close for all loops in POP-2. Pop-11 also introduced a pattern matcher for list structures, making it much easier to teach AI programming.
Around 1980 Pop-11 was ported to a VAX-11/780 computer by Steve Hardy and John Gibson, and soon after that it was replaced by a full incremental compiler (producing machine-code instead of an interpreted intermediate code). The existence of the compiler and all its subroutines at run time made it possible to support far richer language extensions than were possible with Macros, and as a result Pop-11 was used (by Steve Hardy, Chris Mellish and John Gibson)) to produce an implementation of Prolog
, using the standard syntax of Prolog, and the combined system became known as Poplog
, to which Common Lisp
and Standard ML
were later added. This version was later ported to a variety of machines and operating systems and as a result Pop-11 became the dominant dialect of POP-2, still available in the Poplog system.
Around 1986 a new AI company Cognitive Applications Ltd., collaborated with members of Sussex university to produce a variant of Pop-11 called AlphaPop running on Apple Mac computers, with integrated graphics. This was used for a number of commercial projects, as well as being used for teaching AI programming in several universities. The fact that it was implemented in an early dialect of C, using an idiosyncratic compiler made it very hard to maintain and upgrade to new versions of the Mac operating system. In addition to this, AlphaPop was not "32-bit clean" due to the use of high address bits as "tag bits" to signify the type of objects, which was incompatible with the use of memory above 8Mb on later Macintoshes.
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
developed around 1970 from the earlier language POP-1 (originally named COWSEL
COWSEL
COWSEL is a programming language designed between 1964 and 1966 by Robin Popplestone. It was based on a RPN form of Lisp combined with some ideas from CPL....
) by Robin Popplestone
Robin Popplestone
Robin John Popplestone was a pioneer in the fields of machine intelligence and robotics. He developed the POP programming languages....
and Rod Burstall
Rod Burstall
Rodney Martineau Burstall is one of four founders of the Edinburgh Laboratory for Foundations of Computer Science.He was an early and influential proponent of functional programming, pattern matching, and list comprehension, and is known for his work with Robin Popplestone on POP, an innovative...
at the University of Edinburgh
University of Edinburgh
The University of Edinburgh, founded in 1583, is a public research university located in Edinburgh, the capital of Scotland, and a UNESCO World Heritage Site. The university is deeply embedded in the fabric of the city, with many of the buildings in the historic Old Town belonging to the university...
. It drew roots from many sources: the languages LISP
Lisp
A lisp is a speech impediment, historically also known as sigmatism. Stereotypically, people with a lisp are unable to pronounce sibilants , and replace them with interdentals , though there are actually several kinds of lisp...
and ALGOL 60
ALGOL 60
ALGOL 60 is a member of the ALGOL family of computer programming languages. It gave rise to many other programming languages, including BCPL, B, Pascal, Simula, C, and many others. ALGOL 58 introduced code blocks and the begin and end pairs for delimiting them...
, and theoretical ideas from Landin
Peter J. Landin
Peter John Landin was a British computer scientist. He was one of the first to realize that the lambda calculus could be used to model a programming language, an insight that is essential to development of both functional programming and denotational semantics.- Academic :Landin was born in...
. It used an incremental compiler
Incremental compiler
The term incremental compiler may refer to two different types of compiler.-Imperative programming:In imperative programming and software development, an incremental compiler is one that when invoked, takes only the changes of a known set of source files and updates any corresponding output files ...
, which gave it some of the flexibility of an interpreted language
Interpreted language
Interpreted language is a programming language in which programs are 'indirectly' executed by an interpreter program. This can be contrasted with a compiled language which is converted into machine code and then 'directly' executed by the host CPU...
, including allowing new function definitions at run time and modification of function definitions while a program was running (both of which are features of dynamic compilation
Dynamic compilation
Dynamic compilation is a process used by some programming language implementations to gain performance during program execution. Although the technique originated in the Self programming language, the best-known language that uses this technique is Java...
), without the overhead of an interpreted language. It has been described as 'The first true functional language' at
HOPL, the History of Programming Languages web site.
Description
POP-2's syntax was Algol-like, except that assignments were the other way round: instead of writinga := 3;
one wrote
3 -> a;
The reason for this was that the language had explicit notion of an operand stack
Stack (data structure)
In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...
; thus, the previous assignment could be written as two separate statements:
3;
which evaluated the value 3 and left it on the stack, and
-> a;
which popped the top value off the stack and assigned it to the variable 'a'. Similarly, the function call
f(x, y, z);
could be written as
x, y, z; f;
(commas and semicolons being largely interchangeable) or even
x, y, z.f;
or
(x, y, z).f;
There were no special language constructs for creating arrays or record structures as they are commonly understood: instead, these were created with the aid of special builtin functions, e.g. newarray (for arrays that could contain any type of item) and newanyarray for creating restricted types of items.
Thus, array element and record field accessors were simply special cases of a doublet function: this was a function that had another function attached as its updater, which was called on the receiving side of an assignment. Thus, if the variable a contained an array, then
3 -> a(4);
was equivalent to
updater(a)(3, 4);
the builtin function updater returning the updater of the doublet. Of course, updater was itself a doublet and could be used to change the updater component of a doublet.
Because of the stack-based paradigm, there was no need to distinguish between statements and expressions; thus, the two constructs
if a > b then
c -> e
else
d -> e
close;
and
if a > b then
c
else
d
close -> e;
were equivalent (note the use of close as endif hadn't been invented yet).
Variables could hold values of any type, including functions, which were first-class objects. Thus, the following constructs
function max x y; if x > y then x else y close end;
and
vars max;
lambda x y; if x > y then x else y close end -> max;
were equivalent.
An interesting operation on functions was partial application, (sometimes referred to as "currying
Currying
In mathematics and computer science, currying is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions each with a single argument...
"). In partial application some number of the rightmost arguments of the function (which would be the last ones placed on the stack before the function is involved) were frozen to given values, to produce a new function of fewer arguments, which is a closure
Closure (computer science)
In computer science, a closure is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its typical scope. Such a function is said to be "closed over" its free variables...
of the original function. For instance, consider a function for computing general second-degree polynomials:
function poly2 x a b c; a * x * x + b * x + c end;
This could be bound, for instance as
vars less1squared;
poly2(% 1, -2, 1 %) -> less1squared;
such that the expression
less1squared(3)
applies the closure of poly2 with three arguments frozen, to the argument 3, returning the square of (3 - 1), which is 4. The application of the partially applied function causes the frozen values (in this case 1, -2, 1) to be added to whatever is already on the stack (in this case 3), after which the original function poly2 is invoked. It then uses the top four items on the stack, producing the same result as
poly2(3, 1, -2, 1)
i.e.
1*3*3 + (-2)*3 + 1
History
The original version of POP-2 was implemented on an Elliott 4130 computer in the University of Edinburgh (with only 64KB RAM, doubled to 128KB in 1972).At middle 1970s POP-2 was ported on BESM-6 (POPLAN System).
Later versions were implemented for Modula One, PDP-10
PDP-10
The PDP-10 was a mainframe computer family manufactured by Digital Equipment Corporation from the late 1960s on; the name stands for "Programmed Data Processor model 10". The first model was delivered in 1966...
, ICL 1900 series
ICT 1900 series
ICT 1900 was the name given to a series of mainframe computers released by International Computers and Tabulators and later International Computers Limited during the 1960s and '70s...
(running the George operating system). Julian Davies, in Edinburgh, implemented an extended version of POP-2, which he called POP-10 on the PDP-10 computer running TOPS-10
TOPS-10
The TOPS-10 System was a computer operating system from Digital Equipment Corporation for the PDP-10 mainframe computer launched in 1967...
. This was the first dialect of POP-2 that treated case as significant in identifier names, used lower case for most system identifiers, and supported long identifiers with more than 8 characters.
Shortly after that, a new implementation known as WPOP (for WonderPop) was implemented by Robert Rae and Allan Ramsay in Edinburgh, on a research-council funded project. That version introduced caged address spaces, some compile-time syntactic typing (e.g. for integers and reals) as well as some pattern matching constructs for use with a variety of data-structures.
In parallel with that Steve Hardy at Sussex University implemented a subset of POP-2, which he called POP-11
POP-11
POP-11 is a reflective, incrementally compiled programming language with many of the features of an interpreted language. It is the core language of the Poplog programming environment developed originally by the University of Sussex, and recently in the at the...
which ran on a DEC
Digital Equipment Corporation
Digital Equipment Corporation was a major American company in the computer industry and a leading vendor of computer systems, software and peripherals from the 1960s to the 1990s...
PDP-11/40 computer. It was originally designed to run on the DEC operating system RSX-11D, in time-shared mode for teaching, but that caused so many problems that an early version of Unix
Unix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
was installed and used instead. That version was written in Unix assembler, and code was incrementally compiled to an intermediate byte code which was interpreted. That port was completed around 1976 and as a result Pop-11 was used in several places for teaching. In order to support its teaching function many of the syntactic features of POP-2 were modified, e.g. replacing function ... end with define ... enddefine and adding a wider variety of looping constructs with closing brackets to match their opening brackets instead of the use of close for all loops in POP-2. Pop-11 also introduced a pattern matcher for list structures, making it much easier to teach AI programming.
Around 1980 Pop-11 was ported to a VAX-11/780 computer by Steve Hardy and John Gibson, and soon after that it was replaced by a full incremental compiler (producing machine-code instead of an interpreted intermediate code). The existence of the compiler and all its subroutines at run time made it possible to support far richer language extensions than were possible with Macros, and as a result Pop-11 was used (by Steve Hardy, Chris Mellish and John Gibson)) to produce an implementation of Prolog
Prolog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
, using the standard syntax of Prolog, and the combined system became known as Poplog
Poplog
Poplog is a powerful multi-language, multiparadigm, reflective, incrementally compiled software development environment, originally created in the UK for teaching and research in Artificial Intelligence at the University of Sussex.-History:...
, to which Common Lisp
Common Lisp
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
and Standard ML
Standard ML
Standard ML is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.SML is a modern descendant of the ML...
were later added. This version was later ported to a variety of machines and operating systems and as a result Pop-11 became the dominant dialect of POP-2, still available in the Poplog system.
Around 1986 a new AI company Cognitive Applications Ltd., collaborated with members of Sussex university to produce a variant of Pop-11 called AlphaPop running on Apple Mac computers, with integrated graphics. This was used for a number of commercial projects, as well as being used for teaching AI programming in several universities. The fact that it was implemented in an early dialect of C, using an idiosyncratic compiler made it very hard to maintain and upgrade to new versions of the Mac operating system. In addition to this, AlphaPop was not "32-bit clean" due to the use of high address bits as "tag bits" to signify the type of objects, which was incompatible with the use of memory above 8Mb on later Macintoshes.
See also
- COWSELCOWSELCOWSEL is a programming language designed between 1964 and 1966 by Robin Popplestone. It was based on a RPN form of Lisp combined with some ideas from CPL....
programming language - POP-1 programming language
- POP-11POP-11POP-11 is a reflective, incrementally compiled programming language with many of the features of an interpreted language. It is the core language of the Poplog programming environment developed originally by the University of Sussex, and recently in the at the...
programming language - PoplogPoplogPoplog is a powerful multi-language, multiparadigm, reflective, incrementally compiled software development environment, originally created in the UK for teaching and research in Artificial Intelligence at the University of Sussex.-History:...
programming environment