Papers on programming languages: ideas from 70's for today

I present here a small bibliography of papers on programming languages from the 1970’s. I have personally considered these papers interesting in my research on the syntax of programming languages. I give here short annotations and comments (adapted to modern’s day notions) on some of these papers.

Concrete syntax does make a difference. :-)

ALGOL 68 might-have-beens, by S. G. van der Meulen (1977)

About “natural, easy to implement and orthogonal” features missing from Algol. 10+ such features are mentioned.

  • Collateral loop statement with i,j thru hilbert do hilbert(i,j) := 1/(i+j-1) od, to be used instead of nested loops.
  • Mutable/immutable state: assignments x := y; vs. x := copy y;
  • Four new kinds of ref: refix— assignable only (“write-only”), refex — dereferencable only (“read-only”), ref — both assignable and dereferenceable, fer— neither assignable nor dereferenceable, for transfer only.

Moral (according to the author):

a next language should be one which is truly extensible in the sense that a programmer can specify his own might-have beens and declare them within the framework of the language

Doesn’t it resemble language-oriented / intentional programming? ;-)


On the use of keywords for passing procedure parameters, by Rodney Parkin (1978)

About naming parameters in procedure calls.

  • For example, there is a subroutine procedure f(x:integer); begin ... end; ; then its invocation is f(x:=5); , where the formal parameter x is explicitly named.
  • The scope of identifier x is not just procedure f, but also the left-hand side of the assignment x:=5 within the call to f. This may lead to problems when there is a global variable with the same name, as in f(x:=x);
  • What if procedures are first-class concepts?
procedure invoke(procedure what_to_invoke(its_param:integer), param:integer);
begin
what_to_invoke(its_param := param);
end;
procedure silly(x:integer); begin end;

The invocation then is like this:

invoke(what_to_invoke == silly, param := 1);

Here for actual arguments that are functions names == is used instead of := .

IntelliJ IDEA apparently knows about this paper :-)

The use of names to indicate the scope of structured language constructs, by M. G. Richardson (1977)

Argues about naming instances of any construct, for instance:

begin entire_program; ... end entire_program;

or

While data_available; ... Do ... End While data_available;

One of the author’s reasons to implement this is that

maintaining a stack of construct names whilst the program was being compiled would allow a compiler to pinpoint the programmer which construct he has in fact failed to compile, although in practice I believe that the occurrence of such errors would itself be greatly reduced by this device

Note that the paper was written in 1977 (no powerful IDEs at that time!). Clearly, programs are not written on a piece of paper now, so error detection argument seems trivial.

The language usability argument is valid though: in a function declaration, for example, it is convenient to see at the end of the declaration which function is being declared.

void f(int x) {
   // over 9000 lines of code
} // f

This is implemented, for example, in mbeddr.


Towards the ideal programming language, by Robert G. Herriot (1977)

Argues about how natural language can be used in programming languages. Has many examples of interesting constructs.

  • Indefinite articles for declarations of identifiers, definite articles for their uses:
function contents(var a memory: some_array_type,
var an index: integer);
begin
contents := the memory[the index];
end;
  • Identifiers consisting of several words:
the initial flight . the departing time . the hour := 9;
  • “English-friendly” versions of the . operator:
initial flight's departing time's hour := 9;

and

the hour of the departing time of the initial flight := 9;
  • Tagged procedure parameters:
push 3 on the main stack; // instead of push(3, mainstack);
location of "B" in the table // instead of location("B", table)
  • Even more enhanced constructs:
write the top of the stack, which is then pop'd;
3 is push'd on the stack;

Critical comments on the programming language Pascal, by A. N. Habermann (1973)

Argues, among many other things, about using conditional expressions of the form

i := if i = 7 then 1 else i + 1;

instead of

if i = 7 then i:=1 else i:=i+1;
The [first] statement expresses more clearly that a value is assigned to i than the [second] statement in which it is more or less incidental that both alternative statements assign to i and do nothing else.

Block statements and synonyms for PASCAL, by E. N. Kittlitz (1976)

Suggests syn declaration that defines a name for a certain code block. Argues about potential use when nested procedures are used.

procedure f;
syn XSYN;
var a, b: integer;
procedure g;
var a, b: integer;
begin
XSYN.a := a;
b := XSYN.b;
end;
begin
...
end;

A survey of control structures in programming languages, by David A. Fisher (1972)

Discusses about 40+ control structures (e.g., parellel assignments, coroutines, multipass algorithms).

  • Nondeterministic programs: a program to find two distinct digits x and y whose sum is fifteen is
condition(x <- select(0,9)) < (y <- select(0,9)) & (x+y=15);

The chemistry of control structures, by Ben Shneiderman (1974)

The proliferation in control structures is healthy, since it demonstrates the growth of the discipline and the exploration of new areas. But like the chemists who needed the Periodic Table of Elements to organize the large number of atoms that were discovered, … computer scientists must develop a taxonomy of control structures. Such a taxonomy would clarify our thinking about the relationship among the varying control structures and might suggest some new structures which we have missed in the past.
  • Assignments of the form A = B = C vs. “elementary” two assignments A = B and B = C .
  • Loop statement with “joint” ranges DO I = 1 TO 10, 21 TO 30 ...

Another look at the CASE statement, by W. C. M. Vaughan (1974)

Discussion about labelled case statement (as in Pascal) and indexed case statement (as in Algol 68).


IF-THEN-ELSE considered harmful, by Gerald M. Weinberg, Dennis P. Geller, Thomas W. S. Plum (1975)

Argues about using forms of switch statement instead of if statements.


Nested scopes in Pascal and Algol 68, by Norman Hardy (1983)

Programming languages have made explicit what mathematical notations have assumed for many years; Sum(i = 1 to 9: f(i)) refers to f but not to i. This mathematical notation may be the origin of the nested scopes.

Further critical comments on PASCAL, particularly as a systems programming language, by Reidar Conradi (1976)

Mainly about execution semantics of Pascal. Has some suggestions to adopt other language’s constructs (mainly, Algol and Mary) in Pascal.


Preprocessing of typed two-dimensional mathematical expressions, by Mark B. Wells (1976)

How to transform a mathematical expression written in a two-dimensional form to a linear representation.


Graphical systems and two-dimensional mathematical expressions, by James E. George (1972)

About how to convert a linear representation of a mathematical expression into two-dimensional.

A language implemented within JetBrains MPS: no problems with two-dimensional notation (and even arbitrary graphical notation!) in its projectional editor

More papers

The remaining trouble spots in ALGOL 60, by Donald E. Knuth (1967)

Ten mini-languages in need of formal definition, by Henry F. Ledgard (1970)

Restricted global variables in Algol 60, by R. A. Krutar (1973)

Variables: bindings and protection, by James E. George, Gary R. Sager (1973)

Global variable considered harmful, by W. Wulf, Mary Shaw (1973)

Comments considered harmful, by Anders Beckman (1977)

Structured languages, by Leon Presser (1975)

A compatible “structured” extension to Fortran, by Loren P. Meissner (1974)

Array reference operations, by J. B. Hext (1975)

The problem of the definition of subroutine calling conventions, by William A. Wulf (1972)

Suggested revisions and additions to the syntax and control mechanisms of SNOBOL4, by Ralph E. Griswold (1974)

On a missing mode in ALGOL 68, by H. D. Baecker (1972)

Issues in programming language design: an overview, by Anthony I. Wasserman (1975)

The design of a procedureless programming language, by Clair W. Goldsmith (1974)

Control constructs for programming languages, by Eberhard Wegner (1975)

Algol 68 as an extensible language, by Barry J. Mailloux, John E. L. Peck (1969)

Extensibility in programming language design, by Thomas A. Standish (1975)

Alternatives to extensible languages, by M. D. McIlroy (1969)


Many ideas presented in these papers have been implemented in modern programming languages and became standard. No one would question nowadays whether syntax num = 20 if someBoolValue else 30 makes sense or not: it is a reality of life that this is a statement in Python.

My main goal when collecting this bibliography was to find the sources of why certain things are one way or another. I hope you find “interesting grains” in some of the papers I presented here and I am looking forward for your comments!