ゼロからはじめるスクリプト言語製作: プログラミング課題に挑戦する①（１６日目）

前回の実装によって、ユーザーは制御構文を駆使して 処理を分岐させたりループさせたりすることができるようになった。過去に変数宣言や関数宣言にも対応できているので、すでにプログラミングにおける重要概念はカバーできていると思う。
今回からはスクリプト言語の仕上げに入っていこう。やや実践的なプログラミング課題を解きながら、現状では欠けている機能の追加に取り組んでいく。

ここでの「やや実践的なプログラミング課題」には、プロジェクト・オイラーを活用しようと思う。

プロジェクト・オイラーは、数学やプログラミングなどに興味を持つ大人や学生が主な利用者であり、プログラミング (コンピュータ)による一連の計算問題の解決を目的としたウェブサイトである。 400以上の問題の他に毎週末毎に1問ずつ増えており、様々な難問が用意されているが、 一般的なスペックのパソコンで効率的なアルゴリズムを用いれば、いずれも1分未満で解ける。

Wikipedia より

どんな内容なのか。今日のところは有名な第１問に取り組んでみよう。

Multiples of 3 or 5
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

（訳）
３の倍数、５の倍数
１０未満の自然数のうち３の倍数と５の倍数を取り出すと、３、５、６、９となる。これらの倍数を合計すると２３になる。
では１０００未満の自然数で同様に合計するといくつになるか？

Project Euler の Problem 1 より

この問題の場合、中学校で習うレベルの代数学や集合論の知識を活用すれば、コンピューターを使わずとも解くことができてしまうが、このプロジェクト・オイラーの目的はこれを（あなたが）プログラミングによってコンピューターに回答させることにある。
（そしてこの記事では、それを製作中のスクリプト言語で実現可能かどうかを検証し、不足機能を見つけて追加実装していくことを目的としている。）

ということで早速、製作中のスクリプト言語を使い、この問題を解いてみた。
↓以下のスクリプトには脳内で好き勝手に妄想した、今日現在定義されていない機能やシンボルが含まれている。

($ 'is-multiples-of-3-5 (lambda (' v) (' == (* (% v 3) (% v 5)) 0)))
(let
  ($ 'sum 0)
  (for 'i (range 1 1000)
    (if (is-multiples-of-3-5 i) ($= 'sum (+ sum i)))
  )
  sum
)

関数 is-multiples-of-3-5 で倍数かどうかを判定できるようにして、それを for と if で繰り返しながら、条件が合えば変数 sum に足し上げている。
このコードが実際に動作するために足りていない機能を↓以下に列挙した。

・シンボル range は、引数に指定された条件に従った整数列を生成する
→ (range 5) は 0, 1, 2, 3, 4 を、(range 1 6) は 1, 2, 3, 4, 5 を、(range 5 0 -1) は 5, 4, 3, 2, 1 をそれぞれ列挙する

数値を列挙していく

前回１０個のフィボナッチ数列を表示したときに、for の２つめの引数には cell 型のリスト、具体的には (’ 0 1 2 3 4 5 6 7 8 9) を指定していた。しかし今回の問題のように１０００個必要となれば、何か別の手段が必要になってくる。そこで range というシンボルを定義し、仕様としては Python 標準の range() に準拠するということにしたい。

数値が１０００個格納された cell 型の値をシンボル range が返すように実装できれば、前回実装した Type.cell.GetEnumerator() によって数値の列挙は可能になる。万事解決するのでそういう実装を選択しても構わないが、今回はそれとは別の選択をしていこうと思う。将来の機能拡張の布石として。

カギとなるのは yield return 文だ。↓以下の Core.range() のコードを見てほしい。

		public static IEnumerator<expr> range(expr args)
		{
			cell? arg0 = args.astype<cell>();
			cell? arg1 = arg0?.next().astype<cell>();
			cell? arg2 = arg1?.next().astype<cell>();
			cell? arg3 = arg2?.next().astype<cell>();
			if (arg0 is null || arg3 is not null) throw new Exception("wrong number of args");
			long b, e, d = arg2?.element().eval().cast<numberv>()._val ?? 1;
			(b, e) = arg1 is null ? (0, arg0.element().eval().cast<numberv>()._val) : (arg0.element().eval().cast<numberv>()._val, arg1.element().eval().cast<numberv>()._val);
			for (long i = b; (d < 0) ? i > e : i < e; i += d)
			{
				yield return new numberv(i);
			}
		}

for 文の内側にある yield return 文は条件によっては何度も実行されるが、２度目以降の実行は「次の要素」が要求されるまでは保留される。そのため cell 型を生成する実装と比較して余計なメモリ確保が減るなど、プログラム実行上のデメリットを回避することができる。(range 10000000) などと実行したときの挙動の違いを想像してみてほしい。

列挙を担う型

また見ての通り、Core.range() の戻り値の型は IEnumerator<expr> になる。これを格納する型はこれまでのところ定義していない。これまで定義してきた中では functionv 型が近い役割なのだが、戻り値の型は expr だった。

ということで、今回は Type.enumeration  型を新たに定義することにした。
※ 行頭「+」箇所は行追加。

		public delegate expr evaluator(expr args);
		public class functionv : atomv<evaluator>
		{
			public functionv(evaluator val) : base(val)
			{
			}

			public expr eval(expr args) => _val(args);
		}

+		public delegate IEnumerator<expr> enumerator(expr args);
+		public class enumerationv : atomv<enumerator>
+		{
+			public enumerationv(enumerator val) : base(val)
+			{
+			}
+
+			public expr eval(expr args)
+			{
+				_enumeration = _val(args);
+				return this;
+			}
+
+			public override IEnumerator<expr> GetEnumerator() => _enumeration ?? throw new Exception("enumeration not initiated");
+			private IEnumerator<expr>? _enumeration;
+		}

enumerationv 型の実装は functionv 型の実装がベースになっている。GetEnumerator() が追加実装されている点に注意してほしい。

Type.cell 型に↓以下の変更を加える必要があった。
※ 行頭「-」箇所は行削除。行頭「+」箇所は行追加。

		public class cell : expr
		{
			:
			public override expr eval()
			{
-				functionv? func = _car.eval() as functionv ?? throw new Exception("eval against non-function");
-				return func.eval(_cdr);
+				expr arg0 = _car.eval();
+				enumerationv? enum_ = arg0.astype<enumerationv>();
+				if (enum_ is not null)
+				{
+					return enum_.eval(_cdr);
+				}
+				functionv? func = arg0.astype<functionv>();
+				if (func is not null)
+				{
+					return func.eval(_cdr);
+				}
+				throw new Exception("eval against non-function");
			}

			:
		}

enumerationv のシンボル定義を追加して、コンパイル＆デバッグしたのが下図である。
※ 行頭「+」箇所は行追加。

		static Core()
		{
			new symbolv("writeln").assign(new functionv(Core.writeln));
			new symbolv("+").assign(new functionv(Core.add));
			new symbolv("-").assign(new functionv(Core.sub));
			:
+			new symbolv("range").assign(new enumerationv(Core.range));
		}

第１問の回答を算出しているところ（答えは公表しません）

今日はここまで、おつかれさま。
Program.cs は計 81 行、Type.cs は計 305 行、Core.cs は 270 行。コード量は 43 行の増加。

ブラウザー実行環境 replit のご紹介

今日までの成果を実際に動作させて、ブラウザー上で確認できるような環境を準備した。

興味があれば下記リンク先で「Run」ボタンをクリックしてみてほしい。

BuildYourOwnScriptProcessor-Chapter2

ユーザーとしてスクリプトを入力して、実際に実行させてみてほしい。
「Show files」ボタンをクリックすると、コード全体がどんな構成になっているのかを確認することもできる。

次回もプログラミング課題からヒントを得て、スクリプト言語の機能を充実させていこうと思う。
乞うご期待。