プログラミング言語意味論 レポート

1. （main 関数を持つプログラム）
   

   プリント第 4 章

   IO モナドと 4 章で紹介している関数を利用して次のようなプログラム（①〜③の 3 つの小問のうち 2 つ以上）を作成せよ。 各問の出力例は、次の入力テキストに対する出力である。

   Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do
   eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad
   minim veniam, quis nostrud exercitation ullamco laboris nisi ut
   aliquip ex ea commodo consequat. Duis aute irure dolor in
   reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla
   pariatur. Excepteur sint occaecat cupidatat non proident, sunt in
   culpa qui officia deserunt mollit anim id est laborum.
   

   ヒント: getLine を使うよりも、getContents を、lines, unlines, words, unwords などと組み合せて使うほうが簡単である。つまり、

   -- 補助関数 foo （実際は適切な名前をつけること）の定義
   -- lines, unlines, words, unwords などを使う
   foo source = … 
   
   main = do source <- getContents
             putStr (foo source)
   

   というカタチで定義する。

   1. 入力文字列を単語毎（ごと） に大文字と小文字に変換して出力する。

      出力例:

      lorem LOREM ipsum IPSUM dolor DOLOR sit SIT amet, AMET, consectetur CONSECTETUR adipiscing ADIPISCING elit, ELIT, sed SED do DO
      eiusmod EIUSMOD tempor TEMPOR incididunt INCIDIDUNT ut UT labore LABORE et ET dolore DOLORE magna MAGNA aliqua. ALIQUA. ut UT enim ENIM ad AD
      minim MINIM veniam, VENIAM, quis QUIS nostrud NOSTRUD exercitation EXERCITATION ullamco ULLAMCO laboris LABORIS nisi NISI ut UT
      aliquip ALIQUIP ex EX ea EA commodo COMMODO consequat. CONSEQUAT. duis DUIS aute AUTE irure IRURE dolor DOLOR in IN
      reprehenderit REPREHENDERIT in IN voluptate VOLUPTATE velit VELIT esse ESSE cillum CILLUM dolore DOLORE eu EU fugiat FUGIAT nulla NULLA
      pariatur. PARIATUR. excepteur EXCEPTEUR sint SINT occaecat OCCAECAT cupidatat CUPIDATAT non NON proident, PROIDENT, sunt SUNT in IN
      culpa CULPA qui QUI officia OFFICIA deserunt DESERUNT mollit MOLLIT anim ANIM id ID est EST laborum. LABORUM.
      

   2. 入力文字列中の各行の単語数を行の最後につけて出力する。

      出力例:

      Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do 10 
      eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad 12
      minim veniam, quis nostrud exercitation ullamco laboris nisi ut 9
      aliquip ex ea commodo consequat. Duis aute irure dolor in 10
      reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla 10
      pariatur. Excepteur sint occaecat cupidatat non proident, sunt in 9
      culpa qui officia deserunt mollit anim id est laborum. 9
      

   3. 入力文字列中の各行の最初と最後の単語のみを出力する。

      出力例:

      Lorem do
      eiusmod ad
      minim ut
      aliquip in
      reprehenderit nulla
      pariatur. in
      culpa laborum.
      

2. （命令型言語の意味）

   次の C の関数①〜②とほぼ同等な Haskell の関数を（モナドを用いて）定義せよ。

   • 「ほぼ」というのは整数の精度などに起因する違いなどは除く、という程度の意味である。
   • Util コンパイラーを使って良い。 その場合は、用いた Util のソースコードも示すこと。
     • Util コンパイラー
     • Blockly for Util
   • ハンドコーディング（ツールを使わずに自分の手でプログラムを作成すること）しても良い。 モナドを明示的に使わなくてもよい。 その場合は、ほぼ同等と考える何らかの根拠を記すこと（ただし、 いくつかの引数で試して同じだから、という根拠では弱い）。

   1. プリント第 5 章 問 5.3.2 - 1

      int foo(int n) {
          int i = 1, j = 1;
          while (i < n) {
              i = i + j;
              j = i - j;
          }
          return i;
      }
      

   2. プリント第 6 章 問 6.2.1

      int hoge(int n) {
          int i = 1, sum = 0;
          while (i <= n) {
              sum = sum + i;
              if (sum > 21) {
                  sum = 0; 
                  break;
              }
              i = i + 1;
          }
          return sum;
      }
      

3. （CPS への変換）

   プリント第 7 章 問 7.3.1

   hanoiCPS にならって、CPS を使って次の関数（sierpinski）を 「ボタンをクリックしたら、一つの線分を表示する」というバージョンに書き換えよ。

   Sierpinski.html （Sierpinski.js）

   ヒント: 線分を表示する箇所を含む forward, sierpinski, zig, zag を CPS に変換する必要がある。turnLeft, turnRight については、 （この問題では） CPS にする必要はない。

   参考にするプログラム: Hanoi0.html, Hanoi0.js, Hanoi.html, Hanoi.js,
   Fib0.html, Fib0.js Fib.html, Fib.js

チャレンジ問題（ボーナス問題）

4. (Prolog)

   Prolog の プリント中のサンプルプログラムを元にして、 日本史や世界史、あるいは神話・物語の中の有名な家系を Prolog プログラムにし、 実行例を作成せよ。

   • Blockly for Prolog （右上「サンプル」から選択してください。）
   • Try Prolog
   • パソコン上の処理系を使用したい場合は、 SWI-Prolog のホームページから SWI Prolog をインストールせよ （香川大学内のミラー）。

5. (Scheme)

   Scheme 言語をプリントで自習し、 プリント中のサンプルプログラム以外の call/cc (call-with-current-continuation) の使用例を WWW などで探して、 できれば自分なりのアレンジを加えよ。

   • Blockly for Scheme （右上「サンプル」から選択してください。）
   • Try BiwaScheme
   • パソコン上の処理系を使用したい場合は、 MIT/GNU Scheme のホームページから MIT/GNU Scheme をインストールせよ （香川大学内のミラー）。

6. (Haskell)

   （授業プリント中のサンプルプログラム以外の）Haskell の遅延評価 (lazy evaluation) を有効に活用したプログラムの例を WWW などで探して、できれば自分なりのアレンジを加えよ。

• Blockly for Haskell （右上「サンプル」から選択してください。）
• Try Haste

解答上の注意ほか

以上の解答をできるだけ短く簡潔におさめて下さい。 Word などで作成し PDF に変換してください。 手書きでもかまいません。（その場合、スキャンして PDF にしてください。）
いずれにしても、綴じしろとして、余白を上下左右 15mm 以上取るようにしてください。

提出〆切は、2 月 18 日（木）の 18:00 です。 ファイルアップロードのページよりアップロードしてください。

B4/M2 など上記の締切までに提出するのが難しい人は、事前にメールで連絡を下さい。ただし、 事務への成績の提出締切が 2/24 ですので、それまでに提出してください。 その場合でも、2/18 の時点でできたところまで、部分提出してもらうことが望ましいです。