| PLACE |
| languages |
Somewhat differently from the imperative branch of the programming language evolution, the key steps in the development of functional programming seem to have been made in just several but very important scientific publications and programming languages. One seminal work in this line is that of P. Landin (see the link below) on the ISWIM language.
ISWIM is basically a purely functional language to which two imperative constructs are added. One is the so called program-point: a deviant kind of function that forces expression evaluation to be terminated prematurely with delivering some value as that expression's result (‘ISWIM's nearest thing to jumping’). The other is assignment.
Landin's contribution was in several directions. He wrote of ISWIM as ‘a family of languages, of which each member is the result of choosing a set of primitives’. The rationale of this was his considering a programming language as a system of two layers: a basic set of primitives and a set of combinaton facilities which ‘describe things in terms of other things’. Thus a family of languages is supposed to be defined by specifying the latter set, while the former determines a particular language's problem orientation. According to Landin, language design should be systematized so that ‘a new language is a point chosen from a well-mapped space, rather than a laboriously devised construction’. This way, he argued, we would be able to judge to what extent the differences between languages reflect basic logical properties of those languages' application areas or are just accidental, which is important ‘if we are trying to predict or influence language evolution’.
Landin also made clear separation between concrete and abstract syntax, i.e. between written representation, on the one hand, and the abstract entities, structures of them, and the relations between them, on the other. (His terms for these two facets of a language were syntax and structure.) In particular, Landin pointed out that ‘functional programming has little to do with functional notation [...] prefixed operators and heavy bracketing’. (As a terminological issue, he actually considered the word denotative more appropriate than nonprocedural, declarative, or functional.)
There are two notable differences between ISWIM and the other well known ‘functional’ language of that time, Lisp.
First, ISWIM is a λ-calculus-based language, which Lisp was not (at that time, Lisp had dynamic rather than lexical scoping). Second, ISWIM has no inherent commitment to lists – neither as a preferred form of data structuring nor as one in which the program is represented. ISWIM has no built-in notion of list – it is data-structure agnostic – and its operators are written in infix style.
As textual appearance, ISWIM programs are very close to the usual writing style of mathematics. Local definitions are being introduced through where- and let-clauses, and nesting is expressed by use of indentation. All these make the textual appearance of ISWIM programs be very close to the usual writing style of mathematics.
where- and let-clauses were introduced at the same time in ISWIM and in CPL. Simultaneity and self-reference in such definitions can be ensured through explicit ‘decorators’.
It should be noted that the intended use of where-clauses was broader in Landin's proposal for ISWIM than in later languages in which it has been adopted, as it allows specification of types and other properties and relations. Landin even contemplated allowing expressions like the following, which presume some implicit computation to take place:
f(1,-1,-6) where f(a,b,c) = the x such that a x2 + b x + c = 0 & x ≥ 0.
In the discussion that accompanied the presentation of his report on ISWIM, P. Landin argued that: (a) the use of a small number of recursively defined functions can replace a lot of familiar types of loop, (b) these functions can be taken as primitive in the language, and (c) the implementation of the said functions could still be iterative, hence efficient. This is one of the earliest arguments for the use of higher-order functions for program structuring.
The author of ISWIM was very close to introducing tuples – a construct widely used in today's functional languages. Although he did not propose using tuples as a kind of values, he did spoke of various uses of ‘listings of expressions’. Moreover, his main motivation seems to be that, through such a construct, all functions can be considered monadic.
Landin made special emphasis on the applicability of equational reasoning (the ability to substitute equals for equals) to functional programs, pointing out that in functional programs one can formulate many simple equivalences that hold without exception, while this is not true or is very difficult to do in the imperative world. He also observed that having such equivalences is greatly beneficial to the practicability of all kinds of program processing.
ISWIM has never been implemented, but it and the line of thought that brought it to existence have proven very influential in the development of functional programming languages such as e.g. Hope, Miranda, Haskell and ML. The use of where-clauses or similar constructs for local definitions, as well as that of the offside rule are now well established practice. The offside rule has also found its way into some imperative languages, such as occam, ABC, and Python. As for equational reasoning, it is long since it became a standard in functional programming theory.
Tne book ‘Recursive Programming Techniques’ (see the link below) is an excellent text on functional programming using ISWIM. This 1975 book is terse, rich in valuable information and good examples, full of insight and surprisingly modern.
Another work of Landin, no less important and influential than ISWIM and related to it, is that on the SECD (Stack, Environment, Code, Dump) machine: an abstract machine intended as a target for functional programming language compilers.
P.J. Landin. The next 700 programming languages. Comm. of the ACM, Vol.9, No.3 (March, 1966), pp.157-166
P.J. Landin. The mechanical evaluation of expressions. The Computer Journal, Vol.6, No.4, pp.308-320 (1964). [Describes SECD]
P.J. Landin. A generalization of jumps and labels. UNIVAC Systems Programming Research Report, 1965; also in: Higher-Order and Symbolic Computation, Vol.11 (1998), #2, pp.125-143. [Describes the J operator. See also this explanation and this related history]
W.H. Burge. Recursive programming techniques. Addison-Wesley, 1975
boykobbatgmaildotcom