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.)