AWK本の60行で書かれたMake
原文は Ben Hoyt により に公開されました。 このブログを購読する
名著『The AWK Programming Language』（Aho、Weinberger、Kernighan著）の第7章の末尾には、数ページにわたってMakeユーティリティを簡略化したバージョンが紹介されています。わずか1ページのAWKコードで書かれたものです。
その中身を見る前に、まずお知らせがあります。AWK本の第2版が来月発売されます。ブライアン・カーニハンが素晴らしいアップデートを施しており、特に探索的データ解析に関する新しい章が追加され、それを実現するためにAWKに本格的なCSVサポートが追加されています。私は光栄にも第2版の草稿のレビューを依頼されました。
AWKは2023年においてもデータ探索の分野でいまだに輝きを放っており、特に新しい--csvオプションによってその魅力は増しています。CSVモードは最も広く使われているAWKであるGawk（GNU AWK）にも追加されました。私自身の実装であるGoAWKは以前から本格的なCSVサポートを備えており、他の実装に合わせて--csvオプションを追加しています。
第2版でもMakeプログラムは引き続き収録されていますが、「空白と波括弧」の追加によって読みやすさが向上し、行数は50行から62行になりました。
この記事ではそのMakeプログラムを紹介し、AWKがワンライナーに優れているだけでなく、スクリプト言語としても使えることを示します。もっとも、使うべきかどうかは別の話ですが。
その後、同じプログラムをPythonで書くとどうなるかを比較し、この種の用途でAWKとPythonのどちらを選ぶべきかについても簡単に考察します。
言うまでもないことですが、これはあくまで学習のための試みであり（私自身にとっても読者の皆さんにとっても）、実際のプロジェクトのビルドに使うことを推奨するものではありません！
オリジナルのAWK版
第2版ではMakeプログラムが次のように紹介されています。（余談ですが、ここでの「target」という用語は紛らわしいと感じます。「source」や「dependency」の方が適切だと思います。）
この節では、前節で扱った深さ優先探索の手法に基づいて、Unixの
makeコマンドをモデルにした初歩的な更新プログラムを作成する。このupdater（更新プログラム）を使うには、システムを構成する要素が何であるか、それらがどのように相互に依存しているか、そしてそれらを構築するために必要なコマンドは何かを明示的に記述しなければならない。これらの依存関係とコマンドは、
makefileと呼ばれるファイルに、以下の形式のルールを並べて記述するものと仮定する。name: t1 t2 ... tn commandsルールの1行目は依存関係を表し、プログラムやファイルnameがターゲットt1、t2、…、tnに依存することを示す。ここで各tiはファイル名か、別のnameである。各依存関係の後に、nameを生成するために必要なコマンドを列挙したcommandsの行が1行以上続くこともある。以下に、
a.cとb.cという2つの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に依存することを示している。2行目は、progがCコンパイラのコマンドgccを使ってa.o、b.o、c.oとyaccライブラリyをリンクしてファイルprogにまとめることで生成されることを示す。次のルール（3行目）は、a.oがターゲットであるprog.hとa.cに依存し、これらのターゲットをコンパイルすることで作成されることを示しており、b.oも同様である。ファイルc.oはc.cに依存し、c.cはさらにc.yに依存するが、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を大幅に簡略化したものですが、それでも出力、依存関係、ビルドコマンドという中核的な概念は備えています。
仕組みを見る前に、第2版に掲載されている通りの完全なソースコードを以下に示します。太字のテキストをクリックすると展開できます。コードの詳細な解説は「仕組み」の節までスキップしてください。
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を開き、最後まで1行ずつ読み込みます。行（$0）が文字で始まる場合（/^[A-Za-z]/）、それはname: targetsというルールとみなされます。
sub(/:/, "")の呼び出しは、現在の行からコロンを取り除きます（2引数形式のsubでは$0は暗黙的に指定されます）。
次に、names配列をチェックして、このルールがまだ定義されていないことを確認します。AWKの配列は実際には連想配列であり、キーと値のマップを指す昔ながらの呼び方です。
内側のforループは、各ターゲット（依存関係）をslist／scntというデータ構造に追加します。これは本来はリストのマップですが、AWKがネストしたコレクションをサポートしていないことを回避するため、平坦化されています。ループ本体は非常に簡潔です。
for (i = 2; i <= NF; i++)
slist[nm, ++scnt[nm]] = $iこれは各依存関係をループで処理します。フィールド2からNF（行のフィールド数）までのすべてのフィールド$iを対象にします。
各依存関係について、現在のルール（nm）のソース数であるscnt[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話を戻すと、行がタブで始まる場合はコマンドとみなされ、その名前のコマンド文字列に追記します。
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の癖（カーニハン自身が悔やんでいる点）で、ローカル変数を定義する唯一の方法が関数パラメータとして宣言することであり、関数がパラメータ数より少ない引数で呼び出された場合、余ったパラメータはデフォルト値（数値なら0、文字列なら""）を取ります。そのため、AWKの関数定義ではこのような余分な空白をよく見かけます。
次の点はなかなか巧妙です。AWKはシェルのような|構文をサポートしており、プログラムの出力をgetline1回ごとに変数（ここでは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ルールのように、更新対象のルールに依存関係が指定されていない場合を扱います。この場合は常にそのコマンドを再実行します。
これで完成です！1ページのAWKで書かれた最小限のMakeです。
Python版
興味深い試みとして、本書のAWK版MakeをPythonに移植したものを以下に示します。こちらも太字のテキストをクリックするとプログラムを展開できます。
Makeプログラムの私によるPython移植版（完全なソースコード）
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版とよく似ていますが、理解しやすくなるように2つの簡略化を加えました。
slist／scntの扱いにくさを避けるため、よりシンプルなデータ構造にしました。Pythonではリストの辞書をそのまま使えます。（差分を見る）ls -tのトリックを使うのではなく、os.stat()でファイルの更新時刻（mtime）を直接取得するようにして、経過時間の判定をより直接的にしました。これによりageマップやages関数も不要になります。（差分を見る）
狙ったわけではありませんが、import行やif __name__ == '__main__'のお決まりの記述を含めても58行で、AWKプログラムとほぼ同じ長さになりました。
Python版を作っているときに、AWK版でも同様に簡略化できることに気づきました。
slistを直接AWKの配列として保存する方が概念的にシンプルです。キーがルール名、値が依存関係のリストを空白区切りの文字列（makefileと同じ形式）で持つキー・バリューのマップです。必要に応じてsplitを使って依存関係の文字列をリスト（1から依存関係の数までの配列）に変換できます。これによりscntやnamesがまったく不要になります。（差分を見る）- Python版と同様に、
ls -tですべてのファイルを経過時間順に一覧する代わりに、statを呼び出してmtimeを直接取得できます。ここではstat --format %yを使っています。これはGNU拡張だと思いますので、ls -tほど移植性は高くありませんが、よりシンプルでage配列を再計算する必要がなくなります。（差分を見る）
追記：Volodymyr Gubarkov氏が、stat版は「外部プロセスの呼び出しが複数回増える」と指摘してくれましたが、その通りです。より直接的ではありますが、かなり遅くなります。
ちなみに、修正版はオリジナルより4行短くなっています。よりシンプルなslistの方が明確だと思いますし、mtimeをより直接的に取得するアプローチも気に入っています。ただ、stat --formatの移植性の低さは欠点だと認識しています（macOSのstatはかなり異なります）。
結論
AWKのMakeプログラムは、中規模のスクリプトでさえAWKという言語がいかに有用であるかを示す、巧妙でコンパクトなコードです。
ただし、この種の用途にはPythonの方が間違いなく適した言語です。はるかに豊富なデータ型、os.statのような優れたツール、そして癖のないローカル変数の構文を備えています。
私はAWKを素晴らしい言語だと考えていますが、やはり得意分野に留まるべきだと思います。すなわち、探索的データ解析や、ワンライナーでのデータ抽出スクリプトです。
以前からネイティブなCSVサポートを備えたGoAWKの作者として、カーニハンの「one true AWK」とGawkの両方が--csvオプションという形で本格的なCSVサポートを獲得したことを特に嬉しく思っています。カーニハンのAWKのアップデートは間もなくマージされる予定で、Gawkも間もなくリリースされるバージョン5.3.0でこの機能を含む予定です。
AWK本のMakeプログラムと私のPython版の完全なソースコード、さらにAWK本の例に基づいた実行可能なサンプルプロジェクトを含む、私のawkmakeリポジトリもGitHubでご覧いただけます。
コメント
ログインしてコメントする