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.