個人用電卓のプログラミング

情報科学標準問題の1つにfactorialがある.

(define (factorial n)
  (if (= n 0) 1
      (* n (factorial (- n 1)))))

個人用電卓のプログラムでも, この程度のことはやってみたい. プログラム名としては「!」を使うことにしよう.

nがスタックトップにあるとき, これを複製し, 1を引き, !でfactorialをとり, *で掛ければよい. 問題はnが0の時には1を返す仕掛けを組み込むことである. 0と1以上の判定は, 符号を反転して負になれば元は≥1であったわけだ.

従ってプログラムはこうなる.

("_6_G1+5_"G"1-!*)!=
      0123456
            012345

このプログラムの開始時, nを複製し, 符号反転する. その上に-6を置き, ジャンプの準備をする. G命令で6文字右へ飛ぶ. プログラムの下のGの隣りから012...とあるのが飛び先で, 次のGの右の"まで行く. そこで複製し, 1を引き!でfactorialを再帰呼出しする. n-1のfactorialがとれて戻ってきたら, *で掛ける. 一方0だったら, Gではジャンプせず, n(つまり0)に1を足し, 返す値1を作る. 次に-5を2個積んでG命令でプログラムの終りまで飛ぶ. -5を2個置くのは, 上は飛び先, 下は負ジャンプを絶対ジャンプにするためである.

factorial 3の実行の様子は下の図の通り.



一番左はGからの相対位置. 次は命令. (3)から始まる列は最初の実行トレース. G命令で下へ飛ぶ. そのうち, !命令になると, 次に右の列の"からfactorialを再帰実行する.

3回目の再帰実行は, スタックが0の時で, 処理の流れが異る. つまりG命令でジャンプせず, 1を置いて(正しくは0に1を足して)飛び出す.

戻ると1つ左の最下行*に来, 1と1を掛け1にして飛び出す. また左の最下行*で1と2を掛け, 次の左で2と3を掛け, 結果は6になった.