ゼロからはじめるスクリプト言語製作: プログラミング課題に挑戦する②（１７日目）
前回につづき、スクリプト言語製作の仕上げとして、やや実践的なプログラミング課題を解きながら、現状で欠けている機能の追加に取り組んでいこう。
今日は、プロジェクト・オイラーの第２問に挑戦だ。
Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
（訳）
偶数のフィボナッチ数
フィボナッチ数列の新しい項は、手前にある２項を加算することで求められる。数列の先頭を１、２とした場合、１０項目までは次のようになる：
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
では４００万以下の項で構成されるフィボナッチ数列を考えたときに、偶数となった項の合計はいくつになるか？
前回と同様、このプロジェクト・オイラーの目的はこれを（あなたが）プログラミングによってコンピューターに回答させることにある。
いま足りてない機能は何だろうか
早速、製作中のスクリプト言語を使い、この問題を解いてみた。
↓以下のスクリプトには脳内で好き勝手に妄想した、今日現在定義されていない機能やシンボルが含まれているが、そのまま読んでみてほしい。
($ 'is-even (lambda (' v) (' == (% v 2) 0)))
($ 'next-fibonacci
(let
($ 'terms (' 1 2))
(lambda (')
(' do
($ 'newterm (+ (car (@ 0 terms)) (car (@ 1 terms))))
($ 'retterm (car terms))
(car= (@ 0 terms) (car (@ 1 terms)))
(car= (@ 1 terms) newterm)
retterm
)
)
)
)
(let
($ 'sum 0)
($ 'n (next-fibonacci))
(while (<= n 4000000)
(if (is-even n) ($= 'sum (+ sum n)))
($= 'n (next-fibonacci))
)
sum
)まず関数 is-even で、引数 v が偶数かどうかを判別できるようにする。次に関数 next-fibonacci で数列の先頭から順に項を取得できるようにする。引数は無いのでシンボル lambda の１つめの S 式は (‘) となっている。最後に while で next-fibonacci からの数値の取り出しを繰り返しながら、条件が合うときにだけ変数 sum に項を足していく。
過去の記事で紹介したフィボナッチ数列生成のスクリプトは、フィボナッチ数列の定義に忠実でナイーブな実装にしたが、演算量が多すぎるという課題があった。このスクリプト例では、複数のデータを保持するローカル変数 terms を介して、この課題を回避しようとしている。
そのために脳内定義した新たなシンボルは以下の３つである。
@ <num> <cell>: 指定された番目のセルを返す
car <cell>: セルの要素を返す
car= <cell> <expr>: セルの要素に代入する
ローカル変数 terms に２つの numberv 型を格納しておき、next-fibonacci が呼ばれるたびに０つめと１つめの要素に対して代入を行っている（car= が２行並んでるところ）。terms が保持している numberv 型は常に２つのままだ。
フィボナッチ数列生成に関しては、別のアプローチもできる。↓以下のスクリプト例を見てほしい。
($ 'next-fibonacci
(let
($ 'terms (' 1 2))
(lambda (')
(' do
($ 'newterm (+ (car (@ 0 terms)) (car (@ 1 terms))))
($ 'retterm (car terms))
(cdr= (@ 1 terms) (list newterm))
($= 'terms (cdr terms))
retterm
)
)
)
)このスクリプト例では、ローカル変数 terms の扱い方が異なっている。terms に２つの numberv 型を格納しているところは同じだが、next-fibonacci が呼ばれるたびに terms の末尾に新たな項を連結し、terms の先頭を切り捨てている。
ここで脳内定義した新たなシンボルは以下の２つである。
cdr <cell>: セルの残りを返す
cdr= <cell> <cell>: セルの残りに代入する
ほかにもいくつか便利そうなシンボルを追加しておくことにしよう。
# <cell/enum>: 引数の要素数を返す
@first <cell>: 最初のセルを返す
@last <cell>: 末尾のセルを返す
これでデータ構造を操作する方法が最低限揃うことになる。
そして脳内定義したシンボルを実装していこう。
↓以下にセルの要素を操作するシンボル car/car= の実装を示す。
public static expr car(expr args, bool forReadOnly)
{
cell? arg0 = args.astype<cell>();
cell? arg1 = arg0?.next().astype<cell>();
cell? arg2 = arg1?.next().astype<cell>();
if ((forReadOnly ? arg1 : arg2) is not null) throw new Exception("wrong number of args");
cell cells = arg0?.element().eval().cast<cell>() ?? throw new Exception("invalid element type");
if (forReadOnly)
{
return cells.element();
}
expr value = arg1?.element().eval() ?? throw new Exception("invalid element type");
return cells.element(value);
}そのほかの実装については割愛するが、特筆すべき点は無かった。セルの残りを操作するシンボル cdr/cdr= については これとほぼ同じ実装になっている。
さていろいろとデータ操作用のシンボルが整ったので、フィボナッチ数列の生成スクリプトを改良してみよう。先のスクリプト例の next-fibonacci はフィボナッチ数列を先頭から順番に取得することしかできないという制約があった。これを使いやすくするために、指定されたｎ番目の項を返せるよう terms のデータ構造を固定長から可変長に変更した。
($ 'fibonacci
(let
($ 'terms (' 1 2))
(lambda (' n)
(' do
(for 'i (range (# terms) (+ n 1))
($ 'newterm (+ (car (@ (- i 2) terms)) (car (@ (- i 1) terms))))
(cdr= (@last terms) (list newterm))
)
(car (@ n terms))
)
)
)
)
意図通りちゃんと動作しているようだ。
最後に、本丸であるプロジェクトオイラーの第２問を解く様子が↓以下の画面だ。
今日はここまで、おつかれさま。
冗長コードの整理を行った結果、Program.cs は 81 行、Type.cs は 302 行、Core.cs は 333 行。コード量は 60 行の増加。
小さな発見
Core.cs の関数には、S 式の引数を評価した結果が特定の型であることを期待するものが多い。「何個の引数を受け取り、何番目がどの型であるべきか」を汎用的に記述するため、Core.evalArgs() というジェネリック関数を導入することにした。
evalArgs() の使用例として、シンボル range の実装 Core.range() のコードを↓以下に示す。
public static IEnumerator<expr> range(expr args)
{
cell? argLeft = evalArgs(args.astype<cell>(), out numberv? v0, out numberv? v1, out numberv? v2);
if (v0 is null || argLeft is not null) throw new Exception("wrong number of args");
(long b, long e) = v1 is null ? (0, v0._val) : (v0._val, v1._val);
long d = v2?._val ?? 1;
for (long i = b; (d < 0) ? i > e : i < e; i += d)
{
yield return new numberv(i);
}
} private static cell? evalArgs<T0>(cell? arg0, out T0? v0) where T0 : expr
{
expr? v0_ = arg0?._car.eval();
v0 = v0_?.cast<T0>();
return arg0?._cdr.astype<cell>();
}
:
private static cell? evalArgs<T0, T1, T2>(cell? arg0, out T0? v0, out T1? v1, out T2? v2) where T0 : expr where T1 : expr where T2 : expr
{
cell? arg1 = evalArgs<T0>(arg0, out v0);
cell? arg2 = evalArgs<T1>(arg1, out v1);
return evalArgs<T2>(arg2, out v2);
}Core.range() は１つ以上３つ以下の numberv 型引数を期待しているため、呼び出しは evalArgs(args.astype<cell>(), out numberv? v0, out numberv? v1, out numberv? v2) となっている。
ここで注目したいのは、型パラメータ T0・T1・T2 は numberv であって、numberv? ではないという点だ。
C# 言語の仕様上、型パラメータには null 許容型を指定することができないらしいのだ。
これはすこし残念だ。
「ジェネリック関数が呼び出されたときの型パラメータが null 許容型かどうかを区別して、そのジェネリック関数の挙動を変える」といったことはできない、ということになる。
実装を見ると分かるように、与えられた S 式引数の数が正しかったかどうかの判定は、呼び出し元の Core.range() が担っているのだが、例えば「シンボル range の１つめの numberv 引数は省略できない」ということを示すために、「evalArgs() の２つめの引数を out numberv とし、３つめ４つめの引数を out numberv?、つまり null 許容型とする」ということが実現できれば、evalArgs() 内部で引数の過不足をスマートに判断できたのだが。
ということで。
次回もまたプログラミング課題からヒントを得て、スクリプト言語の機能を充実させていこうと思う。
乞うご期待。