パースチャレンジ：オールドロジックのドット表記

Question

J. Barkley Rosserの "Logic for Mathematicians"では、かっこが多すぎないように表記法を使用しています。論理記者がこの記法を使うのはいつかわかりませんが、1957年に最初に出版された本は知っていますが、1916年に出版されたJ. G. P. Nicod's paperもこの記法を使用しています。だから明らかに長い歴史を持っていますが、現代の論理学者はこれが好まれていません。

プログラミングの世界では、LISPのプログラミング言語では、プログラマーが正しい（巨大な）括弧の量を追跡することが大きな課題です。 Haskellは、機能の一部を提供する演算子$を提供しますが、2 * $ 3 + 4と言うことはできませんので、ドットほど強力ではありません（下記の例を参照）。 C言語シリアルは従来の操作優先順位を使用しますが、場合によっては深いネストされたかっこも必要です。だから私はなぜ実際の言語はこの戦略を使用しているのだろうか？私は試しましたが、文法を書くことさえできませんでした！

オペレータ+と*の2人だけのおもちゃの電卓の言語の例を示しましょう。すべての用語は整数です。

この表記を使用すると、翻訳者は、次のテストケースに合格しなければならない：

1 + 3 .* 2 
= (1 + 3) * 2 
1 *. 3 + 2 
= 1 * (3 + 2) 
1 *. 2 +. 2 
= (1 * 2) + 2 
2 *: 2 + 3 .* 4 
= 2 * ((2 + 3) * 4) 

私はこの表記法のすべての詳細を説明望めない、それはロッサーの本の中で、ほぼ5ページがかかります。しかし、gena​​ral（およびshort）では、オペレータの前または後のドット.は、両側を押し離すために "セパレータ"を表します。コロン:はより強いセパレータであり、3つのドット.:または:.はさらに強くなりますが、::より小さくなります。

私は上記の言語の文法をどうやって書くことができますか？また、この表記は廃止されましたが、私はプログラマの目には非常に明確に見えることがわかりました。だから、その賛否両論は何ですか？

Answer 1

ドット表記は、Principia Mathematica（1910-1913）のRussellとWhiteheadによって最も有名になっていますが、表記はGuiseppe Peanoから借りています。それはまた、アロンゾ教会、ウィラード・ヴァン・オルマン・クイン（Willard Van Orman Quine）、および他の影響力のある論理学者によっても使用されました（スタンフォード・エンペロピア・オブ・フィロソフィーのthis entry参照）。

実践のビットでは、ドット表記の数式を読むのは難しくありませんが、最初に表示されるほど優雅ではありません。で開始する、ラッセルとホワイトヘッドは、まだそれが有用否定演算子~で括弧を使用することが見つかりました：上記の例が示すように

*3·01. p.q .=. ~(~p v ~q)

は、ドット積演算子の両方として使用され、優先順位を表現します。結果として、より強い結合は、 :またはさらに :.と書くことができます。

最後に、視覚的混乱を減らすために、RussellとWhiteheadは優先順位の関係を使用します。この場合、演算子のセットは3つの優先グループに分けられ、高い優先順位の演算子のドットがより低い優先順位のオペレータのドット数と等しい。等しい優先順位の演算子の間では、ドットの数が等しくなるのは合法ではありませんが、ラッセルとホワイトヘッドは、重要ではない優先順位を指定する必要を避けるために、p v q v rのような三項演算子を定義しました。 （私が知る限り、このような式の正確な解析ルールは決して正式には書き出されませんでしたが、定義はPMに表示されます。）

これまで述べてきたように、シャントヤードアルゴリズムの変形を使用してドット表記を解析することは非常に困難ではありません。残念なことに、文脈自由文法では解析できないため、自動化されたツールで生成された文法にはあまり役に立ちません。 GLRパーサーでさえ、CFGに制限されています。 （ドット記法が文脈自由でないという事実は、ポンピング補題で証明することができます;通常のポンピング補題適用よりも、少なくともイホの方がかなり面白いです。）無限の数の（ドット）記号とそれに対応する無限の数の規則があれば、規則の大部分がドットカウントによってパラメータ化されているので、文法を書くことは非常に簡単です（より正確には文法テンプレートです）。したがって、理論的には、最初にスキャンして使用するドットの最大数を見つけ出し、テンプレートから対応する有限のCFGを生成することによってドット表現を解析することができます。実際には、これはCFGの述部を使用することによって行われます。したがって、パーサージェネレーターを使用してパーサーを作成することができます（パーサージェネレーターを使用してパーサーを作成することができます）。述語（ANTLRは、例えば、私は個人的には、左回帰の除去を回避するためにボトムアップジェネレータを使用します）。

ドット表記法には、独自の "括弧少なくとも理論的には、必要以上にドットを使用することができるからです。 CFGを自動生成する（理論的ではあるが実用的ではない）アルゴリズムを使って遊んでいたとき、私はドット最小化がより簡単であることを発見しました。私はマシンで読み取り可能なPMをテストするためのコピーを見つけることができませんでしたが、私が行ったすべての検索で、ドットミニマムではない表現は見つかりませんでした。私は、それが強烈な整頓の結果であるのか、ドット最小限の表現だけが合法であるという考えであるのか分かりません。

Answer 2

ここに興味深いアプリケーションがあります。 Perl6を使用すると、言語を拡張し、新しい演算子を追加し、既存の演算子と比較して優先順位を定義することができます。以下のコードサンプルは、演算子*..*などを定義しています。以下のテストは合格です。

use v6; 
use Test; 

sub infix:<*.> ($a, $b) is looser(&infix:<+>) { $a * $b } 
sub infix:<.*> ($a, $b) is looser(&infix:<+>) { $a * $b } 
sub infix:<*:> ($a, $b) is looser(&infix:<*.>) { $a * $b } 
sub infix:<:*> ($a, $b) is looser(&infix:<.*>) { $a * $b } 

sub infix:<+.> ($a, $b) is looser(&infix:<*.>) { $a + $b } 
sub infix:<.+> ($a, $b) is looser(&infix:<.*>) { $a + $b } 
sub infix:<+:> ($a, $b) is looser(&infix:<*:>) { $a + $b } 
sub infix:<:+> ($a, $b) is looser(&infix:<:*>) { $a + $b } 

# Tests 

is 1 + 3 .* 2, 
    (1 + 3) * 2; 

is 1 *. 3 + 2, 
    1 * (3 + 2); 

is 1 *. 2 +. 2, 
    (1 * 2) + 2; 

is 2 *: 2 + 3 .* 4, 
    2 * ((2 + 3) * 4);