プログラミング意味論の基礎を読みました

  • また読んでいる途中です。

第1章

  • 1.1 演習問題がやさしいなと思ったらいっぱい間違えた。「ならば」の使い方が難しい。
  • 2項関係が直積(感覚的には 組 だと思えばOK)の部分集合を指していることの理解に苦労した。まず、関係とは例として < が考えられるけど、 1<2 を見ると1,2の間に挟まっているやつなのにこれが集合になる???という記号に対する違和感を持った。実際は、 x<y(x,y) が満たす条件を定めていて、その条件を満たすような (x,y) を集めているのでこれは直積の部分集合になる。
  • 関数もそうだが、今まで習ってきた x<yf(x)=y という表記に慣れすぎていて、それらを統一的に二項関係 (x,y)∈R という観点からまとめ直すことに苦労した。
  • 対角線論法の理解で、 f(n)(n) の意味を理解するところで苦労した。まず勘違いとして、 f(n) は0,1のいずれかだと思っていた。この勘違いのもとでは f(n) は関数ではないので f(n)(n) はおかしいことになる。幸いTwitterでフォローしている方に教えてもらって、 f はNat -> {0,1}への関数を集めたものなので、 f(n) は(それら関数たちを番号付けできたという仮定をして)、n番目の関数であるという意味にあたることが理解できた。したがって、 f(n)(n) は「n番目の関数に引数nを渡したもので、0 or 1を返す」という理解になる。こうすれば、 g=f(m) なら (f(m))(m)=0f(m)(m)=0 となることが理解でき、後半のパートも理解できる。

第2章

  • 2.2 曖昧な構文が存在しないようにBNFを構成するところが苦労した。以下のように構成するとうまくいくことが多い気がする
  • とりあえず下のやつを最初に持ってきて、後ろに書くやつをうまく考える
A ::= B | ~
B ::= C | ~
C ::= (A) | ~
  • 2.3 具象構文と抽象構文の違いについての理解。構文解析を行うと、それは構文として正しい構造を持つことがチェックされているので、このパートで構造チェック(演算子の優先度や、括弧の有無)が走っている。そこで次に意味論パート(構造は合っているが、意味として正しいか?)に移るので、ここでは構造としての正しさを考えなくてよい。したがって、括弧の有無などは抽象構文では気にしなくてよいことになる。