FUNCTION SUM L; IF NULL(L) THEN 0 ELSE HD(L) + SUM(TL(L)) CLOSE ENDThe user could load her program, or load an individual function and call SUM interactively:
SUM([1 2 3]) =>The machine would respond:
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
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
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.