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


  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 の関数を(モナドを用いて)定義せよ。

    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.htmlSierpinski.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、問5の Prolog, Scheme の例題を実際に実行してみることをお勧めします。

チャレンジ問題(ボーナス問題)

  1. (Prolog)

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

  2. (Scheme)

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

  3. (Haskell)

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


解答上の注意ほか

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

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

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


プログラミング言語特論のホームページ
Koji Kagawa