《AWK 程式語言》中的 60 行 Make 版本
在 Aho、Weinberger 與 Kernighan 合著的精彩著作 The AWK Programming Language 中，第 7 章最後幾頁展示了一個簡化版的 Make 工具——以單頁的 AWK 程式碼寫成。
在深入探討之前，我想先提一下，AWK 一書的第二版將於下個月出版。Brian Kernighan 在更新方面做得非常出色，最值得注意的是新增了一章關於探索式資料分析的內容，並為 AWK 加入了完整的 CSV 支援來實現這個主題。我很榮幸受邀審閱第二版的草稿。
即便到了 2023 年，AWK 在探索資料方面依然表現亮眼，尤其是有了新的 --csv 選項。CSV 模式也已加入 Gawk（GNU AWK）——這是安裝最為廣泛的 AWK 版本。我自己的 GoAWK 實作也已有一段時間具備完整的 CSV 支援，而我也新增了 --csv 選項以與其他版本保持一致。
這本書的第二版仍然收錄了這個 Make 程式，不過透過加入一些「空格與大括號」讓它變得更易讀——這使得程式從 50 行增加到 62 行。
本文將介紹這個 Make 程式，藉此說明 AWK 不僅擅長撰寫單行指令（one-liner），也可以作為腳本語言使用——不過你是否應該這麼做，就是另一回事了。
接著，我會比較同樣的程式用 Python 寫出來會是什麼樣子，並簡要討論在這類情境下，你會在什麼時候選擇 AWK 或 Python。
這應該不用多說，但我寫這篇純粹是作為一個學習練習（對我與讀者而言），並不是要推薦你用這個程式來建置專案！
原始的 AWK 版本
這本書的第二版是這樣介紹這個 Make 程式的。（順帶一提，我覺得這裡的「target」一詞容易讓人混淆——我認為用「source」或「dependency」會更貼切。）
本節將開發一個簡易的更新程式，其設計仿照 Unix 的
make指令，並以奠基於前一節的深度優先搜尋技術為基礎。要使用這個更新程式，必須明確描述系統由哪些元件組成、它們彼此之間如何相依，以及建構它們需要哪些指令。我們假設這些相依關係與指令儲存在一個名為
makefile的檔案中，其中包含一系列形式如下的規則name: t1 t2 ... tn commands規則的第一行是一個相依關係，說明程式或檔案name 相依於目標 t1、t2、…、tn，其中每個 ti 都是一個檔名或另一個 name。在每個相依關係之後，可能會有一或多行commands，列出產生 name 所需的指令。以下是適用於一個包含兩個 C 檔案
a.c與b.c以及一個yacc文法檔c.y的小型程式的makefile範例，這是典型的程式開發應用。prog: a.o b.o c.o gcc a.o b.o c.o -ly -o prog a.o: prog.h a.c gcc -c prog.h a.c b.o: prog.h b.c gcc -c prog.h b.c c.o: c.c gcc -c c.c c.c: c.y yacc c.y mv y.tab.c c.c print: pr prog.h a.c b.c c.y第一行指出
prog相依於目標檔案a.o、b.o與c.o。第二行表示prog是透過使用 C 編譯器指令gcc將a.o、b.o、c.o與yacc函式庫y連結成檔案prog而產生。下一條規則（第三行）指出a.o相依於目標prog.h與a.c，並透過編譯這些目標來產生；b.o亦同。c.o相依於c.c，而c.c又相依於c.y，後者必須經由yacc解析器產生器處理。最後，名稱make總是會執行相關的動作，在此例中即是以pr指令列印所有原始檔。在
makefile中的相依關係可以用一個圖來表示，其中每當有一條相依規則在左側為 x、右側的其中一個目標為 y 時，就會有一條從節點 x 到節點 y 的邊。對於沒有目標的規則，則會建立一個沒有後繼節點、以左側名稱為名的節點。對於上述的makefile，我們得到以下的相依圖：prog print / | \ / | \ a.o b.o c.o / \ / \ \ / \/ \ \ a.c prog.h b.c c.c | c.y
當然，這是一個高度簡化的 Make 版本，但仍具備輸出、相依關係與建置指令等核心概念。
在說明它的運作原理之前，我在下方附上了完整的原始碼，其內容與 AWK 一書第二版中的呈現方式相同。點擊粗體文字即可展開，或直接跳至「運作原理」一節查看詳細的程式碼解說。
AWK 一書中的 Make 程式（完整原始碼）。
BEGIN {
while (getline <"makefile" > 0) {
if ($0 ~ /^[A-Za-z]/) { # $1: $2 $3 ...
sub(/:/, "")
if (++names[nm = $1] > 1)
error(nm " is multiply defined")
for (i = 2; i <= NF; i++) # remember targets
slist[nm, ++scnt[nm]] = $i
} else if ($0 ~ /^\t/) { # remember cmd for
cmd[nm] = cmd[nm] $0 "\n" # current name
} else if (NF > 0) {
error("illegal line in makefile: " $0)
}
}
ages() # compute initial ages
if (ARGV[1] in names) {
if (update(ARGV[1]) == 0)
print ARGV[1] " is up to date"
} else {
error(ARGV[1] " is not in makefile")
}
}
function ages( f,n,t) {
for (t = 1; ("ls -t" | getline f) > 0; t++)
age[f] = t # all existing files get an age
close("ls -t")
for (n in names)
if (!(n in age)) # if n has not been created
age[n] = 9999 # make n really old
}
function update(n, changed,i,s) {
if (!(n in age))
error(n " does not exist")
if (!(n in names))
return 0
changed = 0
visited[n] = 1
for (i = 1; i <= scnt[n]; i++) {
if (visited[s = slist[n, i]] == 0)
update(s)
else if (visited[s] == 1)
error(s " and " n " are circularly defined")
if (age[s] <= age[n])
changed++
}
visited[n] = 2
if (changed || scnt[n] == 0) {
printf("%s", cmd[n])
system(cmd[n]) # execute cmd associated with n
ages() # recompute all ages
age[n] = 0 # make n very new
return 1
}
return 0
}
function error(s) { print "error: " s; exit }運作原理
書中已有關於這個程式如何運作的說明，不過在這裡我會用自己的話來解釋，並聚焦在我覺得有意思的部分。
BEGIN 區塊是這類程式的主要進入點。與大多數隱含地從標準輸入讀取資料的 AWK 程式不同，這個程式使用一個明確的 getline 迴圈來讀取 makefile：
BEGIN {
while (getline <"makefile" > 0) {
if ($0 ~ /^[A-Za-z]/) { # $1: $2 $3 ...
sub(/:/, "")
if (++names[nm = $1] > 1)
error(nm " is multiply defined")
for (i = 2; i <= NF; i++) # remember targets
slist[nm, ++scnt[nm]] = $i
} else if ($0 ~ /^\t/) { # remember cmd for
cmd[nm] = cmd[nm] $0 "\n" # current name
} else if (NF > 0) {
error("illegal line in makefile: " $0)
}
}
...
}getline <filename 是一個重新導向子句，會在第一次時開啟 makefile，並逐行讀取直到結尾。如果該行（$0）以字母開頭（/^[A-Za-z]/），就會被視為一條 name: targets 規則。
sub(/:/, "") 這個呼叫會從目前這一行移除冒號（在雙參數形式的 sub 中，$0 是隱含的）。
接著，我們透過檢查 names 陣列來確保這條規則尚未被定義過。AWK 的陣列其實是一種關聯陣列，這是鍵值對映（key-value map）的舊稱。
內層的 for 迴圈會將每個目標（或相依項目）加入 slist／scnt 資料結構。這實際上是一個由串列組成的對映，但為了因應 AWK 不支援巢狀集合的限制而被扁平化。迴圈的主體非常精簡：
for (i = 2; i <= NF; i++)
slist[nm, ++scnt[nm]] = $i這會遍歷每個相依項目：從第 2 個欄位到 NF（該行的欄位數）的每一個欄位 $i。
對於每個相依項目，它會遞增 scnt[nm]，也就是目前規則（nm）的來源數量。然後，將相依項目 $i 儲存在 slist 中，以多重鍵的名稱與計數作為索引。AWK 透過建立一個以 SUBSEP 分隔符（預設為 "\x1c"）串接而成的鍵來模擬多維或多重鍵陣列。
在迴圈結束後，以 prog 為例，slist 與 scnt 會呈現如下：
slist
a.o,1: prog.h
a.o,2: a.c
b.o,1: prog.h
b.o,2: b.c
c.c,1: c.y
c.o,1: c.c
prog,1: a.o
prog,2: b.o
prog,3: c.o
scnt
a.o: 2
b.o: 2
c.c: 1
c.o: 1
prog: 3回到上層，如果該行以 tab 開頭，它就是一條指令，因此我們會將它附加到該名稱的指令字串中：
cmd[nm] = cmd[nm] $0 "\n"否則，如果該行不是空白行（NF > 0），那就是 makefile 的錯誤。
最後，在 while 迴圈中讀完 makefile 之後，我們會使用 ages() 來計算當前目錄中所有檔案的新舊程度，然後呼叫 update(ARGV[1]) 來更新從命令列傳入的規則：
BEGIN {
...
ages() # compute initial ages
if (ARGV[1] in names) {
if (update(ARGV[1]) == 0)
print ARGV[1] " is up to date"
} else {
error(ARGV[1] " is not in makefile")
}
}ages 函式是開始變得有趣的地方：
function ages( f,n,t) {
for (t = 1; ("ls -t" | getline f) > 0; t++)
age[f] = t # all existing files get an age
close("ls -t")
for (n in names)
if (!(n in age)) # if n has not been created
age[n] = 9999 # make n really old
}參數名稱 f、n 與 t 前面有許多空格，用來表示它們實際上是區域變數，而非預期的引數。這是 AWK 的一個怪癖（Kernighan 對此感到後悔）：定義區域變數的唯一方式是將其作為函式參數，如果呼叫函式時傳入的引數少於參數數量，多餘的參數就會取預設值（數值為 0，字串為 ""）。所以你會在 AWK 的函式定義中經常看到這些額外的空格。
接下來這點相當巧妙：AWK 支援類似 shell 的 | 語法，可將程式的輸出一次一行地透過 getline 導向至變數（在此例中為 f）。ls -t 指令會列出當前目錄中的檔案，並依修改時間排序，最新的排在最前面。
在將每個檔案的新舊程度指派給 age[f] 的迴圈結束後，我們會呼叫 close 來關閉 ls -t 的管線，以避免開啟過多的檔案代碼。
最後，我們遍歷規則名稱，並為 age[n] 指派一個任意的大數值，假裝那些尚未被建立的檔案非常老舊、需要更新。
接下來是遞迴的 update 函式，這是整個演算法的核心所在：
function update(n, changed,i,s) {
if (!(n in age))
error(n " does not exist")
if (!(n in names))
return 0
changed = 0
visited[n] = 1
for (i = 1; i <= scnt[n]; i++) {
if (visited[s = slist[n, i]] == 0)
update(s)
else if (visited[s] == 1)
error(s " and " n " are circularly defined")
if (age[s] <= age[n])
changed++
}
visited[n] = 2
if (changed || scnt[n] == 0) {
printf("%s", cmd[n])
system(cmd[n]) # execute cmd associated with n
ages() # recompute all ages
age[n] = 0 # make n very new
return 1
}
return 0
}同樣地，你會注意到參數列表：n 是預期的引數（要更新的名稱），而 changed,i,s 則是區域變數。
在通過初始檢查後，我們透過從 slist[n, 1] 迭代到 slist[n, scnt[n]] 來遍歷相依項目列表。如果這個相依項目尚未被造訪過，我們會透過遞迴呼叫 update 對相依圖進行深度優先遍歷，以先確認是否需要更新該相依項目：
if (visited[s = slist[n, i]] == 0)
update(s)遞迴會在頂部附近的 if (!(n in names)) return 0 區塊中終止。當要更新的檔案不在規則名稱列表中時，我們就會停止——這在相依圖中即是一個葉節點。
if (age[s] <= age[n]) changed++ 這個區塊會在任何相依項目的新舊程度比目前正在更新的檔案還新時，遞增 changed 的計數。
在遍歷迴圈結束後，如果任何相依項目或子相依項目曾發生變更，我們就會使用 system() 執行相關的指令，重新計算所有檔案的新舊程度，並 return 1 給呼叫者以表示我們確實進行了更新。
scnt[n] == 0 這個子句處理的是要更新的規則未指定任何相依項目的情況，就像範例中的 print 規則一樣。在這種情況下，總是重新執行其指令。
就是這樣！一個用一頁 AWK 寫成的極簡 Make。
Python 版本
出於興趣，我將書中的 AWK Make 移植到了 Python，並附在下方。同樣地，點擊粗體文字即可展開程式。
我移植的 Python 版 Make 程式（完整原始碼）。
import os, re, sys
slist = {} # slist[name] is list of rule's sources
cmd = {} # cmd[name] is shell command to run for rule
def main():
for line in open('makefile'):
if re.match('[A-Za-z]', line):
line = line.replace(':', '')
fields = line.split()
nm = fields[0]
if nm in slist:
error(f'{nm} is multiply defined')
slist[nm] = fields[1:] # remember targets
elif line.startswith('\t'): # remember cmd for current name
cmd[nm] = cmd.get(nm, '') + line
elif line.strip():
error(f'illegal line in makefile: {line}')
if sys.argv[1] in slist:
if not update(sys.argv[1]):
print(sys.argv[1], 'is up to date')
else:
error(f'{sys.argv[1]} is not in makefile')
def mtime(n):
try:
return os.stat(n).st_mtime
except FileNotFoundError:
return 0 # mark as old if it doesn't exist
def update(n, visited={}):
ntime = mtime(n)
if n not in slist and ntime == 0:
error(f'{n} does not exist')
if n not in slist:
return 0
changed = False
visited[n] = 1
for s in slist.get(n, []):
if s not in visited:
update(s)
elif visited[s] == 1:
error(f'{s} and {n} are circularly defined')
if mtime(s) > ntime:
changed = True
visited[n] = 2
if changed or len(slist.get(n, [])) == 0:
print(cmd[n], end='')
os.system(cmd[n]) # execute cmd associated with n
return 1
return 0
def error(msg):
print('error:', msg, file=sys.stderr)
sys.exit(1)
if __name__ == '__main__':
main()它在結構上與原始的 AWK 版本非常相似，不過我做了兩項簡化，我認為這讓它稍微更容易理解：
- 更簡單的資料結構，以避免
slist／scnt的繁瑣——在 Python 中我們可以直接使用由串列組成的字典（dictionary of lists）。（查看差異。） - 使用
os.stat()直接取得檔案的修改時間（mtime）來更直接地判斷新舊程度，而非使用ls -t的技巧。這也省去了對age對映與ages函式的需求。（查看差異。）
這並非刻意為之，但即使把 import 那一行與 if __name__ == '__main__' 這段慣用寫法算進去，它也只有 58 行程式碼——基本上與 AWK 程式長度相同。
在製作 Python 版本時，我意識到我們也可以用類似的方式簡化 AWK 版本：
- 在概念上，將
slist直接儲存為 AWK 陣列會更簡單：一個鍵值對映，其中鍵是規則名稱，而值是以空格分隔的相依項目字串（就像在makefile中一樣）。我們可以視需要使用split將相依字串轉換為串列（一個從 1 到相依項目數量的陣列）。這樣就能完全省去對scnt與names的需求。（查看差異。） - 與 Python 版本類似，我們可以透過直接呼叫
stat來取得 mtime，而非用ls -t將所有檔案依新舊程度列出。我已使用stat --format %y來做到這一點。我認為這是 GNU 的擴充功能，因此可攜性不如ls -t，但它更簡單，也省去了重新計算age陣列的需要。（查看差異。）
更新：Volodymyr Gubarkov 指出 stat 版本「增加了多次外部行程的呼叫」，而他的說法完全正確。它或許更直接，但速度明顯慢了許多。
姑且不論，修改後的版本比原版少了四行。我認為更簡單的 slist 更清晰，而且我喜歡這種更直接地取得 mtime 的方式，儘管我也明白 stat --format 缺乏可攜性是一個缺點（macOS 的 stat 看起來截然不同）。
結論
AWK 的 Make 程式是一段精巧的程式碼，展示了 AWK 這個語言有多實用，即使是用來撰寫中等規模的腳本也一樣。
然而，Python 對於這類工作來說無疑是更棒的語言：它擁有豐富得多的資料型別、像 os.stat 這樣更完善的工具，以及不需要怪異語法的區域變數。
我認為 AWK 非常了不起，但我覺得它應該繼續留在它最擅長的領域：用於探索式資料分析，以及用於單行資料擷取腳本。
作為 GoAWK 的作者——GoAWK 早已原生支援 CSV——我特別樂見 Kernighan 的「正宗 AWK（one true AWK）」與 Gawk 都以 --csv 選項的形式獲得了完整的 CSV 支援。Kernighan 的 AWK 更新很快就會合併，而 Gawk 也將在 5.3.0 版中加入此功能，該版本也即將推出。
你也可以在 GitHub 上查看我的 awkmake 儲存庫，其中包含了 AWK 一書中的 Make 程式與我的 Python 版本的完整原始碼，以及一個基於書中範例、可實際執行的範例專案。
留言
登入後參與討論