Mercurial > hg > Papers > 2015 > atton-thesis

annotate paper/delta.tex @ 63:c75ba6313e39

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Writing prepaper...
author Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
date Tue, 17 Feb 2015 12:08:10 +0900
parents 1181b4facaf9
children ac56c2f84dfb
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 \chapter{プログラムの変更を表現する Delta Monad}
11
76ce5bb18092 Add Category definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
2 \label{chapter:delta}
6
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 本研究では Monad によりプログラムの変更を定義する。
49
ba7f0b5454ab Add description for DeltaM definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
5 第\ref{chapter:delta}章ではプログラムの変更を表す Delta Monad を定義し、その使用例とメタ計算の例を示す。
ba7f0b5454ab Add description for DeltaM definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
6 なお、Monad についての定義と解説は第\ref{chapter:category}章と第\ref{chapter:functional_programming}章にて行なう。
6
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7
63
c75ba6313e39 Writing prepaper...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
8 % {{{ Monad とメタ計算
c75ba6313e39 Writing prepaper...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
9 \section{Monad とメタ計算}
c75ba6313e39 Writing prepaper...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
10 \label{section:monad_with_meta_computation}
30
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
11
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
12 まずはプログラムを定義する。
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
13 プログラムは型付けされた値と、値を値へと写像する関数のみで構成される。
6
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 プログラムの実行は関数の値への適用とする。
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
15 入出力といった、値や関数のみで表現できない計算はメタ計算とする。
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
16 メタ計算を特定のデータ構造に対応させ、メタ計算が必要な関数は値をデータ構造へと写像することで入出力といった処理を実現する。
6
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 メタ計算とデータ構造の対応に用いる性質が Monad である。
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18
30
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
19 例えば、失敗する可能性があるメタ計算 T は式\ref{exp:partiality}のように定義できる。
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
20
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
21 \begin{equation}
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
22 T A = A_{ \bot } (i.e. A + \left\{ \bot \right\})
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
23 \label{exp:partiality}
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
24 \end{equation}
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
25
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
26 型 A の値に対応するメタ計算 T は、A と $ \bot $ の論理和として表現できる。
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
27 計算に成功した際は A を返し、失敗した場合は $ \bot $ を返す。
30
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
28
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
29 ここで、失敗しない前提で作成されたプログラムに対して、失敗する可能性を表現するメタ計算を対応させる。
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
30 プログラムは型 A の値x と、型 A の値を取り型 B の値を返す関数f, 型B の値を取り型Cの値を返す関数g によって構成されるとする(式\ref{exp:non_failure_program})。
30
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
31
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
32 \begin{equation}
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
33 g ( f ( x ))
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
34 \label{exp:non_failure_program}
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
35 \end{equation}
6
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36
30
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
37 ここで関数f は失敗する可能性があるとする。
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
38 その時、f が失敗した場合の計算を考える必要がある。
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
39 この計算の実現方法はいくつか存在する。
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
40 計算g に失敗の判断を追加したり、例外機構により失敗を補足することで呼び出し元の関数で判断するなどがある。
30
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
41
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
42 実現方法の1つとして、 Monad を用いたメタ計算がある。
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
43 Monad により失敗した際の計算をメタ計算としてデータ構造に紐付ける。
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
44 式\ref{exp:partiality} で定義したように、計算の成功は型 A 値を返し、失敗は $ \bot $ を返す。
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
45 計算に失敗した際に対応するメタ計算を定義し、関数をそのメタ計算で拡張することで失敗に対する処理が実現できる。
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
46 例えば、 A に対してはそのまま関数の適用を行ない、 $ \bot $ に対しては $ \bot $ を返すようなメタ計算を定義することで、計算が失敗した時に計算を終了することができる。
30
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
47
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
48 型A を持つx の値をメタ計算と対応して型 T A とした値を x' 、メタ計算による関数の拡張を * と記述すると、式\ref{exp:non_failure_program} の式は式\ref{exp:failure_program} のように書ける。
6
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49
30
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
50 \begin{equation}
49
ba7f0b5454ab Add description for DeltaM definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
51 g^{*} ( f^{*} ( x' ))
30
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
52 \label{exp:failure_program}
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
53 \end{equation}
14
586f3ce1effe Add folding for section
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
54
49
ba7f0b5454ab Add description for DeltaM definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
55 ここで重要な点は、元の関数 $ f $ と $g$ から $f^{*}$ と $g^{*}$ が導けることである。
ba7f0b5454ab Add description for DeltaM definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
56 メタ計算が無い関数 $ f $ とメタ計算を持つ関数 $ f^{*} $ が1対1に対応することは Monad により保証されている。
30
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
57 このように、値と関数で表されたプログラムにおいてメタ計算を用いることで、計算を拡張することができる。
6
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58
63
c75ba6313e39 Writing prepaper...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
59 % }}}
c75ba6313e39 Writing prepaper...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
60
c75ba6313e39 Writing prepaper...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
61 % {{{ Delta Monad の定義
c75ba6313e39 Writing prepaper...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
62
c75ba6313e39 Writing prepaper...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
63 \section{Delta Monad の定義}
c75ba6313e39 Writing prepaper...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
64
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
65 プログラムとメタ計算の関係としての Monad について述べたところで、プログラムの変更をメタ計算として記述することを考える。
30
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
66
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
67 プログラムの変更とは関数や値が変更されることであり、変更される量には単位がある。
30
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
68 最初の変更単位をバージョン1とし、変更された後のプログラムはバージョンが1増加する。
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
69 任意の型Aに対するメタ計算Tを考えた時、プログラムの変更は式\ref{exp:meta_computation_definition}のように定義する。
6
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
70
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 \begin{equation}
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
72 T A = V_A
11
76ce5bb18092 Add Category definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
73 \label{exp:meta_computation_definition}
6
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 \end{equation}
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
75
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
76 V はプログラムの全てバージョンの集合であり、$ V_A $ とすることでAに対応する値の集合を返すものとする。
6
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
78 式\ref{exp:meta_computation_definition}のメタ計算として、全ての変更単位で変更されたプログラムを保存する計算を提案する。
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
79 このメタ計算を Delta Monad と呼ぶ。
49
ba7f0b5454ab Add description for DeltaM definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
80 なお、この Delta Monadが Monad であることの証明は \ref{chapter:proof_delta} 章で行なう
30
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
81
14
586f3ce1effe Add folding for section
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
82 % }}}
8
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
83
14
586f3ce1effe Add folding for section
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
84 % {{{ Haskell における Delta Monad の実装例
8
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
85
6
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 \section{Haskell における Delta Monad の実装例}
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
87
12
11015b94a5cd Add figures category
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
88 式\ref{exp:meta_computation_definition}のメタ計算をMonadで実現する。
6
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
89
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 実装例としてプログラミング言語 Haskell を用いる。
8
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
91
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
92 まずは全てのプログラムのバージョンを表わすデータ型 Delta を考える。
19
43d3e7b31fc0 Fix listings and page numbering
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 14
diff changeset
93 Delta の定義はリスト\ref{src:delta_constructor} とする。
8
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
94
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
95 \begin{table}[html]
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
96 \lstinputlisting[label=src:delta_constructor, caption=Haskellにおけるデータ型Deltaの定義]{src/delta_constructor.hs}
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
97 \end{table}
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
98
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
99 データ型 Delta はコンストラクタ Delta もしくは Mono によって構成される。
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
100 バージョンが1である値は Mono によって構成される。
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
101 プログラムを変更する際には、コンストラクタ Delta を用いて記述し、変更後の値と前のバージョンを持つ。
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
102 なお、a とは任意の型であり、Delta が任意の型の値に対してもデータ型を構築できることを示す。
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
103
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
104 Haskell においてメタ計算とデータ型の対応は Monad によって行なうため、 Monad という型クラスが用意されている。
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
105 型クラスとは特定の性質を持つ型をまとめるための制約である。
32
fc864841ab90 Update description of definition delta monad in haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
106 ある型が型クラスに属するためには制約として型クラスによって指定された関数を定義する。
fc864841ab90 Update description of definition delta monad in haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
107 なお、型aが型クラスCに属することを「型aは型クラスCのインスタンスである」と言う。
fc864841ab90 Update description of definition delta monad in haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
108 型クラス Monad はリスト\ref{src:monad_class}のように定義されている。
8
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
109
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
110 \begin{table}[html]
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
111 \lstinputlisting[label=src:monad_class, caption=Haskell における Monad 型クラス]
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
112 {src/monad_class.hs}
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
113 \end{table}
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
114
32
fc864841ab90 Update description of definition delta monad in haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
115
fc864841ab90 Update description of definition delta monad in haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
116 型クラス Monad に属するために要請される関数は return と \verb/>>=/ である。
34
df55c9df8aac Adjust monad class definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
117 \verb/::/ は型注釈であり、 $ term :: type $ のように記述する。
df55c9df8aac Adjust monad class definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
118 なお、関数型は \verb/ a -> b / のように引数の型と返り値の型を \verb/->/で挟んで記述する。
df55c9df8aac Adjust monad class definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
119 引数が2つ以上の関数は \verb/ a -> b -> ... -> d / のように \verb/->/を増やすことで記述する。
df55c9df8aac Adjust monad class definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
120
8
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
121 関数 return は任意の型aを受けとり、メタ計算と対応された型に対応させて返す。
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
122 \verb/>>=/ は中置関数であり、left operand と right operand を取る。
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
123 left operand にメタ計算と対応された値と、right operand にメタ計算と対応された値を返す関数を取り、メタ計算を行ないながら関数を適用する。
8
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
124
32
fc864841ab90 Update description of definition delta monad in haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
125 データ型 Delta に対応するメタ計算を Monad を用いてリスト\ref{src:delta_instance_monad}のように定義する。
fc864841ab90 Update description of definition delta monad in haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
126
fc864841ab90 Update description of definition delta monad in haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
127 \begin{table}[html]
fc864841ab90 Update description of definition delta monad in haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
128 \lstinputlisting[label=src:delta_instance_monad, caption=Haskell におけるデータ型Deltaとメタ計算の関連付け]
fc864841ab90 Update description of definition delta monad in haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
129 {src/delta_instance_monad.hs}
fc864841ab90 Update description of definition delta monad in haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
130 \end{table}
8
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
131
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
132 \begin{itemize}
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
133 \item 関数 return
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
134
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
135 通常の値をメタ計算と対応させるため、値をバージョン1の値とする。
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
136 そのためにコンストラクタ Mono を用いる。
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
137
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
138 \item 中置関数 \verb/>>=/
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
139
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
140 メタ計算を含んだ関数の適用である。
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
141 通常の関数の適用に加え、バージョンを含んだ計算も行なう。
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
142 値と関数のそれぞれにおいて同じバージョン選択し、関数を適用する。
8
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
143 もしバージョン1であった場合はコンストラクタは Mono であるため、Mono が持っている値に対して関数を適用することとなる。
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
144 もしバージョンが1で無い場合のコンストラクタは Delta であるため、先頭の値を用いて計算し、残りの値と結合することとなる。
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
145 その際、先頭の値を取り出すために headDelta 関数を、先頭以外の値を取り出すために tailDelta 関数を用いる。
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
146 \end{itemize}
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
147
49
ba7f0b5454ab Add description for DeltaM definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
148 なお、中置関数 \verb/>>=/ や headDelta関数などで用いたコンストラクタによる処理の分岐はパターンマッチと呼ばれる。
8
c4da3e667aad Add Delta definition in Haskell
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
149 Haskell ではコンストラクタごとに関数を記述することでパターンマッチを実現する。
6
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
150
14
586f3ce1effe Add folding for section
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
151 % }}}
586f3ce1effe Add folding for section
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
152
31
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
153 % {{{ Delta Monad を用いたプログラムの変更の記述例
6
3b861ecdec9b Add description meta computation
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
154
31
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
155 \section{Delta Monad を用いたプログラムの変更の記述例}
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
156 \label{section:delta_example}
9
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
157 プログラムの変更を表現するメタ計算に対応するデータ型 Delta が記述できた。
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
158
19
43d3e7b31fc0 Fix listings and page numbering
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 14
diff changeset
159 実際に Haskell で Delta を用いたプログラムの変更例をリスト\ref{src:delta_example}に示す。
9
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
160
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
161 \begin{table}[html]
50
37a832dff044 Add DeltaM example
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
162 \lstinputlisting[label=src:delta_example, caption=Deltaを用いたプログラムの例] {src/delta_example.hs}
9
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
163 \end{table}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
164
19
43d3e7b31fc0 Fix listings and page numbering
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 14
diff changeset
165 リスト\ref{src:delta_example}は1からnの間の整数に含まれる特定の数の個数を調べるプログラム numberCount である。
9
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
166
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
167 このプログラムは3つの関数からなり、2つのバージョンを含む。
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
168
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
169 \begin{itemize}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
170 \item generator
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
171
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
172 1からnの間の整数を生成する関数である。
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
173 nを渡すことにより1からnの間の整数のリストを返す。
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
174
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
175 \item numberFilter
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
176
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
177 数のリストから特定の数のみを絞り込む関数である。
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
178 バージョン1では素数の数のみを絞り込み、バージョン2では偶数の数のみを絞り込んでいる。
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
179
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
180 \item count
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
181
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
182 数の個数を数える関数である。
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
183 整数はリストで与えられるため、リストの長さが個数であるとした。
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
184 \end{itemize}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
185
10
c2dda6eeab57 Split chapter 3
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
186 これらの関数3つをMonad の \verb/>>=/ によってメタ計算を含む関数呼び出しとして実行する。
c2dda6eeab57 Split chapter 3
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
187 3つの関数を実行する関数が numberCount 関数であり、この関数がプログラム本体である。
c2dda6eeab57 Split chapter 3
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
188 numberCount を実行すると \ref{txt:delta_example_result}のような結果が得られる。
9
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
189
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
190 \begin{table}[html]
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
191 \lstinputlisting[label=txt:delta_example_result, caption=numberCountプログラムの実行結果] {src/delta_example_result.txt}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
192 \end{table}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
193
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
194 これはnに1000を与えた結果である。
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
195 バージョン1の時は素数の数を求めるため計算結果は168であり、バージョン2の時は偶数の数を求めるために計算結果は500となる。
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
196
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
197 3つの関数で構成されたプログラムに対して1つの変更を加えたプログラムを表現することができた。
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
198 つまり、Monad によってプログラムの変更をメタ計算として定義できたと言える。
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
199
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
200 Haskell において実装した Delta Monad はプログラムの変更を含めた計算もメタ計算としてHaskellで実行する。
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
201 これはプログラムの変更からどのような処理を導くかをメタ計算として Haskell で実行可能であることを意味する。
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
202 つまり、図\ref{fig:non_delta_example}のようにプログラムにおいてバージョンが変わるごとにバージョン間の関係が存在しない状態から、図\ref{fig:delta_example}のようにプログラムの変更を含めてプログラムを実行可能となったことを意味する。
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
203 メタ計算を変更することでプログラムの実行時にバージョン間の挙動の比較することも可能となる。
9
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
204
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
205 \begin{figure}[htbp]
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
206 \begin{center}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
207 \includegraphics[scale=0.8]{fig/non_delta_example.pdf}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
208 \caption{Deltaを用いない通常のプログラムの例}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
209 \label{fig:non_delta_example}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
210 \end{center}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
211 \end{figure}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
212
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
213 \begin{figure}[htbp]
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
214 \begin{center}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
215 \includegraphics[scale=0.8]{fig/delta_example.pdf}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
216 \caption{Deltaを用いたプログラムの例}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
217 \label{fig:delta_example}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
218 \end{center}
324111203070 Add example used delta
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
219 \end{figure}
14
586f3ce1effe Add folding for section
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
220
586f3ce1effe Add folding for section
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
221 % }}}
30
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
222
31
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
223 % プログラムの変更に対するメタ計算の例 {{{
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
224
30
67d79c18a276 Update description and delta definition
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
225 \section{プログラムの変更に対するメタ計算の例}
31
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
226 \label{section:delta_merit}
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
227 \ref{section:delta_example}節ではプログラムの変更に対して、変更前と変更後の挙動を保存した例を述べた。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
228 \ref{section:delta_merit}節ではプログラムの変更に対するメタ計算の例を述べる。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
229
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
230 まず最初に挙げられるものがプログラムの変更を保存するメタ計算である。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
231 これは Delta Monad として実際に定義できた。
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
232 プログラムの変更を保存した場合、以下のような計算可能となる。
31
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
233
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
234 \begin{itemize}
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
235
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
236 \item 異なるバージョンを同時に実行する
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
237
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
238 プログラムの変更列から任意のバージョン2つを取り出し、同時に実行するプログラムを構成する。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
239 プログラムを同時に実行することで以下のようなメリットがある。
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
240 なお、任意の要素どうしの組み合せは category において product として表現されるため、 product と対応があると考えている。
31
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
241
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
242 \begin{itemize}
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
243 \item 実行系とサブの実行系を実行する
31
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
244
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
245 例えば、あるバージョンでリリースしたプログラムがあるとする。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
246 変更を加え、ベータ版としてリリースしたいが動作が不安定である。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
247 そこで、リリースしたプログラムからベータ版への変更から、2つのプログラムが同時に動くようなプログラムを構築する。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
248 見掛け上は安定版として動作するが、安定版の実際の入出力を用いてベータ版をテストすることが可能となる。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
249
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
250 \item バージョン依存のプロトコル間で互換を持つようなプログラムが作成できる
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
251
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
252 異なるバージョン間でプロトコルに互換が無いプログラムを考える。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
253 バージョン間の互換を含めてメタ計算として定義し、全てのバージョンに対して互換を持つプログラムを構築する。
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
254 そうすることで、どのバージョンのプロトコルとも互換を持つような変換器を作成できる。
31
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
255
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
256 \end{itemize}
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
257
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
258 \item バージョン間の動作の比較
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
259
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
260 プログラムの各バージョンにつき、挙動を示すユニークなトレースが得られるとする。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
261 トレースの比較をすることでバージョン間の動作を比較することができる。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
262 トレースの比較により以下のようなものを検出できると考えている。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
263
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
264 \begin{itemize}
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
265 \item 過去のバージョンの挙動を破壊する時を検出する
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
266
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
267 プログラムの変更の際、トレースを変えてはいけない部分を指定する。
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
268 変更の際にトレースが保存される変更のみを受けつけるようにする。
31
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
269
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
270 \item トレースが変化していないことを確認する
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
271
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
272 プログラムの変更にはいくつかの種類がある。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
273 例えば機能拡張の変更などであればトレースは変化するのが正しい。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
274 しかしリファクタリングではプログラムが変更されてもトレースが変わらないのが望ましい。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
275 トレース全体が変わらないような変更のみを受けつけることにより、リファクタリングを支援することができる。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
276 \end{itemize}
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
277
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
278 \item Version Control System との対応
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
279
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
280 全ての変更を保存し、任意のバージョンを生成可能であるようなメタ計算を考える。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
281 そうした時、プログラムの変更を蓄積するものは git や mercurial といった Version Control System の Repository に相当すると考えられる。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
282 Delta により Repository を定義することがでるのならば、 branch や merge といった Version Control System の処理に対して形式的な定義を与えることができる。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
283 また、 category における colimit と対応があると考えている。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
284
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
285 \item 変更単位を用いた処理
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
286
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
287 変更を適用する際に、特定の処理を実行することもできる。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
288 例えばプログラムの変更単位に対してテストを行なうことで、変更に応じてテストの結果の変動が確認できる。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
289 プログラム全体に対応するテストを定義し、変更の際にテストが通る変更のみ受け付けるようにすることでテストベースの信頼性を確保できる。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
290 \end{itemize}
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
291
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
292 他にもプログラムの変更そのものを処理するプログラムを定義することもできる。
57
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
293 この機構を言語処理系に組込むことにより、言語の仕様にプログラムの変更方法も含めることができる。
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
294 例えば、プログラムの変更は許可されたオペレーション内で行なうといった制約を加えることが可能となる。
31
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
295 さらにユーザによりプログラムの変更に対するメタ計算を自由に定義できるような言語処理系を作るとする。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
296 その処理系ではこれまでに挙げた全てのメタ計算の例から使いたい機能を選んだり自分で追加することが可能となる。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
297
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
298 このように、プログラムの変更を形式化することで多くのメタ計算が扱えるようになる。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
299 さらに、メタ計算の内容によっては信頼性の向上に用いたり変更も含めた上でプログラムを作成することが可能になる。
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
300
d0d14c0a795b Add examples of meta computation for program modification
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
301 % }}}