Haskellの遅延評価についてメモ
以前から考えていたことを吐き出したのでメモしておく。
あとで検証してまとめたい。
実用上知っておくべき部分はもっと少なくていいはずだし、そちらも出来るならまとめたい。
宣言的とは、宣言とは
「宣言的」というあやふやな言葉にもう少しまともな定義はつけられないかという試み。
宣言とはInvariantであるとして、対象のシステムを明示した方がいいのでは、という話。
参考link:
函数型なんたらの集い2014でモナドについて話してきた
最近私的にモナドが非常に熱いのでそれについて話してきました。
しかし資料としては要改善点が多いですね...
図入れるとか具体的なコード入れるとか色々出来たのですけど。
例
具体例をスライドに入れられなかったため、trivialな例を示す。
おおまかな雰囲気は感じられると思う。
明記してないけど、純粋関数は任意のモナド内でモナドとは関係なく使えます。
-- Derivingに必要 {-# LANGUAGE GeneralizedNewtypeDeriving #-} import Control.Applicative (Applicative) import Control.Monad.IO.Class (liftIO, MonadIO) import Control.Concurrent (threadDelay) -- DSLとなる型 (IO a のnewtype) newtype Hello a = Hello { unHello :: IO a } deriving (Functor, Applicative, Monad, MonadIO) -- DSLインターフェース(DSL定義) class Monad m => MonadHello m where getName :: m String echo :: String -> m () prompt :: m () wait :: m () -- HelloのDSL化 instance MonadHello Hello where getName = liftIO getLine echo = liftIO . putStrLn prompt = liftIO $ putStr "Enter your name: " wait = liftIO $ threadDelay 400000 -- HelloでSPECIALIZE {-# SPECIALIZE getName :: Hello String #-} {-# SPECIALIZE echo :: String -> Hello () #-} {-# SPECIALIZE prompt :: Hello () #-} {-# SPECIALIZE wait :: Hello () #-} -- run関数 (Hello DSLを実行し、IO上の効果とする) runHello :: Hello a -> IO a runHello = unHello -------------------------------------------------------------------------------- -- DSLを用いたロジック greet :: MonadHello m => m () greet = do echo "What's your name?" -- prompt表示 prompt name <- getName -- ifやcaseは問題なく使える case name of "" -> outputAndGreetAgain "Sorry, I can't hear you." "ruicc" -> outputAndGreetAgain "Hi, ruicc!" "quit" -> -- 実行終了 echo $ "Good bye!!" _ -> outputAndGreetAgain $ "Hello, " ++ name ++ "!" {-# SPECIALIZE greet :: Hello () #-} outputAndGreetAgain :: MonadHello m => String -> m () outputAndGreetAgain str = do -- 表示 echo str -- 待つ wait -- 再帰 greet {-# SPECIALIZE outputAndGreetAgain :: String -> Hello () #-} -------------------------------------------------------------------------------- main :: IO () main = do putStrLn "This is a DSL sample." putStrLn "---------------------" -- DSLを実行 (DSLの多相型(MonadHello m)をHelloに固定する) runHello $ greet
GHCの末尾再帰最適化をCore上で確認してみる
まず簡単に再帰関数(factorialとした)を、
で記述した。
fac1 0 = 1 fac1 n = n * fac1 (n-1) fac2 n = fac' 1 n fac' acc 0 = acc fac' acc n = fac' (acc*n) (n - 1) main = do print $ fac1 35 print $ fac2 35
まあこれはいいだろう。
そうしてSTGに渡す直前のCoreを見てみる(-ddump-prep)
ghc -O1 -ddump-prep -ddump-simpl-stats main.hs > dump1
OK.そうすると以下の用な関数が見える。main_fac1はfac1に、main_fac'はfac'にそれぞれ対応している。
... snip ...
Rec {
Main.main_fac1 [Occ=LoopBreaker]
:: GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer
[GblId, Arity=1, Str=DmdType <S,U>, Unf=OtherCon []]
Main.main_fac1 =
\ (ds_s3Xx :: GHC.Integer.Type.Integer) ->
case GHC.Integer.Type.eqInteger# ds_s3Xx lvl_r3Xw
of wild_s3Xy { __DEFAULT ->
case GHC.Prim.tagToEnum# @ GHC.Types.Bool wild_s3Xy
of _ [Occ=Dead] {
GHC.Types.False ->
case GHC.Integer.Type.minusInteger ds_s3Xx Main.main5
of sat_s3XA { __DEFAULT ->
case Main.main_fac1 sat_s3XA of sat_s3XB { __DEFAULT ->
GHC.Integer.Type.timesInteger ds_s3Xx sat_s3XB
}
};
GHC.Types.True -> Main.main5
}
}
end Rec }
Rec {
Main.main_fac' [Occ=LoopBreaker]
:: GHC.Integer.Type.Integer
-> GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer
[GblId, Arity=2, Str=DmdType <S,1*U><S,U>, Unf=OtherCon []]
Main.main_fac' =
\ (acc_s3XC [Occ=Once*] :: GHC.Integer.Type.Integer)
(ds_s3XD :: GHC.Integer.Type.Integer) ->
case GHC.Integer.Type.eqInteger# ds_s3XD lvl_r3Xw
of wild_s3XE { __DEFAULT ->
case GHC.Prim.tagToEnum# @ GHC.Types.Bool wild_s3XE
of _ [Occ=Dead] {
GHC.Types.False ->
case GHC.Integer.Type.minusInteger ds_s3XD Main.main5
of sat_s3XH { __DEFAULT ->
case GHC.Integer.Type.timesInteger acc_s3XC ds_s3XD
of sat_s3XG { __DEFAULT ->
Main.main_fac' sat_s3XG sat_s3XH
}
};
GHC.Types.True -> acc_s3XC
}
}
end Rec }
... snip ...さらにそれぞれの再帰部のみを抜粋する。
まずはfac1:
case Main.main_fac1 sat_s3XA of sat_s3XB { __DEFAULT ->
GHC.Integer.Type.timesInteger ds_s3Xx sat_s3XB
}次にfac':
case GHC.Integer.Type.timesInteger acc_s3XC ds_s3XD
of sat_s3XG { __DEFAULT ->
Main.main_fac' sat_s3XG sat_s3XH
}お分かりだろうか。分からんよね。
以下に日本語でGHCの内部についてまとまっている素敵文章がある。
Core言語の操作的解釈を抜粋する。caseと関数適用についてだ。
- case式はネストした評価に対応する。「case e of _ {...}」を実行する際は、戻りアドレスをスタックにプッシュした上でeの評価を開始する。評価が終わって、プッシュしておいたアドレスに制御が戻ると、戻り値を調べて分岐する。eが単純なプリミティブ演算の場合は、呼び出しを経ずにインラインで直接それを実行する。
- 関数適用はジャンプ(末尾呼び出し)に対応する。「f v1 v2 ...」を実行するには、単にfのentry codeに飛ぶ。このとき適当な呼び出し規約に従って引数とf自身を渡す。
caseの評価はスタックを消費するらしい。関数適用は単なるジャンプらしい。
それをふまえ、もう一度再帰部を見てみる。
fac1:
case Main.main_fac1 sat_s3XA of sat_s3XB { __DEFAULT ->
GHC.Integer.Type.timesInteger ds_s3Xx sat_s3XB
}case式の内部でmain_fac1を再帰呼び出ししていることが分かる。つまりこいつはスタックを消費する。
次にfac':
case GHC.Integer.Type.timesInteger acc_s3XC ds_s3XD
of sat_s3XG { __DEFAULT ->
Main.main_fac' sat_s3XG sat_s3XH
}最後に関数適用がされているだけ。つまりこいつはスタックを消費しない。単なるジャンプだ。
ということで末尾呼び出しがスタックを消費しない、単なるジャンプになっていることをCore上で確認する方法を確認した。
注意点としては、-ddump-prepではなく、-ddump-simplを用いて吐いたCoreを確認しても、この再帰部の構造は確認出来なかったことだ。
あとCmmは現状読めなかった。STGからCmmはstraight forwardだと書いてあったため、確認してみたが確かにまあ単純な構造になってはいそうだった、慣れれば読めるかもしれない。それならSTG読むけど。
OverloadedRecordFields is row polymorphism
This is not explanation but raw log.
I hope the world needs no more subtyping, and new languages have type class and row polymorphism:)
yesodとcabal sandbox
2015-07-03追記: 現在yesodを使いたい場合は、stackを導入するのが適切だと思います。
https://github.com/commercialhaskell/stack
cabal-install-1.18からsandbox機能が付き便利になったわけだが、いまいちyesodでsandbox機能をスマートに使う方法が見つからなかったのでメモ(というエントリを書いてからその方法が見つかると言うね。まあいいのだけど)。
なおGHC7.6.3, yesod-platform-1.2.7.1を前提としている。
どうでもいいがyesod-platform-1.2.6はyesod-bin-1.2.6で生成したファイル群で使えない悲しさがあった。そこバージョン合わせている訳じゃないのか。
yesod-platfromとは複雑な依存関係を持つyesodにおいてcabal-hellを回避するため、関連する全てのライブラリのバージョンを固定したパッケージである。
以下を見れば分かるが、全てのライブラリのバージョンが(==)で指定されている。
Snoymanは特別な理由がない限り、常にyesod-platformを使う事を薦めている。
ポイントは以下の三つだろうか。
- cabal sandbox initを初めに実行すること、
- yesod-platform yesod-binはcabal installで同時に入れること、
- yesod init --bareすること
cabal installの-jオプションは各自マシンのコア数指定してください。
$ mkdir yesod-test $ cd yesod-test $ cabal sandbox init $ cabal install yesod-platform yesod-bin --max-backjumps=-1 --reorder-goals -j2 $ .cabal-sandbox/bin/yesod init --bare $ cabal install -j2 $ yesod devel
とこのエントリを書いた訳だが、yesod-binで生成した後のコマンドが以前と何やら変わっている。
That's it! I'm creating your files now...
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
___
{-) |\
[m,].-"-. /
[__][__] \(/\__/\)/
[__][__][__][__]~~~~ | |
[__][__][__][__] / |
[__][__][__][__][__]| /| |
[__][__][__][__][]| || | ~~~~
ejm [__][__][__][__][__]__,__, \__/
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
The foundation for your web application has been built.
There are a lot of resources to help you use Yesod.
Start with the book: http://www.yesodweb.com/book
Take part in the community: http://yesodweb.com/page/community
Start your project:
cd yesod-test && cabal sandbox init && cabal install --enable-tests . yesod-platform yesod-bin --max-backjumps=-1 --reorder-goals && yesod devel
以前cabal-devを使ったコマンドが此処に書いてあった訳だけど、cabal sandboxに変わっている。
ということでこの最後の行のコマンドをそのまま実行したら今は問題なく動かせるかもしれない。ただこのコマンドはyesod-binでインストールしたyesodのinit後に表示されるのでもっと早く教えて上げるべきじゃないかなあと思う訳だ。
