全てが式になる，全てが木になる，全てが式木になる

関数型プログラマはプログラムを木だと思ってるらしい，より

もいっこ yhara くんのところから．

関数型プログラマはプログラムを木だと思ってるらしい

gauche.nightで出た話題だけど、関数型プログラマはプログラムを木だと思ってるらしい。

(car (string-split 
       (string-reverse (string-upcase str))
       "\n"))            

うん、これは木だ。

head $ lines $ reverse $ upcase str

Haskellだと $ があるから見た目はネストしてないけど、実際には関数に関数の返り値を渡している。

そう、関数型プログラマは関数呼び出しの中に関数を書くことに抵抗がない。でもC言語とかだとさ、関数呼び出しの中に関数って書かないじゃん、普通。すごく短いやつを除けば、だいたい一旦変数に代入するでしょ。

そのへんの違いが関数型言語を学ぶときの抵抗になってるのかなぁと思った。

そういう目で見れば、Rubyのメソッドチェーンは「木構造を使わずに関数的な処理を書くための発明」っていう風に見えてきませんか？

この視点はいいなぁ．
実は C++ のストリーム演算子は関数に関数の返り値を渡すスタイル．でもやっぱり大多数のプログラマにとって，関数呼び出しは関数呼び出しだし，変数代入は変数代入，ストリーム演算子はストリーム演算子，みたいな意識の壁がある．

C# と木

C# はどうだろう？
出発点としてこんなのを考えてみる．

A(B(C(a), b, D(E(c), d, e)));

うん，これは木だ．

• A
  • B
    • C
      • a
    • b
    • D
      • E
        • c
      • d
      • e

これが木であること自体は悪くないし疑いようもない．しかも C# には C++ から受け継いだ関数オーバーロードやジェネリックメソッドの型推論，さらに C++ には無いジェネリックの制約という仕組みがある．関数形で書くメリットは大きい．
一方で C/C++ から受け継いだ本能により， A( B( C(a), b, D( E(c), d, e ) ) ); という表記には拭いがたい抵抗感がある．というか括弧多すぎだろう．そこで甘い奴を混ぜて飲みやすくしてみる．そう，Extension Methods．

Extension Methods

A(B(C(a), b, D(E(c), d, e)));
// ↓
a.C().B(b, c.E().D(d, e)).A();

だいぶ飲みやすくなった．括弧のネストレベルが明らかに減っている．でも意味するところの木は最初のまま．オーバーロードやジェネリックメソッドの型推論はまるまる温存されている．IntelliSense も絶好調．これも「木構造を使わずに関数的な処理を書くための発明」と言って良いでしょう．花丸．
でもこれだけだともったいない．木にはいろんなものが接ぎ木できるはず．もっと考えてみる．

Anonymous Types, Member Initializers, Collection Initializers

新しく追加する要素が接ぎ木できるためには条件がある．条件とは，それが式であること．例えばこの木に，「型定義」の式を接ぎ木できるようにしてみたい．

a.C().B(new {Name="hauhau", Age=666}, c.E().D(d, e)).A();

• A
  • B
    • C
      • a
    • new AnonymousType<string,int>
      • "hauhau"
      • 666
    • D
      • E
        • c
      • d
      • e

実際には，「型定義」の部分だけ外に切り出されて，残るのはコンストラクタの呼び出しだけ．残るのはやっぱり木だ．
もっと接ぎ木してみる．例えばコンストラクタ呼び出し直後の定型的なプロパティセット．

a.C().B(new {Name="hauhau", Age=666}, c.E().D(new MyClass() { ID = 123 }, e)).A();

• A
  • B
    • C
      • a
    • new AnonymousType<string,int>
      • "hauhau"
      • 666
    • D
      • E
        • c
        • MemberInit
          • new MyClass()
          • set_ID
            • 123
      • e

プロパティへのセットは，今まで関数呼び出しの引数には書けなかった*1．が，もはやそれは制限ではない．
だいぶ長くなってきたのでここでちょっとコードを整形．括弧のネストレベルが下がっているので，昔よりは楽なはず．

a.C()
 .B(new {Name="hauhau", Age=666},
    c.E().D(new MyClass() { ID = 123 }, e))
 .A();

もうひとつだけ足してみよう．コレクションへの要素の追加．

a.C()
 .B(new {Name="hauhau", Age=666},
    c.E().D(new MyClass() { ID = 123 },
            new Dictionary<string, string>() { {"Hello", "World"} }))
 .A();

• A
  • B
    • C
      • a
    • new AnonymousType<string,int>
      • "hauhau"
      • 666
    • D
      • E
        • c
        • MemberInit
          • new MyClass()
            • set_ID(int)
            • 123
        • ListInit
          • new Dictionary
          • ElementInit
            • Add(string, string)
              • "Hello"
              • "World"

これでまたひとつ定型処理を木に組み込めた．
ここで挙げたのは順に Anonymous Types，Member Initializers，Collection Initializers と呼ばれる C# 3.0 の新機能．こいつら全てが式なのは偶然ではなく意図的なもの．と中の人も言っていた．
でも実はこれが最後じゃない．C/C++ の呪縛を引きずっている限り，ドットと括弧がついて回る．これをキーワードとホワイトスペースのパターンに置き換えて，そろそろ新しい世界に旅立とう．そしてこんにちはクエリ式．

クエリ式

from i in Enumerable.Range(0, 100) select i;

この特別甘い奴がクエリ式．実際にはこれは Extension Methods への変換として定義されている．変換してみる．

Enumerable.Range(0, 100).Select( i => i );

Extension Methods もただの甘い奴なのでさらに元に戻す．

Enumerable.Select( Enumerable.Range(0, 100), i => i );

結局，クエリ式はこの木の表現形式の新種．Extension Methods の変換ルールが単純だったのと違い，クエリ式の変換ルールはキーワードごとに結構たくさんあったりする．あとそこそこ複雑なのが混ざってたり．
ここで基本をもう一度おさらい．ポイント1，C# 3.0 でも関数評価戦略は変わらない．だから木は絶対作られる．CPU がマシン語で動くように，コンパイラは絶対に木を作る．どのように評価されるかは木で決まる．
ポイント2，確かにソースコードに木は直書きできた．でも大きな木は書きにくいから変数使おうぜと C/C++ プログラマは言った．一方 C# は変換ルールを入れてみた．Extension Methods のような単純な置き換えルールでも，ソースコードの見た目はがらりと変わった．でも置き換えで How は変わってない．お，How の木が生で見えることはそんなに重要じゃなかったのかも*2．と，ここ重要．
ポイント3．せっかく置き換えるなら何をしたいかに注目した文法の方が良いよね？ ボクたち機械じゃないし．
じゃあちょっと比べてみてみましょう．

クエリ式1

var checkingTypes = new[]
{
    new {DisplayName = "short", Type = typeof(short), Priority = 10},
    new {DisplayName = "ushort", Type = typeof(ushort), Priority = 10},
    new {DisplayName = "void", Type = typeof(void), Priority = 1},
};

from method in typeof(string).GetMethods()
join check in checkingTypes on method.ReturnType equals check.Type
select new { Method = method, CheckingType = check };

これは下の式と等価．

typeof(string).GetMethods().Join(
       checkingTypes,
       method => method.ReturnType,
       check => check.Type,
       (method, check) => new { Method = method, CheckingType = check });

ん？ 全然悲惨じゃない？ まあそうかも．

クエリ式2

from x in Enumerable.Range(0, 100)
from y in Enumerable.Range(0, x)
select new { X = x, Y = y };

これは下の式と等価．

Enumerable.Range(0, 100)
    .SelectMany(x => Enumerable.Range(0, x), (x, y) => new { X = x, Y = y });

クエリ式2'

ネストもう一個増やす．

from x in Enumerable.Range(0, 100)
from y in Enumerable.Range(0, x)
from z in Enumerable.Range(y, 100)
select new { X = x, Y = y, Z = z }

これは下の式と等価．

Enumerable.Range(0, 100)
    .SelectMany(x => Enumerable.Range(0, x), (x, y) => new { x = x, y = y })
    .SelectMany(s => Enumerable.Range(s.y, 100), (s, z) => new { X = s.x, Y = s.y, Z = z });

さらにこれは下の式と等価．まあ書かないよね．

Enumerable.SelectMany(
    Enumerable.SelectMany(
        Enumerable.Range(0, 100),
        Enumerable.SelectMany(x => Enumerable.Range(0, x), (x, y) => new { x = x, y = y })),
    s => Enumerable.Range(s.y, 100), (s, z) => new { X = s.x, Y = s.y, Z = z }
);

クエリ式3

一部の大きなお友達が大好きな let も使ってみる．

from x in Enumerable.Range(1, 100)
let fizz = x % 3 == 0 ? "Fizz" : ""
let buzz = x % 5 == 0 ? "Buzz" : ""
let num = (x % 3 != 0 && x % 5 != 0) ? x.ToString() : ""
select fizz + buzz + num;

これは下の式と等価．

Enumerable.Range(1, 100)
    .Select(x => new {x = x, fizz = (x % 3) == 0 ? "Fizz" : ""})
    .Select(local0 => new {local0, buzz = local0.x % 5 == 0 ? "Buzz" : ""})
    .Select(local1 => new {local1, num = local1.local0.x % 3 != 0 && local1.local0.x % 5 != 0 ? local1.local0.x.ToString() : ""})
    .Select(local2 => local2.local1.local0.fizz + local2.local1.buzz + local2.num);

これを古典的な文法で書くのはやめとこう．怖いから．

一旦変数に代入する，と等価な木

何となくまとめ．まずクエリ式じゃない方から．この時点で確かにすごい．何がすごいって，「一旦変数に代入する」という行為がなんとなく木の中に再現できていること．Anonymous Types が式なのは伊達じゃない．つまり，

変数宣言 & 代入;
変数宣言 & 代入;
関数呼び出し;

という文の並びは，ひとつの木に変換できる．そして実際に何が起きるかは，木を見れば分かる．木は How を全て含んでいるから．
でも弱点も何となく分かってくる．見る感じどうもクエリ式じゃない奴は長文耐性が無い．Extension Methods の力を持ってしてもここまでか，と．変数 (もどき) を増やすことによって How の木が複雑になるのは仕方がないにしても，その複雑さをソースコードがそのまま反映してしまっている感じ．それから同じ記号がたくさん出てきている．ラムダ式も目立ちすぎ．念のためメールアドレスは二回入力して下さい，じゃないんだから．これも長文を書くためには弱点．
ひるがえってクエリ式．こいつは確かに SQL からインスパイアされた文法かもしれないけど，長文耐性という意味では結構イケている．クエリ式の良いところは，定型的なパターンで出てくる部分木の綺麗な圧縮表現になっているところ．ついでに，ホワイトスペースとキーワードで区切られる文法なので，括弧とドットと矢印が激減．
もちろん，クエリ式が長文向きということが，Anders が本来意図していたものとあっているかはかなり怪しい．というか怪しんでおいて欲しい．本人に直接聞いたわけではないわけで．「これは C# ででかい木を書けという Anders 神のお告げ！」，と電波バリ3で受信したのはただの妄想で，その結果みーくんは山で嘘つきに，まーちゃんは川で壊れてしまってさあ大変．かもしれない．嘘だけど．
でもまあ長文向きの文法は，何をしたいかが前面に出た良い文法だね，というと本当っぽく聞こえる嘘なのか，嘘っぽい真実なのか．SQL の文法が，「悪くない」とは思うんですけどね．なんとなく．レゴみたいにがちゃがちゃくっつけていったとき，経営破綻する上限額が結構引き上げられた感じがというか．

クエリ式とネストと let とわたし

ちょっとだけ Extra Stage を追記．
クエリ式は構造表現に記号を使わないので見た目とてもフラット．見慣れた波括弧もなし．セミコロンはひとつだけ．でも実は簡単にネストできる．
例えばこれ．「2000年から2009年までの13日の金曜日は？」

var ft13 = from year in Enumerable.Range(2000, 10)
           from date in from month in Enumerable.Range(1, 12)
                        let numDays = DateTime.DaysInMonth(year, month)
                        from day in Enumerable.Range(1, numDays)
                        select new DateTime(year, month, day) // ← month, numDays, day のスコープここまで
           where date.Day == 13 && date.DayOfWeek == DayOfWeek.Friday
           select date;

let を使うと「一旦変数に代入」も可能．

var ft13 = from year in Enumerable.Range(2000, 10)
           let daysInThisYear = from month in Enumerable.Range(1, 12)
                                let numDays = DateTime.DaysInMonth(year, month)
                                from day in Enumerable.Range(1, numDays)
                                select new DateTime(year, month, day)
           from date in daysInThisYear // ← ここでは month も numDays も day も見えない
           where date.Day == 13 && date.DayOfWeek == DayOfWeek.Friday
           select date;

ここで let daysInThisYear に注目．右辺はクエリ式セミコロン抜きという典型的な入れ子構造．そして daysInThisYear の定義で使った変数達，month に numDays に day のスコープは，セミコロンが無くてもきちんと閉じる．begin 〜 end で囲む言語を知っていればこれはそこまで不思議じゃない．begin 〜 end を from 〜 select x に置き換えれば分かるはず．
インデントはご自由に．白い悪魔は居ないので．インデントしてもしなくてもスコープは変化なし．
しかしなんというどんでん返し．木で書くか「一旦変数に代入するか」からスタートし，特殊な変換ルールによって木構造を捨て，さらにクエリ式という変換ルールを導入し，たどり着いた先でまた同じ話．ちなみにクエリ式の読みやすさの 9 割は，狡猾なインデントでできるのでそこのとこよろしく．
もちろん今さら言うまでもないことだけど，クエリ式の木と，最初に捨てた実際に評価される生の木は全くの別物．間に二回も変換入ってるし*3．そして同じ悩むにしてもクエリ式の木の方が考えがいがある．世界はループしているようで，着実に前に進んでいる，はず．波括弧とドットは消しておいて正解でしょ？
かくして，クエリ式の長文耐性はネストによってさらに延長されましたとさ．

まとめ

というわけで本当にまとめ．

• C# 3.0 で入った変な文法はよく見れば式．これは全くもって意図的とのこと．
• でかい木を簡単に作れるかどうかは，言語の文法に大きく依存している．生成される木が大きいから難しい，と短絡的には言えない．
• C# の従来の式は「どのように評価されるか」の木と見た目が直接対応していた．Extension Method では見た目との対応が若干崩れる．クエリ式ではことごとく崩れる．でもコンパイル時には必ず「どのように評価されるか」の木に変換される．
• クエリ式はネストできる．let を使うと「一旦変数に代入」も可能．従来文法よりも自然にネストが書けるのは二重丸．ネストしたクエリ式を読むときは，コードの意図に注目．正しく書かれていれば，等価な「どのように評価されるか」の木が生成される．

ではまあ皆様楽しい C# の night life を．

参考

• 26.7.1 クエリ式の変換
  • クエリ式から Extension Methods 記法の式への変換ルールは一回目を通しておくと吉．実際書くときに意識する必要はないですけど，まあ教養みたいなものとして．
• シェルのリダイレクトを「こわいものなし」というくらい完全に理解しよう - 檜山正幸のキマイラ飼育記
  • 代入で示した方が分かりやすくなることもある，という話．おもしろ．
• Taking LINQ to Objects to Extremes: A fully LINQified RayTracer
  • クエリ式 = 木を体現した何か．まあ見れば分かるビジュアル系サンプルコード．

*1:書くとしたら，プロパティにセットするというデリゲートを作って渡すことになる

*2:まあ諸悪の根源は括弧な気もするけど

*3:let はとんでもない生の木に変換される恐ろしい子．