Template:Short description Template:Distinguish Template:Use dmy dates Template:Use list-defined references Template:Infobox programming language Plankalkül ({{#invoke:IPA|main}}) is a programming language designed for engineering purposes by Konrad Zuse between 1942 and 1945. It was the first high-level programming language to be designed for a computer. Zuse never implemented Plankalkül on any of his Z-series machines.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
Kalkül (from Latin calculus) is the German term for a formal system—as in Hilbert-Kalkül, the original name for the Hilbert-style deduction system—so Plankalkül refers to a formal system for planning.<ref name="Zenil_2012"/>
History of programmingEdit
In the domain of creating computing machines, Zuse was self-taught, and developed them without knowledge about other mechanical computing machines that existed already – although later on (building the Z3) being inspired by Hilbert's and Ackermann's book on elementary mathematical logic (see Principles of Mathematical Logic).<ref name="Hellige_2004"/>Template:Rp To describe logical circuits, Zuse invented his own diagram and notation system, which he called "combinatorics of conditionals" (Template:Langx). After finishing the Z1 in 1938, Zuse discovered that the calculus he had independently devised already existed and was known as propositional calculus.<ref name="Rojas-Göktekin-Friedland-Krüger-Kuniß-Langmack_2004"/>Template:Rp What Zuse had in mind, however, needed to be much more powerful (propositional calculus is not Turing-complete and is not able to describe even simple arithmetic calculations<ref name="Turing_2013"/>). In May 1939, he described his plans for the development of what would become Plankalkül.<ref name="Hellige_2004"/>Template:Rp He wrote the following in his notebook:
While working on his doctoral dissertation, Zuse developed the first known formal system of algorithm notation<ref name="Knuth-Pardo_1976"/>Template:Rp capable of handling branches and loops.<ref name="Giloi_1997"/>Template:Rp<ref name="Hellige_2004"/>Template:Rp In 1942 he began writing a chess program in Plankalkül.<ref name="Hellige_2004"/>Template:Rp In 1944, Zuse met with the German logician and philosopher Heinrich Scholz, who expressed appreciation for Zuse's utilization of logical calculus.<ref name="Petzold_1992"/> In 1945, Zuse described Plankalkül in an unpublished book.<ref name="Zuse_1945"/> The collapse of Nazi Germany, however, prevented him from submitting his manuscript.<ref name="Giloi_1997"/>Template:Rp
At that time the only two working computers in the world were ENIAC and Harvard Mark I, neither of which used a compiler, and ENIAC needed to be reprogrammed for each task by changing how the wires were connected.<ref name="Rojas-Göktekin-Friedland-Krüger-Kuniß-Langmack_2004"/>Template:Rp
Although most of his computers were destroyed by Allied bombs, Zuse was able to rescue one machine, the Z4, and move it to the Alpine village of Hinterstein<ref name="Knuth-Pardo_1976"/>Template:Rp (part of Bad Hindelang).
Unable to continue building computers – which was also forbidden by the Allied Powers<ref name="Coy_2004"/> – Zuse devoted his time to the development of a higher-level programming model and language.<ref name="Giloi_1997"/>Template:Rp In 1948, he published a paper in the Archiv der Mathematik and presented at the Annual Meeting of the GAMM.<ref name="Hellige_2004"/>Template:Rp His work failed to attract much attention.Template:Citation needed In a 1957 lecture, Zuse expressed his hope that Plankalkül, "after some time as a Sleeping Beauty, will yet come to life."<ref name="Rojas-Göktekin-Friedland-Krüger-Kuniß-Langmack_2004"/>Template:Rp He expressed disappointment that the designers of ALGOL 58 never acknowledged the influence of Plankalkül on their own work.<ref name="Giloi_1997"/>Template:Rp<ref name="Knuth-Pardo_1976"/>Template:Rp
Plankalkül was republished with commentary in 1972.<ref name="Zuse_1972"/> The first compiler for Plankalkül was implemented by Joachim Hohmann in his 1975 dissertation.<ref name="Hohmann_1979"/> Other independent implementations followed in 1998<ref name="Mauerer_2016"/> and 2000 at the Free University of Berlin.<ref name="Rojas-Göktekin-Friedland-Krüger-Kuniß-Langmack_2004"/>Template:Rp
DescriptionEdit
Plankalkül has drawn comparisons to the language APL, and to relational algebra. It includes assignment statements, subroutines, conditional statements, iteration, floating-point arithmetic, arrays, hierarchical record structures, assertions, exception handling, and other advanced features such as goal-directed execution. The Plankalkül provides a data structure called generalized graph ({{#invoke:Lang|lang}}), which can be used to represent geometrical structures.<ref name="Giloi_1990"/>
Many features of the Plankalkül reappear in later programming languages; an exception is its idiosyncratic two-dimensional notation using multiple lines.
Some features of the Plankalkül:<ref name="Hellige_2004"/>Template:Rp
- only local variables
- functions do not support recursion
- only supports call by value
- composite types are arrays and tuples
- contains conditional expressions
- contains a for loop and a while loop
- no goto
Data typesEdit
The only primitive data type in the Plankalkül is a single bit or Boolean (Template:Langx – yes-no value in Zuse's terminology). It is denoted by the identifier <math>S0</math>. All the further data types are composite, and build up from primitive by means of "arrays" and "records".<ref name="Bauer-Wössner_1972"/>Template:Rp
So, a sequence of eight bits (which in modern computing could be regarded as byte) is denoted by <math>8 \times S0</math>, and Boolean matrix of size <math>m</math> by <math>n</math> is described by <math>m \times n \times S0</math>. There also exists a shortened notation, so one could write <math>S1 \cdot n</math> instead of <math>n \times S0</math>.<ref name="Bauer-Wössner_1972"/>Template:Rp
Type <math>S0</math> could have two possible values <math>0</math> and <math>L</math>. So 4-bit sequence could be written like L00L, but in cases where such a sequence represents a number, the programmer could use the decimal representation 9.<ref name="Bauer-Wössner_1972"/>Template:Rp
Record of two components <math>\sigma</math> and <math>\tau</math> is written as <math>(\sigma, \tau)</math>.<ref name="Bauer-Wössner_1972"/>Template:Rp
Type (Template:Langx) in Plankalkül consists of 3 elements: structured value (Template:Langx), pragmatic meaning (Template:Langx) and possible restriction on possible values (Template:Langx).<ref name="Bauer-Wössner_1972"/>Template:Rp User defined types are identified by letter A with number, like <math>A1</math> – first user defined type.
ExamplesEdit
Zuse used a lot of examples from chess theory:<ref name="Bauer-Wössner_1972"/>Template:Rp
| <math>A1</math> | <math>S1 \cdot 3</math> | Coordinate of chess board (it has size 8x8 so 3 bits are just enough) |
| <math>A2</math> | <math>2 \times A1</math> | square of the board (for example L00, 00L denotes e2 in algebraic notation) |
| <math>A3</math> | <math>S1 \cdot 4</math> | piece (for example, 00L0 — white king) |
| <math>A4</math> | <math>(A2, A3)</math> | piece on a board (for example L00, 00L; 00L0 — white king on e2) |
| <math>A5</math> | <math>64 \times A3</math> | board (pieces positions, describes which piece each of 64 squares contains) |
| <math>A10</math> | <math>(A5, S0, S1 \cdot 4, A2)</math> | game state (<math>A5</math> — board, <math>S0</math> — player to move, <math>S1 \cdot 4</math> — possibility of castling (2 for white and 2 for black), <math>A2</math> — information about cell on which en passant move is possible |
IdentifiersEdit
Identifiers are alphanumeric characters with a number.<ref name="Bauer-Wössner_1972"/>Template:Rp There are the following kinds of identifiers for variables:<ref name="Zuse_1945"/>Template:Rp
- Input values (Template:Langx) — marked with a letter V.
- Intermediate, temporary values (Template:Langx) — marked with a letter Z.
- Constants (Template:Langx) — marked with a letter С.
- Output values (Template:Langx) — marked with a letter R.
Particular variable of some kind is identified by number, written under the kind.<ref name="Bauer-Wössner_1972"/>Template:Rp For example:
- <math>\begin{matrix} V \\ 0 \end{matrix}</math>, <math>\begin{matrix} Z \\ 2 \end{matrix}</math>, <math>\begin{matrix} C \\ 31 \end{matrix}</math> etc.
Programs and subprograms are marked with a letter P, followed by a program (and optionally a subprogram) number. For example <math>P13</math>, <math>P5 \cdot 7</math>.<ref name="Bauer-Wössner_1972"/>Template:Rp
Output value of program <math>P13</math> saved there in variable <math>\begin{matrix} R \\ 0 \end{matrix}</math> is available for other subprograms under the identifier <math>\begin{matrix} R17 \\ 0 \end{matrix}</math>, and reading value of that variable also means executing related subprogram.<ref name="Bauer-Wössner_1972"/>Template:Rp
Accessing elements by indexEdit
Plankalkül allows access for separate elements of variable by using "component index" (Template:Langx). When, for example, program receives input in variable <math>\begin{matrix} V \\ 0 \end{matrix}</math> of type <math>A10</math> (game state), then <math>\begin{matrix} V \\ 0 \\ 0 \end{matrix}</math> — gives board state, <math>\begin{matrix} V \\ 0 \\ 0 \cdot i \end{matrix}</math> — piece on square number i, and <math>\begin{matrix} V \\ 0 \\ 0 \cdot i \cdot j \end{matrix}</math> bit number j of that piece.<ref name="Bauer-Wössner_1972"/>Template:Rp
In modern programming languages, that would be described by notation similar to V0[0], V0[0][i], V0[0][i][j] (although to access a single bit in modern programming languages a bitmask is typically used).
Two-dimensional syntaxEdit
Because indexes of variables are written vertically, each Plankalkül instruction requires multiple rows to write down.Template:Citation needed
First row contains variable kind, then variable number marked with letter V (Template:Langx), then indexes of variable subcomponents marked with K (Template:Langx), and then (Template:Langx) marked with S, which describes variable type. Type is not required, but Zuse notes that this helps with reading and understanding the program.<ref name="Bauer-Wössner_1972"/>Template:Rp
In the line <math>S</math> types <math>S0</math> and <math>S1</math> could be shortened to <math>0</math> and <math>1</math>.<ref name="Bauer-Wössner_1972"/>Template:Rp
Examples:
l}
& V \\
V & 3 \\
K & \\
S & m \times 2 \times 1 \cdot n
\end{array}</math>
|
variable V3 — list of <math>m</math> pairs of values of type <math>S1 \cdot n</math> |
l}
& V \\
V & 3 \\
S & m \times 2 \times 1 \cdot n
\end{array}</math>
|
Row K could be skipped when it is empty. Therefore, this expression means the same as above. |
l}
& V \\
V & 3 \\
K & i \cdot 0 \cdot 7 \\
S & 0
\end{array}</math>
|
Value of eights bit (index 7), of first (index 0) pair, of і-th element of variable V3, has Boolean type (<math>S0</math>). |
Indexes could be not only constants. Variables could be used as indexes for other variables, and that is marked with a line, which shows in which component index would value of variable be used:
| Using variable as index for other variable, in 2d Plankalül notation | Z5-th element of variable V3. Equivalent to expression V3[Z5] in many modern programming languages.<ref name="Bauer-Wössner_1972"/>Template:Rp
|
Assignment operationEdit
Zuse introduced in his calculus an assignment operator, unknown in mathematics before him. He marked it with «<math>\Rightarrow</math>», and called it yields-sign (Template:Langx). Use of concept of assignment is one of the key differences between mathematics and computer science.<ref name="Knuth-Pardo_1976"/>Template:Rp
Zuse wrote that the expression:
- <math>\begin{array}{r|lll}
& Z + 1 & \Rightarrow & Z\\
V & 1 & & 1\\
\end{array}</math>
is analogous to the more traditional mathematical equation:
- <math>\begin{array}{r|lll}
& Z + 1 & = & Z\\
V & 1 & & 1\\
K & i & & i + 1\\
\end{array}</math>
There are claims that Konrad Zuse initially used the glyph File:Ergibt-Zeichen.png as a sign for assignment, and started to use <math>\Rightarrow</math> under the influence of Heinz Rutishauser.<ref name="Bauer-Wössner_1972"/>Template:Rp Knuth and Pardo believe that Zuse always wrote <math>\Rightarrow</math>, and that File:Ergibt-Zeichen.png was introduced by publishers of «Über den allgemeinen Plankalkül als Mittel zur Formulierung schematisch-kombinativer Aufgaben» in 1948.<ref name="Knuth-Pardo_1976"/>Template:Rp In the ALGOL 58 conference in Zürich, European participants proposed to use the assignment character introduced by Zuse, but the American delegation insisted on :=.<ref name="Bauer-Wössner_1972"/>Template:Rp
The variable that stores the result of an assignment (l-value) is written to the right side of assignment operator.<ref name="Knuth-Pardo_1976"/>Template:Rp The first assignment to the variable is considered to be a declaration.<ref name="Bauer-Wössner_1972"/>Template:Rp
The left side of assignment operator is used for an expression (Template:Langx), that defines which value will be assigned to the variable. Expressions could use arithmetic operators, Boolean operators, and comparison operators (<math>=, \neq, \leq</math> etc.).<ref name="Bauer-Wössner_1972"/>Template:Rp
The exponentiation operation is written similarly to the indexing operation - using lines in the two-dimensional notation:<ref name="Zuse_1945"/>Template:Rp
Exponentiation notation in Plankalkül
Control flowEdit
Boolean values were represented as integers with <syntaxhighlight lang="text" class="" style="" inline="1">FALSE=0</syntaxhighlight> and <syntaxhighlight lang="text" class="" style="" inline="1">TRUE=1</syntaxhighlight>. Conditional control flow took the form of a guarded statement <syntaxhighlight lang="text" class="" style="" inline="1">A -> B</syntaxhighlight>, which executed the block <syntaxhighlight lang="text" class="" style="" inline="1">B</syntaxhighlight> if <syntaxhighlight lang="text" class="" style="" inline="1">A</syntaxhighlight> was true. There was also an iteration operator, of the form <syntaxhighlight lang="text" class="" style="" inline="1">W { A -> X; B -> Y </syntaxhighlight>} which repeats until all guards are false.<ref name="Rojas_2001"/>
TerminologyEdit
Zuse called a single program a Rechenplan ("computation plan"). He envisioned what he called a Planfertigungsgerät ("plan assembly device"), which would automatically translate the mathematical formulation of a program into machine-readable punched film stock, something today would be called a translator or compiler.<ref name="Hellige_2004"/>Template:Rp
ExampleEdit
The original notation was two-dimensional, i.e. the indentation and thus spatial relation of different terminal symbols mattered in regard to the semantics spanning multiple lines. For a later implementation in the 1990s, a linear notation was developed.
The following example defines a function max3 (in a linear transcription) that calculates the maximum of three variables:
P1 max3 (V0[:8.0],V1[:8.0],V2[:8.0]) → R0[:8.0] max(V0[:8.0],V1[:8.0]) → Z1[:8.0] max(Z1[:8.0],V2[:8.0]) → R0[:8.0] END P2 max (V0[:8.0],V1[:8.0]) → R0[:8.0] V0[:8.0] → Z1[:8.0] (Z1[:8.0] < V1[:8.0]) → V1[:8.0] → Z1[:8.0] Z1[:8.0] → R0[:8.0] END
See alsoEdit
ReferencesEdit
Further readingEdit
- Template:Cite book
- Template:Cite journal (9 pages)
- Template:Cite book[1] (22 pages)
- {{#invoke:citation/CS1|citation
|CitationClass=web }} (24 pages)
External linksEdit
- {{#invoke:citation/CS1|citation
|CitationClass=web }} (NB. Plankalkül Java applets and documents.)