おまえは何をやっとるんじゃ!?>俺
アホじゃー、バカじゃーー。
それでは、いってみましょう。
予備知識:
Make言語には算術演算がない
さて、今話題の(って、そんなこたぁねーよ)プログラミング言語Makeですが、豊富な(って、ホントかぁ?)文字列処理関数を備えていますが、なぜか算術演算がありません。足し算もできません。でも大丈夫、足し算くらいすぐに実装できますよ(って、ホントかぁ?)。
最初に老婆心から言っておきますが、すぐさまホントに足し算が欲しいなら、次の不粋な方法が現実的かと思います。
add = $(shell expr $(1) + $(2))
タリー表現による足し算
自然数(0以上の整数)を次のように表現しましょう; 0は""(空文字列)、1は"I"、2は"II"、3は"III" … ローマ数字*1と似てます。が、I(大文字アイ)以外は使わないので、100はIを100個並べます。分かりやすくていいですね :-)
このような超素朴な数表記はタリー(tally;札、勘定)表現と呼びます。タリー表現をベースとするなら、Make言語による足し算は実に簡単です。
add = $(1)$(2)
10進タリー表現
タリー表現はいくらなんでもヒドイので、0から9まではタリー表現としたうえで、通常の10進記数法を採用しましょう。例えば、253は"II IIIII III"とします。桁と桁のあいだは空白を入れます。ただし、これだと2503でも"II IIIII III"になってしまうので、0を表す文字O(大文字オー)を導入して、2503は"II IIIII O III"としましょう。
10進タリー表現は、数字(digit)の形は違うものの、日常使ってる数表現とまったく同じです。その計算は、小学校で習ったあの方法を愚直に再現すればいいですね(後でそれをやるよ)。
制御構造の強化 -- foldr
foreachだけだと制御構造(高階関数)がどうも足りない感じ、foldが欲しいところ。再帰でユーザー定義するなら、foldlよりfoldrのほうが簡単なのでfoldrを作りましょう。
Make言語で書く前にLisp(つっても、Emacs Lispだが)で示しておくと:
(defun foldr (fun acc lis)
(if (null lis) acc
(funcall fun (car lis) (foldr fun acc (cdr lis)))))
実行例で、5から1はprincによる表示で、最後の15は計算結果です。
(foldr (lambda (elm acc)
(princ (format "%d\n" elm))
(+ acc elm))
0 '(1 2 3 4 5))
5
4
3
2
1
15
Lispのnull, cdrに対応するMake関数empty, butfirstを定義したうえで、foldrのMake版を書きます。(横長でスミマセン、改行を不用意に入れられないので。)
empty = $(if $(strip $(1)),,T)
butfirst = $(wordlist 2,$(words $(1)),$(1))foldr = \
$(if $(call empty,$(3)),$(2),$(call $(1),$(firstword $(3)),$(call foldr,$(1),$(2),$(call butfirst,$(3)))))
foldrを使うと、reverseは次のように書けます。
swap = $(2) $(1)
reverse = $(call foldr,swap,,$(1))
出力の先頭に余分な空白が付きますが大目に見てね。
$ make -f rev.mk
X='a b c d'
reverse X=' d c b a'
リスト処理による10進数の足し算
足し算のハナシに戻ります。
まず、1桁の足し算は文字列連接で出来ます。0を表すO(オー)の処理が必要ですが、たいしたことはありません。複数桁の足し算は、各桁ごとの足し算をします。10を越えてしまった桁にはフラグを立てて、繰り上がり処理をします。この繰り上がり処理のとき、foldrにより右から順に桁を見ていくことにします。
アイディアを示すため、まずはLispで書いてみます。ただし、各桁は、タリー表現ではなくて普通の整数を使います。
(defun foldr (fun acc lis)
(if (null lis) acc
(funcall fun (car lis) (foldr fun acc (cdr lis)))))(defun n-times (n x)
(cond
((>= 0 n) nil)
((= 1 n) (list x))
(t (cons x (n-times (1- n) x)))))(defun adjust-first (first second)
(let ((d (- (length second) (length first))))
(if (<= d 0) first
(append (n-times d 0) first))))(defun adjust-second (first second)
(let ((d (- (length first) (length second))))
(if (<= d 0) second
(append (n-times d 0) second))))(defun join-add (numlis1 numlis2)
(cond
((null numlis1) numlis2)
((null numlis2) numlis1)
(t (cons (+ (car numlis1) (car numlis2))
(join-add (cdr numlis1) (cdr numlis2))))))(defun naive-add (numlis1 numlis2)
(join-add
(adjust-first numlis1 numlis2)
(adjust-second numlis1 numlis2)))(defun process-carry (num numlis)
(if (eq 'X (car numlis))
(process-carry-sub (1+ num) (cdr numlis))
(process-carry-sub num numlis)))(defun process-carry-sub (num numlis)
(if (>= num 10)
(cons 'X (cons (- num 10) numlis))
(cons num numlis)))(defun normalize (numlist)
(foldr (function process-carry) '() numlist))(defun process-last-carry (numlis)
(if (eq 'X (car numlis)) (cons 1 (cdr numlis))
numlis))(defun add (numlis1 numlis2)
(process-last-carry (normalize (naive-add numlis1 numlis2))))
計算例:
(add '(1) '(1))
(2)
(add '(2 0 5) '(2 0))
(2 2 5)
(add '(7 5) '(3 5))
(1 1 0)
(add '(9 8 2) '(5 9))
(1 0 4 1)
繰り上がり処理をしない足し算はnaive-addという関数、最上位桁以外の繰り上がり処理はnormalizeという関数です。
(naive-add '(9 8 2) '(5 9))
(9 13 11)
(normalize '(9 13 11))
(X 0 4 1)
(process-last-carry '(X 0 4 1))
(1 0 4 1)
Make言語による足し算
以下にMake言語による足し算を示します。基本的な流れはLispコードと同様です(細部は異なりますが)。通常の10進数と、内部表現である10進タリー表現との相互変換が入ります。
LispとMakeの関数対応表:
Lisp関数 | Make関数 |
---|---|
adjust-first | adjust_first |
adjust-second | adjust_second |
join-add | join (組み込み) |
naive-add | naive_add |
- | shrink |
- | remainder |
process-carry | process_carry |
process-carry-sub | process_carry_sub |
normalize | normalize |
process-last-carry | - |
add | add |
Make言語のソースは「続きを読む」の下にあります。
足し算はできたので、残りの算術演算もチョイチョイだよ。けど、なぜか掛け算をやる気力がまったく湧かない。
##
## 基本的な関数
### eq データ1 データ2 -> 真偽値
# データ1とデータ2が等しければ真、そうでなければ偽を返す述語
eq = $(and $(findstring !$(1),!$(2)),$(findstring !$(2),!$(1)))# empty データ -> 真偽値
# データが空、または空白文字だけなら真、そうでなければ偽を返す述語
empty = $(if $(strip $(1)),,T)# butfirst リスト -> リスト
# リストの先頭要素を除いた残り
butfirst = $(wordlist 2,$(words $(1)),$(1))# foldr 関数 初期値 リスト -> データ
# リストの右から順に関数を適用し、結果を累積するための高階関数
foldr = \
$(if $(call empty,$(3)),$(2),$(call $(1),$(firstword $(3)),$(call foldr,$(1),$(2),$(call butfirst,$(3)))))##
## 整数表現のエンコード/デコード
## 内部表現は10進タリー表現
### encode 10進数 -> 内部表現
encode = \
$(subst \
9,IIIIIIIII ,$(subst \
8,IIIIIIII ,$(subst \
7,IIIIIII ,$(subst \
6,IIIIII ,$(subst \
5,IIIII ,$(subst \
4,IIII ,$(subst \
3,III ,$(subst \
2,II ,$(subst \
1,I ,$(subst \
0,O ,$(1)))))))))))# decode 内部表現 -> 10進数
decode = \
$(subst O ,0,$(subst \
I ,1,$(subst \
II ,2,$(subst \
III ,3,$(subst \
IIII ,4,$(subst \
IIIII ,5,$(subst \
IIIIII ,6,$(subst \
IIIIIII ,7,$(subst \
IIIIIIII ,8,$(subst \
IIIIIIIII ,9,$(1)))))))))))##
## 桁数を揃える
### diff 内部表現1, 内部表現2 -> 桁数の違い
#
# 桁数の違い:
# 内部表現1が短ければ、“差の個数だけの'B'のリスト”が値となる。
# 内部表現2が短ければ、“差の個数だけの'A'のリスト”が値となる。
diff = \
$(filter-out AB,$(join $(patsubst %,A,$(1)),$(patsubst %,B,$(2))))# zero_prefix_first 内部表現1, 内部表現2 -> ゼロ接頭辞
# 桁数を揃えるために、内部表現1に付けるべきゼロ接頭辞(リスト)を返す。
zero_prefix_first = \
$(if $(strip $(subst A,,$(call diff,$(1),$(2)))),$(foreach x,$(call diff,$(1),$(2)),O),)# zero_prefix_first 内部表現1, 内部表現2 -> ゼロ接頭辞
# 桁数を揃えるために、内部表現2に付けるべきゼロ接頭辞(リスト)を返す。
zero_prefix_second = \
$(if $(strip $(subst B,,$(call diff,$(1),$(2)))),$(foreach x,$(call diff,$(1),$(2)),O),)# adjust_first 内部表現1, 内部表現2 -> 内部表現
# 桁数が揃えられた内部表現1を返す。
adjust_first = \
$(call zero_prefix_first,$(1),$(2)) $(1)# adjust_second 内部表現1, 内部表現2 -> 内部表現
# 桁数が揃えられた内部表現1を返す。
adjust_second = \
$(call zero_prefix_second,$(1),$(2)) $(2)##
## 足し算の実行と関連する処理
### naive_add 内部表現1, 内部表現2 -> 一時内部表現
# 内部表現1と内部表現2の和を一時内部表現で返す。
# 一時内部表現は:
# 1. 桁の左または右に余分なOが付くかもしれない。
# 2. 10以上を表すタリー表現が含まれるかもしれない。
naive_add = $(join $(call adjust_first,$(1),$(2)),$(call adjust_second,$(1),$(2)))# shrink 一時内部表現 -> 一時内部表現(O削除)
# 余分なOを削除する。
shrink = \
$(patsubst OI%,I%,$(patsubst %IO,%I,$(subst OO,O,$(1))))# remainder タリー表現(10以上) -> タリー表現
# 10以上の数を10で割った余り
remainder = \
$(if $(subst IIIIIIIIII,,$(1)),$(subst IIIIIIIIII,,$(1)),O)# process_carry タリー表現 フラグ付き内部表現 -> フラグ付き内部表現
# 内部表現の先頭に繰り上がりフラグ(文字'X')が付いていたら、
# その繰り上がりを処理したうえで、タリー表現を内部表現の先頭に挿入する
process_carry = \
$(if $(call eq,X,$(firstword $(2))),$(call process_carry_sub,$(1)I,$(call butfirst,$(2))),$(call process_carry_sub,$(1),$(2)))# process_carry_sub タリー表現 内部表現 -> フラグ付き内部表現
# タリー表現を、必要ならフラグと10で割った余りに分けて
# 内部表現の先頭に挿入する
process_carry_sub = \
$(if $(findstring IIIIIIIIII,$(1)),X $(call remainder,$(1)) $(2),$(1) $(2))# normalize 一時内部表現 -> 内部表現
# すべての桁の繰り上がりを処理する。ただし、左端の桁のフラグは残る。
normalize = $(call foldr,process_carry,,$(1))# add 内部表現1, 内部表現2 -> 内部表現
# 内部表現1と内部表現2の和を返す。
add = $(subst X,I,$(call normalize,$(call shrink,$(call naive_add,$(1),$(2)))))# Add 10進数1, 10進数2 -> 10進数
# 10進数1と10進数2の和を返す。
Add = \
$(call decode,$(call add,$(call encode,$(1)),$(call encode,$(2))) )##
## 足し算の定義はここまで
### left_summand 加法式 -> 10進数
# x+y(空白なし)のxを返す。
left_summand = \
$(firstword $(subst +, ,$(1)))# right_summand 加法式 -> 10進数
# x+y(空白なし)のyを返す。
right_summand = \
$(word 2,$(subst +, ,$(1)))ifndef Expr
-include expr.mk
endififndef Expr
Expr := \
1+1 1+2 4+7 18+17 99+1 102+49 0030+288 41+0000 299+9001
endifAns := \
$(foreach e,$(Expr),$(call Add,$(call left_summand,$e),$(call right_summand,$e)))
Disp := \
$(join $(Expr),$(foreach a,$(Ans),$(addprefix =,$a)))
print_test:
@for d in $(Disp); do \
echo "$$d"; \
done# END OF Makefile