読者です 読者をやめる 読者になる 読者になる

亀岡的プログラマ日記

京都のベッドタウン、亀岡よりだらだらとお送りいたします。

だらTで作るBrainFuckな実行装置 その3

C#

考えてみたらコンパイラでもなんでもなくて、Executer:実行機などというべきですよね、フツー。

そんなこんなで、多分BrainFuckの中では一番考えないといけない、開き括弧・閉じ括弧を行なって行きましょう。
まずはともあれテストです。ロジック的なことを考えると、普通の開き・閉じに加えて、ネストされた開き・閉じをチェックしておくのがよさそうです。
もう一度BrainFuckの仕様をおさらい。

  1. > ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。
  2. < ポインタをデクリメントする。C言語の「ptr--;」に相当。 + ポインタが指す値をインクリメントする。C言語の「(*ptr)++;」に相当。
  3. - ポインタが指す値をデクリメントする。C言語の「(*ptr)--;」に相当。
  4. . ポインタが指す値を出力に書き出す。C言語の「putchar(*ptr);」に相当。
  5. , 入力から1バイト読み込んで、ポインタが指す先に代入する。C言語の「*ptr=getchar();」に相当。
  6. [ ポインタが指す値が0なら、対応する ] の直後までジャンプする。C言語の「while(*ptr){」に相当。
  7. ] ポインタが指す値が0でないなら、対応する [ にジャンプする。C言語の「}」に相当。
		[Test]
		public void ループテスト_通常()
		{
			var compiler = new BrainFuckCompiler.BrainFuckCompiler("+++{-}");
			compiler.Run();
			compiler.CurrentValue.Is((byte)0);
		}
		
		[Test]
		public void ループテスト_ネスト()
		{
			var compiler = new BrainFuckCompiler.BrainFuckCompiler("+++{{-}}");
			compiler.Run();
			compiler.CurrentValue.Is((byte)0);
		}

とりあえず、この2メソッドを通してみましょう。対応する括弧を見つける手順は以下のようになりますね。ここは馬鹿正直に行きます。

	// 入力を括弧位置のインデックスとする
	int FindIndexOfEndBrucket(int index)
	{
		//まずひとつ進めて・・・
		index++;
		//括弧閉じのカウンタも1に初期化
		int brucketCounter = 1;
		//括弧閉じカウンタが0になるまで入力文字をパース
		while(brucketCounter > 0 && index < _input.Length)
		{
			//開き括弧なら括弧カウンタを加算
			if(_input[index] == '[')
			{
				brucketCounter++;
			}
			//閉じ括弧なら括弧カウンタを減算
			else if(_input[index] == ']')
			{
				brucketCounter--;
			}
			index++;
		}
		//必ず一つ行き過ぎているので、一つ戻しておく
		return index - 1;
	}

閉じ括弧から開き括弧を見つけるのも同様です

	//入力を括弧閉じのインデックスとする
	int FindIndexOfStartBrucket(int currentIndex)
	{
		//初期化
		currentIndex--;
		int brucketCounter = 1;
		//前に戻りながら括弧を見つける
		while(brucketCounter > 0 && currentIndex >= 0)
		{
			if(_input[currentIndex] == '[')
			{
				brucketCounter--;
			}
			else if(_input[currentIndex] == ']')
			{
				brucketCounter++;
			}
			currentIndex--;
		}
		//必ず行き過ぎてるので戻しておく
		return currentIndex + 1;
	}

とりあえずこれで通してみましょう・・・。よし、通りました通りました。
さて、ここでプライベートメソッドを追加したのですが、個人的はこのプライベートメソッドのテストは不要と思っています。帯びだし元のパブリックメソッドのテストで十分にパスが通っているはずですからね。どちらというと可読性の点で切り出していますし。もしどうしてもプライベートをテストしたくなったら、InternalVisibleTo属性をつけるか、MSTestに頼るか、ですね。お金をMSにお布施している人はあんまり悩まなくてもいいんですけど。



さて、入力がちゃんと括弧同士の対応がとれているとは限りません。そういった場合には例外を発生させるべきでしょう。
本当は例外クラスを定義すべきですが、ここはちょっと楽をしてApplicationExceptionを投げておきましょう。

というわけでテストを書きます。

		[Test]
		public void ループテスト_左括弧閉じられず()
		{
			var compiler = new BrainFuckCompiler.BrainFuckCompiler("+++[-");
			Assert.Throws<ApplicationException>(() => compiler.Run());
		}
		
		[Test]
		public void ループテスト_右括弧閉じられず()
		{
			var compiler = new BrainFuckCompiler.BrainFuckCompiler("+++-]");
			Assert.Throws<ApplicationException>(() => compiler.Run());
		}	

さてさて、Runしてみると、おっと、テストが終わりませんね。。。
というわけで、無限ループしてます。テストは”ループテスト_右括弧閉じられず”でおわっていますが。。。
あちゃちゃ、これ、閉じ括弧から先頭に戻ってまた閉じ括弧に・・・と永遠ループしちゃってます。コレはまずい。

また左括弧だけ有る方も、飛び先が領域外ではないので、なんか正常系のループに戻っちゃってます。結局、見つかったことだけを前提にして、”いき過ぎてる部分を一つ戻す”というコード書いたのがひじょうにダメダメでしたね。

んじゃ、修正しましょう。もう範囲外超えそうになったら例外を即出すようにしましょう。例えばこんな感じに。

	int FindIndexOfEndBrucket(int index)
	{
		//まずひとつ進めて・・・
		index++;
		//括弧閉じのカウンタも1に初期化
		int brucketCounter = 1;
		//括弧閉じカウンタが0になるまで入力文字をパース
		while(brucketCounter > 0)
		{
			if(index >= _input.Length)
			{
				throw new ApplicationException("括弧が閉じられていません");
			}
			
			//開き括弧なら括弧カウンタを加算
			if(_input[index] == '[')
			{
				brucketCounter++;
			}
			//閉じ括弧なら括弧カウンタを減算
			else if(_input[index] == ']')
			{
				brucketCounter--;
			}
			index++;
		}
		//必ず一つ行き過ぎているので、一つ戻しておく
		return index - 1;
	}

これでグリーン!・・・になりません。あれれ??
そしてよくよくテストケースを見てみると・・・・

		[Test]
		public void ループテスト_左括弧閉じられず()
		{
			var compiler = new BrainFuckCompiler.BrainFuckCompiler("+++[-"); // <= BrainFuckのループ条件満たしていない!!
			Assert.Throws<ApplicationException>(() => compiler.Run());
		}

というわけで、上のコメントに書いたように、ポインタ値が0のときのみ読み飛ばす、ということで閉じ括弧の探索処理に入らないのでした。
ここは仕様としてどうするのかのも良いどころです。使いたい時にないという状況まで待つのか、最初におかしかったらおかしいというのか。
今回はコンパイラとはいいつつも実装はインタプリタに近い、ということで実際に問題があるときにだけ例外を吐かせるようにしましょう。テストコードの変更です。

		[Test]
		public void ループテスト_左括弧閉じられず()
		{
			var compiler = new BrainFuckCompiler.BrainFuckCompiler("++--[-");
			Assert.Throws<ApplicationException>(() => compiler.Run());
		}

これでめでたく例外が発生し、オールグリーンです。


ふむ、はっきり言ってTDDするまでにある程度の仕様は頭で考えていましたが、こういった場合の動きは想定していませんでした。
曖昧なところがあると本当にちゃんと矛盾となり、レッドになってくれるんですね、TDDって。ほむほむ・・・