Christopher StracheyのGPM

GPMの続きだ.

二進化

例えば3を11, 6を110, 9を1001へのように十進数dを二進数bに変換したいとする.

d % 2の左に⌊d/2⌋の二進化したもを置けばよいが, 除算も剰余もなければ2を繰り返し引くしかない. とりあえずSchemeで書くと

(define (b x y)
 (if (< x 2)
  (if (= y 0) (list x)
   (append (b y 0) (list x)))
  (b (- x 2) (+ y 1))))

というわけで, GPMにすると

$def,b,<$$lt,~1,2;,
 $def,t,<$>~2<,
  $def,>~2<,<$b,>>~2<<,0;>>~1<;,
  $def,0,>~1<;;>;,
 $def,f,
  <$b,$1-,$1-,>~1<;;,$1+,>~2<;;>;;>;
$b,0,0;,$b,1,0;,$b,2,0;,$b,3,0;,$b,4,0;, => 0,1,10,11,100,
$b,5,0;,$b,6,0;,$b,7,0;,$b,8,0;,$b,9,0; 
=> 101,110,111,1000,1001

二項係数

Pascal三角形を思うえば, C_n,mは両端にある時, つまりm=0かm=nの時は1, それ以外は一段上の左(C_n-1,m)と右(C_n-1,m-1)の和 にすればよい.

$def,b,<$~2,
 $def,~2,<$+,$b,$1-,>~1<;,>~2<;,
  $b,$1-,>~1<;,$1-,>~2<;;;>;,
 $def,0,1;,$def,~1,1;;>;
$def,binom,<$bb,0,
 $def,bb,<$~1,
  $def,~1,<$b,>>~1<<,>~1<;,
  $bb,$1+,>~1<;;>;,
  $def,>~1<,1;;>;;>;
$b,4,0;,$b,4,1;,$b,4,2;,$b,4,3;,$b,4,4; => 1,4,6,4,1
$binom,3; => 1,3,3,1

上のbが二項係数で, $~2でmの値を見る. 下の方$def,0,1;はm=0の時, $def,~1,1;はm=nの時の値を返す. $def,~2, がその他の場合を計算する.

binomはPascal三角形のn段目を計算するもので, bbでmを0からnまで回している.

素数テスト

基本演算で定義した剰余を利用する. nの素数性はxを2から順に増やしながらnをxで割り剰余が0なら偽, x=nになったら真とする.

(define (isprime? n)
 (define (p x)
  (cond ((= x n) #t)
        ((= (modulo n x) 0) #f)
        (else (p (1+ x)))))
 (p 2))

従って, isprime?をp?と書くと

$def,p?,<$p,2,
 $def,p,<$~1,
  $def,~1,<$$r,>>~1<<,>~1<;,
   $def,$r,>>~1<<,>~1<;,
    <$p,$1+,>>~1<<;;>;,
   $def,0,f;;>;,
  $def,>~1<,t;;>;;>;
$p?,2;,$p?,3;,$p?,4;,$p?,5;, => t,t,f,t,
$p?,6;,$p?,7;,$p?,8;,$p?,9; => f,t,f,f

p?の定義はまず$p,2,と(p 2)を実行し, すぐにpの定義が続く. $def,p,<$~1, の~1はSchemeのプログラムのxである. その次の行の$def,~1,はelseの部分. 一番下の 行の$def,$gt;~1<<,の~1はn, すなわちx=nならtという定義がこの行だ.

else部分に戻ると$$r,>>~1<<,>~1<,;,とあるが, ここがnをxで割った剰余を計算するところで, >>~1<<がn, >~1<がxである. その剰余でマクロ呼出しし, 下の方の$def,0,f;が割り切れた場合は偽と定義する. elseの定義は$def,の後でもう一度剰余を計算する. やることは$p,$1+,x;である.

tarai関数

竹内郁雄君の発案したtarai関数はGPMでやってみるには都合がよい. tarai関数の定義は

(define (tarai x y z)
  (if (<= x y) y
  (tarai (tarai (- x 1) y z)
         (tarai (- y 1) z x)
         (tarai (- z 1) x y))))

で, (trai 4 2 0) とかやってみると, 盥まわしの様子が分かる. しかしz=0なので早速-1が現れて問題となる. $1-,0;は実行出来て-1になる. 基本関数のltの 引数の下が-1まで使えるようになっているのは, ここで使いたかったからである.

次は(<= x y). 基本関数にあったのはleではなく, ltであったが, もちろん(< y x)の形で使い, then部分とelse部分を交換して書いておく.

従ってtarai関数は

$def,tarai,<$$lt,~2,~1;,
 $def,f,~2;,
 $def,t,<$tarai,
  $tarai,$1-,>~1<;,>~2<,>~3<;,
  $tarai,$1-,>~2<;,>~3<,>~1<;,
  $tarai,$1-,>~3<;,>~1<,>~2<;;>;;>;
$tarai,4,3,2; => 4
$tarai,4,2,0; => 4

この辺でGPMの空白改行問題を説明しなければならない. StracheyのGPMの論文には, マクロ呼出しは評価の文字列に置き換わるがそれ以外は入力がそのまま出力されると書いてある. アセンブリ言語の前処理用としてはその通りであるが, tarai関数のマクロ定義をこのように整形しておくと実はうまく走らないのである.

(tarai 4 3 2)の実行され方を見ると, (<= 4 3) は #fなので(tarai (- 4 1) 3 2), (tarai (- 3 1) 2 4), (tarai (- 2 1) 4 3) つまり(tarai 3 3 2), (tarai 2 2 4), (tarai 1 4 3)をまず計算する. この3個はどれも(<= x y)なので, それぞれ3, 2, 4であり, 次に(tarai 3 2 4)を計算しなければならない.

これも(<= 3 2)ではないので, (tarai 2 2 4), (tarai 1 4 3), (tarai 3 3 2)を計算し, これらは直接終わるので(tarai 2 4 3)の計算に移り, (<= 2 4)だから4となるわけだ.

問題は

$tarai,
 3,
 2,
 4;

になった時に改行や空白が邪魔になることである. このtaraiの第1引数は`改行空白3', 第2引数は`改行空白2', 第3引数は`改行空白4'であり, これらが$1-に渡されてしまう.

そういう次第で, GPMの処理系では改行や空白は無視するようにしてあるが, この後で出て来る例題では改行や空白をそのまま使いたいものもあって, その辺は どう対処するのがよいか疑問である.

BCPLを設計したMartin RichardsはBGPMというGPM処理系を使っているそうだが, そのBGPMではバッククォート(`)をエスケープに使い, バッククォートから後その行の最後までと次の行から空白を無視する仕様になっているとそうだ.