title: Categorical Formalization for Program Modification
author: Yasutaka Higa
profile:
lang: Japanese


# 研究目的 (Categorical Formalization for Program Modification)
* プログラムの信頼性を向上させたい
* プログラムの信頼性が変化するのはプログラムを変更した時である
* プログラムを変更する際に信頼性を保ったまま変更するための手法を確立させたい
* プログラムとその変更を表すモデルとして、圏を用いる

# 研究目的 (Parallel Debugger)
* 本研究ではプログラムの変更を Monad として定義する
* Monad とは meta computation と対応付けられたデータ構造である
* Monad の性質を用いて、異なるバージョンを同時に実行するデータ構造Deltaを定義する
* 異なるバージョンの実行結果を比較することによってデバッグを支援する手法を提案する

# 近況報告
* 業務連絡 : プロシン申し込みました
* 無限の変更を表せる Delta の証明ができました
    * Category の方の Monad則

# 業務連絡 : プロシン申し込み
* プロシン申し込みました
* 事務から書類貰ってきました
    * 講座への振込依頼書
* 12/9 - 12/11 なので 12/8 - 12/11 の予定です

# Prove monad laws in Category for Delta
* とりあえずベタに書きました
    * record とか使ってない
    * Functor, Natural Transformation
* 先週話を聞いた後にいけそうなのでつっ走りました

# Delta の証明のキモ
* bind : (Delta a) -> (a -> Delta b) -> (Delta b)
* f と x のバージョン数が違うかもしれないので合わせる必要がある
* bind そのものは
    * 関数のバージョン数
    * 適用する変数のバージョン数
* が分からないけれど合わせないといけない

# Delta の証明のキモ : x = 1 , f = 1
* bind : (Delta a) -> (a -> Delta b) -> (Delta b)

```
var  = [x]
func = [f]

func(var) = [f(x)]
```

# Delta の証明のキモ : x = 2 , f = 1
* bind : (Delta a) -> (a -> Delta b) -> (Delta b)

```
var  = [x, y]
func = [f]

func(var) = [f(x), f(y)]
```

# Delta の証明のキモ : x = 1 , f = 2
* bind : (Delta a) -> (a -> Delta b) -> (Delta b)

```
var  = [x]
func = [f, g]

func(var) = [f(x), g(x)]
```

# Delta の証明のキモ : x = 2 , f = 2
* bind : (Delta a) -> (a -> Delta b) -> (Delta b)

```
var  = [x, y]
func = [f, g]

func(var) = [[f(x), g(x)],
             [f(y), g(y)]]
```

# Delta の証明のキモ : x = 3 , f = 2
* bind : (Delta a) -> (a -> Delta b) -> (Delta b)

```
var  = [x, y, z]
func = [f, g]

func(var) = [[f(x), g(x)],
             [f(y), g(y)],
             [f(z), g(z)]]
```

# Delta の証明のキモ : x = 2 , f = 3
* bind : (Delta a) -> (a -> Delta b) -> (Delta b)

```
var  = [x, y]
func = [f, g, h]

func(var) = [[f(x), g(x), h(x)],
             [f(y), g(y), h(y)]]
```

# Delta の証明のキモ : x = n , f = n
```
bind (Mono x)    f = f x
bind (Delta x d) f = Delta (headDelta (f x))
                           (bind d (tailDelta . f))
```

* 自然数回分だけ tailDelta が行なわれる
* tailDelta の回数を自然数回適用する equiv を定義したらいけました
    * 発想が出たのは展開するごとに tailDelta が増えるのを見たので

# Delta の証明 : Monad-laws
* 特に TTT に対する Monad-law
    * mu (mu TTT) == mu (fmap mu TTT)
* 先程のやつの三次元版
    * 足りない情報は bind で埋める
    * どこからなぞっても unique ってことと同義に思える

# TODO
* ポジションペーパ
    * どっちを書こうか
    * parallel debuggerだと思ってます
* (P) Monad-laws in Haskell
* (P) MonadTransform
* (C) Universal Mapping Problem
* (C) Functor with Save Limit

<!-- vim: set filetype=markdown.slide: -->