読者です 読者をやめる 読者になる 読者になる

〈式〉の考察 2

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

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

式の構造

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

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

式1:  a b + c (a + b)

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

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

  •  \square \square
  •  \square + \square
  •  ( \square )

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

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

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

リスト2: 式1の部分式

  •  a b + c (a + b)
  •  a b
  •  a
  •  b
  •  c (a + b)
  •  c
  •  (a + b)
  •  a + b

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

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

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

構文木

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

f:id:mandel59:20151129154749p:plain
図1: 式1の構文木

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

曖昧な構文

式1は、 a b + c (a + b)という式と \square \squareという基本構造からなりたっているとみて、図2のように構文解析することもできる。

f:id:mandel59:20151129160323p:plain
図2: 式1の別の構文木

構文解析の結果が1通りでない式がある構文を、曖昧な構文という。構文が曖昧だと、構文解析の結果次第で、式の意味が変わってしまうというようなことが起きる。それでは困るので、普通は構文解析の結果が1通りになるような規則が設けられている。そのような規則に、例えば、演算子の優先順位がある。今後、ここで扱う式は、数学における数式と同じルールで構文解析するということにする。

式の値の計算

式の構成性は、次の性質だ。(前回の記述から修正してある。)

構成性 (compositionality): 式の値は、式の基本構造の機能と、直下の式の値のみから一意に決定される。

基本構造の機能とは、基本構造が表している〈足し算〉や〈掛け算〉のような計算のことだ。

式に構成性がある場合、すべての原子式の値が分かっていて、基本構造の機能をすべて実際に計算できると、次の手続き1に従って式の値が計算できる。

手続き1: 式Eの値を計算する

  • 手順1: 式Eの部分式のうち、まだ値が分かっていない部分式の中から、その式の直下の式すべてについて値が分かっているような式を、どれでもいいので、1つ選ぶ。その式をE’とする。
  • 手順2: 式E’の直下の式の値と、基本構造の機能から、式E’の値を計算する。
  • 手順3: 式Eの値が分かるまで、手順1, 2を繰り返す。

基本構造の機能が計算できるというのは、たとえば \square + \squareの部分の機能は〈足し算〉で、それを実際に計算できるということを表している。

実際に、上の手順で次の式2の計算をしてみよう。

式2:  2 \times 3 + 4 \times 5

式2の部分式は、式2自体を含めて次のものがある。(構文解析は数学と同じルールと決めたので、 3 + 4などは部分式でないことに留意してほしい。)

  •  2 \times 3 + 4 \times 5
  •  2 \times 3
  •  4 \times 5
  •  2
  •  3
  •  4
  •  5

そのうち、原子式 2,  3,  4,  5は値が最初から分かっている。

手順1: 式2の部分式の中で、直下の式すべてについて値が分かっている式は 2 \times 3 4 \times 5だ。ここでは 2 \times 3を選ぶとする。

手順2:  2 \times 3の直下の式の値 2,  3と基本構造の機能〈掛け算〉から、式の値を計算する。2と3を掛け算することで、 2 \times 3の値は 20だと分かる。

手順3: 同様に、 4 \times 5の値は 20だと分かる。すると 2 \times 3 + 4 \times 5の値も計算できて、6と20を足し算し、値は26だと分かる。

数式がどんなに複雑になっても、原理的には同じ方法で計算できる。もちろん、頭を使えばより効率的に計算することができる場合もあるが、とにかく機械的に式の値を計算することができる。

もし式に構成性がないと、手続き1は使えない。式の値が、直下の式の値と基本構造の機能だけから計算できないからだ。