Plankalkül

Plankalkül

编程范型	过程式
設計者	Konrad Zuse
发行时间	1948年​（1948） – 概念首次发表
主要實作產品
Plankalkül-Compiler（柏林自由大学于2000年实现）
影響語言
Superplan, ALGOL 58

Plankalkül（德语发音：[ˈplaːnkalkyːl]）是康拉德·楚澤在1942至1945年间，出于工程目的而设计的一种编程语言。它是第一种为计算机设计的高级编程语言。

“Kalkül”在德语中意为形式系统。如希尔伯特演绎系统原本名为“Hilbert-Kalkül”那样，“Plankalkül”指用于规划（planning）的形式系统。

描述

Zuse在1960年代的照片

Zuse在1945年基于继电器制造的Z4计算机

Plankalkül可比较于APL和关系代数。它包括赋值语句、子例程、条件语句、迭代、浮点算术、阵列、层级记录结构、断言、例外处理和其他高级特征比如目标导向执行。Plankalkül提供了叫做“广义图”（verallgemeinerter Graph）的数据结构，它可以被用来表示几何结构。

Plankalkül的很多特征重现于后来的编程语言之中；一个例外是其特质性的使用占据多行的表示法。

Plankalkül的一些特征：

• 只有局部变量，
• 函数不支持递归，
• 只支持传名调用，
• 合成类型是阵列和元组，
• 包含条件表达式，
• 包含for循环和while循环，
• 没有goto。

数据类型

在Plankalkül中唯一的原始数据类型是单一的“是否值”（德語：Ja-Nein-Werte）即布尔值。它被指称为标识符 $S0$。所有进一步的数据类型都是合成的，并且从原始类型通过“阵列”和“记录”的方式建造而成。

所以8位序列（这在现代计算中被当作字节）被指称为$8\times S0$，而大小为 $m$乘$n$的布尔阵列，被描述为$m\times n\times S0$。还存在更短的表示法，可以将$n\times S0$替代为$S1\cdot n$，它叫做“n位是否值序列”（德語：n-stellige Folge von Ja-Nein-Werten）。

类型$S0$有两个可能的值$0$和$L$。所以4位序列可以写为例如$L00L$，但是在这样的一个序列表示一个数的情况下，编程者可以使用十进制表示法的$9$。

Zuse还定义了$S2$为$2\times \sigma$（或写为$2\sigma$）即有序对（德語：Angabenpaar）；$S3$为$m\times \sigma$即列表（德語：Liste），在元素数量不定时写为$\Box \times \sigma$；$S4$为$m\times 2\sigma$即有序对列表（德語：Paarliste），在元素数量不定时写为$\Box \times 2\sigma$。两个组件（component，德語：Glieder）$\sigma$和$\tau$的结构（德語：Struktur）被写为$(\sigma ,\tau )$。

Plankalkül中类型（德語：Art）构成自3个元素：结构（德語：Struktur），语用意义（德語：Typ），和可能的限制（德語：Beschränkung）。用户定义的类型被标示为字母$A$连带编号，比如$A1$，即第一个用户定义的类型。

例子

Zuse使用了来自象棋理论的很多例子：

$A1$	$S1\cdot 3$	棋盘的坐标（它的大小为$8\times 8$所以$3$位就足够了）。
$A2$	$2\times A1$	棋盘的方格（例如$L00,00L$指称代数记谱法中的e2）。
$A3$	$S1\cdot 4$	棋子（例如$00L0$指称白王）。
$A4$	$(A2,A3)$	棋盘上的棋子（例如$L00,00L;00L0$指称白王在e2中）。
$A5$	$64\times A3$	棋盘（棋子位置，描述64的方格都包含哪个棋子）。
$A10$	$(A5,S0,S1\cdot 4,A2)$	游戏状态（$A5$指称棋盘，$S0$指称行棋玩家，$S1\cdot 4$指称王车易位的可能性（$2$位给白棋$2$位给黒棋），$A2$指称关于哪个单元格有可能吃过路兵）。

标识符

标识符（德語：Bezeichnungen）是字母字符连带编号。针对变量有如下标识符种类：

• 输入值（德語：Eingabewerte, Variablen），标记以字母$V$。
• 中间值，临时值（德語：Zwischenwerte），标记以字母$Z$。
• 常值（德語：Constanten），标记以字母$C$。
• 输出值（德語：Resultatwerte），标记以字母$R$。

特定的某种变量由写在种类之下的编号来标示，例如：${\begin{smallmatrix}V\\0\end{smallmatrix}}$，${\begin{smallmatrix}Z\\2\end{smallmatrix}}$，${\begin{smallmatrix}C\\31\end{smallmatrix}}$等等。

程序和子例程都被表达为过程（德語：Rechenpläne），它被标记以字母$P$，跟随着一个程序编号（德語：Nummer），或者以点号分隔的程序组编号与程序编号。例如：$P12$、$P3\cdot 7$。

子例程$P17$的输出值保存在变量${\begin{smallmatrix}R\\0\end{smallmatrix}}$中，其他子例程能在标识符${\begin{smallmatrix}R17\\0\end{smallmatrix}}$之下获得到它，而读取这个变量的值还意味着调用有关的子例程。

按索引访问元素

Plankalkül允许使用组件（component）索引（德語：Komponenten-Index）访问变量的单独元素。例如，当一个程序接收输入于具有类型$A10$（游戏状态）的变量${\begin{smallmatrix}V\\0\end{smallmatrix}}$之中，那么${\begin{smallmatrix}V\\0\\0\end{smallmatrix}}$给出棋盘状态，${\begin{smallmatrix}V\\0\\0\cdot i\end{smallmatrix}}$给出在编号$i$方格中的棋子，而${\begin{smallmatrix}V\\0\\0\cdot i\cdot j\end{smallmatrix}}$给出这个棋子的位编号$j$。

在现代编程语言中，这可以用描述为表示法类似于V0[0]、V0[0][i]、V0[0][i][j]（尽管访问单一的位在现代编程语言中典型的使用位掩码）。

语法

由于变量的索引是垂直书写的，逻辑上一行的Plankalkül指令要求占据4或3物理行来书写。

一行包含变量种类，第二行标记以$V$（德語：Variablen-Index）包含变量编号，第三行标记以$K$（德語：Komponenten-Index）包含组件索引，而第四行标记以$S$（德語：Struktur-Index）是类型描述。类型不是必需的，但是Zuse注释到这能帮助阅读和理解程序。

在$S$行中类型$S$前缀可以去掉，例如：

$S\;\left|\;S1\cdot n\quad m\times S1\cdot n\quad S0\quad S1\quad \sigma \right.$，可以简写为$\ S\;\left|\;1\cdot n\quad m\times 1\cdot n\quad 0\quad 1\quad \sigma \right.$。

进一步的类型$A$前缀也可以去掉，例如：

$S\;\left|\;A1\quad A2\quad S0\quad A3\ \quad \sigma \right.$，可以简写为$\ A\;\left|\;1\quad 2\quad 0\quad 3\ \quad \sigma \right.$。$A0$同义于$S0$。

变量的索引的例子：

${\begin{array}{r|l}&V\\V&3\\K&\\S&m\times 2\times 1\cdot n\end{array}}$	变量${\begin{smallmatrix}V\\3\end{smallmatrix}}$，它是$m$个有序对的类型$S1\cdot n$的值的列表。
${\begin{array}{r|l}&V\\V&3\\S&m\times 2\times 1\cdot n\end{array}}$	$K$行在其为空时可以越过。因此这个表达式含义同于前者。
${\begin{array}{r|l}&V\\V&3\\K&i\cdot 0\cdot 7\\S&0\end{array}}$	变量${\begin{smallmatrix}V\\3\end{smallmatrix}}$的第$i+1$个有序对的第$1$（索引$0$）组件的第$8$（索引$7$）位，它拥有布尔类型$S0$。

索引可以不只是常值。变量可以被用作其他变量的索引，而这被标记为折线，它展示变量的值将在哪个组件索引中使用：

变量${\begin{smallmatrix}V\\3\end{smallmatrix}}$的第${\begin{smallmatrix}Z\\5\end{smallmatrix}}$个元素。等价于在很多现代语言中的表达式V3[Z5]。

赋值运算

Zuse在他的演算中介入了赋值算子，这个概念未知于他之前的数学中。他将其标记为$\Rightarrow$，并称其为产生符号（德語：Ergibt-Zeichen）。使用赋值的概念是在数学和计算机科学之间的关键差异。

例如下列表达式：

${\begin{array}{r|lll}&Z&+&1&\Rightarrow &Z\\V&1&&&&1\\S&1\cdot n&&1\cdot n&&1\cdot n\\\end{array}}$	向整数中间值${\begin{smallmatrix}Z\\1\end{smallmatrix}}$增加数量$1$。
${\begin{array}{r|lll}&(V&,&V)&\Rightarrow &R\\V&\;\,0&&1&&0\\S&\;\,\sigma &&\sigma &&2\sigma \\\end{array}}$	将值${\begin{smallmatrix}V\\0\end{smallmatrix}}$和${\begin{smallmatrix}V\\1\end{smallmatrix}}$合成为${\begin{smallmatrix}R\\0\end{smallmatrix}}$ 所指称的合成值。

有人宣称Konrad Zuse最初使用图元作为赋值的符号，并在Heinz Rutishauser的影响下开始使用$\Rightarrow$。Knuth和Pardo相信Zuse总是写为$\Rightarrow$，而是»Über den allgemeinen Plankalkül als Mittel zur Formulierung schematisch-kombinativer Aufgaben«的出版商在1948年介入的。在Zürich的ALGOL 58会议中，欧洲与会者提议使用Zuse介入的赋值符号，而美国代表团坚持采用:=。

存储赋值结果的变量（左值）被写在赋值算子的右侧。对一个变量的第一次赋值被认为是对它的初始化声明。

赋值算子的左侧被用作表达式（德語：Ausdrücke），它定义哪个值将被赋值到这个变量。表达式可以使用算术算子、布尔算子和比较算子（$=$，$\neq$，$\leq$等等）。

控制流程

布尔值被表示为整数，“否”（$\mathrm {nein}$）为$0$，而“是”（$\mathrm {ja}$）为$1$。条件控制流程采用守卫语句$\,{\mathcal {A}}{\dot {\rightarrow }}{\mathcal {X}}\,$的形式，这里的加点箭头叫做“条件符号”（德語：Bedingt-Zeichen），它指示在${\mathcal {A}}$为“是”的条件下执行块${\mathcal {X}}$。迭代算子具有如下形式：

${\begin{matrix}W\\\\\\\end{matrix}}{\begin{bmatrix}{\mathcal {A}}{\dot {\rightarrow }}{\mathcal {X}}\\{\mathcal {B}}{\dot {\rightarrow }}{\mathcal {Y}}\\\vdots \end{bmatrix}}$

这里的$W$表示“重复规划”（德語：Wiederholungsplan），它重复直到所有守卫成为“否”。

算子$\mu x(x\in l\land R(x))$和$\lambda x(x\in l\land R(x))$意图用在迭代运算之中，$\mu x$对变量$l$进行递增索引的遍历，而$\lambda x$对其进行递减索引的遍历，找出其符合特定条件$R()$的下一个（含第一个）元素$x$。典型用法是将在局部变量$x$中的符合条件元素赋值到中间变量之中，然后在用竖杠$\left|\right.$分隔出的后续语句之中，在前面语句成功找到符合条件的元素之时对此中间变量做进一步处理。

术语

Zuse称呼一个单一的程序为“计算规划”（德語：Rechenplan）。他设想其所称谓的“规划组装设备”（德語：Planfertigungsgerät），能自动的将一个程序的数学公式转换成机器可读的打孔电影胶片，这是在今天称为翻译器或编译器的某种东西。

例子

下面的例子程序计算整数的阶乘：

${\begin{aligned}&\quad P1.1\\&\;\,{\begin{array}{r}\\V\\K\\A\\\end{array}}\left|\;{\begin{array}{lll}R(V)&\Rightarrow &R\\\,\quad 0&&0\\&&\\\quad 10&&10\\\end{array}}\right.\\&\;\,{\begin{array}{r}\\V\\K\\A\\\end{array}}\left|\;{\begin{array}{lll}1&\Rightarrow &R\\&&0\\&&\\10&&10\\\end{array}}\right.\left|\;{\begin{array}{lll}V+1&\Rightarrow &Z\\0&&0\\&&\\10\;\;\;10&&10\\\end{array}}\right.\\&\;\,{\begin{array}{r}\\V\\K\\A\\\end{array}}\left|\;{\begin{array}{l}W2(Z)\\\quad \quad 0\\\\\quad \quad 10\end{array}}\left[{\begin{array}{l}i>0&{\dot {\rightarrow }}\\\\\\10\;\;10&\\\end{array}}\left[{\begin{array}{lll}R\times i&\Rightarrow &R\\0&&0\\&&\\10\;\;\;10&&10\end{array}}\right]\right]\right.\end{aligned}}$

这里的Zuse定义的用户类型$A10$表示全部整数。第一行包含“边界概要”（德語：Randauszug），它定义程序$P1.1$接受一个变元（实际参数），即叫做${\begin{smallmatrix}V\\0\end{smallmatrix}}$的一个整数，并返回叫做${\begin{smallmatrix}R\\0\end{smallmatrix}}$的一个整数。这个程序将$1$赋值到${\begin{smallmatrix}R\\0\end{smallmatrix}}$，将${\begin{smallmatrix}V\\0\end{smallmatrix}}+1$赋值到${\begin{smallmatrix}Z\\0\end{smallmatrix}}$。接着迭代算子$W2$执行重复运算，将从${\begin{smallmatrix}Z\\0\end{smallmatrix}}-1$递减至$0$的值，依次赋值到局部变量$i$，这里将大于$0$的$i$值累乘至${\begin{smallmatrix}R\\0\end{smallmatrix}}$。当重复结束之时，值${\begin{smallmatrix}R\\0\end{smallmatrix}}$就包含了变元的阶乘。

Zuse还定义了用户类型$A8$表示自然数，$A9$表示非负整数，$A11$表示非负分数，$A12$表示全部分数，$A13$表示复数。迭代算子$W0$、$W1$和$W2$接受一个非负整数$n$，$W0$只重复$n$次而不赋值局部变量，$W1$重复时将从$0$递增至$n-1$的值赋值给局部变量$i$；迭代算子$W3$、$W4$和$W5$接受两个非负整数$(n,m)$并赋值到局部变量$i$，$W3$在$n<m$时从$n$递增至$m-1$，$W4$在$n>m$时从$n$递减至$m+1$，$W5$在$n<m$时从$n$递增至$m-1$而在$n>m$时从$n$递减至$m+1$。使用$W4({\begin{smallmatrix}V\\0\end{smallmatrix}},0)$，可以省略${\begin{smallmatrix}V\\0\end{smallmatrix}}+1$的初始值设置，和$i>0$的守卫条件判断。

延伸阅读

• Zuse, Konrad. Ansätze einer Theorie des allgemeinen Rechnens unter besonderer Berücksichtigung des Aussagenkalküls und dessen Anwendung auf Relaisschaltungen [Inception of a universal theory of computation with special consideration of the propositional calculus and its application to relay circuits] (unpublished manuscript). 1943. Zuse Papers 045/018 （德语）. 
• Zuse, Konrad. 写于Hopferau bei Füssen, Germany. Über den allgemeinen Plankalkül als Mittel zur Formulierung schematisch-kombinativer Aufgaben. Archiv der Mathematik (Karlsruhe / Stuttgart / Basel, Germany: Birkhäuser Verlag). 1948-12-06, 1 (6): 441–449. ISSN 0003-889X. doi:10.1007/BF02038459. eISSN 1420-8938 （德语）.  (9 pages)
• Rojas, Raúl; Göktekin, Cüneyt; Friedland, Gerald; Krüger, Mike; Kuniß, Denis; Langmack, Olaf. Plankalkül: The First High-Level Programming Language and its Implementation (PDF). Berlin, Germany: Institut für Informatik, Freie Universität Berlin & Feinarbeit.de. February 2000. Technical Report B-3/2000. （原始内容存档于2006-05-01） （英语）. [1] (22 pages)
• Bruines, Bram. Plankalkül (PDF) (Thesis). 2010-01-08 [2023-11-02]. （原始内容存档 (PDF)于2023-11-02）.  (24 pages)

外部链接

• Plankalkül-Programme. Konrad Zuse Internet Archive. 2014-08-21 [2017-10-04]. （原始内容存档于2014-08-21） （德语及英语）.  (NB. Plankalkül Java applets and documents.)