しばしば見落とされがちですが, Makefileは立派な(=チューリング完全な)プログラミング言語です.
GNU Make, 3rd Edition([1], 以降make本と記します)をパラパラしながら読み終わりました.
最後の最後で, Makefileの中で｢数字の計算をする方法｣が書いてあり, あ, こりゃ, 僕がやるしか無いな, と思ってこのエントリーを書きました.
- 作者:Robert Mecklenburg
- 発売日: 2005/12/01
- メディア: 大型本
基本事項
Makefileの基本事項です. と言っても, 暗黙のルールとかマニアックな特殊ターゲットとかは今の僕にはあまり興味が無いです.
まず, Makefileをビシビシ書くにあたって, デバッグのために簡単に出力する方法を知って置かなければなりません. warning関数を使います. make本12.1に書かれているように, warningは何処におくことも出来る便利な関数です.
$(warning expression) $(warning $(variable-name))
あと, make言語自体で遊びたい時は,
all: @echo
とでもしておきましょう. 気休めですが. (このエントリーのMakefileのソースコードでは, インデントにスペースを用いている場所がありますが, 実際はタブで書いて下さい. 細かいことを言うと, このエントリーで扱うような, \で続けるような実質一行のコードでは, 別にスペースでもいいのですが, all: @echoのところの改行はスペースはアウトです. Hatenaのスーパーpre記法で, 複数タブインデントを用いたらおかしくなったのです.)
あと, Vimのquickrun.vimは, Makefileも実行できるようになっています. このエントリーを書くのに非常に役に立ちました. ありがとうございます.
変数代入
変数への代入は, = や := などがあります. 通常のスクリプト言語の代入に近いのが := の方です. 変数を後で参照するのは$(variable-name)です.
SOURCE := foo.c TARGET := foo $(TARGET): $(SOURCE) gcc $< -o $@
:= は, Makefileが上から読まれ, その行に来た瞬間評価されて代入されます. 一方, = は違います.
MAKE_DEPEND = $(CC) -M CC = gcc
= は評価が即座に行われません. 遅延評価されます. しかも, MAKE_DEPENDが欲しくなった｢その度に｣, $(CC)を探し, 結果gccが代入されます. よって
$(warning $(MAKE_DEPEND))
の出力は, gcc -M となります. もし
MAKE_DEPEND := $(CC) -M CC := gcc $(warning $(MAKE_DEPEND))
と書けばどうなるか？ 確認してみて下さい.
:= と = を注意しなくてはいけないのは, 例えば次のような場合でしょう.
DATE = $(shell date)
もし, この$(DATE)を複数回しようしていたら？ 危うい例の, 最も簡単な例を次に示します.
DATE = $(shell date) $(warning $(DATE)) $(shell sleep 5) $(warning $(DATE)) $(shell sleep 5) $(warning $(DATE)) $(shell sleep 5) $(warning $(DATE)) $(shell sleep 5) $(warning $(DATE)) $(shell sleep 5) $(warning $(DATE))
2012年 2月13日 月曜日 05時27分52秒 JST 2012年 2月13日 月曜日 05時27分57秒 JST 2012年 2月13日 月曜日 05時28分02秒 JST 2012年 2月13日 月曜日 05時28分07秒 JST 2012年 2月13日 月曜日 05時28分12秒 JST 2012年 2月13日 月曜日 05時28分17秒 JST
同じ$(DATE)を出力しているように見えるのに, その都度時間が更新されて行っているのが分かりますね. こういうのは := を使いましょう. と言うか, 普通 := を使いましょう. = は｢その都度｣展開されるので, makeが遅くなるボトルネックになりうると, make本10.2に書いてあります.
組み込み関数
Makefileでは実に豊富な関数が用意されています. 取り敢えず, make本に載ってるもの全部書いてみます.
$(filter pattern..., text) $(filter-out pattern..., text) $(findstring string, text) $(subst search-string, replace-string, text) $(patsubst search-string, replace-string, text) $(words text) $(word n, text) $(firstword text) $(wordlist start, end, text) $(sort list) $(shell command) $(wildcard pattern...) $(dir list...) $(notdir name...) $(suffix name...) $(basename name...) $(addsuffix suffix, name...) $(addprefix prefix, name...) $(join prefix-list,suffix-list) $(if condition, then-part, else-part) $(error text) $(foreach variable, list, body) $(strip text) $(origin variable) $(warning text) $(eval ...)
うわこりゃ多いな... 実際, 直ぐ使えて役立ちそうなのは, filter, filter-out, subst, shell, wildcard, foreach, warningくらいだと思います. いま言った関数くらいは紹介しておきましょうか.
LIST := huge.c hoge hige.c hoge.c hoga.c hogehogeeee.c $(warning $(filter hoge, $(LIST))) $(warning $(filter hoge%, $(LIST))) $(warning $(filter-out hoge, $(LIST))) $(warning $(filter-out hoge%, $(LIST))) all: @echo
Makefile:2: hoge Makefile:3: hoge hoge.c hogehogeeee.c Makefile:4: huge.c hige.c hoge.c hoga.c hogehogeeee.c Makefile:5: huge.c hige.c hoga.c
filterやfilter-outは, マッチが完全一致で行われます. %記号があらゆる文字にマッチ(いわゆるワイルドカードっぽい)します. しかし, 実は%はpatternの中では一度しか使えないという困ったちゃんです.
$(warning $(filter %hoge%, $(LIST))) $(warning $(filter %hoge%, hogehoge%))
Makefile:6: Makefile:7: hogehoge%
%hoge%の最初の%はワイルドカードとして動作しますが, 二つ目以降の%は文字として扱われます. キモいですね.
次はsubst関数.
SOURCE := foo.c bar.c baz.c $(warning $(subst .c,.o,$(SOURCE)))
Makefile:2: foo.o bar.o baz.o
普通の置換です. そう言えば, (とふと思い出したように書きますが, ) makeはコードのスペースを尊重します. 普通のプログラミング言語だと,
foo(hoge,bar) foo(hoge, bar) foo( hoge, bar ) foo ( hoge , bar )
どんなふうに書いても同じように動作するでしょう. ところがmakeは違います. 先ほどの例で,
$(warning $(subst .c, .o, $(SOURCE)))
と書いてしまった場合(そして, 最初は癖でカンマの後にスペースを書いてしまいやすい),
Makefile:2: foo .o bar .o baz .o
となります. まずは各々の .o の前にスペースが入っていること, そして最初にスペースが一つ(, $(SOURCE)のスペース)入ってることに注意して下さい.
shell関数は, どんなコマンドでも実行して, その標準出力を返します.
all: @echo $(shell date)
2012年 2月13日 月曜日 06時56分09秒 JST
$(shellの中でcatしてgrepみたいなのはよく使いますね. また, バージョンを書いたファイルを用意しておいて,
VERSION := $(shell cat version.txt)
みたいなのとかは便利です. ls -alで情報とか読んだり？ psとか？ killとか？ 何でもアリです. 使い道は無限大.
wildcard関数は, ファイルを選択するワイルドカードです. 生のワイルドカードでいいじゃんと思ってたら, 穴にはまります.
SRC := *.c WILD_SRC := $(wildcard *.c) all: @echo $(SRC) @echo $(WILD_SRC)
bar.c baz.c foo.c bar.c baz.c foo.c
一緒に見える？ 意地悪しちゃいます.
SRC := *.c WILD_SRC := $(wildcard *.c) all: @echo $(SRC) @echo $(WILD_SRC) @echo $(foreach file,$(SRC),$(file)) @echo $(foreach file,$(WILD_SRC),$(file)) @echo "$(foreach file,$(SRC),$(file))" @echo "$(foreach file,$(WILD_SRC),$(file))" @echo $(foreach file,$(SRC),echo $(file)) @echo $(foreach file,$(WILD_SRC),echo $(file))
bar.c baz.c foo.c bar.c baz.c foo.c bar.c baz.c foo.c bar.c baz.c foo.c *.c bar.c baz.c foo.c echo bar.c baz.c foo.c echo bar.c echo baz.c echo foo.c
ｸｽｸｽ... ｵﾓｼﾛｲﾃﾞｽﾈ...
foreach関数は, その名の通りですね.
all: @echo $(foreach name,TweetDeck 夜ふくろう Tween,"$(name)を使っている人は廃人です\n")
TweetDeckを使っている人は廃人です 夜ふくろうを使っている人は廃人です Tweenを使っている人は廃人です
foreachとshellがあれば, ホント何でも出来る気がしますよ.
makeの基礎事項はこれくらいにして, makeで計算やりましょう. さっきからウズウズしてたまらないのです. 紹介した以外の関数は, GNU make 日本語訳(Coop編) - 目次あたりを参照して下さい.
限界を超えて
このタイトルは, make本の付録Bのそのままです. ごめんなさい.
この｢付録B｣には, ｢B.1: 構造体｣に始まり, ｢B.2: 数値計算｣へと続きます. 人によっては, Makefileで構造体を模擬する方法のほうが気になるかもしれませんが, 僕は断然後者ですね. (というかmake本読みましょう. 面白いので.) ｢数値計算｣というタイトルがついていますが, むしろ如何にMakefileのなかで数値をシミュレートするか, というお話で, いわゆる｢数値計算｣とはちょっと違います. ラムダ式で数値をどう扱うかみたいなのと, まぁ話としては同じです. ここのエントリーの内容は, ほぼmake本からパクってきたものです.
まず, Makefileで数値の計算をするにあって, 絶対に守らなくてはならないルールを書いておきます.
- shell関数は使ってはいけない. さらに丁寧に言うと, 他の言語処理系及びプログラムを使ってはいけない.
これ使っちゃったら, 他の言語で書かれたソースコードをファイルに書きだして, コンパイルして実行とかできちゃいますからね. ダメです. catとかファイル書き込みしたりもずるい気がするので禁止.
何よりもまず大前提として, makeの中で普通に数式を書いたら評価してくれる, なんてあまっちょろいものではありません.
VARX = 1 + 2 $(warning $(VARX)) ONE = 1 TWO = 2 $(warning $(ONE) + $(TWO))
Makefile:2: 1 + 2 Makefile:5: 1 + 2
evalしたって無駄です.
$(warning $(eval $(ONE) + $(TWO)))
Makefile:3: *** missing separator. Stop.
一つの逃げ道は, こういうものになるでしょう.
$(warning $(shell python -c "print($(ONE) + $(TWO))")) $(warning $(shell python -c "print(1+2*4)"))
Makefile:3: 3 Makefile:4: 9
実は, shellと直接書かなくても同じ事はできます.
TWO = 2 THREE = 3 all: @python -c "print($(THREE) * $(TWO))"
$ make all
6
こんなのでは元も子もないです. だからshellと, ｢他の言語処理系｣を禁止したんです.
ではどうしましょう. makeは数値の計算をサポートしてない... うーん.
最初の重要な観察は, makeには単語列を処理する関数が豊富にあることです. そして, それらはしばしば｢数値に返り値｣を持つ, 或いは｢数値を引数に取る｣ことがあります.
例えば,
$(warning $(words hoge huga piyo nyan poyo)) $(warning $(word 3,hoge huga piyo nyan poyo)) $(warning $(wordlist 3,5,hoge huga piyo nyan poyo))
Makefile:1: 5 Makefile:2: piyo Makefile:3: piyo nyan poyo
words関数は, 単語の数を返す(返り値が数値), wordはn番目の文字を返す(引数が数値)関数です. $(wordlist a,b,list)は, listのa番目からb個取ってくる関数です. bが十分に大きければ, リストの最後まで返します. (makeは1オリジンです！)
ここから, 少しの発想で(しかしこれは驚くべきものですが), 足し算を行うことに気が付きます.
plus = $(word $2,$(wordlist $1,100,2 3 4 5 6 7 8 9 10 11 12 13 14 15)) $(warning $(call plus,3,4))
Makefile:2: 7
3 + 4 = 7 が計算出来ました. 次のように評価されます. ($1や$2が引数を指していることは言わなくても分かりますよね)
$(call plus,3,4) = $(word 4,$(wordlist 3,100,2 3 4 5 6 7 8 9 10 11 12 13 14 15)) = $(word 4,4 5 6 7 8 9 10 11 12 13 14 15) # 2 3 4 5 6 ...の3番目から100個とってきた = 7 # 4 5 6 7 8 9...の4番目を返した
という訳で, 最初に自然数のリストを作ってやらなければなりません. 直に｢0 1 2 3 4 5 ... ｣と書くのは余りにあれなので, もうちょっと賢く書きます.
# 数値を組み合わせる combine = $(foreach i, $1, $(addprefix $i, $2)) # 05 を 5 に, 08 を 8 にする stripzero = $(patsubst 0%,%,$1) # リストを元に, combineを二回, stripzeroを二回行なって, 0から999までの数列を作る generate = $(call stripzero, \ $(call stripzero, \ $(call combine, $1, \ $(call combine, $1, $1)))) number_line := $(call generate,0 1 2 3 4 5 6 7 8 9) # その長さ ( ただ単に, $(words $(number_line))だと1000になる. この$(length)は999. こっちの方がふさわしい理由は, 後のreverseのところで出てくる. ) length := $(word $(words $(number_line)), $(number_line)) $(warning $(number_line)) $(warning $(length))
Makefile:16: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ... 995 996 997 998 999 Makefile:17: 999
0から999までのリストを作れました. ではでは, 足し算してみましょう. 今回はリストが0から始まるので, 少し注意です.
plus = $(word $2, \ $(wordlist $1, $(length), \ $(wordlist 3, $(length), $(number_line)))) $(warning $(call plus,39,18)) $(warning $(call plus,127,473))
Makefile:21: 57 Makefile:22: 600
39 + 18 = 57 と 127 + 473 = 600 が計算出来ました. はい拍手.
では引き算を定義しましょう. 引き算は, 足し算を配列を逆にして行うだけです.
# 999 ... 0 backwards := $(call generate, 9 8 7 6 5 4 3 2 1 0) # 配列を逆にする. (ここで$(length)が1000だとアウトになる. なぜなら, word 0 がエラーで落ちるから. makeは1オリジンなので, wordの引数は1以上でなくてはならない) reverse = $(strip \ $(foreach n, \ $(wordlist 1, $(length), $(backwards)), \ $(word $n, $1))) # 引き算 minus = $(word $2, \ $(call reverse, \ $(wordlist 1, $1, $(number_line)))) $(warning $(call minus,19,6)) $(warning $(call minus,975,187))
Makefile:33: 13 Makefile:34: 788
19 - 6 = 13 と 975 - 187 = 788 が計算出来ました. ちょっと最初の例で計算を追ってみましょう.
$(call minus,19,6) = $(word 6, $(call reverse, $(wordlist 1, 19, $(number_line)))) = $(word 6, $(call reverse, 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18)) = $(word 6, 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0) = 13
まずは0 .. 18 を作っておいて, 逆にして後ろから数えると言った具合ですね. 引く数の方が大きいと, エラー無しに空の文字が返ってきます.
$(warning $(call minus,50,34)) $(warning $(call minus,34,50))
Makefile:38: 16 Makefile:39:
(あっ 19 - 0 ならどうなるんだろう... と思ったら鋭い. word 0 がエラーで落ちますので, 特別に処理してあげなくてはなりません. このエントリーの最後のコードでは, こういう細かいところを直しています.)
大小比較
# $1 > $2 なら $1, $1 <= $2 なら空 gt = $(filter $1, \ $(wordlist 3, $(length), \ $(wordlist $2, $(length), $(number_line)))) $(warning $(call gt,9,18)) $(warning $(call gt,18,9)) $(warning $(call gt,18,18))
Makefile:44: Makefile:45: 18 Makefile:46:
同値性も必要ですね. filterでいいと思います.(ここからは, 本当にmake本に載ってなくてオリジナルなので, もっと効率のよい方法があるかもしれません)
# 同じ数ならその数, 違ったら空 eq = $(filter $1,$2) $(warning $(call eq,5,5)) $(warning $(call eq,5,50)) $(warning $(call eq,50,5)) $(warning $(call eq,50,500)) $(warning $(call eq,512,512))
Makefile:39: 5 Makefile:40: Makefile:41: Makefile:42: Makefile:43: 512
後は, 掛け算.
# 掛け算 multiply = $(words $(call combine, \ $(wordlist 1, $1, $(number_line)),\ $(wordlist 1, $2, $(number_line)))) $(warning $(call multiply,0,100)) $(warning $(call multiply,100,0)) $(warning $(call multiply,100,1)) $(warning $(call multiply,174,1)) $(warning $(call multiply,9,7))
Makefile:49: 0 Makefile:50: 0 Makefile:51: 100 Makefile:52: 174 Makefile:53: 63
ここで何をやってるかというと, 0 .. ($1 - 1) のリストと, 0 .. ($2 - 1)のリストを combine (これは0 .. 999を作る時に使った)関数で結合しまくって, その長さをwordsで測ってるんですね. いやはや. きちんと0掛けもできてます. (make本のコードは, 0に対する扱いが適当で, plusなどはwordの引数エラーで落ちます. 全て修正したバージョンは, このエントリーの最後に載せています.)
お約束の九九表
# 九九表 from_one = $(wordlist 2, $(length), $(number_line)) kuku = $(foreach n,$(wordlist 1, $1, $(from_one)), \ $(warning $(foreach m,$(wordlist 1, $2, $(from_one)), \ $(call multiply,$n,$m)))) $(call kuku, 9, 9)
Makefile:54: 1 2 3 4 5 6 7 8 9 Makefile:54: 2 4 6 8 10 12 14 16 18 Makefile:54: 3 6 9 12 15 18 21 24 27 Makefile:54: 4 8 12 16 20 24 28 32 36 Makefile:54: 5 10 15 20 25 30 35 40 45 Makefile:54: 6 12 18 24 30 36 42 48 54 Makefile:54: 7 14 21 28 35 42 49 56 63 Makefile:54: 8 16 24 32 40 48 56 64 72 Makefile:54: 9 18 27 36 45 54 63 72 81
最後は割り算です.
# 割り算 divide = $(strip \ $(foreach n, \ $(wordlist 1,$(call plus,$1,1),$(number_line)), \ $(if $(call eq, $1,$(call multiply,$n,$2)),$n,))) $(warning $(call divide,360,1)) $(warning $(call divide,360,2)) $(warning $(call divide,360,120)) $(warning $(call divide,360,360)) $(warning $(call divide,657,73))
Makefile:63: 360 Makefile:64: 180 Makefile:65: 3 Makefile:66: 1 Makefile:67: 9
わぁい！ 割り算もできました. $(call divide, a, b) とすると, 0 .. aから各々nについて, n * b がaと等しければn, 違ったら空文字にします. あとはstripで余分な空白を取り除くだけ. 割り切れなかったときは知りません. (空文字になる...) あと, この計算, 時間がかかります. 効率のよい方法があれば教えて下さい.
もう十分道具は揃いました. 何でも書けます. チューリング完全です.
階乗
# 階乗 factorial = $(strip \ $(if $(call eq,0,$1),1, \ $(call multiply,$1, \ $(call factorial,$(call minus,$1,1))))) $(warning $(call factorial,0)) $(warning $(call factorial,3)) $(warning $(call factorial,5)) $(foreach n,0 1 2 3 4 5 6 7 8 9, $(warning $n! = $(call factorial,$n)))
Makefile:69: 1 Makefile:70: 6 Makefile:71: 120 Makefile:72: 0! = 1 Makefile:72: 1! = 1 Makefile:72: 2! = 2 Makefile:72: 3! = 6 Makefile:72: 4! = 24 Makefile:72: 5! = 120 Makefile:72: 6! = 720 Makefile:72: 7! = 5040 Makefile:72: 8! = 8000 Makefile:72: 9! = 9000
おっと, 6! = 720, 7! = 5040まではいいですが, 後は溢れてますね... 大丈夫. 最初の方のgeneate関数を桁数増やせばいい.
generate = $(call stripzero, \ $(call stripzero, \ $(call stripzero, \ $(call combine, $1, \ $(call combine, $1, \ $(call combine, $1, $1))))))
Makefile:71: 1 Makefile:72: 6 Makefile:73: 120 Makefile:74: 0! = 1 Makefile:74: 1! = 1 Makefile:74: 2! = 2 Makefile:74: 3! = 6 Makefile:74: 4! = 24 Makefile:74: 5! = 120 Makefile:74: 6! = 720 Makefile:74: 7! = 5040 Makefile:74: 8! = 40320 Makefile:74: 9! = 90000
9!はこれでも桁が足りないようです. 大丈夫. generate関数の桁(以下略)... あまりにやると, 計算時間が...
フィボナッチ数
# おそらく, このエントリーの順番に忠実にMakefileを書いていくと, plusがword 0エラーで落ちます. 次のように修正して下さい. plus = $(strip \ $(if $(call eq,$1,0),$2, \ $(if $(call eq,$2,0),$1, \ $(word $2, \ $(wordlist $1, $(length), \ $(wordlist 3, $(length), $(number_line))))))) # フィボナッチ数 fibonacci = $(strip \ $(if $(call eq,0,$1),0, \ $(if $(call eq,1,$1),1, \ $(call plus, \ $(call fibonacci,$(call minus,$1,1)), \ $(call fibonacci,$(call minus,$1,2)))))) $(warning $(call fibonacci,0)) $(warning $(call fibonacci,2)) $(warning $(call fibonacci,6)) $(foreach n,0 1 2 3 4 5 6 7 8 9 10 11 12, \ $(warning fibonacci ($n) = $(call fibonacci,$n)))
Makefile:86: 0 Makefile:87: 1 Makefile:88: 8 Makefile:89: fibonacci (0) = 0 Makefile:89: fibonacci (1) = 1 Makefile:89: fibonacci (2) = 1 Makefile:89: fibonacci (3) = 2 Makefile:89: fibonacci (4) = 3 Makefile:89: fibonacci (5) = 5 Makefile:89: fibonacci (6) = 8 Makefile:89: fibonacci (7) = 13 Makefile:89: fibonacci (8) = 21 Makefile:89: fibonacci (9) = 34 Makefile:89: fibonacci (10) = 55 Makefile:89: fibonacci (11) = 89 Makefile:89: fibonacci (12) = 144
フィボナッチ数も難なくできました. だた, よくある再帰爆発で, 滅茶苦茶時間がかかる. そこで, メモ化したものが次のコード. (スーパーpreの括弧対応が働いてない...)
# フィボナッチ数 (eval展開) fibonacci_fast = $(strip $(call fibonacci_eval,$1)$(FIBONACCI_$1)) fibonacci_eval = $(if $(FIBONACCI_$1),, \ $(if $(call eq,$1,0), \ $(eval FIBONACCI_0 := 0), \ $(call fibonacci_eval,$(call minus,$1,1)) \ $(if $(call eq,$1,1), \ $(eval FIBONACCI_1 := 1), \ $(eval FIBONACCI_$1 := \ $$(call plus, \ $$(FIBONACCI_$(call minus,$1,1)), \ $$(FIBONACCI_$(call minus,$1,2))))))) $(warning $(call fibonacci_fast,0)) $(warning $(call fibonacci_fast,2)) $(warning $(call fibonacci_fast,6)) $(foreach n,$(wordlist 1,21,$(number_line)), \ $(warning fibonacci_fast ($n) = $(call fibonacci_fast,$n)))
Makefile:101: 0 Makefile:102: 1 Makefile:103: 8 Makefile:104: fibonacci_fast (0) = 0 Makefile:104: fibonacci_fast (1) = 1 Makefile:104: fibonacci_fast (2) = 1 Makefile:104: fibonacci_fast (3) = 2 Makefile:104: fibonacci_fast (4) = 3 Makefile:104: fibonacci_fast (5) = 5 Makefile:104: fibonacci_fast (6) = 8 Makefile:104: fibonacci_fast (7) = 13 Makefile:104: fibonacci_fast (8) = 21 Makefile:104: fibonacci_fast (9) = 34 Makefile:104: fibonacci_fast (10) = 55 Makefile:104: fibonacci_fast (11) = 89 Makefile:104: fibonacci_fast (12) = 144 Makefile:104: fibonacci_fast (13) = 233 Makefile:104: fibonacci_fast (14) = 377 Makefile:104: fibonacci_fast (15) = 610 Makefile:104: fibonacci_fast (16) = 987 Makefile:104: fibonacci_fast (17) = 1597 Makefile:104: fibonacci_fast (18) = 2584 Makefile:104: fibonacci_fast (19) = 4181 Makefile:104: fibonacci_fast (20) = 6765
さっきと比較したら, 格段に速い. やってることは, evalで式を展開してるだけ.
ほんまにチューリング完全なん？
そりゃさぁ, フィボナッチくらいじゃぁ...あやしいでしょwww
って人のために, Brainfuckの処理系をMakefileで書いてみました.
combine = $(foreach i, $1, $(addprefix $i, $2)) stripzero = $(patsubst 0%,%,$1) generate = $(call stripzero, \ $(call stripzero, \ $(call stripzero, \ $(call combine, $1, \ $(call combine, $1, \ $(call combine, $1, $1)))))) number_line := $(call generate,0 1 2 3 4 5 6 7 8 9) length := $(word $(words $(number_line)), $(number_line)) plus = $(strip \ $(if $(call eq,$1,0),$2, \ $(if $(call eq,$2,0),$1, \ $(word $2, \ $(wordlist $1, $(length), \ $(wordlist 3, $(length), $(number_line))))))) backwards := $(call generate, 9 8 7 6 5 4 3 2 1 0) reverse = $(strip \ $(foreach n, \ $(wordlist 1, $(length), $(backwards)), \ $(word $n, $1))) minus = $(strip \ $(if $(call eq,$2,0),$1,\ $(word $2, \ $(call reverse, \ $(wordlist 1, $1, $(number_line)))))) eq = $(filter $1,$2) insertspace = $(strip \ $(subst +,+ , \ $(subst -,- , \ $(subst >,> , \ $(subst <,< , \ $(subst [,[ , \ $(subst ],] , \ $(subst .,. ,$1)))))))) ## Brainfuck interpreter in Makefile ### source code input := ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>. ascii = $(if $(call minus,$1,31), \ $(if $(call eq,$1,32), ,\ $(word $(call minus,$1,32),\ ! " \# $$ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~))) i := 1 p := 1 text:=$(call insertspace,$(input)) is = $(findstring $(word $i,$(text)),$1) forward = $(eval i:=$(call plus,$i,1)) backward = $(eval i:=$(call minus,$i,1)) bfplus = $(eval p$p:=$(if $(p$p),$(call plus,$(p$p),1),1)) bfminus = $(eval p$p:=$(if $(p$p),$(call minus,$(p$p),1),1)) bfopen = $(saveopen)$(if $(call eq,$(p$p),0),$(recoverclose),) saveopen = $(eval iopen:=$i) saveclose = $(eval iclose:=$i) recoveropen = $(eval i:=$(iopen)) recoverclose = $(eval i:=$(iclose)) bfclose = $(saveclose)$(recoveropen)$(backward) bfright = $(eval p:=$(call plus,$p,1)) bfleft = $(eval p:=$(call minus,$p,1)) bfoutput = $(warning $(call ascii,$(p$p)))$(call ascii,$(p$p)) debug = $(warning $(p1) $(p2) $(p3) $(p4) $(p5)) bf = $(if $(call is,+),$(bfplus),\ $(if $(call is,-),$(bfminus),\ $(if $(call is,[),$(bfopen),\ $(if $(call is,]),$(bfclose),\ $(if $(call is,>),$(bfright),\ $(if $(call is,<),$(bfleft),\ $(if $(call is,.),$(bfoutput))))))))$(forward) all: @echo $(foreach j,$(wordlist 1,500,$(number_line)),$(bf))
$ make all Makefile:76: H Makefile:76: e Makefile:76: l Makefile:76: l Makefile:76: o Makefile:76: Makefile:76: W Makefile:76: o Makefile:76: r Makefile:76: l Makefile:76: d Makefile:76: ! Makefile:76: H e l l o W o r l d !
なかなか感動モノでしょう. なんかスペースが潰れちゃう...
色々許してください！ ネストした括弧は処理できないけど許してください！ いっぱいeval使っちゃったけど許してください！ [ の仕様をちょっと無視してる(いきなり]に飛べない)けど許してください！ 複数個の [ .. ] があったら破滅する気がするけど許してください！ 取り敢えずHello World!だけはチート無しに実行したかったんです！
まとめ
階乗, フィボナッチ数を計算できたどころか, Brainfuckの処理系も書けたので, makeは立派なプログラミング言語です. 何でも出来ます. 多分文字列の処理が速いはずだから, フィボナッチ数とかあほな事やってないで, makeはmakeらしい使い方を心がけましょう. Makefileを書いて幸せになりましょう.
ところで, だれかMakefileでQuine書いて下さい. 変数展開が二重にも三重にもなっちゃって, 結局出来ませんでした. そもそもQuine得意じゃない僕がやろうとしたことが無謀でした.
ソースコード
足し算引き算, 掛け算割り算から, 階乗, フィボナッチ数までのコードを示します.
# 数値を組み合わせる combine = $(foreach i, $1, $(addprefix $i, $2)) # 05 を 5 に, 08 を 8 にする stripzero = $(patsubst 0%,%,$1) # リストを元に, combineを3回, stripzeroを3回行なって, 0から9999までの数列を作る generate = $(call stripzero, \ $(call stripzero, \ $(call stripzero, \ $(call combine, $1, \ $(call combine, $1, \ $(call combine, $1, $1)))))) # 0 ... 9999 number_line := $(call generate,0 1 2 3 4 5 6 7 8 9) # その長さ ( ただ, $(words $(number_line))だと10000になる. この$(length)は9999. これは, 後のreverseに響いてくる ) length := $(word $(words $(number_line)), $(number_line)) # 足し算 ( 0 + n, n + 0 も出来るように修正 ) plus = $(strip \ $(if $(call eq,$1,0),$2, \ $(if $(call eq,$2,0),$1, \ $(word $2, \ $(wordlist $1, $(length), \ $(wordlist 3, $(length), $(number_line))))))) # 9999 ... 0 backwards := $(call generate, 9 8 7 6 5 4 3 2 1 0) # 配列を逆にする. (ここで$(length)が10000だとアウトになる. なぜなら, word 0 がエラーで落ちるから. makeは1オリジンなので, wordの引数は1以上でなくてはならない) reverse = $(strip \ $(foreach n, \ $(wordlist 1, $(length), $(backwards)), \ $(word $n, $1))) # 引き算, マイナスになったら空 minus = $(strip \ $(if $(call eq,$2,0),$1,\ $(word $2, \ $(call reverse, \ $(wordlist 1, $1, $(number_line)))))) # 同じ数ならその数, 違ったら空 eq = $(filter $1,$2) # $1 > $2 なら $1, $1 <= $2 なら空 ($2 = 0 にも対応) gt = $(strip \ $(if $(call eq,$2,0), \ $(if $(call eq,$1,0),,$1),\ $(filter $1, \ $(wordlist 3, $(length), \ $(wordlist $2, $(length), $(number_line)))))) # 掛け算 multiply = $(words $(call combine, \ $(wordlist 1, $1, $(number_line)),\ $(wordlist 1, $2, $(number_line)))) # 九九表 from_one = $(wordlist 2, $(length), $(number_line)) kuku = $(foreach n,$(wordlist 1, $1, $(from_one)), \ $(warning $(foreach m,$(wordlist 1, $2, $(from_one)), \ $(call multiply,$n,$m)))) # $(call kuku, 9, 9) # 割り算 divide = $(strip \ $(foreach n, \ $(wordlist 1,$(call plus,$1,1),$(number_line)), \ $(if $(call eq, $1,$(call multiply,$n,$2)),$n,))) # 階乗 factorial = $(strip \ $(if $(call eq,0,$1),1, \ $(call multiply,$1, \ $(call factorial,$(call minus,$1,1))))) # フィボナッチ数 (メモ化なし) fibonacci = $(strip \ $(if $(call eq,0,$1),0, \ $(if $(call eq,1,$1),1, \ $(call plus, \ $(call fibonacci,$(call minus,$1,1)), \ $(call fibonacci,$(call minus,$1,2)))))) # フィボナッチ数 (eval展開) fibonacci_fast = $(strip $(call fibonacci_eval,$1)$(FIBONACCI_$1)) fibonacci_eval = $(if $(FIBONACCI_$1),, \ $(if $(call eq,$1,0), \ $(eval FIBONACCI_0 := 0), \ $(call fibonacci_eval,$(call minus,$1,1)) \ $(if $(call eq,$1,1), \ $(eval FIBONACCI_1 := 1), \ $(eval FIBONACCI_$1 := \ $$(call plus, \ $$(FIBONACCI_$(call minus,$1,1)), \ $$(FIBONACCI_$(call minus,$1,2))))))) $(warning $(call fibonacci_fast,0)) $(warning $(call fibonacci_fast,2)) $(warning $(call fibonacci_fast,6)) $(foreach n,$(wordlist 1,21,$(number_line)), \ $(warning fibonacci_fast ($n) = $(call fibonacci_fast,$n))) all: @echo
参考文献
- Robert Mecklenburg著 矢吹道郎 監訳 菊池 彰 訳, GNU Make 第三版, O'REILLY オライリー・ジャパン
追記 終了しないMakefile (2012/02/15)
大声でチューリング完全だといいました. ならば, 永遠に終了しないMakefileを書けるはずです.
まぁ無限ループを考えてみましょう.
では問題です. 次の4つのMakefileの中で, 終了しないMakefileはどれでしょう.
loop := hoge $(loop) all: @echo
loop = hoge $(loop) all: @echo
loop := hoge $(loop) all: @echo $(loop)
loop = hoge $(loop) all: @echo $(loop)
正解は, ｢4つとも無限ループにはならない｣です.
- 1つ目は, 何も出力せずに終了します. $(loop)には, hogeと入っています.
- 2つ目も, 何も出力せずに終了します. $(loop)は評価されません.
- 3つ目は, ｢hoge｣と出力して終了します. ｢:=｣は, その行に来た瞬間に評価がされますが, この時の右辺の$(loop)はそれ｢まで｣の変数テーブルから探すので, 空文字が入ります. よって$(loop)には｢hoge｣が入ります.
- 4つ目は, ｢makefile:1: *** Recursive variable `loop' references itself (eventually). Stop.｣というエラーを吐いて(異常)終了します. ｢=｣は遅延評価で, 謂わばHaskellのような状態で無限ループが発生します. この時, 本当に無限ループになるのではなく, makeがループを検出して終了します.
makeの素晴らしい再帰検出機能によって, 無限ループは作れない.
かと思いきや, そうでもないようです. まずは次のMakefileを考えてみましょう.
loop = $(if $(filter 0,$(words $1)),\ end,\ hoge$(call loop,$(wordlist 2,1000,$1))) all: @echo $(call loop,x x x x x) @echo $(call loop,x x x x x x x x x x x x x x)
$ make
hoge hoge hoge hoge hoge end
hoge hoge hoge hoge hoge hoge hoge hoge hoge hoge hoge hoge hoge hoge end
引数の単語の数だけhogeと出力して, 最後にendと出力して終了します. じゃぁ, wordlist 2,1000をサボったら？
loop = $(if $(filter 0,$(words $1)),\ end,\ hoge$(call loop,$1)) all: @echo $(call loop,x x x x x)
$ make
^C
$
本当に終了しませんでした.
loop = $(if $(filter 0,$(words $1)),\ end,\ $(warning infinite loop!!!)$(call loop,$1)) all: @echo $(call loop,x x x x x)
$ make makefile:5: infinite loop!!! makefile:5: infinite loop!!! makefile:5: infinite loop!!! makefile:5: infinite loop!!! makefile:5: infinite loop!!! ... makefile:5: infinite loop!!! makefile:5: infinite loop!!! makefile:5: infinite loop!!! makefile:5: infinite loop!!! makefile:5: infinite loop!!! makefile:5: infinite loop!!! makefile:5: infi^C $
おお怖い怖い.
