C# で学ぶ関数指向概念超入門(?) / 実際に輸入してみた実験の記録

↑ C# Advent Calendar 2019 13 日目です ↑

この記事は、

• プログラミング自体が興味の対象な人
• プログラミング言語の穴を見つけては楽しくなるタイプの人 (いるのか？)
• 関数指向プログラミングにそこそこ馴染みある人

みたいな人を対象にしています (誰得)。

---

C# のいろんなネタ探しを兼ねて、長らく「過去から未来まで、コード中に書かれるであろう全ての正規表現を一切滅ぼすことを使命とした代替ライブラリ」を書いていたのですが、気がついたら関数指向プログラミング的な仕掛けが (意図せず) あれこれ混入していたので、そこらへんを適当にピックアップしつつ、いくつか馴染みがなさそうな概念について解説してみます。
とか言って、ある程度関数指向を知ってる人向けです。

型クラス的なインターフェース

インターフェースは型クラスのようなものとはよく言われますが、まあ外から差し込みができるできないとかの違いはあるけどだいたい似たようなものです！似たようなものとして使うことができます！

さっそく例ですが、

public enum Ordering { LT, EQ, GT }

public interface IComparable<T>
    where T : IComparable<T>
{
    Ordering CompareTo(T other);
}

TComparable Max<TComparable>(TComparable first, TComparable second)
    where TComparable : IComparable<TComparable>
    => first.CompareTo(second) switch
    {
        Ordering.LT => second,
        Ordering.GT => first,
        _ => first, // EQ
    };

メソッドの引数/戻り値としてインターフェースを直接扱う代わりに、ジェネリック型の引数を取って型引数の制約にインターフェースを指定するように書き換えているだけですね。
この Max メソッドの例では、単純にインターフェースを引数に取る場合とは異なり、first と second が「同じ型でなければならない」という重要な制約が課されています。単に同じインターフェースを実装しているだけでは、その実体が同じ型であるかどうかまでは分からないのですね。
また、戻り値の型を引数と同じ具象型にできているところもポイントです。ジェネリクスを利用しなかった場合、どうやっても IComparable<T> のインターフェースを返すことまでしかできません。
値型でも参照型でも関係なく具体的な型に沿ってメソッドを生成できるので、ボクシングの回避にも使えます。

ところで、

    where TComparable : IComparable<TComparable>

このような、型制約でインターフェースの型引数に「それ自身の型」を渡しているものを勝手に「自己言及型引数」と呼んでいますが、こうするとメソッドに渡すオブジェクトの型と IComparable<TComparable> の TComparable が同じものでない限りコンパイルが通らなくなるので、IComparable<T> の有効な実装を自己言及に制限することができます。
TComparable の実体が仮に IComparable<X> を実装していたとしても、TComparable と X が一致しないので Max に渡されることを防げるのです。
これはインターフェースを型クラス的に使うために必須ではないですが、こういうテクニックも有効活用できるよという話でした。

最後にインターフェース定義の方の、

public interface IComparable<T>
    where T : IComparable<T>

この T に対する制約は実際のところ必要ではないのですが、実装者へのアノテーションとして定義してあると親切かと思って入れています。運用上ではこれ以外の定義は許容されないわけなので。

つかいどころ

RankNTypes

C# でもインターフェースを悪用すればランク2型のようなものを再現することができます。

myfunc :: forall a. a -> (forall x. Show x => x -> a -> String) -> String

例えばこんな (適当な) 関数を定義したいと思います。
C# では、こうです。

public string MyFunc<A>(A a, ISomeFunc<A> f)
    => ...;

public interface ISomeFunc<T>
{
    string Invoke<X>(X x, T a)
        where X : IShow;
}

さすがにいろいろめんどくさいですが、まあ、なんかできました。ジェネリックなインターフェースの中に型制約付きなジェネリックメソッド定義を持たせることで、型が合います。
これデリゲートとラムダ式が Higher rank types を公式にサポートしてくれたらなーーーって思いますね！！！

つかいどころ

存在型

存在型は関数指向というよりはむしろオブジェクト指向の考えに近いので……。

public interface IX<T, T2>
{ }

public class X<T, T2, T3, T4> : IX<T, T2>
{ }

単純にインターフェースを介するときに型引数のいくつかを隠すことで共通化します。はい、普通ゥーのオブジェクト指向ですね！
インターフェースではなく抽象クラスでやるパターンもあります。
隠した型を使う処理は、シグネチャに表れないように普通にクラス内メソッド中に書けばいいだけです。

つかいどころ

不動点

みんなだいすき Fixed point

「関数 f の不動点」とは、f(x) = x となる x のことです。
この不動点を「計算する」関数が fix で、fix に f を渡すと x が手に入ります。この fix を不動点コンビネータと呼びます。
fix(f) = f(fix(f)) で定義され、fix(f) = x です。

C# でもちょっと変形してるけど定義そのままみたいなのが使えます。主に Lazy<T> とかラムダ式とかを使って作ります。

// × 自然な定義だけどこれは無限再帰して動かない
T Fix<T>(Func<T, T> f)
    => f(Fix(f));
// ○ 値を関数で包んで評価タイミングを調整可能にしたもの
Func<T> Fix<T>(Func<Func<T>, Func<T>> f)
    => () => f(Fix(f))();
// ◎ さらにパラメータを任意の T に一般化した形
Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f)
    => x => f(Fix(f))(x);

正格評価な環境だと最初の定義では Fix(f) の評価が無限再帰して止まらないので、f の代わりに x => f x を使うなどして評価タイミングを遅らせます。

つかいどころ

ちなみに、「x = f(x) となる x」という不動点の定義をそのまま書き下したような書き方もあって、効率の面でも有利であるため実際の Haskell では

fix f = let x = f x in x

のような実装が採用されています。
C# でも、工夫すれば同じようなことできます！

末尾呼び出し最適化

C# は、実は条件を満たすことで末尾呼び出しをジャンプに置き換えることができます。つまり、ちゃんと工夫すれば、無限な再帰的呼び出しを真っ当に実行できるワンダーなコードが書けます。

一応先に用語を整理しておくと、

• 末尾再帰
  • 関数の評価手続きの最終ステップが「自身の呼び出し」であるもの
• 末尾再帰最適化
  • 関数が「末尾再帰」になっているとき、関数定義自体を一つのループ構造にリライトするコンパイラ最適化
• 末尾呼び出し
  • 関数の評価手続きの最終ステップが「何らかの関数の呼び出し」であるもの
• 末尾呼び出し最適化
  • 関数の「末尾呼び出し」を、コールスタックを積まずにジャンプに置き換えるコンパイラ最適化

末尾再帰の概念は末尾呼び出しの特殊化されたパターンに過ぎないのですが、末尾再帰最適化は (たいてい) 中間言語レベル、末尾呼び出し最適化はアセンブリレベルでの最適化になるので、最適化の文脈では2つはやや毛色が違う扱いをされることが多いです。

末尾再帰最適化が効く言語はそこそこ数がありますが、末尾呼び出し最適化を行えるランタイムはそう多くなかったと記憶しています。そういう意味では、.NET のランタイムは結構ステキ。
ただし、肝心の末尾呼び出しが最適化される条件がやや厳しい (ここ最近の新機能でさらに厳しくなった) ので、アセンブリに手を加えて条件を緩和するハックも利用して実用レベルにしています。

つかいどころ

必要に駆られて作った絶対末尾呼び出し最適化したい人向けビルドツール

CPS 変換

CPS 変換というのは、一般的に、一連の手続きをぶつ切りにして小さい手続きのチェーンに変換し、再帰的に呼び出すような構造に変換することをいいます。
型の上では、値 a を関数 forall r. (a -> r) -> r に置き換えることに相当します。
例えば a -> b で型付けされる関数を CPS 変換すると a -> (b -> r) -> r になります。

---

ここでおなじみ Factorial くんに登場していただき、末尾呼び出しとそうでないもの、そして CPS 変換の定義を並べてみました。でもよくある内容だし長いので読まなくてもいいです。

末尾じゃない普通の定義

int Factorial(int x)
    => (x == 0) ? 1 : Factorial(x - 1) * x;

Factorial(3) == <Factorial(3 - 1)> * 3
| Factorial(2) == <Factorial(2 - 1)> * 2
| | Factorial(1) == <Factorial(1 - 1)> * 1
| | | Factorial(0) == 1
| | (1) * 1 == 1
| (1) * 2 == 2
(2) * 3 == 6

末尾再帰

int Factorial(int x, int acc)
    => (x == 0) ? acc : Factorial(x - 1, acc * x);

Factorial(3, 1) == <Factorial((3 - 1), (1 * 3))>
| Factorial(2, 3) == <Factorial((2 - 1), (3 * 2))>
| | Factorial(1, 6) == <Factorial((1 - 1), (6 * 1))>
| | | Factorial(0, 6) == 6
| | 6
| 6
6

/* ↑ は ↓ とみなせる */

| Factorial(3, 1) == <Factorial((3 - 1), (1 * 3))>
| Factorial(2, 3) == <Factorial((2 - 1), (3 * 2))>
| Factorial(1, 6) == <Factorial((1 - 1), (6 * 1))>
| Factorial(0, 6) == 6

CPS 変換による末尾再帰

int Factorial(int x, Func<int, int> cont)
    => (x == 0) ? cont(1) : Factorial(x - 1, acc => cont(acc * x));

Factorial(3, (x => x)) == <Factorial((3 - 1), (x => x * 3))>
| Factorial(2, (x => x * 3)) == <Factorial((2 - 1), (x => (x * 2) * 3))>
| | Factorial(1, (x => (x * 2) * 3)) == <Factorial((1 - 1), (x => ((x * 1) * 2) * 3))>
| | | Factorial(0, (x => ((x * 1) * 2) * 3)) == <(((1 * 1) * 2) * 3)>
| | | | (((1 * 1) * 2) * 3) == <((1 * 2) * 3)>
| | | | | ((1 * 2) * 3) == <(2 * 3)>
| | | | | | (2 * 3) == 6
| | | | | 6
| | | | 6
| | | 6
| | 6
| 6
6

/* ↑ は ↓ とみなせる */

| Factorial(3, (x => x)) == <Factorial((3 - 1), (x => x * 3)>
| Factorial(2, (x => x * 3)) == <Factorial((2 - 1), (x => (x * 2) * 3))>
| Factorial(1, (x => (x * 2) * 3)) == <Factorial((1 - 1), (x => ((x * 1) * 2) * 3))>
| Factorial(0, (x => ((x * 1) * 2) * 3)) == <(((1 * 1) * 2) * 3)>
| (((1 * 1) * 2) * 3) == <((1 * 2) * 3)>
| ((1 * 2) * 3) == <(2 * 3)>
| (2 * 3) == 6

---

通常の再帰関数は、自身を呼び出し終わった後に「何か戻り値を処理する手続き」が残るのに対して、末尾再帰とは、呼び出し終わった後の処理が「戻り値をそのまま返すしかやることがない状態」になっているものを指します。
ということは、この返すだけの処理は省略しても結果が変わらなくて、最後の計算結果を直接使えばいい気がしますね！これが「末尾再帰は機械的に最適化が可能 (できるだけで必ずするとは言っていない)」という意味です！

ここで、CPS 変換とは、本来末尾再帰にならないような再帰関数を何でも末尾再帰に変換できてしまうマジックです。
再帰関数内の「何か戻り値を処理する手続き」自体を関数にしてしまえば、「続きの処理」をなくすことができます！
コード例を見比べてみると、CPS では通常の再帰定義と同等の処理がそのままフラットに展開されていることが分かります。
まあ、これは実際にやってみて慣れないと分からないやつなので、覚えたいなら実際に何か作ってみたほうが早いです。

CPS 変換を利用して再帰的な呼び出しをなんでも末尾呼び出しにできるということは、C# でも任意の再帰的な処理を末尾呼び出し最適化の対象にできるということです！素晴らしいですね！

つかいどころ

モナド

モナドが何なのかについては、以前書いた記事を見てもらった方が早いとして……。
C# でモナドを書くなら、ジェネリックなクラス A<T> に対して「T から A<T> を作れる関数」と「A<T> と T -> A<T2> な関数の2つから A<T2> が作れる関数」があれば、後はちょっとしたルールを満たせばモナドになります！簡単ですね！

つかいどころ

ちなみに、モナド的な性質を持っているなら、以下のような (拡張) メソッドを定義しておくと、Linq のクエリ構文を do 記法的に扱うことができます。
順次処理するような複数の計算を並べて書くときなどに、クエリ構文が使えると捗る場面がたまにあります。

• A<T2> Select<T1, T2>(this A<T1>, Func<T1, T2>)
  • これがないとはじまらない、クエリ構文を使うための必須メソッド。
  • クエリ構文最終段の select や、let キーワードを書いたときに使用される。
• A<T3> SelectMany<T1, T2, T3>(this A<T1>, Func<T1, A<T2>>, Func<T1, T2, T3>)
  • モナド的に使うにはこれが必要。
  • 多重 from が書けるようになる。
• A<T1> Where<T1>(this A<T1>, Func<T1, bool>)
  • do 記法でいう guard に相当。
  • 定義できると where キーワードが使えるようになる。

他にも GroupBy や OrderBy などクエリ構文を拡張できるメソッドはまだまだありますが、とりあえず主要なものだけ書きました。
あと、1引数の SelectMany (== bind) はクエリ構文のために定義する必要は無いです。

つかいどころ

おわり

はい。最初から最後まで、だから何？って感じの記事でしたね！

まあ、C# でもかなりアグレッシブな関数指向プログラミングが実際可能であることは分かりました。どれもうまいことオブジェクト指向の上に乗っけることができています。
ただ、本来的に言語仕様がそういう使い方を想定していないので、いざやろうとすると若干めんどくさい場面が多いです。
もう少し楽に書けるような言語仕様が増えてくれたらって思いますが、増える気配はないですね……きっと誰も使わないですし……。
でもでも、もっとカジュアルな感じに関数指向なら全然書けるので、みんなももっと Functional していってもいいと思います！

最後に、今回例に出したプロジェクトでは他にもいろいろチャレンジングなコードが書かれていて、とても C# とは思えないようなコードが散りばめられた極北プロジェクトに仕上がってるので、外面からでも内面からでも、もし興味が沸いたなら是非見ていって下さい。ループ文がなくても、ライブラリはつくれる。