解答例

課題1

_images/parse-tree-quiz.png

課題2

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

課題3

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

_images/dangling-else-1.png
_images/dangling-else-2.png

課題4

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

_images/ambiguous.png

課題5

厳密に言うと、変数宣言と型宣言は同じではない（型がない変数宣言、宣言せずに型推論で型が決まる場合などがある）。また、変数宣言で型以外の属性を指定することもある。

変数の名前を宣言することについては：

宣言なし

宣言あり

読み書き

書きやすい

読みやすい

コードは

短い

長い

スペルミスの発見は

しにくい

しやすい

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

  • コンパイラがそれらの情報を利用してバグを発見したり、効率の良い機械語を生成したりできる。

  • プログラミングの柔軟性は少なくなる。

課題6

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

課題7

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

課題8

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

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

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

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

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

課題9

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

  • ライブラリ関数なので、グローバル変数は使うべきではない。（ユーザのアプリケーションで使っている名前とぶつかる可能性がある。）

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

cf. source code (Apple Open Source) , sample usage (TutorialsPoint)

課題10

  • Cの利点

    • 言語仕様が小さくなるので、処理系が作り易い。

    • 整数値で0だけを特別扱いすること（例えば文字列の終端）が多いので、そのような場合は短いプログラムが書ける。

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

  • Javaの利点

    • プログラムを読む時にわかりやすい。

    • 整数と真偽値を間違えた場合に型検査で発見できる。

    • 型情報を利用して最適化ができる可能性がある。

課題11

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

課題12

  1. 【a#b】$c

  2. a!【b?c】

  3. 【a#b】!【c$d】

  4. 【a#b】!【c?d】

  5. 【【a#b】$c】!【d?e】

課題13

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

課題14

  • Error はシステム的なエラーで、ユーザプログラムでは回復が困難なことが多い。

  • RuntimeException は、次の二つの理由が考えられる。

    • ArrayStoreException などはプログラムを適切に書いていれば起きないはずなので、例外処理でなく、例外が起きないようにプログラムを修正するべきである。

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

課題15

  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}

課題16

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

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

課題17

  • クラスを型と見なす場合、値の集合はそのクラスのインスタンス、操作はそのクラスで定義された（継承されたものも含む）メソッドである。

  • 静的型検査の目的は、エラーが起きる可能性を実行する前に（コンパイル時に）発見することである。

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

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

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

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