演算子の優先順位とプログラム言語

教えて数学のエロい人!

まぁ、友人のMは数学に造詣が深いので教えてくれるでしょう。
歴史的に言うと、数学者も演算子の結合優先順位の曖昧さに悩んでいたそうです。例えば、sin ab って、sin(a)b? sin(ab)?とか。そもそもこのsinって演算子なのかsin()の省略形なのか誰もはっきり言えないというもどかしさがあるわけです。
そこで、いろいろなアプローチがなされています。私が知っているのはコンピューティング界隈だけですけどね。

Łukasiewicz

ポーランドの数学者だったŁukasiewiczは「a+bのような中挿記法を使うから曖昧になるのだ」と考えました。これを根本的に解決するため、「演算子演算子 被演算子」という記法を考えました。被演算子の位置に演算子が来た場合、その演算子にかかる演算を優先します。

* 3 2
=> 6
* 3 + 2 5
=> 21

私の記憶が確かなら、このアイデアに関する原稿は彼の死後発見されています。そして、この前置記法をひっくり返した後置記法が、恐ろしくコンピュータと相性がいいことが発見されるにいたります。被演算子をスタックにプッシュするスタック・マシンは後置記法をフルに活用します。

3 2 *
=> 6
3 2 5 + *
=> 21

後置記法はHPの電卓にも採用され、今でもカルト的な人気を誇ります。Łukasiewiczの祖国ポーランドに敬意を表し、後置記法はRPN (Reverse Polish Notation : 逆ポーランド記法)と呼ばれます。

Iverson

配列演算を曖昧さなしに記述する方式を研究していた彼は、配列からスカラーまで統一的に使える記法を作り上げます。伝説によれば、彼はこれがコンピュータに実装されるとは思っていなかったとのことですが、彼の雇用者であったIBMはAPL : A Programming Languageの実装に成功します。
APLは中挿記法を採用していますが、演算子の優先順位に関するポリシーは極めて単純です。

  • 演算子に優先順位はない
  • 全ての演算は右から左に評価する

3 * 5 + 2
=> 21
5 + 2 * 3
=> 11

APLは演算子の評価順序が一風変わっていただけではなく、行列演算子インタープリタ演算子の実装のために、ASCIIやEBCDICにないι(イオタ)やε(イプシロン)といった文字を多用していましたので、そのプログラムはかなりエキゾチックな外見を持っていました。
80年代半ば、私が学んだ大学の情報処理センターにはTSS端末が並んでいましたが、そのうちかなりの数にはキーボードにAPL用文字の刻印がありました。
スプレッドシートが普及する前は、APLは文系御用達プログラミング言語としてデータ解析に活躍していたそうです。

McCarthy

John McCarthyのLispは数学とは本来無関係の言語*1ですが、括弧だらけの相当変わった記法は、基本的にはŁukasiewiczの前置記法に似ています。

( + 1 3 4)
=> 8
( + 1 (- 7 2 ) 2 )
=> 8

Lispは式を括弧でくるむため、演算子に優先順位はありません*2
良く知られていることですが、LISPは人類が作り出した2番目の高級言語です。最初の言語はFORTRANでした。

Kay

Allan Kay達が開発したSmalltalkはこの世のすべてをオブジェクトと考えます。数も例外ではありません。したがって、2 + 3 はオブジェクト2に+をセレクタとし、3を引数とするメッセージ・パッシングと考えられます。わけがわからないよ。
メッセージは左側のセレクタから順に渡されていきます。メッセージを受け取るたびにオブジェクトは評価結果を返しますので、次のセレクタは評価結果に渡されることになります。
したがって、

  • 演算子に優先順位はない
  • 演算は左から右におこなわれる

と、Smalltalkは式に対してAPLの逆の評価を行います。

2 + 3 * 4
=> 20

Wirth

Algol68の失敗を比較的近い距離で見ていたETHのNiklaus Wirthはプログラミング言語の理論に忠実で、かつシンプルな言語としてPascalを送り出しました。Pascal言語はそれを第一義にしなかったとはいえ、各所をシンプルにまとめようとする意志を感じる体系になっています。
たとえば、二項演算子の優先順位は、わずか3つしかありません。乗法演算子、加法演算子、比較演算子です。その結果、数値乗算演算子と、論理積演算子の優先順位が同じで、比較演算子より高いという事態が起きています。ということは、次のようなプログラムを書くとコンパイル・エラーがおきます。

if  3 > a and a >= 3 then 

こりゃないだろう、と思うわけです。この点はずいぶん昔のC対Pascal論争*3でやり玉にあがりました。とはいえ、私はCプログラマがあのやたら豪華な演算子優先順位数を自信を持って使いこなしているとも思いません。

おわりに

最後にこんなことを書くのもなんですが、プログラミングの勉強をしなくなって長いので、間違いが多いかもしれません。てへっ。

*1:もともとシンボル処理用に作られた。ただし、あとでプロジェクトMACが数式処理システムMACSYMAをLISPを使って実装したため、あながち無関係とは言えない

*2:これは古典的Lispの話。Lispには長い歴史と数多くの方言があり、何度もシンタックス・シュガーが投入されているので今はどうかしらない…

*3:極めてマイナーな論争だった