Mercurial > hg > Papers > 2015 > atton-thesis
diff paper/delta.tex @ 75:0286bbcb59af
Mini fixes
author | Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 17 Feb 2015 17:41:32 +0900 (2015-02-17) |
parents | ac56c2f84dfb |
children | 3562c274db60 |
line wrap: on
line diff
--- a/paper/delta.tex Tue Feb 17 16:56:18 2015 +0900 +++ b/paper/delta.tex Tue Feb 17 17:41:32 2015 +0900 @@ -11,9 +11,8 @@ まずはプログラムを定義する。 プログラムは型付けされた値と、値を値へと写像する関数のみで構成される。 -プログラムの実行は関数の値への適用とする。 -入出力といった、値や関数のみで表現できない計算はメタ計算とする。 -メタ計算を特定のデータ構造に対応させ、メタ計算が必要な関数は値をデータ構造へと写像することで入出力といった処理を実現する。 +プログラムの実行は関数の値への適用とし、入出力といった、値や関数で表現できない計算はメタ計算とする。 +メタ計算を特定のデータ構造に対応させ、メタ計算が必要な関数は値をデータ構造へと写像することで入出力処理を実現する。 メタ計算とデータ構造の対応に用いる性質が Monad である。 例えば、失敗する可能性があるメタ計算 T は式\ref{exp:partiality}のように定義できる。 @@ -23,8 +22,8 @@ \label{exp:partiality} \end{equation} -型 A の値に対応するメタ計算 T は、A と $ \bot $ の論理和として表現できる。 -計算に成功した際は A を返し、失敗した場合は $ \bot $ を返す。 +型 A の値に対応するメタ計算 T A は、A と $ \bot $ の論理和として表現できる。 +計算に成功した際は型 A の値を返し、失敗した場合は $ \bot $ を返す。 ここで、失敗しない前提で作成されたプログラムに対して、失敗する可能性を表現するメタ計算を対応させる。 プログラムは型 A の値x と、型 A の値を取り型 B の値を返す関数f, 型B の値を取り型Cの値を返す関数g によって構成されるとする(式\ref{exp:non_failure_program})。 @@ -34,16 +33,11 @@ \label{exp:non_failure_program} \end{equation} -ここで関数f は失敗する可能性があるとする。 -その時、f が失敗した場合の計算を考える必要がある。 -この計算の実現方法はいくつか存在する。 -計算g に失敗の判断を追加したり、例外機構により失敗を補足することで呼び出し元の関数で判断するなどがある。 +ここで関数f は失敗する可能性がある時、f をメタ計算によって拡張することで失敗を実現する。 -実現方法の1つとして、 Monad を用いたメタ計算がある。 -Monad により失敗した際の計算をメタ計算としてデータ構造に紐付ける。 式\ref{exp:partiality} で定義したように、計算の成功は型 A 値を返し、失敗は $ \bot $ を返す。 +$ \bot $ となった時点で計算を中断するメタ計算を定義すれば、失敗を含めた関数を表現できる。 計算に失敗した際に対応するメタ計算を定義し、関数をそのメタ計算で拡張することで失敗に対する処理が実現できる。 -例えば、 A に対してはそのまま関数の適用を行ない、 $ \bot $ に対しては $ \bot $ を返すようなメタ計算を定義することで、計算が失敗した時に計算を終了することができる。 型A を持つx の値をメタ計算と対応して型 T A とした値を x' 、メタ計算による関数の拡張を * と記述すると、式\ref{exp:non_failure_program} の式は式\ref{exp:failure_program} のように書ける。 @@ -85,9 +79,7 @@ \section{Haskell における Delta Monad の実装例} -式\ref{exp:meta_computation_definition}のメタ計算をMonadで実現する。 - -実装例としてプログラミング言語 Haskell を用いる。 +式\ref{exp:meta_computation_definition}のメタ計算をプログラミング言語 Haskell を実装し、プログラムの変更が表現できることを示す。 まずは全てのプログラムのバージョンを表わすデータ型 Delta を考える。 Delta の定義はリスト\ref{src:delta_constructor} とする。 @@ -99,6 +91,7 @@ データ型 Delta はコンストラクタ Delta もしくは Mono によって構成される。 バージョンが1である値は Mono によって構成される。 プログラムを変更する際には、コンストラクタ Delta を用いて記述し、変更後の値と前のバージョンを持つ。 +Delta で記述することで、プログラムの変更に沿った長さ1以上のリスト構造が構築される。 なお、a とは任意の型であり、Delta が任意の型の値に対してもデータ型を構築できることを示す。 Haskell においてメタ計算とデータ型の対応は Monad によって行なうため、 Monad という型クラスが用意されている。