Mercurial > hg > Papers > 2015 > atton-thesis
changeset 8:c4da3e667aad
Add Delta definition in Haskell
| author | Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sat, 07 Feb 2015 12:13:59 +0900 |
| parents | ff369fd176ff |
| children | 324111203070 |
| files | delta.tex main.tex src/delta_constructor.hs src/delta_instance_monad.hs src/monad_class.hs |
| diffstat | 5 files changed, 91 insertions(+), 1 deletions(-) [+] |
line wrap: on
line diff
--- a/delta.tex Sat Feb 07 11:41:37 2015 +0900 +++ b/delta.tex Sat Feb 07 12:13:59 2015 +0900 @@ -27,12 +27,67 @@ V はプログラムの全てバージョンの集合であり、V AとすることでAに対応する値の集合を返すものとする。 + + \section{Haskell における Delta Monad の実装例} \ref{meta_computation_definition}のメタ計算をMonadで実現する。 実装例としてプログラミング言語 Haskell を用いる。 -% TODO... + +まずは全てのプログラムのバージョンを表わすデータ型 Delta を考える。 +Delta の定義は \ref{src:delta_constructor} とする。 + +\begin{table}[html] + \lstinputlisting[label=src:delta_constructor, caption=Haskellにおけるデータ型Deltaの定義]{src/delta_constructor.hs} +\end{table} + +データ型 Delta はコンストラクタ Delta もしくは Mono によって構成される。 +バージョンが1である値は Mono によって構成される。 +プログラムを変更する際には、コンストラクタ Delta を用いて記述し、変更後の値と前のバージョンを持つ。 +なお、a とは任意の型であり、Delta が任意の型の値に対してもデータ型を構築できることを示す。 + +データ型 Delta に対応するメタ計算は\ref{src:delta_instance_monad}と定義する。 + +\begin{table}[html] + \lstinputlisting[label=src:delta_instance_monad, caption=Haskell におけるデータ型Deltaとメタ計算の関連付け] + {src/delta_instance_monad.hs} +\end{table} + +Haskell においてメタ計算とデータ型の対応は Monad によって行なうため、 Monad という型クラスが用意されている。 +型クラスとは特定の性質を持つ型をまとめるための制約である。 +ある型が型クラスに属するためには制約として型クラスによって指定された関数を定義する必要がある。 +型クラス Monad に要請される関数は return と \verb/>>=/ であり、型クラスは\ref{src:monad_class}のように定義されている。 + +\begin{table}[html] + \lstinputlisting[label=src:monad_class, caption=Haskell における Monad 型クラス] + {src/monad_class.hs} +\end{table} + +関数 return は任意の型aを受けとり、メタ計算と対応された型に対応させて返す。 +\verb/>>=/ は中置関数であり、left operand と right operand を取る。 +left operand であるメタ計算と対応された値と、right operand であるメタ計算と対応された値を返す関数を取り、メタ計算を行ないながら関数を適用する。 + +型クラスMonad を Delta に適用した結果は以下のようになる。 + +\begin{itemize} + \item 関数 return + + 通常の値をメタ計算と対応させるため、値をバージョン1の値とする。 + そのためにコンストラクタ Mono を用いる。 + + \item 中置関数 \verb/>>=/ + + メタ計算を含んだ関数の適用であるため、値と関数の同じバージョンを計算して返すものとなる。 + もしバージョン1であった場合はコンストラクタは Mono であるため、Mono が持っている値に対して関数を適用することとなる。 + もしバージョンが1で無い場合のコンストラクタは Delta であるため、先頭の値を用いて計算し、残りの値と結合することとなる。 + その際、先頭の値を取り出すために headDelta 関数を、先頭以外の値を取り出すために tailDelta 関数を用いる。 +\end{itemize} + +なお、中置関数 \verb/>>=/ で用いたコンストラクタによる処理の分岐はパターンマッチと呼ばれる。 +Haskell ではコンストラクタごとに関数を記述することでパターンマッチを実現する。 \section{Delta を用いたプログラムの変更の記述} +% TODO: ... +プログラムの変更を表現するメタ計算に対応するデータ型Deltaが記述できた。
--- a/main.tex Sat Feb 07 11:41:37 2015 +0900 +++ b/main.tex Sat Feb 07 12:13:59 2015 +0900 @@ -3,6 +3,8 @@ \usepackage{mythesis} \usepackage{multirow} \usepackage{here} +\usepackage{listings} +%\usepackage{listings, jlisting} \setlength{\itemsep}{-1zh} \title{圏によるプログラムの変更の形式化} \icon{ @@ -23,6 +25,30 @@ \makeatother \setlength\abovecaptionskip{0pt} +%% listings settings + +\lstset{% + frame=single, + stringstyle={\ttfamily}, + commentstyle={\ttfamily}, + identifierstyle={\ttfamily}, + keywordstyle={\ttfamily}, + basicstyle={\ttfamily}, + breaklines=true, + xleftmargin=0zw, + xrightmargin=0zw, + framerule=.2pt, + columns=[l]{fullflexible}, + numbers=left, + stepnumber=1, + numberstyle={\scriptsize}, + numbersep=1em, + language={Java}, + tabsize=4, + lineskip=-0.5zw, + morecomment={[s][]{/**}{*/}}, +} + \begin{document} % タイトル
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/delta_constructor.hs Sat Feb 07 12:13:59 2015 +0900 @@ -0,0 +1,1 @@ +data Delta a = Mono a | Delta a (Delta a)