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 a Professor Emeritus at the University of Rome "La Sapienza" and a computer scientist known especially for his contributions to the theory of structured programming, constructive mathemati ...
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 k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
.
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 t ...
. It had no special constructs like user defined functions,
control structures
In computer science, control flow (or flow of control) is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an ''imp ...
. Variables represented only
non-negative integer
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal n ...
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