# HG changeset patch # User Daichi TOMA # Date 1391458466 -32400 # Node ID 5b69636936cca811adf10ed3c0eaf6c94f295920 # Parent bd30d93097da00d1a85f5d7372fe6ef3aad7efcf add impl diff -r bd30d93097da -r 5b69636936cc paper/chapter3.tex --- a/paper/chapter3.tex Tue Feb 04 04:41:52 2014 +0900 +++ b/paper/chapter3.tex Tue Feb 04 05:14:26 2014 +0900 @@ -3,7 +3,7 @@ \section{木構造データベース Jungle} 非破壊的木構造データベース Jungle は、Haskell で実装された並列データベースである。 -非破壊的木構造の方法に則ったAPIを提供する。 +非破壊的木構造の方法に則った関数を提供する。 % 本研究では、HTTP サーバ Warp と組み合わせて掲示板システムとして利用しているが、他のシステムに組み込むことも可能である。 Jungle の基本的な使い方の手順について説明する。 @@ -200,7 +200,7 @@ \label{fig:getrootnode} \end{figure} -ルートノードに関する API を説明する。 +ルートノードに関する関数を説明する。 getRootNode は、最新のルートノードを取得できる。 データベースと木の名前を渡すことで利用できる。 @@ -223,7 +223,7 @@ 木構造があった場合、rootNodeというTreeに定義されているレコード構文のアクセサ関数を使って、(TVar Node)を取得する。 最後に、(TVar Node)に対して、readTVarを行うことで最新のルートノードが取得できる。 -木構造を編集する API は全て Node を受け取って Node を返す。 +木構造を編集する関数は全て Node を受け取って Node を返す。 その返ってきた Node をルートノードとして登録することで、木構造の最新のルートノードが更新される。 updateRootNode は、データベースと木の名前、変更して返ってきた木構造の 3 つを渡す。 updateRootNodeをした後は、getRootNodeで取得できるルートノードが更新された状態になっている。 @@ -235,12 +235,12 @@ map <- readTVar tmap writeTVar (root_node map) node where - root_node map = case M.lookup tree_name map of + root_node map = case lookup tree_name map of Just x -> rootNode x \end{lstlisting} updateRootNodeWithは、ノードを更新する関数とデータベース、木の名前を渡して利用する。 -ノードを更新する関数とは、ノードを受け取ってノードを返す関数である。(Node -> Node) がそれにあたる。 +ノードを更新する関数とは、ノードを受け取ってノードを返す関数である。(Node $->$ Node) がそれにあたる。 このupdateRootNodeWithを利用することで、getRootNodeをした後に編集しupdateRootNodeを行う一連の操作がatomicallyに行われることが保証される。 \begin{lstlisting}[caption=ルートノードの更新] @@ -251,11 +251,11 @@ n <- readTVar (root_node map) writeTVar (root_node map) (f n) where - root_node map = case M.lookup tree_name map of + root_node map = case lookup tree_name map of Just x -> rootNode x \end{lstlisting} -並列データベース Jungle で、他のスレッドと状態を共有する操作は、 +並列データベース Jungle で他のスレッドと状態を共有する操作は、 createJungle、createTree、getRootNode、updateRootNode、updateRootNodeWith で全てである。 並列データベース Jungle では、なるべく状態を共有しないようにすることで並列実行時の性能の向上を実現する。 @@ -264,7 +264,7 @@ \subsection{Node} Node は木構造を表現するデータ構造である。 再帰的に定義されている。 -各ノードは Children としてノードを複数持つことができる（図\ref{fig:node_components}）。 +各ノードは children として子ノードを複数持つことができる（図\ref{fig:node_components}）。 \begin{figure}[!htbp] \begin{center} @@ -274,7 +274,7 @@ \label{fig:node_components} \end{figure} -Children および Attributes も Data.Map を用いて定義されている（ソースコード \ref{src:node}）。 +children および attributes も Data.Map を用いて定義されている（ソースコード \ref{src:node}）。 \begin{lstlisting}[label=src:node, caption=Nodeのデータ型の定義] data Node = Node @@ -282,22 +282,16 @@ , attributes :: (Map String ByteString) } \end{lstlisting} -\newpage - - -\newpage - \subsubsection{木の編集} 木の編集には、Node を使う。 -木の編集に用いる API は全て Node を受け取って Node を返す。 +木の編集に用いる関数は全て Node を受け取って Node を返す。 非破壊的木構造を利用しているため、getRootNode などで取得してきた Node は他のスレッドと干渉することなく自由に参照、編集できる。 -これらの編集のためのAPIは、編集後updateRootNodeするか、ひとつの関数にまとめてupdateRootNodeWithをすることで木構造に反映させることができる。 +これらの編集のための関数は、編集後updateRootNodeするか、ひとつの関数にまとめてupdateRootNodeWithをすることで木構造に反映させることができる。 編集対象のノードを指定するには、NodePath を利用する。 NodePath は、ルートノードからスタートし、ノードの子どもの場所を次々に指定したものである。 Haskell の基本データ構造であるリストを利用している。 - \begin{figure}[!htbp] \begin{center} \includegraphics[width=100mm]{./images/nodepath.pdf} @@ -306,136 +300,140 @@ \label{fig:nodepath} \end{figure} -addNewChildAt で、ノードに新しい子を追加できる。 -addNewChildAt には、Node と NodePath を渡す。 -子には Position という場所の情報があるが、インクリメントしながら自動的に指定される。 - -\begin{lstlisting}[caption=子の追加] -addNewChildAt :: Node -> Path -> Node +木の編集を行う関数を紹介する。 -new_node = addNewChildAt node [l,2] -\end{lstlisting} - -deleteChildAt で、ノードの子を削除できる。 -deleteChildAt には、Node と NodePath、削除したい子のPositionを指定する。 - -\begin{lstlisting}[caption=子の削除] +\begin{lstlisting}[caption=木の編集を行う関数] +addNewChildAt :: Node -> Path -> Node deleteChildAt :: Node -> Path -> Position -> Node - -new_node = deleteChildAt node [1,2] 0 +putAttribute :: Node -> Path -> String -> ByteString -> Node +deleteAttribute :: Node -> Path -> String -> Node \end{lstlisting} +addNewChildAt で、ノードに新しい子を追加できる。 +Node と NodePath を渡す必要がある。 +子には Position という場所の情報があるが、インクリメントしながら自動的に指定される。 + +deleteChildAt で、ノードの子を削除できる。 +Node と NodePath、削除したい子のPositionを指定する。 + putAttribute で、ノードに属性を追加できる。 -putAttribute には、Node と NodePath、Key、Valueを渡す。 -Key は String、 Value は、ByteString である。 +Node と NodePath、キー、値を渡す。 +キーは String、値は、ByteString である。 + +deleteAttribute で、ノードの属性を削除できる。 +Node と NodePath、キーを渡す。 + +これらの関数は、ほぼ同一の関数で定義できる。 +addNewChildAtを用いて説明する。 -\begin{lstlisting}[caption=属性の追加] -putAttribute :: Node -> Path -> String -> ByteString -> Node +\begin{lstlisting}[caption=木の編集を行う関数] +addNewChildAt :: Node -> Path -> Node +addNewChildAt parent [] = addChildAt parent emptyNode +addNewChildAt parent (x:xs) = addChild parent x $ addNewChildAt x_node xs + where + map = children parent + x_node = case lookup x map of + Just x -> x -new_node = putAttribute node [1,2] "key" "value" +addChild :: Node -> Position -> Node -> Node +addChild node pos child = Node new_child attr + where + map = children node + new_child = insert pos child map + attr = attributes node + +addChildAt :: Node -> Node -> Node +addChildAt node child = Node new_child attr + where + map = children node + pos = (size map) + 1 + new_child = insert pos child map + attr = attributes node \end{lstlisting} -deleteAttribute で、ノードの属性を削除できる。 -deleteAttribute には、Node と NodePath、Keyを渡す。 +非破壊的木構造の編集は再帰で定義できる。 +左結合となる\$を使い、対象のノードに到達するまで、addChildを繰り返す。 +addChildは、引数として子となるノードが必要である。 +そのため、下の階層から徐々に上に作られていく。 -\begin{lstlisting}[caption=属性の削除] -deleteAttribute :: Node -> Path -> String -> Node - -new_node = deleteAttribute node [1,2] "key" -\end{lstlisting} +addNewChildAt、deleteChildAt、putAttribute、deleteAttributeといった、 +非破壊的木構造の編集は、対象のノードに対する操作以外は全て同じである。 +Pathのリストが空になる、すなわち対象のノードに到達した時の操作だけが異なる。 +新しい子を追加するのが addNewChildAt、指定されたポジションの子を削除するのが deleteChildAt、 +指定されたキーと値を追加するのが putAttribute、指定されたキーの値を削除するのが deleteAttributeである。 \subsubsection{木の参照} 木の参照にも Node を用いる。 -様々な参照の API があるため、ひとつずつ紹介していく。 - -getAttributes は、対象の Path に存在する属性を Key を用いて参照できる。 +様々な参照の関数があるため、ひとつずつ紹介していく。 \begin{lstlisting}[caption=属性の取得] getAttributes :: Node -> Path -> String -> Maybe ByteString +getAttributes node path key = lookup key map + where + target = getNode node path + map = attributes target -bytestring = getAttributes node [1,2] "key" -\end{lstlisting} +getChildren :: Node -> Path -> [Node] +getChildren node path = elems map + where + target = getNode node path + map = children target + +assocsChildren :: Node -> Path -> [(Int, Node)] +assocsChildren node path = assocs map + where + target = getNode node path + map = children target -あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。 -getChildren は、対象の Node が持つ全ての子を Node のリストとして返す +assocs :: Node -> Path -> [(String, ByteString)] +assocs node path = assocs map + where + target = getNode node path + map = attributes target -\begin{lstlisting}[caption=対象のNodeの全ての子を取得] -getChildren :: Node -> Path -> [Node] +numOfChild :: Node -> Path -> Int +numOfChild node path = size map + where + target = getNode node path + map = children target -nodelist = getChildren node [1,2] +currentChild :: Node -> Path -> Maybe Node +currentChild node path = lookup pos map + where + target = getNode node path + map = children target + pos = size map \end{lstlisting} -あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。 -getChildren と違い、子のPositionも取得できる。 -assocsChildren は、対象の Node が持つ全ての子を Position とのタプルにし、そのタプルのリストを返す。 +elems、assocs、sizeなどはData.Mapの関数である。 -\begin{lstlisting}[caption=対象のNodeの全ての子とPositionを取得] -assocsChildren :: Node -> Path -> [(Int, Node)] +getAttributes は、対象の Path に存在する属性を Key を用いて参照できる。 -nodelist = assocsChildren node [1,2] -\end{lstlisting} - -あるNodeに存在する全ての属性に対して、参照を行いたい場合に利用する。 -assocsAttribute は、対象の Node が持つ全ての属性を、Key と Value のタプルとし、そのタプルのリストを返す。 +getChildren は、対象の Node が持つ全ての子を Node のリストとして返す。 +あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。 -\begin{lstlisting}[caption=対象のNodeの全てのAttributeのKeyとValueを取得] -assocsAttribute :: Node -> Path -> [(String, B.ByteString)] +assocsChildren は、対象の Node が持つ全ての子を Position とのタプルにし、そのタプルのリストを返す。 +あるNodeに存在する全ての子に対して、子のPositionを取得しながら参照を行いたい場合に利用する。 -attrlist = assocsAttribute node [1,2] -\end{lstlisting} +assocsAttribute は、対象の Node が持つ全ての属性を、キーと値のペアとし、そのペアのリストを返す。 +あるNodeに存在する全ての属性に対して、参照を行いたい場合に利用する。 numOfChild では、対象の Node が持つ子どもの数を取得できる。 -\begin{lstlisting}[caption=対象のNodeの子どもの数を取得] -numOfChild :: Node -> Path -> Int - -num = numOfChild node [1,2] -\end{lstlisting} - currentChild では、対象の Node が持つ最新の子を取得できる。 -\begin{lstlisting}[caption=対象のNodeの最新の子を取得] -currentChild :: Node -> Path -> Maybe Node - -node = currentChild node [1,2] -\end{lstlisting} \subsubsection{並列実行} 木構造データベース Jungle は、並列に実行することができる。 アプリケーション側で、データベースを参照や変更する際に各スレッドから呼び出しても問題ない。 利用方法も、シングルスレッドで実行する場合と同じである。 -\clearpage - - -\clearpage -\section{Haskellの並列処理} -純粋関数型言語 Haskell は並列処理に向いていると言われる。 -しかしながら、安直にそう言い切ることはできない。 -参照透過性があるため、各々の関数の処理は独立している。 -そのため、並列で走らせても問題ないように思われるが、Haskell は遅延評価を行うため問題が発生する。 -遅延評価では、結果が必要になるまで評価されない。 -実装においては、deepseqを用いて即時評価を挟むか、出力など計算が必要となる処理を挟むようにする。 - -Haskellでは、様々な並列化手法が提供されている。 -スレッドを直接操作することも可能である。 - -本研究では、抽象度の高い Eval モナドを利用した。 -Eval モナドを利用することで、並列処理のために必要な処理の流れを分かりやすく記述することができた。 -しかしながら Eval モナドは実行順序を細かく制御することはできない。 -Par モナドを利用すれば、並列処理の流れを細かく記述できるが、 -Eval モナドのように処理と並列処理の流れを分けて記述し、後からプログラムに並列処理を組み込むというようなことはできない。 - -Haskellで並列処理を実装する場合は、どの並列化手法を採用するかということをよく考察する必要がある。 - \section{Haskell の生産性} Java を用いた Jungle の実装と比較して、コード行数が約 3000 行から約 300 行へと短くなった。 -これは Haskell の表現力が高いためである。 Haskell では、独自のデータ型を簡単に作成することができる。 再帰的なデータ構造の定義も容易である。 -共通の性質を扱うための型クラスという仕組みが存在し、既存のライブラリを作成したデータ型に利用できる。 また、Haskellは参照透過性を持つため、コードの再利用が行い易く、関数同士の結合も簡単である。 同じような機能を実装する場合でも、Java と比較してコード行数が短くなり生産性が向上する。 diff -r bd30d93097da -r 5b69636936cc paper/master_paper.pdf Binary file paper/master_paper.pdf has changed