Kinds of Programming Languages

I find the number of programming languages mind-boggling. For example, Jean Sammet in her “Roster of programming languages for 1976-1977” [12] lists 156 programming languages in 24 categories. This includes only languages in active use within the USA. The opposite extreme on the spectrum of permissiveness is represented by the “Online historical encyclopedia of programming languages” [7], which claims 8945 “programming languages since the 18th century”.

I doubt whether Jacquard, with his punched cards for controlling looms, thought of card punchings as utterances in a language. I suspect that it is only with the benefit of hindsight that we recognize them as predecessors of the twentieth-century programming languages. Yet, at some point in time, in some place, there must have been a person to whom it first occurred that the programming tool under consideration was a language. I suspect that this occurred soon after the first stored-program electronic computer was running in 1949. At that time there wasn’t anything suggestive of language: there were lists of instructions in the form of sequences of octal digits to be entered via switches in successive memory locations. A sensible user must have first prepared a sheet of paper with a column of fixed-length octal numerals, one for each instruction.

In the beginning of this period, these numerals may not have been thought of as “words”, nor may sequences of such items have been considered as utterances in a language. For example, Konrad Zuse referred to such documents as computation plans expressed in a calculus (hence “Plankalkül”, 1944). A paper by Knuth and Pardo [8] helps pin down the moment when programming aids first were regarded as languages. They quote a 1951 report by Arthur Burks with a title that mentions a “program language” [3]. This makes him my best bet for having been the first to make the conceptual leap that connects these programming artifacts to the world of language.

Within a quarter century there existed a motley collection of programming languages [12]. One way to get some insight into the collection is to classify, as Sammet does with her 24 categories. In this article I propose several categorizations, each characterized by a question: Is the language designed by a committee?, Is it invented or discovered?, Is it conceived as a single-application language?, and, finally, Does it have an essence?.

  1. Is the language designed by a committee?

    This is the criterion used by Frederick Brooks [2] in distinguishing software products more generally. He published two lists, one of products that “excited passionate fans”, the other of unexciting but useful items. In the former category he puts Unix, APL, Pascal, Modula, Smalltalk, and Fortran; in the latter he places Cobol, PL/I, Algol, MVS/370, and MSDOS. Brooks says that the difference is explained by whether the language or operating system was designed by a committee.

    I think Brooks was onto something here, though we should add two items. If ever a language excited a devoted fandom, it is Lisp. If ever a language was further away from being committee-designed, it is Lisp: it was basically a one-man show, if one is willing to overlook crucial contributions of Herbert Gelernter and Steven Russell. Close to the one-man show, and still far away from the committee, are the small teams with a dominant designer: Smalltalk (Alan Kay) and Prolog (Alain Colmerauer). I want to add that language to Brooks’s list because it is one of those languages people can fall in love with.

    Brooks correctly puts “Algol” (presumably Algol 60) in the category of committee-designed. That is not a good move, as Algol 60 is not typical. In fact, it is a miracle, a term I borrow from the following quote.

    And then the 60s started with an absolute miracle, viz. ALGOL 60. This was a miracle because on the one hand this programming language had been designed by a committee, while on the other hand its qualities were so outstanding that in retrospect it has been characterized as “a major improvement on most of its successors” (C.A.R. Hoare).

    Several friends of mine, when asked to suggest a date of birth for Computing Science, came up with January 1960, precisely because it was ALGOL 60 that showed the first ways in which automatic computing could and should and did become a topic of academic concern. [5]).

  2. Was the language invented or discovered?

    The poet William Butler Yeats is said to have remarked that prose is endlessly revisable, while a poem snaps shut, like a box. Lisp and Prolog give me this feeling. These languages seem to have been discovered rather than invented. Algol 60 and Smalltalk are ingenious inventions rather than discoveries. When Paul Graham [5]) distinguishes C and Lisp as high points surrounded by the “swampy ground” of other programming languages I guess he had this aspect in mind. Of course he did not mean Common Lisp (committee-designed), but the interpreter of McCarthy’s 1960 paper [10]), possibly cleaned up as in Scheme.

  3. Was the language conceived for a single application?

    Maybe I can better start by explaining how to tell routine programming projects from the other ones: if it’s best to use an existing language, then it’s routine. Consider some of the other projects.

    1. The advice taker. In 1956 John McCarthy [9]), proposed a computer system that would not need to be programmed, but would incrementally become more useful by absorbing bits of “advice”. At the time Fortran was the highest-level language. Initially McCarthy worked on a version of Fortran enriched with lists as data structure. Apparently this seemed less than compelling after a while—Lisp was the result of his fresh start.
    2. A system for man-machine communication in French. Daniel Bobrow asked: “If Prolog is the answer, what is the question?” [1]), This is an instance of the pattern “If X is the answer, what was the question?”, a supposedly witty way of saying that X is a solution in search of a problem. In the case of Prolog this is a false accusation, as can be discovered with the help of internet. The problem was clearly specified as Project CRI 72-18, awarded to the University of Aix-Marseille. The project was to run from 1972 to 1973. It had as objective to design and implement “Un système de communication homme-machine en Français”. (“A system for man-machine communication in French.”) This was a non-routine programming project if ever there was one. The plan was to design and implement a suitable language first and then write the system in that language. The final report [4] included a manual for the language, which had not existed at the start of the project. The language had been named “Prolog”.
    3. Dynabook. In 1972 Alan Kay conceived of “Dynabook”, a computer-based media machine for “children of all ages”. Although Lisp came close, Kay decided on a fresh start. The result was Smalltalk.
    4. Strategy language. In the early 1970s Robin Milner undertook the design and implementation of a theorem-proving system for the logic of computable functions. The system, being automated, needed a programming language for writing proof tactics. This subsidiary project resulted in ML, for “metalanguage”.

    The advice taker never saw the light of day. It is not clear whether Dynabook ever did. All four languages escaped from their formative projects. They showed that when a man is confronted with an ambitious project, “it concentrates his mind wonderfully”.

  4. Does the language have an essence? The possibility of an affirmative answer is suggested by the title of John Reynolds’s paper: “The essence of Algol” [11]. Reynolds used what he perceived to be the essence of Algol to make distinctions among members of what is usually considered to be a single family. Thus he argues that Algol 60 is a carrier of the essence, whereas this is not the case for other members of that family: Algol W, Euler, Algol 68, and Pascal.

    What is judged to be essence is in the eye of the beholder. I am more interested in what the members of the Algol family have in common and perhaps even with languages not usually considered as members. This could be a topic for a future essay.

Acknowledgements

Thanks to Paul McJones for providing valuable information.

References

[1] Daniel G. Bobrow: “If Prolog is the Answer, What is the Question?” IEEE Transactions on Software Engineering, vol. SE-11, no. 1, November 1985.
[2] Frederick W. Brooks: “No silver bullet”. Computer Vol. 20, no. 4, April 1987, pp. 10–19.
[3] Arthur W. Burks: “An intermediate program language as an aid in program synthesis”, Engineering Research Institute, Report for Burroughs Adding Machine Company (Ann Arbor, Michigan: University of Michigan, 1951), ii + 15 pp.
[4] Alain Colmerauer: “Un système de communication homme-machine en Français” http://tinyurl.com/j4fknrf consulted October 14, 2016.
[5] Edsger W. Dijkstra: “Computing Science: Achievements and Challenges” (EWD1284) http://tinyurl.com/znbzyd7
[6] Paul Graham: “The Roots of Lisp”. http://www.paulgraham.com/rootsoflisp.html
[7] “Online Historical Encyclopaedia of Programming Languages”. hopl.info consulted October 14, 2016.
[8] Donald E. Knuth and Luis Trabb Pardo: “The early development of programming languages.” STAN-CS-76-562, August 1976. A history of computing in the twentieth century (1980): 197-273. The Stanford report is available as http://tinyurl.com/hsuwwrl (consulted October 16, 2016). It reports that the paper was commissioned by the Encyclopedia of Computer Science and Technology, Jack Belzer and Allen Kent (eds.)
[9] John McCarthy: “Programs with common sense”. In Mechanization of Thought Processes vol. I. Her Majesty’s Stationery Office, London 1959.
[10] John McCarthy: “Recursive functions of symbolic expressions and their computation by machine, Part I.” Communications of the ACM 3.4 (1960): 184-195.
[11] John C. Reynolds: “The Essence of Algol”. In Jaco W. de Bakker and J. C. van Vliet, editors, Algorithmic Languages, pp. 345-372. North-Holland, Amsterdam, 1981.
[12] Jean Sammet: “Roster of programming languages for 1976-77” ACM SIGPLAN Notices, 11/1978, Volume 13, Issue 11.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: