iwate/00_stackmachine.md

## 00_stackmachine.md

      
    Raw
  

              00_stackmachine.md
            
          
    計算機を作ってみる

この仕事をしていると当たり前のように使用している計算機=コンピュータ。この演習では簡単な計算機を作成に挑戦しよう。

初めての人は、コンピュータについてより深く考えられるようになるし、すでにやったことのある人も新たな気づきや挑戦ができる何回やっても楽しいお題だと私は考えます。

色々調べながらやるともっと楽しいでしょう。仲間や先輩に聞いたり議論するのも最高ですね。
さっそくはじめてみましょう。
色々な記法

私たち人間が式を書くときに利用するのは、多くの場合、中置記法と呼ばれる記法を用います。
中置記法とは、a + b のように演算子がパラメータの間に記述する記法で数式のスタンダードなスタイルです。
この中置記法だけが式を表す唯一の記法ではありません。有名なのがポーランド記法です。この記法は、 + a b のように、演算子が前に来ます。ポーランド記法はLISPのS式のスタイルとして愛用している人も多いでしょう。
ポーランド記法の逆で、a b + と記述する記法もあります。これを逆ポーランド記法と呼びます。


名称
例


ポーランド記法
+ a b


中置記法
a + b


逆ポーランド記法
a b +


演習1 逆ポーランド記法の式を計算する計算機を作ってみよう

演算子は、+-*/ が利用できるようにし、以下の expression を実行できるような計算機を作ってみましょう。
var expression = "123++8*3-9/"; // 中置記法で表現すると-> ((1+2+3) * 8 - 3) / 9

演習1 参考実装

参考実装 01.cs
スタックと逆ポーランド記法

スタックはLIFO(Last In First Out)なデータ構造です。 スタックに値を積む push 命令と スタックに積まれた値を下す pop 命令の2命令を基軸に様々な問題を解決できる優れたデータ構造です。
このスタックと逆ポーランド記法は相性がとても良いです。
先ほどの演習１参考実装を読むとスタックで逆ポーランド記法を見事に計算しています。
演習2 変数を使えるようにしよう

変数にスタックの値を格納する命令と変数に格納されている値をスタックに積む2命令を追加してスタックに積んだ2つの値を入れ替える式230S1S0L1Lを実行してみましょう。
expression = 230S1S0L1L
この式を実行すると、23でスタックに積まれた[2,3]が最終的に[3,2]に入れ替わります。


演算子
名称
説明


S
ストア命令
変数にスタックの値を格納する


L
ロード命令
変数に格納されて値をスタックに積む


ヒント

ストア命令は値と変数の位置の2引数をとり、ロード命令は変数の位置の1引数をとるようにすると複数の変数が使用できる。
変数の位置には、計算領域の後ろを使と後々都合がよい

演習2 参考実装

参考実装 02.cs
演習3 ループが使えるようにしよう

分岐命令を追加して、無限ループを実行してみましょう。
expression = 10B


演算子
名称
説明


B.
分岐命令
条件値が0以外なら遷移先の位置にPC(Program Counter)を移動させる


※ PCはexpressionのリードインデックス
分岐命令のステップ
I. PC(Program Counter) = 0 の初期状態


Expression
1
0
B


PC
^


Stack


II. PC=0が差す1を実行、Stackに1をpushし、PCを1進める


Expression
1
0
B


PC

^


Stack
1


III. PC=1が差す0を実行、Stackに0をpushし、PCを1進める


Expression
1
0
B


PC


^


Stack
1
0


IV. PC=2が差すBを実行、Stackを2回popし、戻り先のPCと分岐条件を取得する。


Expression
1
0
B


PC


^


Stack
1
0


分岐条件
戻り先のPC


V. 分岐条件が0でないため、PCを戻り先のPC=0に上書く


Expression
1
0
B


PC
^


Stack


以下II~Vを無限ループ
演習3 参考実装

参考実装 03.cs
演習4 次の計算を式にして実行してみよう

5 + 4 + 3 + 2 + 1 を作成した計算機で、変数とループを使用して計算してみよう。
演習4 参考実装

参考実装 04.cs
演習5 式が書きにくい？パーサー&コンバータを書こう

演習4は人間には非常に書きにくかったと思いますがどうでしょうか。特に分岐命令の遷移先を数えるところが現実的ではありませんね。これを解決するためにもう少し書きやすい専用の言語を作ってみましょう。
まずは複雑な構文は考えず、なるべく1対1で変更できるようなものを考えます。先人の例にならってアセンブリ言語を参考にして以下の構文を用意します。


項目
引数
説明
expression


push n
n := 0..9
スタックにnを積む
0,1,...,9


add

加算
+


sub

減算
-


mul

乗算
*


div

除算
/


<ラベル名>:

Indexで<ラベル名>ラベリング


@<ラベル名>

<ラベル名>でIndexを解決する


branch

分岐命令
B


store

ストア命令
S


load

ロード命令
L


; <コメント>

コメント


このルールに従って、演習4を記述してみると以下のコードになります。
    ; 変数0を0で初期化
    push 0
    push 0
    store

    ; 変数1に5で初期化
    push 5
    push 1
    store

LOOP:
    ; 変数0と変数1をたして変数0に書き戻す
    push 1
    load
    push 0
    load
    add
    push 0
    store

    ; 変数1を1減算して変数1に書き戻す
    push 1
    load
    push 1
    sub
    push 1
    store

    ; 変数1が0じゃなかったらラベルLOOPへジャンプ
    push 1
    load
    push @LOOP
    branch

    ; 結果をロード
    push 0
    load
ヒント

パースしやすいようにルールは自由に整えてOK、まずは変換できることを目標にしよう

例: 空白行禁止、ラベルだけの行は禁止、コメントだけの行も禁止、必ず ラベル\t命令;コメント のフォーマットにするなど


拡張しやすいパーサーを目指すならパーサーコンビネータで調べてみよう。

演習5 参考実装

参考実装 05.cs
演習6 2桁以上の数字に対応させよう

2桁以上の数字を計算できるような変更を考えてみましょう。今まではexpression=123++8*3-9/のように1文字ずつを条件にしていましたがこれでは2桁以上の数字は入力することができません。 従って、スペースで区切ることにしましょう。このルールで先の式を書くとexpression=1 2 3 + + 8 * 3 - pになります。 これならば、expression=100 10 1 + +のように2桁以上の値を入力することができます。
さて、今まで作成した計算機とパーサー&コンバータをこのスペース区切りに対応させてみましょう。
演習6 参考実装

計算機
参考実装 06.cs
パーサー&コンバータ
参考実装 07.cs
関数を考えよう

分岐、変数、それを用いたループができるようになりました。次は関数（函数）について考えてみましょう。※今回のようなアセンブリライクな言語ではサブルーチンと呼ぶほうが正しい気もしますが、わかりやすさ重視であえて関数と呼ぶことにします。
現在の状態でも分岐命令を使用して任意の場所へ飛べるので、処理を分けて書くことは可能です。
    ; 変数0を初期化
    push 0
    push 0
    store

    ; MAINに飛ぶ
    push 0
    push @MAIN
    branch

SUB:
    ; 何かの処理

    ; 戻り先を変数でロードし、分岐命令で戻る
    push 0
    ; 戻り先をロード
    push 0
    load
    branch
    
MAIN:
    ; 何かの処理

    ; 戻り先を変数0に保存
    push @SUB_RET1
    store

    ; SUBへ飛ぶ
    push 0
    push @SUB
    branch

SUB_RET1:
    ; 何かの処理

    ; 戻り先を変数0に保存
    push @SUB_RET2
    store

    ; SUBへ飛ぶ
    push 0
    push @SUB
    branch

SUB_RET2:
    ; 何かの処理
さて、このように今でも一応、処理を分けて書くことができます。しかし、書きづらさを感じます。
私が感じる書きづらさ、とりあえずのところ以下の2点です。

変数がグローバル
戻り先のラベル

SUBラベルからの処理のなかで変数を使用したい場合、今まで通り、ストア命令とロード命令を使用します。
ただし、その使用領域はMAINと同様にスタックの先頭です。これはつまり、変数領域をMAINとSUBで共有しています。
そのため、SUBで使用する変数の数をあらかじめ知っておき、変数領域を確保する必要があります。
これは非常に使いにくい仕様です。
また、戻るときの戻り先を知るためにわざわざラベルを作るのも、それを変数に入れておく処理を手で書くのも辛さの一つです。
これらの書きづらさを解消するために、スタックをフレーム化してみましょう。
フレーム化するために、以下の3命令を追加します。


演算子
名称
説明


A
領域確保命令
変数領域を確保する


C
コール命令
PCとFPを保存して、フレームを区切り指定のラベルへ飛ぶ


R
リターン命令
コール命令で保存したPCやFPを戻す


※ FP (Frame Pointer) フレームの境界線を記憶するポインタ
この命令を使用してコードを書くと次のようになります。
    ; MAIN用の変数領域を1確保
    push 1
    alloc

    ; MAIIN用の変数0を5で初期化
    push 5
    push 0 
    store

    ; MAINに遷移
    push 0
    push @MAIN
    branch

SUB:
    ; SUB用の変数領域を1確保
    push 1
    alloc

    ; SUB用の変数0を3で初期化
    push 3
    push 0
    store

L1: push 5
    ; SUB用の変数0をロード
    push 0
    load

    ; 5 - 3 
L2: sub
    
    ; 戻る
    ret
MAIN:
    push @SUB
    call
    ; SUBの戻り値(2:=5-3)はスタックに積まれている
L3: push 1
このコードが実行されたとき、L2ラベルのsubが実行される前のスタックを見てみましょう。


Index
値
説明
SP
FP


99
5
MAIN用変数0


98
5
戻り先のPC = L3


97
0
もとのFP (Frame Pointer)


96
3
SUB用の変数0

<-


...


2


<-


1
3
SUB用の変数0からロードされた値


0
5
L1で積まれた固定値


SUB用の変数0が、スタックの末端ではなく中間(96)に存在します。これはフレーム化によりストア命令の挿入場所をフレームの開始時点に変更することで実現できます。そして、フレームの開始時点を保存するためにFP(Frame Pointer)を導入します。上表の状態では、FP=96になっています。
呼び出しもとのMAINに戻るリターン命令では、FPとPCを復元することで元の処理に戻ることができます。
戻った際、戻り値は組み込みの加算命令、減算命令などと同様にスタックに残ります。
どうやら、フレーム化で関数を手に入れることができそうです。
さらに、任意の地点で計算を停止できる停止命令も追加しましょう。この命令を使うことで、メインの処理をコードの一番後ろに記載する必要が無くなります。


演算子
名称
説明


H
停止命令
直ちに計算を停止する


演習7 フレームを導入してみよう

以下の5命令を計算機、パーサー&コンバータに追加して6のフィボナッチ数を計算してみよう。


項目
説明
expression


alloc
領域確保命令
A


call
コール命令
C


ret
リターン命令
R


halt
停止命令
H


MAIN:
	; 引数を6にしてFIBをコール
	push 6
	push @FIB
	call 
	halt
FIB:
    ; 変数領域を1確保する
	push 1
	alloc
    ; 変数0に引数を格納する
	push 0
	store
	
    ; 引数が0でなければGT0へとぶ
	push 0
	load
	push @GT0
	branch
	
	; 引数が0の時は0で戻る
	push 0 
	ret
	
GT0:
    ; 引数から1引いた値が0でなければGT1へとぶ
	push 0
	load
	push 1
	sub
	push @GT1
	branch
	; 引数から1引いた値が0の時は1で戻る
	; = 引数が1の時は1
	push 1
	ret

GT1:
	; 引数-2を新たな引数にしてFIBをコール
	push 0
	load
	push 2
	sub
	push @FIB
	call 
	; 引数-1を新たな引数にしてFIBをコール
	push 0
	load
	push 1
	sub
	push @FIB
	call 
	; FIB(引数-2) + FIB(引数-1)
	add
	ret
演習7 参考実装

計算機
参考実装 08.cs
パーサー&コンバータ
参考実装 09.cs
演習8 余力があれば糖衣構文を追加してみよう

余力があれば、コードが書きやすいようにパーサー&コンバータに糖衣構文(シンタックスシュガー)を実装してみよう。
例:
    push 0
    store

    ; ↑のコードを↓のように書けるほうが楽
    store 0

    ; 他にも..
    laod 0
    soreArg 0
    loadArg 0
    branch @LABEL
    call @FUNC

  
## 01.cs
var expression = "123++8*3-9/";
var memory = new int[100];
var pc = 0;
var sp = 0;

void push(int v) {
    memory[sp++] = v;
}
int pop() {
    return memory[--sp];
}
void add() {
    var r = pop();
    var l = pop();
    push(l + r);
}
void sub() {
    var r = pop();
    var l = pop();
    push(l - r);
}
void mul() {
    var r = pop();
    var l = pop();
    push(l * r);
}
void div() {
    var r = pop();
    var l = pop();
    push(l / r);
}


while(pc < expression.Length)
{
    var c = expression[pc++].ToString();
    switch(c)
    {
        case "+":
            add();
            break;
        case "-":
            sub();
            break;
        case "*":
            mul();
            break;
        case "/":
            div();
            break;
        default:
            if (int.TryParse(c, out var value)) {
                push(value);
            }
            break;
    }
}

var result = pop();

## 02.cs
var expression = "230S1S0L1L";
var memory = new int[100];
var pc = 0;
var sp = 0;
var lastIndex = memory.Length - 1;

void push(int v) {
    memory[sp++] = v;
}
int pop() {
    return memory[--sp];
}
void add() {
    var r = pop();
    var l = pop();
    push(l + r);
}
void sub() {
    var r = pop();
    var l = pop();
    push(l - r);
}
void mul() {
    var r = pop();
    var l = pop();
    push(l * r);
}
void div() {
    var r = pop();
    var l = pop();
    push(l / r);
}
void store() {
	var n = pop();
	var v = pop();
	memory[lastIndex - n] = v;
}
void load() {
	var n = pop();
	push(memory[lastIndex - n]);
}

while(pc < expression.Length)
{
    var c = expression[pc++].ToString();
    switch(c)
    {
        case "+":
            add();
            break;
        case "-":
            sub();
            break;
        case "*":
            mul();
            break;
        case "/":
            div();
            break;
		case "S":
			store();
			break;
		case "L":
			load();
			break;
        default:
            if (int.TryParse(c, out var value)) {
                push(value);
            }
            break;
    }
}

var result = memory.Take(2);

## 03.cs
var expression = "10B";
var memory = new int[100];
var pc = 0;
var sp = 0;
var lastIndex = memory.Length - 1;

void push(int v) {
    memory[sp++] = v;
}
int pop() {
    return memory[--sp];
}
void add() {
    var r = pop();
    var l = pop();
    push(l + r);
}
void sub() {
    var r = pop();
    var l = pop();
    push(l - r);
}
void mul() {
    var r = pop();
    var l = pop();
    push(l * r);
}
void div() {
    var r = pop();
    var l = pop();
    push(l / r);
}
void store() {
	var n = pop();
	var v = pop();
	memory[lastIndex - n] = v;
}
void load() {
	var n = pop();
	push(memory[lastIndex - n]);
}
void branch() {
	var dst = pop();
	var cond = pop();
	if (cond != 0)
		pc = dst;
}

while(pc < expression.Length)
{
    var c = expression[pc++].ToString();
    switch(c)
    {
        case "+":
            add();
            break;
        case "-":
            sub();
            break;
        case "*":
            mul();
            break;
        case "/":
            div();
            break;
		case "S":
			store();
			break;
		case "L":
			load();
			break;
		case "B":
			branch();
			break;
        default:
            if (int.TryParse(c, out var value)) {
                push(value);
            }
            break;
    }
}

var result = pop();

## 04.cs
var expression = "00S51S1L0L+0S1L1-1S1L6B0L";
var memory = new int[100];
var pc = 0;
var sp = 0;
var lastIndex = memory.Length - 1;

void push(int v) {
    memory[sp++] = v;
}
int pop() {
    return memory[--sp];
}
void add() {
    var r = pop();
    var l = pop();
    push(l + r);
}
void sub() {
    var r = pop();
    var l = pop();
    push(l - r);
}
void mul() {
    var r = pop();
    var l = pop();
    push(l * r);
}
void div() {
    var r = pop();
    var l = pop();
    push(l / r);
}
void store() {
	var n = pop();
	var v = pop();
	memory[lastIndex - n] = v;
}
void load() {
	var n = pop();
	push(memory[lastIndex - n]);
}
void branch() {
	var dst = pop();
	var cond = pop();
	if (cond != 0)
		pc = dst;
}

while(pc < expression.Length)
{
    var c = expression[pc++].ToString();
    switch(c)
    {
        case "+":
            add();
            break;
        case "-":
            sub();
            break;
        case "*":
            mul();
            break;
        case "/":
            div();
            break;
		case "S":
			store();
			break;
		case "L":
			load();
			break;
		case "B":
			branch();
			break;
        default:
            if (int.TryParse(c, out var value)) {
                push(value);
            }
            break;
    }
}

var result = pop();

## 05.cs
void Main()
{
	var program = @"
	; 変数0を0で初期化
    push 0
    push 0
    store

    ; 変数1に5で初期化
    push 5
    push 1
    store

LOOP:
    ; 変数0と変数1をたして変数0に書き戻す
    push 1
    load
    push 0
    load
    add
    push 0
    store

    ; 変数1を1減算して変数1に書き戻す
    push 1
    load
    push 1
    sub
    push 1
    store

    ; 変数1が0じゃなかったらラベルLOOPへジャンプ
    push 1
    load
    push @LOOP
    branch

    ; 結果をロード
    push 0
    load";

	var expression = Compile(program);
	Console.WriteLine(expression);
}

string Compile(string program)
{
	var Spaces    = Select(Pattern(@"^[\t ]+"), str => (IQuery)new QToken(str));
	var Comment   = Select(Pattern(@"^;.*"), str => (IQuery)new QComment(str));
	var Number    = Select(Pattern(@"^\d+"), str => (IQuery)new QNumber(int.Parse(str)));
	var Label     = Select(And(Pattern(@"^[a-zA-Z][a-zA-Z0-9]*"), Token(":")), strs => (IQuery)new QLabel(strs.ElementAt(0)));
	var Alias     = Select(And(Token("@"), Pattern(@"^[a-zA-Z][a-zA-Z0-9]*")), strs => (IQuery)new QAlias(strs.ElementAt(1)));
	var Operand   = Or(Number, Alias);
	var Keyword   = Select(Pattern(@"^[a-zA-Z][a-zA-Z0-9]*"), str => (IQuery)new QToken(str));
	var Operation = Select(And(Keyword, Optional(Spaces), Optional(Operand)), q => (IQuery)new QOperation(((QToken)q.ElementAt(0)).Value, q.ElementAt(2)));
	var LF        = Select(Or(Token("\n"), Token("\r\n")), str => (IQuery)new QToken(str));
	var Line      = And(Optional(Label), Optional(Spaces), Optional(Operation), Optional(Spaces), Optional(Comment), Optional(LF));
	var Code      = Select(Many(Line), qs => qs.SelectMany(q => q).Where(q => q != null && !(q is QToken)));

	var (success, steps, _) = Code.Invoke(program, 0);

	if (!success)
		throw new InvalidOperationException("Cannot parse.");

	return Generate(steps);
}

string Generate(IEnumerable<IQuery> queries)
{
	var labels = new Dictionary<string, int>();
	var mapping = new Dictionary<string, Func<int?, string>>
	{
		{ "add"   , _ => "+" },
		{ "sub"   , _ => "-" },
		{ "mul"   , _ => "*" },
		{ "div"   , _ => "/" },
		{ "store" , _ => "S" },
		{ "load"  , _ => "L" },
		{ "branch", _ => "B" },
		{ "push"  , n => n.ToString() },
	};
	var steps = new List<Func<string>>();

	foreach (var query in queries)
	{
		if (query is QLabel label)
		{
			labels.Add(label.Text, steps.Count);
		}
		else if (query is QOperation operation)
		{
			steps.Add(() => {
				var operand = (operation.Operand is QNumber num) ? num.Value
			                : (operation.Operand is QAlias alias) ? labels[alias.Label]
			                : (int?)null;

				return mapping[operation.Mnemonic.ToLower()].Invoke(operand);
			});
		}
	}

	return string.Join("", steps.Select(step => step()));
}

interface IQuery {}

class QNumber:IQuery
{
	public int Value { get; set; }
	public QNumber(int value) { Value = value; }
}

class QLabel:IQuery
{
	public string Text { get; set; }
	public QLabel(string text) { Text = text; }
}

class QAlias:IQuery
{
	public string Label { get; set; }
	public QAlias(string label) { Label = label; }
}

class QOperation:IQuery
{
	public string Mnemonic { get; set; }
	public IQuery Operand { get; set; }
	public QOperation(string mnemonic, IQuery operand)
	{
		Mnemonic = mnemonic;
		Operand = operand;
	}
}

class QComment:IQuery
{
	public string Text { get; set; }
	public QComment(string text) { Text = text; }
}

class QToken:IQuery {
	public string Value { get; set; }
	public QToken(string value) { Value = value; }
}

Func<string, int,  (bool, E, int)> Select<T, E>(Func<string, int,  (bool, T, int)>parser, Func<T,E> projection) {
	return (string str, int position) => {
		var (success, value, next) = parser.Invoke(str, position);

		if (!success)
			return (success, default(E), next);

		var v = projection.Invoke(value);

		return (success, v, next);
	};
}

Func<string, int, (bool, string, int)> Token(string token)
	=> (str, position) => str.Length >= position + token.Length && str.Substring(position, token.Length) == token
						? (true, token, position + token.Length)
						: (false, null, position);

Func<string, int, (bool, string, int)> Pattern(string regex) {
	return (str, position) => {
		var m = Regex.Match(str.Substring(position), regex);

		if (m.Success)
			return (true, m.Value, position + m.Value.Length);
		return (false, null, position);
	};
}

Func<string, int,  (bool, T, int)> Optional<T>(Func<string, int, (bool, T, int)> parser) {
	return (str, position) => {
		var (success, value, next) = parser.Invoke(str, position);

		return (true, value, next);
	};
}

Func<string, int, (bool, T, int)> Or<T>(params Func<string, int, (bool, T, int)>[] parsers) {
	return (str, position) => {
		foreach (var parser in parsers) {
			var (success, value, next) = parser.Invoke(str, position);

			if (success)
				return (true, value, next);
		}

		return (false, default(T), position);
	};
}

Func<string, int, (bool, IEnumerable<T>, int)> Many<T>(Func<string, int, (bool, T, int)> parser) {
	return (str, position) => {
		var result = new List<T>();

		while(position < str.Length) {

			var (success, value, next) = parser.Invoke(str, position);

			if (!success)
				return (true, result, next);

			result.Add(value);
			position = next;
		}
		return (true, result, position);
	};
}

Func<string, int,  (bool, IEnumerable<T>, int)> And<T>(params Func<string, int, (bool, T, int)>[] parsers) {
	return (str, position) => {
		var result = new List<T>();
		var pos = position;
		foreach (var parser in parsers) {

			var (success, value, next) = parser.Invoke(str, pos);

			if (!success)
				return (false, null, position);

			result.Add(value);
			pos = next;
		}

		return (true, result, pos);
	};
}

## 06.cs
var expression = "100 10 1 + +".Split(' '); // スペース区切りで分割
var memory = new int[100];
var pc = 0;
var sp = 0;
var lastIndex = memory.Length - 1;

void push(int v) {
    memory[sp++] = v;
}
int pop() {
    return memory[--sp];
}
void add() {
    var r = pop();
    var l = pop();
    push(l + r);
}
void sub() {
    var r = pop();
    var l = pop();
    push(l - r);
}
void mul() {
    var r = pop();
    var l = pop();
    push(l * r);
}
void div() {
    var r = pop();
    var l = pop();
    push(l / r);
}
void store() {
	var n = pop();
	var v = pop();
	memory[lastIndex - n] = v;
}
void load() {
	var n = pop();
	push(memory[lastIndex - n]);
}
void branch() {
	var dst = pop();
	var cond = pop();
	if (cond != 0)
		pc = dst;
}

while(pc < expression.Length)
{
    var c = expression[pc++]; // すでにstringなのでToString不要
    switch(c)
    {
        case "+":
            add();
            break;
        case "-":
            sub();
            break;
        case "*":
            mul();
            break;
        case "/":
            div();
            break;
		case "S":
			store();
			break;
		case "L":
			load();
			break;
		case "B":
			branch();
			break;
        default:
            if (int.TryParse(c, out var value)) {
                push(value);
            }
            break;
    }
}

var result = pop();

## 07.cs
string Generate(IEnumerable<IQuery> queries)
{
	var labels = new Dictionary<string, int>();
	var mapping = new Dictionary<string, Func<int?, string>>
	{
		{ "add"   , _ => "+" },
		{ "sub"   , _ => "-" },
		{ "mul"   , _ => "*" },
		{ "div"   , _ => "/" },
		{ "store" , _ => "S" },
		{ "load"  , _ => "L" },
		{ "branch", _ => "B" },
		{ "push"  , n => n.ToString() },
	};
	var steps = new List<Func<string>>();

	foreach (var query in queries)
	{
		if (query is QLabel label)
		{
			labels.Add(label.Text, steps.Count);
		}
		else if (query is QOperation operation)
		{
			steps.Add(() => {
				var operand = (operation.Operand is QNumber num) ? num.Value
			                : (operation.Operand is QAlias alias) ? labels[alias.Label]
			                : (int?)null;

				return mapping[operation.Mnemonic.ToLower()].Invoke(operand);
			});
		}
	}

	return string.Join(" ", steps.Select(step => step())); // スペース区切りに変更
}

## 08.cs
var expression = "6 4 C H 1 A 0 S 0 L 14 B 0 R 0 L 1 - 22 B 1 R 0 L 2 - 4 C 0 L 1 - 4 C + R".Split(' ');
var memory = new int[100];
var pc = 0;
var sp = 0;
var lastIndex = memory.Length - 1;
var rsp = lastIndex;
var fp = lastIndex;

void push(int v) {
    memory[sp++] = v;
}
int pop() {
    return memory[--sp];
}
void add() {
    var r = pop();
    var l = pop();
    push(l + r);
}
void sub() {
    var r = pop();
    var l = pop();
    push(l - r);
}
void mul() {
    var r = pop();
    var l = pop();
    push(l * r);
}
void div() {
    var r = pop();
    var l = pop();
    push(l / r);
}
void store() {
	var n = pop();
	var v = pop();
	memory[fp - n] = v;
}
void load() {
	var n = pop();
	push(memory[fp - n]);
}
void branch() {
	var dst = pop();
	var cond = pop();
	if (cond != 0)
		pc = dst;
}
void rpush(int v) {
	memory[rsp--] = v;
}
int rpop() {
	return memory[++rsp];
}
void alloc() {
	rsp -= pop();
}
void call() {
	var next = pop();
	rpush(pc);
	pc = next;
	rpush(fp);
	fp = rsp;
}
void ret() {
	rsp = fp;
	fp = rpop();
	pc = rpop();
}

var executing = true;
while(executing && pc < expression.Length)
{
    var c = expression[pc++];
    switch(c)
    {
        case "+":
            add();
            break;
        case "-":
            sub();
            break;
        case "*":
            mul();
            break;
        case "/":
            div();
            break;
		case "S":
			store();
			break;
		case "L":
			load();
			break;
		case "B":
			branch();
			break;
		case "A":
			alloc();
			break;
		case "C":
			call();
			break;
		case "R":
			ret();
			break;
		case "H":
			executing = false;
			break;
        default:
            if (int.TryParse(c, out var value)) {
                push(value);
            }
            break;
    }
}

var result = pop();

## 09.cs
void Main()
{
	var program = @"
MAIN:
	; 引数を6にしてFIBをコール
	push 6
	push @FIB
	call
	halt
FIB:
	push 1
	alloc
	push 0
	store

	push 0
	load
	push @GT0
	branch

	; 引数が0の時は0
	push 0
	ret

GT0:
	push 0
	load
	push 1
	sub
	push @GT1
	branch
	; 引数から1引いた値が0の時は1
	; = 引数が1の時は1
	push 1
	ret

GT1:
	; 引数-2を新たな引数にしてFIBをコール
	push 0
	load
	push 2
	sub
	push @FIB
	call
	; 引数-1を新たな引数にしてFIBをコール
	push 0
	load
	push 1
	sub
	push @FIB
	call
	; FIB(引数-2) + FIB(引数-1)
	add
	ret
	";

	var expression = Compile(program);
	Console.WriteLine(expression);
}

string Compile(string program)
{
	var Spaces    = Select(Pattern(@"^[\t ]+"), str => (IQuery)new QToken(str));
	var Comment   = Select(Pattern(@"^;.*"), str => (IQuery)new QComment(str));
	var Number    = Select(Pattern(@"^\d+"), str => (IQuery)new QNumber(int.Parse(str)));
	var Label     = Select(And(Pattern(@"^[a-zA-Z][a-zA-Z0-9]*"), Token(":")), strs => (IQuery)new QLabel(strs.ElementAt(0)));
	var Alias     = Select(And(Token("@"), Pattern(@"^[a-zA-Z][a-zA-Z0-9]*")), strs => (IQuery)new QAlias(strs.ElementAt(1)));
	var Operand   = Or(Number, Alias);
	var Keyword   = Select(Pattern(@"^[a-zA-Z][a-zA-Z0-9]*"), str => (IQuery)new QToken(str));
	var Operation = Select(And(Keyword, Optional(Spaces), Optional(Operand)), q => (IQuery)new QOperation(((QToken)q.ElementAt(0)).Value, q.ElementAt(2)));
	var LF        = Select(Or(Token("\n"), Token("\r\n")), str => (IQuery)new QToken(str));
	var Line      = And(Optional(Label), Optional(Spaces), Optional(Operation), Optional(Spaces), Optional(Comment), Optional(LF));
	var Code      = Select(Many(Line), qs => qs.SelectMany(q => q).Where(q => q != null && !(q is QToken)));

	var (success, steps, _) = Code.Invoke(program, 0);

	if (!success)
		throw new InvalidOperationException("Cannot parse.");

	return Generate(steps);
}

string Generate(IEnumerable<IQuery> queries)
{
	var labels = new Dictionary<string, int>();
	var mapping = new Dictionary<string, Func<int?, string>>
	{
		{ "add"   , _ => "+" },
		{ "sub"   , _ => "-" },
		{ "mul"   , _ => "*" },
		{ "div"   , _ => "/" },
		{ "store" , _ => "S" },
		{ "load"  , _ => "L" },
		{ "branch", _ => "B" },
		{ "alloc" , _ => "A" },
		{ "call"  , _ => "C" },
		{ "ret"   , _ => "R" },
		{ "halt"  , _ => "H" },
		{ "push"  , n => n.ToString() },
	};
	var steps = new List<Func<string>>();

	foreach (var query in queries)
	{
		if (query is QLabel label)
		{
			labels.Add(label.Text, steps.Count);
		}
		else if (query is QOperation operation)
		{
			steps.Add(() => {
				var operand = (operation.Operand is QNumber num) ? num.Value
			                : (operation.Operand is QAlias alias) ? labels[alias.Label]
			                : (int?)null;

				return mapping[operation.Mnemonic.ToLower()].Invoke(operand);
			});
		}
	}

	return string.Join(" ", steps.Select(step => step()));
}

interface IQuery {}

class QNumber:IQuery
{
	public int Value { get; set; }
	public QNumber(int value) { Value = value; }
}

class QLabel:IQuery
{
	public string Text { get; set; }
	public QLabel(string text) { Text = text; }
}

class QAlias:IQuery
{
	public string Label { get; set; }
	public QAlias(string label) { Label = label; }
}

class QOperation:IQuery
{
	public string Mnemonic { get; set; }
	public IQuery Operand { get; set; }
	public QOperation(string mnemonic, IQuery operand)
	{
		Mnemonic = mnemonic;
		Operand = operand;
	}
}

class QComment:IQuery
{
	public string Text { get; set; }
	public QComment(string text) { Text = text; }
}

class QToken:IQuery {
	public string Value { get; set; }
	public QToken(string value) { Value = value; }
}

Func<string, int,  (bool, E, int)> Select<T, E>(Func<string, int,  (bool, T, int)>parser, Func<T,E> projection) {
	return (string str, int position) => {
		var (success, value, next) = parser.Invoke(str, position);

		if (!success)
			return (success, default(E), next);

		var v = projection.Invoke(value);

		return (success, v, next);
	};
}

Func<string, int, (bool, string, int)> Token(string token)
	=> (str, position) => str.Length >= position + token.Length && str.Substring(position, token.Length) == token
						? (true, token, position + token.Length)
						: (false, null, position);

Func<string, int, (bool, string, int)> Pattern(string regex) {
	return (str, position) => {
		var m = Regex.Match(str.Substring(position), regex);

		if (m.Success)
			return (true, m.Value, position + m.Value.Length);
		return (false, null, position);
	};
}

Func<string, int,  (bool, T, int)> Optional<T>(Func<string, int, (bool, T, int)> parser) {
	return (str, position) => {
		var (success, value, next) = parser.Invoke(str, position);

		return (true, value, next);
	};
}

Func<string, int, (bool, T, int)> Or<T>(params Func<string, int, (bool, T, int)>[] parsers) {
	return (str, position) => {
		foreach (var parser in parsers) {
			var (success, value, next) = parser.Invoke(str, position);

			if (success)
				return (true, value, next);
		}

		return (false, default(T), position);
	};
}

Func<string, int, (bool, IEnumerable<T>, int)> Many<T>(Func<string, int, (bool, T, int)> parser) {
	return (str, position) => {
		var result = new List<T>();

		while(position < str.Length) {

			var (success, value, next) = parser.Invoke(str, position);

			if (!success)
				return (true, result, next);

			result.Add(value);
			position = next;
		}
		return (true, result, position);
	};
}

Func<string, int,  (bool, IEnumerable<T>, int)> And<T>(params Func<string, int, (bool, T, int)>[] parsers) {
	return (str, position) => {
		var result = new List<T>();
		var pos = position;
		foreach (var parser in parsers) {

			var (success, value, next) = parser.Invoke(str, pos);

			if (!success)
				return (false, null, position);

			result.Add(value);
			pos = next;
		}

		return (true, result, pos);
	};
}
名称	例
ポーランド記法	+ a b
中置記法	a + b
逆ポーランド記法	a b +
演算子	名称	説明
S	ストア命令	変数にスタックの値を格納する
L	ロード命令	変数に格納されて値をスタックに積む
項目	引数	説明	expression
push n	n := 0..9	スタックに`n`を積む	`0`,`1`,...,`9`
add		加算	`+`
sub		減算	`-`
mul		乗算	`*`
div		除算	`/`
<ラベル名>:		Indexで`<ラベル名>`ラベリング
@<ラベル名>		`<ラベル名>`でIndexを解決する
branch		分岐命令	`B`
store		ストア命令	`S`
load		ロード命令	`L`
; <コメント>		コメント
演算子	名称	説明
A	領域確保命令	変数領域を確保する
C	コール命令	PCとFPを保存して、フレームを区切り指定のラベルへ飛ぶ
R	リターン命令	コール命令で保存したPCやFPを戻す
Index	値	説明	SP	FP
99	5	MAIN用変数0
98	5	戻り先のPC = `L3`
97	0	もとのFP (Frame Pointer)
96	3	SUB用の変数0		<-
...
2			<-
1	3	SUB用の変数0からロードされた値
0	5	`L1`で積まれた固定値
項目	説明	expression
alloc	領域確保命令	`A`
call	コール命令	`C`
ret	リターン命令	`R`
halt	停止命令	`H`
	var expression = "123++8*3-9/";
	var memory = new int[100];
	var pc = 0;
	var sp = 0;

	void push(int v) {
	memory[sp++] = v;
	}
	int pop() {
	return memory[--sp];
	}
	void add() {
	var r = pop();
	var l = pop();
	push(l + r);
	}
	void sub() {
	var r = pop();
	var l = pop();
	push(l - r);
	}
	void mul() {
	var r = pop();
	var l = pop();
	push(l * r);
	}
	void div() {
	var r = pop();
	var l = pop();
	push(l / r);
	}


	while(pc < expression.Length)
	{
	var c = expression[pc++].ToString();
	switch(c)
	{
	case "+":
	add();
	break;
	case "-":
	sub();
	break;
	case "*":
	mul();
	break;
	case "/":
	div();
	break;
	default:
	if (int.TryParse(c, out var value)) {
	push(value);
	}
	break;
	}
	}

	var result = pop();
	var expression = "230S1S0L1L";
	var memory = new int[100];
	var pc = 0;
	var sp = 0;
	var lastIndex = memory.Length - 1;

	void push(int v) {
	memory[sp++] = v;
	}
	int pop() {
	return memory[--sp];
	}
	void add() {
	var r = pop();
	var l = pop();
	push(l + r);
	}
	void sub() {
	var r = pop();
	var l = pop();
	push(l - r);
	}
	void mul() {
	var r = pop();
	var l = pop();
	push(l * r);
	}
	void div() {
	var r = pop();
	var l = pop();
	push(l / r);
	}
	void store() {
	var n = pop();
	var v = pop();
	memory[lastIndex - n] = v;
	}
	void load() {
	var n = pop();
	push(memory[lastIndex - n]);
	}

	while(pc < expression.Length)
	{
	var c = expression[pc++].ToString();
	switch(c)
	{
	case "+":
	add();
	break;
	case "-":
	sub();
	break;
	case "*":
	mul();
	break;
	case "/":
	div();
	break;
	case "S":
	store();
	break;
	case "L":
	load();
	break;
	default:
	if (int.TryParse(c, out var value)) {
	push(value);
	}
	break;
	}
	}

	var result = memory.Take(2);
	var expression = "10B";
	var memory = new int[100];
	var pc = 0;
	var sp = 0;
	var lastIndex = memory.Length - 1;

	void push(int v) {
	memory[sp++] = v;
	}
	int pop() {
	return memory[--sp];
	}
	void add() {
	var r = pop();
	var l = pop();
	push(l + r);
	}
	void sub() {
	var r = pop();
	var l = pop();
	push(l - r);
	}
	void mul() {
	var r = pop();
	var l = pop();
	push(l * r);
	}
	void div() {
	var r = pop();
	var l = pop();
	push(l / r);
	}
	void store() {
	var n = pop();
	var v = pop();
	memory[lastIndex - n] = v;
	}
	void load() {
	var n = pop();
	push(memory[lastIndex - n]);
	}
	void branch() {
	var dst = pop();
	var cond = pop();
	if (cond != 0)
	pc = dst;
	}

	while(pc < expression.Length)
	{
	var c = expression[pc++].ToString();
	switch(c)
	{
	case "+":
	add();
	break;
	case "-":
	sub();
	break;
	case "*":
	mul();
	break;
	case "/":
	div();
	break;
	case "S":
	store();
	break;
	case "L":
	load();
	break;
	case "B":
	branch();
	break;
	default:
	if (int.TryParse(c, out var value)) {
	push(value);
	}
	break;
	}
	}

	var result = pop();
	var expression = "00S51S1L0L+0S1L1-1S1L6B0L";
	var memory = new int[100];
	var pc = 0;
	var sp = 0;
	var lastIndex = memory.Length - 1;

	void push(int v) {
	memory[sp++] = v;
	}
	int pop() {
	return memory[--sp];
	}
	void add() {
	var r = pop();
	var l = pop();
	push(l + r);
	}
	void sub() {
	var r = pop();
	var l = pop();
	push(l - r);
	}
	void mul() {
	var r = pop();
	var l = pop();
	push(l * r);
	}
	void div() {
	var r = pop();
	var l = pop();
	push(l / r);
	}
	void store() {
	var n = pop();
	var v = pop();
	memory[lastIndex - n] = v;
	}
	void load() {
	var n = pop();
	push(memory[lastIndex - n]);
	}
	void branch() {
	var dst = pop();
	var cond = pop();
	if (cond != 0)
	pc = dst;
	}

	while(pc < expression.Length)
	{
	var c = expression[pc++].ToString();
	switch(c)
	{
	case "+":
	add();
	break;
	case "-":
	sub();
	break;
	case "*":
	mul();
	break;
	case "/":
	div();
	break;
	case "S":
	store();
	break;
	case "L":
	load();
	break;
	case "B":
	branch();
	break;
	default:
	if (int.TryParse(c, out var value)) {
	push(value);
	}
	break;
	}
	}

	var result = pop();