課題 1

課題のプログラムですが、少し間違いが記載されていたので訂正しました。具体的には、MOVFW,MOVWF を逆に記述している個所と、第 2 引数を忘れていた個所を付け加えました。home page とプログラムソース双方に変更があります。 12/5 PM4:00 前後に更新したので、(a) の人は、テキスト、プログラムを新しいものに合わせてください。

まずは事務連絡。

提出方法は、こちらを見てください。課題の提出内容ですが、皆さんがつくってくれた部分のプログラムと、プログラムの動作原理などの解説をつけて送ってください。実験のレポートなどと同様のものだと思ってくれてOKです。あと、難易度に関する感想もお願いします。

期限ですが、この通りです。といっても、この期限はきつめに設定してありますので、皆さんの多くが期限に間に合わないかも知れません。そういう場合は、ここを見て、遅れるよ mail を気楽に送ってください。期限をきつめに設定しているのは、最初の期限で皆さんの状況をみてヒントを出すつもりだからです。当然、期限に間に合った人は相応の評価します。「オリジナリティ」も高いでしょうから。質問は、mail でも掲示板でも受け付けます。

さて、課題に入りましょう。

とある実験で皆さんが PIC 用のアセンブリ言語でプログラムを書いているのを見て、僕はこんなことは人がやることではない、機械にやらせることだと思いました。そう、プログラミング言語で書いたプログラムをアセンブリ言語に変換するのは、コンパイラの仕事です。機械の仕事を人が奪ってはいけません。

ということで、簡単な言語用のコンパイラもどきを作ってみることにします。とはいえ、みなさんにいきなり作ってもらうのは大変なので、結構僕が作ってしまいました。皆さんは、動作を理解しながら残りの部品を作って、完成品にしてください。未完成プログラムは、ここにあります。ちなみに、僕が書いた完成プログラムは(サンプル実行例を除けば) 150 行くらいで、そのうち 120 行ぐらいを公開しています。ということで安心してください。それから、バグを見つけたら報告してください。

まずは、簡単な式をどうすればよいか考えることにしました。プログラミング言語の文面に登場するのは、

大域変数: x, y, z など
即値: 1, 2, 3 など(但し、制約から 0 以上 255 以下とする)
+, -, and, or 演算を用いた式(但し、入れ子状の式はないとする)
つまり、x や 3 や (+ x 3 2) とか (都合で前置記法を利用)

です。一方、対象の機械語(PIC16F8X)では、以下の命令を使うことにします。

定数 load 命令: {label} MOVLW val
val の値を、 W レジスタに書き込む
load 命令: {label} MOVF label, 0
label で指定された address の値を、W レジスタに書き込む。
訂正: 以前 MOVWF と書いてましたが訂正しました。
+ 命令: {label} ADDLW val
W レジスタの値に、val で指定された即値を加える。
+ 命令: {label} ADDWF label 0
W レジスタの値に、label で指定されたアドレスの値を加える。
- 命令: + 同様に SUBLW, SUBWF が存在する。但し、それぞれ即値／アドレス値から W レジスタを引いた値を W レジスタに格納することに注意
and 命令: ANDLW, ANDWF が存在。
or 命令: IORLW, IORWF が存在。
not 命令: COMF label 0
label でしていされたアドレスの値を W レジスタに格納

となっています。

さて、大域変数 x, y がそれぞれ address x, y に格納されているとして、 (+ 1 x y 3) を計算して、その結果を W レジスタに置くためにはどうすればいいでしょう？多分、

MOVLW 1   ; 始めに即値 1  を W レジスタにおいて、
ADDWF x 0 ; W レジスタにアドレス x の中身を足しこんで、
ADDWF y 0 ; W レジスタにアドレス y の中身を足しこんで、
ADDLW 3   ; W レジスタに即値 3 を足しこむ

としてやればいいはずです。

ということで、入れ子がない式(の形をした S 式)を与えたら、「対応する式の結果を W レジスタに配置してくれるアセンブリコード」を出力するプログラム trans-simple-expr を作りましょう。こんな感じ。足りない関数は自分で作ってください。あくまでも、プログラムの形をしたデータを扱っていることに注意してください。

;;; trans-simple-expr
;;; 式(入れ子なし)を与えると、
;;; 結果を W レジスタにおくためのアセンブリコード(list形式)を出力する関数
;;; ex.
;;; (trans-simple-expr '4) => ((MOVLW 4))
;;; (trans-simple-expr 'x) => ((MOVF x 0))
;;;       訂正: MOVWF-> MOVF 
;;;
;;; (trans-simple-expr '(+ 1 x y 3)) 
;;;  => ((MOVLW 1) (ADDWF x 0) (ADDWF y 0) (ADDLW 3))
;;;
;;; (trans-simple-expr '(- 1 x y 3)) 
;;;  => ((MOVF x 0) (ADDWF y 0) (ADDLW 3) (SUBLW 1)) ; (- 1 (+ x y 3)) を行う
;;;       訂正: MOVWF-> MOVF 
;;;
;;; (trans-simple-expr '(and x y 3))
;;;  => ((MOVF x 0) (ANDWF y 0) (ANDLW 3))
;;;       訂正: MOVWF-> MOVF 
;;; (trans-simple-expr '(or x y 3))
;;;  => ((MOVF x 0) (IORWF y 0) (IORLW 3))
;;;       訂正: MOVWF-> MOVF 
;;; (trans-simple-expr '(not x))
;;;  => ((COMF x 0))
;;;
;;; ヒント:
;;; 
;;; まずは式についてですが、"変数"とはシンボルのことです。即値とは整数のことです。
;;; また、演算子ですが、それぞれ  +, -, and, or  という"シンボル"です。
;;; 
;;; 演算子付の式を変換するにあたっては、+,and, or については、
;;; 先頭要素を(MOV??) してから、後続部を(AND??)などすればOKです。リスト操作を頑張りましょう。
;;; - については、例をみながら考えてみましょう。

(define (trans-simple-expr expr)
  (cond ((number? expr) (list (trans-expr-num expr)))      ; 即値の場合
        ((symbol? expr) (list (trans-expr-var expr)))      ; 変数そのものの場合
        ((eq? (car expr) '+) (trans-add-expr (cdr expr)))  ; (+ ...) な場合
        ((eq? (car expr) '-) (trans-sub-expr (cdr expr)))  ; (- ...) な場合
        ((eq? (car expr) 'and) (trans-and-expr (cdr expr))); (and ...) な場合
        ((eq? (car expr) 'or) (trans-or-expr (cdr expr)))  ; (or ...) な場合
        ((eq? (car expr) 'not) (trans-not-expr (cdr expr))); (not ...) な場合
        (else (error 'trans-simple-expr                    ; しらないやつの場合
                     "receives an unknown operator symbol."))))

(define (trans-expr-num num) (list 'MOVLW num))
(define (trans-expr-var var) (list 'MOVF var 0))
;;;       訂正: MOVWF-> MOVF 

(define (trans-add-expr expr) 'NOT-IMPLEMENTED-YET) ; 完成させましょう。
(define (trans-sub-expr expr) 'NOT-IMPLEMENTED-YET)
(define (trans-and-expr expr) 'NOT-IMPLEMENTED-YET)
(define (trans-or-expr expr)  'NOT-IMPLEMENTED-YET)

(define (trans-not-expr expr)
  (if (symbol? (car expr))
      (list (list 'COMF (car expr) 0))
      (error 'trans-not-expr "receives only variables.")))

というわけで、サンプル例を実行して確かめてみましょう。

(trans-simple-expr '(+ 1 x y 3)) 
(trans-simple-expr '(- 1 x y 3))
(trans-simple-expr '(and x y 3))
(trans-simple-expr '(or x y 3))
(trans-simple-expr '(not x))

上手く動きました? 素晴らしい。

さて、式を処理できたので、今度は文を幾つか作ってみましょう。とはいえ、ここは半分以上こちらで作ってありますので心配しないでください。

導入するのは、

代入文: (:= 変数式)
if 文: (if 式 else文 then文)
while 文: (while 式文)
複文: (begin 文 ... 文)

だけ。if 文と while 文は、式の値が 0 以外(真)か 0 (偽)かで分かれるものとします。

プログラムは、こんな感じで記述できます。以下は start から end -1 までを足し合わせるプログラム。括弧だらけなので lisp っぽく見えますが、中身は C と変わりません。


(begin
 (:= start 3)
 (:= end  23) 
 (:= result 0)
 (while (- end start)
   (begin 
    (:= result (+ result start))
    (:= start (+ start 1)))))

まずは、各文の形に応じて処理をするプログラムを書きましょう。目指すのは、「文の形をしたリスト構造を渡されたら」「対応するアセンブリコード (list 状)」を返すプログラム trans-stmt です。

;;; trans-stmt
;;; 式を変換して対応するアセンブリコードを出力する関数
;;;
;;; とはいえ、実体は、書く形に応じて個々の関数に振り分けるだけ

(define (trans-stmt stmt)
  (cond ((eq? (car stmt) ':=)                             ; 代入文の場合
         (trans-assign-stmt (cadr stmt) (caddr stmt)))
        ((eq? (car stmt) 'if)                             ; if 文の場合
         (trans-if-stmt (cadr stmt) (caddr stmt) (cadddr stmt)))
        ((eq? (car stmt) 'while)                          ; while 文の場合
         (trans-while-stmt (cadr stmt) (caddr stmt)))
        ((eq? (car stmt) 'begin)                          ; 複文の場合
         (trans-stmts (cdr stmt)))
        (else                                             ; 知らないものの場合
         (error 'trams-stmt "Unknown statement."))))

最終的には、こんな感じで利用します。

(trans-stmt
 '(begin
    (:= start 3)
    (:= end  20) 
    (:= result 0)
    (while (- end start)
	   (begin 
	     (:= result (+ result start))
	     (:= start (+ start 1))))))
 ==>
((MOVLW 3)
 (MOVWF start)  ;;;       訂正: MOVFW-> MOVWF 
 (MOVLW 20)
 (MOVWF end)    ;;;       訂正: MOVFW-> MOVWF 
 (MOVLW 0)
 (MOVWF result)  ;;;       訂正: MOVFW-> MOVWF 
 g856
 (MOVF start 0) ;;;       訂正: MOVWF-> MOVF 
 (SUBWF end 0)
 (BTFSC STATUS 2)  ; 当初、僕は BTFSS と間違えていた
 (GOTO g857)
 (MOVF result 0) ;;;       訂正: MOVWF-> MOVF 
 (ADDWF start 0)
 (MOVWF result)
 (MOVF start 0)  ;;;       訂正: MOVWF-> MOVF 
 (ADDLW 1)
 (MOVWF start)    ;;;       訂正: MOVFW-> MOVWF 
 (GOTO g856)
 g857)

さて、代入文を行うプログラムは難しくありません。式を実行した結果を W レジスタに格納するまでは出来ているので、あとは、

store 命令: {label} MOVWF label
W レジスタの値を、label で指定された address に書き込む訂正: MOVFW-> MOVWF

で書き込むだけです。ということで、

;;; trans-assign-stmt
;;; (trans-assign-stmt var expr) は expr を計算して、var に代入
            
(define (trans-assign-stmt var expr)
  (append (trans-simple-expr expr)      ; ここまで expr が Wレジスタに入り
          (list (list 'MOVWF var))))    ; ここで、var に書き込み
       訂正: MOVFW-> MOVWF

でおしまい。

次は複文ですが、これも、各文を再帰的に変換して、結果のコードをつなげるだけです。

;;; trans-stmts は複数の文を処理

(define (trans-stmts stmts)                               ; 複文の場合
  (if (null? stmts)
      (list)
      (append (trans-stmt (car stmts))                    ; リストとリストを
              (trans-stmts (cdr stmts)))))                ; 連結しましょう

おしまい。

次は、少し面倒な if 文です。if 文を実現するために、以下の機械語命令を利用することにしました。

jump 命令: {label} GOTO label
if NotZero 命令: {label} BTFSC STATUS 2
Zero Flag が立っていない場合、次の行をスキップする。
(当初、僕はこの命令を BTFSS と書いていました。大きな勘違い。指摘してくれた池内君に感謝。というわけでお詫びして訂正です。で、解答については、本来 BTFSC を使うべきところを BTFSS にしていても OK とします。もちろん正しくなっていてもOK)

例えば、 (if expr then-stmt else-stmt) を実現するためには、以下のようなコード列を準備すればOKです。

...EXPR-CODES...   ; expr を W レジスタに配置するコード群
                   ; 実は、Zero Flag も設定してくれている
BTFSC STATUS 2
GOTO ELSE-LABEL
...THEN-CODES...   ; then-stmt を変換したコード群
GOTO EXIT-LABEL
ELSE-LABEL
...ELSE-CODES...   ; else-stmt を変換したコード群
EXIT-LABEL

というわけで、こんな関数を作ってみました。 (gensym) というのは新規の symbol を生成するための関数で、できあがった label を label 用に使っています。

;;; trans-if-stmt
;;; (trans-if-stmt expr then-stmt else-stmt) は
;;; expr の結果が 0  以外なら then を  0  なら else を実行する
          
(define (trans-if-stmt expr then-stmt else-stmt)
  (trans-if-stmt-aux expr then-stmt else-stmt
                     (gensym)  ; else-label 用の新規 symbol の生成
                     (gensym)  ; exit-label 用の新規 symbol の生成
                     ))
                     
(define (trans-if-stmt-aux expr then-stmt else-stmt else-label exit-label)
  (append (trans-simple-expr expr)        ; expr を評価し
          (list (list 'BTFSC 'STATUS 2)   ; Zero-Flag  がたっていなければ then
                (list 'GOTO else-label))  ; たっていれば、else へ goto
          (trans-stmt then-stmt)          ; then を変換したもの
          (list (list 'GOTO exit-label)   ; then が終われば exit へ goto
                else-label)               ; else はここから
          (trans-stmt else-stmt)          ; else を変換したもの
          (list exit-label)))             ; if 文終了

で、皆さんは、if 文を参考にして、while 文を作ってみましょう。参考までに述べておくと、(while expr stmt) であれば、以下のようなコード列にしてやれば良いわけです。

INIT-LABLE
...EXPR-CODES...   ; expr を W レジスタに配置するコード群
                   ; 実は、Zero Flag も設定してくれている
BTFSC STATUS 2
GOTO EXIT-LABEL
...STMT-CODES...   ; stmt を変換したコード群
GOTO INIT-LABEL    ; 最初に戻る
EXIT-LABEL

さあ、残りを埋めてみましょう。

;;; trans-while-stmt
;;; (trans-while-stmt expr stmt) は
;;; expr を評価し、0  以外でならば繰り返し stmt を実行する
;;; ヒント:
;;; trans-if-stmt を理解できれば問題ないはず。
;;; 真似して作ってみましょう。

(define (trans-while-stmt expr stmt)
  (trans-while-stmt-aux expr stmt (gensym) (gensym)))

(define (trans-while-stmt-aux expr stmt init-label exit-label)
  'NOT-IMPLEMENTED-YET)  ; 完成させましょう。

さて、少し試してみましょう。

(trans-stmt
 '(begin
    (:= start 3)
    (:= end  20) 
    (:= result 0)
    (while (- end start)
           (begin 
             (:= result (+ result start))
             (:= start (+ start 1))))))
=> 前述どおり 

(trans-stmt
 '(begin
    (:= x 10)
    (:= y (+ x 12))
    (:= z (and x y))
    (if (- y x z)
        (while (- x z 2)
               (:= z (- z 1)))
        (:= z (+ x y z)))))
=> このとおり

最後に。「コンパイラもどき」と呼んでいることについて。あまりにやっていることが「そのまま」なので、「もどき」といってしまいました。

最近の普通の言語は、もっといろんな構文もありますし、関数呼び出しも出来ますし、局所変数だってありますし、ポインタも使えます。

それに、この「もどき」は出力コードも最適化されていない naive なコードが出力します。

でも、なんとなくプログラミング言語とアセンブリ言語の差が埋まったような気がしてくれると嬉しいです。

2000.12.5/ Tomio KAMADA: kamada@cs.kobe-u.ac.jp