以陣列語言思考：從指令式迴圈到隱式 K

在像 K 這樣的陣列語言中進行程式設計，不僅僅是學習新語法，更需要對問題解決的概念進行根本性的轉變。大多數開發者接受的是指令式思考的訓練——定義一系列步驟並透過迴圈和變數來管理狀態——而陣列語言則鼓勵一種宣告式的方法，將操作一次性應用於整個數據集合。

這種轉變通常被描述為一個持續簡化的過程。目標是將一個龐大、笨重的模式壓縮成一個更小、更具可讀性且更具宣告性的形式。為了說明這種演進，我們可以檢視一個經典演算法的轉換：矩陣乘法。

指令式翻譯的陷阱

當開發者第一次接觸 K 時，直覺往往是直接從 Wikipedia 或教科書將已知的演算法翻譯過來。對於矩陣乘法，迭代演算法非常直觀：

  1. 初始化結果矩陣 $C$。
  2. 遍歷 $A$ 的列 ($i$)。
  3. 遍歷 $B$ 的行 ($j$)。
  4. 使用第三個迴圈 ($k$) 計算 $A$ 的第 $i$ 列與 $B$ 的第 $j$ 行的點積。
  5. 將結果儲存在 $C_{ij}$ 中。

直接翻譯成 K 的樣子如下：

matmul: {
  A::x
  B::y
  n::#A
  m::#*A
  p::#*B
  C::(n;p)#0
  i::0
  j::0
  k::0
  sum::0
  {
    i::x
    {
      j::x
      sum::0
      {
        k::x
        sum::sum+A[i;k]*B[k;j] 
      }'!m
      C[i;j]::sum
    }'!p
  }'!n
  C}

這被認為是「最差情況」的 K 程式碼。它存在三個主要問題：過多的全域賦值、深層嵌套的迴圈，以及不斷地修改狀態。在陣列語言中，這些都是反模式。

簡化的路徑

改進這段程式碼涉及系統性地移除指令式的腳手架。

第一步：用 Fold 替換迴圈

與其手動管理 sum 變數和迴圈，K 提供了 fold 操作符 (/)。最內層的迴圈可以壓縮成單行：

C[i;j]::+/{ k::x; A[i;k]*B[k;j] }'!m

第二步：消除狀態與中間變數

因為 each 操作符 (') 會回傳陣列，因此不需要預先配置矩陣 $C$ 並修改它。嵌套的迴圈可以直接回傳其值：

{ i::x; { j::x; +/{ k::x; A[i;k]*B[k;j] }'!m }'!p }'!n

第三步：利用陣列配對

索引變數 $i$、$j$ 和 $k$ 本質上是中間人。透過識別出我們正在將 $A$ 的列與 $B$ 的行進行配對，我們可以完全消除 $k$ 迴圈：

{ j::x; +/A[i]*B[;j] }'!p }'!n

第四步：轉置與高階函數

為了移除剩餘的索引，我們可以轉置矩陣 $B$ 並使用 eachleft (/:) 和 eachright 來直接配對數據：

matmul: { A::x; B::y; A{+/x*y}/:\:+B }

最終形式：隱式程式設計

一旦全域變數消失了，程式碼可以進一步壓縮。透過移除昂貴的轉置操作並使用隱式對齊（K 會自動對齊不同形狀的陣列），函數變成了：

matmul: {x{+/x*y}\:y}

最後，透過應用「trains」（不帶顯式參數的函數組合）的規則，我們得到了終極的隱式版本：

matmul: (+/*)\:

對陣列語言的看法

雖然 K 的強大之處在於其簡潔，但它並非沒有爭議。社群經常將陣列語言與正規表示式進行比較：對於互動式探索和快速原型設計來說非常強大，但如果過度壓縮，可能會變成「僅能寫入」的程式碼。

正如一位 Hacker News 的觀察者所言：

我仍然沒有使用 K/Q/etc.，因為它們看起來很瘋狂...它們基本上是數學上的正規表示式。超級簡潔且強大。幾乎是僅能寫入的。對於互動式使用來說絕對非常有用。但如果你發現自己正在對一個正規表示式按下「儲存」，那這就是一個警訊...

儘管如此，「用 K 思考」的過程是一個模式簡化的旅程。透過從指令式轉向宣告式，開發者可以用幾個字元來表達複雜的數學運算，將焦點從「如何」計算，轉移到「計算的是什麼」。

Sources