# HG changeset patch
# User Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
# Date 1374117237 -32400
# Node ID 77ee89ae45fb3d6dbb50afa241788fd5521eb389
# Parent  2a4370ed68bc6cc0048d4576ca113a3bdefefe1e
add a description of implementation

diff -r 2a4370ed68bc -r 77ee89ae45fb Paper/jssst.tex
--- a/Paper/jssst.tex	Thu Jul 18 09:07:57 2013 +0900
+++ b/Paper/jssst.tex	Thu Jul 18 12:13:57 2013 +0900
@@ -112,9 +112,9 @@
 Warp を用いてウェブサービスを構築する方法について考察する。
 % Source Codeは実行可能な状態でsrcに置いてある 
 % firstline, lastlineで、どの範囲を表示するか指定できる
-\lstinputlisting[label=src1, caption=Warpを用いたウェブサービスの例, firstline=9]{src/warp.hs}
+\lstinputlisting[label=warp_sample, caption=Warpを用いたウェブサービスの例, firstline=9]{src/warp.hs}
 
-ソースコード \ref{src1}は、URLによって出力する結果を変更するウェブサービスである。
+ソースコード \ref{warp_sample}は、URLによって出力する結果を変更するウェブサービスである。
 /hello/worldへアクセスがあった場合は、インクリメントされる counter が表示される。
 
 HTTP サーバを起動するには、Warp の run 関数を利用する。
@@ -145,7 +145,8 @@
 我々のシステムでは Warp を用いて開発を行う。
 
 \section{コンテンツマネージメントシステムの設計}
-本研究では、スケーラビリティのある CMS の実現のために非破壊的木構造\cite{shoshi:2011a}を用いる。
+コンテンツマネージメントシステムのデータ構造としては木構造を用いる。
+また、スケーラビリティのある CMS の実現のために非破壊的木構造\cite{shoshi:2011a}を採用する。
 非破壊的木構造とは、編集元の木構造を破壊することなく新しい木構造を構成することで木構造を編集する方法である。
 
 破壊的木構造と異なりロックせずに並列に読むことができるため、自由にコピーを作成することが可能である。
@@ -222,11 +223,77 @@
 非破壊的木構造を用いて、コンテンツマネージメントシステムの開発を行う。
 
 \section{コンテンツマネージメントシステムの実装}
-木構造データベースについて述べる。
+コンテンツマネージメントシステムのデータ構造としては木構造を用いると述べた。
+我々が開発している木構造データベース Jungle について説明する。
 \subsection{木構造データベース Jungle}
-Haskellによって実装された木構造データベースである。
+Jungle は、非破壊的木構造を扱う木構造データベースで、既に Java による実装も存在する。
+本研究では、Haskell を用いて実装を行った。
+コンテンツマネージメントシステムに組み込んで利用しているが、他のシステムに組み込むことも可能である。
+
 \subsubsection{利用方法}
+\paragraph*{木の作成}
+はじめに、データベースオブジェクトと木の作成方法について述べる。
+Jungle は複数の木を保持することができる。
+木には名前がついており、名前を利用して作成・編集・削除を行うことができる。
+
+\begin{lstlisting}[label=new_jung, caption=データベースオブジェクトと木の作成]
+jungle = createJungle
+new_jung = createTree jungle "new_tree"
+\end{lstlisting}
+
+createTree 関数を利用して木構造を作成する。
+
+\paragraph*{木と木を構成するノード}
+
+データベースオブジェクトを作成し、木構造とルートノードを取得するためには以下のように記述する。
+
+\begin{lstlisting}[label=get_tree, caption=木とノードの取得]
+tree = getTreeByName new_jung "new_tree"
+node = getRootNode tree
+\end{lstlisting}
+
+getTreeByName 関数で名前を指定することで木構造を取得できる。
+getRootNode 関数でルートノードを取得できる。
+
+\paragraph*{木の編集}
+
+addNewChildAt 関数で、ノードに新しい子を追加することができる。
+また、putAttribute 関数で、ノードが持つ連想リストを編集できる。
+どのノードを編集するかという情報は、ルートノードからのパスを渡すことで解決する。
+木を編集したあと、updateTree 関数を用いて既存のJungleに変更を加え新しいJungleを作成する。
+
+\begin{lstlisting}[label=get_tree, caption=木の編集]
+new_tree  = addNewChildAt tree [0,1] 0
+new_tree2 = putAttribute new_tree [0,1,0] "key" "value"
+new_jungle = updateTree jungle new_tree2
+\end{lstlisting}
+
+毎回、新しい変数に代入することで記述が少々煩雑になりやすい。
+State モナドを用いて記述を簡易にしたものもあるが、利用者にどのようなAPIを提供するかは検討中である。
+
 \subsubsection{実装の詳細}
+\paragraph*{Treeの取り扱い}
+Jungle の Tree の取り扱いには、Haskell の Map を用いている。
+Mapは、平衡木を使った Haskell の連想リストである。
+連想リストを用いて、木の名前と Tree 自体を結びつけている。
+
+\paragraph*{データ構造}
+木のデータ構造は、データ型で定義されている。
+
+\begin{lstlisting}[label=node, caption=データ構造]
+data Node = Empty
+          | Node
+          { children   :: Children
+          , attributes :: Attributes
+          } deriving (Show)
+\end{lstlisting}
+
+各ノードは、Childrenとしてノードを複数持つことができる。
+ChildrenおよびAttributesも、Map を用いて定義されている。
+
+\paragraph*{ルートノードの取り扱い}
+非破壊木構造であっても、どのノードが最新のルートノードなのかという情報が必要である。
+スレッドセーフに取り扱う必要があるため、Haskell のソフトウェア・トランザクショナル・メモリを用いて管理している。
 
 \section{木構造データベース Jungle を用いた CMS の検証}
 複数のクラスタを利用して、サーバに対して並列にアクセスを行う。