--- a/paper/chapter3.tex	Sun Feb 02 08:46:10 2014 +0900
+++ b/paper/chapter3.tex	Sun Feb 02 20:06:07 2014 +0900
@@ -1,21 +1,39 @@
 \chapter{Haskellによる並列データベースの実装}\label{ch:impl}
 
-本章では、並列データベースの実装について述べる。
-まず、実装した木構造データベースの利用方法について述べ、次に詳細な設計と実装について述べる。
+本章では、並列データベース Jungle の実装について述べる。
+まず、実装した非破壊的木構造データベースの利用方法について述べ、次に詳細な設計と実装について述べる。
 
 \section{木構造データベース Jungle}
-木構造データベース Jungle は、Haskell で実装された並列データベースである。
+非破壊的木構造データベース Jungle は、Haskell で実装された並列データベースである。
 非破壊的木構造の方法に則ったAPIを提供する。
-本研究では、HTTP サーバ Warp と組み合わせて掲示板システムとして利用しているが、他のシステムに組み込むことも可能である。
+
+% 本研究では、HTTP サーバ Warp と組み合わせて掲示板システムとして利用しているが、他のシステムに組み込むことも可能である。
+Jungle の基本的な使い方の手順について説明する。
+\begin{enumerate}
+  \item{木構造を保持する Jungle を作成する（Jungle は複数の木を保持できる）}
+  \item{Jungle 内に新しい木を名前をつけて作成する}
+  \item{木の名前を用いて、ルートノードの取得を行い、データを参照する}
+  \item{もしくは、木の名前を用いて、ルートノードの更新を行う}
+\end{enumerate}
+
+\subsubsection{Jungle と木の作成}
+Jungle は複数の非破壊的木構造を扱うことができる（図\ref{fig:jungle}）。
 
-\subsubsection{木の作成}
-Jungle は複数の木構造を保持する事ができる。
-木構造は、名前を付けて管理する。
-名前を利用することで他の木構造と識別し、作成・編集を行う。
+\begin{figure}[!htbp]
+\begin{center}
+\includegraphics[scale=0.7]{./images/jungle.pdf}
+\end{center}
+\caption{複数の木を扱えるJungle}
+\label{fig:jungle}
+\end{figure}
 
-createJungle で、データベースを作成できる。
+木構造の識別には、名前を利用する。
+名前を付けて作成し、名前を用いることで参照を行う。
+
+createJungle で、Jungle を作成できる。
+
 木を作成するには、createTree を利用する。
-createTree には、createJungle で作成したデータベースと新しい木の名前を渡す。\\
+createTree には、createJungle で作成した Jungle と新しい木の名前を渡す。
 
 \begin{lstlisting}[caption=データベースと木の作成]
 jungle <- createJungle
@@ -23,11 +41,22 @@
 \end{lstlisting}
 
 \subsubsection{ルートノード}
-Jungle は参照および編集に木構造のルートノードを活用する。
+非破壊的木構造データベース Jungle では、木の最新の状態を更新・参照するのにルートノードを使う。
+ルートノードは、最新の木構造の根がどれかの情報を保持している（図\ref{fig:getrootnode}）。
+
+\begin{figure}[!htbp]
+\begin{center}
+\includegraphics[scale=0.7]{./images/get_root_node.pdf}
+\end{center}
+\caption{ルートノード}
+\label{fig:getrootnode}
+\end{figure}
+
 ルートノードに関する API を説明する。
 
 getRootNode は、最新のルートノードを取得できる。
-データベースと木の名前を渡すことで利用する。\\
+データベースと木の名前を渡すことで利用できる。
+例えば、図\ref{fig:getrootnode}の状態の時は、B というルートノードが取得できる。
 
 \begin{lstlisting}[caption=最新のルートノードの取得]
 node <- getRootNode jungle "your tree name here"
@@ -35,9 +64,11 @@
 
 
 木構造を編集する API は全て Node を受け取って Node を返す。
-その返ってきた Node をルートノードとして新たに登録することで木構造が更新される。
+その返ってきた Node をルートノードとして登録することで、木構造の最新のルートノードが更新される。
+
 updateRootNode は、データベースと木の名前、変更して返ってきた木構造を渡す。
-updateRootNodeをした後は、getRootNodeで取得できるルートノードが更新された状態になっている。\\ 
+
+updateRootNodeをした後は、getRootNodeで取得できるルートノードが更新された状態になっている。
 
 \begin{lstlisting}[caption=ルートノードの更新]
 updateRootNode jungle "your tree name here" node
@@ -46,7 +77,6 @@
 updateRootNodeWithは、ノードを更新する関数とデータベース、木の名前を渡して利用する。
 ノードを更新する関数とは、ノードを受け取ってノードを返す関数である。
 このupdateRootNodeWithを利用することで、getRootNodeをした後、編集しupdateRootNodeを行う一連の操作がatomicallyに行われることが保証される。
-\\
 
 \begin{lstlisting}[caption=関数を渡してルートノードの更新]
 updateRootNodeWith func jungle "your tree name here"
@@ -74,14 +104,14 @@
 addNewChildAt で、ノードに新しい子を追加できる。
 addNewChildAt には、Node と NodePath を渡す。
 子には Position という場所の情報があるが、インクリメントしながら自動的に指定される。
-\\
+
 \begin{lstlisting}[caption=子の追加]
 new_node = addNewChildAt node [l,2]
 \end{lstlisting}
 
 deleteChildAt で、ノードの子を削除できる。
 deleteChildAt には、Node と NodePath、削除したい子のPositionを指定する。
-\\
+
 \begin{lstlisting}[caption=子の削除]
 new_node = deleteChildAt node [1,2] 0
 \end{lstlisting}
@@ -89,14 +119,14 @@
 putAttribute で、ノードに属性を追加できる。
 putAttribute には、Node と NodePath、Key、Valueを渡す。
 Key は String、 Value は、ByteString である。
-\\
+
 \begin{lstlisting}[caption=属性の追加]
 new_node = putAttribute node [1,2] "key" "value"
 \end{lstlisting}
 
 deleteAttribute で、ノードの属性を削除できる。
 deleteAttribute には、Node と NodePath、Keyを渡す。
-\\
+
 \begin{lstlisting}[caption=属性の削除]
 new_node = deleteAttribute node [1,2] "key"
 \end{lstlisting}
@@ -107,14 +137,14 @@
 様々な参照の API があるため、ひとつずつ紹介していく。
 
 getAttributes は、対象の Path に存在する属性を Key を用いて参照できる。
-\\
+
 \begin{lstlisting}[caption=属性の取得]
 bytestring = getAttributes node [1,2] "key"
 \end{lstlisting}
 
 あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。
 getChildren は、対象の Node が持つ全ての子を Node のリストとして返す
-\\
+
 \begin{lstlisting}[caption=対象のNodeの全ての子を取得]
 nodelist = getChildren node [1,2]
 \end{lstlisting}
@@ -122,7 +152,7 @@
 あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。
 getChildren と違い、子のPositionも取得できる。
 assocsChildren は、対象の Node が持つ全ての子を Position とのタプルにし、そのタプルのリストを返す。
-\\
+
 \begin{lstlisting}[caption=対象のNodeの全ての子とPositionを取得]
 nodelist = assocsChildren node [1,2]
 \end{lstlisting}
@@ -130,29 +160,41 @@
 
 あるNodeに存在する全ての属性に対して、参照を行いたい場合に利用する。
 assocsAttribute は、対象の Node が持つ全ての属性を、Key と Value のタプルとし、そのタプルのリストを返す。
-\\
+
 \begin{lstlisting}[caption=対象のNodeの全てのAttributeのKeyとValueを取得]
 attrlist = assocsAttribute node [1,2]
 \end{lstlisting}
 
 numOfChild では、対象の Node が持つ子どもの数を取得できる。
-\\
+
 \begin{lstlisting}[caption=対象のNodeの子どもの数を取得]
 num = numOfChild node [1,2]
 \end{lstlisting}
 
 currentChild では、対象の Node が持つ最新の子を取得できる。
-\\
+
 \begin{lstlisting}[caption=対象のNodeの最新の子を取得]
 node = currentChild node [1,2]
 \end{lstlisting}
 
+\subsubsection{並列実行}
+木構造データベース Jungle は、並列に実行することができる。
+アプリケーション側で、データベースを参照や変更する際に各スレッドから呼び出しても問題ない。
+利用方法も、シングルスレッドで実行する場合と同じである。
+
+\clearpage
 \section{木構造データベース Jungle の実装}
 \subsubsection{開発環境}
 実装には、Haskell を用いる。
+コンパイラは、Haskell の並列実行に対応した Glasgow Haskell Compiler (GHC) を用いる。
+GHC は、Haskell で最も広く使われているコンパイラである。
+並列実行のためのMonadや、スレッドセーフな参照型を提供している。
+
 \subsubsection{全体の構造}
-木構造の集まりを表現する Jungle、単体の木構造を表現する Node から構成される。
-Jungle は複数の Node の集まりである。Jungle を利用して最新のルートノードを取得することができる。
+木構造の集まりを表現する Jungle、単体の木構造を表現する Tree から構成される。
+Tree は外部から見えないように実装されている。
+
+Jungle は複数の Tree の集まりである。Jungle と木構造の名前を利用して最新のルートノードを取得することができる。
 Node は子と属性を任意の数持てる。
 
 \begin{table}[!htbp]
@@ -162,6 +204,7 @@
 \begin{tabular}{|c||c|} \hline
 名前 & 概要 \\ \hline
 Jungle & 木の作成・取得を担当する。 \\ \hline
+Tree & 木の名前とルートノードの情報を保持している。 \\ \hline
 Node & 基本的なデータ構造、子と属性を任意の数持てる。 \\ \hline
 RootNode & 木構造のルートを表す。Jungle から最新のルートノードを取得できる。 \\ \hline
 children & 子となるノードを任意の数持つことができる。 \\ \hline
@@ -176,6 +219,7 @@
 
 \subsubsection{木の取り扱い}
 Jungle の木の取り扱いには、Haskell の Data.Map を利用している。
+
 Haskell で連想配列を扱いたい場合、平衡木によって実装された Data.Map を一般的に用いる。
 Haskell のライブラリには配列や、ハッシュ・テーブルといったものも存在するがあまり使われない。
 配列は参照に適しているが、データを追加する際に配列を再作成するためコストが大きい。
@@ -183,18 +227,25 @@
 Data.Mapは、挿入や参照が O(log n) で済む。
 
 また、木の取り扱いには Haskell のソフトウェア・トランザクショナル・メモリ (STM) を利用して状態を持たせ、スレッド間で共有できるようにしてある。
-これは、木構造の各スレッドから作成できるようにするためである。
+これは、各スレッドから木構造を新たに作成できるようにするためである。
 STM は、スレッド間でデータを共有するためのツールである。STM を利用することでロック忘れによる競合状態や、デッドロックといった問題から解放される。
-STM は、アクションのブロックを atomically コンビネータを使ってトランザクションとして実行する。
-いったんブロック内に入るとそこから出るまでは、そのブロック内の変更は他のスレッドから見ることはできない。
-こちら側のスレッドからも他のスレッドによる変更はみることはできず、実行は完全に孤立して行われる。
-トランザクションから出る時に、以下のことが１つだけ起こる。
-\begin{itemize}
- \item 同じデータを平行して変更したスレッドが他になければ、加えた変更が他のスレッドから見えるようになる。
- \item そうでなければ、変更を実際に実行せずに破棄し、アクションのブロックを再度実行する。
-\end{itemize}
-STM は簡単に使え、また同時に安全である。
+
+\subsection{Tree}
+Jungleが保持する木構造は、内部的には Tree というデータ型で保持している。
+Tree は木の名前と、ルートノードの情報を持っている。
+実際にユーザがJungleを利用する際は、Jungle と木の名前を使ってルートノードを取ってくるため、Tree という構造は見えない。
 
+ルートノードの情報はスレッド間で状態を共有する必要がある。
+スレッドセーフに取り扱う必要があるため、この情報も Haskell の ソフトウェア・トランザクショナル・メモリ (STM) を用いて管理している。
+TVar というのは、Transactional variablesの略で、STM で管理する変数に対して利用する。
+
+\begin{lstlisting}[label=src:node, caption=Treeのデータ型の定義]
+data Tree = Tree
+          { rootNode :: (TVar Node)
+          , treeName :: String }
+\end{lstlisting}
+
+\newpage
 \subsection{Node}
 Node は木構造を表現するデータ構造である。
 再帰的に定義されている。
@@ -216,30 +267,22 @@
           , attributes :: (Map String ByteString) }
 \end{lstlisting}
 
-\subsubsection{ルートノード}
-非破壊的木構造ではノードは破壊されない。
-そのため、どのノードが最新のルートノードなのかという情報が必要である。
-この情報もスレッドセーフに取り扱う必要があるため、Haskell の ソフトウェア・トランザクショナル・メモリ (STM) を用いて管理している。
 
-\section{並列実行}
-木構造データベース Jungle は、並列に実行することができる。
-アプリケーション側で、データベースを参照や変更する際に各スレッドから呼び出しても問題ない。
-利用方法も、シングルスレッドで実行する場合と同じである。
-
+\clearpage
 \section{Haskellの並列処理}
 純粋関数型言語 Haskell は並列処理に向いていると言われる。
 しかしながら、安直にそう言い切ることはできない。
 参照透過性があるため、各々の関数の処理は独立している。
 そのため、並列で走らせても問題ないように思われるが、Haskell は遅延評価を行うため問題が発生する。
-遅延評価では、結果が必要になるまで評価せず、同じ呼び出しがあった場合メモ化を行うことで最適化を行う。
-並列で実行する際は、遅延評価を行っていては並列度を高めることができない。
-また、メモ化は結果をキャッシュするため各スレッド間で同期するコストが発生する。
+遅延評価では、結果が必要になるまで評価されない。
+実装においては、deepseqを用いて即時評価を挟むか、出力など計算が必要となる処理を挟むようにする。
 
 Haskellでは、様々な並列化手法が提供されている。
-もちろんスレッドを直接操作することも可能である。
+スレッドを直接操作することも可能である。
+
 本研究では、抽象度の高い Eval モナドを利用した。
-Eval モナドを利用することで、並列処理のために必要な処理の流れを分かりやすく記述することができる。
-しかしながら実行順序を細かく制御することはできない。
+Eval モナドを利用することで、並列処理のために必要な処理の流れを分かりやすく記述することができた。
+しかしながら Eval モナドは実行順序を細かく制御することはできない。
 Par モナドを利用すれば、並列処理の流れを細かく記述できるが、
 Eval モナドのように処理と並列処理の流れを分けて記述し、後からプログラムに並列処理を組み込むというようなことはできない。
 
@@ -249,7 +292,7 @@
 Java を用いた Jungle の実装と比較して、コード行数が約 3000 行から約 300 行へと短くなった。
 
 これは Haskell の表現力が高いためである。
-Haskell では、データ型を簡単に作成することができる。
+Haskell では、独自のデータ型を簡単に作成することができる。
 再帰的なデータ構造の定義も容易である。
 共通の性質を扱うための型クラスという仕組みが存在し、既存のライブラリを作成したデータ型に利用できる。
 また、Haskellは参照透過性を持つため、コードの再利用が行い易く、関数同士の結合も簡単である。