〈式〉の考察 2

その1 ⇒ プログラミングにおける〈式〉についての考察 - Ryusei’s Notes (a.k.a. M59のブログ)

前回、式の望ましい性質として確定性・構成性・純粋性があるという話をした。これらの性質がなぜ望ましいのかを、実際に式を分析しながら詳しく見ていく。

式の構造

式は一般に、原子式と式の基本構造から再帰的に構成されている。

例えば、次の式1は、2つの式, と、式の基本構造から成り立っている。そして、各部分式もまた部分と基本構造に分解できる。

式1:

式1の基本構造には次のものがある。

リスト1: 式1の基本構造

• 
• 
• 

リスト1は、式を構成する規則として見ることができる。すなわち、これらの基本構造の組み合わせで、さまざまな式を構成できるわけで、どのようなものが式であるかを決めるルールになっているということだ。

式の構成規則を構文という。構文に従って式を分解し、式の構造を明らかにすることを構文解析という。

式1を構文解析していくと、式1を構成する次のような式が得られる。

リスト2: 式1の部分式

• 
• 
• 
• 
• 
• 
• 
• 

構文解析の途中で得られた、元の式を構成する式を、部分式という。今後、部分式と言った時には、元の式自体も含めることにする。

また、部分式のうち、基本構造を使って1回分解して得られた部分式のことを、ここでは「直下の式」と呼ぶことにする。式1の直下の式は, の2つだ。

, , のように、構文によってこれ以上分解できない式を、原子式という。

構文木

式1を構文解析した結果は、次の図1のように木構造として表現できる。この木構造を構文木と言う。

図1: 式1の構文木

構文木の各ノードは、ある部分式と対応している。構文木の根は元の式と対応し、子ノードは直下の式と対応する。

曖昧な構文

式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は使えない。式の値が、直下の式の値と基本構造の機能だけから計算できないからだ。