- 筆者はもともとC/Pascal/Adaを書いていた
- Standard MLを書くようになり、手続き型のデータ構造を(SMLに)変換してみた
- 幾つかのデータ構造は、簡単に変換でき、より簡潔にもなった
- ただし、必ずしも全てのデータ構造が簡単に変換できる訳ではなかった
- 破壊的な更新が使いたい！ (けどStandard MLにはないのでどうすれば...)
- 文献調査したけど、ほとんど情報が見つからなかった
- 自分で研究を始めた
- 8年たって、知見がいろいろと溜まったので、本にまとめます
- ただし、全ての破壊的なデータ構造の効率的な(SMLでの)実装方法が見つかった訳ではない
- この本が、以下の目的に役立つことを望みます
- 関数型言語プログラマの参考書として
- 関数型データ構造について学びたい人向けのテキストとして
- この本で紹介するデータ構造は、Standard MLで記述されている
- Standard MLの利点
- (1) 正格な言語: アルゴリズムの実行時間の推測を容易にする
- (2) 抽象データ型を記述するのに理想的なモジュールシステムを備えている
- ただし、基本的に、どの関数型言語でも実装可能
- Haskell, Lisp, etc にも簡単に適用可能
- 本書の大半の例はHaskell版が付録として載っている
- CとかJavaでも比較的直截的な対応する実装が見つかるでしょう
- ただしC言語はGCがないから、大変な時があるかも
- Haskell, Lisp, etc にも簡単に適用可能
- 本書は一般的なデータ構造自体の入門書ではない
- スタックとかキューとかヒープとか有限マップとかの基本的な抽象データ型は、もう知ってるよね？
- big-O記法等の、アルゴリズム解析の基礎も知っている前提
省略
- Cプログラマが効率的なデータ構造が必要になったら、沢山ある良書の中から探せば良い
- 関数型言語のプログラマは、そのような贅沢は享受できない
- 大抵の本は言語非依存を謳っているけど、実際にはそれは「手続き型的操作が可能ならば」という条件がつく
- この不公平を緩和するために、本書は関数型の観点からデータ構造を記述する
- 言語はStandard MLを使う (ただし、他の言語にも簡単に変換可能。序文要約参照)
関数型言語の方法論な利点は良く知られている:
- しかし、大多数のプログラムは依然としてCのような手続き型言語で書かれている
- この矛盾は、関数型言語は、歴史的に手続き型言語よりも遅かったという事実によって説明できる
- コンパイラ技術はいろいろと改良されてきているので、その差は縮まりつつある
- だけどコンパイラの改善では、不適切なデータ構造の使用による性能劣化には対処できない
- 残念なことに、既存の文献は、この点(適切なデータ構造)に関してあまり良いアドバイスを与えてくれない
何故、関数型データ構造は、手続き型のものよりもデザインするのが難解なのか？
- (1) 効率の観点から云えば、破壊的な更新(代入)がないのは、大きなハンディキャップ
- 破壊的更新は危険だけど、適切に使えば凄く効果的
- 手続き型データ構造は、しばしば代入に致命的に依存しているので、関数型プログラムには別の解法が必要
- (2) 関数型データ構造は(手続き型のそれよりも)より柔軟であることが期待されている
- 関数型データ構造は、更新を行った後に、新旧の両方のバージョンのインスタンスが参照可能
- 複数バージョンをサポートするデータ構造は 永続(persistent) と呼ばれる
- 一度に一つのバージョンしかサポートされないデータ構造は 短命(ephemeral) と呼ばれる
- 関数型言語では、全てのデータ構造が自動的に永続化されるという特性を有する
- 手続き型のデータ構造は、典型的には短命
- 手続き型プログラマは、その永続化版が要求された際に、その実現がより複雑でかつ漸近的により非効率だとしても驚かないだろう
- 関数型データ構造は、更新を行った後に、新旧の両方のバージョンのインスタンスが参照可能
さらに、
- 理論家は、関数型言語は手続き型言語よりも、いくつかのシチュエーションでは本質的に非効率であることを示唆する、下限を確立している
- これらを考慮すると、関数型データ構造は時々"踊る熊"のようにも見える (上手にではなくても、踊っていること自体が驚き)
ただし実際には、状況はそこまで気がめいるものではない。
後続の章では、関数型データ構造の効率を、手続き型での最適な実装に対して、漸近的に同程度となるように工夫することが、往々にして可能であることを見ていく。
多くの(逐次)関数型言語は 正格(strict) か 遅延(lazy) のいずれかに分類できる:
- 評価順序の違い
- 関数の引数の扱い方に顕著な差が出る
- 正格言語: 引数は、関数の本体の前に評価される
- 遅延言語: 引数は、
demand-driven fashionで評価される- 評価されないまま関数に渡され、処理を続けるために、実際に結果が必要となった時に初めて評価される
- また、一度評価された結果はキャッシュされ、次回以降はその結果が再利用される (memoization)
両者は一長一短:
- ただし正格評価は漸近的な複雑さを推測しやすいという点では、明確に優れている
- どの式がいつ評価されるかが、文法上の見た目とほとんど一致している
- 遅延評価では、熟練者でも特定の式がいつ(when or even if)評価されるかを予測するのが難しい
- そのような言語のプログラマはしばしば、実行時間を見積もるために、言語が正格であるかのように扱うことがある
それぞれの評価順序は、データ構造のデザインと解析方法に影響を与える:
- 正格評価: 最悪ケースのデータ構造について言及することが可能
- 遅延評価: 償却ケースのデータ構造について言及することが可能
- 両方の種類のデータ構造について述べるためには、両方の評価順序をサポートする言語が必要
- 本書では、StandardMLを、遅延評価をサポートするように拡張する (see: Schapter4)
データ構造(data structure) という用語は、以下のようないろいろな(and 互いに関連した)意味で使われて紛らわしい:
- 抽象データ型(abstract data type):
- これは「型とその型に適用される関数の集合」を表す
- 本書ではこれを 抽象(abstraction) と呼ぶ
- 抽象データ型の具体的な実現:
- 本書ではこれを 実装(implementation) と呼ぶ
- 実装 は具体的なコードである必要はない (具体的なデザインで十分)
- データ型のインスタンス:
- 例: 特定のリストや木
- 本書ではこれを基本的には オブジェクト(object) あるいは バージョン(version) と呼ぶ
- ただし、特定のデータ型は、しばしばそれら独自の用語を持っているので、その場合はそちらに従う
- we will refer to stack or queue objects simply as stacks or queues
- A unique identity that is invariant under updates: (更新群を跨いで、不変項となるユニークなidentity)
- 例: スタックベースのインタプリタの話:
- 時間共に内容(version)が変わるにも関わらず、単に"the stack"と呼称することがある
- 本書ではこのidentityを 永続identity と呼ぶ
- 主に永続データ構造の文脈で問題になり得る
- 手続き型言語なら大抵は、ポインタの値(reference cell)が等しければ、永続identityも等しいと見做せるので簡単
- 「同じデータ構造の異なるバージョン群」と話す時は、それらのバージョン群が同じ永続identityを共有していることを意味する
- 例: スタックベースのインタプリタの話:
Standard MLとの関係:
- 抽象: signatures
- 実装: strucgures or functors
- オブジェクト(or version): values
- 永続identity: 明確な対応物なし
operation という用語も同じように重複した意味を持つ:
- 抽象データ型が提供する関数群: function or operator と呼称
- 上記関数群の適用: operation と呼称
- 全ての目的に沿うような効率的なデータ構造群のカタログを提供することは試みない (a hopeless task!)
- 代わりに、効率的な関数型データ構造をデザインするための、一握りの一般的なテクニックに集中する
- それぞれのテクニックを使った基礎的なデータ構造の実装例もいくつか紹介する
- これらのテクニックを理解すれば、実際の要求に応じた、データ構造の選択や実装が行えるようになるでしょう
本書は三部構成となっている:
- 第一部: 基礎的なデータ構造への導入
- 第二章: 基礎的なデータ構造をどう永続化するか
- 第三章: 三つの良く知られたデータ構造をStandardMLでどう実装するか
- 第二部: 遅延評価と償却の関係について
- 第四章: 遅延評価への導入 (基本コンセプトとStandardMLの拡張について)
- 第五章: 基本的な償却テクニックとそれらが永続データ構造を分析するためには不適切な理由
- 第六章: 遅延評価が償却と永続化を調停する方法。償却コストを解析するための二つの方法も紹介。
- 第七章: 正格と遅延を併用した場合の強力さ。償却データ構造から最悪ケースデータ構造への機械的な変換方法。
- 第三部: 関数型データ構造をデザインするための汎用的なテクニック集
- 第八章: __lazy rebuilding__について
- 第九章: __numerical representations__について
- 第十章: __data-structural bootstrapping__について
- 第十一章: __implicit recursive slowdown__について
- 付録: Haskellコード