CP/M68K で intcodeインタプリタで動いたが、それだけではもったいない。
Martin RichardsのBCPLサイト「https://www.cl.cam.ac.uk/~mr10/index.html」に
bcplで記述されたmlisp.bがある。これを動かすことを考えた。
ところがいろいろな問題が発生(*1)。なんとか回避したが、最後にインタプリタのバグ？が判明し諦めた。
(根本は CP/M68KのCにまで遡る。これを回避するのは難しい)
・バグの発見までの経緯
さまざまな問題を開始したが、どうしてもmlisp.bが動かない。
コンパイル途中のTREEを見ると、P_LISTが -0 になっていた? ソースでは $80000000 なのに。
! *--1
*-OP75
*-OP43
! *-OP43
! ! *-OP43
! ! ! *-NIL
! ! ! *-P_LIST
! ! ! *--0
! ! *-B
! ! *-2
そこでテストコードを作成しコンパイルしてみた
===================
GET "LIBHDR"
MANIFEST $(
X =#X7FFFFFFF
Y =#X80000000
Z =#X80000001
$)
LET START() BE
$(
WRITEF("%X8 %X8 %X8*N", X, Y, Z)
WRITEF("%N %N %N*N", X, Y, Z)
$)
===================
OCODEではなぜか #X80000000が -00 になっている
STACK 2 JUMP L2 ENTRY 5 L1 83 84 65 82 84 SAVE 2 STACK 4 LSTR
12 37 88 56 32 37 88 56 32 37 88 56 10 LN 2147483647 LN -00 LN
-2147483647 LG 76 RTAP 2 STACK 4 LSTR 9 37 78 32 37 78 32 37 78
10 LN 2147483647 LN -00 LN -2147483647 LG 76 RTAP 2 RTRN ENDPROC
0 STACK 2 LAB L2 STORE GLOBAL 1 1 L1
INTCODEは 0 になっている
JL2
$ 1 LL499 SP4 L2147483647 SP5 L0 SP6 L-2147483647 SP7 LIG76 K2 LL498 SP/
4 L2147483647 SP5 L0 SP6 L-2147483647 SP7 LIG76 K2 X4 2
499 C12 C37 C88 C56 C32 C37 C88 C56 C32 C37 C88 C56 C10 498 C9 C37 C78 /
C32 C37 C78 C32 C37 C78 C10
G1L1
Z
実行してみると
===========================
C>icint test.int
INTCODE SYSTEM ENTERED
PROGRAM SIZE = 644
7FFFFFFF 00000000 80000001
2147483647 0 -2147483647
EXECUTION CYCLES = 2295, CODE = 0
============================
どうやら0x80000000を表示できないらしい。
今度はCでテストコードを実行
===test2.c======================
#include <stdio.h>
int main()
{
long x = 0x80000000L;
int y = 1;
int z = 0;
printf("%08lx\n", x);
printf("%08lx\n", -x);
printf("%08lx\n", x / y);
printf("%08lx\n", x / z);
printf("%d\n", y / z);
}
C>test2
80000000 ==> わかる
80000000 ==> わからないこともない
00000000 ==> 1で割っているのに？ わからない
80000000 ==> 0で割っているのに？ わからない
Exception $05 at user address $000082A8. Aborted. ==> わかる(当然)
===test2.s======
.globl __iob
.globl _main
.text
_main:
~~main:
~_EnD__=8
link R14,#-12
~x=-4
*line 5
move.l #$80000000,-4(R14) long x = 0x80000000L;
~y=-6
*line 6
move #1,-6(R14) int y = 1;
~z=-8
*line 7
clr -8(R14) int z = 0;
*line 8
move.l -4(R14),(sp) printf("%08lx\n", x); ==> 80000000
move.l #L2,-(sp)
jsr _printf
addq.l #4,sp
*line 9
move.l -4(R14),R0 printf("%08lx\n", -x); ==> 80000000
neg.l R0
move.l R0,(sp)
move.l #L3,-(sp)
jsr _printf
addq.l #4,sp
*line 10
move -6(R14),R0 printf("%08lx\n", x / y); ==> 00000000
ext.l R0
move.l R0,-(sp)
move.l -4(R14),-(sp)
jsr ldiv
addq.l #8,sp
move.l R0,(sp)
move.l #L4,-(sp)
jsr _printf
addq.l #4,sp
*line 11
move -8(R14),R0 printf("%08lx\n", x / z); ==> 80000000
ext.l R0
move.l R0,-(sp)
move.l -4(R14),-(sp)
jsr ldiv
addq.l #8,sp
move.l R0,(sp)
move.l #L5,-(sp)
jsr _printf
addq.l #4,sp
*line 12
move -6(R14),R0 printf("%d\n", y / z); ==> Exception $05
ext.l R0
divs -8(R14),R0
move R0,(sp)
move.l #L6,-(sp)
jsr _printf
addq.l #4,sp
L1:
unlk R14
rts
.data
L2:
.dc.b $25,$30,$38,$6C,$78,$A,$0
L3:
.dc.b $25,$30,$38,$6C,$78,$A,$0
L4:
.dc.b $25,$30,$38,$6C,$78,$A,$0
L5:
.dc.b $25,$30,$38,$6C,$78,$A,$0
L6:
.dc.b $25,$64,$A,$0
=================================================
CP/MのDDTで確認したところ、
CP/M68KのCの32ビットの割り算ルーチン(_ldiv)にいろいろ癖があることが判明。
除数が0だと(エラーではなく)0x80000000になる。
被除数が16ビット内だと divuを使うが、それ以上だとソフトウエアでの除算
被除数が0x80000000の場合への考慮がない。
(被除数が負の場合はnegしているが0x80000000の場合はnegしても0x80000000)
---$4(A7)/$8(A7) -> D1/D3 ----------------------------
---D1が 0x80000000の場合は、neg.l D1によりD1= となる。
_ldiv:
ldiv:
0000AD7A movea.l D3,A0
0000AD7C move.l $4(A7),D1 被除数をD1へ
0000AD80 bge $AD84 被除数が0または正なら分岐
0000AD82 neg.l D1 負の場合は正の数にする
0000AD84 move.l $8(A7),D3 除数をD3へ
0000AD88 bgt $AD98 除数が正なら分岐
0000AD8A blt $AD96 除数が負なら分岐
0000AD8C move.l #$80000000,D0 ここに来るのは除数が0 返り値が$80000000
0000AD92 move.l D0,D1
0000AD94 bra $ADE4
0000AD96 neg.l D3 除数を正の数にする
0000AD98 moveq.l #$0,D0
0000AD9A cmp.l D1,D3 被除数と除数を比較
0000AD9C blt $ADA6 D1>D3(被除数>除数)なら分岐
0000AD9E bgt $ADD2 D1<D3(被除数<除数)なら分岐
0000ADA0 moveq.l #$1,D0 D1=D3(被除数=除数)なら 商=1 余り=0
0000ADA2 moveq.l #$0,D1
0000ADA4 bra $ADD2 符号調整
0000ADA6 moveq.l #$2,D2
0000ADA8 cmp.l #$10000,D1
0000ADAE bge $ADBC 被除数が>=#$10000なら分岐(ソフトウエアで割り算)
0000ADB0 divu D3,D1 d1.l / d3.w => d1.h ... d1.l
0000ADB2 move.w D1,D0 d0=余り
0000ADB4 clr.w D1
0000ADB6 swap D1 d1=商
0000ADB8 bra $ADD2 符号調整
0000ADBA add.l D2,D2
0000ADBC add.l D3,D3
0000ADBE cmp.l D3,D1
0000ADC0 bcc $ADBA 被除数<除数 になるまで除数を左シフトしながらループ
0000ADC2 bra $ADCC
0000ADC4 cmp.l D3,D1
0000ADC6 bcs $ADCC D1<D3ならブランチ
0000ADC8 or.l D2,D0 商はD0に出来てくる
0000ADCA sub.l D3,D1 D1=D1-D3
0000ADCC lsr.l #1,D3 除数を右シフト
0000ADCE lsr.l #1,D2
0000ADD0 bne $ADC4
0000ADD2 tst.w $4(A7) 被除数が
0000ADD6 bpl $ADDC 正ならブランチ
0000ADD8 neg.l D0 負の場合は、商も余りも符号反転
0000ADDA neg.l D1
0000ADDC tst.w $8(A7) 除数が
0000ADE0 bpl $ADE4 正ならブランチ
0000ADE2 neg.l D0 負なら商を符号反転
0000ADE4 move.l D1,$B294 ._ldivr
0000ADEA move.l A0,D3
0000ADEC rts
商と余りの符号は以下のようになる
正 / 正 = 正 ... 正
負 / 正 = 負 ... 負
正 / 負 = 負 ... 正
負 / 負 = 正 ... 負
・結論
コンパイラで0x80000000が表示出来ないのはlongの除算の扱いがおかしなためと思われる。
(BCPLの印字のライブラリでも以下のようになっており、N=0x80000000では問題が起きる)
=================
AND WRITED(N, D) BE
$(1 LET T = VEC 20
AND I, K = 0, N
TEST N<0 THEN D := D-1 ELSE K := -N
T!I, K, I := K REM 10, K/10, I+1 REPEATUNTIL K=0
FOR J = I+1 TO D DO WRCH('*S')
IF N<0 DO WRCH('-')
FOR J = I-1 TO 0 BY -1 DO WRCH('0'-T!J) $)1
AND WRITEN(N) BE WRITED(N, 0)
=================
では、CP/M68KのCの問題かといえば、(CP/M68KのCはANSIではないけれど)
ANSI Cであっても long は <=−2,147,483,647 とのこと。
なので、−2,147,483,647まで扱えれば、-2,147,483,648が扱えなくても文句は言えない。
・大本の原因
結局 -2,147,483,648が表示出来ると想定しているインタプリタのバグと言えるかも。。。
(*1)
[1]syntaxエラー
BCPLは歴史的にuppercaseが使用されるが該当プログラムはlowercaseとなっている。
ソースを置換することも検討した。(cat mlisp.b | tr [a-z] [A-Z] > mlisp2.b)
ところがunderscore も使用されている。これを受け入れるようにするためsyn.bの変更が必要となった。
[2]%演算子
元のコンパイラでGETBYTE, PUTBYTEという関数があったが、mlisp.bでは%演算子が使用されている。
GETBYTE(x,y) は x%y, PUTBYTE(x,y,z) は x%y = zとなる。
[3]領域不足
コンパイルすると「PROGRAM TOO LARGE」というエラーが出る。
OPTIONSでL7500としている(もともと設定されていた)が足らない。L9000まで増加すればエラーは出なくなった。
コンパイル結果を見ると TREE SIZE 8499 となっていた。
[4]領域不足
コンパイルすると「TOO MANY GLOBALS」というエラーが出る。
trn.bを見ると100に設定されている。これでは足りないようだ。
[5]ライブラリ関数不足
NAME NOT DECLAREDが出る。RDARGS, STR2NUMB, GETVEC, FREEVECがない。
GETVECやFREEVECもCのmallocを使いたいところであるが、
intcodeインタプリタ方式では簡単に追加出来ない
X(EXECUTEOPERATIONS)に割り振って、LIBHDRで名前定義して、iclib.iで連携することが必要。
実はINTCODE_documentaion.pdfではX1(A:=loc(A))〜X27(output)なのに、
icint.cではX1(A:=loc(A))〜X39(output)、さらにiclib.iではX41(REWIND)まである。
(LIBHDRにはGLOBAL変数としてREWINDが用意されているのだが)
要するにintcodeには共通規格があるわけでなく、それぞれの処理系でインタプリタと一緒に
提供されるもののようだ。
Martin RichardsのBCPLサイト「https://www.cl.cam.ac.uk/~mr10/index.html」に
bcplで記述されたmlisp.bがある。これを動かすことを考えた。
ところがいろいろな問題が発生(*1)。なんとか回避したが、最後にインタプリタのバグ？が判明し諦めた。
(根本は CP/M68KのCにまで遡る。これを回避するのは難しい)
・バグの発見までの経緯
さまざまな問題を開始したが、どうしてもmlisp.bが動かない。
コンパイル途中のTREEを見ると、P_LISTが -0 になっていた? ソースでは $80000000 なのに。
! *--1
*-OP75
*-OP43
! *-OP43
! ! *-OP43
! ! ! *-NIL
! ! ! *-P_LIST
! ! ! *--0
! ! *-B
! ! *-2
そこでテストコードを作成しコンパイルしてみた
===================
GET "LIBHDR"
MANIFEST $(
X =#X7FFFFFFF
Y =#X80000000
Z =#X80000001
$)
LET START() BE
$(
WRITEF("%X8 %X8 %X8*N", X, Y, Z)
WRITEF("%N %N %N*N", X, Y, Z)
$)
===================
OCODEではなぜか #X80000000が -00 になっている
STACK 2 JUMP L2 ENTRY 5 L1 83 84 65 82 84 SAVE 2 STACK 4 LSTR
12 37 88 56 32 37 88 56 32 37 88 56 10 LN 2147483647 LN -00 LN
-2147483647 LG 76 RTAP 2 STACK 4 LSTR 9 37 78 32 37 78 32 37 78
10 LN 2147483647 LN -00 LN -2147483647 LG 76 RTAP 2 RTRN ENDPROC
0 STACK 2 LAB L2 STORE GLOBAL 1 1 L1
INTCODEは 0 になっている
JL2
$ 1 LL499 SP4 L2147483647 SP5 L0 SP6 L-2147483647 SP7 LIG76 K2 LL498 SP/
4 L2147483647 SP5 L0 SP6 L-2147483647 SP7 LIG76 K2 X4 2
499 C12 C37 C88 C56 C32 C37 C88 C56 C32 C37 C88 C56 C10 498 C9 C37 C78 /
C32 C37 C78 C32 C37 C78 C10
G1L1
Z
実行してみると
===========================
C>icint test.int
INTCODE SYSTEM ENTERED
PROGRAM SIZE = 644
7FFFFFFF 00000000 80000001
2147483647 0 -2147483647
EXECUTION CYCLES = 2295, CODE = 0
============================
どうやら0x80000000を表示できないらしい。
今度はCでテストコードを実行
===test2.c======================
#include <stdio.h>
int main()
{
long x = 0x80000000L;
int y = 1;
int z = 0;
printf("%08lx\n", x);
printf("%08lx\n", -x);
printf("%08lx\n", x / y);
printf("%08lx\n", x / z);
printf("%d\n", y / z);
}
C>test2
80000000 ==> わかる
80000000 ==> わからないこともない
00000000 ==> 1で割っているのに？ わからない
80000000 ==> 0で割っているのに？ わからない
Exception $05 at user address $000082A8. Aborted. ==> わかる(当然)
===test2.s======
.globl __iob
.globl _main
.text
_main:
~~main:
~_EnD__=8
link R14,#-12
~x=-4
*line 5
move.l #$80000000,-4(R14) long x = 0x80000000L;
~y=-6
*line 6
move #1,-6(R14) int y = 1;
~z=-8
*line 7
clr -8(R14) int z = 0;
*line 8
move.l -4(R14),(sp) printf("%08lx\n", x); ==> 80000000
move.l #L2,-(sp)
jsr _printf
addq.l #4,sp
*line 9
move.l -4(R14),R0 printf("%08lx\n", -x); ==> 80000000
neg.l R0
move.l R0,(sp)
move.l #L3,-(sp)
jsr _printf
addq.l #4,sp
*line 10
move -6(R14),R0 printf("%08lx\n", x / y); ==> 00000000
ext.l R0
move.l R0,-(sp)
move.l -4(R14),-(sp)
jsr ldiv
addq.l #8,sp
move.l R0,(sp)
move.l #L4,-(sp)
jsr _printf
addq.l #4,sp
*line 11
move -8(R14),R0 printf("%08lx\n", x / z); ==> 80000000
ext.l R0
move.l R0,-(sp)
move.l -4(R14),-(sp)
jsr ldiv
addq.l #8,sp
move.l R0,(sp)
move.l #L5,-(sp)
jsr _printf
addq.l #4,sp
*line 12
move -6(R14),R0 printf("%d\n", y / z); ==> Exception $05
ext.l R0
divs -8(R14),R0
move R0,(sp)
move.l #L6,-(sp)
jsr _printf
addq.l #4,sp
L1:
unlk R14
rts
.data
L2:
.dc.b $25,$30,$38,$6C,$78,$A,$0
L3:
.dc.b $25,$30,$38,$6C,$78,$A,$0
L4:
.dc.b $25,$30,$38,$6C,$78,$A,$0
L5:
.dc.b $25,$30,$38,$6C,$78,$A,$0
L6:
.dc.b $25,$64,$A,$0
=================================================
CP/MのDDTで確認したところ、
CP/M68KのCの32ビットの割り算ルーチン(_ldiv)にいろいろ癖があることが判明。
除数が0だと(エラーではなく)0x80000000になる。
被除数が16ビット内だと divuを使うが、それ以上だとソフトウエアでの除算
被除数が0x80000000の場合への考慮がない。
(被除数が負の場合はnegしているが0x80000000の場合はnegしても0x80000000)
---$4(A7)/$8(A7) -> D1/D3 ----------------------------
---D1が 0x80000000の場合は、neg.l D1によりD1= となる。
_ldiv:
ldiv:
0000AD7A movea.l D3,A0
0000AD7C move.l $4(A7),D1 被除数をD1へ
0000AD80 bge $AD84 被除数が0または正なら分岐
0000AD82 neg.l D1 負の場合は正の数にする
0000AD84 move.l $8(A7),D3 除数をD3へ
0000AD88 bgt $AD98 除数が正なら分岐
0000AD8A blt $AD96 除数が負なら分岐
0000AD8C move.l #$80000000,D0 ここに来るのは除数が0 返り値が$80000000
0000AD92 move.l D0,D1
0000AD94 bra $ADE4
0000AD96 neg.l D3 除数を正の数にする
0000AD98 moveq.l #$0,D0
0000AD9A cmp.l D1,D3 被除数と除数を比較
0000AD9C blt $ADA6 D1>D3(被除数>除数)なら分岐
0000AD9E bgt $ADD2 D1<D3(被除数<除数)なら分岐
0000ADA0 moveq.l #$1,D0 D1=D3(被除数=除数)なら 商=1 余り=0
0000ADA2 moveq.l #$0,D1
0000ADA4 bra $ADD2 符号調整
0000ADA6 moveq.l #$2,D2
0000ADA8 cmp.l #$10000,D1
0000ADAE bge $ADBC 被除数が>=#$10000なら分岐(ソフトウエアで割り算)
0000ADB0 divu D3,D1 d1.l / d3.w => d1.h ... d1.l
0000ADB2 move.w D1,D0 d0=余り
0000ADB4 clr.w D1
0000ADB6 swap D1 d1=商
0000ADB8 bra $ADD2 符号調整
0000ADBA add.l D2,D2
0000ADBC add.l D3,D3
0000ADBE cmp.l D3,D1
0000ADC0 bcc $ADBA 被除数<除数 になるまで除数を左シフトしながらループ
0000ADC2 bra $ADCC
0000ADC4 cmp.l D3,D1
0000ADC6 bcs $ADCC D1<D3ならブランチ
0000ADC8 or.l D2,D0 商はD0に出来てくる
0000ADCA sub.l D3,D1 D1=D1-D3
0000ADCC lsr.l #1,D3 除数を右シフト
0000ADCE lsr.l #1,D2
0000ADD0 bne $ADC4
0000ADD2 tst.w $4(A7) 被除数が
0000ADD6 bpl $ADDC 正ならブランチ
0000ADD8 neg.l D0 負の場合は、商も余りも符号反転
0000ADDA neg.l D1
0000ADDC tst.w $8(A7) 除数が
0000ADE0 bpl $ADE4 正ならブランチ
0000ADE2 neg.l D0 負なら商を符号反転
0000ADE4 move.l D1,$B294 ._ldivr
0000ADEA move.l A0,D3
0000ADEC rts
商と余りの符号は以下のようになる
正 / 正 = 正 ... 正
負 / 正 = 負 ... 負
正 / 負 = 負 ... 正
負 / 負 = 正 ... 負
・結論
コンパイラで0x80000000が表示出来ないのはlongの除算の扱いがおかしなためと思われる。
(BCPLの印字のライブラリでも以下のようになっており、N=0x80000000では問題が起きる)
=================
AND WRITED(N, D) BE
$(1 LET T = VEC 20
AND I, K = 0, N
TEST N<0 THEN D := D-1 ELSE K := -N
T!I, K, I := K REM 10, K/10, I+1 REPEATUNTIL K=0
FOR J = I+1 TO D DO WRCH('*S')
IF N<0 DO WRCH('-')
FOR J = I-1 TO 0 BY -1 DO WRCH('0'-T!J) $)1
AND WRITEN(N) BE WRITED(N, 0)
=================
では、CP/M68KのCの問題かといえば、(CP/M68KのCはANSIではないけれど)
ANSI Cであっても long は <=−2,147,483,647 とのこと。
なので、−2,147,483,647まで扱えれば、-2,147,483,648が扱えなくても文句は言えない。
・大本の原因
結局 -2,147,483,648が表示出来ると想定しているインタプリタのバグと言えるかも。。。
(*1)
[1]syntaxエラー
BCPLは歴史的にuppercaseが使用されるが該当プログラムはlowercaseとなっている。
ソースを置換することも検討した。(cat mlisp.b | tr [a-z] [A-Z] > mlisp2.b)
ところがunderscore も使用されている。これを受け入れるようにするためsyn.bの変更が必要となった。
[2]%演算子
元のコンパイラでGETBYTE, PUTBYTEという関数があったが、mlisp.bでは%演算子が使用されている。
GETBYTE(x,y) は x%y, PUTBYTE(x,y,z) は x%y = zとなる。
[3]領域不足
コンパイルすると「PROGRAM TOO LARGE」というエラーが出る。
OPTIONSでL7500としている(もともと設定されていた)が足らない。L9000まで増加すればエラーは出なくなった。
コンパイル結果を見ると TREE SIZE 8499 となっていた。
[4]領域不足
コンパイルすると「TOO MANY GLOBALS」というエラーが出る。
trn.bを見ると100に設定されている。これでは足りないようだ。
[5]ライブラリ関数不足
NAME NOT DECLAREDが出る。RDARGS, STR2NUMB, GETVEC, FREEVECがない。
GETVECやFREEVECもCのmallocを使いたいところであるが、
intcodeインタプリタ方式では簡単に追加出来ない
X(EXECUTEOPERATIONS)に割り振って、LIBHDRで名前定義して、iclib.iで連携することが必要。
実はINTCODE_documentaion.pdfではX1(A:=loc(A))〜X27(output)なのに、
icint.cではX1(A:=loc(A))〜X39(output)、さらにiclib.iではX41(REWIND)まである。
(LIBHDRにはGLOBAL変数としてREWINDが用意されているのだが)
要するにintcodeには共通規格があるわけでなく、それぞれの処理系でインタプリタと一緒に
提供されるもののようだ。