Perl 6の正規表現について

以下の文章は[正規表現技術入門](http://gihyo.jp/book/2015/978-4-7741-7270-5)に掲載予定で書いたものですが，結局ボツにして3年間ほど私のMacBookの奥底でひっそりと眠っていたものです．
[YAPC::Okinawa](http://yapcjapan.org/2018okinawa/) で @dankogai さんと話していてPerl 6の正規表現について本文章を書いたことを思い出したので，せっかくの機会ですのでQiitaにて公開します．

(本文中の「[1-9]章」というのは正規表現技術入門の章立てを指しています)
(\cite, \ref, table などのコマンドでまだ未処理な部分がありますが，随時アップデートしていきます)

**なお，以下の文章は2014年の年末から2015年の年始にかけて書かれたモノです．現在と成っては不正確な(あるいは古臭い)記述があるかもしれませんが，その点はご勘弁ください**

---
# Larryの黙示録：Perl 6 の正規表現の仕様変更から学ぶ
2章で解説したように，Kleeneによって理論の世界で生みだされた正規表現は，Thompsonの「最初の実装」からコンピューターの世界に導入され，Perlを始めとしたプログラミング言語の進化と共に成長してきました．

Perlは正規表現をプログラマにとって「使うのが当たり前」と言われるレベルに普及させただけでなく，様々な拡張機能の導入も積極的に行ってきました．キャプチャしない括弧`(?:)`，先読み`(?=)`，後読み`(?<=)`，アトミックグループ`(?>)`等の`(?`から始まる拡張機能の構文などはPerlが最初に導入し，その後多くの処理系に広まったものです．機能・構文の両面において，Perlが「プログラマのための現代の正規表現」の形成に与えた影響はとても大きいのです．

そのPerlの正規表現がPerlの次期バージョンであるPerl 6 において劇的なまでに仕様を変更します．Perlの生みの親であるLarry Wall は彼の著書『Programming Perl 第四版』\cite{Wall2012}の中で Perl 6 は Perl 5 と比べてもはや別の言語であることを強調しています．

> That 6 is deceptive though; Perl 6 is really a “kid sister” language to
> Perl 5, and not just a major update to Perl 5 that version numbers have trained you to expect.

> Perl 6 は Perl 5の ``妹'' のような言語であって，6というバージョン番号から想像させられるような単なるPerl 5のメジャーアップデート言語では無い．

特に正規表現に関しては「全くの別物」と言っても良いでしょう．
Perl 5 との**互換性を捨ててまで**，Perl 6 では一体何を目指しているので
しょうか．

本節では，Perl 6 の仕様に関する[公式資料](http://perlcabal.org/syn/)


 - **Apocalypse (黙示録)**：Perlの生みの親Larry Wall による，5までの
	   Perlにおける反省点や改善策，Perl 6の構想．
 - **Exegesis (釈義)**： Perl 6の開発リーダー__Damian Conway__に
	   よる，Apocalypseに対する詳細な解説及び具体的なアプローチの提案．
 - **Synopsis (梗概)**：以上を纏めた Perl 6 の基本仕様．


を参考に Perl 6の「正規表現の仕様変更」に注目して，これまでの問題点とその改善策について解説していきます．なお，これら公式資料(英語)については，『正規表現メモ』で有名な木村浩一氏による(非公式な)[日本語訳](http://www.kt.rim.or.jp/~kbk/regex/perl6.htm)が公開されています．


本書は「Perl 6の入門書」ではなく「正規表現の入門書」です．そのため，Perl6 でのプログラミング作法などには触れず，あくまで「正規表現の仕様変更」に解説範囲を絞ります．

Perl 6での正規表現の仕様変更から，はたして**正規表現のあるべき未来**のようなものが視えてくるのでしょうか．これからの「正規」の話をしましょう．

##良く使う構文ほど簡潔に：キャプチャする括弧とキャプチャしない括弧
これまでの正規表現では，普通の括弧`()`でパターンを囲むとキャプチャ情報を保存します．そこでPerlは`(?:)`という構文をキャプチャしない括弧として導入し，その後多くの処理系にその構文が広がりました．

しかし，キャプチャしない括弧は良く使われるわりに`(?:)`という構文はあまりにも長ったらしくはないでしょうか．
「使用頻度の高い記号ほど短いデータで表現する」ことは可読性の観点からもデータ圧縮の観点からも基本的な原則ですが，`(?:)`という構文はその原則に従っているのでしょうか．

ここでApocalypse からLarry のコメント(の木村氏による和訳)を引用しましょう．
<quote>

**貧弱なハフマン符号化**

> Huffmanは、一般的なキャラクタを少ないビットで表現し、あまり登場しないキャ ラクタを 表すにはより多くのビットで表現するというデータ圧縮の方法を発明した。 この原則はもっと普遍的なものであるが、言語デザイナーは 「簡単なことは簡単に。難しいことを可能に」という''別の''Perlのスローガンを 考慮に入れるだろう。しかし、我々はいつも与えられた助言を容れているというわけではない。 ここで、

```
    (?<=...)
    (??{...})
```

> という二つの正規表現構造について考えてみよう。 日々の使用で一般的なのはどちらだと思う? 長いほうじゃないかな・・・

現在の正規表現においては、貧弱なHuffman符号化の例は多くある。ここで以下の例について考えてみよう。

```
    (...)
    (?:...)
```

> グループ化をすることは捕獲(capturing)することよりも稀なことなんだろうか? そして二つのgobbledygookyキャラクタは価値あるものなのだろうか? このように、同じ長さを持ったそう表現すべきではない構造が数多くある。たとえば

```
    (?:...)
    (?#...)
```

> が挙げられるだろう。

> グループ化は埋め込みコメントの機能よりも重要である。が、これら二つは現在のところ同じ長さである。

これらの状況を鑑みて，Perl 6 ではキャプチャするグループ化に変わらず`()`を，**キャプチャしないグループ化にブラケット**`[]`を採用しています．`(?:regex)`と`[regex]`，たった2文字の違いですが使用頻度から考えると劇的な違いです．本章(8章)の冒頭で触れた，読みやすい正規表現のための「正規表現を簡潔に書く」という原則にも嬉しい変更です．

グループ化が短くなるのは大歓迎ですが，ここで1つ疑問が出てきます．ブラケット構文`[]`は元々文字クラスのための構文だったのですが，では一体文字クラスはどう書くことになったのでしょうか？ 答えは次項で明らかになります．

## 正規表現の呪文化を避ける：メタ構文の導入
Perl にキャプチャしない括弧`(?:)`と先読み`(?=)`が導入された当時，`(?`から始まる形にした理由は`(?)`という正規表現が認められていないからだったそうです\cite{Friedl:2006:MRE:1209014}．その後，Larryは`(?`から始まる形でつぎつぎと拡張機能を追加していきました．

一方で， Apocalypse において Larry は次のように語っています．

**異なる事柄が同じように見える**

> 以下の構造について考えてみよう:

```
    (??{...})
    (?{...})
    (?#...)
    (?:...)
    (?i:...)
    (?=...)
    (?!...)
    (?<=...)
    (?<!...)
    (?>...)
    (?(...)...|...)
```

> これらは皆、同じように見える。しかしこれらのうちの幾つかは全然異なることをするのである。 特に、`(?<...)` は `(?>...)`の反対の意味ではない。 視覚的な問題はLispのごとき括弧の使いすぎにある。 プログラムは違いがはっきりとわかればより読みやすくなる。

これは「ごもっとも」という言葉以外に感想が出てこないぐらいにまっとうな意見です．`(?`という非直感的なシーケンスに拡張機能を詰め込みすぎているのです．

これらの問題は，拡張機能のための構文に割り当てることができるメタ文字があまりにも少ないという事実からも生まれているのです．
Perl 5までの正規表現の拡張機能の追加は，既存の正規表現との互換性を保ちつつ行われてきました．互換性のためには「直感的な構文」や「統一的な構文」等の新規導入は不可能だったわけです．その結果，拡張構文の構文は初心者から見ると非直感的で記号の不可解な組合せによる「呪文のような」構文となってしまったのです．

**少なすぎるメタキャラクタに依存しすぎている**
> 我々のHuffmanトラブルの多くは新しい機能を何も壊さずに古い構文に押し込めようと していることに起因している。 `(?...)` 構造は到達点としては成功した。 しかしそれは古い皮袋の中の新しいワインである。もっと成功した例は 控え目マッチング`*?` に関するハックである。しかし、これは既存の文法の中で動作するように選択するのに 我々がたった三つのキャラクタしか持っていなかったことの問題を示している。 バックスラッシュシーケンスについても似たような問題がある。

> 言語的な複雑性のWaterbed理論([Larryがプログラミング言語に関して述べている原則](http://en.wikipedia.org/wiki/Waterbed_theory)は、ど こかを押し下げればほかのどこかが競り上がると言っている。少数のメタキャラクタに制限しようとしたならば、 ほかのどこかが複雑になるのである。 だから、この複雑さを避ける策はもう少しメタキャラクタを増やすこと であるのが明らかであるとわたしには思えるのである。そしてわたしが増やそうとしている メタキャラクタは・・・いや、これは後回しにしよう。

Perl 6 からはあらゆる拡張機能はアングルブラケット`<>`で囲む**メタ構文**(__meatsyntax__)と呼ばれる構文によって統一的に表現されることになりました．さらに，新たにコロン`:`が**バックトラックの制御構文のためのメタ文字**として導入されることになりました．上記で問題として揚げられていた`(?`から始まる拡張機能は，Perl 6のメタ構文では下の表のように書くことが出来ます．

<table>
<th>機能</th><th>Perl 5</th><th>Perl 6 (メタ構文)</th><tr>
<td>  変数展開   </td><td>  (??{$rule})   </td><td>  &lt;$rule>  </td><tr>
<td> 埋め込みコード </td><td>  (?{ code })   </td><td> { code }      </td><tr>
<td>インラインコメント</td><td>  (?#...) </td><td> &lt;'...'>  </td><tr>
<td>キャプチャしないグループ<td> (?:...) <td> [...] </td><tr>
<td>     先読み   </td><td>   (?=...) </td><td> &lt;before ...> </td><tr>
<td>   否定先読み  </td><td> (?!...) </td><td> &lt;!before ...> </td><tr>
<td>    後読み    </td><td>    (?<=...) </td><td> &lt;after ...> </td><tr>
<td>  否定後読み   </td><td>   (?&lt;!...) </td><td> &lt;!after ...> </td><tr>
<td>アトミックグループ</td><td> (?>...) <td> [...]: </td><tr>
<td>条件式</td><td> (?(cond)yes|no) </td><td> [ cond :: yes | no ] </td><tr>
</table>


特に先読み・後読みに関しては劇的に読みやすくなっているのではないでしょうか．構文の長さだけで比べると多少長くなってはいますが，本章(8章)冒頭で触れた，読みやすい正規表現のための「正規表現を説明的に書く」という原則に従った改善だと言えるのではないでしょうか．


実は，Perl 6にて「キャプチャしないグループ化」にブラケット構文`[]`を奪われた文字クラスは，メタ構文中にブラケット構文を用いる構文に変更されました．つまり，Perl 5 まで`[a-z]`と書いていた文字クラスは，Perl 6 では`<[a-z]>`と記述されるのです．
「文字クラスは良く使う構文のはずなのに，その構文が長くなっては『良く使う構文ほど簡潔に』の原則に反するのでは？」と思われた読者もいるかもしれません．しかし，Perl 6ではそれに対しての解答も持ち合わせています．この点については続く節で解説します．

Perl 6では，バックトラック制御構文として`:`や`::`や`:::`はそれぞれ**異なる意味を持った演算子**となります．コロン構文によってどのようにバックトラックを制御するのか，1節まるまる使って解説したい欲求に駆られますが，前述した通り本書はPerl 6の入門書ではないため省略することにします．興味のある読者はSynopsisを参照しください．

## スペースとコメントが自由に挿入できる/x モードがデフォルトに
Perl 6 ではデフォルトで正規表現中の空白や改行が無視されます．すなわち，Perl 5までの`/x`モードがデフォルトとなったのです．

Perlの文化は他のプログラミング言語の文化に比べても特に正規表現を多用する文化だと言われています．そんな Perl の正規表現文化においてもっとも良く使われる正規表現のオプションの1つは`/x`でしょう．
「良く使う構文ほど簡潔に」という原則は同時に「良く使う機能ほどデフォルトに」という原則も導出します．正規表現中に埋め込む空白は，「リテラル」としての空白よりも「正規表現の整形」のために使われる方が多いという Larry の判断でしょう．

## 正規表現のモジュール化：grammarとrule
本章(8章)の冒頭で「正規表現を短く書くコツ」として**正規表現を上手く部品化する**と述べました．いきなり長くて複雑な正規表現を書くのではなく，小さな部品から正規表現を組み立てていこう，というアプローチです．

Perl 6 では正にその機能を標準でサポートするようになりました．それが`grammar`と`rule`です．Perl 6では `rule`という単位で正規表現を記述し，`grammar`という単位でそれをモジュール化することができます．次のコードは`nmaem,age,addr,desc`の4つの`rule`(正規表現)を`Idenitity`という名前空間に纏めています．

```
     grammar Identity {
         rule name :w { Name = (\N+) }
         rule age  :w { Age  = (\d+) }
         rule addr :w { Addr = (\N+) }
         rule desc {
             <name> \n
             <age>  \n
             <addr> \n
         }
         # etc.
     } 
```

ここで定義した`Identity`内の`rule`は，アングルブラケットを用いて`<Identity.name>`という構文で参照することが出来るのです．

上のコードを見て，「`grammar`と`rule`の関係は，オブジェクト指向でいう所の`class`と`method`に似ているな」と思われた読者はいるでしょうか．実はただ単に見た目た似ているだけでなく，`grammar`は**継承**することができるのです．

```
     grammar Letter {
         rule text     { <greet> <body> <close> }
         rule greet :w { [Hi|Hey|Yo] $<to>\mu=(\S+?) , $$}
         
         rule body     { <line>+ }
         rule close :w { Later dude, $<from>\mu=(.+) }
         # etc.
     }
     grammar FormalLetter is Letter {
         rule greet :w { Dear $<to>:=(\S+?) , $$}
         
         rule close :w { Yours sincerely, $<from>:=(.+) }
     }
```


### 正規表現は，grammarは，ruleは再利用するもの
ユーザーが自由に定義できる`rule`ですが，Perl 6では標準で「良く使うrule」を提供しています．例えば`<wp>`は空白文字を，`<upper>`は大文字アルファベット，`<lower>`は小文字アルファベットとして定義されています．

Perl 6では「多用する正規表現は`rule`として定義して再利用する」という方針を全面に押し出しています．正規表現は再利用されるべきものなのです．これまでの多くのプログラミング言語では正規表現を再利用するのに十分な機能が与えられているとは言いがたい状況だったのです．

**いい加減正規表現をコピペする時代は終わらないものでしょうか．**

Perl 6に限らず，正規表現を再利用する仕組みは他の言語にも普及して欲しいものです．

### Perl自身の文法
Perl 6では`STD`と呼ばれる「Perl 6自身の文法」を表す`grammar`が提供されています．

```
     grammar STD {    # Perl's own standard grammar
          rule prog { <statement>* }
          rule statement {
                   | <decl>
                   | <loop>
                   | <label> [<cond>|<sideff>|';']
         }
          rule decl { <sub> | <class> | <use> }
          # etc. etc. etc.
     }
```


そのため，変数`$source_code`がPerl 6のコードである場合に

```
$parsetree = STD.parse($source_code)
```

というコードを実行するだけでPerl 6コードの構文木を得ることが出来ます．

## PEGを言語組み込みでサポート

```
$parsetree = STD.parse($source_code)
```

というコードで Perl 6 の構文解析が簡単に行えるように，ユーザー自身が定義した`grammar`に対しても`parse`メソッドを呼ぶことで構文解析を行うことが出来ます．

Perl 6では構文解析の機構にPEGを採用しているようです．
前節「正規表現よりも表現力の高い文法を使う」では，正規表現単体で扱うには複雑すぎる問題には，より強力な文法機能を使うことを提案しました．Perl 6におけるPEGの採用は正にこの提案にぴったり合致しています．

## 最長と早い者勝ちの両方に対応した選択演算
Perl 6での正規表現の仕様変更は構文だけではありません，マッチング機構に関する根本的な仕様もガラリと変わっています．

7章では，Perl 5までの正規表現エンジンを含む，バックトラック実行をベースとしたVM型正規表現エンジンは「早い者勝ち」のマッチングを行うことと解説しました．
一方，Perl 6からは選択`|`は「最長」のマッチングを優先するものとなりました．
これは劇的な仕様の変更です．

「早い者勝ち」のマッチングよりも「最左最長」のマッチングの方が直感的な方式だと考えることができるので，この仕様変更は歓迎されるべきだと著者は考えています．
選択演算において「早い者勝ち」ではなく「最長」のマッチングを採用するとい
う点は，マッチングの**並列実行の恩恵を受けやすい**という利点も考えられ
ます(実際，Synopsisにはその旨の記述がありました)．

Perl 6の偉い点は，`||`という構文で「早い者勝ち」用の選択演算も用意している点です．Perl 5までのマッチングのセマンティクスを好むのであれば，`||`を用いれば良いでしょう．

バックトラック演算の充実や2種類の選択演算の導入など，Perl 6の正規表現はプログラマがより**正規表現の挙動の細部をコントロールできる**仕組みを提供していることが分かります．

## キャプチャをより便利に
7章では，サブパターンが複数回文字列にマッチする場合は，サブマッチは上書きされることを説明しました．Perl 6からは，複数回マッチする場合は「サブマッチのリストを返す」という仕様に変更されました．

それに伴い，キャプチャのアクセス方法も根本的な見直しが行われています．特にPerl 5まではキャプチャする括弧の出現順に`$1,$2,$3,..`と参照する**フラットな**サブマッチの参照構造でしたが，Perl 6からは**括弧のネストに対応した**サブマッチの参照構造になっています．

下の表はネストしたキャプチャに対する Perl 5までの参照方法と Perl 6か
らの参照方法を示したアスキーアートをSynopsisから引用したものです．
ネストの構造を保っているため，本質的にPerl 6の参照構造のほうが可読性・メ
ンテナンス性ともに優れている言えるでしょう．

```
   # Perl 5...
   #
   # $1---------------------  $4---------  $5------------------
   # |   $2---------------  | |          | | $6----  $7------  |
   # |   |         $3--   | | |          | | |     | |       | |
   # |   |         |   |  | | |          | | |     | |       | |
  m/ ( A (guy|gal|g(\S+)  ) ) (sees|calls) ( (the|a) (gal|guy) ) /x

   # Perl 6...
   #
   # $0---------------------  $1---------  $2------------------
   # |   $0[0]------------  | |          | | $2[0]-  $2[1]---  |
   # |   |       $0[0][0] | | |          | | |     | |       | |
   # |   |         |   |  | | |          | | |     | |       | |
  m/ ( A (guy|gal|g(\S+)  ) ) (sees|calls) ( (the|a) (gal|guy) ) /;
```

## ここであげた変更点はごく一部
本節で紹介したPerl 6の正規表現の仕様変更は，重要なものから選んだつもりですが，本当にごく一部にすぎません．

本節を読んで Perl 6に興味を持った読者は，冒頭で紹介した Apocalypse,Exegesis, Synopsis 以外にも，以下の文献リストが参考になるかもしれません．


 - 竹迫良範氏による入門スライド『Perl 6 正規表現プログラミング』：
	   http://www.slideshare.net/takesako/perl6-regex-programming-with-rakudo
 - Teodor Zlatanov による `grammar`の解説記事『洗練されたPerl:
	   Perl 6文法と正規表現』：
	   http://www.ibm.com/developerworks/jp/linux/library/l-cpregex/
 - 大和利之によるオープンソースのPerl 6入門書の翻訳『Using Perl6日本
	   語版』(Webで読めます)：
	   https://dl.dropboxusercontent.com/u/877032/UsingPerl6_JA.html



## Perl 6の正規表現は受け入れられるのか
Perl 6の正規表現の仕様変更から，これからの正規表現のあり方を読み解くことができたでしょうか．著者の感想としては，Perl 6における正規表現の仕様変更の多く（全部とは言いませんが）は素晴らしいものだと思います．

読者に誤解してもらいたくないのは，本節は「Perl 6の使用を推奨」するという意図で書かれたものでは**無い**ことです．実際，現在のPerl 6の公式の処理系**Rakudo**(**ラクドスター**)のパフォーマンスは多くのプログラマにとって我慢できないものでしょう．

しかし，少なくとも Perl 6 の正規表現については，他のプログラミング言語にも影響を与えるべき素晴らしい点が多いと断言できます．例えばSchemeの処理系Gaucheも可変長後読みやリストを返すキャプチャなどの機能が， Perl 6に続き，Gauche 0.8.7 にパッチとして取り込まれました<footnote>http://practical-scheme.net/wiliki/wiliki.cgi?Rui:正規表現の拡張</footnote>．
願わくば「Perl 6の正規表現」に対応した grep 実装やライブラリ等も提供されると嬉しいのですが...

「Perl 6の使用を推奨する意図はない」とは言え，Perl 6の未来はどうなるのか，まともなパフォーマンスの実装は提供されるのか，果たしてプログラマに受け入れられるのか，行く先に大いに興味があります．

興味深いことに，2015年1月に開催される[FOSDEM](https://fosdem.org/2015/schedule/track/languages/)と呼ばれるイベントで，Larry WallがPerl 6に関する講演を行うようです．

**講演タイトル「Get ready to party!」**
> The last pieces are finally falling into place. After years of design and implementation, 2015 will be the year that Perl 6 officially launches for production use.

『正規表現技術入門』が出る頃(2015年4月14日に初版が発売されました)には Larry は既に講演を終えているはずです．2015年は Perl 6にとって，正規表現にとって，特別な1年になるのでしょうか．

1951年に生まれた正規表現は，1968年からプログラマの最高の相棒になり，それから半世紀近く過ぎた2015年でもその動向から目が離せそうにありません．