Mercurial > hg > Papers > 2015 > atton-midterm

comparison bachelor_middle_draft.tex @ 4:0805d4984b1f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update v2.1
author Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
date Wed, 29 Oct 2014 15:05:38 +0900
parents 331d9984930f
children 156ae5d5750b
comparison
equal deleted inserted replaced
3:331d9984930f 4:0805d4984b1f
40 40
41 % {{{ 限定されたプログラムの変更を表す Delta Monad 41 % {{{ 限定されたプログラムの変更を表す Delta Monad
42 42
43 \section{限定されたプログラムの変更を表す Delta Monad} 43 \section{限定されたプログラムの変更を表す Delta Monad}
44 Monad を用いたプログラムの変更の例として、プログラミング言語HaskellにおけるMonadを利用する。 44 Monad を用いたプログラムの変更の例として、プログラミング言語HaskellにおけるMonadを利用する。
45 Haskell におけるMonadとはメタ計算と対応されたデータ型である。 45 Haskell におけるMonadとはメタ計算を内包したデータ型である。
46 Monadであるデータ型は任意の型を内包することができ、内包した型に対する計算を行なった際にメタ計算も同時に行なう。 46 Monadであるデータ型は任意の型の値を内包することができ、内包した型に対する計算を行なった際にメタ計算も同時に行なう。
47 47
48 Haskell において限定されたプログラムの変更を表すことができる Delta Monad を定義した。 48 Haskell において限定されたプログラムの変更を表すことができる Delta Monad を定義した。
49 Delta Monad におけるプログラムの変更は、変更前と変更後の実行結果を両方持つことによって表現する。 49 Delta Monad におけるプログラムの変更は、変更前と変更後の実行結果を両方持つことによって表現する。
50 また、実行結果に対する変更履歴を持ち、2つ変更履歴の比較によってプログラムがどのように変更したか判断する。 50 また、実行結果に対する変更履歴を持ち、2つ変更履歴の比較によってプログラムがどのように変更したか判断する。
51 51
116 116
117 117
118 % {{{ Delta Monad におけるプログラムの変更例 118 % {{{ Delta Monad におけるプログラムの変更例
119 119
120 \section{Delta Monad におけるプログラムの変更例} 120 \section{Delta Monad におけるプログラムの変更例}
121 Delta Monad を用いたHaskellのプログラムを示す(図\ref{delta-program})。 121 変更例となるHaskellのプログラムを示す(図\ref{raw-program-before})。
122 122
123 % {{{ delta.hs 123 % {{{ raw-program-before
124
125 \begin{breakbox}
126 {\scriptsize
127 \begin{verbatim}
128 generator :: Int -> [Int]
129 generator x = [1..x]
130
131 primeFilter :: [Int] -> [Int]
132 primeFilter xs = filter isPrime xs
133
134 count :: [Int] -> Int
135 count xs = length xs
136
137 primeCount :: Int -> Int
138 primeCount x = count . primeFilter . generator $ x
139 \end{verbatim}
140 }
141 \caption{変更前のHaskellプログラム}
142 \label{raw-program-before}
143 \end{breakbox}
144
145 % }}}
146
147
148 このプログラムは整数nを取り、1からnまでの整数の中から素数の個数を調べるプログラムである。
149 1からnまでの整数の個数を調べる primeCount 関数は3つの関数からなる。
150
151 \begin{itemize}
152 \item 1 から n までの整数を返す関数 generator
153 \item 整数のリストから素数である整数のみを残したリストを返す関数 primeFilter
154 \item リストの中に存在する要素の個数を返す関数 count
155 \end{itemize}
156
157 ここで、 primeFilter 関数を変更する。
158 素数である整数を残すのではなく、偶数を残すようにする。
159 Delta Monad を使わずに primeFilter 関数を変更すると図\ref{raw-program-after}のプログラムとなる。
160
161 % {{{ raw-program-after
162
163 \begin{breakbox}
164 {\tt
165 primeFilter :: [Int] -> [Int]
166
167 primeFilter xs = filter \underline{even} xs
168 }
169 \caption{変更後の primeFilter 関数(変更点は下線)}
170 \label{raw-program-after}
171 \end{breakbox}
172
173 % }}}
174
175 プログラム(図\ref{raw-program-before})に対する図\ref{raw-program-after}の変更を Delta Monad で記述したものが図\ref{delta-program}のプログラムである。
176
177 % {{{ delta-program
124 178
125 \begin{breakbox} 179 \begin{breakbox}
126 {\scriptsize 180 {\scriptsize
127 \begin{verbatim} 181 \begin{verbatim}
128 generator :: Int -> Delta [Int] 182 generator :: Int -> Delta [Int]
140 194
141 primeCount :: Int -> Delta Int 195 primeCount :: Int -> Delta Int
142 primeCount x = generator x >>= primeFilter >>= count 196 primeCount x = generator x >>= primeFilter >>= count
143 \end{verbatim} 197 \end{verbatim}
144 } 198 }
145 \caption{Delta Monadを用いたプログラムの例} 199 \cprotect\caption{図\ref{raw-program-before}のプログラムに対する図\ref{raw-program-after}の変更を Delta Monad で記述した例}
146 \label{delta-program} 200 \label{delta-program}
147 \end{breakbox} 201 \end{breakbox}
148 202
149 % }}} 203 % }}}
150 204
151 このプログラムは整数nを取り、1からnまでの整数の中から素数の個数を調べるプログラムである。 205 Delta Monad を用いたプログラムでは全ての関数はDelta Monadを返す関数として記述される。
152 1からnまでの整数の個数を調べるprimeCount 関数は3つの関数からなる 206 変更される primeFilter 関数は、素数によるフィルタと偶数によるフィルタの両方の結果を持ったDelta Monad を返すよう変更する。
153
154 \begin{itemize}
155 \item 1 から n までの整数を返す関数 generator
156 \item 整数のリストから素数であるもののみを残したリストを返す関数 primeFilter
157 \item リストの中に存在する要素の個数を返す関数 count
158 \end{itemize}
159
160 このプログラムの primeFilter 関数が返す Delta Monad を変更する。
161 本来ならば素数である整数のみを返す計算だったが、変更により偶数である整数のみを返すようにした。
162 図\ref{delta-program}のプログラムを実行した例が図\ref{delta-result}である。 207 図\ref{delta-program}のプログラムを実行した例が図\ref{delta-result}である。
163 208
164 % {{{ results 209 % {{{ results
165 210
166 \begin{breakbox} 211 \begin{breakbox}
176 \label{delta-result} 221 \label{delta-result}
177 \end{breakbox} 222 \end{breakbox}
178 223
179 % }}} 224 % }}}
180 225
226 Delta Monad による実行結果は2つの実行結果が存在する。
181 変更前のプログラムの実行順序が上側の実行結果である。 227 変更前のプログラムの実行順序が上側の実行結果である。
182 \begin{itemize} 228 \begin{itemize}
183 \item 1 から 10 までのリストを作成し 229 \item 1 から 10 までのリストを作成し
184 \item 素数のみを残すために 2,3,5,7 が残り 230 \item 素数のみを残すために 2,3,5,7 が残り
185 \item その個数を数えるために4となる 231 \item その個数を数えるために4となる
216 262
217 \begin{thebibliography}{9} 263 \begin{thebibliography}{9}
218 264
219 \bibitem{moggi} Eugenio Moggi, Notion of Computation and Monads(1991) 265 \bibitem{moggi} Eugenio Moggi, Notion of Computation and Monads(1991)
220 \bibitem{proofs-and-types} Jean-Yves Girard, Paulr Taylor, Yves Lafont, Proofs and Types(1990) 266 \bibitem{proofs-and-types} Jean-Yves Girard, Paulr Taylor, Yves Lafont, Proofs and Types(1990)
267 \bibitem{category} Michael Barr and Chariles Wells, Category Theory for Computing Science
221 \bibitem{agda} The Agda Wiki - Agda \url{http://wiki.portal.chalmers.se/agda/pmwiki.php} 268 \bibitem{agda} The Agda Wiki - Agda \url{http://wiki.portal.chalmers.se/agda/pmwiki.php}
222 269
223 \end{thebibliography} 270 \end{thebibliography}
224 \end{document} 271 \end{document}