🎵ミニマリストのためのコンピュータ言語Bracmat入門#5 アトム(atom)のこと 非線形パターンマッチングの謎とは？ 未来のチート言語
「：」はパターンマッチング二項演算子だが覚えるのはたくさんの接頭辞 まず「？」
ここは他の言語と比較したほうがいいかもしれない。まずは「？」マークだが。パターンマッチングの最初の個所ででてくる。「：」が二項演算子なので左辺LHS「マッチ対象（主語）」：右辺RHS「マッチ条件（パターン）」で見ていただきたい。
{?} 20+a+b+c:?+b+? { Is there a term "b" in the sum (20+a+b+c) ?}
{!} 20+a+b+c
S 0,00 sec
正規表現で書くなら「?+b+?」が「.*b.*」みたいな感じの式になると思う。ただマッチングの条件が異なるみたい。
If the match operation is to succeed, the pattern must be similar to the subject.マッチ演算が成功するためには、パターンが主語（左辺）に似ていなければなりません。
正規表現では「.*」はゼロ回以上の何かの文字だが、Bracmatの「？」はもっともやっとしている。ちょっとややこしくなってしまうが、正規表現での「？」は一文字の文字という意味で別の意味がある。
「？」receiving variables「受け」変数 「！」giving variables 「立ち」変数 が下りなく非線形パターンマッチング
receiving variables (those that are preceded by a question mark), but also giving variables (those that are preceded by an exclamation mark).
パターンマッチの二項演算子「：」を中心に「？」は受信変数「！」送信変数に分けられるということのようだ。こちらは概要説明でアトムという言葉は出てこない。ここのポイントは、正規表現でいう後方参照みたいなことが、受信と送信の順番でできるという点だと思う。javascrptでは\n(nは数字)とか￥ｎ（ｎは数字）で知られる。（こっから先はしばらくは正規表現の話）
正規表現での後方参照とは
例えば /apple(,)\sorange\1/ は "apple, orange, cherry, peach" の 'apple, orange,' にマッチします。
ちょっとわかりづらいが、ここでは後方参照でマッチした「,」をオレンジの後ろでパターンとして使っている。後方参照の話はイメージとして持っているだけで、こっからはbracmatの話になるが
Bracmatでの非線形パターンマッチングとは？
If an occurrence of a variable is receiving and a later in the pattern giving, than the pattern is said to be non-linear.（受信変数のあとに送信変数が来たら、そのパターンは「非線形パターン」と呼ばれる）
非線形という言葉をもちだしたのはbracmatで、この場合状況が非線形というのは、イメージとして腑に落ちる気がしている。bracmatでのサンプルを見ればより分かりやすいだろう。
{?} ( (teabag.1904) (sonar.1906) (computer.1941) (triode.1906) (zeppelin.1900)
: ? (?invention1.?year) ? (?invention2.!year) ?
& !invention1 !invention2
)
{!} sonar triode少し先の表現が出てくるが、頑張って解析すると、二項演算子としては「：」と「＆」が出てくる、「＆」については後で話すが、大きくは(teabag.1904) (sonar.1906) (computer.1941) (triode.1906) (zeppelin.1900)という左辺の表現について? (?invention1.?year) ? (?invention2.!year) ?という右辺のパターンが成り立つかを聞いている句だが、あらかじめinvention1やyearのアトムのバインディングは行われていない。つまり、全体の構成を（非線形に？）パターンマッチしたのちにそれぞれのアトムにマッチしたキャラクターが入っていくことになる。ここでやっと「？」に書かれていた後半の説明が腑に落ちる。
then the matched part of the subject is captured by this variable or member. In other words, pattern matching can have assignment as a side-effect.
副作用としてinvention1に代入が起こると書いてある。副作用として?invention1に代入が起こって、?yearにも代入が起こるなら?yearには"1906"がアサインされるわけで、後方参照的に?invention2を選ぶ相手としては!yearの結果となる表現、つまり「sonarの次に1906が入ってる表現」triodeがinovention2に入ってくる。すごい、というかうっとりする。期待感しかない。
他の言語との引き合い(javascript)
後方参照的なマッチングの事を「非線形」というのは、初めて聞いたが、一連のやりとりがまだわからなくても。分割代入という概念は最近の言語では多いみたいだ。javascriptではこんな感じ
分割代入＆後方参照＝非線形パターンマッチング？
今までいろいろな技術を広く浅く振れてきたつもりだが、分割代入と後方参照を合わせるとすごいチート技みたいなものが使えている気がする。何がそれを可能にしているのだろうか？
後方参照については、多くの言語が大域変数（グローバル変数）として扱っていて、その悪い帰結が９０年代のPerlのダラー変数だと、javascriptを作ったブレンダンアイク先輩入っていた。（単純明快なハイコンセプト映画に対抗して、了解不能なローコンセプト言語とでもいうか）、bracmatは確かこの構文をしっかりしたスコープ管理のもとやっているコンセプトだと読んだ気がする。本当にそうなら、めちゃめちゃかっこいい。
Bracmat (github.com/BartJongejan/Bracmat) はすべてのパターンをサポートし、可換演算子 (+ と *) を含む式を自動的に正規化する。
これは，"commutative PM "の不足を一部補うものである。
非線形パターン（1つのパターン内で同じ変数が複数現れるパターン）に対するパターンマッチをサポートしている。 また、パターンマッチのよるデータの分解方法が複数ある場合でも、パターンマッチのための探索空間を効率よくバックトラッキングする。
非線形処理とバックトラッキングには関係があります。
非線形処理:
非線形処理は、処理が一定の順序やパターンに従わず、分岐や繰り返し、あるいは異なる処理経路を取ることを指します。
これには、再帰やバックトラッキング、分岐などのテクニックが含まれます。
バックトラッキング:
バックトラッキングは、問題を解決するための特定の手段としての非線形処理の1つです。
ある選択を行い、その選択が問題の解決に繋がらない場合に、前の状態に戻り（バックトラックし）、異なる選択を試みるというアプローチを取ります。
言い換えれば、バックトラッキングは非線形処理の一形態であり、非線形的な探索を行いながら最適な解を見つけるための手法として用いられます。
いいなと思ったら応援しよう！
