The Art of Computer Programming を読む(7)

(5) の続きから。

アルゴリズムP (500の素数の表を印刷する)

素数列挙プログラムを通じてMIXALを学ぶ。

ローカルシンボル
今いる行から一番近い行を指示することができる。プログラム内で複数の同じシンボルを扱うことができ、記号名の取り扱いの煩雑さからプログラマを解放する。

ALF
MIXの5バイトの定数を作るが、その時に文字コードを利用する擬命令。

ORIG
ここに来て意味がわかるようになった。MIXアセンブラが解釈するロケーションカウンタの値をアドレス欄の値にセットする擬命令。

ロケーションカウンタ
MIXアセンブラが書かれたMIX命令を解釈する時、このカウンタの値に命令を書き込む。

二項演算 //
見慣れない命令だが、上位5バイトに対して割り算をする擬命令と思えば良いだろうか。下位5バイトには0が詰め込まれる。
1//3の値は、バイトが10なら10000/3と同じになる。バイトが2なら2^5/3と同じになる。

EQU
アセンブラ上でのみ有効な定数を定義する擬命令。マクロのようなもの。MIX命令は生成しない。

CON
MIXプログラム上で利用する定数を、ロケーションカウンタの値に生成する擬命令。

これで一通りMIXALの説明を読み終わった。また演習問題を解いていく。

3.

最大値を求めるプログラムMに続けて次のプログラムを実行するとどうなるか?という問題。

START IN   X+1(0)
      JBUS *(0)
      ENT1 100
1H    JMP  MAXIMUM
      LDX  X,1
      STA  X,1
      STX  X,2
      DEC1 1
      J1P  1B
      OUT  X+1(1)
      HLT
      END  START

順に一つ一つ見ていく。

START IN  X+1(0)
JBUS  *(0)

IN命令は、Fパートのユニットからユニットごとに決められたワード数だけ指定されたアドレスに転送するのであった。Xは元のプログラムMで EQU 1000 と定められている。したがってこれは「0番テープの100ワードを1001-1100番地に転送する」という命令になる。
JBUS命令は、Fパートで指定されたユニットがビジーならジャンプする。ロケーションカウンタ*により自分自身へのジャンプなので、これは「0番テープがビジーでなくなるまで無限ループする」という命令になる。

ENT1  100

元のプログラムMでは、rI1は「最大値を求める対象の要素数」を表していた。今回は1001-1100なので100が正しい。

1H JMP  MAXIMUM

MAXIMUMは元のプログラムPの開始番地になっている。したがって、ここでプログラムPにジャンプしている。
プログラムPの呼び出しが終わった後、rAには最大値が、rI2には最大値を与える値のメモリの番地がセットされる。

LDX  X,1
STA  X,1
STX  X,2

X,1は「1000をrI1で修飾したメモリの番地」である。今rI1は100なので、LDX X,1は「1100番地の値をrXにロードする」命令となる。
その後、rA、つまりプログラムによって与えられた最大値が1100番地に格納される。rXにロードされていた元々の1100番地の値は、「1000をrI2で修飾したメモリの番地」、つまり最大値を与えるメモリの番地にストアされている。

DEC1 1
J1P  1B

rI1の値を1減らし、rI1が正ならこれをもう一度繰り返す。

rI1が100から99にデクリメントされて再度実行される様子を考えると、今度は99個の要素から最大値を探し、その値がrAに、この値を与えるインデックスがrI2に格納される。
その後、1100番地の時と同様に、1099番地の値と最大値が交換される。
これを繰り返すと、1001番地から1100番地の値が昇順にソートされることがわかる。

OUT X+1(1)
HLT
END START

OUT命令は書き出しだ。今度はテープユニットの1番テープに、1001-1100の100ワードを転送している。

したがって、まとめると
0番テープの100ワードが、昇順にソートされて1番テープに書き出される
となる。

問題4の手動アセンブルも面白そうなのだが、遅い時間になってしまったのでまた次回にする。

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

ksk

哲学者でも科学者でもない素人が、哲学とか科学とか科学哲学とかを考えながら本を読む。

TAOCP読書メモ

Donald E. Knuth博士の The Art of Computer Programming の読書メモ。 アスキードワンゴ社から出ている日本語訳を読んでいます。 https://asciidwango.jp/post/122327235600/the-art-of...
コメントを投稿するには、 ログイン または 会員登録 をする必要があります。