Iswim

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.)

Iswim can be looked on as an attempt to create a λ-calculus-based language which, unlike Lisp, 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, and its program structure makes use of infix operators, where- and let-clauses and indentation. All the three make the textual appearance of Iswim programs be very close to the usual writing style of mathematics.

where-clauses, and the functionally equivalent let-clauses, were invented in Iswim (and at the same time in CPL, as it turns out) as a form of providing auxiliary, local definitions. Simultaneity and self-reference in such definitions can be ensured through explicit ‘decorators’ in a where-clause.

Indentation (‘the offside rule’) was introduced for expressindg program structure. Its use is not obligatory and can be mixed with punctuation such as in other languages, e.g. semicolons and block delimiters.

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 considered 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 x² + b x + c = 0 & x ≥ 0.

In the discussion that accompanied his paper, 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.

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 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 considerations that accompanied it 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 (although the name Iswim is not mentioned in it). This more-than-thirty year old 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. SECD is described in ‘The mechanical evaluation of expressions’ article – see below.

Links of Relevance:

P.J. Landin. The next 700 programming languages. Comm. of the ACM, Vol.9, No.3 (March, 1966), pp.157-166 (or here, here, or here)

P.J. Landin. The mechanical evaluation of expressions. The Computer Journal, Vol.6, No.4 (January, 1964), pp.308-320

W.H. Burge. Recursive programming techniques. Addison-Wesley, 1975

boykobbatgmaildotcom