アンダースタンディングコンピュテーション――単純な機械から不可能なプログラムまで_読書メモ 2章

いつもは一冊読み終えてからレビューみたいな感じで
書いてるんですが、それだと後回しにしちゃう本とか、途中まで読んで
満足しちゃうことがあるので、メモみたいな感じで最期に総括できたらなぁ、と思って
各章で書いてみることにしました。

とりあえずはある程度の速度で一冊読むことを継続したいのと
読んだ内容忘れちゃうので、こんな感じで続けて書いていけたらと思います。

書籍の中に書かれているコードとか、より詳しい説明は極力載せません。
基本的には本の中に出てくる用語の解説等をかいつまんだ感じ・・・
興味を持っていただけたら実際に購入して読んでみることをオススメします。

※自分用メモなので内容は適当なのと、理解が進んでいくうちに追記していく可能性があります

コンピュータサイエンスにおける形式意味論 (formal semantics)

新しい言語の仕様化、コンパイラ最適化の工夫、プログラム正当性の数学的証明等
幅広く応用されている。

プログラミング言語を記述するためには2つの要素が必要

  1. 構文 (Syntax) プログラムがどのように見えるか
  2. 意味論 プログラムが何を意味するのか

プログラミング言語を記述するためのアプローチ

  1. 実装による仕様 (Ruby, PHP, Perl5)
  2. 公式文章としての仕様 (C++, Java, ECMAScript)
  3. プログラミング言語の意味を形式意味論の数学的なテクニックを利用して記述する

構文 (Syntax)

どんな文字列がそのプログラミング言語で有効であるか、というものを記述した集まり。
これによって言語の構文(Syntax)を規定する

これをパーサ(parser)を使って解析して処理に適した構造化された表現に変換する
パーサは一般的に文字列を抽象構文木(Abstract Syntax Tree)に変換するものを指す

構文はプログラムの表面的な見え方にのみ関係していて、意味論には無関係

操作的意味論(Operational semantics)

プログラムがある装置(抽象機械:abstract machine)で、どのように実行されるのか、
その規則を定義することでプログラミング言語の意味を記述する方法

操作的意味論を与えることで言語における具体的な構成要素と目的を、厳密にして
言語の振る舞いを確実に伝える。

抽象機械(abstract machine)

ある言語で書かれたプログラムがどのように実行されるかを説明するために
設計された架空上のコンピュータ。通常、言語ごとに異なる抽象機械を設計する必要がある。

スモールステップ意味論

構文を小さなステップで繰り返し簡約(reduce)することで、プログラムを評価する
抽象機械を設計する。

例) (1 + 2) + (3 + 4) => 3 + (3 + 4) => 3 + 7 => 10 (これ以上簡約できないので、これを結果として返す)

反復(iterative)という特徴があり、簡約規則を繰り返し実行するための抽象機械が必要

本の中では

  • 値: 数字(Number)、真偽値(Boolean)
  • 式: 足し算,掛け算, 小なり(less than)
  • 文: 変数(variable), 代入(assign), if, while

の意味論をRubyで実装している。(スモールステップ、ビッグステップ共に)

スモールステップ意味論の実行指向スタイルは、実世界のプログラミング言語を
誤解のないように記述するのに向いている。

ビッグステップ意味論

どうやって式や文から直接結果を得るか、を記述する。
プログラムの実行プロセスを反復ではなく再帰(recursice)として見なす。

スモールステップ意味論は計算の途中段階を簡単に観察できるが
ビッグステップ意味論は結果を返すだけで、どのように計算されたか、という証拠は残さない

表示的意味論(Denotational semantics)

プログラムをネイティブ言語から別の表現に変換する。
すでに確率された別の言語の意味を利用して、新しい言語を説明すること。

動的意味論(Dynamic semantics)

プログラムが実行されるときに、そのプログラムは何をするのかについて説明する意味論。
この章に含まれる意味論がこれに該当する。
静的意味論(Static semantics)ももちろん存在するが、それは後述らしい

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です