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