The Next 700 Programming Languages

The Next 700 Programming Languages

P. J. Landin

Univac Division of Sperry Rand Corp., New York, New York

"... today... 1,700 special programming languages used to 'com- municate' in over 700 application areas."

--Computer Software Issues,

an American Mathematical Association Prospectus, July 1965.

A family of unimplemented computing languages is described that is intended to span differences of application area by a unified framework. This framework dictates the rules about the uses of user-coined names, and the conventions about characterizing functional relationships. Within this framework the design of a specific language splits into two independent parts. One is the choice of written appearances of programs (or more generally, their physical representation). The other is the choice of the abstract entities (such as numbers, character-strings, lists of them, functional relations among them) that can be referred to in the language.

The system is biased towards "expressions" rather than "statements." It includes a nonprocedural (purely functional) subsystem that aims to expand the class of users' needs that can be met by a single print-instruction, without sacrificing the important properties that make conventional right-hand-side expressions easy to construct and understand.

1. Introduction

Most programming languages are partly a way of expressing things in terms of other things and partly a basic set of given things. The IsWIM (If you See What I Mean) system is a byproduct of an attempt to disentangle these two aspects in some current languages.

This attempt has led the author to think that many linguistic idiosyneracies are concerned with the former rather than the latter, whereas aptitude for a particular class of tasks is essentially determined by the latter rather than the former. The conclusion follows that many language characteristics are irrelevant to the alleged problem orientation.

IsWIM is an attempt at a general purpose system for describing things in terms of other things, that can be problem-oriented by appropriate choice of "primitives." So it is not a language so much as a family of languages, of which each member is the result of choosing a set of primitives. The possibilities concerning this set and what is needed to specify such a set are discussed below.

IsWIM is not alone in being a family, even after mere syntactic variations have been discounted (see Section 4). In practice, this is true of most languages that achieve more than one implementation, and if the dialects are well disciplined, they might with luck be characterized as differences in the set of things provided by the library or operating system. Perhaps had ALGOL 60 been launched as a family instead of proclaimed as a language, it would have fielded some of the less relevant criticisms of its deficiencies

At first sight the facilities provided in IsWIM will appear comparatively meager. This appearance will be especially misleading to someone who has not appreciated how much of current manuals are devoted to the explanation of common (i.e., problem-orientation independent) logical structure rather than problem-oriented specialties. For example, in almost every language a user can coin names, obeying certain rules about the contexts in which the name is used and their relation to the textual segments that introduce, define, declare, or otherwise constrain its use. These rules vary considerably from one language to another, and frequently even within a single language there may be different conventions for different classes of names, with near-analogies that come irritatingly close to being exact. (Note that restrictions on what names can be coined also vary, but these are trivial differences. When they have any logical significance it is likely to be pernicious, by leading to puns such as ALGOL'S integer labels.)

So rules about user-coined names is an area in which we might expect to see the history of computer applications give ground to their logic. Another such area is in specifying functional relations. In fact these two areas are closely related since any use of a user-coined name implicitly involves a functional relation; e.g., compare

$ x(x+a) $

where $x = b -4- 2c$

$ f(b+2c) $

where $f(x) = x(x+a) $

ISWIM is thus part. programming language and part program for research. A possible first step in the research program is 1700 doctoral theses called "A Correspondence between x and Church's X-notation.

2、The where-Notation

In ordinary mathematical communication, these uses of 'where' require no explanation. Nor do the following:

$ f(b+2c) + f(2b-c) $

where $ f(x) = x(x+a) $

$ f(b+2c) + f(2b-c) $

where $ f(x) = x(x+a) $

and $b=\mu/(\mu+1)$

and $c=\nu/(\nu+1)$

$g(f$ where $f(x)=ax^{2}+bx+c$,

$\mu/(\mu+1)$

$\nu/(\nu+1))$

where $g(f,p,q) = f(p+2q, 2p-q)$

A phrase of the form 'where definition' will be called a "where-clause." An expression of the form 'expression where-clause' is a "where-expression." Its two principal components are called, respectively, its "main clause" and its "supporting definition." To put 'where' into a programming language the following questions need answers

Linguistic Structure. What structures of expression can appropriately be qualified by a where-clause, e.g., conditional expressions, operand-listings, statements, declarations, where-expressions?

Likewise, what structures of expression can appropriately be written as the right-hand side (rhs) of a supporting definition? What contexts are appropriate for a where-expression, e.g., as an arm of a conditional expression, an operator, the main-clause of a where-expression, the left-hand side (lhs) of a supporting definition, the rhs of a supporting definition?

Syntax. Having answered the above questions, what are the rules for writing the acceptable configurations unambiguously? E.g., where are brackets optional or obligatory? or other punctuation? or line breaks? or indentation? Note the separation of decisions about structure from decisions about syntax. (This is not a denial that language designers might iterate, like hardware designers who distinguish levels of hardware design.)

Semantic Constraints on Linguistic Structure. In the above examples each main clause was a numerical expression; i.e., given appropriate meanings for the various identifiers in it, it denoted a number. What other kinds of meaning are appropriate for a mainclause, e.g., arrays, functions, structure descriptions, print-formats?

Likewise what kinds of meaning are appropriate for rhs's of supporting definitions? Notice there is not a third question analogous to the third question above under linguistic structure. This is because a where-expression must mean the same kind of thing as its main clause and hence raises no new question concerning what contexts are meaningful. Notice also that the questions about meaning are almost entirely independent of those about structure. They depend on classifying expressions in two ways that run across each other.

Outcome. What is the outcome of the more recondite structural configurations among those deemed admissible, e.g. mixed nests of where-expressions, function definitions, conditional expressions, etc.?

Experimental programming has led the author to think that there is no configuration, however unpromising it might seem when judged cold, that will not turn up quite naturally. Furthermore, some configurations of 'where' that might first appear to reflect somewhat pedantic distinctions, in fact provide close matches for current language features such as name/value and own (see [2, 3]).

All these questions are not answered in this paper. The techniques for answering them are outlined in Section 4

One other issue arises when 'where' is added to a programming language-types and specifications. A method of expressing these functionally is explained in [2]. It amounts to using named transfer-functions instead of class names like integer, i.e., writing

where $ n = round(n) $

instead of the specification

integer $ n $

Thus the use of functional notation does not jeopardize the determination of type from textual evidence

3. Physical ISWIM and :Logical ISWIM

Like ALGOL 60, ISWIM has no prescribed physical appearance. ALGOL 60'S designers sought to avoid commitment to any particular sets of characters or type faces. Accordingly they distinguish between "publication language," "reference language" and "hardware languages." Of these the reference language was the standard and was used in the report itself whenever pieces of ALGOL 60 occurred. Publication and hardware languages are transliterations of the reference language, varying according to the individual taste, needs and physical constraints on available type faces and characters.

Such variations are different physical representations of a single abstraction, whose most faithful physical representation is the reference language. In describing ISWIM we distinguish an abstract language called "logical ISWIM," whose texts are made up of "textual elements," characterized without commitment to a particular physical representation. There is a physical representation suitable for the medium of this report, and used for presenting each piece of ISWIM that occurs in this report. So this physical representation corresponds to "reference ALGOL 60," and is called "reference ISWIM," or the "ISWIM reference representation," or the "ISWIM reference language."

To avoid imprecision one should never speak just of "ISWIM," but always of "logical IswxM" or of "such-and-such physical ISWlM." However, in loose speech, where the precise intention is clear or unimportant, we refer to "ISWlM" without qualification. We aim at a more formal relation between physical and logical languages than was the case in the ALGOL 60. This is necessary since we wish to systematize and mechanize the use of different physical representations.

4. Four Levels of Abstraction

The "physical/logical" terminology is often used to distinguish features that are a fortuitous consequence of physical conditions from features that are in some sense more essential. This idea is carried further by making a similar distinction among the "more essential" features. In fact ISWIM is presented here as a four-level concept comprising the following:

(1) physical ISWIM'S, of which one is the reference language and others are various publication and hardware languages (not described here)

(2) logical ISWIM, which is uncommitted as to character sets and type faces, but committed as to the sequence of textual elements, and the grammatical rules for grouping them, e.g., by parentheses, indentation and precedence relations.

(3) abstract ISWIM, which is uncommitted as to the grammatical rules of sequence and grouping, but committed as to the grammatical categories and their nesting structure. Thus abstract Iswim is a “tree language’ of which logical ISWIM is one linearization

(4) applicative expressions (AEs), which constitute another tree language, structurally more austere than abstract ISWIM,and providing certain basic grammatical categories in terms of which all of Iswim's more numerous categories can be expressed.

The set of acceptable texts of a physical Iswim is specified by the relations between 1 and 2, and between 2 and 3. The outcome of each text is specified by these relations, together with a "frame of reference", i.e., a rule that associates a meaning with each of a chosen set of identifiers

These are the things that vary from one member of our language family to the next. The specification of the family is completed by the relation between abstract ISWIM and AEs, together with an abstract machine that interpret AEs. These elements are the same for all members of the family and are not discussed in this paper (see [1, 2, 4]).

The relationship between physical ISWIM and logical ISWIM is fixed by saying what physical texts represent each logical element, and also what layout is permitted in stringing them together. The relationship between logical ISWIM and abstract ISWIM is fixed by a formal grammar not unlike the one in the ALGOL 60 report, together with astatement connecting the phrase categories with the abstract grammatical categories

These two relations cover what is usually called the “syntax’ or “grammar’ of a language. In this paper syntax is not discussed beyond a few general remarks anda few examples whose meaning should be obvious

The relationship between abstract ISWIM and AEs is fixed by giving the form of AE equivalent to each abstract ISWIM grammatical category. It happens that these latter include a subset that exactly matches AEs. Hence this link in our chain of relations is roughly a mapping of ISWIM into an essential kernel’ of ISWIM, of which all the rest is mere decoration.

5. Abstract ISWIM

The texts of abstract ISWIM are composite information structures called amessage's. The following structure definition defines the class amessage in terms of a class called identifier. It also defines several functions for manipulating amessage's. These comprise the predicates demand, simple, infixed, etc; also the selectors body, rator,leflarm, nee, etc; also (taking for granted certain unformalized conventions concerning structure definitions) the constructors, consdemand, conscombination (elsewhere abbreviated to combine), consstandardadef, etc. Examples of reference ISWIM are given alongside, against the right margin.

An amessage is either a demand, and has a body which is an aexpression,or else a definition,

$ [Print \qquad a+2b $

$ [Def \qquad x=a+2b $

5.1 where rec

an aexpression (aexp) is

5.1.1 either simple, and has a body which is an identifier

$ [C Ath231'' $

5.1.2 or a combination,

in which case

• it has a rator,

  which is an aexp,

  $ [sin(a+2b) $

• and a rand,

  which is an aexp,

  $ a+2b $

5.1.3 or conditional, in which case it is

• either two-armed,

  and has a condition, which is an aexp, and a leftarm, which is an aexp, and a rightarm, which is an aexp,

  $ [p\to a+2b ; \quad 2a-b$

• or one-armed,

  and has a condition, which is an aexp, and an arm, which is an aexp

  $ [p\to 2a-b$

5.1.4 or a listing, and has a body which is an aexp-list,

$ [a+b,c+d,e+f $

5.1.5 or beet, and has

• a mainclause,

  which is an aexp,

  $ [x(x+1) \quad where \quad x=a+2b $

• and a support

  which is an adef

  $ let \quad x=a+2b; \quad x(x+1) $

5.2 and an a definition (adef)

5.2.1 is either standard,

and has

a definee (nee), which is an abv,

and a defniens (niens), which is an aexp

$ [x=a+2b $

5.2.2 or functionform,

and has

• a lefthandside (lhs) which is an abv-list of length $\ge 2$

• and a righthandside (rhs), which is an aexp

$[f(x)=x(x+1)$

5.2.3 or programpoint,

and has a body which is an adef.

$[pp \quad f(x)=x(x+1)$

5.2.4 or circular,

and has a body which is an adef.

$ [rcc \quad f(n)=(n=0) \to 1; nf(n-1)$

5.2.5 or simultaneous,

and has a body, which is an adef-list.

$ [x=a+2b \quad and \quad y=2a-b$

5.2.6 or beet, and has

a mainclause which is an adef and a support, which is an adef

$ f(y)=x(x+y) \quad where \quad x=a+2b$

5.3 where an abv is

5.3.1 either simple,

and has a body, which is an identifier.

5.3.2 or else, is an abv-list.

$ [k, (y, z), w$

A program-point definition introduces a deviant kind of function. Applying such a function precipitates premature termination of the where-expression containing it, and causes its result to be delivered as the value of theentire where expression.

Program-points are ISWIM's, nearest thing to jumping. Assignment is covered as a particular case of an operator. For both of these the precise specification is in terms of the underlying abstract machine.

6. Relationship to LISP

ISWIM can be looked on as an attempt to deliver LISP from its eponymous commitment to lists, its reputation for hand-to-mouth storage allocation, the hardware dependent flavor of its pedagogy, its heavy bracketing, and its compromises with tradition. These five points are now dealt with in turn:

(1) ISWIM has no particular problem orientation. Experiments so far have been mainly in numerical work and language processing with brief excursions into "commercial" programming and elsewhere. No bias towards or away from a particular field of application has emerged

(2) Outside a certain subset (corresponding closely to ALGOL 0 without dynamic own arrays), ISWIM needs garbage collection. An experimental prototype implementation followed common ALGOL 60 practice. It used dynamic storage allocation with two sources, one LIFO and the other garbage collected, with the intention that the LIFO source should take as big a share as possible.

However, as with ALGOL 60, there is a latent potential for prealloeating storage in certain favorable and commonly useful situations. Compared with LISP the chief amelioration of storage allocation comes out of a mere syntactic difference, namely, the use of where ( 'let' which is exactly equal in power and program structure). This provides a block-structure not dissimilar in textual appearance from ALGOL 60'S, though it slips off the pen more easily, and is in many respects more general.

(3) Lisp has some dark corners, especially outside "pure LISP," in which both teachers and programmers resort to talking about addresses and to drawing storage diagrams. The abstract machine underlying ISWIM is aimed at illuminating these corners with a mininmm of hardware dependence.

(4) The textual appearance of ISWIM is not like Lisp's S-expressions. It is nearer to LISP'S M-expressions (which constitute an informal language used as an intermediate result in hand-preparing LISP programs). ISWIM has the following additional features:

(a) "Auxiliary" definitions, indicated by 'let' or 'where', with two decorations: 'and' for simultaneous definitions, and 'rec' for self-referential definitions (not to be mistaken for a warning about recursive activation, which can of course also arise from self-application, and without self-reference).

(b) Infixed operators, incorporated systematically. A logical ISWIM can be defined in terms of four unspecified parameters: three subsets of the class of identifiers, for use as prefixed, infixed and postfixed operators; and a precedence relation defined over the union of these subsets.

(c) Indentation, used to indicate program structure. A physical ISWIM can be defined in terms of an unspecified parameter: a subset of phrase categories, instances of which are restricted in layout by the following rule called "the offside rule." The southeast quadrant that just contains the phrase's first symbol must contain the entire phrase, except possibly for bracketed subsegments. This rule has three important features. It is based on vertical alignment, not character width, and hence is equally appropriate in handwritten, typeset or typed texts. Its use is not obligatory, and use of it can be mixed freely with more conventional alternatives like punctuation. Also, it is incorporated in ISWIM in a systematic way that admits of alternatives without changing other features of ISWIM and that can be applied to other languages

(5) The most important contribution of Lisp was not in listprocessing or storage allocation or in notation, but in the logical properties lying behind the notation, Here ISWIM makes little improvement because, except for a few minor details, Lisp left none to make. There are two equivalent ways of stating these properties.

(a) Lisp simplified the equivalence relations that determine the extent to which pieces of program can be interchanged without affecting the outcome.

(b) Lisp brought the class of entities that are denoted by expressions a programmer can write nearer to those that arise in models of physical systems and in mathematical and logical systems.

These remarks are expanded in Sections 7 and 8.

7. The Characteristic Equivalences of ISWIM

For most programming languages there are certain statements of the kind, "There is a systematic equivalence between pieces of program like this, and pieces like that," that nearly hold but not quite. For instance in ALGOL 60 there is a nearly true such statement concerning procedure calls and blocks.

At first sight it might appear pedantic to quibble about such untidiness--"What's the point of having two different ways of doing the same thing anyway? Isn't it better to have two facilities than just one?" The author believes that expressive power should be by design rather than accident, and that there is great point in equivalences that hold without exception. It is a platitude that any given outcome can be achieved by a wide variety of programs. The practicability of all kinds of program-processing (optimizing, checking satisfaction of given conditions, constructing a program satisfying given conditions) depends on there being elegant equivalence rules. For ISWIM there are four groups, concerning:

(1) the extent to which a subexpression can be replaced by an equivalent subexpression without disturbing the equivalence class of the whole expression. Without this group the other rules would be applicable only to complete expressions, not to subexpressions.

(2) user-coined names, i.e., in definitions and, in particu- lar, function definitions.

(3) built-in entities implicit in special forms of expression. The only iiistanees of this in ISWIM are conditional expressions, listings and self-referential definitions.

(4) named entities added in any specific problem orientation of ISWIM.

7.1 Group 1

$(\mu) \quad If \quad L \equiv L' \quad then \quad L(M) \equiv L'(M)$

$(\nu) \quad If \quad M \equiv M' \quad then \quad L(M) \equiv L(M')$

$(\nu') \quad If \quad M \equiv M' \quad then \quad (L,...,M,...,N) \equiv (L,...,M',...N)$

$(\nu'') \quad If \quad L \equiv L' \quad then \quad (L \to M; N) \equiv (L' \to M; N)$

$(\nu''') \quad If \quad M \equiv M' \quad then \quad (L \to M; N) \equiv (L \to M'; N) $

$(\nu^{iv}) \quad If \quad N \equiv N' \quad then \quad (L \to M; N) \equiv (L \to M; N')$

$(\nu^{v}) \quad If \quad M \equiv M' \quad then \quad (L : where : x = M) \equiv (L : where : x = M')$

The significant omissions here are the main-clause in the last case above, the rhs of a function definition $"f(x) = M" $ and of a circular definition $ "rec x = M" $.

7.2 Group 2

$(let) \quad let : x = M; L \quad \equiv \quad L : where : x = M$

$(I')\quad f(x) = L \quad \equiv \quad f=(g : where : g(x)=L)$

$\quad \quad f(a, b, c)(x, y) = L \quad \equiv \quad f(a,b,c) = (g : where : g(x,y) = L)$

and so on for each shape of left-hand side

$(I) \quad (f : where : f(x)=L) M \quad \equiv \quad L : where : x=M $

$(\beta') \quad (x=L) : where : y=M \quad \equiv x=(L : where : y=M)$

$(D') \quad x = L : and : y=M : and \quad \equiv ... : and : z=N \quad \equiv (x,y,...,z) = (L,M,...,N)$