〈式〉の考察 2
その1 ⇒ プログラミングにおける〈式〉についての考察 - Ryusei’s Notes (a.k.a. M59のブログ)
前回、式の望ましい性質として確定性・構成性・純粋性があるという話をした。これらの性質がなぜ望ましいのかを、実際に式を分析しながら詳しく見ていく。
式の構造
式は一般に、原子式と式の基本構造から再帰的に構成されている。
例えば、次の式1は、2つの式,
と、式の基本構造
から成り立っている。そして、各部分式もまた部分と基本構造に分解できる。
式1:
式1の基本構造には次のものがある。
リスト1: 式1の基本構造
リスト1は、式を構成する規則として見ることができる。すなわち、これらの基本構造の組み合わせで、さまざまな式を構成できるわけで、どのようなものが式であるかを決めるルールになっているということだ。
式の構成規則を構文という。構文に従って式を分解し、式の構造を明らかにすることを構文解析という。
式1を構文解析していくと、式1を構成する次のような式が得られる。
リスト2: 式1の部分式
構文解析の途中で得られた、元の式を構成する式を、部分式という。今後、部分式と言った時には、元の式自体も含めることにする。
また、部分式のうち、基本構造を使って1回分解して得られた部分式のことを、ここでは「直下の式」と呼ぶことにする。式1の直下の式は,
の2つだ。
,
,
のように、構文によってこれ以上分解できない式を、原子式という。
曖昧な構文
式1は、と
という式と
という基本構造からなりたっているとみて、図2のように構文解析することもできる。
図2: 式1の別の構文木
構文解析の結果が1通りでない式がある構文を、曖昧な構文という。構文が曖昧だと、構文解析の結果次第で、式の意味が変わってしまうというようなことが起きる。それでは困るので、普通は構文解析の結果が1通りになるような規則が設けられている。そのような規則に、例えば、演算子の優先順位がある。今後、ここで扱う式は、数学における数式と同じルールで構文解析するということにする。
式の値の計算
式の構成性は、次の性質だ。（前回の記述から修正してある。）
構成性 (compositionality): 式の値は、式の基本構造の機能と、直下の式の値のみから一意に決定される。
基本構造の機能とは、基本構造が表している〈足し算〉や〈掛け算〉のような計算のことだ。
式に構成性がある場合、すべての原子式の値が分かっていて、基本構造の機能をすべて実際に計算できると、次の手続き1に従って式の値が計算できる。
手続き1: 式Eの値を計算する
- 手順1: 式Eの部分式のうち、まだ値が分かっていない部分式の中から、その式の直下の式すべてについて値が分かっているような式を、どれでもいいので、1つ選ぶ。その式をE’とする。
- 手順2: 式E’の直下の式の値と、基本構造の機能から、式E’の値を計算する。
- 手順3: 式Eの値が分かるまで、手順1, 2を繰り返す。
基本構造の機能が計算できるというのは、たとえばの部分の機能は〈足し算〉で、それを実際に計算できるということを表している。
実際に、上の手順で次の式2の計算をしてみよう。
式2:
式2の部分式は、式2自体を含めて次のものがある。（構文解析は数学と同じルールと決めたので、などは部分式でないことに留意してほしい。）
そのうち、原子式,
,
,
は値が最初から分かっている。
手順1: 式2の部分式の中で、直下の式すべてについて値が分かっている式はと
だ。ここでは
を選ぶとする。
手順2: の直下の式の値
,
と基本構造の機能〈掛け算〉から、式の値を計算する。2と3を掛け算することで、
の値は
だと分かる。
手順3: 同様に、の値は
だと分かる。すると
の値も計算できて、6と20を足し算し、値は26だと分かる。
数式がどんなに複雑になっても、原理的には同じ方法で計算できる。もちろん、頭を使えばより効率的に計算することができる場合もあるが、とにかく機械的に式の値を計算することができる。
もし式に構成性がないと、手続き1は使えない。式の値が、直下の式の値と基本構造の機能だけから計算できないからだ。
