Extensible Effectsについての論文

2013/9/23

著者

大まかな流れ

Abstract

モナド変換子より効率よく柔軟なExtensible EffectというLibraryを設計し、実装した

1 Introduction

関数型言語にMonadが導入された当初はモナド同士の合成の仕方が自明ではなかったが、モナド変換子の登場によりこの辺の問題について調査されるようになった

しかし、モナド変換子にはパフォーマンスや柔軟性の観点でいくつかの課題がある

liftを書くのがめんどい

モナドスタックを積むほどパフォーマンスが悪くなる

モナド変換子の代替としてEDLSがあるが、これにも課題がある

Effectがカプセル化されてない、Effectが型として表現されていないなど

Extensible Effectは、モナド変換子とEDLSの課題を両方とも改善する

2 A Tour of the Extensible Effects Framework

具体例を用いたExtensible Effectの簡単な概説

Eff 型や Member などのシグネチャの意味

値レベルではmtlとほぼ同じであることの解説など

3 The Extensible Effects Framework

4 Simulating the Full MTL

mtlをsimulateできることを確認

5 Beyond the MTL

mtlではできないことを例を用いて解説

Ext Effの方がmtlより一般的なので。

6 Related Work

7 Conclusions

面白そうな関連論文

参考

論文読みの補助資料としてめっちゃ助かった

前提とされる知識

モナド変換子

Freeモナド

Typeable型クラス

Abstract

Ext Effを使った実装は、モナド変換子よりも修正が容易

モナド変換子は不可能なこともできる

何 #??

Ext Effは単一のMonadである

clientとhandlerの間のコルーチンのような通信をする

型も良い感じ

Libraryは軽量である

例外追跡もできる

1 Introduction

関数型プログラミングにMonadが導入された初期は、Monadの合成の仕方はあまりわかっていなかったが、An Abstract View of Programming Languagesの考えに基づいて、様々なMonadの合成方法が調査されてきた

その一つがモナド変換子

問題点がいろいろある

liftを書くのがめんどい

層を重ねるごとにオーバーヘッドがある

一部のモナドを使いたいときも全階層のモナドが実行されてしまうからか

モナドスタックは静的に決定されるので、動的に変更できない

IOを頻繁に使うだけの関数でも、毎度 liftIO を嵩まないといけないということ？

Effectをインターリーブする必要がある

1つのEffectを、もう1つのEffectのスタックにしても目的のセマンティクスが提供されない

これが最も重要らしいが、どういう状況のことを言っているのかわからない #??

5章で具体例ありで解説されるらしい

モナド変換子の代替としてEDLSがある

Effectをinteractionとしてモデル化する

意味がわからん

Effectは、requestとauthorityに送信する

Effectの例としては、可変変数の更新、例外のthrow, fileの書き込みなど

requestには

実行するactionが記されている

requestの送り元(requester)を再開する継続が含まれている

actionの内容を解釈し、requesterに変わって実行し、

requesterを続行して結果を渡す、か、続行の中断をする

hsのIOの実行が、compilerに任されているのと似ている(?)

これには3つの問題がある

globalな外部機関を拡張するのが難しい

Effectがカプセル化されていない

Computational Effectが型に反映されていない

Ext Effは、Freeモナドなどを使ってこれらの問題を解決する

1ページ下の黒丸の箇所がよくわからん #??

Effectを型でちゃんと表現する

Open Unionというものを使う

以下のようなことを行った

mtlと似た構文のExt Effの開発

任意の順序でMonadを組み合わせたり、インターリーブが可能

Libraryなので既存のHaskellプログラムへ導入可能

微妙なバグを引き起こすモナド変換子の表現力の分析

open union typeの実装

Ext Effは、モナド変換子と、EDLSの両方の改善を行っていることになる

2 A Tour of the Extensible Effects Framework

小さな例を使用してinterfaceの紹介する

extensible effects frameworkのtour

interfaceをfigre 1に示す

構文的にはmtlに似ている

全ての計算はEffモナド Eff r で表現されている

Effの型シグネチャの理解に書いた

todos

上記メモの??の部分の解決

3 The Extensible Effects Framework

semanticsの解説

4 Simulating the Full MTL

mtlをsimulateできることを確認

5 Beyond the MTL

mtlではできないことを例を用いて解説

6 Related Work

7 Conclusions