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