Magnet PatternとMethod Overloading

# はじめに
社内勉強会でMagnet Patternについてまとめて話したので、話した内容について記事にまとめました。その際に作成スライドは[こちら](https://speakerdeck.com/kentarousuzuki/magnet-pattern-to-method-overload)にアップロードしたので、スライドバージョンをみたい方はご覧下さい。

# Magnet Patternが解決する問題
今回紹介するMagnet Patternは[こちらのsprayのブログ](http://spray.io/blog/2012-12-13-the-magnet-pattern/)で詳しく紹介されており、こちらの実装を用いてAkka HTTPのcomplete関数などが実装されております。このブログでは、以下の様な文章を引用した上で、Scala APIをデザインする際に「名付け」の問題は大きな課題だとしています。そして、Magnet Pattern名付けの問題を解決すると述べています。
> There are only two hard things in Computer Science: cache invalidation, naming things and off-by-1 errors.
> —Phil Karlton (slightly adapted)

まずは、この名付けの問題とはどのような問題なのか、具体的に説明します。

## 名付けの問題とは?
例えば、以下の様な要件を想定します。
- `ListGenerator`に対して値を渡して、Listの返り値を得る
- 想定している引数と返り値は以下の表の通り

| 引数の値              | 引数の型      | 返り値                 | 返り値の型   | 
| -------------------- | ------------ | --------------------- | ---------- | 
| 1                    | Int          | List(1)               | List[Int]  | 
| "Hoge"               | String       | List(H, o, g, e)      | List[Char] | 
| List(1, 2)           | List[Int]    | List(1, 2)            | List[Int]  | 
| List("Hoge", "Fuga") | List[String] | List(H,o,g,e,F,u,g,a) | List[Char] | 

このような要件があった際に、想定される実装の例としては

```scala
val fromInt = ListGenerator.generate(1)
val fromStr = ListGenerator.generate("hoge")

// val fromInt: List[Int] = List(1)
// val fromStr: List[Char] = List(h, o, g, e)
```

のような実装が想定できます。
この時にListGeneratorに定義されるgenerateメソッドの名前を適切なものにしなければならないということが、ここで述べられている「名付け」の問題です。

## Method Overloadingを使った実装
さて、では実装にどのように要件を実現するのか考えましょう。例えば、`ListGenerator.generate`に引数を渡すとき、Scalaは静的型付け言語なので、引数に渡せる値の型をあらかじめ決めておかなければなりません。そこでMethod Overloadingを使って複数の型を渡せる様にします。

```scala
object ListGenerator {
	def generateFromInt(x: Int): List[Int] = x::Nil
	def generateFromStr(x: String): List[Char] = x.map(_.toChar).toList
}

val fromInt = ListGenerator.generateFromInt(1)
val fromStr = ListGenerator.generateFromStr("hoge")

// val fromInt: List[Int] = List(1)
// val fromStr: List[Char] = List(h, o, g, e)
```

いい感じですね。では、IntやStringだけではなく、List[Int]やList[String]も渡せるようにしましょう。すると以下のような実装ができます。
 
```scala
object ListGenerator {
	def generate(x: Int): List[Int] = x::Nil
	def generate(x: String): List[Char] = x.map(_.toChar).toList
	def generate(x: List[Int]): List[Int] = x
	def generate(x: List[String]): List[Char] = x.flatMap(_.map(_.toChar).toList)
}

val fromInt = ListGenerator.generate(1)
val fromStr = ListGenerator.generate("hoge")
val fromIntList = ListGenerator.generate(List(1, 2, 3, 4))
val fromStrList = ListGenerator.generate(List("hoge", "fuga"))
```

しかし、このコードはコンパイルしようとすると、以下のエラーが出力されます。

```
double definition:
def generate(x: List[Int]): List[Int] at line 4 and
def generate(x: List[String]): List[Char] at line 5
have same type after erasure: (x: List): List
        def generate(x: List[String]): List[Char] = x.flatMap(_.map(_.toChar).toList)
            ^
Compilation Failed
```

なぜ、エラーが出力されたのでしょうか? 

## 型消去とは?
出力されたメッセージを読んでみると`def generate`には同じ型が渡されていると書いてあります。今回のコードでコンパイルが失敗した原因は、型消去(type erasure)が起きたことでList[Int]とList[String]がListとして定義され、Listを引数として受け取るメソッドが重複したことです。型消去とは、簡単に説明すると、コンパイル時に総称型(ジェネリクス)のパラメータが消去されることです。今回のコードの場合は `List[Int]` と `List[String]` で別々に定義されていたメソッドで引数の型消去され、コンパイル後にはどちらも `List` として型が定義されます。そのため、List型以外にもOption型でも以下の様に型消去による型のコンフリクトが発生します。

```scala
object ListGenerator {
	def generate(x: Int): List[Int] = x::Nil
	def generate(x: String): List[Char] = x.map(_.toChar).toList
	def generate(x: Option[Int]): List[Int] = x.toList
	def generate(x: Option[String]): List[Char] = x.map(_.map(_.toChar).toList).getOrElse(Nil)
}

val fromInt = ListGenerator.generate(1)
val fromStr = ListGenerator.generate("hoge")
val fromIntOpt = ListGenerator.generate(Option(1))
val fromStrOpt = ListGenerator.generate(Option("hoge"))

// double definition:
// def generate(x: Option[Int]): List[Int] at line 4 and
// def generate(x: Option[String]): List[Char] at line 5
// have same type after erasure: (x: Option): List
//         def generate(x: Option[String]): List[Char] = x.map(_.map(_.toChar).toList).getOrElse(Nil)
//             ^
// Compilation Failed
```

このジェネリクスをコンパイルする時に型消去するのはJavaの仕様であり、[OracleのJava8のドキュメント](https://docs.oracle.com/javase/jp/8/docs/technotes/guides/language/generics.html)にも書かれています。
> ジェネリクスは型消去によって実装されます。ジェネリック型情報は、コンパイル時にしか存在せず、コンパイル後はコンパイラによって消去されます。このアプローチの主な利点としては、ジェネリック・コードと、パラメータ化されていない型(技術的にはraw型と呼ばれる)を使用するレガシー・コードとの間に、総合的な相互運用性が実現する点です。主な短所としては、パラメータ型情報を実行時に利用できない点と、動作が適切でないレガシー・コードと相互運用すると、自動的に生成されたキャストが失敗する恐れがある点です。しかし、動作が適切でないレガシー・コードと相互運用するときも、ジェネリック・コレクションに対して実行時の型の安全性を保証する方法があります。

## 定義するメソッド名を変える
引数の型消去による型の衝突を回避するためには以下のようにメソッドの名前を変更する必要があります。以下の例に示したコードではInt、String、List[Int]、List[String]からそれぞれに対応するList型を生成できるようにメソッド名を変えて実装してあります。

```scala
object ListGenerator {
	def generateFromInt(x: Int): List[Int] = x::Nil
	def generateFromStr(x: String): List[Char] = x.map(_.toChar).toList
	def generateFromIntList(x: List[Int]): List[Int] = x
	def generateFromStrList(x: List[String]): List[Char] = x.flatMap(_.map(_.toChar).toList)
}

val fromInt = ListGenerator.generateFromInt(1)
val fromStr = ListGenerator.generateFromStr("hoge")
val fromIntList = ListGenerator.generateFromIntList(List(1, 2, 3, 4))
val fromStrList = ListGenerator.generateFromStrList(List("hoge", "fuga"))

// val fromInt: List[Int] = List(1)
// val fromStr: List[Char] = List(h, o, g, e)
// val fromIntList: List[Int] = List(1, 2, 3, 4)
// val fromStrList: List[Char] = List(h, o, g, e, f, u, g, a)
```

確かに、こちらの実装だと引数の型消去が起きても、メソッドが異なるために型の衝突が発生しません。しかし、それぞれのメソッド名はgenerateFromXXとなっており、やや冗長な印象を受けます。この時期で紹介するMagnet Methodはこのような「名付け」の問題を解決するために使われます。

# Magnet Patternの仕組み
まずは、Magnet Patternの実装を見てみましょう。

```scala
trait ListGeneratorMagnet {
	type Out
	def list(): Out
}

implicit def intMagnet(x: Int) = new ListGeneratorMagnet {
	type Out = List[Int]
	def list(): Out = x::Nil
}

implicit def strMagnet(x: String) = new ListGeneratorMagnet {
	type Out = List[Char]
	def list(): Out = x.map(_.toChar).toList
}

implicit def intListMagnet(x: List[Int]) = new ListGeneratorMagnet {
	type Out = List[Int]
	def list(): Out = x
}

implicit def strListMagnet(x: List[String]) = new ListGeneratorMagnet {
	type Out = List[Char]
	def list(): Out = x.flatMap(_.map(_.toChar).toList)
}

object ListGenerator {
	def generate(magnet: ListGeneratorMagnet): magnet.Out = magnet.list()
}

val fromInt = ListGenerator.generate(1)
val fromStr = ListGenerator.generate("hoge")
val fromIntList = ListGenerator.generate(List(1, 2, 3))
val fromStrList = ListGenerator.generate(List("hoge", "fuga"))

// val fromInt: List[Int] = List(1)
// val fromStr: List[Char] = List(h, o, g, e)
// val fromIntList: List[Int] = List(1, 2, 3, 4)
// val fromStrList: List[Char] = List(h, o, g, e, f, u, g, a)
```

このコードを理解する上で、ポイントとなるのは `ListGeneratorMagnet` と `implicit def` です。そこでまずは `ListGeneratorMagnet` について説明します。

## ListGeneratorMagnet
このListGeneratorMagentは付けられた名前の通り、Magnet(磁石)としてメソッドと引数を結びつける役割をします。このListGeneratorMagnetには `type Out` と `def list(): Out` が定義されており、 `ListGenerator.generate` に渡す型ごとに具体的な実装をします。
例えば、intMagnetの実装を見ていきましょう。

```scala
implicit def intMagnet(x: Int) = new ListGeneratorMagnet {
	type Out = List[Int] // 受け取ったx: Intを変換した先の型
	def list(): Out = x::Nil // x: Intをtype Outに変換する具体的なロジック
}
```

intMagnetではまず、 `type Out = List[Int]` と実装されています。これはScala2.10で追加されたDependent Method Typeを利用しています。Dependent Method Typeはこれが定義されているインスタンスを変数として渡し、Dependent Method Typeを呼び出すことで、インスタンスで定義されている型を返す機能になっています。今回のコードではgenerateメソッドの返り値の型として定義されています。例えば、generateメソッドの引数にintMagnetを渡せばList[Int]が返り値の型として定義され、strMagnetを渡せばList[Char]を返すというようになります。したがって、今回の `type Out` には渡した引数の返り値として返したい値の型を定義します。
そして、intMagnetにはlist()が定義されています。ここには渡ってくる値を返したい値に変換するロジックを書きます。例えば、intMagetではInt型の値が渡ってきて、それをInt[List]に変換するロジックを書きます。同じようにstrMagentではStringをList[Char]に変換するロジックを書きます。そして、intMagnetやstrMagnetで実装されたlist()はListGeneratorでmagnet.list()のように呼び出されています。

## implicit def
さて、例として示したListGenerator.generateにはListGeneratorMagnetを渡すように定義されています。しかし、実際にメソッドを利用しているところでは`1`や`"hoge"`のようなListGenerarotMagnetではない値を渡しています。なぜ、そのような値を渡しても大丈夫なのか。それは`implicit def`で暗黙の変換をしているからです。例えば、generateメソッドに`1`が渡された場合を考えてみましょう。この時、intMagnetが定義されているために、generateメソッドに渡された`1`はInt型からListGeneratorMagnet型に変換されて、generateメソッドに渡されます。したがって、ここではimplicit defでListGeneratorMagnet型への変換方法が定義されていないFloat型をgenerateメソッドに渡した場合以下のようなエラーが出力されます。

```
type mismatch;
 found   : Float(1.0)
 required: ListGeneratorMagnet
val fromFloat = ListGenerator.generate(1.0f)
                                    ^
Compilation Failed
```

## Scala3での変更
先日、Scala3がリリースされました。

<blockquote class="twitter-tweet"><p lang="en" dir="ltr">🎺🎺🎺<br><br>After 8 years of work, 28,000 commits, 7,400 pull requests, 4,100 closed issues – Scala 3 is finally out!<br><br>Read more here: <a href="https://t.co/qyqRlVOjwY">https://t.co/qyqRlVOjwY</a></p>&mdash; Scala (@scala_lang) <a href="https://twitter.com/scala_lang/status/1393139114535444484?ref_src=twsrc%5Etfw">May 14, 2021</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

新しくリリースされたScala3では以前のものと比べて文法が変更されたものがあります。その中の一つに今回のMagnet Patternを実現するにあたって利用したimplicit defも含まれます。Scala3では暗黙の変換(implicit def)は以下の様に実装が変更されました。

```scala
given Conversion[String, Token] with
  def apply(str: String): Token = new KeyWord(str)
```

[Scala3のリファレンスより引用](http://dotty.epfl.ch/docs/reference/contextual/conversions.html)


この文法の変更を踏まえて、Scala3でMagnet Patternを実現と以下のコードのようになります。

```scala
import scala.language.implicitConversions
​
trait ListGeneratorMagnet {
	type Out
	def list(): Out
}
​
given fromInt:  Conversion[Int, ListGeneratorMagnet] with
	def apply(x: Int): ListGeneratorMagnet = new ListGeneratorMagnet {
		type Out = List[Int]
		def list(): Out = x::Nil
	}

object ListGenerator {
	def generate(magnet: ListGeneratorMagnet): magnet.Out = magnet.list()
}

ListGenerator.generate(1)
// val res0: ListGeneratorMagnet#Out = List(1)
```

# まとめ
この記事ではAkka HTTPのcompleteメソッドを実装でも利用されているMagnet Patternの仕組みについて紹介しました。sprayのブログでは「名付け」の問題を解決するためにMagnet Patternが紹介されました。ScalaではMethod Overloadingを使って同じメソッド名でも異なる引数の型を渡せる様に定義ができます。しかし、総称型の値を引数に定義すると、型消去によって引数の型が衝突することがあります。この問題を回避するためにgenerateFromInt, generateFromStringのようにメソッド名を変えて実装することができます。ただ、引数の型の衝突を回避するためにメソッド名を変更することは時に適切でない「名付け」をしなければならないこともあります。その問題を解決するためにMagnet Patternが使われます。Magnet PatternではDependency Type Methodでメソッドの返り値の型とそれぞれの型を変換するためのロジックを定義されたMagnetを引数に受け取るメソッドを定義します。さらに、そのメソッドに引数を渡すためにimplicit defで暗黙的に型を変換し、値を渡します。Scala3ではこの暗黙的に型を変換するための文法は変更されましたが。その文法を使うことで引き続きMagnet Patternを使って、コードを書くことができます。

# 参考URL
[spray | The Magnet Pattern](http://spray.io/blog/2012-12-13-the-magnet-pattern/)
[Java8 Generics](https://docs.oracle.com/javase/jp/8/docs/technotes/guides/language/generics.html)
[Scala3 Reference | Implicit Conversions](http://dotty.epfl.ch/docs/reference/contextual/conversions.html)