Mercurial > hg > Papers > 2014 > toma-master
annotate paper/chapter1.tex @ 34:345eacdf29e4
add apendix
| author | Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 03 Feb 2014 16:54:48 +0900 |
| parents | cafd13e1d930 |
| children | 909c9097ebb8 |
| rev | line source |
|---|---|
|
6
37efb7dc0bda
describe introduciton
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
1 \chapter{Haskellとは} \label{ch:haskell} |
| 7 | 2 Haskell とは純粋関数型プログラミング言語である。 |
| 2 | 3 |
| 15 | 4 \section{純粋関数型プログラミング} |
| 7 | 5 関数とは、一つの引数を取り一つの結果を返す変換器のことである。 |
| 27 | 6 関数型プログラミング言語では、関数を引数に適用させていくことで計算を行う。 |
| 15 | 7 |
| 8 既存の手続き型言語と異なり、手順を記述するのではなく、この関数が何であるかということを記述する。 | |
| 9 例えば、Haskell でフィボナッチ数列を定義するにはソースコード\ref{src:fib}のように記述する。 | |
| 7 | 10 |
| 15 | 11 \begin{lstlisting}[label=src:fib, caption=フィボナッチ数列] |
| 34 | 12 fib :: Int -> Int |
| 15 | 13 fib 0 = 0 |
| 14 fib 1 = 1 | |
| 15 fib n = fib (n-2) + fib (n-1) | |
| 16 \end{lstlisting} | |
| 17 | |
| 27 | 18 Haskell は、関数を引数を適用するという考えに基づいて、抽象的なプログラミングを可能とする。 |
| 15 | 19 |
| 20 純粋関数型プログラミングでは、変数の代入は一度のみで後から書き換えることはできない。 | |
| 21 また、関数自体は副作用を持たない\footnote{副作用を実現するには、Haskell のアクションという仕組みを用いる}。 | |
| 22 関数にできることは、何かを計算してその結果を返すことだけである。 | |
| 23 そのため、引数が同じならば関数は必ず同じ値を返すことが保証されている。 | |
| 24 この性質は関数の理解を容易にし、プログラムの証明を可能にする。 | |
| 25 正しいと分かる単純な関数を組み合わせて、より複雑な正しい関数を組み立てていくのが関数型言語のプログラミングスタイルである。 | |
| 7 | 26 |
| 27 関数型プログラミング言語は、関数を第一級オブジェクトとして扱うことができ、高階関数を定義することができる。 | |
| 28 これは、引数として関数を取ったり返り値として関数を返すことができるということである。 | |
| 29 高階関数は問題解決の強力な手段であり、関数型プログラミング言語にはなくてはならないものである。 | |
| 30 Haskell では標準ライブラリに、リストを処理するための便利な高階関数がいくつも定義されている。 | |
| 31 | |
| 32 Haskell では、全ての関数は一度に一つの引数だけを取る。 | |
| 33 複数の引数を取るようにみえる関数は、実際には１つの引数を取り、その次の引数を受け取る関数を返す。 | |
| 34 このように関数を返すことで全ての関数を一引数関数として表すことをカリー化という。 | |
| 35 カリー化によって、関数を本来より少ない引数で呼び出した際に部分適用された関数を得ることができる。 | |
| 36 | |
| 37 再帰もまた関数型プログラミング言語において必要不可欠な要素である。 | |
| 38 再帰とは、関数を関数自身を使って定義することをいう。 | |
| 39 関数型プログラミング言語では、ループといった処理を行う場合再帰を用いる。 | |
| 40 また、リストの畳み込み関数といった再帰を用いた関数が標準ライブラリで提供されている。 | |
| 41 | |
| 15 | 42 関数型言語は手続き型言語と比較して、関数の利用に関する制約が少ない。 |
| 43 Haskell では、関数を用いたプログラミングを簡潔かつ強力にするための機能を多く提供している。 | |
| 44 関数をリストなどのデータ構造の要素にしたり、 関数が引数として関数を取ったり、 | |
| 45 関数の返り値として関数を返したり、関数を自分自身を用いて定義したりできる。 | |
| 46 | |
|
16
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
47 \clearpage |
| 7 | 48 \section{型} |
| 15 | 49 Haskell では、すべての式、すべての関数に型がある。 |
| 50 値の型は、その値が同じ型の別の値と何らかの性質を共有していることを示す。 | |
| 51 例えば、数値は加算できる、文字列は表示できるといった性質である。 | |
| 52 | |
| 53 型システムはプログラムに抽象をもたらす。 | |
| 54 抽象を導入することで、低水準の詳細を気にせずプログラミングが可能になる。 | |
| 55 例えば、値の型が文字列ならば、どのように実装されているかという細かいことは気にせず、 | |
| 56 その文字列が他の文字列と同じように振る舞うとみなすことができる。 | |
| 57 | |
| 58 GHCi\footnote{Haskellの対話環境}では、式の前に :type コマンドを付けることで、式の型を確認することができる。 | |
| 59 | |
| 60 \begin{lstlisting}[caption=型の確認] | |
| 61 ghci> :type True | |
| 62 True :: Bool | |
| 63 \end{lstlisting} | |
| 64 | |
| 34 | 65 Haskell は静的型検査によりエラーを広範囲に検出することができる。 |
| 66 データ構造を独自の型で表現することができ、その定義したデータ構造も型検査でエラーがないか調べることができる。 | |
| 67 | |
| 15 | 68 \subsubsection{基本的な型} |
| 69 Haskell は多くの基本型を提供している。 | |
| 70 Haskell の基本型を表\ref{tab:type}に示す。 | |
| 71 Haskell では、全ての型の名前は大文字で始まる。 | |
| 72 | |
| 73 \begin{table}[!htbp] | |
| 74 \caption{Haskellの基本的な型} | |
| 75 \label{tab:type} | |
| 76 \begin{center} | |
| 77 \begin{tabular}{|c||c|} \hline | |
| 78 型名 & 概要 \\ \hline \hline | |
| 79 Bool & 真理値 \\ \hline | |
| 80 Char & 文字 \\ \hline | |
| 81 String & 文字列 \\ \hline | |
| 82 Int & 固定精度整数 \\ \hline | |
| 83 Integer & 多倍長整数 \\ \hline | |
| 84 Float & 単精度浮動小数点数 \\ \hline | |
| 85 \end{tabular} | |
| 86 \end{center} | |
| 87 \end{table} | |
| 88 | |
| 30 | 89 \newpage |
| 15 | 90 \subsubsection{リスト型} |
| 91 リストは同じ型の要素の並びである。角括弧で包み、各要素はコンマで区切る。 | |
| 92 リストの長さに制限はない。空リストは[]で表す。 | |
| 93 Haskell は遅延評価を行うので無限リストを作成することもできる。 | |
| 94 | |
| 95 リストの例をソースコード\ref{src:list}に示す。 | |
| 96 | |
| 97 \begin{lstlisting}[label=src:list, caption=Haskellのリスト] | |
| 98 ghci> :type [True, False, False] | |
| 99 [True, False, False] :: [Bool] | |
| 100 | |
| 101 ghci> :type ['a','b','c','d'] | |
| 102 ['a','b','c','d'] :: [Char] | |
| 103 | |
| 104 ghci> :type [[True, False], [False, True]] | |
| 105 [[True, False], [False, True]] :: [[Bool]] | |
| 106 \end{lstlisting} | |
| 107 | |
| 108 リストのリストを作ることもできる。 | |
| 109 | |
| 34 | 110 %\subsubsection{タプル型} |
| 111 %タプルは固定サイズの要素の組である。各要素の型は異なってもよい。 | |
| 112 %各要素をコンマで区切って、全体を括弧で包む。 | |
| 113 % | |
| 114 %タプルの例をソースコード\ref{src:tuple}に示す。 | |
| 115 % | |
| 116 %\begin{lstlisting}[label=src:tuple, caption=Haskellのタプル] | |
| 117 %ghci> :type (False, True) | |
| 118 %(False, True) :: (Bool, Bool) | |
| 119 % | |
| 120 %ghci> :type ('a', True, False) | |
| 121 %('a', True, False) :: (Char, Bool, Bool) | |
| 122 % | |
| 123 %ghci> :type ([True, False], 'a', 'b') | |
| 124 %([True, False], 'a', 'b') :: ([Bool], Char, Char) | |
| 125 %\end{lstlisting} | |
| 126 % | |
| 15 | 127 \subsubsection{型の安全性} |
| 8 | 128 |
| 15 | 129 Haskell では、評価の際に型に起因するエラーが起きないことを保証している。 |
| 130 引数として整数を受け取る関数に文字列を渡そうとしても Haskell のコンパイラはこれを受け付けない。 | |
| 131 Haskell は、すべての式、すべての関数に型があるためコンパイル時に多くのエラーを捕まえることができる。 | |
| 132 | |
| 133 型検査でも捕まえられないエラーは存在する。 | |
| 134 例えば、式 "1 `div` 0" は、型エラーではないが、0 での除算は定義されていないので評価時にエラーとなる。 | |
| 135 | |
| 136 \subsubsection{型推論} | |
| 137 Haskell は型推論を持つ。 | |
| 138 型推論のない静的型付け言語は、プログラマが型の宣言を行うことが強制されるが Haskell では型の宣言は必須ではない。 | |
| 139 | |
| 140 例として、型の宣言を省略し、引数を 2 倍にして返す関数を定義する。 | |
| 141 | |
| 142 \begin{lstlisting}[caption=doubleの宣言] | |
| 143 double x = x + x | |
| 144 \end{lstlisting} | |
| 145 | |
| 146 このとき、double の型は型推論され、次のように明示的に宣言したのと同じになる。 | |
| 147 | |
| 148 \begin{lstlisting}[caption=doubleの型推論] | |
| 149 double :: Num a => a -> a | |
| 150 double x = x + x | |
| 151 \end{lstlisting} | |
| 152 | |
| 153 この型の宣言は、「Num のインスタンスである a の型の値を引数にとり、a の型の値を返す」という意味である。 | |
| 154 a は、多相型である。多相型についてはのちほど説明する。 | |
| 155 | |
| 156 型推論では、適用可能な最も広い型が選択されてしまうため、制限するには明示的に型宣言を行う。 | |
| 157 明示的な型宣言は可読性の向上や問題の発見に役に立つため、トップレベルの関数には型を明記することが一般的である。 | |
| 158 | |
| 159 \subsubsection{型の定義} | |
| 160 Haskell で新しい型を宣言する一番簡単な方法は、type キーワードを使って既存の型に別名を付けることである。 | |
| 161 | |
| 162 基本型で説明した、String 型は、文字のリスト[Char]の別名である。 | |
| 163 標準ライブラリでは、ソースコード\ref{string}のように定義されている。 | |
| 164 | |
| 165 \begin{lstlisting}[label=string, caption=String型の定義] | |
| 166 type String = [Char] | |
| 167 \end{lstlisting} | |
| 168 | |
| 169 完全に新しい型を宣言するには、data キーワードを用いる。 | |
| 170 標準ライブラリにおける Bool 型はソースコード\ref{bool}のように定義されている。 | |
| 8 | 171 |
| 172 \begin{lstlisting}[label=bool, caption=Bool型の定義] | |
| 173 data Bool = False | True | |
| 174 \end{lstlisting} | |
| 175 | |
| 176 この型宣言は、「Bool 型は True または False の値を取り得る」ということを表している。 | |
| 15 | 177 型のために新しく定義された値、TrueやFalseは値コンストラクタである。 |
| 178 値コンストラクタは大文字で始まる必要があり、複数の型に対して同じ名前の値コンストラクタを用いることはできない。 | |
| 8 | 179 |
| 15 | 180 data キーワードによる型宣言では、値コンストラクタが引数を取ることもできる。 |
| 181 標準ライブラリにおける Maybe 型はソースコード\ref{maybe}のように定義されている。 | |
| 8 | 182 |
| 15 | 183 \begin{lstlisting}[label=maybe, caption=Maybe型の定義] |
| 184 data Maybe a = Nothing | Just a | |
| 8 | 185 \end{lstlisting} |
| 186 | |
| 15 | 187 Maybeは型引数を取るので、型コンストラクタと呼ばれる。 |
| 188 型コンストラクタは、型引数を受け取ってはじめて具体型を生成する。 | |
| 189 単なる Maybe という型の値は存在できない。 | |
| 190 Maybe Intや、Maybe Charといった形で存在することになる。 | |
| 191 具体型を生成するため何かしらの型引数を渡す必要があるが、 | |
| 192 殆どの場合、型コンストラクタに明示的に型引数を渡さなくても型推論があるので問題がない。 | |
| 8 | 193 |
| 15 | 194 data キーワードによる型宣言では、再帰的に定義することもできる。 |
| 195 例えば木構造といったデータ型はソースコード\ref{tree}のように定義できる。 | |
| 8 | 196 |
| 15 | 197 \begin{lstlisting}[label=tree, caption=再帰的なデータ型の定義] |
| 198 data Tree a = EmptyTree | Node a (Tree a) (Tree a) | |
| 8 | 199 \end{lstlisting} |
| 200 | |
| 15 | 201 この型宣言は、「Tree a 型は、空の木、もしくは何らかの値 a と 2 つの木を含む要素である」ということを表している。 |
| 202 | |
| 34 | 203 \subsubsection{多相型} |
| 204 Haskell の型は多相的である。 | |
| 205 型変数を使い、型を抽象化できる。 | |
| 206 型変数は、型安全を保ちながら、関数を複数の型に対して動作するようにできる。 | |
| 207 Haskell の型の名前は全て大文字から始まるが、型変数は小文字から始まる。 | |
| 208 任意の型のリストを引数に取り、その型の先頭要素を返すという関数 head の型はソースコード\ref{type_variable}のように定義される。 | |
| 209 | |
| 210 \begin{lstlisting}[label=type_variable, caption=型変数] | |
| 211 head :: [a] -> a | |
| 212 \end{lstlisting} | |
| 213 | |
| 214 \subsubsection{多重定義型} | |
| 215 Haskell の (+) は、整数や浮動小数点数のどちらにも使える。 | |
| 216 これは型にクラス制約を含めることで実現している。 | |
| 217 | |
| 218 \begin{lstlisting}[label=type_class, caption=クラス制約] | |
| 219 ghci> :t (+) | |
| 220 (+) :: Num a => a -> a -> a | |
| 221 \end{lstlisting} | |
| 222 | |
| 223 =$>$ というシンボルの前にあるものがクラス制約である。 | |
| 224 これは、a が Num 型クラスのインスタンスでなければいけないということを意味する。 | |
| 225 Num 型クラスのインスタンスとなる型は数値型である。 | |
| 226 | |
| 227 型クラスは型の振る舞いを定義するものである。 | |
| 228 ある型クラスのインスタンスである型は、その型クラスに属する関数の集まりを実装する。 | |
| 229 これは、それらの関数がその型ではどのような意味になるのか定義するということである。 | |
| 230 | |
| 231 例えば、Eq 型クラスのインスタンスとなる型は等値性をテストできる。 | |
| 232 この型クラスに属させるためには、(==)と、(/=)の 2 つの関数を実装する。 | |
| 233 | |
| 234 Haskell の型クラスは、動的型付けの利点を安全で使いやすい形で実現するものである。 | |
| 235 | |
| 15 | 236 自作のデータ型を作成する際は、型クラスを利用することで、既存の Haskell ライブラリを利用できる。 |
| 237 特定の型クラスは自動導出することも可能である。自動導出には deriving キーワードを使う。 | |
| 238 ソースコード\ref{deriving}は、Showのインスタンスを自動導出している。 | |
| 239 | |
| 240 \begin{lstlisting}[label=deriving, caption=型クラスの自動導出] | |
| 241 data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show) | |
| 242 \end{lstlisting} | |
| 8 | 243 |
|
16
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
244 \clearpage |
| 8 | 245 \section{モナド} |
| 246 Haskell では、さまざまな目的にモナドを使う。 | |
|
16
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
247 I/O 処理を行うためには IO モナドを使う必要がある。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
248 プログラミングを行うにあたり、I/O 処理は欠かせないため、Haskell を利用するにあたってモナドの理解は必須である。 |
| 8 | 249 |
|
16
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
250 モナドとは、型クラスの 1 つである。 |
| 8 | 251 モナドとなる型は、型変数として具体型をただ１つ取る。 |
| 252 これにより何かしらのコンテナに包まれた値を実現する。 | |
|
16
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
253 モナドの振る舞いは型クラスとして実装し、関数として return および $>$$>$= (bind) を定義する。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
254 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
255 \begin{lstlisting}[label=monad, caption=モナドに属する関数] |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
256 return :: Monad m => a -> m a |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
257 (>>=) :: Monad m => m a -> (a -> m b) -> m b |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
258 \end{lstlisting} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
259 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
260 return は値を持ち上げてコンテナに包む機能を実装する（図\ref{fig:monad_return}）。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
261 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
262 \begin{figure}[!htbp] |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
263 \begin{center} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
264 \includegraphics[scale=0.6]{./images/monad_return.pdf} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
265 \end{center} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
266 \caption{モナドに属する return 関数} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
267 \label{fig:monad_return} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
268 \end{figure} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
269 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
270 bind は、「コンテナに包まれた値」と、「普通の値を取りコンテナに包まれた値を返す関数」を引数にとり、コンテナに包まれた値をその関数に適用する（図\ref{fig:monad_bind}）。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
271 適用する際、前のコンテナの結果に依存して、後のコンテナの振る舞いを変えられる。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
272 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
273 \begin{figure}[!htbp] |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
274 \begin{center} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
275 \includegraphics[scale=0.6]{./images/monad_bind.pdf} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
276 \end{center} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
277 \caption{モナドに属する $>$$>$= (bind) 関数} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
278 \label{fig:monad_bind} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
279 \end{figure} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
280 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
281 この2つの関数を利用することにより、文脈を保ったまま関数を繋いでいくことができる。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
282 Haskell の遅延評価は記述した順序で実行することを保証しないが、モナドの bind は実行順序の指定も可能で、IO モナドを bind で繋いだものは記述順に実行することができる。 |
| 8 | 283 |
| 284 Haskellで副作用を持つ処理を実行するには、IO モナドを利用する。 | |
|
16
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
285 IO モナド自体は単なる命令書であり、命令ではない。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
286 bind を使って、小さな命令書を合成して大きな命令書を作成できる。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
287 最終的に、mainという名前をつけることで初めてランタイムにより実行される。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
288 |
| 28 | 289 Haskell の関数には副作用がないと述べたが、IO モナドを返す関数にも副作用は存在しない。 |
| 8 | 290 |
|
16
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
291 例えば、getChar という関数がある。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
292 呼び出した状況によって、返ってくる文字が違うため副作用があるようにみえる。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
293 しかし、実際にこの関数が返すのは、「一文字読み込む」という命令書である。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
294 どんな状況においても同じ命令書を返すため、副作用はない。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
295 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
296 \clearpage |
|
5
658281be77ec
describe the abstract
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
297 \section{並列実行} |
| 8 | 298 Haskellはデフォルトではシングルスレッドで走る。 |
| 28 | 299 並列に実行したい場合は、-threaded 付きでコンパイルし、RTS の -N オプションを付けて実行する。 |
| 8 | 300 -N オプションで指定された数だけ、OSのスレッドが立ち上がり実行される。 |
| 301 | |
| 302 \begin{lstlisting}[language=bash, label=concurrent, caption=並列実行の様子] | |
| 303 $ ghc -O2 par.hs -threaded | |
| 304 $ ./par +RTS -N2 | |
| 305 \end{lstlisting} | |
| 306 | |
| 307 当然これだけでは並列に動かず、並列に実行できるようにプログラムを書く必要がある。 | |
| 308 | |
| 309 Haskell は遅延評価を行うため、必要となるまで式の評価が遅延される。 | |
| 310 普段は気にする必要はないが、並列実行ではどのように評価されるか意識する必要がある。 | |
| 311 並列に動くように処理を分割したとしても、値が必要になるまで評価されない。 | |
| 312 この問題は、Control.DeepSeq モジュールにある deepseq 関数を使用し、式を即時評価することで解決できる。 | |
| 313 | |
| 314 Haskellの並列化手法はいくつかあるが、その中で最もシンプルなのは Eval モナドを利用することである。 | |
| 315 Control.Parallel.Strategies モジュールをインポートすることで使用できる。 | |
| 316 | |
| 317 | |
| 318 \begin{lstlisting}[label=eval, caption=Eval モナド] | |
| 319 data Eval a | |
| 320 instance Monad Eval | |
| 321 | |
| 322 runEval :: Eval a -> a | |
| 323 | |
| 324 rpar :: a -> Eval a | |
| 325 rseq :: a -> Eval a | |
| 326 \end{lstlisting} | |
| 327 | |
| 328 rpar は、引数が並列処理可能であることを示す。 | |
| 329 rseq は、引数を評価し、結果を待つように示す。 | |
| 330 どちらも式が完全に即時評価されるわけではないので、出力を挟んだり、deepseq 関数をうまく活用する必要がある。 | |
| 331 runEval は、評価を実行し結果を返す操作である。 | |
| 332 実際の利用方法として２つのパターンを紹介する。 | |
| 333 | |
| 334 | |
| 335 \begin{lstlisting}[label=rpar/rpar, caption=rpar/rpar] | |
| 336 runEval $ do | |
| 337 a <- rpar (f x) | |
| 338 b <- rpar (f y) | |
| 339 return (a,b) | |
| 340 \end{lstlisting} | |
| 341 | |
|
16
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
342 rpar/rpar パターンは即座に return される（図\ref{fig:rpar}）。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
343 単純に並列に動かしたい時に利用する。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
344 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
345 \begin{figure}[!htbp] |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
346 \begin{center} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
347 \includegraphics[scale=0.6]{./images/rpar_rpar.pdf} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
348 \end{center} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
349 \caption{rpar/rpar パターン} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
350 \label{fig:rpar} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
351 \end{figure} |
| 8 | 352 |
| 353 \begin{lstlisting}[label=rpar/rseq/rseq, caption=rpar/rseq/rseq] | |
| 354 runEval $ do | |
| 9 | 355 a <- rpar (f x) |
| 356 b <- rseq (f y) | |
| 357 rseq a | |
| 358 return (a,b) | |
| 8 | 359 \end{lstlisting} |
| 360 | |
|
16
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
361 rpar/rseq/rseq パターンは、f x および f y の結果を待ってから return する（図\ref{fig:rseq}）。 |
| 8 | 362 他の処理が結果を必要としている時に利用する。 |
| 363 | |
|
16
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
364 \begin{figure}[!htbp] |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
365 \begin{center} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
366 \includegraphics[scale=0.6]{./images/rpar_rseq.pdf} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
367 \end{center} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
368 \caption{rpar/rseq/rseq パターン} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
369 \label{fig:rseq} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
370 \end{figure} |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
371 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
372 rparは非常にコストが低いため、リストに対してmapするといった適用の仕方でも充分な並列性が出る。 |
|
eb6a70fc9c9f
describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
373 そのための関数 parMap も、 Control.Parallel.Strategies モジュールには用意されている。 |