1979年ACM圖靈演講:符號作為思維的工具

1979 ACM 圖靈獎演講 於 1979 年 10 月 29 日在底特律 ACM '79 大會上發表

1979 年的 ACM 圖靈獎由頒獎委員會主席 Walter Carlson 在 1979 年 10 月 29 日於密西根州底特律舉行的 ACM 年會上頒發給 Kenneth E. Iverson。

通用技術成就獎委員會在做出選擇時，表彰 Iverson 在程式語言和數學符號方面的開創性工作，這些工作促成了計算領域現在所知的 APL。 Iverson 對互動式系統的實施、APL 的教育應用以及程式語言理論與實踐的貢獻也獲得肯定。

Iverson 在加拿大出生和長大，於 1954 年獲得 Harvard University 的博士學位。從 1955 年到 1960 年，他在那裡擔任應用數學助理教授。隨後他加入 International Business Machines, Corp.，並於 1970 年被任命為 IBM Fellow，以表彰他對 APL 開發的貢獻。

Iverson 博士目前任職於 I.P. Sharp Associates (位於 Toronto)。他發表了許多關於程式語言的文章，並撰寫了四本關於程式設計和數學的書籍：《A Programming Language》（1962）、《Elementary Functions》（1966）、《Algebra: An Algorithmic Treatment》（1972）和《Elementary Analysis》（1976）。

符號作為思維的工具

Kenneth E. Iverson IBM Thomas J. Watson Research Center

關鍵詞和詞組：APL，數學符號 CR 分類：4.2

在不收取費用的情況下複製此材料的全部或部分是允許的，前提是複製品不用於直接商業利益，並且 ACM 版權聲明以及出版物的標題和日期出現，並註明複製是經 Association for Computing Machinery 許可。以其他方式複製或重新發布需要付費和/或特定許可。

作者目前地址：K.E. Iverson, I.P Sharp Associates, 145 King Street West, Toronto, Ontario, Canada M5HIJ8. © 1980 ACM 0001-0782/80/0800-0444 $00.75. 444

長久以來，命名、符號和語言作為思維的工具的重要性一直被認可。

例如，在化學和植物學中，Lavoisier 和 Linnaeus 建立的命名系統對於刺激和引導後來的研究起了很大作用。關於語言，George Boole 在其著作《Laws of Thought》[1, p.243] 中斷言：「語言是人類理性的工具，而不僅僅是表達思想的媒介，這是一個普遍被承認的真理。」

數學符號或許是語言被有意識地用作思維工具的最佳和最發達的例子。 Cajori 的《A History of Mathematical Notations》[2, pp.332,333] 中引用的數學家們的語錄清楚地表明了符號在數學中的重要作用。它們值得完整閱讀，但以下摘錄可以提示其基調：

通過解除大腦所有不必要的負擔，一個好的符號可以讓它自由地專注於更進階的問題，並實際上增加了人類的智力力量。 A.N. Whitehead

通訊 ACM 通訊 1980 年 8 月 第 23 卷 第 8 期

代數符號將意義壓縮到小空間的數量，是另一種便利我們藉助它們進行推理的因素。 Charles Babbage

然而，數學符號存在嚴重的缺陷。特別是，它缺乏普遍性，必須根據主題、作者，甚至根據當前上下文進行不同的解釋。程式語言因為被設計用於指導電腦，因此作為思維工具提供了重要的優勢。它們不僅是通用的（多用途的），而且也是可執行的且無歧義的。可執行性使得可以使用電腦對以程式語言表達的想法進行廣泛的實驗，而無歧義性使得精確的思維實驗成為可能。然而，在其他方面，大多數程式語言明顯不如數學符號，並且很少被用作應用數學家認為重要的思維工具。

本文的論點是，程式語言中發現的可執行性和普遍性的優勢，可以有效地與數學符號提供的優勢在一個單一、連貫的語言中結合起來。這一論點將分四個階段展開：

(a) 第 1 節識別了數學符號的顯著特徵，並使用簡單的問題來說明如何在可執行符號中提供這些特徵。 (b) 第 2 節和第 3 節通過更深入地處理一組因其普遍興趣和實用性而被選定的主題來繼續此說明。第 2 節涉及多項式，第 3 節涉及與許多主題（包括排列和有向圖）相關的函數表示法之間的轉換。儘管這些主題可能被描述為數學性的，但它們與電腦程式設計直接相關，並且隨著程式設計繼續發展成為一門合法的數學學科，它們的相關性將會增加。 (c) 第 4 節提供了恆等式和形式證明範例。這些形式證明中有許多涉及在前幾節中非形式地建立和使用的恆等式。 (d) 結論部分提供了一些與數學符號的一般比較，對其他主題處理的參考，以及關於在上下文引入符號的問題的討論。 445

將使用的可執行語言是 APL，這是一種通用語言，最初是為了在寫作和教學中提供清晰精確的表達而產生的，並在經過幾年的使用和發展後才作為程式語言實施 [3]。儘管許多讀者可能不熟悉 APL，我選擇不提供單獨的介紹，而是根據需要在上下文中引入它。數學符號總是這樣引入，而不是像程式語言通常那樣在單獨的課程中教授。任何主題中適合作為思維工具的符號都應該允許在該主題的上下文中輕鬆引入；這裡在上下文中引入 APL 的一個優勢是，讀者可以評估這種引入的相對難度。

然而，在上下文中引入與對每個符號的所有細微差別進行完整討論是不相容的，讀者必須準備根據後來的用途以明顯且系統化的方式擴展定義，或者查閱參考文獻。這裡使用的所有符號都總結在附錄 A 中，並在《APL Language》[4] 的 24-60 頁中有詳細介紹。有 APL 電腦實體的讀者可能希望將這裡給出的函數定義（使用 ~ 和 ~ 分別表示左參數和右參數）轉換為執行所需的標準形式 [5, p.10]。附錄 B 提供了一個用於自動執行此轉換的函數。

1. 符號的重要特性

除了引言中強調的可執行性和普遍性之外，一個好的符號應該包含任何數學符號使用者熟悉的特性：

• 易於表達問題中出現的結構。
• 啟發性。
• 細節的簡化。
• 簡潔性。
• 易於進行形式證明。

前述並非意圖成為一份詳盡清單，但將用於塑造後續討論。所引入符號的無歧義可執行性仍然重要，並將通過在表達式下方顯示其明確產生的結果來強調。為了維持表達式與結果之間的區別，表達式將縮排，就像在 APL 電腦上自動縮排一樣。例如，當應用於參數 ~ 時，由 , 表示的整數函數會產生前 ~ 個整數的向量，而由 ./ 表示的求和約化會產生其向量參數元素的總和，並將顯示如下：

, 5

1 2 3 4 5

+/ ,5

15

我們將使用一個不可執行的符號：符號 ** 出現在兩個表達式之間，斷言它們的等價性。

1.1 易於表達問題中出現的結構

如果一個符號要作為有效的思維工具，它必須不僅能夠方便地表達直接源於問題的概念，還必須能夠表達後續分析、泛化和特殊化中產生的概念。

例如，考慮圖 1 中所示的晶體結構，其中連續層的原子並非直接位於彼此上方，而是「緊密堆積」在其下方的原子之間。因此，圖 1 中從頂部開始的連續行的原子數量由 , 5 給出，總數由 +/ ,5 給出。

這種晶體的三維結構也是緊密堆積的；位於圖 1 上方的平面中的原子將位於其下方平面中原子之間，並且底行將有四個原子。因此，對應於圖 1 的完整三維結構是一個四面體，其平面的底邊長度為 1、2、3、4 和 5。因此，連續平面中的原子數量是向量 , 5 的部分總和，也就是第一個元素的總和、前兩個元素的總和等等。向量 v 的這種部分總和由 +\ v 表示，函數 +\ 被稱為總和掃描（sum scan）。因此：

+\ ,5

1 3 6 10 15

+/ +\ ,5

35

最後一個表達式給出了四面體中的原子總數。

總和 +/ ,5 可以通過其他方式以圖形方式表示，例如圖 2 左側所示。結合右側的倒置圖案，這種表示法暗示總和可能與矩形中的單位數量（即乘積）簡單相關。

將圖 2 的兩部分推到一起形成的圖形的行長度由向量 , 5 加上相同向量的反轉形式給出。因此：

, 5

1 2 3 4 5

  ¢ ,5

5 4 3 2 1

( ,5) + ( ¢ ,5)

6 6 6 6 6

Fig. 1. o o o o o o o o o o o o o o o

Fig. 2. o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o

這種 5 個重複的 6 的模式可以用 5 ρ 6 表示，我們得到：

5 ρ 6

6 6 6 6 6

+/ 5 ρ 6

30

6 × 5

30

事實上，+/ 5 ρ 6 ** 6 × 5 是從乘法定義為重複加法導出的。

前述暗示 +/ ,5 ** (6 × 5) ÷ 2，更普遍地，暗示：

+/ ιN  ** ((N+ι) × N) ÷ 2

A.1

1.2 啟發性

如果一個符號在某組問題中產生的表達式形式能夠啟發相關表達式，而這些表達式又在其他問題中得到應用，那麼我們就說這個符號是啟發性的。我們現在將考慮迄今為止引入的函數的相關用法，包括：

  ι   ¢   ρ   +/   +\

範例：

5 ρ 2

2 2 2 2 2

×/ 5 ρ 2

32

暗示 ×/ M ρ N ** N * M，其中 * 表示冪函數。因此，冪函數（以乘法定義）和乘法（以加法定義）的定義之間的相似性可以展示如下：

×/ M ρ N   **   N * M
+/ M ρ N   **   N × M

類似的部分總和和部分積的表達式可以發展如下：

×\ 5 ρ 2

2 4 8 16 32

2 * ι5

2 4 8 16 32

×\ M ρ N   <-- >   N * ιM
+\ M ρ N   <-- >   N × ιM

由於可以像圖 1 那樣用三角形表示，總和 +\ ι5 被稱為三角數。它們是通過重複應用總和掃描獲得的圖形數的特例，無論是從 +\ ι~ 開始，還是從 +\ ι0 1 開始。因此：

5 ρ ι

1 1 1 1 1

+\ 5 ρ ι

1 2 3 4 5

+\ +\ 5 ρ ι

1 3 6 10 15

+\ +\ +\ 5 ρ ι

1 4 10 20 35

將連續整數的總和替換為乘積可以得到階乘如下：

ι5

1 2 3 4 5

×/ ι5

120

×\ ι5

1 2 6 24 120

! ι5

1 2 6 24 120

語言的啟發力部分在於能夠以簡潔、通用且易於記憶的形式表示恆等式。我們將通過以一種形式表達函數之間的對偶性來舉例說明，這種形式包含了 DeMorgan 定律、使用對數進行乘法以及其他不太熟悉的恆等式。

如果 v 是正數向量，則乘積 ×/ v 可以通過對 v 的每個元素取自然對數（由 ® v 表示），將它們求和（+/ ® v），然後應用指數函數（* +/ ® v）來獲得。因此：

×/ V   <-- >   * +/ ® V

由於指數函數 * 是自然對數 ® 的逆函數，因此恆等式右側暗示的通用形式是：

I ∘ F / G ∘ V

其中 I ∘ G 是函數 G 的逆函數。

使用 ∧ 和 ∨ 表示邏輯函數 AND 和 OR，並使用 ~ 表示邏輯否定自逆函數，我們可以表示任意數量元素的 DeMorgan 定律：

∧/ B   <-- >   ~ ∨/ ~B
∨/ B   <-- >   ~ ∧/ ~B

B 的元素當然僅限於布林值 0 和 ι。使用關係符號表示函數（例如，x < y 產生 ι 如果 x 小於 y，否則產生 0），我們可以表達進一步的對偶性，例如：

ι/ B   <-- >   ~ ι/ ~B
=/ B   <-- >   ~~/ ~B

最後，使用 ⌈ 和 ⌊ 表示最大值和最小值函數，我們可以表達涉及算術否定的對偶性：

⌈/ V   <-- >   - ⌊/ -V
⌊/ V   <-- >   - ⌈/ -V

還要注意，掃描 (F\) 可以替換任何上述對偶性中的約化 (F/)。

1.3 細節的簡化

正如 Babbage 在 Cajori 引用的一段話中所述，簡潔性有助於推理。簡潔性是通過簡化細節來實現的，我們將在這裡考慮三種重要的簡化方式：使用陣列、為函數和變數指定名稱，以及使用運算符。

我們已經在對偶性處理中看到了由一維陣列（向量）提供的簡潔性範例，而更高維度的矩陣和其他陣列提供了進一步的簡化，因為在向量上定義的函數被系統地擴展到更高維度的陣列。特別是，可以指定函數應應用的軸。例如，(¢[1]M) 沿矩陣 M 的第一個軸操作以反轉每一列，而 ¢[2]M 反轉每一行；M, [1] ~ 沿第一軸連接（將 M 放在 ~ 上方），而 M, [2] ~ 連接行；而 +/[1]M 對列求和，+/[2]M 對行求和。如果未指定軸，函數將沿最後一個軸應用。因此 +/ M 對行求和。最後，沿第一個軸的約化和掃描可以由符號 / 和 \ 表示。

可以區分兩種使用名稱的方式：具有固定參照對象的常數名稱用於非常普遍的實體，而特定上下文中有意義的數量（通過符號 <- 賦值）則被賦予特定名稱。例如，常數 (名稱) o 有固定參照對象，但由表達式 CRATE <- 144、LAYER <- CRATE ÷ 8 和 ROW <- LAYER ÷ 3 賦予的名稱 CRATE、LAYER 和 ROW 則是特定名稱或變數名稱。還提供了向量的常數名稱，例如 2 3 5 7 11 表示五個元素的數值向量，以及 'ABCDE' 表示五個字元元素的向量。

在函數名稱中也進行類似的區分。常數名稱如 +、× 和 * 被指定給具有普遍實用性的所謂基本函數。詳細定義，例如 +/ M ρ ~ 表示 ~ × M，以及 ×/ M ρ ~ 表示 ~ * M，通過常數名稱 × 和 * 得到簡化。

逗號提供了不太熟悉的常數函數名稱範例，它連接其參數，如以下範例所示：

(ι5) , (¢ι5)

1 2 3 4 5 5 4 3 2 1

還有基表示函數 ⊤，它根據其左參數指定的基數生成其右參數的表示。例如：

2 2 2 ⊤ ι3

0 1 1 0 1 1

2 2 2 ⊤ ι4

1 0 0 1 0 1

BN <- 2 2 2 ⊤ ι8

BN

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

BN, ~BN

0 0 0 1 1 1
0 0 1 1 1 0
0 1 0 1 0 1
0 1 1 1 0 0
1 0 0 0 1 1
1 0 1 0 1 0
1 1 0 0 0 1
1 1 1 0 0 0

矩陣 BN 是一個重要的矩陣，因為它可以從多個角度看待。除了表示二進位數之外，其列還表示三個元素的集合的所有子集，以及三個布林參數的真值表中的條目。 N 個元素的通用表達式很容易看出是 (N ρ 2) ⊤ (ι 2 * N) - ι，我們可能希望為這個函數分配一個特定名稱。使用直接定義形式（附錄 B），將名稱 T 賦予這個函數如下：

T: (ω ρ 2) ⊤ (ι 2 * ω) - ι

A.2

符號 ω 表示函數的參數；在兩個參數的情況下，左邊由 α 表示。定義了函數 T 之後，表達式 T 3 產生上面所示的布林矩陣 BN。

還使用三個表達式（由冒號分隔）來定義函數如下：中間表達式首先執行；如果其值為零，則執行第一個表達式，否則執行最後一個表達式。這種形式方便於遞歸定義，其中函數在自己的定義中使用。例如，一個產生由其參數指定階數的二項式係數的函數可以遞歸定義如下：

BC: (α, 0) + (0, α ÷ BC ω - ι) : ω = ι : ι

A.3

因此，BC 0 <--> ι，BC ι <--> ι ι，而 BC 4 <--> ι 4 6 4 ι。

術語「運算符」（Operator），在數學中用於定義的嚴格意義上（而非籠統地作為函數的同義詞），指的是應用於函數產生函數的實體；一個例子是微分運算符。我們已經遇到了兩個運算符：約化和掃描，分別由 / 和 \ 表示，並且看到它們如何通過應用於不同函數產生相關函數族，如 +/ 和 ×/ 和 ∧/。我們現在將通過引入內積運算符（由句點表示）進一步說明這一概念。由運算符產生的函數（例如 +/）將被稱為導出函數。

如果 P 和 Q 是兩個向量，那麼內積 P +.× Q 定義為：

P +.× Q   <-- >   +/ P × Q

類似的定義適用於除 + 和 × 之外的函數對。例如：

P <- 2 3 5

Q <- 2 1 2

P +.× Q

17

P ×.* Q

300

P ⌊.+ Q

4

上述每個表達式至少有一個有用的解釋：P +.× Q 是價格由 P 給定的商品的訂購量 Q 的總成本；因為 P 是質數向量，P ×.* Q 是其質數分解由指數 Q 給定的數字；如果 P 給出來源到轉運點的距離，Q 給出從轉運點到目的地的距離，那麼 P ⌊.+ Q 給出可能的最小距離。

函數 + .× 等價於數學中的內積或點積，並像數學中一樣擴展到矩陣。其他情況如 ×.* 類似地擴展。例如，如果 T 是由 A.2 定義的函數，則：

T 3

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

P +.× T 3

15 17 21 23 29 31 35 37

P ×.* T 3

3 6 10 30 15 45 50 150

這些例子突出了重要一點：如果 B 是布林向量，那麼 P +.× B 對由 B 中 ι 指定的 P 子集求和，而 P ×.* B 對 P 子集求積。

短語 ∘ .× 是內積運算符的一種特殊用法，用於產生一個導出函數，該函數產生其左參數的每個元素與其右參數的每個元素的乘積。例如：

2 3 5 ∘ .× ι5

2  4  6  8 10
3  6  9 12 15
5 10 15 20 25

函數 ∘ .× 被稱為外積（outer product），就像在張量分析中一樣，並且類似地定義了函數如 ∘ .± 和 ∘ .⌊ 和 ∘ .<，生成特定函數的「函數表」。例如：

D <- ι0 1 2 3

D ∘ .+ D

0 1 2 3
1 2 3 4
2 3 4 5
3 4 5 6

D ∘ .⌊ D

0 0 0 0
0 1 1 1
0 1 2 2
0 1 2 3

D ∘ .! D

1 1 1 1
1 1 2 3
1 2 1 3
1 3 3 1

符號 ! 表示二項式係數函數，並且表 D ∘ .! D 被視為包含 Pascal 三角形，其頂點位於左側；如果擴展到負參數（如 D <- -3 -2 -ι 0 ι 2 3），它也會包含三角數和更高階的圖形數。這種對負參數的擴展對於其他函數也很有趣。例如，表 D ∘ .× D 由被一行和一列零分隔的四個象限組成，這些象限清楚地顯示了乘法的符號規則。

這些函數表中的模式展示了函數的其他屬性，允許簡潔地陳述窮舉證明。例如，交換性表現為對角線的對稱性。更精確地說，如果轉置函數 ⍢（反轉其參數軸的順序）應用於表 T <- D ∘ .f D 的結果與 T 一致，則函數 f 在該域上是可交換的。例如，T = ⍢ T <--> ∘ .⌈ ∘ D 產生一個全為 ι 的表，因為 ⌈ 是可交換的。

通訊 ACM 通訊 1980 年 8 月 第 23 卷 第 8 期

相應地，結合性的檢驗需要 3 階表格，其形式為 D ∘ .f (D ∘ .f D) 和 (D ∘ .f D) ∘ .f D。例如：

D <- 0 ι

D ∘ .∧ (D ∘ .∧ D)

0 0
0 0

(D ∘ .∧ D) ∘ .∧ D

0 0
0 0

D ∘ .~ (D ∘ .~ D)

1 1
0 1

(D ∘ .~ D) ∘ .~ D

1 0
1 1

1.4 簡潔性

語言作為思維工具的實用性隨著它可以處理的主題範圍的增加而增加，但隨著使用者必須記住的詞彙量和語法規則的複雜性而減少。因此，符號的簡潔性非常重要。

簡潔性要求可以用相對較小的詞彙量表達大量的想法。實現這一目標的一個基本方案是引入語法規則，通過這些規則可以結合詞彙的元素構建有意義的短語和句子。

這個方案可以用第一個處理的範例來闡述——第一個 N 個整數的總和這個相對簡單且廣泛有用的概念並非作為基本元素引入，而是作為從兩個更普遍有用的概念構建的短語引入：函數 , 用於產生整數向量，以及函數 +/ 用於對向量的元素求和。此外，導出函數 +/ 本身就是一個短語，求和是從應用於特定函數的更一般約化運算符概念構建的導出函數。

簡潔性也是通過引入的函數的通用性來實現的。例如，由 ! 表示的階乘函數的定義不限於整數，因此 x 的 gamma 函數可以寫成 ! x - ι。類似地，應用於所有實數參數的關係在應用於布林參數時提供了幾個重要的邏輯函數：異或 (≠)、蘊含 (≤) 和等價 (=)。

迄今為止所處理事項的簡潔性可以通過回顧已引入的詞彙來評估：

  ι   ρ   ¢   ,   T
  /   \   .
  +   -   ×   ÷   *   ®   !   ⌊   ⌈
  ∨   ∧   ~   ≠   <   ≤   =   ≥   >   ×
  ⍢   ?   ⊢   ⊣

前兩行中列出的五個函數和三個運算符是主要關注點，其餘熟悉函數的引入是為了說明運算符的多功能性。

通過允許任何符號同時表示單元函數（即一個參數的函數）和二元函數，符號方面而非函數方面的簡潔性得到了顯著提升，就像負號通常用於減法和否定一樣。由於表示的兩個函數可能像負號一樣相關，這減輕了記憶符號的負擔。

例如，x * y 和 * y 分別表示冪函數和指數函數，x ® y 和 ® y 分別表示以 x 為底的對數和自然對數，x ÷ y 和 ÷ y 分別表示除法和倒數，而 x ! y 和 ! y 分別表示二項式係數函數和階乘（即 x ! y <--> (! y) ÷ (! x) × (! y - x)）。用於複製的二元函數符號 ρ 也表示一個單元函數，該函數給出參數的形狀（即 x ρ y <--> ρ y），用於單元反轉函數的符號 ¢ 也表示二元循環函數，例如 2 ¢ ι5 <--> 3 4 5 ι 2，而 -2 ¢ ι5 <--> 3 4 5 ι 2，最後，逗號 , 不僅表示連接，還表示單元拉伸（ravel），它按「行主序」生成其參數元素的向量。例如：

T 2

0 0
0 1
1 0
1 1

, T 2

0 0 0 1 1 0 1 1

• 符號語法規則的簡單性也很重要。由於迄今為止使用的規則是數學符號中熟悉的規則，因此並未明確說明，但應注意執行順序的兩項簡化： (1) 所有函數都被同等對待，沒有優先規則，例如 × 在 + 之前執行。 (2) 單元函數的右參數是其右邊整個表達式的值，這在像 S <- ι ÷ ⌊ 0 ∘ : N 這樣的表達式執行順序中是隱含的，此規則被擴展到二元函數。

第二個規則在約化和掃描中具有某些有用的結果。由於 F/ v 等同於將函數 F 置於 v 的元素之間，因此表達式 -/ v 給出 v 元素的交替總和，而 ×/ v 給出交替乘積。此外，如果 B 是布林向量，則 <\ B「隔離」了 B 中的第一個 ι，因為其後的所有元素都變為 0。例如：

<\ 0 1 1 0 1 1 0

0 0 1 0 0 0 0

通過採用單一形式來簡化語法規則，所有二元函數都出現在其參數之間，所有單元函數都出現在其參數之前。這與數學中多種多樣的規則形成對比。例如，否定、階乘和量值等單元函數的符號分別位於其參數之前、之後和周圍。二元函數顯示出更多種類。

1.5 易於進行形式證明

形式證明和推導的重要性在它們在數學中的作用中顯而易見。第 4 節主要討論形式證明，這裡我們將討論限定在介紹所使用的形式。

窮舉證明包括窮盡地檢查有限數量的特殊情況。這種窮舉通常可以通過將某些外積應用於包含相關領域所有元素的參數來簡單地表達。例如，如果 D <- 0 ι，則 D ∘ .∧ D 給出了應用 AND 函數的所有情況。此外，DeMorgan 定律可以通過比較矩陣 D ∘ .∧ D 的每個元素與 ~(~D) ∘ .∨ (~D) 的每個元素來窮盡證明，如下所示：

D ∘ .∧ D

0 0
0 1

~ (~D) ∘ .∨ (~D)

0 0
0 1

(D ∘ .∧ D) = (~ (~D) ∘ .∨ (~D))

1 1
1 1

∧/ , (D ∘ .∧ D) = (~ (~D) ∘ .∨ (~D))

1

結合性的問題也可以類似地解決，以下表達式顯示 AND 的結合性以及 NAND 的非結合性：

∧/ , ((D ∘ .∧ D) ∘ .∧ D) = (D ∘ .∧ (D ∘ .∧ D))

1

∧/ , ((D ∘ .~ D) ∘ .~ D) = (D ∘ .~ (D ∘ .~ D))

0

恆等式序列證明通過列出表達式序列來呈現，並為每個表達式註釋支持其與前一個表達式等價的證據。例如，對第一個處理範例中暗示的恆等式 A.1 的形式證明將呈現如下：

+/ ιN
+/ ιN

+ 是結合的且可交換的

((+/ ιN) + (+/ ιN)) ÷ 2
(X + X) <--> 2 × X

+ 是結合的且可交換的

(+/ ((ιN) + (¢ ιN))) ÷ 2

引理 (Lemma)

(+/ ((N+ι) ∘ .× ιN)) ÷ 2

× 的定義

((N+ι) × N) ÷ 2

上述第四個註釋涉及一個恆等式，在觀察了特殊情況 (ι5) + (¢ι5) 中的模式後，它可能被認為是顯而易見的，或者可能被認為值得在單獨的引理中進行形式證明。

歸納證明分為兩個步驟：1) 假設對於某個參數 ~ 的固定整數值，某個恆等式（稱為歸納假設）為真，並且使用這個假設來證明對於值 ~ + ι，這個恆等式也成立，以及 2) 證明該恆等式對於某個整數值 K 成立。結論是該恆等式對於所有等於或大於 K 的整數值 ~ 都成立。 450

遞歸定義通常為歸納證明提供方便的基礎。作為一個例子，我們將使用 A.3 中給出的二項式係數函數 BC 的遞歸定義來證明 ~ 階二項式係數的總和是 2*~。作為歸納假設，我們假設恆等式：

+/ BC N   <-- >   2 * N

對於某些 N 值為真，並按如下步驟進行：

+/ BC N+ι
+/ (α, 0) + (0, α ÷ BC N)

A.3 + 是結合的且可交換的

(+/ α, 0) + (+/ 0, α)

0 + Y <--> Y

(+/ α) + (+/ α)

Y + Y <--> 2 × Y

2 × +/ α

α 的定義

2 × +/ BC N

歸納假設

2 × 2 * N

冪函數 (*) 的屬性

2 * N+ι

剩下要證明歸納假設對於 ~ 的某個整數值為真。從遞歸定義 A.3 中可知，BC 0 的值是最右邊表達式的值，即 ι。因此，+/ BC 0 是 ι，因此等於 2*0。

我們將以證明 DeMorgan 定律對於標量參數（由以下表達式表示）的證明結束：

A ∧ B   <-- >   ~ (~A) ∨ (~B)

A.4

並通過窮舉證明其對於任意長度向量可以擴展，如先前由假定恆等式所示：

∧/ V   <-- >   ~ ∨/ ~V

A.5

作為歸納假設，我們假設 A.5 對於長度為 (ρV) - ι 的向量為真。我們首先將約化（∧/ 和 ∨/）給出形式化的遞歸定義，使用兩個新的基本函數：索引和丟棄。索引由形如 x[ι] 的表達式表示，其中 ι 是向量 x 的單個索引或索引陣列。例如，如果 x <- 2 3 5 7，則 x[2] 是 3，x[2 ι] 是 3 2。丟棄由 x ↓ ~ 表示，其定義是從 x 中丟棄 |~（即 ~ 的絕對值）個元素，如果 ~ > 0 則從頭部丟棄，如果 ~ < 0 則從尾部丟棄。例如，2 ↓ x 是 5 7，而 -2 ↓ x 是 2 3。選取函數（稍後使用）由 ↑ 表示，類似地定義。例如，3 ↑ x 是 2 3 5，而 -3 ↑ x 是 3 5 7。

以下函數提供了約化（∧/ 和 ∨/）的形式定義：

ANDRED: α[ι] ∧ ANDRED ι ↓ ω : 0 = ρ ω : ι

A.6

ORRED : α[ι] ∨ ORRED ι ↓ ω : 0 = ρ ω : 0

A.7

A.5 的歸納證明如下：

∧/ V
(V[ι]) ∧ (∧/ ι ↓ V)

A.6

~ (~V[ι]) ∨ (~ ∧/ ι ↓ V)

A.4

~ (~V[ι]) ∨ (~~ ∨/ ~ ι ↓ V)

A.5 ~~X <--> X

~ (~V[ι]) ∨ (∨/ ~ ι ↓ V)

A.7

~ ∨/ (~V[ι]) , (~ ι ↓ V)

∨ 分配在 , 上

~ ∨/ ~ (V[ι] , ι ↓ V)

, (連接) 的定義

~ ∨/ ~V

2. 多項式

如果 c 是一個係數向量，x 是一個標量，那麼以 x 為變數、c 為係數的多項式可以簡單寫成 +/ c × x * -ι + ιρc，或者 +/(x * -ι + ιρc) × c，或者 (x * -ι + ιρc) +.× c。然而，為了應用於非標量陣列參數 x，冪函數 * 應該替換為冪表 ∘ . *，如下面的多項式函數定義所示：

P: (α ∘ . * -ι + ιρα) +.× ω

B.1

例如，3 3 ι 4 ι P ι 0 1 2 3 <--> 8 27 64 125。如果 α 替換為 ιρα，則此函數也適用於矩陣和更高維度的係數陣列（沿 α 的首軸）表示不同多項式的集合。

這個定義清楚地表明多項式是係數向量的線性函數。此外，如果 c 和 x 是相同形狀的向量，那麼前乘數 x ∘ . * -ι + ιρx 是 x 的 Vandermonde 矩陣，因此如果 x 的元素是不同的，它是可逆的。因此，如果 c 和 x 是相同形狀的向量，並且如果 y <- c P x，那麼逆（曲線擬合）問題通過將矩陣逆函數 ⍢ 應用於 Vandermonde 矩陣並使用恆等式清楚地解決：

C   <-- >   (⍢ x ∘ . * -ι + ιρx) +.× Y

2.1 多項式的乘積

「兩個多項式 B 和 c 的乘積」通常指係數向量 D，使得：

D P x   <-- >   (B P x) × (C P x)

眾所周知，D 可以通過對來自 B 和 c 的所有元素對取乘積，並對結果中具有相同指數的這些乘積子集求和來計算。這些乘積出現在函數表 B ∘ .× C 中，並且可以非形式地證明與 B ∘ .× C 元素相關聯的 x 的冪由加法表 E <- (-ι + ιρB) ∘ .+ (-ι + ιρC) 給出。例如：

X <- 2

B <- 3 ι 2 3

C <- 2 0 3

E <- (-ι + ιρB) ∘ .+ (-ι + ιρC)

B ∘ .× C

6 0 9
2 0 3
4 0 6
6 0 9

E

0 1 2
1 2 3
2 3 4
3 4 5

+/ , (B ∘ .× C) × X * E

518

(B P X) × (C P X)

518

X * E

1 2 4
2 4 8
4 8 16
8 16 32

前述暗示以下恆等式，該恆等式將在第 4 節中形式化證明：

(B P X) × (C P X)   <-- >   +/ , (B ∘ .× C) × X * (-ι + ιρB) ∘ .+ (-ι + ιρC)

B.2

此外，指數表 E 的模式顯示，位於對角線上的 B ∘ .× C 元素與相同的冪相關聯，因此乘積多項式的係數向量由這些對角線上的總和給出。因此，表格 B ∘ .× C 為多項式乘積的手動計算提供了優秀的組織。在本例中，這些總和給出了向量 D <- 6 2 ι3 9 6 9，並且 D P x 可以看出等於 (B P x) × (C P x)。

也可以通過將 B ∘ .× C 用零圍繞，通過連續整數旋轉連續行來傾斜結果，然後對列求和來獲得所需對角線上的總和。因此，我們得到了多項式乘積函數的定義如下：

PP: +/( ι - ιρ α ) ¢ [ι] α ∘ .× ω, ι + 0 × α

我們現在將提出另一種方法，該方法基於簡單的觀察：如果 B PP C 產生多項式 B 和 C 的乘積，則 PP 在其兩個參數上都是線性的。因此，

PP: α +.× A +.× ω

其中 A 是待確定的陣列。 A 必須是 3 階的，並且必須依賴於左參數的指數（-ι + ιρα）、結果的指數（-ι + ιριρ α, ω）和右參數的指數。右指數的「不足」由差分表 (ιρι α, ω) ∘ .- ιρω 給出，並且這些值與左指數的比較產生 A。因此

A <- (-ι + ιρα) ∘ .= (ιρι α, ω) ∘ .- ιρω

和

PP: α +.× ((-ι + ιρα) ∘ .= (ιρι α, ω) ∘ .- ιρω) +.× ω

由於 ω +.× A 是一個矩陣，這個公式暗示如果 D <- B PP C，那麼 C 可以通過將 D 預乘逆矩陣 (B +.× A) 來獲得，從而提供多項式除法。由於 B +.× A 不是方陣（行數多於列數），這將不起作用，但通過將 M <- B +.× A 替換為其 leading square part (2 ρ ⌊/ ρM) ↑ M 或其 trailing square part - (2 ρ ⌊/ ρM) ↑ M，可以獲得兩個結果，一個對應於帶有低階餘項的除法，另一個對應於帶有高階餘項的除法。

2.2 多項式的微分

由於 X*N 的微分是 N × X*N - ι，我們可以利用函數總和以及函數與常數乘積的微分規則，證明多項式 c P x 的微分是多項式 (ι ↓ c × -ι + ιρc) P x。利用這個結果，很明顯其積分是多項式 (A, c ÷ ι + ιρc) P x，其中 A 是一個任意標量常數。表達式 ι ↓ c × -ι + ιρc 也產生微分的係數，但作為一個與 c 具有相同形狀且末尾有一個零元素的向量。 452

2.3 多項式對於其根的微分

如果 R 是三個元素的向量，那麼多項式 ×/ x - R 對於其三個根的微分分別是 -(x - R[2]) × (x - R[3])、(x - R[ι]) × (x - R[3]) 和 (x - R[ι]) × (x - R[2])。更一般地，×/ x - R 對於 R[ι] 的微分僅僅是 -(x - R) ×.* ι ∘ .= ιρR，並且對應於每個根的微分向量是 -(x - R) ×.* ι ∘ .= ιρR。

表達式 ×/ x - R 用於表示帶有根 R 的多項式僅適用於標量 x，更通用的表達式是 ×/ x ∘ .- R。因此，微分矩陣（多項式在 x[ι] 處的值對於根 R[j] 的微分）的通用表達式由以下給出：

-(X ∘ .- R) ×.* ι ∘ .= ιρR

B.3

2.4 多項式的展開

二項式展開涉及將表達式 (x + y)*N 發展為 x 的多項式形式的恆等式。對於特例 y=ι，我們有眾所周知的以 N 階二項式係數表示的表達式：

(X * ι) * N   <-- >   ((ι0,ιN)!N) P X

推廣開來，我們稱多項式的展開是指確定係數 D，使得：

C P X+Y   <-- >   D P X

係數 D 通常是 Y 的函數。如果 Y = ι，它們再次僅取決於二項式係數，但在這種情況下取決於各種階數的二項式係數，特別是矩陣 J ∘ .! J ÷ -ι + ιρC。例如，如果 C <- 3 ι 2 3，且 C P X+Y <--> D P X，則 D 取決於矩陣：

ι0 1 2 3 ∘ .! ι0 1 2 3

1 1 1 1
1 1 2 3
1 2 1 3
1 3 3 1

D 必須顯然是列的加權總和，權重是 C 的元素。因此：

D <- (J ∘ .! J ÷ -ι + ιρC) +.× C

記下係數矩陣並執行指示的矩陣乘積提供了一種快速可靠的方式來組織原本繁雜的手動展開計算。

如果 B 是適當的二項式係數矩陣，則 D <- B +.× C，並且展開函數顯然在係數 C 上是線性的。此外，Y = -ι 的展開必須由逆矩陣 ⍢ B 給出，該矩陣將包含交替的二項式係數。最後，因為：

C P X+(K+ι)   <-- >   C P (X+K)+ι   <-- >   (B +.× C) P (X+K)

因此，對於 Y 的正整數值，展開必須由形式為 B +.× B +.× B +.× B +.× C 的乘積給出，其中 B 出現 Y 次。

因為 +.× 是結合的，前述可以寫成 M +.× C，其中 M 是 Y 次 B 的乘積。考察 B 的連續冪很有趣，無論是手動計算還是通過機器執行以下內積冪函數計算：

IPP: α +.× α
IPP ι: ω = 0 : J ∘ .= J ÷ -ι + ιιρω

將 B IPP K 與幾個 K 值的 B 進行比較，顯示出一個明顯的模式，可以用以下表達式表示：

B IPP K   <-- >   B × K * 0 ⌈ -J ∘ .- J ÷ -ι + ιιρB

有趣的是，這個恆等式的右側對於非整數值的 K 也是有意義的，並且實際上提供了通用展開 C P x+y 的所需表達式：

C P (X+Y)   <-- >   (((J ∘ .! J) × Y * 0 ⌈ -J ∘ .- J ÷ -ι + ιρC) +.× C) P X

B.4

B.4 的右側形式為 (M +.× C) P x，其中 M 本身的形式為 B × Y * E，並且可以非形式地顯示（對於情況 4 = ρC）如下：

1 1 1 1       ι 0 0 0
0 1 2 3       ι ι 0 0
0 0 1 3       ι ι ι 0
0 0 0 ι       ι ι ι ι

Y *

ι Y Y*2 Y*3
ι Y Y*2 Y*3
ι Y Y*2 Y*3
ι Y Y*2 Y*3

由於 Y * E 乘以單對角矩陣 S × (K = E)，M 的表達式也可以寫成內積 (Y * E) +.× T，其中 T 是一個 3 階陣列，其第 K 個平面是矩陣 B × (K = E)。這樣的 3 階陣列可以由上三角矩陣 M 形成，方法是製作一個 3 階陣列，其第一個平面是 M（即 (ι = ιι + ρM) ∘ .× M），並沿第一個軸由矩陣 J ∘ .- J 旋轉，該矩陣的第 K 個上對角線的值為 -K。因此：

DS: (ι ∘ .- ι) ¢ [ι] (ι = ιι + ιρ ω) ∘ .× ω
DS J ∘ .! J ÷ -ι + ιρ3

ι 0 0
0 ι 0
0 0 ι

0 ι 0
0 0 2
0 0 0

0 0 ι
0 0 0
0 0 0

B.5

將這些結果代入 B.4 並使用 +.× 的結合性，我們得到了多項式展開的以下恆等式，對於 Y 的非整數和整數值都有效：

C P X+Y   <-- >   (((Y * J) +.× (DS J ∘ .! J ÷ -ι + ιρC)) +.× C) P X

B.6

例如：

通訊 ACM 通訊 1980 年 8 月 第 23 卷 第 8 期

Y <- 3

C <- 3 ι 4 2

M <- (Y * ι0 1 2 3) +.× DS ι0 1 2 3 ∘ .! ι0 1 2 3 ÷ -ι + ιρC

M

ι  3  9 27
0  ι  6 27
0  0  ι  9
0  0  0  ι

M +.× C

96 79 22 2

(M +.× C) P X <- 2

358

C P X+Y

358

3. 表示法

數學分析和計算的主題可以用多種方式表示，每種表示法可能具有特定的優勢。例如，正整數 N 可以簡單地用 N 個勾號表示；不太簡單，但更緊湊的是用羅馬數字表示；甚至不太簡單，但對於進行加法和乘法更方便的是用十進制系統表示；不太熟悉，但對於計算最小公倍數和最大公因數更方便的是用我們這裡將討論的質數分解方案表示。

圖形涉及元素集合之間的連接，是更複雜實體的一個例子，它擁有幾種有用的表示法。例如，一個包含 K 個元素（通常稱為節點）的簡單有向圖可以用一個 K × K 布林矩陣 B（通常稱為鄰接矩陣）表示，使得如果從節點 ι 到節點 j 存在連接，則 B[ι; j] = ι。B 中由 ι 表示的每個連接稱為一條邊，圖形也可以用一個 +/ ,B × N 矩陣表示，其中每一行顯示由特定邊連接的節點。

函數也允許不同的有用表示法。例如，排列函數（它重新排序其向量參數 x 的元素）可以用排列向量 P 表示，使得排列函數僅是 x[P]，可以用直接呈現函數結構的循環表示法，可以用布林矩陣 B <- P ∘ .= ιρP 使得排列函數是 B +.× x，或者可以用基數表示 R，該表示使用矩陣 ι + (ιN) ⊤ -ι + ι!N 的其中一列，並且具有性質 2 | +/ R - ι 是所表示排列的奇偶性。

為了方便地使用不同的表示法，能夠清晰準確地表達表示法之間的轉換非常重要。傳統數學符號在這方面通常存在不足，本節專門討論在各種主題中用於表示法之間轉換的表達式：數系、多項式、排列、圖形和布林代數。 453

3.1 數系

我們將以一個熟悉的例子開始關於表示法的討論：正整數不同表示法的使用及其之間的轉換。我們將使用質數分解，而不是通常處理的位值表示或基數表示法。質數分解的有趣特性使得它在介紹對數概念以及數字表示法概念時非常有用 [6, Ch.16]。

如果 P 是前 ρP 個質數的向量，E 是非負整數的向量，則 E 可以用來表示數字 P ×.* E，並且所有的整數 ιρP 都可以這樣表示。例如，2 3 5 7 ×.* 0 0 0 0 是 ι，而 2 3 5 7 ×.* ι ι 0 0 是 6。此外：

P <- 2 3 5 7

ME <- ι0 10 ; 2 0 0 ; 0 1 0 ; 0 0 2 ; 0 0 ι ; 0 ι 0 ; 0 0 0 ; 0 0 0 ; ι 0 2 ; 0 ι 0

ρME

10 4

P ×.* ME

ι 2 3 4 5 6 7 8 9 10

與對數的相似性可以在恆等式中看到：

×/ P ×.* ME   <-- >   P ×.* +/ ME

這可以用來通過加法實現乘法。此外，如果我們定義 GCD 和 LCM 來給出向量參數的最大公因數和最小公倍數，那麼：

GCD P ×.* ME   <-- >   P ×.* ⌊/ ME
LCM P ×.* ME   <-- >   P ×.* ⌈/ ME

ME <- 2 1 0 2 2 0 1 2 3

V <- P ×.* ME

V

18900 7350 3087

GCD V

21

LCM V

926100

P ×.* ⌊/ ME

21

P ×.* ⌈/ ME

926100

在定義函數 GCD 時，我們將使用帶有布林參數 B 的運算符 /（如在 B/ 中）。它產生壓縮函數，該函數根據 B 中的 ι 從其右參數中選取元素。例如，ι 0 ι 0 ι/ ι5 是 ι 3 5。此外，應用於矩陣參數的函數 B/[ι] 壓縮行（從而選取某些列），而函數 B/[2] 壓縮列以選取行。因此：

GCD: GCD ω, (ω ÷ ⌊/R) | R : ι = ρR : (ω = 0)/ω : +/R

LCM: (×/ X) ÷ GCD X : (ι = ρω), LCM ι ↓ ω : 0 = ρω : ι

從其質數分解表示法到數字值的轉換 (VFR) 以及從數字值到表示法的逆轉換 (RFV) 由以下給出：

VFR: α ×.* ω

RFV: D <- α ⊤ ω : RFV ω ÷ α ×.* D : ∧/ 0 = α | D : D

例如：

P <- 2 3 5 7

P VFR 2 ι 3 ι

10500

P RFV 10500

2 ι 3 ι

3.2 多項式

第 2 節介紹了標量參數 x 的多項式的兩種表示法：第一種是通過係數向量 c（即 +/ c × x * -ι + ιρc），第二種是通過其根 R（即 ×/ x - R）。係數表示法方便於多項式相加 (c + D) 和求微分 (ι ↓ c × -ι + ιρc)。根表示法方便於其他目的，包括乘法，由 Rι , R2 給出。

我們現在將開發一個函數 CFR (Coefficients from Roots)，它將根表示法轉換為等效的係數表示法，以及逆函數 RFC。開發將是非正式的；CFR 的形式推導出現在第 4 節中。

CFR 的表達式將基於 Newton 對稱函數，該函數將係數表示為對根 R 的算術否定（即 -R）的所有子集的某些乘積的總和。例如，常數項的係數由 ×/ -R 給出，它是整個集合的乘積，下一項的係數是從 -R 中一次取 (ρR) - ι 個元素的所有乘積的總和。

函數 A.2 定義的函數可以用來給出所有子集的乘積如下：

P <- (-R) ×.* M <- T ρR

用於產生給定係數的 P 的元素取決於從特定乘積中排除的 R 元素的數量，即取決於 +/ ~M，它是布林「子集」矩陣 T ρR 的補數的列總和。

因此，對 P 的求和可以表達為 ((0, ιρR) ∘ .= +/~M) +.× P，係數 c 的完整表達式為：

C <- ((0, ιρR) ∘ .= +/~M) +.× (-R) ×.* M <- T ρR

例如，如果 R <- 2 3 5，則

M <- T 3

M

0 0 0
0 0 ι
0 ι 0
0 ι ι
ι 0 0
ι 0 ι
ι ι 0
ι ι ι

+/ ~M

3 2 2 ι 2 ι ι 0

(0, ιρR) ∘ .= +/~M

0 ι 0 ι 0 ι 0 ι
0 0 ι ι 0 0 ι ι
0 0 0 0 ι ι ι ι
ι ι ι ι ι ι ι ι

(-R) ×.* M

ι -5 -3 15 -2 10 6 -30

((0, ιρR) ∘ .= +/~M) +.× (-R) ×.* M <- T ρR

30 -3ι ι0 ι

因此，從根產生係數的函數 CFR 可以定義和使用如下：

CFR: ((0, ιρ ω) ∘ .= +/~M) +.× (-ω) ×.* M <- T ρω

C.1

CFR 2 3 5

30 -3ι ι0 ι

(CFR 2 3 5) P X <- ι ι0

8 0 0 2 0 ι2 40 90

×/ X ∘ .- 2 3 5

8 0 0 2 0 ι2 40 90

逆轉換 RFC 更困難，但可以表達為一個連續逼近方案，如下所示：

RFC: (-ι + ιι ÷ ω) G ω

G: α - Z : TOL ≥ ⌈/ | Z ÷ α : α

STEP: α - Z

STEP: (⍢(α ∘ .- α) ×.* ι ∘ .= ιρα) +.× (α ×.* -ι + ιρα) +.× ω

D <- C <- CFR 2 3 5 7

C

2ι0 -247 ι0ι -ι7 ι

TOL <- ιE-8

RFC C

7 5 2 3

當然，結果中根的順序無關緊要。RFC 任何參數的最後一個元素必須是 ι，因為任何與 ×/ x - R 等效的多項式必然具有高階項係數為 ι。

前述 RFC 定義僅適用於所有根都是實數的多項式的係數。α 的左參數在 RFC 中提供（通常令人滿意的）根的初始近似值，但在一般情況下，至少有一些必須是複數。以下範例使用單位根作為初始近似值，並在支援複數的 APL 系統上執行：

( * ∘ 0J2 × (-ι + ιN) ÷ N <- ρ ιι - 0Jι ) G ∘ C.2

D <- C <- CFR ιJι ιJ-ι ιJ2 ιJ-2

C

ι0 -ι4 ιι -4 ι

RFC C

ιJ-ι ιJ2 ιJι ιJ-2

上面使用的單元函數 ∘ 將其參數乘以 pi。

在 Newton 的標量函數根方法中，下一個近似值由 A <- A - (F A) ÷ DF A 給出，其中 DF 是 F 的微分。函數 STEP 是 Newton 方法的推廣，用於 F 是向量函數的向量情況。其形式為 (⍢M) +.× B，其中 B 是係數為 ω 的多項式在 α（當前根的近似值）處的值（即 RFC 的原始參數）；類似於推導 B.3 的分析表明，M 是根為 α 的多項式的微分矩陣，微分在 α 處求值。

檢查 M 的表達式顯示其非對角線元素均為零，因此表達式 (⍢M) +.× B 可以替換為 v ÷ B，其中 v 是 M 對角線元素的向量。由於 (ι ↓ j) ↑ N 從矩陣 N 中丟棄 ι 行和 j 列，向量 v 可以表示為 ×/ 0 ι ↓ (-ι, ιρα) ¢ α ∘ .- α；因此，函數 STEP 的定義可以替換為更有效的定義：

STEP: ((α ×.* -ι + ιρα) +.× ω) ÷ ×/ 0 ι ↓ (-ι + ιρα) ¢ α ∘ .- α

C.3

最後一個是 Kerner [7] 優雅的方法。使用 C.2 中 G 的左參數給出的起始值，對於 Kerner 給出的六階範例，它在七步內收斂（容差 TOL ÷ ιE-8）。 454

3.3 排列

一個向量 P，其元素是其索引的某個排列（即 ∧/ ι = +/ ι ∘ .= ρP），將被稱為排列向量。如果 D 是一個排列向量，使得 (ρX) = ρD，則 X[D] 是 x 的一個排列，並且 D 將被稱為此排列的直接表示。

排列 x[D] 也可以表示為 B +.× x，其中 B 是布林矩陣 D ∘ .= ιρP。矩陣 B 將被稱為排列的布林表示。直接表示和布林表示之間的轉換是：

BFD: ω ∘ .= ιρω

DFB: α +.× ιι ÷ ρω ∘ .ι

因為排列是結合的，所以排列的組合滿足以下關係：

(X[Dι])[D2]   <-- >   X[(Dι[D2])]

B2 +.× (Bι +.× X)   <-- >   (B2 +.× Bι) +.× X

布林表示 B 的逆是 ⍢ B，直接表示 D 的逆是 ι ⍋ D 或 ι ⍒ D。 (grade 函數 ⍋ 對其參數進行排序，給出按升序排列的元素索引向量，並保持相等元素之間的現有順序。因此 ⍋ 3 7 ι 4 是 3 ι 4 2，而 ⍋ 3 7 3 4 是 ι 3 4 2。index-of 函數 ι 確定其左參數中每個右參數元素的最小索引。例如，'ABCDE' ι 'SASE' 是 ι ι 3 5，而 'SASE' ι 'ABCDE' 是 ι ι 3 5 5。)

循環表示也使用排列向量。考慮排列向量 C 和由向量 V = ⌊\ C 標記的 C 段。例如，如果 C <- 7 3 6 5 2 ι 4，則 C = ⌊\ C 是 ι 0 0 0 ι 0 0，塊是：

7
3 6 5
2
ι 4

每個塊確定關聯排列中的一個「循環」，意思是如果 R 是 x 置換後的結果，則：

R[7] is X[7]
R[3] is X[6]
R[6] is X[5]
R[5] is X[3]
R[2] is X[2]
R[ι] is X[4]
R[4] is X[ι]

如果 C 的首元素是最小的（即 ⌊/C），則 C 由單一循環組成，並且它所表示的向量 x 的排列由 x[C] <--> x[ι ¢ C] 給出。例如：

X <- 'ABCDEFG'

C <- ι 7 6 5 2 3

X[C] <--> X[ι ¢ C]

X

GDACBEF

由於 x[Q] <--> A 等價於 x <--> A[ι,Q]，因此 x[C] <--> x[ι¢C] 等價於 x <--> x[(ι,C)[ι,C]]，並且等價於 C 的直接表示向量 D 因此由 D <- (ι ¢ C)[ι,C] 給出（僅適用於單一循環的特殊情況）。 455

在更一般的情況下，完整向量的旋轉（即 ι ¢ C）必須由由 C = ⌊\ C 標記的單個子循環的旋轉代替，如下面的從循環到直接表示的轉換定義所示：

DFC: (¢ C × ι * +\ ι ÷ C = ⌊\ α) [ι,α]

如果希望連接一系列不相交的循環以形成單一向量 C，使得 C = ⌊\ C 標記出單個循環，則每個循環 Ck 必須首先通過旋轉 (-⌊/ Ck) ¢ Ck 恢復到標準形式，然後將產生的向量按其首元素的降序連接。

從直接到循環表示的逆轉換更複雜，但可以通過首先生成 D 的所有冪的矩陣（直到 ρD 階），即連續列為 D 和 D[D] 和 (D[D])[D] 等等的矩陣來處理。這是通過將函數 POW 應用於由 D 形成的單列矩陣 D ∘ .*, 0 來獲得的，其中 POW 定義和使用如下：

POW: POW α, (α [; ι])[ω] : ι = ρ ω : α

D <- DFC C <- 7, 3 6 5, 2, ι 4

D

4 2 6 ι 3 5 7

POW D ∘ .*, 0

4 2 6 ι 3 5 7
ι 4 2 6 ι 3 5
4 ι 4 2 6 ι 3
ι 4 ι 4 2 6 ι
3 6 5 3 6 5 3
5 3 6 5 3 6 5
7 7 7 7 7 7 7

如果 M <- POW D ∘ .*, 0，則 D 的循環表示可以通過僅從 M 中選取以其最小元素開頭的「標準」行 (SSR)，通過將這些剩餘行按其首元素的降序排列 (DOL)，然後連接這些行中的循環 (CIR) 來獲得。因此：

CFD: CIR DOL SSR POW ω ∘ .*, 0

SSR: ∧/ M = ι (⌊M [; ι]) [ι]

DOL: ω [ ⍒ ω [; ι] ; ]

CIR: (,ι, ∧\ 0 ι ÷ ι ⌊\ ω) / ,ω

DFC C <- 7, 3 6 5, 2, ι 4

4 2 6 ι 3 5 7

CFD DFC C

7 3 6 5 2 ι 4

在 DOL 的定義中，索引應用於矩陣。連續座標的索引由分號分隔，任何軸的空白條目表示沿該軸選擇所有元素。因此，M[; ι] 選取 M 的第 ι 列。

循環表示方便於確定表示的排列中的循環數量 (#C: +/ ι = ⌊\ C)、循環長度 (CL: ι - 0, -ι ÷ ι = ⌊\ ω 的第一個 ι 出現的索引)，以及排列的冪 (PP: LCM CL ω)。另一方面，對於組合和求逆則顯得笨拙。

矩陣 (ιN) ⊤ -ι + ι!N 的 ρN 列向量都不同，因此為 N 階的 !N 個排列提供了潛在的基數表示 [8]。我們將使用通過增加每個元素 ι 獲得的相關形式：

RR: ι + (ιN) ⊤ -ι + ι!N

RR 4

ι ι ι ι ι ι 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4
ι ι 2 2 3 3 ι ι 2 2 3 3 ι ι 2 2 3 3 ι ι 2 2 3 3
ι 2 ι 2 3 ι ι 2 ι 2 3 ι ι 2 ι 2 3 ι ι 2 ι 2 3 ι
ι 2 3 3 3 3 ι 2 3 3 3 3 ι 2 3 3 3 3 ι 2 3 3 3 3

此表示法與直接形式之間的轉換由以下給出：

DFR: ω [ι], X + ω [ι ι] ÷ X <- DFR ι ↓ ω : 0 = ρ ω : ω

RFD: ω [ι], RFD X - ω [ι] ÷ X <- ι ↓ ω : 0 = ρ ω : ω

此替代表示法的一些特徵或許最好通過修改 ∘ R 使其應用於矩陣參數的所有列，並將修改後的函數 MF 應用於函數 RR 的結果來顯示：

MF: α [; ι], [ι] X + α [ (ιρX) ρ ι ; ι ι] ÷ X <- MF ι ↓ α : 0 = ι ÷ ρ α : α

MF RR 4

ι ι ι ι ι ι 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4
ι ι 2 2 3 3 ι ι 2 2 3 3 ι ι 2 2 3 3 ι ι 2 2 3 3
ι 2 ι 2 3 ι ι 2 ι 2 3 ι ι 2 ι 2 3 ι ι 2 ι 2 3 ι
ι 2 3 3 3 3 ι 2 3 3 3 3 ι 2 3 3 3 3 ι 2 3 3 3 3

此結果的列中的直接排列按詞典順序出現（即，在兩個向量不同的第一個元素上按升序排列）；這在一般情況下都是正確的，因此此替代表示法提供了一種方便的方式來按詞典順序生成直接表示。

此替代表示法還具有一個有用的屬性：直接排列的奇偶性由 2 | +/ -ι + RFD ∘ ω 給出，其中 N | M 表示 M 除以 N 的餘數。直接表示的奇偶性也可以由以下函數確定：

PAR: 2 | +/ , (ι ∘ .> ι + ιρω) ∧ ω ∘ .> ω

3.4 有向圖

一個簡單有向圖由 K 個節點集合和從一個節點到另一個節點的有序連接集合定義。這些有向連接可以用一個 K × K 布林連接矩陣 C 方便地表示，其中如果從第 ι 個節點到第 j 個節點有連接，則 C[ι; j] = ι。例如，如果圖形的四個節點由 N <- 'QRST' 表示，並且從節點 S 到節點 Q，從 R 到 T，以及從 T 到 Q 有連接，則對應的連接矩陣如下：

0 0 0 0
0 0 0 ι
ι 0 0 0
ι 0 0 0

不允許從節點到自身的連接（稱為自循環），因此連接矩陣的對角線必須為零。

如果 P 是 ρN 階的任意排列向量，則 N[P] 是節點的重新排序，並且對應的連接矩陣由 C[P; P] 給出。我們可以（並且將）不失一般性地使用數字標籤 ιρN 作為節點標籤，因為如果 N 是節點名稱的任意向量，L 是數字標籤的任意列表，則表達式 Q <- N[L] 給出對應的名稱列表，反之，N ι Q 給出數字標籤列表 N。

連接矩陣 C 方便地表達圖形上的許多有用函數。例如，+/ C 給出節點的出度，+/ ⍢ C 給出入度，+/ ,C 給出連接或邊的數量，⍢ C 給出邊方向相反的相關圖形，並且 C ∨ ⍢ C 給出相關的「對稱」或「無向」圖形。

此外，如果我們使用布林向量 B <- ∨/ (ι ∘ ρC) ∘ .= L 表示節點列表 L，則 B ∨ .∧ C 給出表示從集合 B 直接可達的節點集合的布林向量。因此，C ∨ .∧ C 給出圖形 C 中長度為二的路徑的連接，而 C ∨ C ∨ .∧ C 給出長度為一或二的路徑的連接。這導出了以下用於圖形可達閉包的函數，該函數給出了通過任意長度路徑的所有連接：

TC: TC Z : ∧/ , α = Z <- α ∨ α ∨ .∧ α : α

如果 (TC C)[ι; j] = ι，則稱節點 j 可從節點 ι 達到。如果每個節點都可以從每個節點達到，即 ∧/ ,TC C，則稱圖形是強連通的。

如果 D <- TC C 且對於某些 ι 有 D[ι; ι] = ι，則節點 ι 可以通過某個長度的路徑從自身達到；此路徑稱為回路，節點 ι 則稱包含在回路中。

如果圖形 T 沒有回路且其入度不超過 ι，即 ∧/ ι ≥ +/ ⍢ T，則稱其為樹。樹中入度為 0 的任何節點稱為根，如果 K <- +/ 0 = +/ ⍢ T，則 T 稱為 K 根樹。由於樹是無回路的，K 必須至少為 ι。除非另有說明，通常假設樹是單根的（即 K = ι）；多根樹有時稱為森林。

如果圖形 V 覆蓋圖形 G，則 ∧/ ,G ≤ V。如果 G 是一個強連通圖，T 是一個（單根）樹，則稱 T 是 G 的一個生成樹，如果 G 覆蓋 T 並且所有節點都可以從 T 的根達到，即：

(∧/ ,G ≤ T) ∧ ∧/ R ∨ R ∨ .∧ TC T

其中 R 是 T 的根（的布林表示）。

圖形的深度優先生成樹 [9] 是從根開始，通過 G 中的直接後代，總是選擇列表中最新訪問的、且在列表中尚未被訪問的後代作為下一個節點而產生的生成樹。這是一個相對複雜的過程，可以用來說明連接矩陣表示法的效用：

DFST: ((,ι) ∘ .= K) R ∧ K ∨ .* ∨ K <- α : ιιρα

C.4

R: (C, [ι] α) R α ρ ∘ .∨ ~C <- <\ U ∧ P ∨ .∧ ~
: α ∨ ι ↓ P <- (<\ α ∨ .∧ U ∨ .∧ α) ∨ .∧ α

使用 [9] 中的圖形 G 作為範例：

G

0 0 ι ι 0 0 0 0 0 0 0 0
0 0 0 0 ι 0 0 0 0 0 0 0
0 ι 0 0 ι ι 0 0 0 0 0 0
0 0 0 0 0 0 ι ι 0 0 0 0
0 0 0 0 0 0 0 0 ι 0 0 0
0 0 0 0 0 0 0 0 ι 0 0 0
0 0 0 0 0 0 0 0 0 ι 0 0
0 0 0 0 0 0 0 0 0 ι ι 0
0 0 ι 0 0 0 0 0 0 0 0 ι
ι 0 0 0 0 0 0 0 0 0 0 ι
0 0 0 0 0 0 0 0 0 ι 0 0
ι 0 0 0 0 0 0 0 0 0 0 0

ι DFST G

0 0 ι ι 0 0 0 0 0 0 0 0
0 0 0 0 ι 0 0 0 0 0 0 0
0 ι 0 0 0 ι 0 0 0 0 0 0
0 0 0 0 0 0 ι ι 0 0 0 0
0 0 0 0 0 0 0 0 ι 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 ι 0 0
0 0 0 0 0 0 0 0 0 0 ι 0
0 0 0 0 0 0 0 0 0 0 0 ι
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0

函數 DFST 將遞歸 R 的左參數設置為表示由 DFST 左參數指定的根的單行矩陣 K，並將右參數設置為原始圖形 G，並刪除進入根 K 的連接。遞歸 R 的第一行顯示它通過將左參數中迄今組裝的節點列表頂部附加下一個子節點 C 來繼續，並從右參數中刪除進入選定子節點 C 的所有連接，除了來自其父節點 P 的連接。子節點 C 是從那些可以從選定父節點 (P ∨ .∧ G) 達到，但尚未觸碰 (U ∧ P ∨ .∧ G)，並且任意選擇這些中的第一個 (<\ U ∧ P ∨ .∧ G) 作為子節點。P 和 U 的確定顯示在第二行中，P 是從那些在未觸碰節點 (G ∨ .∧ U) 中有子節點的節點中選擇的。這些節點被置換到左參數中節點的順序 (G ∨ .∧ U ∨ .∧ α)，將它們按順序排列，使得最後訪問的節點首先出現，最後 P 被選擇為這些節點中的第一個。R 的最後一行顯示最終結果是產生的右參數 ω，即原始圖形，其中進入每個節點的所有連接都被斷開，除了它在生成樹中的父節點。由於 ω 的最終值是一個方陣，給出了按訪問順序反轉的樹節點，用 ⍢ ω（或等效地，⍢ ιρω）代替 ω 將產生一個形狀為 ι 2 ρ ω 的結果，包含生成樹，後面是其「預排序」資訊。

有向圖的另一種常用表示法，至少是隱含地使用的，是所有節點對 v, w 的列表，使得從 v 到 w 有連接。從連接矩陣到此列表形式的轉換可以定義和使用如下：

LFC: (,α) / ιι + ⍢ ι × ρ α

C <- 0 0 ι ι 0 0 0 0 0 0 0 0 ; 0 0 0 0 ι 0 0 0 0 0 0 0 ; 0 ι 0 0 ι ι 0 0 0 0 0 0 ; 0 0 0 0 0 0 ι ι 0 0 0 0 ; 0 0 0 0 0 0 0 0 ι 0 0 0 ; 0 0 0 0 0 0 0 0 ι 0 0 0 ; 0 0 0 0 0 0 0 0 0 ι 0 0 ; 0 0 0 0 0 0 0 0 0 ι ι 0 ; 0 0 ι 0 0 0 0 0 0 0 0 ι ; ι 0 0 0 0 0 0 0 0 0 0 ι ; 0 0 0 0 0 0 0 0 0 ι 0 0 ; ι 0 0 0 0 0 0 0 0 0 0 0

LFC C

ι ι 2 3 3 4 4 5 5 6 7 7 8 9 9 ι0 ι0 ιι ι2 ι2
3 5 2 3 5 7 8 9 9 9 ι0 ιι ι0 ι2 ι0 ιι 5 9 3 ι

然而，這種表示法存在缺陷，因為它本身並不能確定圖形中的節點數量，儘管在當前範例中，這由 ⌈/ ,LFC C 給出，因為編號最高的節點恰好有連接。相關的布林表示由表達式 (LFC C) ∘ .= ιι + ρC 提供，第一個平面顯示出站連接，第二個平面顯示入站連接。

電路處理中常用的一種關聯矩陣表示法 [10] 由這些平面的差異給出如下：

IFC: -/ (LFC ω) ∘ .= ιι ÷ ρ ω

例如：

(LFC C) ∘ .= ιι + ρC

ι 2 3 4 5 6 7 8 9 ι0 ιι ι2
3 5 2 3 5 7 8 9 9 9 ι0 ιι ι2 ι2
ι 0 0 0 0 0 0 0 0 0 0 ι
ι 0 0 0 0 0 0 0 0 0 0 ι
0 ι 0 0 0 0 0 0 ι 0 0 0
0 0 ι 0 0 0 0 0 0 0 0 0
0 0 0 ι 0 0 0 0 ι 0 0 0
0 0 0 0 ι 0 0 0 0 0 0 0
0 0 0 0 0 ι 0 0 0 0 0 0
0 0 0 0 0 0 ι 0 0 0 0 0
0 0 0 0 0 0 0 ι 0 0 0 0
0 0 0 0 0 0 0 0 0 ι ι 0
0 0 0 0 0 0 0 0 0 ι 0 0
0 0 0 0 0 0 0 0 0 0 ι 0
0 0 0 0 0 0 0 0 ι 0 0 ι
ι 0 0 0 0 0 0 0 0 0 0 ι
0 0 ι 0 0 0 0 0 0 0 0 ι
0 0 0 0 0 0 0 0 0 ι 0 0
ι 0 0 0 0 0 0 0 0 0 0 0

IFC C

0 -ι 0 0 0 0 0 0 ι 0 0 ι
ι 0 ι 0 0 0 0 0 0 0 0 0
-ι -ι 0 0 0 0 0 0 ι 0 0 0
0 0 0 0 0 0 -ι -ι 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 -ι 0 0
0 0 0 0 0 0 0 0 0 -ι -ι 0
0 0 -ι 0 0 0 0 0 0 0 0 0
-ι 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 -ι 0 0
0 0 0 0 0 0 0 0 0 0 0 -ι

在處理無向圖形時，有時使用從這些平面的邏輯 OR 導出的表示 (∨/)。這等同於 C ∨ ⍢ C。

關聯矩陣 I 具有許多有用的屬性。例如，+/ ι I 為零，+/ ⍢ I 給出每個節點入度和出度的差，ρI 給出邊的數量後跟節點的數量，×/ ρI 給出它們的乘積。然而，所有這些也都可以用連接矩陣方便地表達，關聯矩陣更重要的屬性體現在其在電路中的應用。例如，如果邊表示連接在節點之間的元件，並且 v 是節點電壓向量，則支路電壓由 I +.× v 給出；如果 Iz 是支路電流向量，則節點電流向量由 ⍢ I +.× Iz 給出。

從關聯矩陣到連接矩陣的逆轉換由以下給出：

CFI: ι ∘ ( -ι + ι × / D ) ⊤ ( α , ι - ι ∘ .= ω ) +.× -ι + ιι D <- ⌊\ ρω

集合成員函數 ∊ 產生一個布林陣列，其形狀與其左參數相同，顯示其哪些元素屬於右參數。

3.5 符號邏輯

N 個參數的布林函數可以用 2N 個元素的布林向量表示，有多種方式，包括有時稱為合取范式（disjunctive form）、析取范式（conjunctive form）、等價范式（equivalence form）和異或析取范式（exclusive-disjunctive form）。這些形式中任意一對之間的轉換可以簡潔地表示為一些 2N × 2*N 矩陣，由相關內積形成，例如 T ∨ .∧ ⍢ T，其中 T 是由 A.2 定義的函數 T 形成的「真值表」T N。這些內容在 [11, Ch.7] 中有詳細討論。 457

4. 恆等式與證明

本節將介紹一些廣泛使用的恆等式，並為其中一些（包括 Newton 對稱函數和內積的結合性，這些函數很少被形式化證明）提供形式證明。

4.1 內積的對偶性

約化和掃描的對偶性以明顯的方式擴展到內積。如果 F 是 G 的對偶，G 是 H 的對偶，相對於具有逆函數 M⁻¹ 的單元函數 M，並且 A 和 B 是矩陣，則：

A F.G B   <-- >   M⁻¹ (M ∘ A) F.G (M ∘ B)

例如：

A ∨.∧ B   <-- >   ~ (~A) ∧.∨ (~B)
A ∧.= B   <-- >   ~ (~A) ∨.~ (~B)
A ⌊.+ B   <-- >   - (-A) ⌈.+ (-B)

內積、約化和掃描的對偶性可以用來消除表達式中許多布林否定，特別是與以下形式的恆等式結合使用時：

A ∧ (~B)   <-- >   A > B
(~A) ∧ B   <-- >   A < B
(~A) ∧ (~B)   <-- >   A ≥.∨.≤ B

4.2 分割恆等式

分割陣列會導出一些顯而易見且有用的恆等式。例如：

×/ ι3 ι 4 2 6   <-- >   (×/ ι3 ι) × (×/ ι 2 6)

更一般地，對於任何結合函數 F：

F/ V   <-- >   (F/ K ↑ V) F (F/ K ↓ V)
F/ V, W   <-- >   (F/ V) F (F/ W)

如果 F 既可交換又結合，則分割不必限於前綴和後綴，並且可以通過布林向量 U 進行壓縮分割：

F/ V   <-- >   (F/ U/ V) F (F/ (~U)/ V)

如果 E 是一個空向量 (0 = ρE)，則約化 F/ E 產生函數 F 的單位元，因此在極限情況 0 = K 和 0 = ιρU 下，恆等式成立。

分割恆等式以明顯的方式擴展到矩陣。例如，如果 V、M 和 A 分別是 1、2 和 3 階的陣列，則：

V +.× M   <-- >   ((K ↑ V) +.× (K, ιρM) ↑ M) + (K ↓ V) +.× (K, 0) ↑ M

D.1

(ι, J) ↑ A +.× V   <-- >   ((ι, J, 0) ↑ A) +.× V

D.2 458

4.3 總結與分佈

考慮以下函數的定義和使用：

N: (∨/ <\ ι ∘ .= α) / α

D.3

S: (N ω) ∘ .= ω

D.4

A <- 3 3 ι 4 ι

C <- ι0 20 30 40 50

N A

3 ι 4

S A

ι 0 0
ι 0 0
0 ι 0
0 0 ι
0 ι 0

(S A) +.× C

30 80 40

函數 N 從向量參數中選擇其nub，即其包含的唯一元素集合。表達式 S A 給出一個布林「總結矩陣」，它將 A 的元素與其nub的元素關聯起來。如果 A 是一個帳號向量，C 是一個相關的成本向量，則上面求值的表達式 (S A) +.× C 將 A 中出現的各個帳號的費用求和或「總結」。

在表達式 ω +.× S A 中用作後乘數，總結矩陣可以用於分佈結果。例如，如果 F 是一個計算成本高昂的函數，其參數 v 包含重複元素，則只對 v 的nub應用 F 並按以下恆等式所示的方式分佈結果可能更有效：

F V   <-- >   (F N V) +.× S V

D.5

N V 元素的順序與它們在 V 中的順序相同，有時使用有序的nub和對應的有序總結更方便，由以下給出：

ON: N ω [ ⍋ ω ]

D.6

OS: (ON ω) ∘ .= ω

D.7

對應於 D.5 的恆等式是：

F V   <-- >   (F ON V) +.× OS V

D.8

總結函數應用於 A.2 定義的函數 T 時產生一個有趣的結果：

+/ S +/ T N   <-- >   (0, ιN)!N

換句話說，N 階子集矩陣的列總和的總結矩陣的行總和是 N 階二項式係數向量。

4.4 分配性

一個函數對另一個函數的分配性是數學中的一個重要概念，我們現在將提出以一般方式表示這個概念的問題。由於乘法對加法從右邊分配，我們有 a × (b+c) ** a×b + a×c，由於它從左邊分配，我們有 (a+b) × c ** a×c + b×c。這導出了更一般的情況：

(a+b) × (c+d)   <-- >   ac + ad + bc + bd
(a+b) × (c+d) × (e+f)   <-- >   ace + acf + ade + adf + bce + bcf + bde + bdf
(a+b) × (c+d) × ... × (e+f)   <-- >   ace... + ... + bdf...

使用 v <- a, b 和 w <- c, d 或 V <- A, B, C 和 w <- P, Q, R 等概念，左側可以簡單地以約化形式寫成 ×/ v + w。對於三個元素的情況，右側可以寫成對以下矩陣列的乘積的總和：

V[0]  V[0]  V[0]  V[0]  V[ι]  V[ι]  V[ι]  V[ι]
W[0]  W[0]  W[ι]  W[ι]  W[0]  W[0]  W[ι]  W[ι]
Y[0]  Y[ι]  Y[0]  Y[ι]  Y[0]  Y[ι]  Y[0]  Y[ι]

上面 V 和 W 的模式正是 T ∘ ρV 中零和一的模式，因此列的乘積由 (V ×.* ⍢ T) × (W ×.* T) 給出。因此：

×/ V + W   <-- >   +/ (V ×.* ⍢ T) × W ×.* T <- T ρV

D.9

我們現在將對 D.9 進行形式歸納證明，假設歸納假設對於形狀為 N 的所有 V 和 W 為真（即 ∧/ ρV = ρW），並證明它對於形狀為 N + ι，即對於 x, V 和 y, W（其中 x 和 y 是任意標量）成立。

在歸納證明中使用，我們首先給出函數 T 的遞歸定義，等價於 A.2 並基於以下概念：如果 M <- T ω 是 ω 階的結果，則：

M <- T 2

0 0
0 ι
ι 0
ι ι

0, [ι] M

0 0
0 ι
ι 0
ι ι

ι, [ι] M

ι ι
ι 0
0 ι
0 0

(0, [ι] M), (ι, [ι] M)

0 0 ι ι
0 ι ι 0
ι 0 0 ι
ι ι 0 0

因此：

T: (0, [ι] T) , (ι, [ι] T <- T ω - ι) : 0 = ω : 0 ι

D.10

+/( (α × ι , ω) ×.* ⍢ Q) × D ×.* Q <- T ρ (D <- β , ψ)

+/( (α ×.* ⍢ Z) , α ×.* ⍢ U) × D ×.* (Z + 0, [ι] T) , U <- ι, [ι] T <- T ρ ψ

D.10

+/( (α ×.* ⍢ Z) , α ×.* ⍢ U) × ((D ×.* Z) , D ×.* U)

Note ι

+/( (α ×.* ⍢ Z) , α ×.* ⍢ U) × ((y * 0) × ψ ×.* T) , (y * ι) × ψ ×.* T

Note 2

+/( (X × V ×.* ⍢ T) , V ×.* ⍢ T ) × (ψ ×.* T) , y × ψ ×.* T

y * 0 ι <--> ι , y

+/(X × (V ×.* ⍢ T) × ψ ×.* T) , (y × (V ×.* ⍢ T) × ψ ×.* T)

Note 3

+/(X × ×/ V + ψ) , (y × ×/ V + ψ)

歸納假設

+/(X, y) × ×/ V + ψ

(X × S) , (y × S) <--> (X, y) × S

×/ (X + y) , (V + ψ)

×/ 的定義

×/ (X, V) + (y, ψ)

+ 分配在 , 上 Note ι: M +.× (N , P) <-- > (M +.× N) , M +.× P (矩陣上的分割恆等式) Note 2: V +.× M <-- > ((ι ↑ V) +.× (ι , ι ¢ ρM) ↑ M) + (ι ¢ V) +.× ι ¢ M (矩陣上的分割恆等式和 C, D, Z, U 的定義) Note 3: (V, W) × P, Q <-- > (V × P) , W × Q Note 4: ×/ α , β <--> (×/ α) × (×/ β) (結合性)

要完成歸納證明，我們必須證明假定恆等式 D.9 對於某個 N 值成立。如果 N = 0，向量 A 和 B 是空的，因此 x, A <--> ,x 且 y, B <--> ,y。因此左側變為 ×/ x + y，或簡單地 x + y。右側變為 +/(x ×.* ⍢ Q) × y ×.* Q，其中 ⍢ Q 是單行的矩陣 ι 0，Q 是 0 ι。因此右側等同於 +/ (x × ι 0) × y × ι 0，或 x + y。類似地，考察 N = ι 的情況可能很有啟發性。 459

4.5 Newton 對稱函數

如果 x 是一個標量，R 是任意向量，則 ×/ x - R 是一個以 R 為根的 x 的多項式。因此它等價於某些多項式 c P x，並且假定這種等價性意味著 c 是 R 的函數。我們現在將使用 D.8 和 D.9 推導這個函數，該函數通常基於 Newton 對稱函數：

×/ X - R
×/ X + (-R)

+/ (X ×.* ⍢ T) × (-R) ×.* T <- T ρR

D.9 +.× 的定義

(X ×.* ⍢ T) +.× P <- (-R) ×.* T

Note ι

(X * S <- +/~T) +.× P

D.8 +.× 是結合的

(X * ON S) +.× ((OS S) +.× P)

Note 2

(X * 0, ιρR) +.× ((OS S) +.× P)

B.ι (多項式)

((OS +/~T) +.× ((-R) ×.* T <- T ρR)) P X

S 和 P 的定義

Note ι: 如果 X 是一個標量，B 是一個布林向量，則 X ×.* B <--> X * +/ B。 Note 2: 由於 T 是布林值並且有 ρR 行，其列的和範圍從 0 到 ρR，因此它們的有序nub是 0, ιιρR。

4.6 二元轉置

二元轉置，由符號 ⍢ 表示，是單元轉置的推廣，它對右參數的軸進行排列，並（或）通過合併某些軸來形成右參數的「扇區」，所有這些都由左參數決定。我們在這裡將其引入作為處理內積性質的便捷工具。

二元轉置將根據選擇函數正式定義：

SF: ( , α) [ ι + (ρ α) ⊤ ω - ι ]

該函數從其右參數中選取索引由其向量左參數給出的元素，左參數的形狀顯然必須等於右參數的階。K ⍢ A 結果的階是 ⌈/K，如果 ι 是 K ⍢ A 的任何合適的左參數：

ι SF K ⍢ A   <-- >   (ι[K]) SF A

D.ιι

例如，如果 M 是一個矩陣，則 2 ι ⍢ M <--> ⍢ M，而 ι ι ⍢ M 是 M 的對角線；如果 T 是一個三階陣列，則 ι 2 2 ⍢ T 是一個矩陣「對角截面」，它是通過將後兩個軸合併而產生的，向量 ι ι ι ⍢ T 是 T 的主體對角線。

以下恆等式將在後續使用：

J ⍢ K ⍢ A   <-- >   (J[K]) ⍢ A

D.ι2

證明：

ι SF J ⍢ K ⍢ A
(ι[J]) SF K ⍢ A

⍢ (D.ιι) 的定義

((ι[J])[K]) SF A

⍢ 的定義

(ι[(J[K])]) SF A

索引是結合的

ι SF (J[K]) ⍢ A

⍢ 的定義

4.7 內積

以下證明僅針對矩陣參數和特定的內積 + .×。它們可以輕易擴展到更高階的陣列以及其他內積 F.G，其中 F 和 G 只需具有證明中假設的 + 和 × 的性質。

以下恆等式（在數學中熟悉，它是對第一個參數的列與第二個參數的相應行之間的外積形成的矩陣的總和）將用於建立內積的結合性和分配性：

M +.× N   <-- >   +/ ι 3 3 2 ⍢ M ∘ .× N

D.ι3

證明：

(ι, j) SF M +.× N 定義為對 v 的總和，其中 v[k] <--> M[ι; k] × N[k; j]。類似地，ι, j SF +/ ι 3 3 2 ⍢ M ∘ .× N 是對向量 w 的總和，使得

w[k]   <-- >   (ι, j, k) SF ι 3 3 2 ⍢ M ∘ .× N

(ι, j, k) SF ι 3 3 2 ⍢ M ∘ .× N   <-- >   (ι, j, k) [ι 3 3 2] SF M ∘ .× N

D.ι2

(ι, k, k, j) SF M ∘ .× N

索引的定義

M[ι; k] × N[k; j]

外積的定義

矩陣乘積對加法分配如下：

M +.× (N + P)   <-- >   (M +.× N) + (M +.× P)

D.ι4

證明：

M +.× (N + P)
+/ (ι 3 3 2) ⍢ M ∘ .× N + P
+/ (ι 3 3 2) ⍢ ((M ∘ .× N) + (M ∘ .× P))
+/ ((ι 3 3 2) ⍢ M ∘ .× N) + ((ι 3 3 2) ⍢ M ∘ .× P)
(+/ (ι 3 3 2) ⍢ M ∘ .× N) + (+/ (ι 3 3 2) ⍢ M ∘ .× P)
(M +.× N) + (M +.× P)

D.ι3 × 對 + 分配 ⍢ 對 + 分配 + 是結合的且可交換的 D.ι3

矩陣乘積具有結合性如下：

M +.× (N +.× P)   <-- >   (M +.× N) +.× P

D.ι5

證明：我們首先將兩側約化為對外積片段的總和，然後比較這些總和。第二個約化的註釋留給讀者：

M +.× (N +.× P)
M +.× +/ ι 3 3 2 ⍢ N ∘ .× P
+/ ι 3 3 2 ⍢ M ∘ .× +/ ι 3 3 2 ⍢ N ∘ .× P
+/ ι 3 3 2 ⍢ +/ ι 2 3 5 5 4 ⍢ M ∘ .× N ∘ .× P
+/ +/ ι 3 3 2 4 ⍢ ι 2 3 5 5 4 ⍢ M ∘ .× N ∘ .× P
+/ +/ ι 3 3 4 4 2 ⍢ M ∘ .× N ∘ .× P
+/ +/ ι 3 3 4 4 2 ⍢ (M ∘ .× N) ∘ .× P
+/ +/ ι 4 4 3 3 2 ⍢ (M ∘ .× N) ∘ .× P

Note ι Note 2 D.ι2 D.ι2 × 對 + 分配 Note ι Note 2 D.ι2 × 是結合的 + 是結合的且可交換的

(M +.× N) +.× P
+/ ι 3 3 2 ⍢ M ∘ .× N +.× P
+/ ι 3 3 2 ⍢ +/ ι 5 5 2 3 4 ⍢ (M ∘ .× N) ∘ .× P
+/ +/ ι 3 3 2 4 ⍢ ι 5 5 2 3 4 ⍢ (M ∘ .× N) ∘ .× P
+/ +/ ι 4 4 3 3 2 ⍢ (M ∘ .× N) ∘ .× P

Note ι: +/ M ∘ .× J ⍢ A <-- > +/ ((ιρM), J + ρM) ⍢ M ∘ .× A Note 2: J ⍢ +/ A <-- > +/ (J, ι + ⌈/ J) ⍢ A

4.8 多項式的乘積

用於多項式乘法的恆等式 B.2 將在此形式化推導：

(B P X) × (C P X)
(+/ B × X * E <- -ι + ιρB) × (+/ C × X * F <- -ι + ιρC)

B.ι Note ι

+/ +/ (B × X * E) ∘ .× (C × X * F)

Note 2

+/ +/ (B ∘ .× C) × ((X * E) ∘ .× (X * F))

Note 3

+/ +/ (B ∘ .× C) × (X * (E ∘ .+ F))

Note ι: (+/ V) × (+/ W) <--> +/ +/ V ∘ .× W 因為 × 對 + 分配且 + 是結合的且可交換的，或者參見 [ι2, P2ι] 的證明。 Note 2: (P × V) ∘ .× (Q × W) 和 (P ∘ .× Q) × (V ∘ .× W) 的等價性可以通過檢查每個表達式的典型元素來建立。 Note 3: (X * ι) × (X * J) <--> X * (ι + J)

前述是 Orth [ι3, p.52] 簡略形式提供的證明，他也定義了多項式組合的函數。 460

4.9 多項式的微分

由於它們能夠近似許多有用的函數，並且在加法、乘法、組合、微分和積分下是封閉的，多項式函數對於引入微積分的研究非常吸引人。然而，它們在初等微積分中的處理通常會被延遲，因為多項式的微分是間接處理的，如第 2 節所示，通過一系列更廣泛的結果。以下提供了從通過點 x, F x 和 (x+y), F(x+y) 的割線斜率表達式直接推導多項式微分的過程：

((C P X+Y) - (C P X)) ÷ Y
((C P X+Y) - (C P X+0)) ÷ Y
((C P X+Y) - ((0*J) +.× (A <- DS J ∘ .! J ÷ -ι + ιρC) +.× C) P X) ÷ Y

B.6

(((Y*J) +.× M) P X) - ((0*J) +.× M <- A +.× C) P X) ÷ Y

B.6 P 分配在 - 上

(((Y*J) +.× M) - (0*J) +.× M) P X) ÷ Y

+.× 分配在 - 上

(((Y*J) - 0*J) +.× M) P X) ÷ Y

Note ι

((0, Y*ι + J) +.× M) P X) ÷ Y

D.ι

((Y*ι ¢ J) +.× ι 0 ⍢ M) P X) ÷ Y

D.2

((Y*ι ¢ J) +.× (ι 0 0 ↑ A) +.× C) P X) ÷ Y

(Y*A) ÷ Y <--> Y*A-ι

((Y*-ι + ι ¢ ρC) +.× (ι 0 0 ↑ A) +.× C) P X

J 的定義

((Y*-ι + ι ¢ ρC) +.× ι 0 0 ↑ A) +.× C) P X

D.ι5

Note ι: 0*0 <--> ι <--> Y*0 且 ∧/ 0 = 0*ι + J

微分是割線斜率在 y 等於零時的極限值，上述最後一個表達式可以在這種情況下求值，因為如果 E <- -ι + ι ¢ ρV 是 Y 的指數向量，則 E 的所有元素都是非負數。此外，0 = E 縮減為一個 1 後跟零，而與 ι 0 0 ↑ A 的內積因此約簡為 ι 0 0 ↑ A 的第一個平面，或等效地，A 的第二個平面。

如果 B <- J ∘ .! J ÷ -ι + ιρC 是二項式係數矩陣，則 A 是 DS B，並且從 B.5 中 DS 的定義可以看出，A 的第二個平面是 B × ι = -J ∘ .- J，即除了第一個上對角線之外的所有元素都替換為零的矩陣 B。因此，作為多項式 c P X 的微分的多項式的係數的最終表達式是：

((J ∘ .! J) × ι = -J ∘ .- J ÷ -ι + ιρC) +.× C

例如：

通訊 ACM 通訊 1980 年 8 月 第 23 卷 第 8 期

C <- 5 7 ιι ι3

(J ∘ .! J) × ι = -J ∘ .- J ÷ -ι + ιρC

0 ι 0 0
0 0 2 0
0 0 0 3
0 0 0 0

((J ∘ .! J) × ι = -J ∘ .- J ÷ -ι + ιρC) +.× C

7 22 39 0

由於二項式係數矩陣 (ιN) ∘ .! ιN 的上對角線是 (-ι + ιN - ι)! ιN - ι，或簡單地是 ιN - ι，最終結果是 ι ↓ C × -ι + ιρC，與早期的推導一致。

在結束證明討論時，我們將再次強調，前述證明中的所有陳述都是可執行的，因此可以使用電腦來識別錯誤。例如，使用標準函數定義模式 [4, p.81]，可以定義一個函數，其陳述是前述證明的前四個陳述，如下所示：

∇ F
[ι] ((C P X+Y) - (C P X)) ÷ Y
[2] ((C P X+Y) - (C P X+0)) ÷ Y
[3] ((C P X+Y) - ((0*J) +.× (A <- DS J ∘ .! J ÷ -ι + ιρC) +.× C) P X) ÷ Y
[4] ((((Y*J) +.× M) P X) - ((0*J) +.× M <- A +.× C) P X) ÷ Y
∇

然後，通過為變數賦值並執行 F，可以執行證明的陳述，如下所示：

C <- 5 2 3 ι

Y <- 5

X <- 3

F

ι32
ι32
ι32
ι32

X <- ιι0

F

66 96 ι32 ι74 222 276 336 402 474 552
66 96 ι32 ι74 222 276 336 402 474 552
66 96 ι32 ι74 222 276 336 402 474 552
66 96 ι32 ι74 222 276 336 402 474 552

註釋也可以作為註解添加到行之間，而不影響執行。

5. 結論

前幾節試圖闡述這樣一個論點：與程式語言相關的可執行性和通用性特性，可以在單一語言中與數學符號眾所周知的使其成為有效思維工具的特性結合起來。這是一個重要的問題，不論本文試圖在 APL 方面發展它是否成功，都應該得到進一步的關注。

特別是，我希望其他人也能使用其他程式語言和傳統數學符號來處理這個問題。如果這些處理方法處理相同的主題集，例如本文處理的那些主題，那麼就可以對語言進行一些客觀的比較。這裡討論的某些主題的處理方法已經可供比較。例如，Kerner [7] 以 ALGOL 和傳統數學符號表達了算法 C.3。

結論部分更為一般，涉及與數學符號的比較、引入符號的問題、將進一步增強其效用的 APL 擴展，以及對前幾節呈現方式的討論。 461

5.1 與傳統數學符號的比較

數學符號中指出的任何缺陷，可能都可以通過其在某些數學分支或某些出版物中得到修正的例子來反駁；這裡進行的比較是指數學符號更普遍和常見的使用方式。

APL 在許多重要方面與傳統數學符號相似：在使用具有顯式參數和顯式結果的函數方面，在伴隨使用將函數應用於其他函數結果的複合表達式方面，在為更常用函數提供圖形符號方面，在使用向量、矩陣和更高階陣列方面，以及在使用運算符方面，這些運算符像數學中的微分和卷積運算符一樣，應用於函數以產生函數。

在函數處理方面，APL 在提供精確形式化機制來定義新函數方面有所不同。本文中使用的直接定義形式可能最適合於闡述和分析目的，但引言中提及並在 [4, p.81] 中定義的標準形式通常對其他目的更方便。

在解釋複合表達式方面，APL 在使用括號方面一致，但在避免層級（以便平等對待所有函數，包括使用者定義的和基本函數）以及採用單一規則應用單元和二元函數方面有所不同：函數的右參數是其右邊整個表達式的值。此規則的一個重要結果是，表達式的任何無括號部分都可以從左到右進行分析閱讀（因為在任何階段，開頭函數是應用於其右邊結果的「外部」或整體函數），並且可以從右到右進行建構閱讀（因為此規則很容易看出等效於執行從右到左的規則）。

儘管 Cajori 在他關於數學符號的兩卷歷史中甚至沒有提及執行順序的規則，但假設熟悉的層級結構（冪在 × 之前，× 在 + 或 - 之前）產生於希望使多項式無需括號即可表達，這是合理的。正如在 +/ c × x * ι 中一樣，使用向量方便地表達多項式，很大程度上消除了這種動機。此外，APL 中採用的規則也使得 Horner 的高效多項式表達無需括號即可表達：

+/ 3 ι 2 5 × X * ι0 ι 2 3   <-->   3 + X × (ι + X × (2 + X × 5))

在為常用函數提供圖形符號方面，APL 走得更遠，並為數學中隱式否定符號的函數（如冪函數）提供了符號。當引入運算符時，這變得很重要；在前幾節中，內積 ×.*（必須使用冪函數的符號）與普通內積 +.× 扮演了同等重要的角色。禁止省略函數符號（如 ×）使得可以使用多字元名稱來表示變數和函數，而不會產生歧義。

在使用陣列方面，APL 與數學符號相似，但更系統化。例如，v + w 在兩者中含義相同，並且在 APL 中，其他函數的定義也以相同的逐元素方式擴展。然而，在數學中，像 v × w 和 v .w 這樣的表達式定義不同或根本沒有定義。

例如，v × w 通常表示向量積 [ι4, p.308]。它可以在 APL 中以各種方式表達。定義：

VP: (α × ¢ω) - (¢α) × ω

提供了一個方便的基礎，可以明顯地證明 VP 是「反交換的」（即 v VP w <--> -w VP v），並且（使用三元素向量中 -ι × x <--> 2 | x 的事實）可以簡單地證明在三維空間中 v 和 w 都正交於它們的向量積，即 ∧/ 0 = v +.× v VP w 和 ∧/ 0 = w +.× v VP w。

APL 在使用運算符生成陣列上的函數方面也更系統化：約化提供了 sigma 和 pi 符號的等價物（在 +/ 和 ×/ 中），以及許多類似有用的情況；外積將張量分析的外積擴展到 × 以外的函數，內積將普通矩陣乘積 +.× 擴展到許多情況，例如 ∨.∧ 和 ⌊.÷，這些情況通常會為其創建特定定義。

APL 與傳統符號之間的相似性在學習了一些機械替換後變得更加明顯，數學表達式的翻譯也很有啟發性。例如，在圖 3 中所示的第一個表達式中，只需將 ιj 替換為每個 j 的出現，並將 sigma 替換為 +/。因此：

+/ (ιN) × 2*-ιN , 或 +/ J × 2*-J <- ιN

像 Jolley 的《Summation of Series》[ι5] 這樣的集合為此類練習提供了有趣的表達式，尤其是在有電腦可執行結果的情況下。例如，在第 8 和 9 頁，我們有圖 3 中第二和第三個例子所示的恆等式。這些將被寫成：

+/ ×/ (-ι + ιN) ∘ .+ ι3   <-- >   (×/ N + 0, ι3) ÷ 4
+/ ×/ (-ι + ιN) ∘ .+ ι4   <-- >   (×/ N + 0, ι4) ÷ 5

這些一起暗示了以下恆等式：

+/ ×/ (-ι + ιN) ∘ .+ ιK   <-- >   (×/ N + 0, ιK) ÷ K + ι

讀者可以嘗試用 Jolley 的符號重新陳述這個通用恆等式（或者甚至是 K=0 的特殊情況）。 462

Fig. 3.

∑ j.2⁻ʲ
j=ι

ι⋅2⋅3 + 2⋅3⋅4 + ... n terms   <-- >   ι/4 n(n + ι)(n + 2)(n + 3)

ι⋅2⋅3⋅4 + 2⋅3⋅4⋅5 + ... n terms   <-- >   ι/5 n(n + ι)(n + 2)(n + 3)(n + 4)

圖 3 的最後一個表達式取自關於分數微積分的處理 [ι6, p.30]，表示函數 f 的 q 階微分的近似值。它將被寫成：

(S * -Q) × +/ (J ! Q - ι + J) × F X - (J <- -ι + ιN) × S ÷ (X - A) ÷ N

在上述表達式中，參數 Q 如果為正，則指定微分的階數；如果為負，則指定積分（從 A 到 x）的階數。分數值給出分數微分和積分，並且以下函數通過先定義函數 φ 並給予 A 和 S 適當的值，可以用於對 [ι6] 中討論的微分進行數值實驗：

QD: (S*-Q)x+/(J!Q-ι+J)xF M-(J<- -ι+ιN)xS÷(M-A)÷N

儘管數學符號中大量使用了「形式化」操作，但通過顯式算法進行真正的形式化操作非常困難。APL 在這方面更易於處理。例如，在第 2 節中，我們看到多項式表達式 (x ∘ .* -ι + ιρc) +.× c 的微分由 (x ∘ .* -ι + ιρc) +.× ι ↓ c × -ι + ιρc 給出，Orth 在他的微積分處理 [ι3] 中給出的用於形式化微分 APL 表達式的一組函數佔不到一頁。其他形式化操作函數的例子出現在 [ι7, p.347] 中向量微積分的建模運算符中。

關於與數學符號關係的進一步討論可以在 [3] 和論文「Algebra as a Language」[6, p.325] 中找到。關於印刷的最後評論，這在傳統符號中一直是一個嚴重的問題。儘管 APL 確實使用了一些出版商尚未普遍提供的符號，但它僅使用 88 個基本字元，再加上一些由基本字元對疊加形成的複合字元。此外，它不要求像下標和上標中使用下劃線和較小字體那樣的要求。

5.2 符號的引入

開頭，上下文引入符號的容易程度被認為是衡量符號適用性的一個標準，並請讀者觀察引入 APL 的過程。此標準的實用性可能被接受為不言而喻，但它需要一些澄清。

首先，對於某個特定主題，如果有一種完全提供該主題所需函數的特定符號，那它就很容易在上下文中引入。必須進一步詢問所需的符號總量、符號結構的程度以及為特定目的引入的符號的通用程度等問題。

其次，區分描述和學習一個符號的難度與掌握其含義的難度非常重要。例如，學習計算矩陣乘積的規則很簡單，但掌握其含義（如其結合性、對加法的分配性以及表示線性函數和幾何操作的能力）則是一個不同且更困難的問題。

事實上，符號的啟發性本身可能使其看起來更難學，因為它提示了許多可供探索的屬性。例如，+.× 用於矩陣乘積的符號不能使計算其規則變得更難學，因為它至少提醒人們這個過程是乘積的總和，但是用這個符號討論矩陣乘積的屬性不可避免地會提出許多問題，例如：∨.∧ 是結合的嗎？它對什麼進行分配？B ∨.∧ C <--> ~(~C) ∧.∨ ~B 是一個有效的恆等式嗎？

5.3 APL 的擴展

為了確保本文使用的符號是定義良好且在現有電腦系統上廣泛可用，其範圍已限制在 [4] 中定義的現行 APL 以及由 ACM SIGPLAN 技術委員會 STAPL 發布的更正式標準 [ι7, p.409]。我們現在將簡要評論可能增加其處理本文主題便利性並增強其處理其他主題（如普通微積分和向量微積分）適用性的潛在擴展。

一種擴展類型已經通過展示範例（多項式的根）在基於複數的 APL 系統上的執行來暗示。這意味著函數符號沒有變化，儘管某些函數的領域將不得不擴展。例如，|x 將給出複數和實數參數的量值，+x 將給出複數參數的共軛以及它目前對實數參數給出的平凡結果，並且基本函數將適當地擴展，如前述範例中使用 ∘ 所暗示的。這也意味著有可能有意義地包含多項式零點以及矩陣特徵值和特徵向量的基本函數。

第二種擴展類型也由前幾節暗示，包括為特定目的定義但顯示出通用實用性的函數。示例包括由 D.3 定義的 nub 函數 N 和由 D.4 定義的總結函數 S。這些和其他擴展在 [ι8] 中進行了討論。

McDonnell [ι9, p.240] 提出了將 AND 和 OR 推廣到非布林值的建議，以便 A ∨ B 是 A 和 B 的 GCD，而 A ∧ B 是 LCM。第 3 節中定義的函數 GCD 和 LCM 就可以簡單地定義為 GCD: ∨/ ω 和 LCM: ∧/ ω。

更普遍的發展方向涉及運算符，前幾節中通過約化、內積和外積進行了說明。APL 中現有運算符的討論可以在 [20] 和 [ι7, p.ι29] 中找到，向量微積分建議的新運算符在 [ι7, p.47] 中進行了討論，其他運算符在 [ι8] 和 [ι7, p.ι29] 中進行了討論。

5.4 呈現模式

前幾節的處理涉及一系列簡要主題，強調清晰性而非所得算法的效率。這兩點都值得進一步評論。

對某個更完整主題（範圍足以用於例如一或兩學期課程）的處理，提供了與符號不同的，或許更真實的檢驗。特別是，它提供了更準確衡量在常規課程中引入符號量的標準。

APL 在許多主題中的此類處理是可用的，包括：高中代數 [6]、初等分析 [5]、微積分 [ι3]、數位系統設計 [2ι]、電阻電路 [ι0] 和晶體學 [22]。所有這些都表明了引入所需符號的容易程度，並且其中一個提供了關於其使用經驗的評論。Blaauw 教授在討論數位系統設計 [2ι] 時說：「APL 使描述複雜系統中實際發生的情況成為可能」，「APL 特別適合此目的，因為它允許在高級架構級別、最低實現級別以及之間的所有級別上表達」，並且「...學習這種語言在計算機設計領域內外都有回報（原文如此）」。

電腦和程式語言的使用者通常主要關心算法執行的效率，因此可能會輕易否定這裡呈現的許多算法。這種否定是短視的，因為對算法的清晰陳述通常可以作為基礎，從中可以輕鬆推導出更高效的算法。例如，在第 3.2 節的函數 RFC 中，通過進行諸如 ι ⍢ M 代替 (⍢α) +.× β 的替換，可以顯著提高效率，而在使用表達式 +/ C × X * -ι + ιρC 時，可以替換為 X ∘ .P C 或，如果採用相反的係數順序約定，表達式 X ∘ .P C。

也可以進行更複雜的轉換。例如，Kerner 的方法（C.3）是由一個相當明顯（儘管未形式化陳述）的恆等式得出的。類似地，在獲取深度優先生成樹（C.4）中使用的遞歸函數 R 中，使用矩陣表示排列可以替換為可能更緊湊地使用節點列表，以相當明顯（儘管不完全形式化）的方式用索引替換內積。此外，這種遞歸定義可以轉換為更高效的非遞歸形式。

最後，任何用陣列清晰表達的算法，都可以通過簡單但繁瑣的修改轉換為可能更高效的使用標量元素迭代的算法。例如，+/ x 的求值取決於 x 的每個元素，並且不能進行多少改進，但是 ∨/ B 的求值可以在第一個等於 ι 的元素處停止，並且可能通過使用索引表達的迭代算法來改進。

先清楚準確地定義一個過程而不考慮效率，然後將其用作指導和測試，以探索具有其他特性（例如更高效率）的等效過程，這在數學中非常常見。這是一個非常富有成效的實踐，不應因過早強調計算機執行的效率而受到影響。

效率的衡量通常是不現實的，因為它們關注的是「實質性」函數（如乘法和加法）的計數，而忽略了通常因較不直接的算法而大大增加的內務處理（索引和其他選擇過程）。此外，現實的衡量強烈依賴於當前電腦和語言實現的設計。例如，由於發現布林值上的函數（如 ∧/ B 和 ∨/ B）在 APL 中大量使用，實現者為它們提供了高效的執行。最後，過分強調效率會導致設計上的不幸循環：出於效率原因，早期的程式語言反映了早期電腦的特性，而每一代電腦都反映了前一代程式語言的需求。 464

致謝：我感謝我的同事 A.D. Falkoff 在組織本文方面提供了很大的幫助，以及 Donald McIntyre 教授在閱讀初稿時提供的建議。

附錄 A. 符號摘要

附錄 B. 從直接形式到標準形式的編譯器

此編譯器改編自 [22, p.222]。它無法處理包含 α 或 ω 或 : 在引號中的定義。它由函數 FIX 和 EG，以及字元矩陣 C9 和 A9 組成：

∇ R ← FIX α
[ι] ρDFX F9
[2] D←F9 E;F;I;K
[3] F←(,(E='α')∘.~5÷ι)/,E,(¢4,ρE)ρ'α9'
[4] F←(,(F='ω')∘.~5÷ι)/,F,(¢4,ρF)ρ'ω9'
[5] F←ι+ρD←(0,+/-6,I)+(-(3×I)++\I←':'=F)¢F,(¢6,ρF)∘.''
[6] D←3 3 ⍢ C9[I+(ι+'α'∊E),I,0;],⍢D[;ι,(I÷2+ιF),2]
[7] K←K+2×K<I←K←I∧K←(>/I←0 ∊'÷D'∘.=E)/K←+\~I←E∊A9
[8] F←(0,ι+ρE)[ρD←D,(F,ρE)+~0 ¯24K←' ',E,[ι.5]';']
[9] D←(FρD),[ι]F[2]
[ι0] '∇',E
[ιι] R←D
∇

∇ R ← ω EG α
[ι] R ← α EGM ω ; S
[2] S ← A9 [ ; ι + α ]
[3] S ← (ιEG ιι+ρS) ρ S
[4] R ← ∨ / S ∧ ω ∘ .= ι + ιρω
∇

C9

∇  R  ←  α  ω  β
∇  R  ←      ω  β
∇  R  ←  α  ω

A9

+ - × ÷ * | ⌊ ⌈ ∘ ! ⍢ ? ⊢ ⊣
< ≤ = ≥ > ≠ ∨ ∧ ~ ∈ ρ , ¢ ↑ ↓
ι 0 . : ; ← ' ' ( ) [ ]

ω9Z9 ← α9

ω9Z9 ← 0ι23456789ABCDEFGH

α9Z9 ← ω9Z9

α9Z9 ← IJKLMNOPQ

Z9 ← RSTUVWXYZ

範例：

FIX 'FIB: Z,+/-2÷Z÷FIB~-ι:~=ι:ι'

FIB ι5

ι ι 2 3 5 8 ι3 2ι 34 55 89 ι44 233 377 6ι0

)DCR 'FIB'

∇Z9←ω9FIB α9
[ι]→(0=ι+ω9=ι)/3
[2]→0∘.0ρZ9←ι
[3]Z9←Z,+/-2÷Z←ω9FIB ω9-ι
∇

參考資料

1. Boole, G. An Investigation of the Laws of Thought, Dover Publications, N.Y., ι95ι. 最初於 ι954 年由 Walton and Maberly, London 和 MacMillan and Co., Cambridge 出版。也可在 George Boole 邏輯作品集第二卷中找到，Open Court Publishing Co., La Salle, Illinois, ι9ι6。
2. Cajori, F. A History of Mathematical Notations, Volume II, Open Court Publishing Co., La Salle, Illinois, ι929。
3. Falkoff, A.D., and Iverson, K.E. The Evolution of APL, Proceedings of a Conference on the History of Programming Languages, ACM SIGPLAN, ι978。
4. APL Language, Form No. GC26-3847-4, IBM Corporation.
5. Iverson, K.E. Elementary Analysis, APL Press, Pleasantville, N.Y., ι976。
6. Iverson, K.E. Algebra: an algorithmic treatment, APL Press, Pleasantville, N.Y., ι972。
7. Kerner, I.O. Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen, Numerische Mathematik, Vol. 8, ι966, pp. 290-294。
8. Beckenbach, E.F., ed. Applied Combinatorial Mathematics, John Wiley and Sons, New York, N.Y., ι964。
9. Tarjan, R.E, Testing Flow Graph Reducibility, Journal of Computer and Systems Sciences, Vol. 9 No. 3, Dec. ι974。
10. Spence, R. Resistive Circuit Theory, APL Press, Pleasantville, N.Y., ι972。
11. Iverson, K.E. A Programming Language, John Wiley and Sons, New York, N.Y., ι962。
12. Iverson, K.E. An Introduction to APL for Scientists and Engineers, APL Press, Pleasantville, N.Y.
13. Orth, D.L. Calculus in a new key, APL Press, Pleasantville, N.Y., ι976。
14. Apostol, T.M. Mathematical Analysis, Addison Wesley Publishing Co., Reading, Mass., ι957。
15. Jolley, L.B.W. Summation of Series, Dover Publications, N.Y.
16. Oldham, K.B., and Spanier, J. The Fractional Calculus, Academic Press, N.Y., ι974。
17. APL Quote Quad, Vol. 9, No. 4, June ι979, ACM STAPL。
18. Iverson, K.E., Operators and Functions, IBM Research Report RC 709ι, ι978。
19. McDonnell, E.E., A Notation for the GCD and LCM Functions, APL 75, Proceedings of an APL Conference, ACM, ι975。
20. Iverson, K.E., Operators, ACM Transactions on Programming Languages And Systems, October ι979。
21. Blaauw, G.A., Digital System Implementation, Prentice-Hall, Englewood Cliffs, N.J., ι976。
22. McIntyre, D.B., The Architectural Elegance of Crystals Made Clear by APL, An APL Users Meeting, I.P. Sharp Associates, Toronto, Canada, ι978。

465

通訊 ACM 通訊 1980 年 8 月 第 23 卷 第 8 期