アセンブラ短歌詠み初め

冬のプロシンで竹迫さんが紹介していたアセンブラ短歌をお正月ですし私も詠んでみました．私が一番得意なのは高校生のときに親しんだ6502です．6502はターミーネータでも使われていて，非常に強力なCPUです．

私は「アルゴリズムとして何か意味のあることをさせたい派」なので，適当な何かやるべきことを考えたいです．31バイトだとあまり難しいことはできないので，たとえば

ユークリッドの互除法で最大公約数をもとめる
アッカーマン関数とか竹内関数をもとめる
配列の合計とか平均をもとめる

とかです．プロシンで理科大の山口文彦先生がフィボナッチ数列をもとめるアセンブラ短歌を詠んでいたので，私もアッカーマン関数をもとめることにしました．

アセンブラ短歌を詠むプロセス

アセンブラ短歌を詠むプロセスは，詠み人により異なるのですが，私は次のようして詠みました．

機械語の資料を集めておく．機械語になったときの形が大事なため，最低限命令表は必須になります．
アセンブラの開発ができる環境を用意しておく．86系ならPC上でgdbを用意すれば開発できます．ハンドアセンブルもする必要がありますが，とりあえずアセンブラを通した方が間違いが少なくて，正しくアセンブルできるのではかどります．
実行環境も用意しておく，実機やエミュレータや実機のデバッガ上で動作を確認できるようにしておく必要があります．
一応は動く短いコードを書き．それをもとに57577の短歌の形に合わせていく．全体を吟味しながら作者個人の感性とテクニックで，少しずつ味わい深いものにしていく．

作った作品

作品名は「ミサカじゃないよ」です．コードは以下の通りです．

    
L0:                         ;; 5 // ack(x,y)=y+1 when x=0
       d0 03      BNE L1    ;; x!=0 goto L1
       c8         INY       ;; y=y+1
       98         TYA       ;; result is in a
       60         RTS

L1:                         ;; 7 // ack(x,y)=ack(x-1,1) when y=0
       98         TYA       ;; a=y, y=0?
       d0 04      BNE L2    ;; y!=0 goto L2
       c8         INY       ;; y=1
       ca         DEX       ;; x=x-1
       50 f4      BVC L0    ;; get ack(x-1,1)

L2:                         ;; 5 // ack(x-1, ack(x,y-1)) otherwise
       88         DEY       ;; *in
       C8         INY       ;; *in
       88         DEY       ;; y=y-1
       8a         TXA       ;; a=x
       48         PHA       ;; save x into stack

       20 04 06   JSR L0    ;; 7 // get ack(x,y-1)
       a8         TAY       ;; set y=ack(x,y-1)
       68         PLA       ;; recover x into a
       aa         TAX       ;; *in
       8a         TXA       ;; *in
       
       ca         DEX       ;; 7
       aa         TAX       ;; *in
       ca         DEX       ;; *in
       aa         TAX       ;; x=a
       ca         DEX       ;; x=x-1 
       50 e8      BVC L0    ;; get ack(x-1, ack(x,y-1))

バイト列はつぎのようになります．


   d0 03 c8 98 60
   98 d0 04 c8 ca 50 f4
   88 c8 88 8a 48
   20 04 06 a8 68 aa 8a
   ca aa ca aa ca 50 e1

この作品のアピールポイント

このプログラムの目的は，アッカーマン関数A(m,n)を計算することです．目的派としては欠かせないことです．全体の実行時間も長く，末尾再帰を除去してあるため，スタックの使用量も少ないです．どうしても除去できない再帰呼び出しは普通に行っており，全体として複雑な動作をしています．

作品名「ミサカじゃないよ」は，アッカーマン関数を何故か暗示しており，日本古来よりの「萌え文化」を大切にしたいのとちょっとした遊びごころで，少し萌えた感じで付けました．なお，アッカーマン関数はヴィルヘルム・アッカーマンというドイツの数学者が考案したそうです．3句，5句で韻も踏んでいます．

この作品のアセンブル方法と実行方法

アッカーマン関数A(m,n)を計算するとすると，mをXレジスタ，nをYレジスタにいれ，JSR命令で先頭番地（L0）をコールするとAレジスタに答えが入ります．アッカーマン関数なのでAに答えが入るようにすることにもこだわりました．A(3,3)まで求まります．それ以上はスタックが足りません．呼び出すときにYレジスタ，Xレジスタの順に設定してください．

私は6502の実機を一応は持っているのですが，お手軽なeasy6502というサイトでエミュレートが可能です．コードを入力して「Assemble」「Run」とすれば，Aレジスタに結果が返されます．アッカーマン関数なのでAに結果が入るところにもこだわりました．A(3,3）までは結果が求まりました．それ以上はスタックが足りませんでした．6502は常にブランチする命令を持っていないのですが，Xレジスタ，YレジスタはVフラグが変化しないので，ブランチ命令BVCは常にブランチするので，フラグクリア命令をさぼることができます．