無名関数のためのプレースホルダ構文の特異性　～Scala Advent Calendar 2015じゃないよ～

本当はScala Advent Calendarの記事として書こうと思っていたのですが、既にだいたい埋まってしまっていたので、自分のブログで書きます。Scalaistの皆さん、プレースホルダ構文、使ってますよね？

List(1, 2, 3, 4, 5).map(_ + 1) // List(2, 3, 4, 5, 6)

という風にして使うアレです。使ったことはなくとも、Scalaをギョームで使っておられる皆さんもギョームで使っておられない皆さんも一度は見たことがあるのではないかと思います。この構文、正確には、 Scala Language Specification 6.23.1で「Placeholder Syntax for Anonymous Functions」として定義されている機能ですが、長いのでプレースホルダ構文としましょう。ちなみに、

scala> Math.abs _
res2: Int => Int = <function1>

のようにして出てくるプレースホルダは、ここで言及するプレースホルダ構文と全く異なり、メソッド型の何かを関数型のオブジェクトに変換するものですので注意してください。何故こんなこと書いたかというと、このプレースホルダは意味解析時に作用する（従って、代入先などの型情報が考慮される）のに対して、この記事で触れるプレースホルダ構文は構文解析時に作用するからです。したがって、

このコード(A)

scala> List(1, 2, 3, 4, 5).map(1 + _ + 3)
res14: List[Int] = List(5, 6, 7, 8, 9)

と構文的に等価に見える(Scalaでは演算子呼び出しもメソッド呼び出しの構文糖にすぎないので）以下のコード(B)

scala> List(1, 2, 3, 4, 5).map(((1).+(_)).+(3))
<console>:8: error: missing parameter type for expanded function ((x$1) => 1.+(x$1))
              List(1, 2, 3, 4, 5).map(((1).+(_)).+(3))

が等価でないという結果が起きたりもします。ちなみに、ここから余分な括弧を取り除いただけの以下のコード(C)は無事にコンパイルできます：

scala> List(1, 2, 3, 4, 5).map((1).+(_).+(3))
res12: List[Int] = List(5, 6, 7, 8, 9)

なんかわけがわからないですね（この機能考えついた人はちょっとおかしい)。この記事の目的は、何故(A)と(C)はOKなのに、(B)はNGなのかを追求することです。これについて真面目に触れてる人はちょっと見当たらなかったので、Scala Language Specification(SLS、Scala言語仕様）を参照することにしました。

まず、6.23.1の最初の節を引用しましょう

An expression (of syntactic category Expr) may contain embedded underscore symbols _ at places where identifiers are legal. Such an expression represents an anonymous function where subsequent occurrences of underscores denote successive parameters.

構文カテゴリExprの式の中には_を埋め込むことができ（ただし、識別子を置くことがOKな場所に限る）、そのような式は無名関数（後続の_を残りの引数とするような）を表現している、と言っています。構文カテゴリというのは聞き慣れない言葉ですが、構文規則のことだと考えて間違いないです。この、構文カテゴリExprは次のようになっています。

Expr         ::=  (Bindings | id | `_') `=>' Expr
               |  Expr1
Expr1        ::=  `if' `(' Expr `)' {nl} Expr [[semi] `else' Expr] //if式
               |  `while' `(' Expr `)' {nl} Expr //while式
               |  `try' (`{' Block `}' | Expr) [`catch' `{' CaseClauses `}'] [`finally' Expr] //try式
               |  `do' Expr [semi] `while' `(' Expr ')' //do-while式
               |  `for' (`(' Enumerators `)' | `{' Enumerators `}') {nl} [`yield'] Expr //for式
               |  `throw' Expr //throw式
               |  `return' [Expr] //return式
               |  [SimpleExpr `.'] id `=' Expr //メンバへの代入
               |  SimpleExpr1 ArgumentExprs `=' Expr //receiver(arg1,..,argN) = expr 形式
               |  PostfixExpr //中置式またはそれに識別子を付けたもの
               |  PostfixExpr Ascription //PostfixExprに型注釈をつけたもの
               |  PostfixExpr `match' `{' CaseClauses `}' //match式

//は筆者がコメントを付けた場所ですが、まあだいたいScalaの式を表す構文規則ということでわかってもらえるかと思います。要は式を表す構文の中にはだいたいどこでも埋め込むことができるということです。さて、なんでそれだけの事を書くのにわざわざ「構文カテゴリ」などというものを持ちだしたかというと、_構文から構成される無名関数のスコープに関係してくるからなのです。続いて引用します

Define an underscore section to be an expression of the form :T where T is a type, or else of the form , provided the underscore does not appear as the expression part of a type ascription _:T.

underscore sectionというのは、

• _
• _ に型注釈を付けたもの

のどちらかということです。

An expression e of syntactic category Expr binds an underscore section u, if the following two conditions hold: (1) e properly contains u, and (2) there is no other expression of syntactic category Expr which is properly contained in e and which itself properly contains u.

再び、構文カテゴリExprが出てきました。構文カテゴリがExprであるような式eがunderscore section uを束縛する、というのは、e全体が無名関数を表していて、uがその仮引数を表現しているという意味です。その条件として、

(1) e properly contains u

が挙げられているのは、たとえば

List.map(1, 2, 3, 4, 5).map(_)

が

List.map(1, 2, 3, 4, 5).map(x => x)

のように解釈されたりしないということです。

(2) there is no other expression of syntactic category Expr which is properly contained in e and which itself properly contains u.

これは、eの中にuを「真に含む」（u = eでない)ような他の構文カテゴリExprであるような式が存在してはならない、平たく言うと同じような構造がネストしていないということを言っています。

If an expression e binds underscore sections u1,…,un, in this order, it is equivalent to the anonymous function (u′1, ... u′n) => e′ where each u′i results from ui by replacing the underscore with a fresh identifier and e′ results from e by replacing each underscore section ui by u′i.

eがunder score section u1～unを束縛する（つまり、eが無名関数の全体で、u1～unがその仮引数としてみなされる）とき、無名関数が生成されるということを言っています。

以上を踏まえて、(A)、(B)、(C)について考えてみましょう。

まず、(A)です。

List(1, 2, 3, 4, 5).map(1 + _ + 3)

単純に考えて、解釈は

List(1, 2, 3, 4, 5).map((x) => 1 + x) + 3)

か

List(1, 2, 3, 4, 5).map((x) => 1 + x + 3)

のどちらかになりますが、結果が後者になるのは何故でしょうか。これには、無名関数を構成する（元の式）eが構文カテゴリExprでなければいけないという条件が絡んでいます。中置演算子を適用した式1 + _は、さらに外側に中置演算子を適用した式1 + _ + 3があり、構文カテゴリExprには属さずに、構文カテゴリInfixExprに還元されて止まってしまうため、構文カテゴリExprに「昇格」できないのです（下記規則参照。構文カテゴリInfixExprが再帰的に定義されていることがわかりますね）

PostfixExpr  ::=  InfixExpr [id [nl]]
InfixExpr    ::=  PrefixExpr
               |  InfixExpr id [nl] InfixExpr

そして、式1 + _ + 3について、それより外側をみると、メソッド呼び出しの実引数を表す規則ArgumentExprsに突き当たり、そこから1 + _ + 3の構文カテゴリは、Exprs -> Exprという風になり、Exprへの還元が行われます。

SimpleExpr    ::=  SimpleExpr1 ArgumentExprs
ArgumentExprs ::=  `(' [Exprs] `)'
                |  `(' [Exprs `,'] PostfixExpr `:' `_' `*' ')'
                |  [nl] BlockExpr
Exprs         ::=  Expr {`,' Expr}

ここで、式1 + _ + 3が構文カテゴリExprになり、underscore sectionを束縛していることになるので、無名関数としては

(x) => (1 + x + 3)

が生成されます。結果として、

List(1, 2, 3, 4, 5).map((x) => 1 + x + 3)

となり、これはコンパイルを（当然ながら）通ります。

次に(B)について検討してみます。

List(1, 2, 3, 4, 5).map(((1).+(_)).+(3))

コードの字面だけをみたときの可能な解釈は、

((1).+(x => x)).+(3)

((x) => ((1).+(x)).+(3))

((x) => ((1).+(x))).+(3)

のいずれかになります。最初の解釈については、無名関数を表現する式eはunderscore section uを「真に」含まなければいけないという条件で否定されます。二番目の解釈については、

((1).+(_)).+(3)

が構文カテゴリExprである式

((1).+(_))

を真に含んでしまっているため（'('')'で囲まれた式は構文カテゴリExprに還元されます）、これも否定されます。最後の解釈では、それより内側に構文カテゴリExprの式を含まない最小の式が

((1).+(_))

になるため、結果的にこれが採用されます。

最後に、(C)について検討します。

List(1, 2, 3, 4, 5).map((1).+(_).+(3))

(B)と非常に類似していますが、式(1).+(_)を囲む括弧が存在しない点が(B)と異なります。結論から言うと、

式

(1).+(_)

は、メソッド呼び出しのレシーバとなっているため、SimpleExpr1までしか還元されず、さらにその外側の式

(1).+(_).+(3)

の時点でようやく構文カテゴリExprに還元されます。したがって、解釈としては、

(x) => (1).+(_).+(3)

のようになります。

ここまで書いてきましたが、プレースホルダ構文、本当にややこしいですね。このややこしさは主に、

• 構文解析の中ではたらく機能であるため、（言語仕様の）構文規則をみない限り、挙動を把握できない
• ボトムアップパーザで主に使われるreduce（還元）のような概念を知らないと、やはり挙動を把握できない

ことに起因しています。これだけややこしい機能ながら、普段は詳細を知らなくても、「なんとなく」動く辺り、うまく設計されているなとは思いますが、濫用するとよくわからないコンパイルエラーに邪魔されるので注意しましょう。