Böhm's language

Böhm's language refers to the language, machine and a translation method developed by Corrado Böhm during 1950. Böhm used this work as his dissertation, published in 1952.^[1]

The compiler

Böhm's work described the first complete meta-circular compiler. The code for the compiler was remarkably precise, and consisted of only 114 lines of code.^[2] Since the language accepted only two kinds of expressions: fully parenthesized or without parenthesis, but with operator precedence, therefore the code of the compiler split into two parts. 59 lines were used to handle formulas with parenthesis, 51 to handle operator precedence expressions and 4 to decide between those two cases.^[3]

Böhm's parsing technique for expressions had only linear complexity. It generated instructions to a structure similar to a binary tree.^[4]

The language

Böhm's language consisted of only assignment operations. It had no special constructs like user defined functions, control structures. Variables represented only nonnegative integers. To perform a jump one had to write to a special π variable. To perform I/O ? symbol was used.^[5]

An example program which loads 11-element array from an input would look as follows.

A. Set i = 0 (plus the                                π → G
   base address 100 for                             100 → i
   the input array a).                                B → π

B. Let a new input a[i] be                           π' → B
   given. Increase i by unity,                        ? → ↓i
   and stop if i > 10,                              i+1 → i
   otherwise repeat B.  [(1∩(i∸110))∙Ω]+[(1∸(i∸110))∙B] → π

∩ represents a minimum operator and ∸ logical difference.

References

1. Knuth, p. 36
2. Knuth, p. 36
3. Knuth, p. 39
4. Knuth, p. 40
5. Knuth, p. 36-37

Sources

• Knuth, Donald E.; Pardo, Luis Trabb (1976). "Early development of programming languages". Stanford University, Computer Science Department.