Mercurial > hg > Papers > 2014 > toma-master
annotate paper/chapter3.tex @ 47:e32c9a53310c
fix
| author | Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 06 Feb 2014 21:12:49 +0900 |
| parents | aa6de0f67a0a |
| children | 88b11a3afb93 |
| rev | line source |
|---|---|
| 43 | 1 \chapter{Haskellによる\\並列データベースの実装}\label{ch:impl} |
| 47 | 2 本章では, 並列データベース Jungle の実装について述べる. |
| 10 | 3 |
| 4 \section{木構造データベース Jungle} | |
| 47 | 5 非破壊的木構造データベース Jungle は, Haskell で実装された並列データベースである. |
| 6 非破壊的木構造の方法に則った関数を提供する. | |
| 23 | 7 |
| 47 | 8 % 本研究では, HTTP サーバ Warp と組み合わせて掲示板システムとして利用しているが, 他のシステムに組み込むことも可能である. |
| 9 Jungle の基本的な使い方の手順について説明する. | |
| 23 | 10 \begin{enumerate} |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
11 \item{木構造を保持する Jungle を作成する} |
| 23 | 12 \item{Jungle 内に新しい木を名前をつけて作成する} |
| 47 | 13 \item{木の名前を用いて, ルートノードの取得を行い, データを参照する} |
| 14 \item{もしくは, 木の名前を用いて, ルートノードの更新を行う} | |
| 23 | 15 \end{enumerate} |
| 16 | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
17 \subsubsection{Jungle が持つデータ型} |
| 47 | 18 Jungle が持つのデータ型を表\ref{tab:components}に表す. |
| 19 木構造の集まりを表現する Jungle, 単体の木構造を表現する Tree がある. | |
| 20 Node は子と属性を任意の数持てる. | |
| 21 データ型として定義することで, データ内部の型の整合性が保たれ, また型検査でエラーがないか検出することができる. | |
| 22 Jungle のデータ型について, ひとつずつ説明する. | |
| 35 | 23 |
| 34 | 24 \begin{table}[!htbp] |
| 25 \label{tab:components} | |
| 26 \begin{center} | |
| 27 \begin{tabular}{|c||c|} \hline | |
| 28 型名 & 概要 \\ \hline | |
| 47 | 29 Jungle & 木の作成・取得を担当する. \\ \hline |
| 30 Tree & 木の名前とルートノードの情報を保持している. \\ \hline | |
| 31 Node & 基本的なデータ構造, 子と属性を任意の数持てる. \\ \hline | |
| 34 | 32 \end{tabular} |
| 33 \end{center} | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
34 \caption{Jungle が持つデータ型} |
| 34 | 35 \end{table} |
| 36 | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
37 \subsection{Jungle} |
| 47 | 38 Jungle は木構造の集まりを表現する. |
| 39 木には名前がついており, Tree の情報と一緒に保持している. | |
| 35 | 40 |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
41 \begin{lstlisting}[caption=Jungleのデータ型の定義] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
42 data Jungle = Jungle { getJungleMap :: (TVar (Map String Tree)) } |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
43 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
44 |
| 47 | 45 Jungle のデータ構造は, Jungle (TVar (Map String Tree)) である. |
| 46 getJungleMap :: というのは, Haskell のレコード構文である. | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
47 |
| 47 | 48 レコード構文は, データ構造へのアクセサを提供する. |
| 49 getJungleMap は関数で, 以下のような型を持つ. | |
| 50 これは, Jungleを受け取って, TVar (Map String Tree)を返す関数である. | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
51 |
| 47 | 52 レコード構文はデータ型を受け取って, :: の右側の型の値を取り出せる関数を作成すると思えば良い. |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
53 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
54 \begin{lstlisting}[caption=getJungleMap] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
55 getJungleMap :: Jungle -> TVar (Map String Tree) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
56 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
57 |
| 47 | 58 Jungle の木の取り扱いには, Haskell の Data.Map を利用している. |
| 59 型名は, Map である. | |
| 60 Map は, 連想配列を扱うことのできるデータ構造である. | |
| 61 平衡木を用いて, 挿入や参照が O (log n)で済むように設計されている. | |
| 62 Data.Mapを理解するためにはリストで考えると分かりやすい. | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
63 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
64 \begin{lstlisting}[caption=getJungleMap] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
65 data Map k a = Map [(k,a)] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
66 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
67 lookup' :: Eq k => k -> Map k a -> Maybe a |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
68 lookup' k (Map []) = Nothing |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
69 lookup' k (Map ((k',a):xs)) = if k == k' |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
70 then Just a |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
71 else lookup k xs |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
72 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
73 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
74 insert :: k -> a -> Map k a -> Map k a |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
75 insert k a (Map x) = Map ((k,a):x) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
76 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
77 test = Map [("key","value"),("fizz","buzz")] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
78 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
79 |
| 47 | 80 Map は, キーと値のペアのリストだと考えることができる. |
| 81 キーが一致する値を探す場合, lookup'を用いる. | |
| 82 Maybe モナドを用いて, データがなければ Nothing, データがあれば Just に包んで返す. | |
| 83 $=>$ の前にある, Eq kは, 型クラスの制約である. | |
| 84 内部で k と k' の同値性をテストしているため, k は同値性をチェックできる型クラス Eq に属している型である必要がある. | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
85 |
| 47 | 86 新たにキーと値のペアを, Mapに追加するには insertを用いる. |
| 87 Haskell では, 受け取った引数を変更することができないため, ペアを追加した新しい Map を返す. | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
88 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
89 |
| 47 | 90 木の取り扱いには Haskell のソフトウェア・トランザクショナル・メモリ (STM) を利用して状態を持たせ, スレッド間で共有できるようにしてある. |
| 91 これは, 各スレッドから木構造を新たに作成できるようにするためである. | |
| 92 STM は, スレッド間でデータを共有するためのツールである. STM を利用することでロック忘れによる競合状態や, デッドロックといった問題から解放される. | |
| 93 Jungle のデータ構造の Map の前に付いている TVar というのは, Transactional variablesの略で, STM で管理する変数に対して利用する. | |
| 34 | 94 |
| 23 | 95 \subsubsection{Jungle と木の作成} |
| 47 | 96 Jungle は, Mapで木を管理しているため, 複数の非破壊的木構造を持つことができる（図\ref{fig:jungle}）. |
| 10 | 97 |
| 23 | 98 \begin{figure}[!htbp] |
| 99 \begin{center} | |
| 100 \includegraphics[scale=0.7]{./images/jungle.pdf} | |
| 101 \end{center} | |
| 102 \caption{複数の木を扱えるJungle} | |
| 103 \label{fig:jungle} | |
| 104 \end{figure} | |
| 10 | 105 |
| 47 | 106 木構造の識別, つまり Map の キー にはString を利用する. |
| 107 String は Haskell の文字列の型で, Char のリスト [Char] の別名である. | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
108 |
| 47 | 109 Jungle を作成するには, createJungle を用いる. |
| 110 empty は空のMapを作成する関数である. | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
111 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
112 \begin{lstlisting}[caption=createJungle] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
113 createJungle :: IO Jungle |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
114 createJungle = atomically $ do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
115 map <- newTVar empty |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
116 return (Jungle map) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
117 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
118 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
119 \begin{lstlisting}[caption=STMの関数] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
120 newTVar :: a -> STM (TVar a) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
121 readTVar :: TVar a -> STM a |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
122 writeTVar :: TVar a -> a -> STM () |
| 23 | 123 |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
124 atomically :: STM a -> IO a |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
125 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
126 |
| 47 | 127 createJungleは, 新たにSTMの変数を作成する newTVar を実行する. |
| 128 newTVar などの STM の操作は STM モナド内で行う. | |
| 129 最後にatomicallyを行うことで, do 構文内がトランザクションとして実行される. | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
130 |
| 47 | 131 atomically の隣にある \$ は関数適用演算子である. |
| 132 \$ 関数は最も低い優先順位を持っており, 右結合である. | |
| 133 括弧を減らすのに使う. \$ を使わない場合は以下の様に記述することになる. | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
134 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
135 \begin{lstlisting}[caption=STMの関数] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
136 createJungle :: IO Jungle |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
137 createJungle = atomically (do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
138 map <- newTVar empty |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
139 return (Jungle map)) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
140 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
141 |
| 47 | 142 createJungle は, IOを返すため使う際には main に関連付ける必要がある. |
| 23 | 143 |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
144 \subsection{Tree} |
| 47 | 145 Jungleが保持する木の情報は, 内部的には Tree というデータ型で保持している. |
| 146 Tree は木の名前と, ルートノードの情報を持っている. | |
| 147 実際にユーザがJungleを利用する際は, Jungle と木の名前を使ってルートノードを取ってくるため, Tree という構造は見えない. | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
148 |
| 47 | 149 ルートノードの情報はスレッド間で状態を共有する必要がある. |
| 150 スレッドセーフに取り扱う必要があるため, この情報も Haskell の ソフトウェア・トランザクショナル・メモリ (STM) を用いて管理している. | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
151 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
152 \begin{lstlisting}[caption=Treeのデータ型の定義] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
153 data Tree = Tree |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
154 { rootNode :: (TVar Node) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
155 , treeName :: String } |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
156 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
157 |
| 47 | 158 新たな非破壊的木構造を作るには, createTree を用いる. |
| 159 createTree は, createJungleで作成した Jungle と木の名前を String で受け取る. | |
| 10 | 160 |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
161 \begin{lstlisting}[caption=createTree] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
162 createTree :: Jungle -> String -> IO () |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
163 createTree (Jungle tmap) tree_name = atomically $ do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
164 map <- readTVar tmap |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
165 tree <- emptyTree tree_name |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
166 writeTVar tmap (insert tree_name tree map) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
167 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
168 emptyTree :: String -> STM Tree |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
169 emptyTree tree_name = do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
170 node <- newTVar emptyNode |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
171 return (Tree node tree_name) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
172 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
173 emptyNode :: Node |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
174 emptyNode = Node (empty) (empty) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
175 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
176 |
| 47 | 177 createJungleも STM を操作するため IOを返す. |
| 178 Jungle の持つ, tmapをreadTVarで取得し, 複数の木構造を管理するためのMapを取得する. | |
| 179 STM の変数をもった Tree を作成し, Map に insert する. | |
| 180 writeTVar は更新する先の変数と, 更新内容の2つを受け取る STM の関数である. | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
181 |
| 47 | 182 実際にcreateJungleとcreateTreeを使う時は以下のように記述する. |
| 34 | 183 |
| 10 | 184 \begin{lstlisting}[caption=データベースと木の作成] |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
185 main = do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
186 jungle <- createJungle |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
187 createTree jungle "name of new tree here" |
| 10 | 188 \end{lstlisting} |
| 189 | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
190 |
| 10 | 191 \subsubsection{ルートノード} |
| 47 | 192 非破壊的木構造データベース Jungle では, 木の最新の状態を更新・参照するのにルートノードを使う. |
| 193 ルートノードは, 最新の木構造の根がどれかの情報を保持している（図\ref{fig:getrootnode}）. | |
| 23 | 194 |
| 195 \begin{figure}[!htbp] | |
| 196 \begin{center} | |
| 197 \includegraphics[scale=0.7]{./images/get_root_node.pdf} | |
| 198 \end{center} | |
| 199 \caption{ルートノード} | |
| 200 \label{fig:getrootnode} | |
| 201 \end{figure} | |
| 202 | |
| 47 | 203 ルートノードに関する関数を説明する. |
| 10 | 204 |
| 47 | 205 getRootNode は, 最新のルートノードを取得できる. |
| 206 データベースと木の名前を渡すことで利用できる. | |
| 207 例えば, 図\ref{fig:getrootnode}の状態の時は, B というルートノードが取得できる. | |
| 10 | 208 |
| 209 \begin{lstlisting}[caption=最新のルートノードの取得] | |
| 34 | 210 getRootNode :: Jungle -> String -> IO Node |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
211 getRootNode (Jungle tmap) tree_name = atomically $ do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
212 map <- readTVar tmap |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
213 readTVar (root_node map) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
214 where |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
215 root_node map = case lookup tree_name map of |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
216 Just x -> rootNode x |
| 10 | 217 \end{lstlisting} |
| 218 | |
| 47 | 219 まず, readTVarでJungleが持つmapを参照する. |
| 220 Haskell の where キーワードは, 計算の中間結果に名前をつけるために用いられる. | |
| 221 今回は, root\_node という map を受け取る関数を定義している. | |
| 222 root\_node map では, Jungle が持つ Map をみて取得しようとしている名前の木構造があるかどうか調べている. | |
| 223 木構造があった場合, rootNodeというTreeに定義されているレコード構文のアクセサ関数を使って, (TVar Node)を取得する. | |
| 224 最後に, (TVar Node)に対して, readTVarを行うことで最新のルートノードが取得できる. | |
| 10 | 225 |
| 47 | 226 木構造を編集する関数は全て Node を受け取って Node を返す. |
| 227 その返ってきた Node をルートノードとして登録することで, 木構造の最新のルートノードが更新される. | |
| 228 updateRootNode は, データベースと木の名前, 変更して返ってきた木構造の 3 つを渡す. | |
| 229 updateRootNodeをした後は, getRootNodeで取得できるルートノードが更新された状態になっている. | |
| 10 | 230 |
| 231 \begin{lstlisting}[caption=ルートノードの更新] | |
| 34 | 232 updateRootNode :: Jungle -> String -> Node -> IO () |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
233 updateRootNode (Jungle tmap) tree_name node = |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
234 atomically $ do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
235 map <- readTVar tmap |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
236 writeTVar (root_node map) node |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
237 where |
| 41 | 238 root_node map = case lookup tree_name map of |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
239 Just x -> rootNode x |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
240 \end{lstlisting} |
| 34 | 241 |
| 47 | 242 updateRootNodeWithは, ノードを更新する関数とデータベース, 木の名前を渡して利用する. |
| 243 ノードを更新する関数とは, ノードを受け取ってノードを返す関数である. (Node $->$ Node) がそれにあたる. | |
| 244 このupdateRootNodeWithを利用することで, getRootNodeをした後に編集しupdateRootNodeを行う一連の操作がatomicallyに行われることが保証される. | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
245 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
246 \begin{lstlisting}[caption=ルートノードの更新] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
247 updateRootNodeWith :: (Node -> Node) -> Jungle -> String -> IO () |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
248 updateRootNodeWith f (Jungle tmap) tree_name = |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
249 atomically $ do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
250 map <- readTVar tmap |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
251 n <- readTVar (root_node map) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
252 writeTVar (root_node map) (f n) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
253 where |
| 41 | 254 root_node map = case lookup tree_name map of |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
255 Just x -> rootNode x |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
256 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
257 |
| 47 | 258 並列データベース Jungle で他のスレッドと状態を共有する操作は, |
| 259 createJungle, createTree, getRootNode, updateRootNode, updateRootNodeWith | |
| 260 で全てである. | |
| 261 並列データベース Jungle では, なるべく状態を共有しないようにすることで並列実行時の性能の向上を実現する. | |
| 262 ソフトウェアトランザクショナルメモリは書き込み時に他から変更があった場合にやり直しという操作はあるものの, 読み込みに関してはロックなしで高速に読み込める. | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
263 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
264 \subsection{Node} |
| 47 | 265 Node は木構造を表現するデータ構造である. |
| 266 再帰的に定義されている. | |
| 267 各ノードは children として子ノードを複数持つことができる（図\ref{fig:node_components}）. | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
268 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
269 \begin{figure}[!htbp] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
270 \begin{center} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
271 \includegraphics[width=110mm]{./images/node_component.pdf} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
272 \end{center} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
273 \caption{Nodeの構成要素} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
274 \label{fig:node_components} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
275 \end{figure} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
276 |
| 47 | 277 children および attributes も Data.Map を用いて定義されている（ソースコード \ref{src:node}）. |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
278 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
279 \begin{lstlisting}[label=src:node, caption=Nodeのデータ型の定義] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
280 data Node = Node |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
281 { children :: (Map Int Node) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
282 , attributes :: (Map String ByteString) } |
| 10 | 283 \end{lstlisting} |
| 284 | |
| 285 \subsubsection{木の編集} | |
| 47 | 286 木の編集には, Node を使う. |
| 287 木の編集に用いる関数は全て Node を受け取って Node を返す. | |
| 288 非破壊的木構造を利用しているため, getRootNode などで取得してきた Node は他のスレッドと干渉することなく自由に参照, 編集できる. | |
| 289 これらの編集のための関数は, 編集後updateRootNodeするか, ひとつの関数にまとめてupdateRootNodeWithをすることで木構造に反映させることができる. | |
| 10 | 290 |
| 47 | 291 編集対象のノードを指定するには, NodePath を利用する. |
| 292 NodePath は, ルートノードからスタートし, ノードの子どもの場所を次々に指定したものである. | |
| 293 Haskell の基本データ構造であるリストを利用している. | |
| 10 | 294 |
| 295 \begin{figure}[!htbp] | |
| 296 \begin{center} | |
| 297 \includegraphics[width=100mm]{./images/nodepath.pdf} | |
| 298 \end{center} | |
| 299 \caption{NodePath} | |
| 300 \label{fig:nodepath} | |
| 301 \end{figure} | |
| 302 | |
| 47 | 303 木の編集を行う関数を紹介する. |
| 34 | 304 |
| 41 | 305 \begin{lstlisting}[caption=木の編集を行う関数] |
| 306 addNewChildAt :: Node -> Path -> Node | |
| 34 | 307 deleteChildAt :: Node -> Path -> Position -> Node |
| 41 | 308 putAttribute :: Node -> Path -> String -> ByteString -> Node |
| 309 deleteAttribute :: Node -> Path -> String -> Node | |
| 10 | 310 \end{lstlisting} |
| 311 | |
| 47 | 312 addNewChildAt で, ノードに新しい子を追加できる. |
| 313 Node と NodePath を渡す必要がある. | |
| 314 子には Position という場所の情報があるが, インクリメントしながら自動的に指定される. | |
| 41 | 315 |
| 47 | 316 deleteChildAt で, ノードの子を削除できる. |
| 317 Node と NodePath, 削除したい子のPositionを指定する. | |
| 41 | 318 |
| 47 | 319 putAttribute で, ノードに属性を追加できる. |
| 320 Node と NodePath, キー, 値を渡す. | |
| 321 キーは String, 値は, ByteString である. | |
| 41 | 322 |
| 47 | 323 deleteAttribute で, ノードの属性を削除できる. |
| 324 Node と NodePath, キーを渡す. | |
| 41 | 325 |
| 47 | 326 これらの関数は, ほぼ同一の関数で定義できる. |
| 327 addNewChildAtを用いて説明する. | |
| 23 | 328 |
| 41 | 329 \begin{lstlisting}[caption=木の編集を行う関数] |
| 330 addNewChildAt :: Node -> Path -> Node | |
| 331 addNewChildAt parent [] = addChildAt parent emptyNode | |
| 332 addNewChildAt parent (x:xs) = addChild parent x $ addNewChildAt x_node xs | |
| 333 where | |
| 334 map = children parent | |
| 335 x_node = case lookup x map of | |
| 336 Just x -> x | |
| 34 | 337 |
| 41 | 338 addChild :: Node -> Position -> Node -> Node |
| 339 addChild node pos child = Node new_child attr | |
| 340 where | |
| 341 map = children node | |
| 342 new_child = insert pos child map | |
| 343 attr = attributes node | |
| 344 | |
| 345 addChildAt :: Node -> Node -> Node | |
| 346 addChildAt node child = Node new_child attr | |
| 347 where | |
| 348 map = children node | |
| 349 pos = (size map) + 1 | |
| 350 new_child = insert pos child map | |
| 351 attr = attributes node | |
| 10 | 352 \end{lstlisting} |
| 353 | |
| 47 | 354 非破壊的木構造の編集は再帰で定義できる. |
| 355 左結合となる\$を使い, 対象のノードに到達するまで, addChildを繰り返す. | |
| 356 addChildは, 引数として子となるノードが必要である. | |
| 357 そのため, 下の階層から徐々に上に作られていく. | |
| 23 | 358 |
| 47 | 359 addNewChildAt, deleteChildAt, putAttribute, deleteAttributeといった, |
| 360 非破壊的木構造の編集は, 対象のノードに対する操作以外は全て同じである. | |
| 361 Pathのリストが空になる, すなわち対象のノードに到達した時の操作だけが異なる. | |
| 362 新しい子を追加するのが addNewChildAt, 指定されたポジションの子を削除するのが deleteChildAt, | |
| 363 指定されたキーと値を追加するのが putAttribute, 指定されたキーの値を削除するのが deleteAttributeである. | |
| 10 | 364 |
| 365 | |
| 366 \subsubsection{木の参照} | |
| 47 | 367 木の参照にも Node を用いる. |
| 368 様々な参照の関数があるため, ひとつずつ紹介していく. | |
| 23 | 369 |
| 10 | 370 \begin{lstlisting}[caption=属性の取得] |
| 34 | 371 getAttributes :: Node -> Path -> String -> Maybe ByteString |
| 41 | 372 getAttributes node path key = lookup key map |
| 373 where | |
| 374 target = getNode node path | |
| 375 map = attributes target | |
| 34 | 376 |
| 41 | 377 getChildren :: Node -> Path -> [Node] |
| 378 getChildren node path = elems map | |
| 379 where | |
| 380 target = getNode node path | |
| 381 map = children target | |
| 382 | |
| 383 assocsChildren :: Node -> Path -> [(Int, Node)] | |
| 384 assocsChildren node path = assocs map | |
| 385 where | |
| 386 target = getNode node path | |
| 387 map = children target | |
| 2 | 388 |
| 41 | 389 assocs :: Node -> Path -> [(String, ByteString)] |
| 390 assocs node path = assocs map | |
| 391 where | |
| 392 target = getNode node path | |
| 393 map = attributes target | |
| 23 | 394 |
| 41 | 395 numOfChild :: Node -> Path -> Int |
| 396 numOfChild node path = size map | |
| 397 where | |
| 398 target = getNode node path | |
| 399 map = children target | |
| 34 | 400 |
| 41 | 401 currentChild :: Node -> Path -> Maybe Node |
| 402 currentChild node path = lookup pos map | |
| 403 where | |
| 404 target = getNode node path | |
| 405 map = children target | |
| 406 pos = size map | |
| 10 | 407 \end{lstlisting} |
| 408 | |
| 47 | 409 elems, assocs, sizeなどはData.Mapの関数である. |
| 23 | 410 |
| 47 | 411 getAttributes は, 対象の Path に存在する属性を Key を用いて参照できる. |
| 34 | 412 |
| 47 | 413 getChildren は, 対象の Node が持つ全ての子を Node のリストとして返す. |
| 414 あるNodeに存在する全ての子に対して, 参照を行いたい場合に利用する. | |
| 23 | 415 |
| 47 | 416 assocsChildren は, 対象の Node が持つ全ての子を Position とのタプルにし, そのタプルのリストを返す. |
| 417 あるNodeに存在する全ての子に対して, 子のPositionを取得しながら参照を行いたい場合に利用する. | |
| 34 | 418 |
| 47 | 419 assocsAttribute は, 対象の Node が持つ全ての属性を, キーと値のペアとし, そのペアのリストを返す. |
| 420 あるNodeに存在する全ての属性に対して, 参照を行いたい場合に利用する. | |
| 10 | 421 |
| 47 | 422 numOfChild では, 対象の Node が持つ子どもの数を取得できる. |
| 23 | 423 |
| 47 | 424 currentChild では, 対象の Node が持つ最新の子を取得できる. |
| 23 | 425 |
| 10 | 426 |
| 23 | 427 \subsubsection{並列実行} |
| 47 | 428 木構造データベース Jungle は, 並列に実行することができる. |
| 429 アプリケーション側で, データベースを参照や変更する際に各スレッドから呼び出しても問題ない. | |
| 430 利用方法も, シングルスレッドで実行する場合と同じである. | |
| 23 | 431 |
| 10 | 432 \section{Haskell の生産性} |
| 47 | 433 Java を用いた Jungle の実装と比較して, コード行数が約 3000 行から約 300 行へと短くなった. |
| 10 | 434 |
| 47 | 435 Haskell では, 独自のデータ型を作成することができる. |
| 436 再帰的なデータ構造の定義も容易である. | |
| 437 また, Haskellは参照透過性を持つため, コードの再利用が行い易く, 関数同士の結合も簡単である. | |
| 10 | 438 |
| 47 | 439 同じような機能を実装する場合でも, Java と比較してコード行数が短くなり生産性が向上する. |