ニッシー
1990年生まれ
血液型 O型

こんにちは。ITブログアルケーナム管理人のニッシーです。

詳細プロフィールへ

お問い合わせへ






2019-01-02

CASL2での再起処理のやり方







再起処理は、プログラムにおける合わせ鏡といったところでしょうかね。


鏡の中に鏡自身が無限に続いていく...。


今回は、CASL2を使った「再起処理」について見てみたいと思います。














再起処理とは?



再起処理とは、ある関数(サブルーチン)内でその関数(サブルーチン)そのものを呼び出す処理をいいます。


例えば「関数REC」内で再び関数RECを呼び出す処理がこれに当たります。



以下のプログラムは、CASL2における「REC」というサブルーチンの再起処理の例です。


1 MAIN START 
2   CALL REC 
3   RET 
4    
5 REC CALL REC ;再起処理
6   RET 
7   END 



このプログラムは、RECサブルーチンが呼び出されると、更にRECサブルーチンが呼び出され、また更にRECサブルーチンが呼び出され続けます。


試しに、シミュレータにコピー&ペーストして動作を確認してもらえば解りますが、無限にループします。


まさに「合わせ鏡」ですね。


しかし、CALL命令を繰り返すため、やがてスタックの容量を食いつぶし、オーバーフローすることで停止します。


これは合わせ鏡において、鏡の中の鏡が連なる度に、映し出された像の面積が徐々に小さくなることでやがて消滅することに似ている気がします。


そういう点を踏まえても、合わせ鏡という比喩はある意味正しいといえるのではないでしょうか。



スタックオーバーフローによってプログラムが停止するとはいえ、シミュレータによってはずっと処理している場合もあります。


COMET2は架空のコンピュータなので、その辺はご愛嬌ですね。


理論上はスタックの容量がいっぱいになり停止します。


再起処理を記述する際は、停止用の条件を必ず設けなくてはなりません。



それでは再起処理でどのような機能が実現できるのか見てみたいと思います。





数を列挙するプログラム



例1:0~3までの数(文字列)を出力


1 MAIN START 
2   LD GR0, NUMSTR 
3   LAD GR1, 0 
4   CALL ENUM 
5   OUT RES, STRLEN 
6   RET 
7    
8 ENUM CPA GR1, STRLEN 
9   JZE FIN 
10   ST GR0, RES, GR1 
11   ADDA GR0, =1 
12   LAD GR1, 1, GR1 
13   CALL ENUM ;再起処理
14 FIN RET 
15    
16 RES DS 4 ;文字列を入れる領域
17 NUMSTR DC '0' ;数字文字列
18 STRLEN DC 4 ;文字列の長さ
19   END 


シミュレータにそのままコピー&ペーストで使えます。



解説



数を列挙するプログラムは、再起する度に文字コードに1を加算し、メモリにその文字を転送することで実現しています。


例えば...


・初め:
 「0」文字コード(0030)16 をメモリA番地に転送


・再起1回目:
 「0」文字コード(0030)16 +1 をメモリA+1番地に転送


・再起2回目:
 「1」文字コード(0031)16 +1 をメモリA+2番地に転送


・再起3回目:
 「2」文字コード(0032)16 +1 をメモリA+3番地に転送


というような処理を施しています。


再起処理の停止条件として、GR1の値がSTRLEN番地の値と同じになったときに処理を抜けるようになっています。



それでは、机上デバッグもどきでデータの流れを見てみたいと思います。



例1のENUM(7~14行)のトレース



初期状態

【汎用レジスタ】
GR0110000
GR10

【フラグレジスタ】
ZFSFOF
000

【メモリ】
RES+0
RES+1
RES+2
RES+3



8行 CPA GR1, STRLEN

【汎用レジスタ】
GR0110000
GR10

【フラグレジスタ】
ZFSFOF
010

【メモリ】
RES+0
RES+1
RES+2
RES+3

CPA命令で、GR1の値 0 と STRLEN番地の値 4 を比較します。
0 < 4 なのでフラグレジスタが変化します。



9行 JZE FIN

【フラグレジスタ】
ZFSFOF
010

ZFが0なので、JZE命令で指定されたラベル「FIN」に移動せず10行を処理します。



10行 ST GR0, RES, GR1

【汎用レジスタ】
GR0110000
GR10

【フラグレジスタ】
ZFSFOF
010

【メモリ】
RES+0110000
RES+1
RES+2
RES+3

ST命令で、RES+0番地に「0」の文字コードを格納します。



11行 ADDA GR0, =1

【汎用レジスタ】
GR0110001
GR10

【フラグレジスタ】
ZFSFOF
000

【メモリ】
RES+0110000
RES+1
RES+2
RES+3

GR0の値が(0031)16になるためフラグレジスタが変化します。



12行 LAD GR1, 1, GR1

【汎用レジスタ】
GR0110001
GR11

【フラグレジスタ】
ZFSFOF
000

【メモリ】
RES+0110000
RES+1
RES+2
RES+3



13行 CALL ENUM

CALL命令で、「ENUM」サブルーチンを呼び出し、再起処理により再び8行を処理します。




~再起1回目~

8行 CPA GR1, STRLEN

【汎用レジスタ】
GR0110001
GR11

【フラグレジスタ】
ZFSFOF
010

【メモリ】
RES+0110000
RES+1
RES+2
RES+3

CPA命令で、GR1の値 1 と STRLEN番地の値 4 を比較します。
1 < 4 なのでフラグレジスタが変化します。



8行 JZE FIN

【フラグレジスタ】
ZFSFOF
010

ZFが0なので、JZE命令で指定されたラベル「FIN」に移動せず10行を処理します。



10行 ST GR0, RES, GR1

【汎用レジスタ】
GR0110001
GR11

【フラグレジスタ】
ZFSFOF
010

【メモリ】
RES+0110000
RES+1110001
RES+2
RES+3

ST命令で、RES+1番地に「1」の文字コードを格納します。



11行 ADDA GR0, =1

【汎用レジスタ】
GR0110010
GR11

【フラグレジスタ】
ZFSFOF
000

【メモリ】
RES+0110000
RES+1110001
RES+2
RES+3

GR0の値が(0032)16になるためフラグレジスタが変化します。



12行 LAD GR1, 1, GR1

【汎用レジスタ】
GR0110010
GR110

【フラグレジスタ】
ZFSFOF
000

【メモリ】
RES+0110000
RES+1110001
RES+2
RES+3



13行 CALL ENUM

CALL命令で、「ENUM」サブルーチンを呼び出し、再起処理により再び8行を処理します。




~再起2回目~

8行 CPA GR1, STRLEN

【汎用レジスタ】
GR0110010
GR110

【フラグレジスタ】
ZFSFOF
010

【メモリ】
RES+0110000
RES+1110001
RES+2
RES+3

CPA命令で、GR1の値 2 と STRLENの値 4 を比較します。
2 < 4 なのでフラグレジスタが変化します。



8行 JZE FIN

【フラグレジスタ】
ZFSFOF
010

ZFが0なので、JZE命令で指定されたラベル「FIN」に移動せず10行を処理します。



10行 ST GR0, RES, GR1

【汎用レジスタ】
GR0110010
GR110

【フラグレジスタ】
ZFSFOF
010

【メモリ】
RES+0110000
RES+1110001
RES+2110010
RES+3

ST命令で、RES+2番地に「2」の文字コードを格納します。



11行 ADDA GR0, =1

【汎用レジスタ】
GR0110011
GR110

【フラグレジスタ】
ZFSFOF
000

【メモリ】
RES+0110000
RES+1110001
RES+2110010
RES+3

GR0の値が(0033)16になるためフラグレジスタが変化します。



12行 LAD GR1, 1, GR1

【汎用レジスタ】
GR0110011
GR111

【フラグレジスタ】
ZFSFOF
000

【メモリ】
RES+0110000
RES+1110001
RES+2110010
RES+3



13行 CALL ENUM

CALL命令で、「ENUM」サブルーチンを呼び出し、再起処理により再び8行を処理します。




~再起3回目~

8行 CPA GR1, STRLEN

【汎用レジスタ】
GR0110011
GR111

【フラグレジスタ】
ZFSFOF
010

【メモリ】
RES+0110000
RES+1110001
RES+2110010
RES+3

CPA命令で、GR1の値 3 と STRLENの値 4 を比較します。
3 < 4 なのでフラグレジスタが変化します。



9行 JZE FIN

【フラグレジスタ】
ZFSFOF
010

ZFが0なので、JZE命令で指定されたラベル「FIN」に移動せず10行を処理します。



10行 ST GR0, RES, GR1

【汎用レジスタ】
GR0110011
GR111

【フラグレジスタ】
ZFSFOF
010

【メモリ】
RES+0110000
RES+1110001
RES+2110010
RES+3110011

ST命令で、RES+3番地に「3」の文字コードを格納します。



11行 ADDA GR0, =1

【汎用レジスタ】
GR0110100
GR111

【フラグレジスタ】
ZFSFOF
000

【メモリ】
RES+0110000
RES+1110001
RES+2110010
RES+3110011

GR0の値が(0034)16になるためフラグレジスタが変化します。



12行 LAD GR1, 1, GR1

【汎用レジスタ】
GR0110100
GR1100

【フラグレジスタ】
ZFSFOF
000

【メモリ】
RES+0110000
RES+1110001
RES+2110010
RES+3110011



13行 CALL ENUM

CALL命令で、「ENUM」サブルーチンを呼び出し、再起処理により再び8行を処理します。




~再起4回目~

8行 CPA GR1, STRLEN

【汎用レジスタ】
GR0110011
GR1100

【フラグレジスタ】
ZFSFOF
100

【メモリ】
RES+0110000
RES+1110001
RES+2110010
RES+3110011

CPA命令で、GR1の値 3 と STRLENの値 4 を比較します。
4 = 4 なのでフラグレジスタが変化します。



9行 JZE FIN

【フラグレジスタ】
ZFSFOF
100

ZFが1なので、JZE命令で指定されたラベル「FIN」に移動し14行を処理します。




~再起3回目に戻る~

14行 RET

RET命令で、「ENUM」サブルーチンを抜けて、呼び出し元の「ENUM」サブルーチンに戻り処理が終了します。




~再起2回目に戻る~

14行 RET

RET命令で、「ENUM」サブルーチンを抜けて、呼び出し元の「ENUM」サブルーチンに戻り処理が終了します。




~再起1回目に戻る~

14行 RET

RET命令で、「ENUM」サブルーチンを抜けて、呼び出し元の「ENUM」サブルーチンに戻り処理が終了します。




~再起から抜ける~

14行 RET

RET命令で、「ENUM」サブルーチンを抜けて、呼び出し元の「MAIN」サブルーチンに戻り処理が終了します。



以上で、処理が終了しメモリの内容が以下のようになります。



RES+0:(0030)16 = 「0」の文字コード


RES+1:(0031)16 = 「1」の文字コード


RES+2:(0032)16 = 「2」の文字コード


RES+3:(0033)16 = 「3」の文字コード



最後にOUT命令で、RES+0番地 ~ RES+3番地まで出力され「0 1 2 3 」と表示されます。


正しい答えになっていますね。













再起処理を用いた階乗



例2:3! の計算


1 MAIN START 
2   LAD GR0, 1 
3   LD GR1, VAL 
4   CALL FAC 
5   ST GR0, ANS 
6   RET 
7    
8 FAC CPA GR1, =0 
9   JZE FIN 
10   PUSH 0, GR1 
11   LAD GR1, -1, GR1 
12   CALL FAC ;再起処理
13   POP GR1 
14   CALL MUL 
15 FIN RET 
16    
17 MUL LAD GR3, 0 
18   LD GR2, GR0 
19 LP ADDA GR3, GR1 
20   SUBA GR2, =1 
21   JPL LP 
22   LD GR0, GR3 
23   RET 
24    
25 VAL DC 3 ;階数
26 ANS DS 1 ;答え
27   END 


シミュレータにそのままコピー&ペーストで使えます。



解説



再起処理を用いた階乗は、「FAC」サブルーチンを呼び出す度に階数の値から1を引き、その階数の値をスタックへ退避しています。


その後、階数の値が0になったら、呼び出し元のサブルーチンに戻り、スタックの一番上からデータを汎用レジスタに戻し掛け算処理を行っています。





再起処理は少し分かり難いものなので、データの流れを一つ一つ追っていくことで理解の助けになるはずです。


以下のデバッグは長いですが、興味のある方は見てみてください。


また、シミュレータをお持ちの方はそちらで動作を確認してみてください。



例2のFAC(7~16行)・MUL(18~24行)のトレース



初期状態

【汎用レジスタ】
GR01
GR111
GR2?
GR3?

【フラグレジスタ】
ZFSFOF
000

【スタック】



8行 CPA GR1, =0

【汎用レジスタ】
GR01
GR111
GR2?
GR3?

【フラグレジスタ】
ZFSFOF
000

【スタック】

CPA命令で、GR1の値 3 と 0 を比較します。
3 > 0 なのでフラグレジスタに変化はありません。



9行 JZE NX

【フラグレジスタ】
ZFSFOF
000

ZFが0なので、JZE命令で指定されたラベル「FIN」に移動せず10行を処理します。



10行 PUSH 0, GR1

【汎用レジスタ】
GR01
GR111
GR2?
GR3?

【フラグレジスタ】
ZFSFOF
000

【スタック】
SP>11

GR1の値3をスタックへ退避します。



11行 LAD GR1, -1, GR1

【汎用レジスタ】
GR01
GR110
GR2?
GR3?

【フラグレジスタ】
ZFSFOF
000

【スタック】
SP>11



12行 CALL FAC

CALL命令で、「FAC」サブルーチンを呼び出し、再起処理により再び8行を処理します。




~再起1回目~

8行 CPA GR1, =0

【汎用レジスタ】
GR01
GR110
GR2?
GR3?

【フラグレジスタ】
ZFSFOF
000

【スタック】
SP>11

CPA命令で、GR1の値 2 と 0 を比較します。
2 > 0 なのでフラグレジスタに変化はありません。



9行 JZE NX

【フラグレジスタ】
ZFSFOF
000

ZFが0なので、JZE命令で指定されたラベル「FIN」に移動せず10行を処理します。



10行 PUSH 0, GR1

【汎用レジスタ】
GR01
GR110
GR2?
GR3?

【フラグレジスタ】
ZFSFOF
000

【スタック】
SP>10
11

GR1の値2をスタックへ退避します。



11行 LAD GR1, -1, GR1

【汎用レジスタ】
GR01
GR11
GR2?
GR3?

【フラグレジスタ】
ZFSFOF
000

【スタック】
SP>10
11



12行 CALL FAC

CALL命令で、「FAC」サブルーチンを呼び出し、再起処理により再び8行を処理します。




~再起2回目~

8行 CPA GR1, =0

【汎用レジスタ】
GR01
GR11
GR2?
GR3?

【フラグレジスタ】
ZFSFOF
000

【スタック】
SP>10
11

CPA命令で、GR1の値 1 と 0 を比較します。
1 > 0 なのでフラグレジスタに変化はありません。



9行 JZE NX

【フラグレジスタ】
ZFSFOF
000

ZFが0なので、JZE命令で指定されたラベル「FIN」に移動せず10行を処理します。



10行 PUSH 0, GR1

【汎用レジスタ】
GR01
GR11
GR2?
GR3?

【フラグレジスタ】
ZFSFOF
000

【スタック】
SP>1
10
11

GR1の値1をスタックへ退避します。



12行 LAD GR1, -1, GR1

【汎用レジスタ】
GR01
GR10
GR2?
GR3?

【フラグレジスタ】
ZFSFOF
000

【スタック】
SP>1
10
11



12行 CALL FAC

CALL命令で、「FAC」サブルーチンを呼び出し、再起処理により再び8行を処理します。




~再起3回目~

8行 CPA GR1, =0

【汎用レジスタ】
GR01
GR10
GR2?
GR3?

【フラグレジスタ】
ZFSFOF
100

【スタック】
SP>1
10
11

CPA命令で、GR1の値 0 と 0 を比較します。
0 = 0 なのでフラグレジスタが変化します。



9行 JZE NX

【フラグレジスタ】
ZFSFOF
100

ZFが1なので、JZE命令で指定されたラベル「FIN」に移動し15行を処理します。



15行 RET

RET命令で、「FAC」サブルーチンを抜けて、呼び出し元の「FAC」サブルーチンに戻り13行を処理します。




~再起2回目に戻る~

13行 POP GR1

【汎用レジスタ】
GR01
GR11
GR2?
GR3?

【フラグレジスタ】
ZFSFOF
100

【スタック】
1
SP>10
11

POP命令で、スタックから値1をGR1に戻します。



12行 CALL MUL

CALL命令で、「MUL」サブルーチンを呼び出し、18行を処理します。





~MULサブルーチン内~

17行 LAD GR3, 0

【汎用レジスタ】
GR01
GR11
GR2?
GR30

【フラグレジスタ】
ZFSFOF
100

【スタック】
SP>10
11



18行 LD GR2, GR0

【汎用レジスタ】
GR01
GR11
GR21
GR30

【フラグレジスタ】
ZFSFOF
100

【スタック】
SP>10
11



~1ループ目~

19行 ADDA GR3, GR1

【汎用レジスタ】
GR01
GR11
GR21
GR31

【フラグレジスタ】
ZFSFOF
000

【スタック】
SP>10
11

GR3の値が1になるためフラグレジスタが変化します。



20行 SUBA GR2, =1

【汎用レジスタ】
GR01
GR11
GR20
GR31

【フラグレジスタ】
ZFSFOF
100

【スタック】
SP>10
11

GR2の値が0になるためフラグレジスタが変化します。



21行 JPL LP

【フラグレジスタ】
ZFSFOF
100

ZFが1、SFが0なので、JPL命令で指定されたラベル「LP」に移動せず22行を処理します。



22行 LD GR0, GR3

【汎用レジスタ】
GR01
GR11
GR20
GR31

【フラグレジスタ】
ZFSFOF
100

【スタック】
SP>10
11



23行 RET

RET命令で、「FAC」サブルーチンを抜けて、呼び出し元の「FAC」サブルーチンに戻り13行を処理します。





~再起1回目に戻る~

13行 POP GR1

【汎用レジスタ】
GR01
GR110
GR20
GR31

【フラグレジスタ】
ZFSFOF
100

【スタック】
10
SP>11

POP命令で、スタックから値2をGR1に戻します。



14行 CALL MUL

CALL命令で、「MUL」サブルーチンを呼び出し、18行を処理します。





~MULサブルーチン内~

17行 LAD GR3, 0

【汎用レジスタ】
GR01
GR110
GR20
GR30

【フラグレジスタ】
ZFSFOF
100

【スタック】
SP>11



18行 LD GR2, GR0

【汎用レジスタ】
GR01
GR110
GR21
GR30

【フラグレジスタ】
ZFSFOF
100

【スタック】
SP>11



~2ループ目~

19行 ADDA GR3, GR1

【汎用レジスタ】
GR01
GR110
GR21
GR310

【フラグレジスタ】
ZFSFOF
000

【スタック】
SP>11

GR3の値が2になるためフラグレジスタが変化します。



20行 SUBA GR2, =1

【汎用レジスタ】
GR01
GR110
GR20
GR310

【フラグレジスタ】
ZFSFOF
100

【スタック】
SP>11

GR2の値が0になるためフラグレジスタが変化します。



21行 JPL LP

【フラグレジスタ】
ZFSFOF
100

ZFが1、SFが0なので、JPL命令で指定されたラベル「LP」に移動せず22行を処理します。



22行 LD GR0, GR3

【汎用レジスタ】
GR010
GR110
GR20
GR310

【フラグレジスタ】
ZFSFOF
100

【スタック】
SP>11



23行 RET

RET命令で、「MUL」サブルーチンを抜けて、呼び出し元の「FAC」サブルーチンに戻り13行を処理します。





~再起から抜ける~

13行 POP GR1

【汎用レジスタ】
GR010
GR111
GR20
GR310

【フラグレジスタ】
ZFSFOF
100

【スタック】
11

POP命令で、スタックから値3をGR1に戻します。



14行 CALL MUL

CALL命令で、「MUL」サブルーチンを呼び出し、17行を処理します。





~MULサブルーチン内~

17行 LAD GR3, 0

【汎用レジスタ】
GR010
GR111
GR20
GR30

【フラグレジスタ】
ZFSFOF
100

【スタック】



18行 LD GR2, GR0

【汎用レジスタ】
GR010
GR111
GR210
GR30

【フラグレジスタ】
ZFSFOF
100

【スタック】



~1ループ目~

19行 ADDA GR3, GR1

【汎用レジスタ】
GR010
GR111
GR210
GR311

【フラグレジスタ】
ZFSFOF
000

【スタック】

GR3の値が3になるためフラグレジスタが変化します。



20行 SUBA GR2, =1

【汎用レジスタ】
GR010
GR111
GR21
GR311

【フラグレジスタ】
ZFSFOF
000

【スタック】

GR2の値が1になるためフラグレジスタに変化はありません。



21行 JPL LP

【フラグレジスタ】
ZFSFOF
000

ZFが0、SFが0なので、JPL命令で指定されたラベル「LP」に移動し19行を処理します。



~2ループ目~

19行 ADDA GR3, GR1

【汎用レジスタ】
GR010
GR111
GR21
GR3110

【フラグレジスタ】
ZFSFOF
000

【スタック】

GR3の値が6になるためフラグレジスタに変化はありません。



20行 SUBA GR2, =1

【汎用レジスタ】
GR010
GR111
GR20
GR3110

【フラグレジスタ】
ZFSFOF
100

【スタック】

GR2の値が0になるためフラグレジスタが変化します。



21行 JPL LP

【フラグレジスタ】
ZFSFOF
100

ZFが1、SFが0なので、JPL命令で指定されたラベル「LP」に移動せず22行を処理します。



22行 LD GR0, GR3

【汎用レジスタ】
GR0110
GR111
GR20
GR3110

【フラグレジスタ】
ZFSFOF
100

【スタック】



23行 RET

RET命令で、「MUL」サブルーチンを抜けて、呼び出し元の「FAC」サブルーチンに戻り13行を処理します。





13行 RET

RET命令で、「FAC」サブルーチンを抜けて、呼び出し元の「MAIN」サブルーチンに戻り処理が終了します。



以上で処理が終了し、GR0が答えです。


GR0:(110)2 = 6


3! = 6
なので、正しい答えになっていますね。



ちなみに、上記のデバッグ内でスタックの動作は実際の動作とは異なります。


実際は、CALL命令を実行した段階で呼び出し元のサブルーチンのアドレスもスタックに積み上げられます。


とはいえ、プログラムの整合性に影響はない上、何より分かり難いので省略しています。



階乗とは?






階乗とは、例えば「3の階乗」であれば、3までの数を順番に掛け算する計算をいいます。


また、「3!」のように感嘆詞の「!」を使用して表します。



例えば、以下のような意味になります。





なので、1000の階乗はというと...


1000! = 1 × 2 × 3 × .... ×1000


大きな数字になると処理が膨大になってしまうため、大変な計算でもあります。





最後に



再起処理はイメージし難い処理の一つですが、処理の流れを一行一行追ってみることで理解できるようになるはずです。


それでは、続きはまた次回にご期待を!














プロフィール

ニッシー
1990年生まれ
血液型 O型

こんにちは。ITブログアルケーナム管理人のニッシーです。

詳細プロフィールへ

お問い合わせへ