その日は来ないと弾言しちゃいます。
[Swiftで気になった所]
代数的データ構造を彷彿とさせる魔改造を施されたenumですが、再帰的データ構造が出来そうで出来ないのでガッカリ感が有ります。
enum List { // (!) Recursive value type 'List' is not allowed
case Car(AnyObject)
case Cdr(List?)
}
> 正座して実装される日を待ちます。
[Swiftで気になった所]: http://qiita.com/ykst/items/3aba08ba1bf8955004d1
なぜなら、それが出来るようにするということはSwiftの型システムのありようを根本から崩壊させてしまうことになるからです。
結論を述べる前に、上記のコードをあえてCで書いたらどうなるのか見てみましょう。
````C
typedef void *AnyObject;
typedef union List {
AnyObject car;
union List cdr;
} List;
どこがおかしいかおわかりになるでしょうか?
そうです。union List cdrがおかしい。試しにコンパイルしてみると、clangではdefinition of 'union List' is not complete until the closing '}'というエラーが出ます。Listの中にListを入れることは、数学的にはできても物理学的にはできないのです。
なので、再帰的データ構造は、データそのものの代わりにデータへの参照を入れることで実現されています。マトリョーシカではなくロケット鉛筆なわけですね。
Cにおける参照とはポインターのことなので、上記コードは
typedef void *AnyObject;
typedef union List {
AnyObject car;
union List *cdr;
} List;
として、*をcdrの前に加えるだけでいいわけです。
ところが、Swiftにポインターはありません1。どうしたらよいでしょうか?
参照型なのはClassだけ
The Swift Programming Languageにはこう明記されています。
"Classes Are Reference Types”
そうです。Classを使えばいいのです。
import Foundation
class List {
var car:AnyObject = NSNull()
var cdr:List? = nil
}
これは問題なく動きます。
以下のようにすれば、さらによいでしょう。
class Atom<T> {
var value:T
init(_ value:T) {
self.value = value
}
}
enum Node<T> {
case None
case Data(Atom<T>)
case Link(Pair<T>)
}
class Pair<T> {
var car:Node<T> = .None
var cdr:Node<T> = .None
}
enumとclassが相互参照することで、再帰的なenumが実現しました。
structとenumは実体型
上記のコードは、こう書きたくなる誘惑に駆られます。
enum Node<T> {
case None
case Data(T)
case Link(Pair<T>)
}
ところが、これは動きません。なぜかといえば、The Swift Programming Languageにも"Structures and Enumerations Are Value Types"とあるように、enumは実体型だから。実体型ということは、実際に必要なメモリーの量を割り出して確保しなければならないということですが、上記のコードではTの大きさがわからないと必要なメモリーの量もわかりません。
そこでAtomというclassで包んでいる(wrap)わけです。classは参照型なので、sizeof(Atom<T>)は必ずCにおけるポインターのサイズと一致します2。
実は、サイズが固定であれば包装はclassでなくても構いません。Atom<T>のかわりに[T]でも()->Tでも動きます。が、一番メモリーを食わないのはラッパークラスを使う方法。見た目もこれが一番すっきりしていると思います。
マシン語が透けて見える
モダンな言語のほとんどは、ポインターを追放しています。その代償としてデータ構造の実装もまた隠蔽されているのですが、@shi3zがポエムに歌ったように、Swiftはポインターを追放したにも関わらずマシン語が透けて見える言語でもあります。型がstruct、enum、classと分かれているのは透明度が一番高い部分ではないでしょうか。
まとめ
- 再帰的データ構造を有限のメモリーで実現するには、参照が必要
- Swiftにおける唯一の参照型は
class -
classとenumを相互再帰することで、再帰的enumが実現できる。
Dan the Self-Referential Coder