Init stack、Push D、Pop D、Pop A、Push Value【NandGame編】

2023年11月21日

はじめに

本記事は、Stack machineグループの前半のレベルについて焦点を当てます。

スタックの必要性

2個のレジスターだけでプログラムするのは難しく、いずれ限界がきます。例えば、2つのレジスターで2＋2を計算できますが、2－(3－2)を計算するには中間結果を保存する必要があり、すでに難しくなっています。

そこで、シンプルですが非常に強力なツールであるスタックを導入します。

スタックとは、先入れ先出し方式（FIFO）で中間値を格納したり取り出したりできる、特殊なメモリー領域です。

スタックポインタ（SP：Stack Pointer）はスタックの先頭アドレスを指すものです^[1]ここでいうポインタとは、メモリーアドレス上のデータを指すもの、すなわちデータのアドレスに相当します。。

よくある設計としてはSP専用のレジスターが用意されていますが、NandGameのコンピューターでは2つのレジスター（AとD）しかありません。そこで、Ram上のアドレス0x0000をSP専用の場所として扱います。

それでは、NandGameのコンピューターにスタックを導入してみましょう。

Init stackレベル

Init stackレベルのゴールは、マクロINIT_STACKを実装することです。

マクロとは、簡単に再利用できるコードのスニペットです。

マクロINIT_STACKはスタックポインターをメモリーアドレスに初期化するコードです。"INIT_STACK"というキーワードがアセンブリー言語のコード内で使われれば、本来のコード（当レベルで実装したコード）に置き換えられます。

Init stackレベルを解く

1：まだ何もRam上に特別な用途（ここではSP）の場所を設定しない状況を見てみます。computerの枠の下側にRamがあります。4つのアドレスが並んでおり、すべて中身は0x0000です。

右側の「Shared Constants」の[Define Constant]ボタンを押すと、Ram上に特別な用途の場所を作れます。その場所の名前とアドレスを設定する入力欄が出ます。

試しにNameに"SP"、Numberに0を入力します。すると、Ramのアドレス0x0000に"SP"とつきました。

※ポイントはあくまでSPというアドレス0x0000の別名と考えてください。よって、SPは0x0000という固定アドレス、*SPはそのアドレスに設定されたデータ（スタックの先頭アドレス）になります。

※特別な用途の場所を2個以上を作成する場合は、[Add]ボタンから増やせます。

2：（NandGameにおける）スタックの初期化は、SPの値、すなわちRAMにおけるアドレス0x0000にあるデータを256d（＝0x0100）に設定することです。

これをアセンブリー言語で実装すると次のようになります。

A = 0x0100
D = A
A = SP
*A = D

1行目で、レジスターAに0x0100という定数をセットします。

2行目で、レジスターDにレジスターAの保持するデータ0x0100をセットします。この処理の目的は、レジスターAを使うため、この定数を一時的にレジスターDに待避させることにあります。

3行目で、レジスターAにSPのアドレス（0x0000）をセットします。

4行目で、アドレス0x0000のデータをレジスターDの保持するデータ（ここでは定数0x0100）により上書きします。

以上で、SPが0x0100を保持した状態になります。

3：テストにパスするとクリアします。

Push Dレベル

Push Dレベルのゴールは、マクロPUSH_Dを実装することです。

PUSH（プッシュ）とは、スタックに新しい値を格納することです。

マクロPUSH_Dは、レジスターDの現在値をスタックの一番上に置くコードに対応します。

Push Dレベルを解く

1：プログラムを組む前に、Test toolsで実験してみます。

Test toolsの[Init Stack]ボタンを押すと、スタックを使う前準備として初期化します。

Init stackレベルで説明したように、INIT_STACKマクロが実行されます。SPのアドレスは0x0000であり、SPが保持する値（言い換えればRamにおいて0x0000番地に位置する値）は0x0100に初期化されます。

そして、"Stack is empty"と表示されます。

次に0x2aを入力して、[Push]ボタンを押します。すると、Ramの下にStackが現れます。

アドレス0x0100のデータは0x002aになっています。

さらに、SPのデータは0x0100から0x0101に変化しています。つまり、1だけインクリメントされました。

2：それではプログラムを実装してみます。

ステップ1の挙動を一般化したものをプログラムとして実装することになります。

流れとしては、

①SPの指すアドレス、すなわちスタックの先頭アドレスを取得する。

②そのアドレスのデータをレジスターDのデータで上書きします（これがPUSHに相当）。

③その後、SPをインクリメントする。

ポイントはスタックにデータを格納してから、SPをインクリメントすることです。これでSPのデータはスタック上における次の値をセットすべきアドレスを指しています。

A = SP
A = *A
*A = D
A = SP
*A = *A + 1

1行目の「A = SP」で、レジスターAにSP（0x0000）がセットされます。

2行目の「A = *A」で、レジスターAにSPのデータ、すなわちスタックの先頭アドレスがセットとされます。

3行目の「*A = D」で、スタックの先頭アドレスに対応するデータをレジスターDのデータで上書きします。

以降はスタックポインタのインクリメント処理になります。

4行目の「A = SP」で、レジスターAにSP（0x0000）がセットされます。

5行目の「*A = *A + 1」で、SPのデータ、すなわち先頭アドレスをインクリメントします。

Pop Dレベル

Pop Dレベルのゴールは、マクロPOP_Dを実装することです。

POP（ポップ）とは、スタックの一番上にある値を取り出すことです。

マクロPOP_Dは、スタックの一番上のデータを取り出して、レジスターDにセットするコードに対応します。

Pop Dレベルを解く

POPするとき、SPは1減らす必要があります。

NandGameのスタックの仕様において、先にSPをデクリメントしてから、値を取り出します。

A = SP
*A = *A - 1
A = *A
D = *A

前提としてSPはスタックの先頭アドレスを指しています。つまり、SPはそのアドレスを保持しています。

1行目の「A = SP」で、レジスターAにはSP（アドレス0x0000）がセットされます。

2行目の「*A = *A – 1」で、先頭アドレスをデクリメントします。

※ポイントは先にデクリメントすることです。デクリメント前のアドレス、すなわち元の先頭アドレスの位置には値が何もありません（厳密には何かあったとしてもそれは残留している値であり、使ってはならない）。

3行目の「A = *A」で、スタックの先頭アドレス（先頭アドレスのデータではない）をレジスターAにセットします。

4行目の「D = *A」で、スタックの先頭アドレスのデータを取り出して、レジスターDにセットします。

Pop Aレベル

Pop Aレベルのゴールは、マクロPOP_Aを実装することです。

マクロPOP_Dは、スタックの一番上のデータを取り出して、レジスターAにセットするコードに対応します。

ただし、マクロの実行でレジスターDのデータが書き換わってはいけません。

Pop Aレベルを解く

Pop Dレベルのアセンブリーコードを参考にしてください。

4行目の処理をレジスターDではなく、レジスターAにセットするようにするだけです。

A = SP
*A = *A - 1
A = *A
A = *A

コード上にレジスターDが登場していませんので、レジスターDのデータに影響を与えていません。

Push Valueレベル

Push Valueレベルのゴールは、マクロPUSH_VALUEを実装することです。

マクロPUSH_VALUEは、例えばPUSH_VALUE 42のように数字を与えられます。

このマクロを使用すると、マクロコード内のプレースホルダーキーワード値は指定した数値（ここでは42）に置き換えられます。

Push Valueレベルを解く

作成済みのマクロPUSH_Dを活用すれば簡単に実現できます。

A = value
D = A
PUSH_D

1～2行目で、valueをレジスターDにセットしています。

※NandGameの仕様上「D = value」といきなりセットはできません。実際に入力するとエラーになることを確認できます。

3行目で、マクロPUSH_Dを呼び出しています。