窓辺の小石 第229回 逆回りのExpression

最近ではほとんど見かけなくなったが、かつては、「逆ポーランド記法（Reverse Polish Notation、RPN）」を採用した電卓があった。著名なのは、HP社の製品だが、それ以外のメーカーでも、採用した製品があった。逆ポーランド記法とは、演算子を被演算子の後ろに置く記法。「X　＋　Y」を「X　Y　+」と表記する。

これを「後置記法」（Postfix Notation）といい、逆に演算子を前に置く記法を「前置記法」（Prefix Notation）という。また、前置記法を「ポーランド記法」、後置記法を「逆ポーランド記法」とも呼ぶ。ポーランドは、前置記法を提案したヤン・ウカシェヴィチ（Jan Łukasiewicz）の故国である。

なお、いわゆる普通の数式は、数値の間に演算子を置くことから「中置記法（infix notation）」という。

通常の数式（中置記法）と前置記法、後置記法は、お互いに変換が可能でそのためのアルゴリズムがある。もちろん、人間が普通の数式を後置記法に変換することも難しくない。人間が中置記法を後置記法に変換する場合、もっとも優先度の高いところ、たとえば括弧の内側から計算を進めていく。話だけを聞くと、かなり面倒そうだが、実際には、数式をどうやって計算するのかを考えれば、自然と逆ポーランド記法になる。

数式には、計算手順を1つに決めるためのルールがある。たとえば、乗算、除算は加算、減算よりも優先される、括弧でくくられた部分の計算は、先に行うなどだ。学校では、理由も教えられずに「ルール」として覚えるように強制される。こうした数式計算のルールがあるために、計算機は、数式の計算に少し手間をかける必要がある。もっとも、コンピュータ言語では、数式に人間のルールを持ち込むかどうかは設計者次第。多くの言語では、人間のルールを使って数式を計算してくれるが、そうない言語も存在する。

多くのコンピュータ言語で、数式の計算手順を理解するための用語に「優先順位」がある。演算子には、優先順位があり、計算は、優先順位の高い方から行うというのが基本的なルールとなる。このルールがなければ、数式も先頭から順に計算していけばいいわけだが、ルールがあるがために、先に出てきた演算を一時棚上げして優先度の高い演算子を先に計算しなければならない。

コンピュータで数式を計算させる場合の方法の1つとして、中置記法を先頭から見ていき、スタックを使って逆ポーランド記法に変換しつつ計算を行う方法がある。演算子の優先順位を考慮して作られた逆ポーランド記法は、すでに演算子の優先度が考慮された計算順となっているため、そのまま計算していくだけで答えを得られる。

中置記法を逆ポーランド記法に変換するための有名な方法の1つに「操車場アルゴリズム」がある。これは、列車の引き込み線を使って、車両を入れ替える方法に例えて、中置記法を後置記法（前置記法も可）に変換する手順を説明したものだ。

数式が後置記法に変換できたら、あとは、スタックを使って順に計算していく。手順としては単純で、数値はスタックに積み、演算子はスタック上の上2つ数値に対して演算を行う。これを最後まで繰り返すだけだ。

コンピュータの機械語命令は多くの場合、「ADD X,Y」のように前置記法になっている。スタック上の2つの数値を計算するには、最終的に機械語命令を使うことになる。そう考えると、数式の計算は、「中置記法 ⇒ 後置記法 ⇒ 前置記法」として実行されていくわけだ。

記法というと、単なる表記の仕方だと思いがちだが、このように具体的なアルゴリズムを併用することで、記法が計算方法になっていることがわかる。

1968年に作られた世界初の関数電卓 HP 9100Aに、逆ポーランド記法が使われたのは、複雑な数式を効率良く計算するためだ。人間に中置記法から逆ポーランド記法に変換させて、括弧や優先度を考慮しないで、連続計算を可能にした。ある時期までは、逆ポーランド記法の関数電卓は、効率のいい計算が可能だったが、そのうち、日本の電卓メーカーにより、「完全数式通り」の計算が可能になる。中置記法をそのまま入力して最後にイコールキーを押せばよく、計算手順を考える必要もない。いくつか、完全数式通りの関数電卓を購入してみた。ある意味、進歩なのだが、数式を入れるだけなので、計算しているという手応えを感じられず、なじめずにいる。高機能化したにもかかわらず、キーの打鍵感が安っぽい、というのも理由なのかもしれないが……。

今回のタイトルネタは、Philip K. Dickの「Counter-Clock World, 1967」（邦訳逆回りの世界。早川）である。時間逆流現象“ホバート位相”で死者が蘇る世界を描いた作品。再生した死者を適当な保護者に売却する事業がすでに成立しているのが、何ともアメリカ風。