Böhm's language refers to the language, machine and a translation method developed by
Corrado Böhm
Corrado Böhm (17 January 1923 – 23 October 2017) was an Italian computer scientist and Professor Emeritus at the Sapienza University of Rome, University of Rome "La Sapienza", known especially for his contributions to the theory of structured ...
during the latter part of 1950. Böhm used this work as part of his
dissertation, submitted in 1951 (amended after submission), published in 1954.
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. 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.
Böhm's parsing technique for expressions had only linear complexity. It generated instructions to a structure similar to a
binary tree
In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the ''left child'' and the ''right child''. That is, it is a ''k''-ary tree with . A recursive definition using set theor ...
.
The language
Böhm's language consisted of only
assignment operations
Assignment, assign or The Assignment may refer to:
* Homework
* Sex assignment
* The process of sending National Basketball Association players to its development league; see
Computing
* Assignment (computer science), a type of modification to ...
. It had no special constructs like user defined functions,
control structures. Variables represented only
non-negative integer
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...
s. To perform a jump one had to write to a special π variable. To perform I/O ? symbol was used.
[Knuth, p. 36-37]
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
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
Sources
*
Knuth, Donald E.; Pardo, Luis Trabb (1976). "
Early development of programming languages". Stanford University, Computer Science Department.
{{DEFAULTSORT:Bohm's language
Translation
Computer languages
Computer data
Encodings