# HG changeset patch # User Yasutaka Higa # Date 1424151160 -32400 # Node ID b1271d62390cbdb7188c60260e7c2aa4ba3f3447 # Parent b5c04cca699bbda7c8572639bad90c63d900ff2d Mini fixes diff -r b5c04cca699b -r b1271d62390c paper/main.pdf Binary file paper/main.pdf has changed diff -r b5c04cca699b -r b1271d62390c prepaper/115763K.pdf Binary file prepaper/115763K.pdf has changed diff -r b5c04cca699b -r b1271d62390c prepaper/115763K.tex --- a/prepaper/115763K.tex Tue Feb 17 12:28:48 2015 +0900 +++ b/prepaper/115763K.tex Tue Feb 17 14:32:40 2015 +0900 @@ -49,7 +49,7 @@ \begin{abstract} Reliability of program reduced by many factors. Generally, reliability changes due to modification. -We formalize modification of program through Monad. +We formalize modification of program using Monad. We define Delta Monad as meta computation that save behavior when modify program. Delta help to improve reliability. For example, debug method that compare traces of different versions is available. @@ -57,7 +57,6 @@ \end{abstract} \section{プログラムの変更の形式化} -本研究はプログラムの信頼性を向上させることを目的とする。 信頼性とはプログラムが正しく動作する保証であり、プログラムのバグなど多くの原因により低下する。 信頼性が変化する点としてプログラムの変更に注目し、プログラムの変更を Monad を用いたメタ計算として形式化する。 加えて、定義した計算が Monad 則を満たすか証明する。 @@ -65,16 +64,14 @@ \section{メタ計算と Monad} プログラムを形式化するにあたり、プログラムを定義する。 プログラムの要素は型付けされた値と関数により定義され、関数は値から値への写像を行なう。 -プログラムの実行は関数の適用として表される。 -この時、入出力といった値の写像のみで表現できない計算を表現するために Monad を用いる。 -プログラムにおける Monad とはデータ構造とメタ計算の関連付けであり、メタ計算とは計算を行なう計算である ~\cite{Moggi:1991:NCM:116981.116984}。 -メタ計算として入出力機構をプログラムの計算とは別に定義し、入出力を利用したい関数は値をメタ計算と関連付けられたデータ型へと写像することで実現する。 -Monad を用いることでプログラムの内部ではメタ計算を扱わずにメタ計算を実現できる。 +プログラムの実行は関数の適用として表わされる。 +この時、入出力といった値の写像で表現できない計算は Monad を用いいたメタ計算とすることで解決できる~\cite{Moggi:1991:NCM:116981.116984}。 \section{変更を表す Delta Monad} -本研究ではプログラムの変更を表すメタ計算として、変更時に過去のプログラムも保存するメタ計算を提案する。 -このメタ計算に対応する Monad として Delta Monad を定義し、プログラミング言語 Haskell にて実装する。 +プログラムの変更を表すメタ計算として、変更時に過去のプログラムも保存する Delta Monad を提案する。 Delta Monad では変更単位をバージョンとし、全てのバージョンを保存しつつ実行することができる。 +Delta Monad をプログラミング言語 Haskell において実装し、異なるバージョンのプログラムを同時に実行する。 + まずは、Delta Monad と対応するデータ型 Delta を定義する(リスト\ref{src:delta_data})。 \begin{table}[html] @@ -96,9 +93,9 @@ コンストラクタが Mono であった場合はバージョン1であるためバージョン1どうしの計算を行ない、バージョンが1より大きい Delta で構成される場合は、先頭のバージョンどうしを計算し、先頭を除いた形に変形してから再帰的にメタ計算を適用する。 \section{Delta Monad を用いたプログラムの例} -Delta Monad を用いてプログラムの変更を記述する。 +Delta Monad を用いて、異なるバージョンのプログラムを同時に実行した例を示す。 -まずは変更の対象となるプログラム numberCount を示す(リスト\ref{src:numberCountV1})。 +まずは変更の対象となる numberCount プログラムのバージョン1を示す(リスト\ref{src:numberCountV1})。 \begin{table}[html] \lstinputlisting[label=src:numberCountV1, @@ -108,22 +105,16 @@ numberCount プログラムは、1 から n の整数において特定の数の個数を数えるプログラムである。 プログラムは3つの関数によって表現される。 -\begin{itemize} - \item generator - n を取り、1からnまでの整数のリストを返す - - \item numberFilter +{\tt generator} : +n を取り、1からnまでの整数のリストを返す - 整数のリストを取り、特定の性質を持つ数のみを残す。 - バージョン1では素数の数のみを残す。 - - \item count +{\tt numberFilter} : +整数のリストを取り、特定の性質を持つ数のみを残す。 +バージョン1では素数の数のみを残す。 - 整数のリストを取り、その個数を数える。 - -\end{itemize} - +{\tt count} : +整数のリストを取り、その個数を数える。 次に、numberCount プログラムを変更する。 変更点は numberFilter 関数の抽出条件とし、素数判定による抽出から偶数判定による抽出に変更する。 @@ -156,7 +147,7 @@ numberCount プログラムに対して 1000 を与えると、1 から 1000 までの中から素数の個数を数えた 168 と、偶数の個数を数えた500が得られる。 このように Delta Monad によってプログラムの変更を表すことで全てのバージョンを同時に実行することが可能となる。 -なお、 Delta が Monadであることを保証するMonad則を満たすることは証明支援言語Agda~\cite{agdawiki}によって証明した。 +なお、 Delta が Monadであることを保証するMonad則を満することを証明支援言語Agda~\cite{agdawiki}によって証明した。 \section{他の Monad との組み合せ} Delta Monad によりプログラムの変更を表現することができた。 diff -r b5c04cca699b -r b1271d62390c prepaper/src/numberCount1.hs --- a/prepaper/src/numberCount1.hs Tue Feb 17 12:28:48 2015 +0900 +++ b/prepaper/src/numberCount1.hs Tue Feb 17 14:32:40 2015 +0900 @@ -1,5 +1,5 @@ generator x = [1..x] -numberFilter xs = filter isPrime xs +numberFilter xs = filter @ {\underline {isPrime}} $ _1 $ @ xs count xs = length xs numberCount x = count (numberFilter (generator x)) diff -r b5c04cca699b -r b1271d62390c prepaper/src/numberCount2.hs --- a/prepaper/src/numberCount2.hs Tue Feb 17 12:28:48 2015 +0900 +++ b/prepaper/src/numberCount2.hs Tue Feb 17 14:32:40 2015 +0900 @@ -1,5 +1,5 @@ generator x = [1..x] -numberFilter xs = filter @ {\underline {even}} @ xs +numberFilter xs = filter @ {\underline {even}} $ _2 $ @ xs count xs = length xs numberCount x = count (numberFilter (generator x)) diff -r b5c04cca699b -r b1271d62390c prepaper/src/numberCountDelta.hs --- a/prepaper/src/numberCountDelta.hs Tue Feb 17 12:28:48 2015 +0900 +++ b/prepaper/src/numberCountDelta.hs Tue Feb 17 14:32:40 2015 +0900 @@ -1,6 +1,6 @@ generator x = Mono [1..x] -numberFilter xs = let primeList = filter isPrime xs - evenList = filter even xs in +numberFilter xs = let primeList = filter @ {\underline {isPrime} $ _1 $ @ xs + evenList = filter @ {\underline {even} $ _2 $ @ xs in Delta evenList (Mono primeList) count xs = return (length xs)