******
解答例
******

.. comment
   
    .. _ex1-answer:

    .. admonition:: 課題1
       :class: exercise

       .. figure:: parse-tree-quiz.png
	  :scale: 70%

    .. _ex2-answer:

    .. admonition:: 課題2
       :class: exercise

       .. code-block:: bnf

	  <var> ::= A | B | C
	  <factor> ::= <var> | ( <expr> )
	  <term> ::= <factor> | <term> * <factor>
	  <expr> ::= <term> | <expr> + <term>

    .. _ex3-answer:

    .. admonition:: 課題3
       :class: exercise

       この文法は曖昧なので、次の2通りの構造のどちらであるか、これだけでは決められない。

       .. figure:: dangling-else-1.png
	  :scale: 60%

       .. figure:: dangling-else-2.png
	  :scale: 60%

    .. _ex4-answer:

    .. admonition:: 課題4
       :class: exercise

       曖昧であることを示すためには二種類の構文解析が可能であるような文を見つければ良い。例えば ``AAA`` はそのような文である。

       .. figure:: ambiguous.png
	  :scale: 70%

    .. _ex5-answer:

    .. admonition:: 課題5
       :class: exercise

       .. list-table::
	  :header-rows: 1

	  * -
	    - 宣言なし
	    - 宣言あり
	  * - 読み書き
	    - 書きやすい
	    - 読みやすい
	  * - コードは
	    - 短い
	    - 長い
	  * - スペルミスの発見は
	    - しにくい
	    - しやすい

       変数宣言に型(e.g. int, double)、スコープ(e.g. global, local)、アクセス修飾子(e.g. public, private)などを含める場合は：

       * コンパイラがそれらの情報を利用してバグを発見したり、効率の良い機械語を生成したりできる。
       * プログラミングの柔軟性は少なくなる。

    .. _ex6-answer:

    .. admonition:: 課題6
       :class: exercise

       静的スコープでは5、動的スコープでは10。

    .. _ex7-answer:

    .. admonition:: 課題7
       :class: exercise

       AとBというデータがお互いに参照している場合、外部からの参照が無くなればAとBの両方が不要になるが、参照カウンタは1のままである。

    .. _ex8-answer:

    .. admonition:: 課題8
       :class: exercise

       1. 変数に記憶されているデータA, Bと、Bから参照されているデータCがあるとする。

       2. GCにより、Aからたどれるデータにマークが付けられる。

       3. プログラムの実行によりA, Bの内容が変更され、AがCを参照し、Bは何も参照しなくなる。

       4. GCにより、Bからたどれるデータにマークが付けられる。

       5. そうすると、CはAから参照されているので必要なデータだが、GCでマークが付けられないので捨てられる。

    .. _ex9-answer:

    .. admonition:: 課題9
       :class: exercise

       C言語のライブラリ関数 ``strtok`` は、文字列を区切り文字で区切ってトークンに分解する。最初に呼び出す時は、第1引数に文字列を与え、先頭のトークンが返ってくる。2回目以降の呼び出しでは、第1引数に ``NULL`` を与え、呼び出すたびに次のトークンが順に返ってくる。これは、 ``strtok`` が static local 変数で文字列をどこまで分解したかを覚えているからである。

       * ライブラリ関数なので、グローバル変数は使うべきではない。（ユーザのアプリケーションで使っている名前とぶつかる可能性がある。）
       * 1回の呼び出しですべてのトークンを返そうとすると、不定個の文字列の配列が必要となるが、ライブラリ関数で記憶領域を割り当てるべきではない。（ユーザのアプリケーションでどのようなメモリ管理をしているかわからない。）

       cf. `source code (Apple Open Source) <http://www.opensource.apple.com/source/Libc/Libc-167/string.subproj/strtok.c>`_ , `sample usage (TutorialsPoint) <http://www.tutorialspoint.com/c_standard_library/c_function_strtok.htm>`_

    .. _ex10-answer:

    .. admonition:: 課題10
       :class: exercise

       * Cの利点

	 * 言語仕様が小さくなるので、処理系が作り易い。
	 * 整数値で0だけを特別扱いすること（例えば文字列の終端）が多いので、そのような場合は短いプログラムが書ける。

	   .. code-block:: c

	      while (*q++ = *p++);  /* pからqへの文字列コピー */

       * Javaの利点

	 * プログラムを読む時にわかりやすい。
	 * 整数と真偽値を間違えた場合に型検査で発見できる。
	 * 型情報を利用して最適化ができる可能性がある。

    .. _ex11-answer:

    .. admonition:: 課題11
       :class: exercise

       ``(a->b)->[a]->[b]``

    .. _ex12-answer:

    .. admonition:: 課題12
       :class: exercise

       1. ``(a#b)$c``
       2. ``a!(b?c)``
       3. ``(a#b)!(c$d)``
       4. ``(a#b)!(c?d)``
       5. ``((a#b)$c)!(d?e)``

    .. _ex13-answer:

    .. admonition:: 課題13
       :class: exercise

       短絡評価の場合、後半部分に副作用があると、前半部分の値によって副作用が起きたり起きなかったりするので、それを避けるために短絡評価をしない演算子が用意されている。副作用がない場合は、短絡評価の方が効率が良い。

    .. _ex14-answer:

    .. admonition:: 課題14
       :class: exercise

       * ``Error`` はシステム的なエラーで、ユーザプログラムでは回復が困難なことが多い。
       * ``RuntimeException`` は、次の二つの理由が考えられる。

	 * ``ArrayStoreException`` などはプログラムを適切に書いていれば起きないはずなので、例外処理でなく、例外が起きないようにプログラムを修正するべきである。
	 * ``ArithmeticException`` （ゼロ除算など）や ``NumberFormatException`` は、入力データを処理する時はcatchしたいかもしれない。しかし、すべての除算や ``parseInt`` に例外処理を書くのはあまりに煩雑なので、プログラマが必要と考えるところのみ例外処理を行えるようにしている。

    .. _ex15-answer:

    .. admonition:: 課題15
       :class: exercise

       1. value: 2, list: {1, 3, 5, 7, 9}
       2. value: 2, list: {3, 1, 5, 7, 9}
       3. value: 2, list: {3, 2, 1, 7, 9}

    .. _ex16-answer:

    .. admonition:: 課題16
       :class: exercise

       無名関数 ``function() { alert(i); }`` に出てくる変数 ``i`` の束縛は、それを囲むスコープによって決まっているので、繰り返して10回closureを生成すると、すべて同じ実体に束縛される。 ``for`` ループを終了した時点の ``i`` の値は 11 なので、どのボタンをクリックしても 11 が表示される。

       ``let`` を使用すると、 ``i`` はブロックスコープになり、 ``for`` の各繰り返しで別々の実体に束縛されるので、異なる値を保持できる。

    .. _ex17-answer:

    .. admonition:: 課題17
       :class: exercise

       * クラスを型と見なす場合、値の集合はそのクラスのインスタンス、操作はそのクラスで定義された（継承されたものも含む）メソッドである。
       * 静的型検査の目的は、エラーが起きる可能性を実行する前に（コンパイル時に）発見することである。

       ``A x = new B()`` が許される理由

	 変数 ``x`` が ``A`` 型であるということは、変数 ``x`` に対してクラス ``A`` で定義されている操作が行われる可能性がある。クラス ``B`` はクラス ``A`` を継承しているので、クラス ``B`` のインスタンスでもクラス ``A`` の操作はすべて可能であり、実行時に問題は起きない。

       ``B y = new A()`` を許さない理由

	 変数 ``y`` に対して、クラス ``A`` では定義されていないが、クラス ``B`` で定義されている操作が行われる可能性がある。実際にはそのような操作は行わないプログラムなのかもしれないが、静的型検査の目的は、実行時にエラーが起きる可能性を排除することなので、これは許さない。

    .. _ex18-answer:

    .. admonition:: 課題18
       :class: exercise


       哲学者の人数 n に関する数学的帰納法を用いる。

       n=1 の場合は明らか。

       n=kで成り立つと仮定する。k+1人の哲学者をp(1), p(2), ... , p(k+1)とし、この順に座っているとする。右端のp(k+1)は常に自分の右のフォークを取れるので、左のフォークされ取れれば食事が出来る。p(k+1)が左のフォークを取れない状態が続いたとすると、p(1), ..., p(k)は仮定からデッドロックしないので、いつかはp(k)が右のフォークを置く瞬間があり、その時点でp(k+1)が食事できる。p(k+1)の食事が終われば、p(k)は右のフォークを取れるので、p(1), ..., p(k)がp(k)の右のフォークを取れないためにデッドロックすることもない。

    .. _ex19-answer:

    .. admonition:: 課題19
       :class: exercise

       モニタ

	  * ``synchronized`` 文
	  * メソッドの ``synchronized`` 修飾子

       モニタの中で寝る

	  * ``Object.wait`` メソッドの呼び出し

       モニタの中で寝ているタスクを起こす

	  * ``Object.notify`` メソッドの呼び出し
	  * ``Object.notifyAll`` メソッドの呼び出し