ゼロからはじめるスクリプト言語製作: コードブロックとローカルスコープを実装する（１４日目）

前回の実装によって、ユーザーは変数と関数を駆使して 自由に計算ができるようになった。今回からは、いくつかの代表的な制御構文に取り組んでいく。

ということで今回の実装ゴールを以下のように課して、実装を進めていくことにしよう。

＜要件１＞
1) シンボル do・break・which・list は多数の引数を取り、先頭から順番に評価していく（引数が全く無いときは nil を返す）
2) do は引数すべてを評価し、最後の評価結果を返す
3) break は nil が得られるまで評価を続け、その評価結果（nil）を返す（すべてが nil 以外のときは末尾の評価結果を返す）
4) which は nil 以外が得られるまで評価を続け、その評価結果を返す（すべてが nil のときは nil を返す）
5) list は引数すべてを評価し、すべての評価結果をつなげたリストを返す

> (do 1 null 2)
===> 2
> (break 3 null 4 null)
===> nil
> (which null 5 null 6)
===> 5
> (list 7 null null 8)
===> 7 nil nil 8

＜要件２＞
6) シンボル let は多数の引数を取り、先頭から順番に評価していく（引数が全く無いときは nil を返す）
7) let はローカルスコープを確保してから、引数すべてを評価し、最後の引数の評価結果を返す。引数の中に変数を宣言する $ 命令がある場合は、その変数をローカル変数として扱う
8) シンボル $= は２つの引数を取り、１つめは symbolv 型でなければならない
9) １つめの symbolv は定義済み変数名を示し、それを評価したときに２つめの expr を返す

> (let
>>> ($ 'sum 0)
>>> ($= 'sum (+ sum 1))
>>> ($= 'sum (+ sum 2))
>>> ($= 'sum (+ sum 3))
>>> sum)
===> 6

４つのコードブロックを１つの関数で表す

要件１を落ちついて眺めていると、それぞれの挙動は非常に似通っていることに気が付く。与えられた引数を順番に評価していくところ（①）、戻り値の初期値は nil であるところ（②）は共通している。
逆に何を返すか（③）、いつ処理をやめるか（④）、というところは異なっている。

連載９日目で整数の四則演算を実装した際に、演算部以外を Core.reduce() としてまとめて処理したことを覚えているだろうか。四則演算では Core.reduce() に①②③を指定可能としていたが、コードブロックの実装においては新たに④を加える形に増築すれば良さそうだ。

そのような都合の良い Core.reduce() があれば、シンボル do の実装 Core.do_() は↓以下の１行で表現できる。

		public static expr do_(expr args) => reduce(args.astype<cell>(), new nil(), (expr left, expr right) => right, (cell? args, expr other) => args?.next().astype<cell>());

３番目の引数は、戻り値の算出方法を示している。引数 left はそれまでの評価結果を、引数 right は新たに処理した命令の評価結果を示しており、見てのとおりいつでも right の値で上書きしている。
４番目の引数は、逐次処理の継続方法を示している。引数 args は命令の羅列を、引数 other は直近の命令の評価結果を示しており、見てのとおり args に命令が続く限り処理を継続することになっている。

参考までに変更後の Core.reduce() のコードを↓以下に示しておこう。

		public static expr reduce(cell? args, expr value, Func<expr, expr, expr> func0, Func<cell?, expr, cell?> func1)
		{
			if (args is null) return value;
			expr arg0 = args.element().eval();
			value = func0(value, arg0);
			cell? next = func1(args, arg0);
			return reduce(next, value, func0, func1);
		}

残る３つのシンボルについても、それぞれ１行で表現できている。これで要件１を満たすことができる。

		public static expr break_(expr args) => reduce(args.astype<cell>(), new nil(), (expr left, expr right) => right, (cell? args, expr other) => other is nil ? null : args?.next().astype<cell>());
		public static expr which_(expr args) => reduce(args.astype<cell>(), new nil(), (expr left, expr right) => right, (cell? args, expr other) => other is not nil ? null : args?.next().astype<cell>());
		public static expr list_(expr args) => reduce(args.astype<cell>(), new nil(), (expr left, expr right) => left.astype<cell>()?.append(new cell(right)) ?? new cell(right), (cell? args, expr other) => args?.next().astype<cell>());

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

		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("do").assign(new functionv(Core.do_));
+			new symbolv("break").assign(new functionv(Core.break_));
+			new symbolv("which").assign(new functionv(Core.which_));
+			new symbolv("list").assign(new functionv(Core.list_));
		}

さまざまなコードブロックの挙動の違い
（writeln は評価結果としては常に nil を返すことに注意）

ローカル変数を扱うための仕込み

次に要件２を見ていこう。シンボル let の定義のほとんどは、do の定義と一致する。違うのはローカルスコープが確保されるかどうか、というだけだ。

さて一般的なプログラミング言語と同様にローカルスコープが有益にふるまうには、どのような要件が必要となるのだろうか。
少しばかり頭をひねってみると、以下のような要件があることはすぐに思い付く。

・ローカルスコープの中でシンボル定義した場合は、ローカルスコープから出た時に、そのシンボルには（シンボル名を介して直接的に）読み書きができなくなる
・上位のスコープに同名のシンボルがある場合は、ローカルスコープの中から上位のシンボルには（シンボル名を介して直接的に）読み書きができなくなる

前回までで、部分的にはこれらを実現できている。
しかし実際にはさらにもう一歩、押し進めて考えた方が良い。

・関数は、自身が定義されたときのスコープを保持し、呼び出された際には保持したスコープで処理本体を評価する

少し分かりづらいので、実例を挙げよう。
Wikipedia の動的スコープという見出しには、↓以下のような疑似コードが載っている。

A {
  print x
}

B {
  var x
  call A  // Aの中からxを参照することができる
}

C {
  var y
  call A  // Aの中からxを参照することはできない
}

コメントにあるように、プログラミング言語の仕様として「コードブロック A が関数として定義されているときに、これをコードブロック B から呼び出したときは変数 x を参照できるが、コードブロック C から呼び出したときは変数 x を参照できずエラーとなる」と規定することもできる。これを動的スコープというらしい。

動的スコープの問題点は、別のコードブロックの呼び出しが今のスコープに対する副作用を一切制限できない前提となっている点だ。これはコードの保守性の問題を引き起こすので、関数を作る側も使う側も気が抜けないのだ。

個人製作のスクリプト言語なんかで コードの保守性まで考えるのは少し大袈裟に感じるかもしれないけど、先に紹介した要件一点を導入するだけで今の弱点を克服できるし、その実装も実はそこまで複雑ということもない。

新しくなった Type.symbolv.scope のコードは↓以下の通りだ。
※ 行頭「-」箇所は行削除。行頭「+」箇所は行追加。

		public class symbolv : atomv<string>, IDisposable
		{
			:

-			private static Dictionary<string, expr> _scope = new Dictionary<string, expr>();
+			private static symbols _symbolPool = new symbols(null);
			private Action _disposer = () => {};

+			public class symbols : Dictionary<string, expr>
+			{
+				public symbols(symbols? parent) => _parent = parent;
+				public expr get(string key) => TryGetValue(key, out expr? val) ? val : _parent?.get(key) ?? throw new Exception($"unknown symbol [{key}]");
+				public expr set(string key, expr val) => TryGetValue(key, out var _) ? this[key] = val : _parent?.set(key, val) ?? throw new Exception($"unknown symbol [{key}]");
+				private readonly symbols? _parent;
+			}

-			public class scope : List<symbolv>, IDisposable
+			public class scope : IDisposable
			{
+				public scope(scope? dedicatedScope = null) => (_storedPool, _symbolPool) = (_symbolPool, new symbols(dedicatedScope?._storedPool ?? _symbolPool));
-				public void Dispose() => ForEach((symbolv v) => v.Dispose());
+				public void Dispose() => _symbolPool = _storedPool;
+				private readonly symbols _storedPool;
			}
		}

scope は階層的に生成され、それぞれには親となるスコープを指定できる。デフォルトでは現在のスコープが親スコープとなる。大元となるグローバルスコープには、親スコープは存在しない。
またローカルスコープを表す Type.symbolv.scope とは別に、シンボルプールを表す Type.symbolv.symbols を新設している。詳細は割愛するが、これでローカルスコープの生存区間と、定義されたシンボル達の生存区間を分離できている。

シンボルの代入の実装 Type.symbolv.assign() も、少し変更になった。
※ 行頭「-」箇所は行削除。行頭「+」箇所は行追加。

		public class symbolv : atomv<string>, IDisposable
		{
			:

-			public symbolv assign(expr val)
+			public symbolv assign(expr val, bool localScope = true)
			{
-				_scope[_val] = val;
-				_disposer += () => _scope.Remove(_val);
+				if (localScope)
+				{
+					if (!_symbolPool.TryGetValue(_val, out var _))
+					{
+						_disposer += () => _symbolPool.Remove(_val);
+					}
+					_symbolPool[_val] = val;
+				}
+				else
+				{
+					_symbolPool.set(_val, val);
+				}
				return this;
			}

			:
		}

仕上げに lambda における関数定義の実処理部分 Core.binder() の変更箇所を↓以下に示す。
※ 行頭「-」箇所は行削除。行頭「+」箇所は行追加。

-		private static evaluator binder(expr keys, expr body)
+		private static evaluator binder(symbolv.scope dedicatedScope, expr keys, expr body)
		{
			return (expr args) => {
+				expr values = list_(args);
-				using var symbols = new symbolv.scope();
+				using var symbols = new symbolv.scope(dedicatedScope);
-				for (cell? key = keys.astype<cell>(), arg = args.astype<cell>(); key is not null || arg is not null; (key, arg) = (key.next().astype<cell>(), arg.next().astype<cell>()))
+				for (cell? key = keys.astype<cell>(), arg = values.astype<cell>(); key is not null || arg is not null; (key, arg) = (key.next().astype<cell>(), arg.next().astype<cell>()))
				{
					if (key is null || arg is null)
					{
						throw new Exception("wrong number of args");
					}
-					symbols.Add(binder0(key, arg));
+					symbolv key0 = key.element().cast<symbolv>() ?? throw new Exception("invalid element type");
+					expr arg0 = arg.element();
+					new symbolv(key0._val).assign(arg0, true);
				}
				return body.eval();
			};
		}

最後に変数を宣言せずに代入するだけのオプションを Core.assign() に追加した。
※ 行頭「-」箇所は行削除。行頭「+」箇所は行追加。

-		public static expr assign(expr args)
+		public static expr assign(expr args, bool localScope = true)
		{
			cell? arg0 = args.astype<cell>();
			cell? arg1 = arg0?.next().astype<cell>();
			cell? arg2 = arg1?.next().astype<cell>();
			if (arg2 is not null) throw new Exception("wrong number of args");
			expr key = arg0?.element().eval() ?? throw new Exception("invalid element type");
			expr value = arg1?.element().eval() ?? throw new Exception("invalid element type");
-			return key.cast<symbolv>().assign(value);
+			return key.cast<symbolv>().assign(value, localScope);
		}

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

		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("$").assign(new functionv(Core.assign));
+			new symbolv("$").assign(new functionv((expr args) => Core.assign(args, true)));
+			new symbolv("$=").assign(new functionv((expr args) => Core.assign(args, false)));
			:
+			new symbolv("let").assign(new functionv(Core.let_));
		}

コードブロックにローカル変数を定義して、読み書きできた！
let を抜けた後はローカル変数にアクセスできない

これで要件２を実現することができた。ローカルスコープに関する副作用などは、これで一掃解決できたように思う。

今回実現した静的スコープを応用すると、より多様な書き方ができるようになるが、中でもクロージャーが実現できるようになった点は興味深い。
↓以下のコード例を見てほしい。

静的スコープを応用したクロージャーが実現できた！

変数 counter には let を評価した結果が代入される。それは lambda によって生成された functionv となるので、counter は関数としてふるまうことができる。functionv の処理本体からは let で区切られたローカルスコープにアクセスできるので、その変数 v を使って呼び出されるたびに増加する値を返すことができる。これで全体としてはカウンターとしてふるまうことができる。

さらにカウンターを複数生成できるようにしてみた。

counter-generator は互いに干渉しないカウンターを生成する

いやー、良くできているなぁ（自画自賛）。

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