Prehistory of esoteric programming languages

From Esolang
Jump to: navigation, search

While INTERCAL marks a watershed in the history of esoteric programming languages, it is by no means the first of the genre. In fact its main serious effect is the recognition that languages with screwy syntax and semantics might be objects worthy of study in their own right. But, there were esoteric programming languages in the 1960s and even earlier.

Obviously, before computers had programming languages (say 1950 or so) nobody had any idea what they ought to look like, and a lot of more-or-less screwy ideas were tried out before the establishment of the hegemony of languages in the Algol, FORTRAN and Lisp families. What distinguishes these languages from "modern" (post-INTERCAL) esoteric languages is that people intended them to be used for serious purposes. The principles of programming language design, and indeed of programming in general, that most of us take for granted today had not yet been worked out, and these languages were serious attempts to explore the possibilities. Take EXPLOR, for example: here is a programming language with probabilistic execution (every instruction specifies the probability with which it should be executed) and no variables -- every instruction operates on either the screen image or other instructions. Nevertheless, it was used by multiple artists to generate a wide range of animated art, and was used for several years to teach computer graphics to artists and children. For those of us interested in continuing along the esoteric path, there is a lot to be gleaned from early struggles with the very nature of programming.

Here's a short list of a few exemplars:

Corrado Böhm's P′′[edit]

Main article: P′′

The theoretical programming language P′′.png is a formal-language predecessor of brainfuck — but is even more "minimalist", having only four instruction-symbols 'R', 'λ', '(', ')', equivalent to what brainfuck would write as '>', '+<', '[', ']', respectively. (Or, since P′′ memory is unbounded to the left to match the manner in which many numerical computations are normally done by hand, the correspondence might be reflected as '<', '+>', '[', ']' in brainfuck.) P′′ was published in 1964 by Corrado Böhm and was also used later in the seminal and often-cited 1966 paper by Böhm & Jacopini on the structured program theorem; so, in a sense, P′′ was the first "structured programming" language. Böhm constructed P′′ programs sufficient to compute any computable function, thus establishing its Turing-completeness.

Ken Knowlton's languages[edit]

EXPLOR program output

Ken Knowlton designed a whole bunch of peculiar, but exquisitely useful, languages at Bell Labs in the 1960s and '70s. L6 (the Bell Labs Low Level Linked List Language) was a very low-level language for manipulating linked data structures whose basic primitives involved Bugs that walked from node to node.

BEFLIX and EXPLOR were languages for making movies of bitmap graphics. Here's a sample EXPLOR program, which produced a short animation ending in the abstract image to the right.

    dim    (1,1)    (512,384)
    wbt    (1,1)    (abc,012,)
    bxl    (1,1)    40(20,20,45,45,10,10,50,38)1(a.)
 ax axl    (1,1)    4,news,01,1(.01)
    axl    (1,1)    4,news,12,1(.12)
    axl    (1,1)    4,news,ab,1(.ab)
    axl    (1,1)    4,news,bc,1(.bc)
    xl     (1,1)    1(.012abac0)
    camera (1,1)    1
 cm goto   (x,29,1) ax

One of Ken's movies (made with BEFLIX, I think) was an animated introduction to L6.

GPM and TRAC language[edit]

TRAC (Text Reckoning And Compiling) language was devised by Calvin N Mooers in 1964. It had the peculiar property that programs diddled themselves until they were the answer. Here's an example (from [1]), that putatively computes Fibonacci numbers:

 :(s,fibo,(
 :(ei,<1>, 1, 0,(
 :(ei,<1>, 2, 1,(
 :(aa, :(ri,fibo,:(as, <1>,1)),:(ri,fibo,:(as, <1>,2)))
 ))
 ))
 ))`
 :(mw,fibo)'

Christopher Strachey's GPM (General Purpose Macrogenerator), invented about the same time, independently used a similar principle.

The idea that complex computations can be done by rewriting has been around since Emil Post's tag machines (invented in 1920, but not published until the '40s.) Macro processors with serious computational ability date to Doug McIlroy's work on macroassemblers in the late '50s and early '60s.

TECO and QED, two macro-based text editors, took this idea to extremes. They were the geek's choice of editors in the '60s and '70s (TECO at MIT, QED at Bell Labs.) Both had macro facilities that made them Turing-complete; programs in either looked like line noise. For example, the QED command ea/\(\ea*\)/ defines a pattern that matches any non-empty balanced string of parentheses. Mark Chu-Carroll has just posted a detailed appreciation of TECO [2] to his Good Math, Bad Math weblog [3].

TMG[edit]

TMG (for TransMoGrify) was a compiler-writing system, designed by Robert McClure, and further extended by Doug McIlroy. It made syntax-directed translation really easy, but with an abstruse syntax and semantics that any esoteric language enthusiast could appreciate. Here's an example from McIlroy's UNIX TMG manual that translates fully parenthesized infix expressions to Polish postfix:

 expr: <(>/exp1 expr operator expr <)> = { 3 1 2 };
 exp1: ident = { < LOAD > 1 };
 operator:
 op0: <+>/op1 = { < ADD > };
 op1: <->/op2 = { < SUB > };
 op2: <*>/op3 = { < MPY > };
 op3: </>     = { < DIV > };

APL[edit]

The original APL, a notation for mathematics and programming, was invented by Ken Iverson in the late 1950s and published in his 1962 book A Programming Language. The original notation involved lists of statements in a box, with arrows connecting lines to indicate control flow, all written in a notation reminiscent of mathematics, complete with mixed Greek and Latin alphabets, super- and subscripts and weird invented symbols. The values of variables could be numbers, strings, multi-dimensional arrays and trees.

APL is important for two reasons: first, it turned out to be a useful notation for describing computer hardware (operational details of the IBM /360 series were all worked out in APL) and second, an interactive time-shared implementation of a big part of the language was made available around 1967. The implementation left out the tree data structures, and greatly simplified the notation to make it possible to type programs in, but retained the weird character set by using a typewriter terminal with customizable fonts (the IBM 2741, a Selectric typewriter with a computer interface.)

References[edit]

  1. Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, July 1964.
  2. Böhm, C. and Jacopini, G.: "Flow diagrams, Turing machines and languages with only two formation rules", CACM 9(5), 1966. (Note: This is the most-cited paper on the structured program theorem.)
  3. Knowlton, K. C., "A computer technique for producing animated movies", AFIPS '64 (Spring) Proceedings of the April 21-23, 1964, spring joint computer conference
  4. Knowlton, K. C., "A programmer's Description of L6", Comm. ACM, Vol. 9, No. 8 (Aug. 1966), pp. 616-625
  5. Knowlton, K. C., "EXPLOR - A Generator of Images from Explicit Patterns, Local Operations, and Randomness," Proceedings of UAIDE Annual Meeting, Stromberg Datagraphix, 1970.
  6. C. Strachey", "A general purpose macrogenerator", Computer J., Vol. 8, No. 3 (Oct 1965), pp. 225-241
  7. Mooers, C.N., "TRAC, a text handling language". Proc. ACM 20th Nat. Conf., Cleveland, Aug. 1965, pp. 229-246.
  8. An incomplete history of the QED text editor by Dennis Richie
  9. Worlds Greatest Pathological Language: TECO, an appreciation by Mark Chu-Carroll
  10. McClure, R. M., "TMG--A Syntax-Directed Compiler", Proc 20th ACM National Conf. (1968), pp. 262-74.
  11. A Manual for the Tmg Compiler-writing Language by Doug McIlroy, transcribed from the sixth edition UNIX manual
  12. Iverson, K. E., A Programming Language, 1962, John Wiley and Sons, Inc.
  13. Sammet, Jean E., Programming Languages: History and Fundamentals, 1969, Prentice-Hall -- a great historical and technical reference covering 120 pre-1969 languages.