Skinerrian's blog

論理学・哲学・科学史・社会学などに興味があるので、その方面のことを書きます。更新は不定期。

ポーランド記法

書くことが特に無いので、9/5の続きを載せてみる。念のためにもう一度断っておくと、『数学ガール』は結城浩先生の創造物です。

  • ぼく:…というようなことを話したんだ。そんなに間違ったことは言ってないよね。
  • ミルカ:たぶんね。君が言った省略規則は命題論理でしばしば目にするものだよ。この場合、「+」や「×」に相当するのは「&」とか、「∨」、「→」だけどね。
  • ぼく:「→」はどういう意味?
  • ミルカ:「ならば」という意味だね。「A→B」は「AならばB」。命題論理では、ふつう「&」や「∨」が「→」よりも結びつきが強い。だから、

( (A&B)→C)

  • に省略規則を適用すると、

A&B→C

  • になる。四則計算の省略規則は小学校のころからの訓練で馴れているだろうけど、こちらは見慣れるのに少し時間がかかるかもね。
  • ぼく:…ミルカさんは論理学もできるんだね。
  • ミルカ:これはelementaryだよ。それからね、もう少し工夫をするとすべての括弧を省略することができるよ。ポーランド記法Polish notationという。
  • ぼく:全ての!えぇ、だって「(2+3)×5」の括弧を省略したら3×5が先に計算されちゃうでしょう。
  • ミルカ:そこは「工夫」だよ。我々がふだん見慣れている四則計算の表記法は、演算子を数字と数字の真ん中に書くからinfix notationと呼ばれるんだが、ポーランド記法では演算子の位置を前にもってくる。例えば、「2+3」は「+23」と書かれる。
  • ぼく:ふーん。でもさ、「2」と「3」なのか、「23」なのかはどうやって区別するの。
  • ミルカ:案外鋭いね、君。やり方は幾つかあるだろう。スペースを空けるのが一つのやり方。あるいは、そもそも数字の書き方を変えてしまうというやり方もある。例えば、「2」を「0''」という風に表す。「'」はアクセント記号だけど、この場合は「+1」の意味。まぁ、今は原理的な話をしているわけだから、こういう話はいいだろう。以下ではスペースを空けることにするよ。
  • ぼく:うん。
  • ミルカ:ポーランド記法では、「( (2+3)×5)」はこう書かれる。

×+2 3 5

  • ぼく:暗号みたいだなぁ。
  • ミルカ:これも馴れだよ。左から順に読んでいこう。まず、「×」だから、二つの引数があると考えられる。次は「+」だから、これまた二つの引数があると考えられる。次は「2」と「3」だから二つ揃ったから、「(2+3)」になる。最後は「5」だ。これでまた二つ揃ったから結局「( (2+3)×5)」になる。
  • ぼく:…何となく分かってきたけど。今の説明をフォーマルに書き下すのは大変そうだなぁ。
  • ミルカ:そうかもね。じゃあ、少し練習してみようか。

(1) −+5÷×4 8 2 3

  • これは?
  • ぼく:…。( (5+( (4×8)÷2) )−3)。だから18だね。
  • ミルカ:ふむ。…じゃあ、

(2) +5÷×2 4 −+9 1

  • これは?
  • ぼく:…。あれ、これって何だか変だなぁ。
  • ミルカ:デタラメに書いただけだからね。さっき君はポーランド記法を読む規則をフォーマルに書くのは難しそうだと言ったけれども、ここにはもう一つの難しさがある。文字列を適切なルールに従って分節化して読み込むプログラムをパーサーparserと言うんだが、パーサーは(1)のような式を読めるだけでなく、(2)のような式についてはエラーを出せなくてはならないんだよ。
  • ぼく:ところで、そのポーランド記法は何か実用性があるの?
  • ミルカ:プログラミングでよく使われるよ。それから、ポーランド記法とは逆に、演算子を操作対象の後ろに置くような表記法があるんだが――逆ポーランド記法というんだが――これをベースにした関数電卓なんかがある。
  • ぼく:使いにくそうな電卓だなぁ。
  • ミルカ:そうでもないよ。実はね、逆ポーランド記法の語順は日本語と同じなんだよ。君、ちょっとこれを読んでくれたまえ。

2+(3×5)

  • ぼく:…2に3と5を掛けたものを足す、かな。
  • ミルカ:その語順通りに記号化してごらん。

235×+

  • ぼく:本当だ。ポーランド記法の逆になっている!すごいなぁ。
  • ミルカ:これは形式言語の表記法が自然言語の分析にも繋がる興味深い一例だよ。まぁこれだけではたいしたことは言えないけどね。