# HG changeset patch # User Daichi TOMA # Date 1392202815 -32400 # Node ID 13535fc08357575a09d7a035c676e9ec0d788d13 # Parent d5ebba12766267e8436f25c50070d1911e343db7 modify diff -r d5ebba127662 -r 13535fc08357 paper/abstract_eng.tex --- a/paper/abstract_eng.tex Wed Feb 12 17:56:08 2014 +0900 +++ b/paper/abstract_eng.tex Wed Feb 12 20:00:15 2014 +0900 @@ -1,15 +1,13 @@ \begin{abstract_eng} Haskell is a purely-functional programming language. -It provides a modern type system, type-safe and type inference makes it possible to write a program reliable\cite{types}. +It provides a modern type system which type-safe and type inference makes it possible to write a program reliable\cite{types}. Haskell has referential transparency that allows the programmer and the compiler to reason about program behavior. In this study, we implement the parallel database using Haskell. It is use non-destructive tree structure. -Non-destructive tree structure is not the destruction of data. -Editing of data is done creating by new tree. -Haskell compatible with non-destructive tree, because Haskell is destructive updates does not exist +Haskell compatible with non-destructive tree, because Haskell has no destructive updates does not exist We measures the performance for reading and writing of parallel database. -We achieve to bring out the performance of the multi-core processor. -Further, in order to indicate the availability of practical applications, we have developed a web bulletin board service. +We achieve to sufficient performance on the multi-core processor. +Further, in order to indicate the availability of practical applications, we measures our database against top of database. \end{abstract_eng} diff -r d5ebba127662 -r 13535fc08357 paper/chapter1.tex --- a/paper/chapter1.tex Wed Feb 12 17:56:08 2014 +0900 +++ b/paper/chapter1.tex Wed Feb 12 20:00:15 2014 +0900 @@ -16,40 +16,45 @@ \end{lstlisting} % 関数の引数への適用とは何か? Haskell の計算とは何か? -フィボナッチ数列の関数が三行に渡って書かれているが, これは Haskell のパターンマッチを活用している. +フィボナッチ関数が三行に渡って書かれているが, これは Haskell のパターンマッチを活用している. +例えば fib 3 -を受け取ると、Haskellは、fib のパターンマッチを行う。3 は0でも1でもないので、三行目の定義、 +を受け取ると, Haskellは, fib のパターンマッチを行う. 3 は 0 でも 1 でもないので, 三行目の定義, fib n = fib (n-2) + fib (n-1) -にマッチする。ここで、変数n は3となる。この式は、 +にマッチする. ここで, 変数 n は 3 となる. この式は, fib 3 = fib (3-2) + fib (3-1) -つまり変数nが3に置換された式が生成される。この変換がHaskellの計算の一段である。 +つまり変数 n が 3 に置換された式が生成される. この変換がHaskellの計算の一段である. -(3-2)と(3-1)は、それぞれ、1と2になる。これはHaskellの内蔵された計算によって行われる。 +(3-2) と (3-1) は, それぞれ 1 と 2 になる. これは Haskellの内蔵された計算によって行われ, fib 3 = fib 1 + fib 2 -fib 1は、... - fib 3 = 1 + (fib (2-2) + fib (2-1)) - fib 3 = 1 + (fib 0 + fib 1) - fib 3 = 1 + (0 + 1) - fib 3 = 2 - -引数の値が 0 ならば 2 行目が呼び出され, 関数の結果は 0 となる. -引数の値が 1 ならば 3 行目が呼び出され, 関数の結果は 1 となる. -上から順に引数と一致する行がないか調べていき, 引数が 0 でも 1 でもなければ引数は n に束縛され, fib (n-2) + fib (n-1) が計算される. +と括弧内が置き換えられる. +fib 1は, 関数二行目の定義とマッチするため, 1 となる. +その後の簡約の様子をソースコード\ref{src:fib2}に示す. +fib 3 の最終的な結果として 2 が返される. +\begin{lstlisting}[label=src:fib2, caption=フィボナッチ関数の簡約] +fib 3 = 1 + (fib (2-2) + fib (2-1)) +fib 3 = 1 + (fib 0 + fib 1) +fib 3 = 1 + (0 + 1) +fib 3 = 2 +\end{lstlisting} フィボナッチ数列の関数は, 自分自身を使って再帰的に定義している. -再帰は, 関数型プログラミング言語において必要不可欠な要素である. -手続き型言語では, 配列とループを主に用いてプログラミングを行うが Haskell ではリスト構造と再帰を用いる. +Haskell では for 文は使わずに再帰でループ処理を記述する. -Haskell で、上記のfib関数を定義すると、Haskell は以下の型を推論する。 - -\begin{lstlisting}[label=src:fib-type, caption=フィボナッチ関数の型] -fib :: Num a => a -> a +Haskell で, 上記のfib関数を定義すると, Haskell はソースコード\ref{src:fib-type}の型を推論する. +\begin{lstlisting}[label=src:fib-type, caption=フィボナッチ関数の型推論] +fib :: (Num a1, Num a, Eq a) => a -> a1 \end{lstlisting} -fib :: Int -$>$ Int は, 関数の型宣言である. -この関数は, Int を受け取って Int を返す関数ということを示す. +$=>$の前の括弧内は型クラスの制約である. +型クラスはその型がどのような振る舞いをするかといったことを定義するものであり, +今回は数値として扱われる Num 型クラスと, 値が同じかどうかテストできる Eq 型クラスが使われている. +a というどんな型でも受け取れる型が引数になっているが, +パターンマッチをするためには値が同じかどうかテストできる必要があり, +また計算するために数値でなければいけないといった制約を Haskell は推論し実行時に型の不整合が起きないようにしている. -\begin{lstlisting}[label=src:fib, caption=フィボナッチ関数] +型の定義を手動で行いたい場合は, 関数の前に型の定義を書くとよい（ソースコード\ref{src:fib3}）. +\begin{lstlisting}[label=src:fib3, caption=フィボナッチ関数の型の定義] fib :: Int -> Int fib 0 = 0 fib 1 = 1 @@ -57,16 +62,17 @@ \end{lstlisting} -\subsubsection{変数の代入} -このように、 純粋関数型プログラミングでは, 変数の代入は式の書き換えによって行われるので、 -一つの変数(例えばn)を二度書き換えることはできない。なぜなら、書き換えられた変数は式から -消えてしまうからである。 +\subsubsection{参照透過性} +このように, 純粋関数型プログラミングでは, 変数の代入は式の書き換えによって行われるので, +一つの変数(例えばn)を二度書き換えることはできない. +なぜなら, 書き換えられた変数は式から消えてしまうからである. + フィボナッチ関数でも, 一度引数を束縛した n を書き換えることはできない. -変数への代入が一度のみのため, 関数にできることは何かを計算してその結果を返すことだけであり, 引数が同じならば関数は必ず同じ値を返すことが保証されている. これを参照透過性と言う。 +変数への代入が一度のみのため, 関数にできることは何かを計算してその結果を返すことだけであり, 引数が同じならば関数は必ず同じ値を返すことが保証されている. これを参照透過性と言う. \subsubsection{高階関数とカリー化} 関数型プログラミング言語は, 関数を変数の値として扱うことができる. -Haskell は, 引数として関数を取ったり返り値として関数を返すことができる高階関数を定義できる. +Haskell は, 引数として関数を取ったり返り値として関数を返すことができる. 2 つのInt を受け取り, 大きい方を返す max はソースコード\ref{src:max}のように定義できる. @@ -77,39 +83,36 @@ else x \end{lstlisting} -このmaxの型宣言に現れる-$>$は右結合であり, -\begin{lstlisting}[label=src:max_curry, caption=max関数のカリー化] -max :: Int -> (Int -> Int) -\end{lstlisting} -と読むことになっている。 +このmaxの型宣言に現れる$->$は右結合であり, +max :: Int $->$ (Int $->$ Int) +と読むことになっている. +max は Int を受け取った後, Int $->$ Int の関数を返すということである. -関数の引数は左結合であり、 +関数の引数は左結合であり, max 3 4 は (max 3) 4 -と解釈する。 +と解釈する. -ここで、max 3 は、Int -> Int の関数「3と大小を比較する」である。このように、 -複数の引数を取るようにみえる関数は, 実際には 1 つの引数を取り, その次の引数を受け取る関数を返す（ソースコード\ref{src:max_curry}）. -max 3は、 高階関数の例になっている。複数引数の関数を高階関数と考えることをカリー化という。 - - -このように関数を返すことで全ての関数を一引数関数として表すことをカリー化という. -カリー化によって, 関数を本来より少ない引数で呼び出した際に部分適用された関数を得ることができる（ソースコード\ref{src:partial}）. +ここで (max 3) は, Int $->$ Int の関数「3と大小を比較する」である. +このように, +複数の引数を取るようにみえる関数は, 実際には 1 つの引数を取り, その次の引数を受け取る関数を返す（ソースコード\ref{src:partial}）. \begin{lstlisting}[label=src:partial, caption=関数の部分適用] -x = max 3 -- x は Int -> Int の関数 +x = max 3 -- x は Int -> Int の関数「3と大小を比較する」 x 4 -- (max 3) 4 の結果として 4 が返される \end{lstlisting} +max 3は, 関数を返すことができる高階関数の例となっている. 複数引数の関数を高階関数と考えることをカリー化という. + \clearpage \section{型} Haskell では, すべての式, すべての関数に型がある. -Int とか Char などは、値の型であり、 +Int や Char などは, 値の型であり, その値が何らかの性質を共有していることを示す. 例えば, 数値は加算できる, 文字列は表示できるといった性質である. -% これは、型クラスあるいは型変数の話。 +% これは, 型クラスあるいは型変数の話. % 型はプログラムに抽象をもたらす. % 型を導入することで, 低水準の詳細を気にせずプログラミングが可能になる. % 例えば, 値の型が文字列ならば, どのように実装されているかということを気にせず, @@ -124,26 +127,26 @@ また, リスト型の定義とあわせてデータ型の定義についても説明する. リストとは, 角括弧で包まれた同じ型の要素の並びである. [1,2,3] や ['a','b','c'] などと表現する. +[1,2,3] というのは, シンタックスシュガーであり, 内部では 1 : 2 : 3 : [] のように表現される（図\ref{fig:list}）. -Haskell では, [1,2,3] という様にリストを表すが, これは単なるシンタックスシュガーであり, -内部では 1 : 2 : 3 : [] のように表現される. - : - 1 : - 2 : - 3 [] +\begin{figure}[!htbp] + \begin{center} + \includegraphics[scale=0.6]{./images/list.pdf} + \end{center} + \caption{リストの展開} + \label{fig:list} +\end{figure} つまりリストの型の値は, [] もしくは a : [a] になることが分かる. -このリストをHaskellでは\ref{src:list}のように定義する。 +このリストをHaskellでは\ref{src:list}のように定義する. -\begin{lstlisting}[label=src:list, caption=Haskellのリスト定義] +\begin{lstlisting}[label=src:list, caption=Haskellのリストの定義] data [] a = [] | a : [a] \end{lstlisting} -等号の後は, 型の値となるものを列挙する. -$|$ は, もしくはという意味である. + data というのは新しい型を定義する際に利用するキーワードである. - 等号の前に型の名前, 等号の後に型が取り得る値の種類を指定する. 等号の前にある [] a というのが型名である. @@ -151,6 +154,8 @@ リスト型は, Intのリスト, Floatのリストといった様々な型のリストを作ることができ, 型変数を用いてそれを実現する. 型変数が何の型になるのかという情報は実行時には決まっており, 関数に渡される際に型の不整合が起きることはない. +等号の後は, 型の値となるものを列挙する. +$|$ は, もしくはという意味である. 型の値 [] は空のリストを表す. 型名と同じであるが, 型とは名前領域が異なるため問題ない. 型名はプログラム中では注釈としてしか使われないためである. @@ -161,7 +166,6 @@ 型の値の定義 [] $|$ a : [a] は, 展開すると a : a : a : .. : a : [] となる. a が任意個続いた後に, [] が来ることとなる. つまり, リストは無限に繋げることができ, リストの終端は空のリスト [] で終わる. - このように定義した型であっても, Haskell は型検査を行う. リストは : を使うことで新しい要素を加えることができるが, 全ての要素は同じ型の要素である必要がある. 違った型の要素を付け加えようとすると Haskell はコンパイル時にエラーを出す. @@ -183,8 +187,8 @@ 型推論とは, 型の宣言をせずともそれを導くのに使われた関数の型シグネチャなどから自動的に型を決定する機構のことである. 型推論のない静的型付け言語は, プログラマが型の宣言を行うことが強制されるが Haskell では型の宣言は必須ではない. -どのように型推論が行われるの例をみてみよう。 -まず、前提として以下の型の定義がある。 （ソースコード\ref{src:type2}）. +どのように型推論が行われるの例を使って説明する. +まず, 前提として以下の型の定義がある. （ソースコード\ref{src:type2}）. \begin{lstlisting}[label=src:type2, caption=getChildrenに含まれる関数の型] getNode :: Node -> Path -> Node @@ -192,13 +196,13 @@ children :: Node -> Map Int Node \end{lstlisting} -開発したデータベースで実装した getChildren という関数で調べる（ソースコード\ref{src:getchildren}）. +開発したデータベースで実装した getChildren という関数がある（ソースコード\ref{src:getchildren}）. \begin{lstlisting}[label=src:getchildren, caption=getChildren関数] getChildren node path = elems (children (getNode node path)) \end{lstlisting} -型の注釈なしに関数を定義し, Haskell の対話環境である GHCi で型情報を取得してみる. +このgetChildrenを型の注釈なしに定義し, Haskell の対話環境である GHCi で型情報を取得してみる. 型情報を取得するには, :type の後ろに関数名を入力する（ソースコード\ref{src:type}）. \begin{lstlisting}[label=src:type, caption=型情報の取得] @@ -209,7 +213,7 @@ そうすると, 推論された型情報 Node -$>$ [Int] -$>$ [Node]が得られる. この型情報は期待する型の定義と一致する. -例えば, getChildrenの引数である, node と path は getNode に渡されているため, getNode の型である Node 型と Path 型であることが分かる. +getChildrenの引数である, node と path は getNode に渡されているため, getNode の型である Node 型と Path 型であることが分かる. 返り値となる型は, elemsの[a]となる. このaは, elemsが受け取るMapの2つ目の型と一致するため, childrenの返り値であるMap Int Node より, [Node]ということが分かる. Haskell では, プログラマが型の宣言を行わずとも, 型を推論し型安全を保つ. @@ -218,25 +222,44 @@ \clearpage \section{モナド} Haskell では, さまざまな目的にモナドを使う. -I/O 処理を行うためには IO モナドを使う必要がある. -プログラミングを行うにあたり, I/O 処理は欠かせないため, モナドの説明を行う. +I/O 処理を行うために必要な IO モナドはよく使われ, また並列処理にもモナドを使う. + +Maybe 型を使ってモナドについて説明する. +Maybe 型は失敗する可能性を扱うデータ型である（ソースコード\ref{src:maybe}）. + +\begin{lstlisting}[label=src:maybe,caption=Maybe型の定義] +data Maybe a = Nothing | Just a +\end{lstlisting} + +失敗したことを表す Nothing, もしくは成功したことを表す Just a のいずれかの値を取る. +検索を行う関数の返り値によく使われ, 何も取得できなければNothing, 何か取れればJust aといった形で返す. + +モナドを使いたい場面は, 失敗するかもしれないという計算を繋いでいく時である. +Maybe型をモナドにするための定義をみていく（ソースコード\ref{src:maybe_monad}）. + +\begin{lstlisting}[label=src:maybe_monad, caption=Maybeモナドの定義] +instance Monad Maybe where + return x = Just x + Nothing >>= f = Nothing + Just x >>= f = f x +\end{lstlisting} モナドとは, 型クラスの 1 つである. 型クラスとは型の振る舞いを定義するものである. -ある型クラスのインスタンスである型は, その型クラスに属する関数の集まりを実装する. -これは, それらの関数がその型ではどのような意味になるのか定義するということである. +instance Monad Maybe whereというのは, Maybe型をモナド型クラスのインスタンスとするのに使う構文である. +型クラスのインスタンスにするためには, その型クラスに属する関数を実装する. +モナドでは, return と $>>=$ (bind) を, Maybeではどう振る舞うかを考え定義していく. -モナドとなれる型は, 型変数を 1 つ取ることができる型である. -これにより何かしらのコンテナに包まれた値を実現する. -モナドとなった型はコンテナに包まれた値に対する共通の操作を行うことができる. -モナドの振る舞いは型クラスとして実装し, 関数として return および $>>$= (bind) を定義する（ソースコード\ref{monad}）. +return および $>>=$ (bind) はソースコード\ref{monad}のような型をもつ関数である. \begin{lstlisting}[label=monad, caption=モナドに属する関数の型] return :: Monad m => a -> m a (>>=) :: Monad m => m a -> (a -> m b) -> m b \end{lstlisting} -return は値を持ち上げてコンテナに包む機能を実装する（図\ref{fig:monad_return}）. +return は値を持ち上げてコンテナに包む機能を実装すればよい（図\ref{fig:monad_return}）. +Maybe モナドの return は, 値をJustで包む. +これがコンテナに包む機能という意味である. \begin{figure}[!htbp] \begin{center} @@ -246,8 +269,10 @@ \label{fig:monad_return} \end{figure} -bind は, 「コンテナに包まれた値」と, 「普通の値を取りコンテナに包まれた値を返す関数」を引数にとり, コンテナに包まれた値をその関数に適用する（図\ref{fig:monad_bind}）. +bind は, 「コンテナに包まれた値」と, 「普通の値を取りコンテナに包まれた値を返す関数」を引数にとり, コンテナに包まれた値をその関数に適用する機能を実装すればよい（図\ref{fig:monad_bind}）. 適用する際, 前のコンテナの結果に依存して, 後のコンテナの振る舞いを変えられる. +Maybe モナドの $>>=$ (bind) は, コンテナが Nothing なら, そのまま Nothing を返す. +コンテナがJustならば, Just に包まれた値を取り出し, 「普通の値を取り Maybe 型を返す関数」に適用する. \begin{figure}[!htbp] \begin{center} @@ -257,48 +282,9 @@ \label{fig:monad_bind} \end{figure} -この2つの関数を利用することにより, 文脈を保ったまま関数を繋いでいくことができる. -Haskell の遅延評価は記述した順序で実行することを保証しないが, モナドの bind は実行順序の指定も可能で, IO モナドを bind で繋いだものは記述順に実行することができる. - -\subsubsection{Maybe モナド} - -文脈を保ったまま関数を繋いでいくとはどういうことなのか, 具体例を用いて説明する. -Maybe 型は失敗する可能性を扱うデータ型である（ソースコード\ref{src:maybe}）. - -\begin{lstlisting}[label=src:maybe,caption=Maybe型の定義] -data Maybe a = Nothing | Just a -\end{lstlisting} - -失敗したことを表す Nothing, もしくは成功したことを表す Just a のいずれかの値を取る. - -Maybe 型が使われている例として, Data.Map の lookup 関数がある. -Data.Map はキーと値を保持する辞書型のデータ構造である. -何らかのキーを渡して, Data.Map から値を取得しようとした時, 返される値は Maybe a 型である. -何かしらの値が取得できた場合は, Just a として値に Just がついて返される. -取得できなければ, Nothing が返る. +この2つの関数を利用することにより, 失敗するかもしれないという計算を繋いでいくことができる. -Maybe モナドを使いたい場面は, 失敗するかもしれないという計算を繋いでいく時である. -Maybe モナドの定義をみていく（ソースコード\ref{src:maybe_monad}）. - -\begin{lstlisting}[label=src:maybe_monad, caption=Maybeモナドの定義] -instance Monad Maybe where - return x = Just x - Nothing >>= f = Nothing - Just x >>= f = f x -\end{lstlisting} - -instance Monad Maybe whereというのは, Maybe型をモナド型クラスのインスタンスとするのに使う構文である. -モナド型クラスに属させるために必要な関数である return と $>>$= (bind) を, Maybeではどう振る舞うかを考え定義していく. - -Maybe モナドの return は, 値をJustで包む. -これがコンテナに包む機能という意味である. - -$>>=$ (bind) は, 「コンテナに包まれた値」と, 「普通の値を取りコンテナに包まれた値を返す関数」を引数にとり, コンテナに包まれた値をその関数に適用すると説明した. -Maybe モナドの場合, コンテナが Nothing なら, そのまま Nothing を返す. -コンテナがJustならば, Just に包まれた値を取り出し, 「普通の値を取りコンテナに包まれた値を返す関数」に適用する. - -失敗するかもしれない計算を繋いでいくとはどういうことなのか. -単純な関数を定義して説明する（ソースコード\ref{src:updown}）. +失敗するかもしれないという計算を行うために単純な関数を定義する（ソースコード\ref{src:updown}）. \begin{lstlisting}[label=src:updown, caption=up関数とdown関数] up 4 = Nothing @@ -312,18 +298,17 @@ up の場合, 引数として4が渡された場合は上がれないため失敗, down の場合, 引数として0が渡された場合は下がれないため失敗と考える. -3 という値にdown, down, up, up 繰り返していく時, +3 という値にdown, down, up, up 繰り返していく時, ソースコード\ref{src:upmonad}のように記述する. +どこかでNothingとなった場合には, 答えがNothingとなる. +失敗するかもしれないという文脈を持ちながら計算を繋げられる. \begin{lstlisting}[label=src:upmonad, caption=Maybeモナドを用いてupとdownを行う] return 3 >>= down >>= down >>= up >>= up \end{lstlisting} -% モナドを使わない場合ソースコード\ref{src:up_without_monad}のように定義することになる. -% これを文脈を保ったまま, 関数を繋げられるモナドを使えばソースコード\ref{src:upmonad}のように記述できる. +ソースコード\ref{src:upmonad}は, ソースコード\ref{src:up_without_monad}のように展開される. -これは、以下のように展開される。 - -\begin{lstlisting}[label=src:up_without_monad, caption=Maybeモナドを使わずにupとdownを行う] +\begin{lstlisting}[label=src:up_without_monad, caption=Maybeモナドの展開] updown :: Maybe Int updown = case down 3 of Nothing -> Nothing @@ -332,7 +317,6 @@ Just place2 -> case up place2 of Nothing -> Nothing Just place3 -> up place3 - \end{lstlisting} case 式は, caseとofの間の式を評価し, その値によって評価を分岐させるためのものである. @@ -340,8 +324,7 @@ 例えば, 3 行目は down 3 の結果が Nothing なら, Nothing を返すという意味である. Justの場合, 値をplace1という変数に束縛しその後の処理を続ける. -% ソースコード\ref{src:up_without_monad}では, 毎回失敗したか成功したか確認するために非常に煩雑なコードとなってしまった. -% Maybe モナドを使うことで, この計算は失敗しているかもしれないという文脈を保ったまま処理を繋げていくことができる. +$>>=$ (bind) を使うことでコンパクトに記述することができる. \subsubsection{IO モナド} Haskellで副作用を持つ処理を実行するには, IO モナドを利用する. @@ -356,8 +339,11 @@ main = putStrLn "Hello, World!" \end{lstlisting} +IO では実行順序が重要になる. +getしてprintするのと, printしてgetするのは全く違った結果になるためである. +Haskell では遅延評価のため記述した順序で実行することを保証しないが, モナドの $>>=$ (bind) で繋ぐことで記述順に実行することができる. + Haskell の関数には副作用がないと述べたが, IO モナドを返す関数にも副作用は存在しない. - 例えば, Jungle には getRootNode というIOを返す関数がある. 呼び出した状況によって, 返ってくるノードが違うため副作用があるようにみえる. しかし, 実際にこの関数が返すのは, 「ノードを取得する」という命令書である. @@ -408,35 +394,35 @@ リストの例より, Haskell では本当に値が必要となるまで決して計算しないことが分かる. -\subsubsection{引数のメモ化} - -Haskell の遅延評価では引数のメモ化を行う. -ある関数の仮引数が, その関数の本体に複数回出現したとしても評価回数が1回のみである. -例えば, ソースコード\ref{memo} は, 図 \ref{fig:memo} のようにメモ化される. -y は未評価のthunkとして同じ x を参照する. -そのため, x が2回評価されることはない. - - (fib 100) ..... (fib 100) - - ^ ^ - | | - +------------------+ 同じものだと思う。 - -\newpage -\begin{lstlisting}[label=memo, caption=メモ化] -Prelude> let x = 1 + 2 :: Int -Prelude> let y = (x,x) <---- これは共有 -Prelude> :sprint y -y = (_,_) -\end{lstlisting} - -\begin{figure}[!htbp] - \begin{center} - \includegraphics[scale=0.6]{./images/memo.pdf} - \end{center} - \caption{メモ化の様子} - \label{fig:memo} -\end{figure} +% \subsubsection{引数のメモ化} +% +% Haskell の遅延評価では引数のメモ化を行う. +% ある関数の仮引数が, その関数の本体に複数回出現したとしても評価回数が1回のみである. +% 例えば, ソースコード\ref{memo} は, 図 \ref{fig:memo} のようにメモ化される. +% y は未評価のthunkとして同じ x を参照する. +% そのため, x が2回評価されることはない. +% +% (fib 100) ..... (fib 100) +% +% ^ ^ +% | | +% +------------------+ 同じものだと思う. +% +% \newpage +% \begin{lstlisting}[label=memo, caption=メモ化] +% Prelude> let x = 1 + 2 :: Int +% Prelude> let y = (x,x) <---- これは共有 +% Prelude> :sprint y +% y = (_,_) +% \end{lstlisting} +% +% \begin{figure}[!htbp] +% \begin{center} +% \includegraphics[scale=0.6]{./images/memo.pdf} +% \end{center} +% \caption{メモ化の様子} +% \label{fig:memo} +% \end{figure} \clearpage \section{並列実行} diff -r d5ebba127662 -r 13535fc08357 paper/chapter2.tex --- a/paper/chapter2.tex Wed Feb 12 17:56:08 2014 +0900 +++ b/paper/chapter2.tex Wed Feb 12 20:00:15 2014 +0900 @@ -1,4 +1,4 @@ -\chapter{Haskellによる\\並列データベースの設計}\label{ch:design} +\chapter[Haskellによる並列データベースの設計]{Haskellによる\\並列データベースの設計}\label{ch:design} \section{マルチコアプロセッサで十分な性能を得るためには} 現在, CPU はマルチコア化が進んでいる. diff -r d5ebba127662 -r 13535fc08357 paper/chapter3.tex --- a/paper/chapter3.tex Wed Feb 12 17:56:08 2014 +0900 +++ b/paper/chapter3.tex Wed Feb 12 20:00:15 2014 +0900 @@ -1,4 +1,4 @@ -\chapter{Haskellによる\\並列データベースの実装}\label{ch:impl} +\chapter[Haskellによる並列データベースの実装]{Haskellによる\\並列データベースの実装}\label{ch:impl} 　本章では, 並列データベース Jungle の実装について述べる. \section{木構造データベース Jungle} @@ -16,7 +16,20 @@ \subsubsection{Jungle が持つデータ型} 非破壊的木構造データベース Jungle が持つのデータ型を表\ref{tab:components}に表す. -また, データ型内部のデータ構造を表\ref{tab:components2}に表す. + + +\begin{table}[htbp] +\begin{center} +\begin{tabular}{|c|c|c|} \hline + 型名 & データ構造 & 概要\\ \hline + Jungle & Jungle (TVar (Map String Tree)) & 木と木の名前を管理 \\ \hline + Tree & Tree (TVar Node) String & ルートノードの管理 \\ \hline + Node & Node (Map Int Node) (Map String ByteString) & 子と属性を任意の数持てる\\ \hline +\end{tabular} +\end{center} +\label{tab:components} +\caption{Jungle が持つデータ型} +\end{table} 木構造の集まりを表現する Jungle, 単体の木構造を表現する Tree がある. Node は子と属性を任意の数持てる. @@ -24,33 +37,6 @@ 例えば, Node の1つ目の型は (Map Int Node) となり他の型は許されない. 非破壊的木構造データベース Jungle のデータ型について, ひとつずつ説明する. -\begin{table}[!htbp] -\begin{center} -\begin{tabular}{|c||c|c|} \hline - 型名 & 概要 \\ \hline - Jungle & 木の作成・取得を担当する. \\ \hline - Tree & 木の名前とルートノードの情報を保持している. \\ \hline - Node & 基本的なデータ構造, 子と属性を任意の数持てる. \\ \hline -\end{tabular} -\end{center} -\label{tab:components} -\caption{Jungle が持つデータ型} -\end{table} - -\newpage -\begin{table}[htbp] -\begin{center} -\begin{tabular}{|c||c|} \hline - 型名 & データ構造 \\ \hline - Jungle & Jungle (TVar (Map String Tree)) \\ \hline - Tree & Tree (TVar Node) String \\ \hline - Node & Node (Map Int Node) (Map String ByteString) \\ \hline -\end{tabular} -\end{center} -\label{tab:components2} -\caption{データ型のデータ構造} -\end{table} - \clearpage \section{Jungle} Jungle は木構造の集まりを表現する. diff -r d5ebba127662 -r 13535fc08357 paper/images/list.graffle --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/list.graffle Wed Feb 12 20:00:15 2014 +0900 @@ -0,0 +1,723 @@ + + + + + ActiveLayerIndex + 0 + ApplicationVersion + + com.omnigroup.OmniGrafflePro + 139.17.0.185490 + + AutoAdjust + + BackgroundGraphic + + Bounds + {{0, 0}, {559, 783}} + Class + SolidGraphic + ID + 2 + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + + BaseZoom + 0 + CanvasOrigin + {0, 0} + ColumnAlign + 1 + ColumnSpacing + 36 + CreationDate + 2014-02-12 09:56:49 +0000 + Creator + Daichi TOMA + DisplayScale + 1.000 cm = 10.000 cm + GraphDocumentVersion + 8 + GraphicsList + + + Class + LineGraphic + Head + + ID + 18 + + ID + 19 + Points + + {254.08410664119802, 274} + {274, 293.08992648190832} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 12 + + + + Bounds + {{274, 291}, {24, 27}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + ID + 18 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Pad + 0 + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 RictyDiscord-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 []} + VerticalPad + 0 + + Wrap + NO + + + Class + LineGraphic + Head + + ID + 12 + + ID + 16 + Points + + {204.5, 225} + {226.5, 247} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 9 + + + + Class + LineGraphic + Head + + ID + 9 + + ID + 15 + Points + + {161.29591836734693, 176} + {179.70408163265307, 198} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 3 + + + + Bounds + {{196, 296}, {12, 27}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + ID + 14 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Pad + 0 + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 RictyDiscord-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 3} + VerticalPad + 0 + + Wrap + NO + + + Class + LineGraphic + ID + 13 + Points + + {226.5, 274} + {206.5, 294} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 12 + + + + Bounds + {{223, 247}, {34, 27}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + ID + 12 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Pad + 0 + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 RictyDiscord-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 :} + VerticalPad + 0 + + + + Bounds + {{146, 247}, {12, 27}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + ID + 11 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Pad + 0 + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 RictyDiscord-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 2} + VerticalPad + 0 + + Wrap + NO + + + Class + LineGraphic + ID + 10 + Points + + {177.5, 225} + {157.5, 245} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 9 + + + + Bounds + {{174, 198}, {34, 27}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + ID + 9 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Pad + 0 + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 RictyDiscord-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 :} + VerticalPad + 0 + + + + Bounds + {{104, 198}, {12, 27}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + ID + 8 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Pad + 0 + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 RictyDiscord-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 1} + VerticalPad + 0 + + Wrap + NO + + + Class + LineGraphic + ID + 6 + Points + + {136.5, 176} + {116.5, 196} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 3 + + + + Bounds + {{133, 149}, {34, 27}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + ID + 3 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Pad + 0 + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 RictyDiscord-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 :} + VerticalPad + 0 + + + + GridInfo + + GuidesLocked + NO + GuidesVisible + YES + HPages + 1 + ImageCounter + 1 + KeepToScale + + Layers + + + Lock + NO + Name + Layer 1 + Print + YES + View + YES + + + LayoutInfo + + Animate + NO + circoMinDist + 18 + circoSeparation + 0.0 + layoutEngine + dot + neatoSeparation + 0.0 + twopiSeparation + 0.0 + + LinksVisible + NO + MagnetsVisible + NO + MasterSheets + + ModificationDate + 2014-02-12 10:01:09 +0000 + Modifier + Daichi TOMA + NotesVisible + NO + Orientation + 2 + OriginVisible + NO + PageBreaks + YES + PrintInfo + + NSBottomMargin + + float + 41 + + NSHorizonalPagination + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSLeftMargin + + float + 18 + + NSPaperSize + + size + {595, 842} + + NSPrintReverseOrientation + + int + 0 + + NSRightMargin + + float + 18 + + NSTopMargin + + float + 18 + + + PrintOnePage + + ReadOnly + NO + RowAlign + 1 + RowSpacing + 36 + SheetTitle + Canvas 1 + SmartAlignmentGuidesActive + YES + SmartDistanceGuidesActive + YES + UniqueID + 1 + UseEntirePage + + VPages + 1 + WindowInfo + + CurrentSheet + 0 + ExpandedCanvases + + + name + Canvas 1 + + + Frame + {{1430, 179}, {667, 961}} + ListView + + OutlineWidth + 142 + RightSidebar + + ShowRuler + + Sidebar + + SidebarWidth + 119 + VisibleRegion + {{0, -19}, {533, 822}} + Zoom + 1 + ZoomValues + + + Canvas 1 + 1 + 1 + + + + + diff -r d5ebba127662 -r 13535fc08357 paper/images/list.pdf Binary file paper/images/list.pdf has changed diff -r d5ebba127662 -r 13535fc08357 paper/images/list.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/list.xbb Wed Feb 12 20:00:15 2014 +0900 @@ -0,0 +1,8 @@ +%%Title: ./list.pdf +%%Creator: extractbb 20130405 +%%BoundingBox: 0 0 194 175 +%%HiResBoundingBox: 0.000000 0.000000 194.000000 175.000000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Wed Feb 12 19:06:12 2014 + diff -r d5ebba127662 -r 13535fc08357 paper/introduciton.tex --- a/paper/introduciton.tex Wed Feb 12 17:56:08 2014 +0900 +++ b/paper/introduciton.tex Wed Feb 12 20:00:15 2014 +0900 @@ -1,10 +1,28 @@ \chapter{研究背景と目的} \label{ch:introduction} \pagenumbering{arabic} -　ITシステムが巨大化していくにつれ, 障害発生事例が社会に与える影響もより大きな物となる. -それに伴い, ITシステムにおけるディペンダビリティへの注目が増している. +　Web サービスの脆弱性狙った攻撃が頻繁に発生している。 +脆弱性を悪用されると、Web サービス運営者は賠償など多大な損害を受ける可能性がある。 +純粋関数型プログラミング言語 Haskell は, バッファオーバーフローや, クロスサイトスクリプティング, SQL インジェクションを事前の型検査で防ぐことができる. +つまり, Haskell を用いることで信頼性の高い Web サービスを開発できると言える. + +本研究の目標は, Haskell を用いて信頼性の高い Web サービスおよびデータベースの開発である. +また, 並列実行で性能が線形に向上するスケーラビリティの達成を目指す. +Web サービス のスケーラビリティを実現するための難点の一つはデータベースであり, データベースは並列にデータにアクセスできる設計が必要となる. -そこで, DEOSプロジェクトはITシステムにおけるディペンダビリティを担保する技術体系をまとめ, 制度化, さらには事業化を目指している. +本研究では並列にデータへアクセスする手法として, 非破壊的木構造を利用する. +非破壊的木構造では, 排他制御をせずにデータへアクセスすることが可能でありスケーラビリティを確保できる\cite{shoshi:2010a}\cite{shoshi:2011a}\cite{shoshi:2011b}. + +実装した並列データベースの読み込みと書き込みについて性能を計測し, +読み込みに関して 12 コアで実行した場合, 1 コアで実行した場合と比較して, 10.37 倍 という性能向上率が確認でき, +マルチコアプロセッサの性能を引き出すことができた. + +また, Web 掲示板サービスを開発し, 既存の Java の非破壊的木構造データベースを用いた掲示板実装との比較をおこない, 読み込みで 3.25 倍, 書き込みで 3.78 倍の性能が確認できた. + +本研究は JST/CREST 「実用化を目指した組み込みシステム用ディペンダブル・オペレーティングシステム」研究領域 (DEOSプロジェクト) として実施した. +本研究ではDEOSプロジェクト内の DEOS Agreement Description Database 信頼性を持って構築ができる非破壊的木構造データベースの実装を示した. + +DEOSプロジェクトはITシステムにおけるディペンダビリティを担保する技術体系をまとめ, 制度化, さらには事業化を目指している. DEOSプロジェクトは2006年に独立行政法人科学技術機構(JST)はCRESTプログラムの1つとして始まったプロジェクトである. DEOSプロジェクトは, 変化し続ける目的や環境の中でシステムを適切に対応させ, 継続的にユーザが求めるサービスを提供することができるシステムの構築法を開発することを目標としている\cite{deos2013}. DEOSプロジェクトではそれらの技術体系を「オープンシステムディペンダビリティ」として定義し, それをDEOSプロセスとしてまとめた(図\ref{fig:deos_proccess}). @@ -29,19 +47,3 @@ このようなデータベースは様々なデータを柔軟に格納する必要があり, データベーススキーマの頻繁な変化に対応する必要がある. これらのデータベースは, Web からアクセスされることも想定される. そのため, DEOSは Web サービスとして捉えることができる. - -純粋関数型プログラミング言語 Haskell は, バッファオーバーフローや, クロスサイトスクリプティング, SQL インジェクションを事前の型検査で防ぐことができる. -つまり, Haskell を用いることで信頼性の高い Web サービスを開発できると言える. - -本研究の目標は, Haskell を用いて信頼性の高い Web サービスおよびデータベースの開発である. -また, 並列実行で性能が線形に向上するスケーラビリティの達成を目指す. -Web サービス のスケーラビリティを実現するための難点の一つはデータベースであり, データベースは並列にデータにアクセスできる設計が必要となる. - -本研究では並列にデータへアクセスする手法として, 非破壊的木構造を利用する. -非破壊的木構造では, 排他制御をせずにデータへアクセスすることが可能でありスケーラビリティを確保できる\cite{shoshi:2010a}\cite{shoshi:2011a}\cite{shoshi:2011b}. - -実装した並列データベースの読み込みと書き込みについて性能を計測し, -読み込みに関して 12 コアで実行した場合, 1 コアで実行した場合と比較して, 10.37 倍 という性能向上率が確認でき, -マルチコアプロセッサの性能を引き出すことができた. - -また, Web 掲示板サービスを開発し, 既存の Java の非破壊的木構造データベースを用いた掲示板実装との比較をおこない, 読み込みで 3.25 倍, 書き込みで 3.78 倍の性能が確認できた. diff -r d5ebba127662 -r 13535fc08357 paper/master_paper.pdf Binary file paper/master_paper.pdf has changed diff -r d5ebba127662 -r 13535fc08357 paper/master_paper.tex --- a/paper/master_paper.tex Wed Feb 12 17:56:08 2014 +0900 +++ b/paper/master_paper.tex Wed Feb 12 20:00:15 2014 +0900 @@ -31,7 +31,7 @@ \input{font.sty} \jtitle{関数型言語 Haskell による\\並列データベースの実装} -\etitle{Implementation of the Parallel Database using Haskell} +\etitle{An Implementation of Parallel Database using Haskell} \year{平成26年度} \affiliation{\center% \includegraphics[clip,keepaspectratio,width=.15\textwidth]