課題 2

• 関数呼び出し機構(返り値無し)を導入しよう

• for 文などを導入しよう
• 複雑な式を処理しよう (オプション課題)

今回も、問題の意味が取りづらいところが多いでしょうが、 良くわからないところは早めに質問してください。 加筆していきますので。

あと、scheme 演習も最後なので、感想をいろいろ書いてくれるとうれしいです。 来年度は、scheme 演習はなくなるんですが、他の演習などの参考にもしたいですし。 それから、2000年度アンケートにも答えておいてください。

オプション課題に関しては、余力のある人だけが解いてくれればOKです。 といっても、それほど難しくないので、多くの人に解いて欲しいところです。 また、課題提出にあたっては、オプション課題を解くつもりの人も、 他の課題が出来た時点で提出してもらって、 オプション課題は追加提出(revised)の形で提出してくれてOKです(基本的に 早めの提出も評価項目に加えているので)。

(def-func 関数名  文)

さて、プログラムは 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 (....)
          (....))))

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))

(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)))))

(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)))))

       (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)))

一応、入力プログラム例と、 変換例を示しておきます。

加えて、ヒント(誘導)をつけてみました。