\chapter{プログラムの変更を表現する Delta Monad}
\label{chapter:delta}

本研究では Monad によりプログラムの変更を定義する。

そのためにまずはプログラムを定義する。
プログラムは型付けされた値と、値を値へと写像する関数のみで構成されるものとする。
プログラムの実行は関数の値への適用とする。
入出力といった、値や関数で表現できない計算はメタ計算とする。
メタ計算をある性質を持つデータ構造に対応させ、メタ計算が必要な関数は値をデータ構造へと写像することで入出力といった処理を実現する。
メタ計算とデータ構造の対応に用いる性質が Monad である。

プログラムの変更とは関数や値が変更されることであり、変更される量には単位があるとする。
最初の変更単位をバージョン1とし、変更された後のプログラムはバージョンが1増加する。

ここで、プログラムが変更される際に過去のバージョンのプログラムも保存するメタ計算を提案する。
全ての変更単位で変更されたプログラムを保存し、それらを比較することでプログラムの変更を表現しようと考えた。
このメタ計算を表す Monad を Delta Monad と呼ぶ。

\section{Delta Monad の定義}

任意の型Aに対するメタ計算Tを考えた時、プログラムの変更は式\ref{exp:meta_computation_definition}のように定義される。

\begin{equation}
    T A = V A
    \label{exp:meta_computation_definition}
\end{equation}

V はプログラムの全てバージョンの集合であり、V AとすることでAに対応する値の集合を返すものとする。



\section{Haskell における Delta Monad の実装例}

式\ref{exp:meta_computation_definition}のメタ計算をMonadで実現する。

実装例としてプログラミング言語 Haskell を用いる。

まずは全てのプログラムのバージョンを表わすデータ型 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 を用いたプログラムの変更の記述例}
プログラムの変更を表現するメタ計算に対応するデータ型 Delta が記述できた。

実際に Haskell で Delta を用いたプログラムの変更例を\ref{src:delta_example}に示す。

\begin{table}[html]
    \lstinputlisting[label=src:delta_example, caption=Deltaを用いたプログラムの例]
                    {src/delta_example.hs}
\end{table}

\ref{src:delta_example}は1からnの間の整数に含まれる特定の数の個数を調べるプログラム numberCount である。

このプログラムは3つの関数からなり、2つのバージョンを含む。

\begin{itemize}
    \item generator

        1からnの間の整数を生成する関数である。
        nを渡すことにより1からnの間の整数のリストを返す。

    \item numberFilter

        数のリストから特定の数のみを絞り込む関数である。
        バージョン1では素数の数のみを絞り込み、バージョン2では偶数の数のみを絞り込んでいる。

    \item count

        数の個数を数える関数である。
        整数はリストで与えられるため、リストの長さが個数であるとした。
\end{itemize}

これらの関数3つをMonad の \verb/>>=/ によってメタ計算を含む関数呼び出しとして実行する。
3つの関数を実行する関数が numberCount 関数であり、この関数がプログラム本体である。
numberCount を実行すると \ref{txt:delta_example_result}のような結果が得られる。

\begin{table}[html]
    \lstinputlisting[label=txt:delta_example_result, caption=numberCountプログラムの実行結果] {src/delta_example_result.txt}
\end{table}

これはnに1000を与えた結果である。
バージョン1の時は素数の数を求めるため計算結果は168であり、バージョン2の時は偶数の数を求めるために計算結果は500となる。

3つの関数で構成されたプログラムに対して1つの変更を加えたプログラムを表現することができた。
つまり、Monad によってプログラムの変更をメタ計算として定義できたと言える。

Haskell において実装した Delta Monad はプログラムの変更を含めた計算もメタ計算としてHaskellで実行する。
これはプログラムの変更からどのような処理を導くかをメタ計算として Haskell で実行可能であることを意味する。
つまり、図\ref{fig:non_delta_example}のようにプログラムにおいてバージョンが変わるごとにバージョン間の関係が存在しない状態から、図\ref{fig:delta_example}のようにプログラムの変更を含めてプログラムを実行可能となったことを意味する。
例えば、プログラムの実行時にバージョン間の挙動の比較することで過去の挙動との差異を指摘することなどが可能となる。

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[scale=0.8]{fig/non_delta_example.pdf}
        \caption{Deltaを用いない通常のプログラムの例}
        \label{fig:non_delta_example}
    \end{center}
\end{figure}

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[scale=0.8]{fig/delta_example.pdf}
        \caption{Deltaを用いたプログラムの例}
        \label{fig:delta_example}
    \end{center}
\end{figure}