今回も、問題の意味が取りづらいところが多いでしょうが、 良くわからないところは早めに質問してください。 加筆していきますので。
あと、scheme 演習も最後なので、感想をいろいろ書いてくれるとうれしいです。 来年度は、scheme 演習はなくなるんですが、他の演習などの参考にもしたいですし。 それから、2000年度アンケートにも答えておいてください。
オプション課題に関しては、余力のある人だけが解いてくれればOKです。 といっても、それほど難しくないので、多くの人に解いて欲しいところです。 また、課題提出にあたっては、オプション課題を解くつもりの人も、 他の課題が出来た時点で提出してもらって、 オプション課題は追加提出(revised)の形で提出してくれてOKです(基本的に 早めの提出も評価項目に加えているので)。
(def-func 関数名 文)という形をとることにします。複数の文を書きたい人は、 文のところを複文(begin ...) にしましょう。
さて、プログラムは def-func 文が複数並んだリストで与えられるものとします。 つまり、こんな感じ。
((def-func main (begin (if x (:= y 2) (return)) (call func1) (...)) (def-func func1 (begin (while y (begin (:= y (- y 1)) ....)) (....))) (def-func foo (begin (....) (....))))ということで、各 def-func 文を変換する trans-def-func と、 リスト状の複数のdef-func文に対して変換を行う trans-def-funcs があれば、プログラムを変換可能という事になります。
trans-def-funcが行うのは、以下のような変換です。さあ、それぞれ作ってみましょう。
(trans-def-func '(def-func func0 stmt)) => (func0 ; function を示す label ..... ; 以後、stmt を変換したもの ..... (RETURN)) (trans-def-funcs '((def-func func0 stmt0) (def-func func1 stmt1))) => (func0 ; func0 のlabel ..... ; 以後、stmt0 を変換したもの ..... (RETURN) func1 ; func1 の label ..... ; 以後、stmt1 を変換したもの ..... (RETURN))これだけでは、関数呼び出し出来ないので、call 文 (call 関数名) と RETURN 文 (return) を付け加えましょう。 trans-stmt を拡張して付け加えましょう。それぞれ、以下の様に変換されます。
(trans-stmt '(call func0)) => ((CALL func0)) (trans-stmt '(return)) => ((RETURN))
;;; (trans-stmt '(asm (BCF PORTB 0))) => ((BCF PORTB 0)) ;;; とできるように すこし拡張 (define (trans-stmt stmt) (cond .... ((eq? (car stmt) 'asm) (trans-asm-stmt (cdr stmt))) ...)) (define (trans-asm-stmt stmt) (list (car stmt)))
;;; (for (初期化文 条件式 ステップ文) 本体の文) (for ((:= i 0) ; 初期化に利用したい文 (- 10 i) ; ループを繰り返すための条件式(0以外はtrue、0はfalse) ; 不等号は導入してなかったので、変更しました。以下、同様 (:= i (+ i 1))) ; 各ステップ毎に実行する文 (:= result (+ result i))) ; for 文の body 部の文
for 文を作るのに、いきなり機械語レベルで考えても良いのですが、 ここでは少し違った方法を取りましょう。for 文はなくても、while 文はもう作ってあります。 以下の、while 文を含んだ複文は、先ほどの for 文と同じ役割をするはずです。
(begin (:= i 0) (while (- 10 i) (begin (:= result (+ result i)) (:= i (+ i 1)))))ということで、先ほどの例のように for 文から while文を含んだ複文に変換するexpand-for-stmt という関数を作ってみましょう。
(expand-for-stmt '(for ((:= i 0) (- 10 i) (:= i (+ i 1))) (:= result (+ result i)))) => (begin (:= i 0) (while (- 10 i) (begin (:= result (+ result i)) (:= i (+ i 1)))))で、この関数を利用すれば、for 文は、
(trans-stmt (expand-for-stmt stmt))とすればアセンブリ言語にまで変換出来るはずです。
実は、このように構文の幾つかは、文の形を変換すれば等価なもので代用出来るものがあります。 こういった構文は、文の変換規則をあたえてやるだけで、実は出来てしまうんです。 scheme をはじめとした Lisp の処理系では、マクロといわれる機能をつかって、 一般のプログラマが新たな構文を作って、登録することが出来るようになっています。
こちらからのサンプルとして、 プログラム例と 変換例をのせておきます。 こちらは、レポートにのせなくてもOKです。
入れ子状になった式を処理してみましょう。 このままでは処理ができないので、一時変数として大域変数 tmp0, tmp1, ... を利用することとします。
(+ (- (- x y) 2 (+ x y)) ; PIC で積演算を導入してないので、*を- 演算に訂正します (- (- x z) 3 (+ x z)) (+ y z) 5)という式があった場合、
(:= tmp0 (- x y)) ; 第 0 式の中の評価 tmp0, tmp1 を順次利用 (:= tmp1 (+ x y)) (:= tmp0 (- tmp0 2 tmp1)) ; 結果については、第 0 式は tmp0 に格納 (:= tmp1 (- x z)) ; 第 1 式の評価には、tmp0 が埋まっているので、tmp1 以降を利用 (:= tmp2 (+ x z)) (:= tmp1 (- tmp1 3 tmp2)) ; 結果については、第 1 式は tmp1 に格納 (:= tmp2 (+ y z)) ; 第 2 式の評価には、tmp0,tmp1 が埋まっているので、tmp2 以降を利用という文を処理した後、
(+ tmp0 tmp1 tmp2 5)を実行すると考えてもあまり問題はありません。 ということで、入れ子状の式については、まず上のような文と式に変換を施した後、アセンブリ言語 に変換してみましょう(やり方はいろいろなので、別の方法で実装しても構わないです。でも、一時変数を大量消費はしないように)。
ただし、 n 番目の一時変数(tmp0, tmp1, ...) は、(gen-tmp-var n) で作成できることとする。
(define (gen-tmp-var n) (let* ((str-n (number->string n)) (str-var (string-append "tmp" str-n))) (string->symbol str-var)))
加えて、ヒント(誘導)をつけてみました。
2001.01.10/ Tomio KAMADA: kamada@cs.kobe-u.ac.jp