Plankalkül

Plankalkül
Paradigm	Procedural
Designed by	Konrad Zuse
First appeared	1948; 76 years ago – concept first published
Major implementations
	Plankalkül-Compiler by the FU Berlin in 2000
Influenced by
	Begriffsschrift
Influenced
	Superplan by Heinz Rutishauser, ; ALGOL 58

Plankalkül (German pronunciation: [ˈplaːnkalkyːl]) 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.

Kalkül 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.^[3]

History of programming

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).^[4] To describe logical circuits, Zuse invented his own diagram and notation system, which he called "combinatorics of conditionals" (Template:Lang-de). After finishing the Z1 in 1938, Zuse discovered that the calculus he had independently devised already existed and was known as propositional calculus.^[5] 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^[6]). In May 1939 he described his plans for the development of what would become Plankalkül.^[4] He wrote the following in his notebook:

Seit etwa einem halben Jahr allmähliches Einführen in die formale Logik. Viele meiner früheren Gedanken habe ich dort wiedergefunden. (Bedingungskombinatorik = Aussagenlogik; Lehre von den Intervallen = Gebietenkalkül). Ich plane jetzt die Aufsetzung des 'Plankalküls'. Hierzu sind eine Reihe von Begriffen zu klären.

Almost half a year of gradual introduction into formal logic. I rediscovered there lots of my previous thoughts. (combinatorics of conditionals = propositional calculus; study of intervals = lattice theory). Now I plan creation of "Calculus of plans". There are series of concepts needed to clarify for this.

—Konrad Zuse's notebook^[5]

While working on his doctoral dissertation, Zuse developed the first known formal system of algorithm notation^[7] capable of handling branches and loops.^[8]^[9] In 1942 he began writing a chess program in Plankalkül.^[10] In 1944, Zuse met with the German logician and philosopher Heinrich Scholz, who expressed appreciation for Zuse's utilization of logical calculus.^[11] In 1945, Zuse described Plankalkül in an unpublished book.^[12] The collapse of Nazi Germany, however, prevented him from submitting his manuscript.^[8]

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.^[13]

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^[14] (part of Bad Hindelang).

The very first attempt to devise an algorithmic language was undertaken in 1948 by K. Zuse. His notation was quite general, but the proposal never attained the consideration it deserved.
— Heinz Rutishauser, creator of ALGOL

Unable to continue building computers – which was also forbidden by the Allied Powers^[15] – Zuse devoted his time to the development of a higher-level programming model and language.^[8] In 1948 he published a paper in the Archiv der Mathematik and presented at the Annual Meeting of the GAMM.^[16] His work failed to attract much attention.^{[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."^{[citation needed]} He expressed disappointment that the designers of ALGOL 58 never acknowledged the influence of Plankalkül on their own work.^[8]^[17]

Plankalkül was more comprehensively published ^[vague] in 1972. The first compiler was implemented by Joachim Hohmann in his 1975 dissertation.^[18] Other independent implementations followed in 1998^[19] and 2000 at the Free University of Berlin.^[20]

Description

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 (verallgemeinerter Graph), which can be used to represent geometrical structures.^[21]

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:^[22]

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 types

The only primitive data type in the Plankalkül is a single bit or boolean (Template:Lang-de – yes-no value in Zuse's terminology). It is denoted by the identifier $S0$ . All the further data types are composite, and build up from primitive by means of "arrays" and "records".^[23]

So, a sequence of eight bits (which in modern computing could be regarded as byte) is denoted by $8\times S0$ , and boolean matrix of size $m$ by $n$ is described by $m\times n\times S0$ . There also exists a shortened notation, so one could write $S1\cdot n$ instead of $n\times S0$ .^[23]

Type $S0$ could have two possible values $0$ and $L$ . 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.^[23]

Record of two components $\sigma$ and $\tau$ is written as $(\sigma ,\tau )$ .^[23]

Type (Template:Lang-de) in Plankalkül consists of 3 elements: structured value (Template:Lang-de), pragmatic meaning (Template:Lang-de) and possible restriction on possible values (Template:Lang-de).^[23] User defined types are identified by letter A with number, like $A1$ – first user defined type.

Examples

Zuse used a lot of examples from chess theory:^[24]

$A1$	$S1\cdot 3$	Coordinate of chess board (it has size 8x8 so 3 bits are just enough)
$A2$	$2\times A1$	square of the board (for example L00, 00L denotes e2 in algebraic notation)
$A3$	$S1\cdot 4$	piece (for example, 00L0 — white king)
$A4$	$(A2,A3)$	piece on a board (for example L00, 00L; 00L0 — white king on e2)
$A5$	$64\times A3$	board (pieces positions, describes which piece each of 64 squares contains)
$A10$	$(A5,S0,S1\cdot 4,A2)$	game state ( $A5$ — board, $S0$ — player to move, $S1\cdot 4$ — possibility of castling (2 for white and 2 for black), $A2$ — information about cell on which en passant move is possible

Identifiers

Identifiers are alphanumeric characters with a number.^[23] There are the following kinds of identifiers for variables:^[25]

Input values (Template:Lang-de) — marked with a letter V.
Intermediate, temporary values (Template:Lang-de) — marked with a letter Z.
Constants (Template:Lang-de) — marked with a letter С.
Output values (Template:Lang-de) — marked with a letter R.

Particular variable of some kind is identified by number, written under the kind.^[23] For example:

{\begin{matrix}V\\0\end{matrix}}

,

{\begin{matrix}Z\\2\end{matrix}}

,

{\begin{matrix}C\\31\end{matrix}}

etc.

Programs and subprograms are marked with a letter P, followed by a program (and optionally a subprogram) number. For example $P13$ , $P5\cdot 7$ .^[23]

Output value of program $P13$ saved there in variable ${\begin{matrix}R\\0\end{matrix}}$ is available for other subprograms under the identifier ${\begin{matrix}R17\\0\end{matrix}}$ , and reading value of that variable also means executing related subprogram.^[24]

Accessing elements by index

Plankalkül allows access for separate elements of variable by using "component index" (Template:Lang-de). When, for example, program receives input in variable ${\begin{matrix}V\\0\end{matrix}}$ of type $A10$ (game state), then ${\begin{matrix}V\\0\\0\end{matrix}}$ — gives board state, ${\begin{matrix}V\\0\\0\cdot i\end{matrix}}$ — piece on square number i, and ${\begin{matrix}V\\0\\0\cdot i\cdot j\end{matrix}}$ bit number j of that piece.^[24]

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 syntax

Because indexes of variables are written vertically, each Plankalkül instruction requires multiple rows to write down.

First row contains variable kind, then variable number marked with letter V (Template:Lang-de), then indexes of variable subcomponents marked with K (Template:Lang-de), and then (Template:Lang-de) marked with S, which describes variable type. Type is not required, but Zuse notes that this helps with reading and understanding the program.^[26]

In the line $S$ types $S0$ and $S1$ could be shortened to $0$ and $1$ . ^[26]

Examples:

${\begin{array}{r\|l}&V\\V&3\\K&\\S&m\times 2\times 1\cdot n\end{array}}$	variable V3 — list of $m$ pairs of values of type $S1\cdot n$
${\begin{array}{r\|l}&V\\V&3\\S&m\times 2\times 1\cdot n\end{array}}$	Row K could be skipped when it is empty. Therefore, this expression means the same as above.
${\begin{array}{r\|l}&V\\V&3\\K&i\cdot 0\cdot 7\\S&0\end{array}}$	Value of eights bit (index 7), of first (index 0) pair, of і-th element of variable V3, has boolean type ( $S0$ ).

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:

Z5-th element of variable V3. Equivalent to expression V3[Z5] in many modern programming languages.^[26]

Assignment operation

Zuse introduced in his calculus an assignment operator, unknown in mathematics before him. He marked it with « $\Rightarrow$ », and called it yields-sign (Template:Lang-de). Use of concept of assignment is one of the key differences between math and computer science.^[27]

Zuse wrote that expression:

{\begin{array}{r|lll}&Z+1&\Rightarrow &Z\\V&1&&1\\\end{array}}

is analogous to more traditional mathematical equation:

{\begin{array}{r|lll}&Z+1&=&Z\\V&1&&1\\K&i&&i+1\\\end{array}}

There are claims that Konrad Zuse initially used the glyph as a sign for assignment, and started to use $\Rightarrow$ under the influence of Heinz Rutishauser.^[26] Knuth and Pardo believe that Zuse always wrote $\Rightarrow$ , and that was introduced by publishers of «Über den allgemeinen Plankalkül als Mittel zur Formulierung schematisch-kombinativer Aufgaben» in 1948.^[27] In the ALGOL 58 conference in Zurich, European participants proposed to use for assignment character introduced by Zuse, but the American delegation insisted on :=.^[26]

The variable that stores the result of an assignment (l-value) is written to the right side of assignment operator.^[27] First assignment to the variable is considered to be a declaration.^[26]

The left side of assignment operator is used for expression (Template:Lang-de), that defines which value will be assigned to variable. Expressions could use arithmetic operators, boolean operators, and comparison operators ( $=,\neq ,\leq$ etc.).^[28]

Exponentiation operation is written similarly to the indexing operation - using lines in 2d notation:^[29]

Control flow

Boolean values were represented as integers with FALSE=0 and TRUE=1. Conditional control flow took the form of a guarded statement A -> B, which executed the block B if A was true. There was also an iteration operator, of the form W { A -> X; B -> Y} which repeats until all guards are false. ^[30]

Terminology

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.^[31]

Example

The original notation was two dimensional.^{[clarification needed]} 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

Notes

^ "Early Programming Languages / CS208e: Great Ideas in Computer Science" (PDF).
^ Rojas, Raúl; Hashagen, Ulf (2002). The First Computers: History and Architectures. MIT Press. p. 292. ISBN 978-0262681377. Retrieved October 25, 2013.
^ Hector Zenil (ed.), 2012. A Computable Universe: Understanding and Exploring Nature As Computation with a Foreword by Sir Roger Penrose. Singapore: World Scientific Publishing Company. Page 791.
^ ^a ^b Hans Dieter Hellige, ed. (2004). Geschichten der Informatik. Visionen, Paradigmen, Leitmotive (in German). Berlin: Springer. pp. 113n 152, 216. ISBN 978-3-540-00217-8.
^ ^a ^b Rojas et al. 2004, p. 3.
^ "Why is propositional logic not Turing complete?".
^ Knuth & Pardo 1976, p. 9
^ ^a ^b ^c ^d Giloi 1997
^ Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlin, Springer 2004, ISBN 3-540-00217-0. p. 56.
^ Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlin, Springer 2004, ISBN 3-540-00217-0. p. 216,217.
^ Hartmut Petzold,Moderne Rechenkünstler. Die Industrialisierung der Rechentechnik in Deutschland. München. C.H. Beck Verlag 1992
^ (full text of the 1945 manuscript)
^ Rojas et al. 2000, p. 3.
^ Knuth & Pardo 1976, p. 8
^ Prof. Wolfgang Coy: Was ist Informatik? Zur Entstehung des Faches an den deutschen Universitäten, in: Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlin, Springer 2004, ISBN 3-540-00217-0. p. 474.
^ Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlin, Springer 2004, ISBN 3-540-00217-0. p. 89.
^ Knuth & Pardo 1976, p. 15
^ Joachim Hohmann: Der Plankalkül im Vergleich mit algorithmischen Sprachen. Reihe Informatik und Operations Research, S. Toeche-Mittler Verlag, Darmstadt 1979, ISBN 3-87820-028-5.
^ Description of Plankalkül-Compiler by Wolfgang Mauerer
^ Rojas et al. 2000, p. 2.
^ Prof. Wolfgang Giloi [de]: Konrad Zuses Plankalkül als Vorläufer moderner Programmiermodelle, November 1990
^ Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlin, Springer 2004, ISBN 3-540-00217-0. p. 217.
^ ^a ^b ^c ^d ^e ^f ^g ^h Bauer & Wössner 1972, p. 679.
^ ^a ^b ^c Bauer & Wössner 1972, p. 680.
^ Zuse 1945, p. 10.
^ ^a ^b ^c ^d ^e ^f Bauer & Wössner 1972, p. 681.
^ ^a ^b ^c Knuth & Pardo 1976, p. 14.
^ Bauer & Wössner 1972, p. 682.
^ Zuse 1945, p. 45.
^ Rojas, Raúl (2001). "Plankalkül" (PDF). Encyclopedia of computers and computer history. Chicago London: Fitzroy Dearborn Publ. p. 634. ISBN 1579582354. Retrieved 26 May 2023.
^ Hellige, Hans Dieter, Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlin, Springer 2004, ISBN 3-540-00217-0. pp. 45, 104, 105

References

Giloi, Wolfgang [in German] (1997). "Konrad Zuse's Plankalkül: The First High-Level "non von Neumann" Programming Language". IEEE Annals of the History of Computing. 19 (2): 17–24. doi:10.1109/85.586068.
Knuth, Donald Ervin; Pardo, Luis Trabb (1976), The Early Development of Programming Languages (PDF), Stanford University, Computer Science Department, archived from the original (PDF) on 2017-09-12, retrieved 2017-12-28
Zuse, Konrad (1943), "Ansätze einer Theorie des allgemeinen Rechnens unter besonderer Berücksichtigung des Aussagenkalküls und dessen Anwendung auf Relaisschaltungen", (i.e. Inception of a universal theory of computation with special consideration of the propositional calculus and its application to relay circuits.) unpublished manuscript, Zuse Papers 045/018.
Zuse, Konrad (1948/49). "Über den allgemeinen Plankalkül als Mittel zur Formulierung schematisch-kombinativer Aufgaben". Arch. Math. 1, pp. 441–449, 1948/49.
Zuse, Konrad (1972). "Der Plankalkül". Gesellschaft für Mathematik und Datenverarbeitung. Nr. 63, BMBW - GMD - 63, 1972.
Bauer, Friedrich L.; Wössner, Hans (1972). "The "Plankalkül" of Konrad Zuse: A Forerunner of Today's Programming Languages" (PDF). Communications of the ACM. 15 (7): 678–685. doi:10.1145/361454.361515. S2CID 17681101. Archived from the original (pdf) on 2009-02-20.(HTML version)
Rojas, Raúl; Göktekin, Cüneyt; Friedland, Gerald; Krüger, Mike (2000). Plankalkül: The First High-Level Programming Language and its Implementation (PDF). Archived from the original on 2006-05-01.
Rojas, Raúl; Göktekin, Cüneyt; Friedland, Gerald; Krüger, Mike; Scharf, Ludmila (2004). Konrad Zuses Plankalkül – Seine Genese und eine moderne Implementierung (PDF). pp. 215–235. doi:10.1007/978-3-642-18631-8_9. ISBN 978-3-642-62208-3. Archived from the original (PDF) on 2006-05-01.

External links

The "Plankalkül" of Konrad Zuse: A Forerunner of Today's Programming Languages by Friedrich L. Bauer (alternative source)
Rojas, Raúl, et al. (2000). "Plankalkül: The First High-Level Programming Language and its Implementation". Institut für Informatik, Freie Universität Berlin, Technical Report B-3/2000. (full text)(archived)
Mauerer, Wolfgang (2016-06-03). "Der Plankalkül von Konrad Zuse" (in German). Implementation in German. Archived from the original on 2016-06-03. Retrieved 2017-10-03.
"Plankalkül". Konrad Zuse Internet Archive. Archived page with Plankalkül java applets (non functioning) and several documents (German/English). 2014-08-21. Archived from the original on 2014-08-21. Retrieved 2017-10-04.{{cite web}}: CS1 maint: others (link)
Bram Bruines: Plankalkul(2010) - Plankalkül described in a formal way

[cs208e-1] "Early Programming Languages / CS208e: Great Ideas in Computer Science" (PDF).

[2] Rojas, Raúl; Hashagen, Ulf (2002). The First Computers: History and Architectures. MIT Press. p. 292. ISBN 978-0262681377. Retrieved October 25, 2013.

[3] Hector Zenil (ed.), 2012. A Computable Universe: Understanding and Exploring Nature As Computation with a Foreword by Sir Roger Penrose. Singapore: World Scientific Publishing Company. Page 791.

[hellige-springer-4] Hans Dieter Hellige, ed. (2004). Geschichten der Informatik. Visionen, Paradigmen, Leitmotive (in German). Berlin: Springer. pp. 113n 152, 216. ISBN 978-3-540-00217-8.

[FOOTNOTERojasGöktekinFriedlandKrüger20043-5] Rojas et al. 2004, p. 3.

[6] "Why is propositional logic not Turing complete?".

[Knuth76p9-7] Knuth & Pardo 1976, p. 9

[Giloi97p18-8] Giloi 1997

[9] Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlin, Springer 2004, ISBN 3-540-00217-0. p. 56.

[10] Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlin, Springer 2004, ISBN 3-540-00217-0. p. 216,217.

[11] Hartmut Petzold,Moderne Rechenkünstler. Die Industrialisierung der Rechentechnik in Deutschland. München. C.H. Beck Verlag 1992

[12] (full text of the 1945 manuscript)

[FOOTNOTERojasGöktekinFriedlandKrüger20003-13] Rojas et al. 2000, p. 3.

[Knuth76p8-14] Knuth & Pardo 1976, p. 8

[15] Prof. Wolfgang Coy: Was ist Informatik? Zur Entstehung des Faches an den deutschen Universitäten, in: Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlin, Springer 2004, ISBN 3-540-00217-0. p. 474.

[16] Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlin, Springer 2004, ISBN 3-540-00217-0. p. 89.

[Knuth76p15-17] Knuth & Pardo 1976, p. 15

[18] Joachim Hohmann: Der Plankalkül im Vergleich mit algorithmischen Sprachen. Reihe Informatik und Operations Research, S. Toeche-Mittler Verlag, Darmstadt 1979, ISBN 3-87820-028-5.

[19] Description of Plankalkül-Compiler by Wolfgang Mauerer

[FOOTNOTERojasGöktekinFriedlandKrüger20002-20] Rojas et al. 2000, p. 2.

[21] Prof. Wolfgang Giloi [de]: Konrad Zuses Plankalkül als Vorläufer moderner Programmiermodelle, November 1990

[22] Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlin, Springer 2004, ISBN 3-540-00217-0. p. 217.

[FOOTNOTEBauerWössner1972679-23] ^ ^a ^b ^c ^d ^e ^f ^g ^h Bauer & Wössner 1972, p. 679.

[FOOTNOTEBauerWössner1972680-24] Bauer & Wössner 1972, p. 680.

[FOOTNOTEZuse194510-25] Zuse 1945, p. 10.

[FOOTNOTEBauerWössner1972681-26] ^ ^a ^b ^c ^d ^e ^f Bauer & Wössner 1972, p. 681.

[FOOTNOTEKnuthPardo197614-27] Knuth & Pardo 1976, p. 14.

[FOOTNOTEBauerWössner1972682-28] Bauer & Wössner 1972, p. 682.

[FOOTNOTEZuse194545-29] Zuse 1945, p. 45.

[30] Rojas, Raúl (2001). "Plankalkül" (PDF). Encyclopedia of computers and computer history. Chicago London: Fitzroy Dearborn Publ. p. 634. ISBN 1579582354. Retrieved 26 May 2023.

[31] Hellige, Hans Dieter, Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlin, Springer 2004, ISBN 3-540-00217-0. pp. 45, 104, 105

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]