See also
Programming languages should not be designedby piling feature on top of feature.—after the RnRS reports
This note reviews David Schmidt’s language-extension principles for a basic imperative language.
None.
None.
An imperative language reflects the Von Neuman architecture: a memory and a processor sequentially executing instructions that are stored in the memory. Together, the processor and the memory define a state. The syntactic units of an imperative program implement a state change. Executing a program amounts to performing a series of state changes.
Here is the syntax of a prototypical imperative language:
where N+1 is the size of the store (i.e., of the available memory).
A program is a command, indicating the imperative nature of this programming language. The store can be updated at a given location (the assignment command, represented with the infix :=); commands can be executed one after another (the sequencing command, represented with the infix ;), selectively (the conditional command, represented with the mixfix if ... then ... else ..., repeatedly (the repetition command, represented with the mixfix while ... do ...), and in a grouped way (the block command, represented with the braces). An expression can be a reference in the store, a literal, a unary operation, or a binary operation. A literal can be a Boolean or a fix-sized integer. The operators are enumerated in the BNF.
This programming language is minimalistic, and it gives rise to terse programs. For example, here is how to compute the factorial of a given natural number (here: 5) in this programming language (reminder: the factorial of 5 is 1 * 2 * 3 * 4 * 5, i.e., 120):
loc0 := 5;
loc1 := 1;
loc2 := 1;
while @loc1 <= @loc0 do {
loc2 := @loc2 * @loc1;
loc1 := @loc1 + 1
};
loc0 := @loc2
This program starts by storing the input number at Location 0. It yields the resulting factorial number at Location 0, and uses Locations 1 and 2 in the course of the computation.
Simulate, by hand, a run of this program. What result does it give?
NB. The program above is implemented using the BNF of the basic imperative language from the previous chapter as a unit test for its interpreter. Therefore you can correlate your simulation by
loading the syntax checker;
loading the interpreter after tracing visit in run-command; and
interpreting the factorial program in a store of size at least 3, as in the following scenario:
> (run-program (make-factorial-program 5) 3)
...
(120 6 120)
>
Beware of the Turing tar pitin which everything is possiblebut nothing of interest is easy.—Alan Perlis‘s programming epigram #54
Why do we find this prototypical imperative language to be not very expressive? One answer is that it does not let us abstract syntactic entities, giving them names (definition) and referring to them using these names (use). Let us extend the language with this ability to define and to use abstractions. We want to be able to abstract each of the non-terminals in the grammar, i.e., literals, operators, locations, expressions, and commands. To this end, let us introduce a new non-terminal for declarations, be them parallel, sequential, or grouped, and a new non-terminal for names. To be consistent, we need to also have the ability to name declarations as well as to name names, since names and declarations form new non-terminals in the grammar. And finally, let us extend each grammar production with the ability to invoke named entities. The resulting BNF reads as follows:
Revisiting the example above, here is a more abstract way to compute the factorial of a given number (here: 5) in this BNF:
block {
input = 5,
ref_n = loc0,
ref_i = loc1,
ref_x = loc2
} ; {
val_n = @ref_n,
val_i = @ref_i,
val_x = @ref_x
}
in ref_n := input;
ref_i := 1;
ref_x := 1;
while val_i <= val_n do {
ref_x := val_x * val_i;
ref_i := val_i + 1
};
ref_n := val_x
end
No expressive power has been gained with this more convenient notation: the original program is regained by replacing names by their definiens and eliminating the block.
A next step is to parameterize named entities, and a last step is to allow declarations to occur not just globally but in each syntactic category.
I learned very early the difference betweenknowing the name of somethingand knowing something.
Analyzing the resulting programming language, we can observe that most of the named and parameterized abstractions of syntactic units correspond to known concepts in programming languages:
Also, local declarations pave the way to objects.
Re2visiting the example above, here is a more usual way to compute the factorial of a given number (here: 5) in the final BNF, spreading a little bit of syntactic sugar:
block constant input = 5
var n = input
var i = 1
var x = 1
in while i <= n do {
x := x * i;
i := i + 1
};
n := x
end
Again, no expressive power has been gained with this more convenient notation: the original program is regained by replacing names by their definiens and eliminating the block.
These abstractions (alias, constant, variable, etc.) determine the taxonomy of programming languages: languages whose main syntactic unit is the expression are functional languages; languages whose main syntactic unit is the command are procedural languages (among imperative languages); languages whose main syntactic unit is the declaration are modular languages; and languages whose main syntactic unit is the type are class-based languages (among object-oriented languages). All these concepts were latent in the prototypical, not very expressive imperative language we started with.
A programming language is low levelwhen its programs require attention to the irrelevant.
Let us paraphrase George Orwell again, with a mix of Alan Turing and John McCarthy: in the programming-language landscape, all languages are expressively equal; however, some are more convenient than others.
We are thus led to tune the opening sentence of the lecture (“A programming language is a notation to express computations.”) into the following value judgment: a good programming language is a convenient and expressive notation for a given notion of computation.
Created [23 Oct 2025]