sasagawa さんが開発されている ミニマム Lisp 処理系 Mono で (tak 12 6 0) が動作しないとのことですが、思い当たる節があったのでちょっと調べてみました。
リスト : mono.c の修正
int evlis(int addr){
int car_addr,cdr_addr;
checkgbc();
argpush(addr);
if(IS_NIL(addr)){
argpop();
return(addr);
}
else{
car_addr = eval(car(addr));
argpush(car_addr); /* 追加 */
cdr_addr = evlis(cdr(addr));
argpop(); /* 追加 */
argpop();
return(cons(car_addr,cdr_addr));
}
}
Mono の場合、ガベージコレクション (GC) が起動されるのは evlis だけです。eval(car(addr)) で新しいセルが生成された場合、そのセルはＣ言語の変数 car_addr だけが保持しています。このあと evlis(cdr(addr)) を実行したときに GC が起動すると、car_addr のセルはマークされずに回収されてしまいます。car_addr のセルをマークするように argpush(car_addr) を追加し、evlis(cdr(addr)) のあと argpop() を追加すれば、M.Hiroi の実行環境では問題なく (tak 12 6 0) を評価することができました。
昔々の話になりますが、X68000 で動作する Lisp インタプリタ VTOL を作ったとき、GC のバグで大変苦労したこと思い出しました。VTOL はアスキーの『Ｃプログラムブック３』を参考にして作ったのですが、GC の基本的な考え方は Mono と同じです。Ｃ言語の変数で保持しているセルは、GC でマークするため明示的に専用のスタックに積んでおく必要がありました。ところが、人間は間違いをおかすもので、M.Hiroi も積み忘れてしまうことがよくありました。これがなかなか取れないバグの原因となるわけです。
もし、M.Hiroi がいまＣ言語で小さな Lisp 処理系を作るのであれば、保守的な GC または Gauche のように Boehm GC を使ってみたいですね。保守的な GC については、拙作のページ Lisp 入門番外編 仮想計算機 COMETⅡの簡易シミュレータ (10) で簡単に説明しています。興味のある方はお読みくださいませ。また、Ｃ言語の実装例では、飯野卓見さんの ガベージコレクションの実装法と評価 が参考になると思います。
Common Lisp / Scheme の繰り返し へ移動しました。
ソートのお話です。Fussy さん の アルゴリズムの紹介 遅いソート・ルーチン で紹介されていた「ノームソート (gnome sort) 」に興味を持ったので、M.Hiroi も Python でプログラムを作ってみました。
ノームソートのアルゴリズムはとても簡単です。配列 buff をノームソートする場合、手順は次のようになります。
基本的な考え方は単純挿入ソートとよく似ています。単純挿入ソートは 0 から i 番目の要素を整列済みと考えて、その中に i + 1 番目の要素を正しい位置に挿入します。ノームソートの場合、i 番目と i + 1 番目の要素が正しい順序になるまで、要素を交換していくことでデータをソートします。つまり、要素を交換しながら挿入する位置を探しているわけです。
このアルゴリズムをそのままプログラムにすると次のようになります。参考までに、単純挿入ソートのプログラムも示します。
リスト : ノームソート
def gnome_sort(buff):
k = len(buff) - 1
i = 0
while i < k:
if buff[i] <= buff[i + 1]:
i += 1
else:
buff[i], buff[i + 1] = buff[i + 1], buff[i]
if i > 0: i -= 1
リスト : 単純挿入ソート
def insert_sort(buff):
k = len(buff)
for i in xrange(1, k):
temp = buff[i]
j = i - 1
while j >= 0 and temp < buff[j]:
buff[j + 1] = buff[j]
j -= 1
buff[j + 1] = temp
このように、単純挿入ソートは二重ループになりますが、ノームソートは単純なループでプログラムを作成することができます。
それでは単純挿入ソートと実行時間を比較してみましょう。ソートするデータは拙作のページ Algorithms with Python 整列 (sorting) [1] と同じです。結果は次のようになりました。
表 : ノームソートの実行結果
個数 乱数 昇順 逆順 山型
-----+---------+-------+--------+--------
1000 : 0.290 : 0.000 : 0.569 : 0.284
2000 : 1.148 : 0.001 : 2.278 : 1.136
4000 : 4.585 : 0.001 : 9.121 : 4.547
8000 : 18.299 : 0.002 : 36.435 : 18.204
表 : 単純挿入ソートの実行結果
個数 乱数 昇順 逆順 山型
-----+-------+-------+--------+-------
1000 : 0.112 : 0.001 : 0.222 : 0.109
2000 : 0.432 : 0.001 : 0.878 : 0.433
4000 : 1.745 : 0.002 : 3.496 : 1.730
8000 : 6.895 : 0.004 : 13.943 : 6.970
実行環境 : Windows XP, celeron 1.40 GHz, Python 2.7
ノームソートの場合、整列済みのデータはとても高速ですが、それ以外のデータは単純挿入ソートよりもかなり遅くなりました。実は、ノームソートには無駄な処理があるのです。それは M 番目の要素を N 番目 (N < M) にセットしたあと、先頭から M 番目までの要素は整列済みのはずですが、ノームソートはインデックス i を +1 しながらデータの比較を行っています。つまり、i が N から M までの間は要素を比較する必要がないのです。この処理を改良すると、実行速度はもう少し速くなるかもしれません。
プログラムは次のようになります。
リスト : ノームソート (改良版)
def gnome_sort1(buff):
k = len(buff) - 1
i = 0
j = 0
while i < k:
if buff[i] <= buff[i + 1]:
if i == j:
i += 1
j += 1
else:
i = j
else:
buff[i], buff[i + 1] = buff[i + 1], buff[i]
if i > 0: i -= 1
変数 j にソート済みの位置を保存しておきます。i を増加するとき、i と j が等しい場合は両方とも +1 します。そうでなければ、先頭から j までの要素は整列済みなので、i に j の値をセットします。これで不要な比較処理を省くことができます。
実行結果は次のようになりました。
表 : ノームソート改良版の実行結果 個数 乱数 昇順 逆順 山型 -----+--------+-------+--------+-------- 1000 : 0.208 : 0.001 : 0.414 : 0.205 2000 ; 0.822 : 0.001 : 1.638 : 0.812 4000 : 3.292 : 0.002 : 6.603 : 3.271 8000 : 13.086 : 0.004 : 26.191 : 13.071 実行環境 : Windows XP, celeron 1.40 GHz, Python 2.7
改良版のほうが少し速くなりました。効果は確かにあるのですが、それでも単純挿入ソートにはかないませんでした。興味のある方はいろいろ試してみてください。
Shiro さんの Islnad Life foldパターン の話に興味を持ったので、M.Hiroi も Prolog でプログラムを作ってみました。リストを平坦化する flatten は Prolog でも簡単に作ることができます。
リスト : リストの平坦化
flatten0([], []) :- !.
flatten0([X | Xs], Ys) :-
!, flatten0(X, Ys1), flatten0(Xs, Ys2), append(Ys1, Ys2, Ys).
flatten0(X, [X]).
flatten は拙作のページ Prolog Programming データ型と型述語 で取り上げていますが、上のプログラムはデータ型のチェックは行わずにカットで済ましています。2 番目の規則で第 1 引数がリストの場合、リストを X と Xs に分解します。そして、リストの先頭の要素 X を平坦化し、残りのリスト Xs を平坦化して、その結果を append で結合します。第 1 引数がアトムの場合は最後の規則が選択されます。1, 2 番目の規則が選択された場合、カットを通過しているのでバックトラックで最後の規則が再試行されることはありません。
SWI-Prolog での実行例を示します。
?- flatten0([a, [b, [c, d | e], f], g], X). X = [a, b, c, d, e, f, g] ; No
ところで、append を使うとリストのコピーが何度も行われるため、flatten0 は効率のよいプログラムとはいえません。append を使わないでリストを平坦化するには次のようにプログラムします。
リスト : 平坦化 (append を使わないバージョン)
flatten1([], Ys, Ys) :- !.
flatten1([X | Xs], A, Ys) :-
!, flatten1(Xs, A, Ys1), flatten1(X, Ys1, Ys).
flatten1(X, A, [X | A]).
flatten1(Xs, Ys) :- flatten1(Xs, [], Ys).
flatten1 はリストの最後尾から順番に要素を取り出し、累積変数 A に要素を追加していきます。リストを分解して flatten1 を再帰呼び出しするとき、Xs から平坦化するところがポイントです。それから、その結果 Ys1 を flatten1 に渡して X を平坦化するわけです。
実行例を示します。
?- flatten1([a, [b, [c, d | e], f], g], X). X = [a, b, c, d, e, f, g] ; No
次はリストを木とみなして畳み込みを行う fold_tree_right を作ってみましょう。プログラムの基本的な考え方は flatten1 と同じです。次のリストを見てください。
リスト : 木の畳み込み
fold_tree_right(_, Ys, [], Ys) :- !.
fold_tree_right(F, A, [X | Xs], Ys) :-
!, fold_tree_right(F, A, Xs, Ys1), fold_tree_right(F, Ys1, X, Ys).
fold_tree_right(F, A, X, X1) :- call(F, X, A, X1).
% リストの平坦化
cons(X, Y, [X | Y]).
flatten2(Xs, Ys) :- fold_tree_right(cons, [], Xs, Ys).
fold_tree_right の第 1 引数 F が関数 (述語)、第 2 引数 A が累積変数、第 3 引数がリストです。1, 2 番目の規則は flatten1 とほとんど同じです。3 番目の規則で、F に要素 X と累積変数 A を渡して call で呼び出します。結果は X1 に格納されます。これでリストを木とみなして畳み込みを行うことができます。
flatten2 は fold_tree_right に cons を渡して呼び出すだけです。それでは実行してみましょう。
?- flatten2([a, [b, [c, d | e], f], g], X). X = [a, b, c, d, e, f, g] ; No
リストの先頭から畳み込みを行う fold_tree_left も簡単にプログラムすることができます。
リスト : 木の畳み込み (2)
fold_tree_left(_, Ys, [], Ys) :- !.
fold_tree_left(F, A, [X | Xs], Ys) :-
!, fold_tree_left(F, A, X, Ys1), fold_tree_left(F, Ys1, Xs, Ys).
fold_tree_left(F, A, X, X1) :- call(F, X, A, X1).
2 番目の規則で fold_tree_left を再帰呼び出しするとき、最初にリストの先頭要素 X に fold_tree_left を適用し、それから残りのリスト Xs に fold_tree_left を適用します。これでリストを木とみなして先頭要素から畳み込みを行うことができます。
実行例を示します。
?- fold_tree_left(cons, [], [a, [b, [c, d | e], f], g], X). X = [g, f, e, d, c, b, a] ; No
正常に動作していますね。
最近、M.Hiroi は Erlang という関数型言語を勉強しています。Erlang のパターンマッチング、とくにリストのマッチングは Prolog とよく似ていますが、Prolog の「ユニフィケーション (unification) 」とは異なります。Erlang のパターンマッチングは右辺式に未束縛変数 (自由変数) があるとエラーになりますが、Prolog のユニフィケーションは右辺式に自由変数があってもかまいません。Prolog の場合、自由変数同士のマッチングは成功しますし、右辺式 (たとえばリストなど) の中に自由変数が含まれていてもかまいません。
また、Prolog のユニフィケーションは、教科書に載っているユニフィケーションとも少し異なります。M.Hiroi はユニフィケーションを 参考文献 [1] で勉強しました。パターンマッチングやユニフィケーションは Lisp で簡単にプログラムすることができます。興味のある方は拙作のページ Common Lisp 入門 記号のパターンマッチング (1), (2) をお読みください。
拙作のページで作成したプログラムでは、ユニフィケーションを関数 unify で行います。変数は先頭が ? のシンボルで表します。unify の場合も自由変数同士の照合は成功します。ところが、自由変数とリストを照合する場合、リストの中に同じ自由変数が含まれていると照合は失敗します。簡単な例を示しましょう。
(unify '?x '(a . ?y) '()) => ((?x a . ?y)) (unify '?x '(a . ?x) '()) => fail
最初の例は ?x と (a . ?y) を照合します。?x と ?y は自由変数です。変数束縛は第 3 引数に連想リストとして渡します。リストの中には同じ変数 ?x がないので照合は成功します。返り値は変数束縛を表す連想リストです。次の例はリストの中に同じ自由変数 ?x があるので照合は失敗します。返り値は失敗を表すシンボル fail です。
Prolog ではどちらの場合も照合に成功します。SWI-Prolog での実行例を示します。
?- X = [a | Y]. X = [a|Y] ; No ?- X = [a | X]. X = [a, a, a, a, a, a, a, a, a|...] ; No
結果を見ればおわかりのように、X = [a | X] は「循環リスト」になります。右辺のリストにある X は自由変数ですが、Prolog はこのようなリストでも扱うことができます。また、右辺と左辺で同じ自由変数 X がありますが、このようなユニフィケーションでも Prolog では実行することができます。X は自由変数なので、X の値はリスト (セルの先頭アドレス) になります。セルの終端は X なので、先頭のセルとつながって循環リストになるわけです。
M.Hiroi は Prolog で循環リストを使ったことがなかったので、今回は FizzBuzz 問題に循環リストを使ってみました。なお、リストを循環させて解くアイデアは deepgreen さんに教えていただきました。deepgreen さんに感謝いたします。
リスト : FizzBuzz 問題 (循環リスト版)
fizzbuzz2(N, _, _, []) :- N > 100, !.
fizzbuzz2(N, [X | Xs], [Y | Ys], [Z | A]) :-
toStr(X, Y, N, Z),
N1 is N + 1,
fizzbuzz2(N1, Xs, Ys, A).
toStr(0, 0, N, N).
toStr(1, 0, _, fizz).
toStr(0, 1, _, buzz).
toStr(1, 1, _, fizzbuzz).
fizzbuzz2(A) :-
Xs = [0, 0, 1 | Xs],
Ys = [0, 0, 0, 0, 1 | Ys],
fizzbuzz2(1, Xs, Ys, A).
Xs と Ys が循環リストです。N が 3 の倍数のとき Xs の先頭要素は 1 になり、N が 5 の倍数のとき Ys の先頭要素は 1 になります。どちらの先頭要素も 1 のときが 15 の倍数になります。これを toStr でチェックして整数値 N を fizz, buzz, fizzbuzz に変換します。
ところで、unify を Prolog と同じような動作に変更することは、制限をはずすことで対応できると思います。ただし、循環したデータ構造を扱うことになるので、それにきちんと対応しないと無限ループに陥る場合があります。これはプログラムを Scheme に移植して試してみたいと思っています。
FizzBuzz 問題は 1 から 100 までの値を表示するとき、3 の倍数のときは Fizz を、5 の倍数ときは Buzz を表示するというものです。FizzBuzz 問題の詳細については Fizz Buzz - Wikipedia をお読みください。
FizzBuzz 問題を Prolog で解く場合、答えをリストで返すことにすると次のようになるでしょう。
リスト : FizzBuzz 問題
fizzbuzz(N, []) :- N > 100, !.
fizzbuzz(N, [fizzbuzz | A]) :-
N mod 15 =:= 0, !, N1 is N + 1, fizzbuzz(N1, A).
fizzbuzz(N, [fizz | A]) :-
N mod 3 =:= 0, !, N1 is N + 1, fizzbuzz(N1, A).
fizzbuzz(N, [buzz | A]) :-
N mod 5 =:= 0, !, N1 is N + 1, fizzbuzz(N1, A).
fizzbuzz(N, [N | A]) :- N1 is N + 1, fizzbuzz(N1, A).
実行結果を示します。
?- fizzbuzz(1, A), write(A), fail. [1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz, 16, 17, fizz, 19, buzz, fizz, 22, 23, fizz, buzz, 26, fizz, 28, 29, fizzbuzz, 31, 32, fizz, 34, buzz, fizz, 37, 38, fizz, buzz, 41, fizz, 43, 44, fizzbuzz, 46, 47, fizz, 49, buzz, fizz, 52, 53, fizz, buzz, 56, fizz, 58, 59, fizzbuzz, 61, 62, fizz, 64, buzz, fizz, 67, 68, fizz, buzz, 71, fizz, 73, 74, fizzbuzz, 76, 77, fizz, 79, buzz, fizz, 82, 83, fizz, buzz, 86, fizz, 88, 89, fizzbuzz, 91, 92, fizz, 94, buzz, fizz, 97, 98, fizz, buzz] No
ここで「演算子 mod を使わない」という制約をつけて、FizzBuzz 問題を解くことを考えてみてください。いろいろな方法があると思いますが、M.Hiroi は次のようにプログラムしてみました。
リスト : FizzBuzz 問題 (2)
fizzbuzz1(N, _, _, []) :- N > 100, !.
fizzbuzz1(N, X, Y, [fizzbuzz | A]) :-
N =:= X,
N =:= Y,
!,
N1 is N + 1,
X1 is X + 3,
Y1 is Y + 5,
fizzbuzz1(N1, X1, Y1, A).
fizzbuzz1(N, X, Y, [fizz | A]) :-
N =:= X,
!,
N1 is N + 1,
X1 is X + 3,
fizzbuzz1(N1, X1, Y, A).
fizzbuzz1(N, X, Y, [buzz | A]) :-
N =:= Y,
!,
N1 is N + 1,
Y1 is Y + 5,
fizzbuzz1(N1, X, Y1, A).
fizzbuzz1(N, X, Y, [N | A]) :-
N1 is N + 1, fizzbuzz1(N1, X, Y, A).
引数 X には次に現れる 3 の倍数を、引数 Y には次に現れる 5 の倍数をセットします。N と X と Y が等しい場合、N は 15 の倍数なので fizzbuzz に変換します。そして、X の値を +3, Y の値を +5 します。N と X が等しい場合、N は 3 の倍数なので fizz に変換します。X の値は +3 しますが、Y の値はそのままです。N と Y の値が等しい場合、N は 5 の倍数なので buzz に変換します。X の値はそのままにして Y の値を +5 します。それ以外の場合は N をそのまま出力します。
実行結果は次のようになります。
?- fizzbuzz1(1, 3, 5, A), write(A), fail. [1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz, 16, 17, fizz, 19, buzz, fizz, 22, 23, fizz, buzz, 26, fizz, 28, 29, fizzbuzz, 31, 32, fizz, 34, buzz, fizz, 37, 38, fizz, buzz, 41, fizz, 43, 44, fizzbuzz, 46, 47, fizz, 49, buzz, fizz, 52, 53, fizz, buzz, 56, fizz, 58, 59, fizzbuzz, 61, 62, fizz, 64, buzz, fizz, 67, 68, fizz, buzz, 71, fizz, 73, 74, fizzbuzz, 76, 77, fizz, 79, buzz, fizz, 82, 83, fizz, buzz, 86, fizz, 88, 89, fizzbuzz, 91, 92, fizz, 94, buzz, fizz, 97, 98, fizz, buzz] No
正常に動作していますね。
他の言語でも簡単にプログラムできるでしょう。たとえば、Common Lisp で do ループを使うと、プログラムは次のようになります。
リスト : FizzBuzz 問題 (3)
(defun fizzbuzz ()
(do ((n 1 (1+ n))
(a nil) (x 3) (y 5))
((> n 100) (nreverse a))
(cond ((= n x y)
(incf x 3)
(incf y 5)
(push 'fizzbuzz a))
((= n x)
(incf x 3)
(push 'fizz a))
((= n y)
(incf y 5)
(push 'buzz a))
(t (push n a)))))
実行結果を示します。
(fizzbuzz) => (1 2 fizz 4 buzz fizz 7 8 fizz buzz 11 fizz 13 14 fizzbuzz 16 17 fizz 19 buzz fizz 22 23 fizz buzz 26 fizz 28 29 fizzbuzz 31 32 fizz 34 buzz fizz 37 38 fizz buzz 41 fizz 43 44 fizzbuzz 46 47 fizz 49 buzz fizz 52 53 fizz buzz 56 fizz 58 59 fizzbuzz 61 62 fizz 64 buzz fizz 67 68 fizz buzz 71 fizz 73 74 fizzbuzz 76 77 fizz 79 buzz fizz 82 83 fizz buzz 86 fizz 88 89 fizzbuzz 91 92 fizz 94 buzz fizz 97 98 fizz buzz)
sasagawa さん が「整数の分割」を Prolog で プログラム されていたので、M.Hiroi も Prolog で作ってみました。整数の分割については、拙作のページ Yet Another Scheme Problems 問題 92, 問題 93 をお読みください。
最初に分割数を求めるプログラムを作りましょう。整数 n を k 以下で分割する総数を求める関数を p(n, k) で表します。参考文献 [1] によると、p(n, k) は次の式で表すことができるそうです。
p(n, 1) = 1 p(1, k) = 1 p(0, k) = 1 p(n, k) = p(n - 1, 1) + p(n - 2, 2) + ... + p(n - k, k)
r = 1 の場合は簡単ですね。n 個の 1 を選ぶ方法しかありません。同様に n = 1 の場合も、1 を選ぶ方法しかありません。なお、n = 0 の場合は 1 とします。Prolog の場合、この公式をそのままプログラムすることができます。次のリストを見てください。
リスト : 分割数
part_num(0, _, 1) :- !.
part_num(1, _, 1) :- !.
part_num(_, 1, 1) :- !.
part_num(N, K, 0) :- (N < 0 ; K < 1), !.
part_num(N, K, A) :-
N1 is N - K,
part_num(N1, K, A1),
K1 is K - 1,
part_num(N, K1, A2),
A is A1 + A2.
partition_number(N, A) :- part_num(N, N, A).
実際の処理は述語 part_num で行います。最初の 3 つの規則で、分割数が 1 になる場合を定義しています。次の規則は N が負または K が 1 未満の場合を表します。この場合、分割数は 0 になります。最後の規則で、p(n - 1, 1) + ... + p(n - k, k) を計算します。プログラムでは K の値をひとつずつ減らしていることに注意してください。
それでは実際に SWI-Prolog で試してみましょう。
?- between(1, 20, I), partition_number(I, N), write(N), nl, fail. 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627 No
分割の仕方を列挙する述語 partition_of_integer も公式にそってプログラムすることができます。次のリストを見てください。
リスト : 整数の分割
part_int(0, _, []) :- !.
part_int(N, K, [K | A]) :-
N1 is N - K,
N1 >= 0,
part_int(N1, K, A).
part_int(N, K, A) :-
K1 is K - 1,
K1 >= 1,
part_int(N, K1, A).
partition_of_integer(N, A) :- part_int(N, N, A).
実際の処理は述語 part_int で行います。最初の規則は N が 0 の場合です。分割する整数がないので空リストになります。これが再帰呼び出しの停止条件になります。次の規則は整数 N から K を選択する場合です。N - K が 0 以上であれば K を選択できるので、part_int を再帰呼び出ししてリスト A に K を追加します。
N - K が負になった場合は 3 番目の規則が選択されます。ここで K の値を -1 して part_int を再帰呼び出しします。K - 1 が 1 未満の場合は失敗してバックトラックすることになります。これで分割の仕方をすべて求めることができます。
それでは実際に試してみましょう。
?- partition_of_integer(6, L), write(L), nl, fail. [6] [5, 1] [4, 2] [4, 1, 1] [3, 3] [3, 2, 1] [3, 1, 1, 1] [2, 2, 2] [2, 2, 1, 1] [2, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1] No ?- partition_of_integer(7, L), write(L), nl, fail. [7] [6, 1] [5, 2] [5, 1, 1] [4, 3] [4, 2, 1] [4, 1, 1, 1] [3, 3, 1] [3, 2, 2] [3, 2, 1, 1] [3, 1, 1, 1, 1] [2, 2, 2, 1] [2, 2, 1, 1, 1] [2, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1] No
やっぱり Prolog は面白いですね。Prolog でのプログラミングはひさしぶりだったので、頭を切り替えるのに時間がかかりました。最初に作ったプログラムはひどいもので、ぜんぜん Prolog らしくなかったのですが、試行錯誤しているうちに今のプログラムになりました。けっきょく、公式をそのままプログラムしているだけですが、それが Prolog らしくてよいかもしれない、と思っています。
ＣＱ出版社 発行の月刊誌 Interface 7 月号 (5/25 発売) で、M.Hiroi は特集「CPUの動作原理とアセンブラの基礎知識」の第 5 章「アセンブリ言語の基本を理解する」と第 6 章「Ｃ言語とコンパイル結果のアセンブリ言語の比較」を執筆しました。第 1 章から第 4 章は中森章氏が執筆されていて、CPU の動作原理をわかりやすく丁寧に解説されています。興味のある方はぜひお読みください。
一般に、関数の呼び出し方には二つの方法があります。一つが「値呼び (call by value) 」で、もう一つが「参照呼び (call by reference) 」です。近代的なプログラミング言語では「値呼び」が主流です。
値呼びと参照呼びは「値渡し」と「参照渡し」と呼ばれることもあります。また、Ｃ言語は値呼びですが、変数やデータのアドレスを関数に渡すことを「参照渡し」と呼ぶ場合があって、参照呼びと混同することがあります。拙作の入門講座 (Python, Ruby, Java) でも、オブジェクトへの参照を渡しているから参照呼びと間違って記述していました。訂正するとともに深くお詫び申しあげます。
参照呼びを簡単に説明すると、呼び出し先 (callee) の仮引数の値を更新すると、それが呼び出し元 (caller) の変数にも直ちに反映されるような呼び出し方のことをいいます。値呼びと参照呼びは関数呼び出しにおける仮引数と実引数の対応を表したもので、渡される値のデータ型とは関係ありません。
Ｃ言語はポインタを使って参照呼びと同じことができます。次のリストを見てください。
リスト : 値の交換
#include <stdio.h>
void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int main()
{
int a = 10;
int b = 20;
swap(&a, &b);
printf("a = %d, b = %d\n", a, b);
return 0;
}
& 演算子で変数 a, b のアドレスを取り出し、関数 swap の仮引数 x, y に渡します。これで関数 main の変数 a, b の値を swap で書き換えることができますが、これを「参照呼び」とはいいません。Ｃ言語は値呼びであり、あくまでも変数のアドレスを値渡ししているだけなのです。
swap を呼び出す箇所は次のようにコンパイルされます。
リスト : swap を呼び出す箇所のアセンブリコード (Ｃ言語 : gcc)
movl $10, -8(%ebp)
movl $20, -4(%ebp)
leal -4(%ebp), %eax
movl %eax, 4(%esp)
leal -8(%ebp), %eax
movl %eax, (%esp)
call _swap
movl はデータの転送命令、leal はアドレスの転送命令です。leal で局所変数のアドレスをレジスタ EAX にセットし、それを movel でスタックに積んでいることがわかります。
ここで、変数に値を代入する式 a = 10, b = 20 に注目してください。= の右側を「右辺式」、左側を「左辺式」といいます。一般に、左辺式は変数やその定義を表していて、右辺式は値を生成する式になります。値呼びは右辺の式 (値) が渡されると考えてください。Ｃ言語の場合、アドレスを取り出す演算子 &a と &b は swap の仮引数 x と y の値を表す右辺式と考えることができます。
これに対し、参照呼びは左辺式 (変数) が渡されると考えてください。たとえば、値を交換する swap はＣ++の「参照」を使うと次のようになります。
リスト : 値の交換
#include <iostream>
using namespace std;
void swap(int& x, int& y)
{
int tmp = x;
x = y;
y = tmp;
}
int main(void)
{
int a = 10;
int b = 20;
swap(a, b);
cout << "a = " << a << endl;
cout << "b = " << b << endl;
return 0;
}
Ｃ++は値呼びが基本ですが、関数の仮引数に & を付けると、その引数は参照呼びになります。main() では swap(a, b) を呼び出していますが、swap の仮引数 x, y は参照呼びなので、変数 a, b の参照 (アドレス) が x, y に渡されます。そして、x, y の値を更新すると、呼び出し元の変数 a, b の値も更新されます。また、swap(a, 20) のような呼び出しはコンパイルエラーになります。
swap を呼び出す箇所は次のようにコンパイルされます。
リスト : swap を呼び出す箇所のアセンブリコード (Ｃ++ : g++)
movl $10, -8(%ebp)
movl $20, -4(%ebp)
leal -4(%ebp), %eax
movl %eax, 4(%esp)
leal -8(%ebp), %eax
movl %eax, (%esp)
call __Z4swapRiS_
Ｃ言語と同様に leal で局所変数のアドレスをレジスタ EAX にセットし、それを movel でスタックに積んでいます。けっきょく、Ｃ++の参照も変数のアドレスを仮引数に渡すことで実現しているのですが、それを処理系が自動的に行ってくれるところが「参照呼び」のメリットです。Ｃ++ の場合はコンパイル時に型チェックも行われるので、Ｃ言語のようにポインタを使って参照呼びを実現するよりも安全といえるでしょう。なお、Ｃ++の参照は高機能で、参照呼びだけではなく、いろいろなところでポインタの代わりに使うことができます。
このほかにも参照呼びをサポートしている言語があります。たとえば Pascal は値呼びが基本ですが、関数や手続きの仮引数に var を付けると参照呼びになります。Pascal はこの機能を「変数引数」または「変数パラメータ (variable parameter) 」と呼んでいます。
スクリプト言語では Perl が参照呼びです。Perl の場合、実引数は $_ という特別な配列に格納されていて、その要素を書き換えると、呼び出し元の変数の値を書き換えることができます。Perl では $_ から値を取り出して局所変数にセットすることで「値呼び」と同様の動作になります。
ＣＱ出版社 発行の月刊誌 Interface 10 月号 (8/25発売) で、M.Hiroi は特集「進化するコンピュータ・アーキテクチャの 30 年」の第 6 章「プログラミング言語の歴史」を執筆しました。拙作の記事はともかく、コンピュータが発展してきた歴史を振り返る素晴らしい特集記事なので、興味のある方はぜひお読みください。