Stack Safety for Free
2015/8/8
>#WIP
想定される知識が割とある気がする
Freeモナドについて
Trampolined Styleとはなにか
pursの知識
JSにコンパイルされる正格評価言語だということ
型クラス、
諸々の標準的なモナド
昔のpursの知識
Eff は古い、とかそういうの先にStackless Scala With Free Monadsを読んでると良さそう
大きな流れ
問題提起
Freeについて見ていく
普通のFreeモナド
Freeモナド変換子
Freeのstack unsafe問題について
Scalaとかにも言及する
stack safeなFreeを作ろうぜ
普通のFreeのstack safe版
Freeモナド変換子のStack safe版
Abstract
この論文内の「Safe」は「Stack Over Flowを起こさないことが保証されている」という意味
Introduction
Host言語がJSなので、その上で関数型プログラミング的な抽象化をしてもパフォーマンスが落ちてしまうことがある
特に再帰におけるStack Over Flowなど
そこで、安全なFreeモナドを実装する
pursでFreeモナドをナイーブに実装するとこんな感じになる
purs(hs)
newtype Free f a = Free (Either a (f (Free f a)))
instance Functor f => Functor (Free f) where
map g fr = g <$> fr
instance Functor f => Apply (Free f) where
apply = apply
instance Functor f => Bind (Free f) where
bind = bind
instance Functor f => Applicative (Free f) where
pure = pure
instance Functor f => Monad (Free f)
resume :: ∀ f a. Free f a -> Either a (f (Free f a))
resume (Free a) = a
liftFree :: ∀ f a. (Functor f) => f a -> Free f a
liftFree = Free <<< Right <<< map pure
runFree :: ∀ f m a.
(Monad m) =>
(f (Free f a) -> m (Free f a)) -> Free f a ->
m a
runFree phi = either pure ((_ >>= runFree phi) <<< phi) <<< resume実装が古くてところどころ書き換えている
Freeのmonad実装などは省略されているが、自明な実装をした
derivingができないので自明でも書くしかないっぽい
Freeモナドはモナド変換子に一般化できる
The free monad can be generalized to a monad transformer, where a monadmis used to track effects at each step of the computation.
FreeモナドをFreeTに一般化する方法は困難
Current attemptsto generalize stack-safe implementations of the free monad to the free monad transformer FreeT have met with difficulty.
変換可能なMonadに制限を課すことで、Freeモナドと組み合わすことが出来るようにする
In this paper, we’ll construct a stack-safe implementation of the free monad and its monad transformer, by imposing a restriction on the class of monads which can be transformed.
Computing with Free Monads
Free f aの計算は、completeかsuspension
Pure と Join のことを言っているsuspensionで利用可能な操作は
Functor である f で記述されるCounter DSL的なやつをFreeを使って作ってみる
purs(hs)data CounterF a
= Increment a
| Read (Int -> a)
| Reset a
instance functorCounterF :: Functor CounterF where
map f (Increment a) = Increment (f a)
map f (Read k) = Read (f <<< k)
map f (Reset a) = Reset (f a)3つの命令を持つ
Incrementは1つinc
Readはcurrent valueを返す
Resetはcurrent valueを0にする
CounterF a をFreeに埋め込むと、 a は継続を表すことになるpurs(hs)type Counter = Free CounterF
increment :: Counter Unit
increment = liftFree (Increment unit)
read :: Counter Int
read = liftFree (Read identity)
reset :: Counter Unit
reset = liftFree (Reset unit)
readAndReset :: Counter Int
readAndReset = do
current <- read
reset
pure currentFreeと組み合わすことで、
Counter はMonadになったこのmonadがどういう計算を実行するかは、
Counter ~> Hoge となるような、Monad Hogeを選択して、これに合うように自然変換を作ればいいこの
Hoge のことを以下で「base monad」とか「target monad m」などと呼んでるその一例として
Hoge に Eff を与えたものがp.4の上に載っているコード他の例としては、Affと組み合わせてremote server上の値を非同期で更新するとか、Effでlogを吐くとか
> This is the powerof working with free monads we have completely separated the interpretation of our computations from the syntax that describes them.
あーーー、これが「Freeモナドの嬉しさはDSLだよ」とかいうやつの真意か
上の例で言えば、
increment , read , reset , readAndReset とかが「構文」で、 runCounter とかが「解釈」構文と解釈が完全に分離している、分離できる
Free Monad Transformers
purs(hs)newtype FreeT f m a = FreeT (m (Either a (f (FreeT f m a))))
instance (Functor f, Monad m) => Functor (FreeT f m) where
map f = FreeT <<< map (bimap f (map (map f))) <<< resumeT
instance (Functor f, Monad m) => Apply (FreeT f m) where
apply = ap
instance (Functor f, Monad m) => Bind (FreeT f m) where
bind (FreeT a) f = FreeT (a >>= go)
where
go (Left a) = resumeT (f a)
go (Right fs) = pure (Right (map (_ >>= f) fs))
instance (Functor f, Monad m) => Applicative (FreeT f m) where
pure = FreeT <<< pure <<< Left
instance (Functor f, Monad m) => Monad (FreeT f m)
instance (Functor f) => MonadTrans (FreeT f) where
lift = FreeT <<< map Left
resumeT :: ∀ f m a. FreeT f m a -> m (Either a (f (FreeT f m a)))
resumeT (FreeT a) = a
liftFreeT :: ∀ f m a. Functor f => Monad m => f a -> FreeT f m a
liftFreeT = FreeT <<< pure <<< Right <<< map pure
runFreeT :: ∀ f m a.
(Monad m) =>
(f (FreeT f m a) -> m (FreeT f m a)) -> FreeT f m a ->
m a
runFreeT phi = either pure ((_ >>= runFreeT phi) <<< phi) <=< resumeTFreeTを使うと計算の各stepでbase monadとなる
m からのEffectをインターりーぷできるおー、合間にlogを挟んだり出来る
purs(hs)type CounterT = FreeT CounterF
incrementT :: ∀ m. (Monad m) => CounterT m Unit
incrementT = liftFreeT (Increment unit)
readT :: ∀ m. (Monad m) => CounterT m Int
readT = liftFreeT (Read identity)
resetT :: ∀ m. (Monad m) => CounterT m Unit
resetT = liftFreeT (Reset unit)Deffering Monadic Binds
runFreeは末尾再帰ではないため、大規模な計算をしようとするとStack Over Flowする
この辺の問題は、ScalaのStackless Scala With Free Monadsが解決策として知られている
><Bjarnason> describes how to defer monadic binds in the free monad, by capturing binds as a data structure.
ちょっとよくわからんのでの解釈が正しいかわからんが書いてみる
Free型はMonadをdata構造として表現したものなので、Monadをデータ構造とすることができる
そのデータ構造をcaputureすることで、bindを延期できる
だからなに #??
Stack Over Flowを起こさないってことか？
末尾再帰関数を使用して、Freeを解釈し、延期したbindの構造を折りたたむ
そうすることで、深い再帰をサポートするFree monadの実装ができる
ただし、この方法には制限がある
base monadとして使用できるmは、stack safeである必要がある
「任意のモナドをtargetに取れる」と言っている割に制限があるということか？
次の節を読んだ感じ
Stackless Scala With Free Monadsを読んでないのであまりわからんな
pursのFree型の定義が変な感じだったのは、この辺が理由7日
これ、Scalaの構文勉強しないとだめかもな #??
だが、まあ解説があることを信じて読み進めてみる
purs(hs)data GosubF f a b = GosubF (Unit -> Free f b) (b -> Free f a)
data Free f a
= Free (Either a (f (Free f a)))
| Gosub (Exists (GosubF f a))> Gosub captures the arguments to a monadic bind, existentially hiding there turn type b of the intermediate computation.Tail Recursiveモナドを理解する必要がある
ていうか
Exists 知らんなTail Recursive Monads
Scalaのやり方では制限があるので、なんとかしよう、という流れ
target monad m に「Tail Recusiveモナドである」という制限を加える末尾呼び出しの除去に関する話
これはちゃんと末尾呼び出しの除去される
purs(hs)pow :: Int -> Int -> Int
pow n p = go (Tuple 1 p)
where
go (Tuple acc 0) = acc
go (Tuple acc p) = go (Tuple (acc * n) (p - 1))しかし、Monadを使った再帰をすると最適化されない
そのため、
powWriter に大きな値を与えるとStack Over Flowするpurs(hs)powWriter :: Int -> Int -> Writer Product Unit
powWriter n = go
where
go 0 = pure unit
go m = do
tell n
go $ m -1再帰だけでなく、
forever のような無限に繰り返す関数も機能しなくなるこれか
末尾再帰関数を一般化する
末尾再帰は、「終了」もしくは「自分自身の呼び出し」にパターン化できるのでこれを一般化した関数を定義できる
purs(hs)tailRec :: ∀ a b. (a -> Either a b) -> a -> b
tailRec f a = go (f a)
where
go (Left a) = go (f a)
go (Right b) = bへー、Left側を「自分自身の呼び出し」にするのか。たしかに
これはTrampolined Styleとよく似ている
Left側は、「値」ではなく、「関数」を返している
と、いうわけでもないが、「似てる」言われれば似てる気もする
というかは、手続き言語のTrampolineしか知らんので、関数型ならこんな感じになるのかもしれない
tailRecを使って、powを書き直すr
purs(hs)pow :: Int -> Int -> Int
pow n p = tailRec go (Tuple 1 p)
where
go :: Tuple Int Int -> Either (Tuple Int Int) Int
go (Tuple acc 0) = Right acc
go (Tuple acc p) = Left $ Tuple (acc * n) (p - 1)元の
pow との違いは、 tailRec を使っている点 go の返り値がEitherでwrapされている点 tailRec はstackを積まないので、このpowもstackを積まないことがわかるこれによって、コンパイラに依る末尾呼び出しの除去に頼らなくて良くなる
これを一般化したMonadRec型クラスがある
purs(hs)class Monad m <= MonadRec m where
tailRecM :: forall a b. (a -> m (Either a b)) -> a -> m bもとの
tailRec との違いは、 Either と返り値が、 m でwrapされている点この論文内では、
Either を使っているが、実際の実装は Step という型を使ってる構造としてはほぼ同じ
data Step a b = Loop a | Done b MonadRecは任意のMonadに対して定義できることがわかる
ただし、MonadRec則なるものが存在する
>A valid implementation ofMonadRecmust guarantee that the stack usage oftailRecM fis at most a constant multiple of the stack usage off itself.
この辺は、型システムの扱えるレベルを超えているため、人間が気にする必要がある
forever はMonadRecのMonadに安全さ実装を与えるMonadRecはいろいろinstanceが用意されているので便利
StateT, WriterT, ExcpeTなどにMonadRecは使われている
使われているとは言ってないか
組み合わせたら色々出来るよ、と言っている
Interpreting Free Monads Safely
resume を末尾再帰として実装する resume はFree monadの最初のstepを実行する必要に応じて遅延もなどのbindをunpackingする
これはStackless Scala With Free Monadsに倣っている
復習すると
purs(hs)-- ただのFree型に対する実装
resume :: ∀ f a. Free f a -> Either a (f (Free f a))
resume (Free a) = a
-- FreeTに対する実装
resumeT :: ∀ f m a. FreeT f m a -> m (Either a (f (FreeT f m a)))
resumeT (FreeT a) = a
-- 末尾再帰にしたstack safeな実装
resume
:: forall f a
. Functor f
=> Free f a
-> Either (f (Free f a)) a
resume = ..purs(hs)tailRecM' f a = f a >>= go
where
go (Left a) = f a >>= go
go (Right b) = pure b
resume
:: forall f a
. Functor f
=> Free f a
-> Either (f (Free f a)) a
runFree :: ∀ f m a.
Functor f => Monad m =>
(f (Free f a) -> m (Free f a)) -> Free f a -> m a
runFree phi = tailRecM \m ->
case resume m of
Left fs -> map Left (phi fs)
Right a -> pure $ Right a>Here, the MonadRec instance is used to define a tail-recursive function whichunrolls the data structure of monadic binds, one step at a time.
MonadRecインスタンスは、monadic bindのデータ構造を一度に1ステップずつ展開する末尾再帰関数を定義するために使用される
Freeの層を一度に1stepずつ展開する
これによって、有効なtarget monadの範囲を拡大できた
Scalaのやつの前提をあまり理解してないので、この辺、曖昧な理解になっている
Stack-Safe Free Monad Transformers
Stack SafeなFreeを作れたので、次はそれのモナド変換子を作ろう
purs(hs)data GosubF f m a b = GosubF (Unit -> FreeT f m a) (a -> FreeT f m b)
data FreeT f m a
= FreeT (Unit -> m (Either a (f (FreeT f m a))))
| Gosub (Exists (GosubF f m a))FunctorやMonadのinstanceは、FreeからFreeTまで上手く一般化されている
問題はtarget monad mでFreeTの計算をどう実行するか
R ́unar ́Oli Bjarnasonのresumeは、tailrecMを使用している
prus(hs)resume ::
∀ f m a.Functor f => MonadRec m =>
FreeT f m a ->m (Either a (f (FreeT f m a)))
resume = tailRecM go
where
go :: FreeT f m a -> m (Either (FreeT f m a) (Either a (f (FreeT f m a))))
go (FreeT f) = map Right (f unit)
go (Gosub e) = runExists (\(GosubF m f) ->
case m unit of
FreeT m -> do
e <- m unit
case e of
Left a -> pure (Left (f a))
Right fc -> pure (Right (Right (map (\h -> h >>= f) fc)))
Gosub e1 -> runExists (\(GosubF m1 f1) ->
pure (Left (bind (m1 unit) (\z -> f1 z >>= f)))) e1) e
runFreeT :: ∀ f m a.
Functor f => MonadRec m =>
(f (FreeT f m a) -> m (FreeT f m a)) ->FreeT f m a ->m a
runFreeT interp = tailRecM (go <=< resume)
where
go :: Either a (f (FreeT f m a)) -> m (Either (FreeT f m a) a)
go (Left a) = pure (Right a)
go (Right fc) = do
c <- interp fc
pure (Left c)MonadRecのinstanceであるmonadならstack safeになった
Stack Safety for Free
purs(hs)newtype Identity a = Identity a
runIdentity :: forall a. Identity a -> a
runIdentity (Identity a) = a
type SafeT = FreeT Identity
runSafeT :: forall m a. (MonadRec m) => SafeT m a -> m a
runSafeT = runFreeT (pure <<< runIdentity)Identityに対してFreeTを使って、Freeを得ている
mがMonadRecなら、
runSafeTが解釈を与えてくれる
stack over flowを心配せずに、入れ子になっているmonadを使用できる
入れ子は、モナド変換子の文脈での入れ子
上の
resume がエラーになるので外部ライブラリも使用して動くやつにしたFreeTは提供されている
purs(hs)import Control.Monad.Free.Trans (FreeT, runFreeT)
import Control.Monad.Rec.Class (class MonadRec)
import Data.Identity (Identity(..))
import Effect (Effect)
import Effect.Class (liftEffect)
import Effect.Class.Console (log)
runIdentity :: forall a. Identity a -> a
runIdentity (Identity a) = a
type SafeT = FreeT Identity
runSafeT :: forall m a. (MonadRec m) => SafeT m a -> m a
runSafeT = runFreeT (pure <<< runIdentity)
main :: Effect Unit
main = go 100000
where
go :: Int -> Effect Unit
go n | n <= 0 = pure unit
go n = do
log $ show n
go (n - 2)
go (n - 1)
main' :: Effect Unit
main' = runSafeT $ go 100000
where
go :: Int -> SafeT Effect Unit
go n | n <= 0 = pure unit
go n = do
liftEffect (log $ show n)
go (n - 2)
go (n - 1)Application: Coroutines
3つのコルーチンの実装例の紹介 #??
Free monad transformers can be used to construct models ofcoroutines, by usingthe base functor to specify the operations which can take place when a coroutinesuspends.
base functorが、「コルーチンの中断時に実行できる操作」を表す
これ、今回の例だから、↑こう言えるのか、Freeモナド自体の理解として、こう解釈しちゃっていいのか #??
FreeTを使ってcoroutineのModelを構築する
Functor として Emit 型を使うサスペンションでの単一の操作をサポートするベースファンクタEmit
purs(hs)data Emit o a = Emit o a
instance Functor (Emit o) where
map f (Emit o a) = Emit o (f a)値のみを生成するProducer型
Freeで囲んでいるのでMonadになる
purs(hs)type Producer o = FreeT (Emit o)emitは、単一の出力値を出力
purs(hs)emit :: forall o m. (Monad m) => o -> FreeT (Emit o) m Unit
emit o = liftFreeT (Emit o unit)purs(hs)producer :: ∀ m. Monad m => MonadEffect m => Producer String m Unit
producer = forever do
liftEffect $ log "Emitting a value..."
emit "Hello World"どういう挙動になるのか #??
Stackless Scala With Free Monadsでも紹介されている例
await の定義、誤植してるなpurs(hs)data Await i a = Await (i -> a)
instance Functor (Await i) where
map f (Await k) = Await (f <<< k)
type Consumer i = FreeT (Await i)
await :: ∀ i m. Monad m => Consumer i m i
await = liftFreeT (Await identity)
consumer :: ∀ m. Monad m => MonadEffect m => FreeT (Await String) m Unit
consumer = forever do
s <- await
liftEffect $ log spurescript-coroutines
ちょっと飛ばした
Application: List Monad Transformer
ListTを使うことで、副作用のある非決定的計算を表すことが出来る
これはFree関係ない一般的なListTの話
しかし、stack safeなListTを構築する方法は自明でない
Freeと組み合わせてListTを定義すればいいじゃない
purs(hs)data ListF a r t = Nil r | Cons a t
newtype ListT m a r = ListT (m (ListF a r (ListT m a r))) ListT m a r と前述の FreeT (Emit a) m r は同型Procedureを使ってListTを再定義
purs(hs)newtype ListT m a = ListT (Producer a m Unit)ちょっと飛ばした
Application: Lifting Control Operators
COntrole Operatorというのは、
mapM_ 、 foldM , replicateM_ , iterateM などのこと