関数のメモ化
ブログに書いてみるとよく分からなくなってきました 🙃
Haskell-jp で回答をもらいました。
@lotz84_ さんの記事や GHC のプロファイルに出てくる CAF がよく分かってなかったのをまとめる。
fact
のメモ化
lotz さんの記事の階乗 fact
関数を題材にする。
fact :: Int -> Integer fact 0 = 1 fact n = fromIntegral n * fact (n-1)
lotz さんの記事よれば、次の実装だとメモ化されるとのこと。
-- | 関数をメモ化する関数 memoize :: (Int -> a) -> Int -> a memoize f = (map f [0..] !!) fact :: Int -> Integer fact = memoize fact' where fact' 0 = 1 fact' n = fromIntegral n * fact' (n-1)
な、なんで……
1つめを fact1
、2つめを fact2
として GHCi で確かめてみる。
> :set +s > fact1 50000 `seq` pure () (2.44 secs, 2,605,979,968 bytes) > fact1 50000 `seq` pure () (2.41 secs, 2,605,979,968 bytes) > fact2 50000 `seq` pure () (2.50 secs, 2,613,580,040 bytes) > fact2 50000 `seq` pure () (0.00 secs, 88,432 bytes)
確かに fact2
の2回めの評価はすぐに終わっている。
簡単のために fact2
を次のように書き換える。
fact3 :: Int -> Integer fact3 = (map fact' [0..] !!) where fact' 0 = 1 fact' n = fromIntegral n * fact' (n-1)
> fact3 50000 `seq` pure () (2.47 secs, 2,611,180,024 bytes) > fact3 50000 `seq` pure () (0.00 secs, 88,432 bytes)
同じようにメモ化されている。
では次のように書き換えると?ポイントフリー化されていたのを引数を明示するようにした。
fact4 :: Int -> Integer fact4 x = map fact' [0..] !! x where fact' 0 = 1 fact' n = fromIntegral n * fact' (n-1)
> fact4 50000 `seq` pure () (2.58 secs, 2,619,180,432 bytes) > fact4 50000 `seq` pure () (2.59 secs, 2,619,180,432 bytes)
メモ化されない。
もう1つ、ラムダ式で定義すると?
fact5 :: Int -> Integer fact5 = \x -> map fact' [0..] !! x where fact' 0 = 1 fact' n = fromIntegral n * fact' (n-1)
> fact5 50000 `seq` pure () (2.57 secs, 2,619,180,432 bytes) > fact5 50000 `seq` pure () (2.52 secs, 2,619,180,432 bytes)
メモ化されない。
何か特別な形である必要があるみたい。
Constant Applicative Form・Super Combinator
Haskell High Performance Programming によると、その特別な形は Constant Applicative Form(定作用形)というらしい。プロファイルを取ると Cost Centre に CAF と書かれてあるやつ。
とりあえず、項がラムダ式であるとダメだそうなので fact5
は CAF ではない。
項がスーパーコンビネーターであるとは、項が定数もしくは、項がコンビネーターであり全ての部分項がスーパーコンビネーターであるものである。
これは次の定義と同値だそう。
任意の
\x1 x2 … xn -> E
(E
はラムダ式でない。。)の形の式で次の場合に限りそれはスーパーコンビネーターである。E
における自由変数はx1
,x2
, …xn
のみで、かつE
に出現するラムダ式は全てスーパーコンビネーターである。
fact3
が CAF であるかを確認する。
fact3 :: Int -> Integer fact3 = (map fact' [0..] !!) where fact' 0 = 1 fact' n = fromIntegral n * fact' (n-1)
map fact' [0..] !!
は定数でないため部分式が全てスーパーコンビネーターであればよい。部分項である
map
は、あ、あれ?定数でないしスーパーコンビネーターでもなくただの変数では……?2つめの定義においてもx1
,x2
, …xn
以外の自由変数だし……
…………
……
…
いかがでしたか?関数がメモ化関数になるためには定義が CAF でないといけないようです 😎
なんで fact3
が CAF なのか教えてください 🙏
Haskell-jp で回答をもらいました。
(Markdown モードで引用の中でコードブロック書くのどうやるんだ……)
@mizunashi-mana
スーパーコンビネータは,一般の文脈では確かにコンビネータで部分項がスーパーコンビネータであるものを指しますが, CAF の文脈では,
- ラムダ式でない
- ローカル関数が全てグローバルに出しても問題ない定義になっている
だと思うのが良いと思います.厳密には,
https://gitlab.haskell.org/ghc/ghc/wikis/commentary/rts/storage/gc/CAFs
に書いてある通り,要はサンクとなる static closure のことを指しています.
ところでメモ化の要因は,確かに fact3
が CAF であることもありますが,一番の要因として, Core では関数適用の引数は let を通して変数に束縛されることになるので,実際にはこのプログラムは
fact3 = (!!) fact3' where fact3' = map fact' l l = [0..] fact' 0 = 1 fact' n = ...
みたいなものと等価になります (厳密にはこれも怪しいですが) .で, fact3' が CAF となるからというのが大きいですね (なお実際 GHC 8.6.5 では fact3' が floating out されていて, fact3 自体は最終的に eta expand されて fact3 = \x -> (!!) fact3' x
という形になっていました)
技術書典 5 ふりかえり
え?6?いやいや 5 ですよ?
池袋
慣れ親しんだ秋葉原の地を飛び出して池袋にやってきました。
めちゃくちゃ広くてびっくりです。秋葉原通運会館からアキバスクエアにやってきたときも思いましたが、同じ感想がもう一度。
ガラス張りじゃなくなったので外の行列見てやばいやばい言えなくなったのはほんのちょっとだけ残念です。
か61
kakkun61 という名前でもろもろアカウントを取っているのですが、今回は卓番号が「か61」ということでまさに自分のための場所でした。覚えやすい!
そんな弊卓の様子です。
落
新刊落としました…… フィルムカメラに目覚めた結果土日をそれに使ってしまい云々
ま、まぁ、でも、商業化した『Haskell で作る Web アプリケーション』は初技術書典持参だったし云々
はい。楽しみにしていただいたみなさまにはすみませんでした。
数字
被チェック数は60でした。
売上部数は下記の通り。
『手続き Haskell』は印刷部数のおよそ半分が売れて、『Haskell で作る Web アプリケーションは完売でした。
技術書典 2・4 でも頒布した(同人版ですが)『Haskell で作る Web アプリケーション』が思った以上にサクサク売れていったのが印象的でした。技術書典への新規参加者か、表紙がよくなったことか、その両方か。
それでは。
Servant と Relational Record でウェブアプリケーション開発
Servant とは
Servant は型レベルプログラミングによって、ウェブアプリとしてのインターフェースと実装との差異を防ぐことのできるウェブアプリフレームワークです。
haskell-servant.readthedocs.io
日本語記事としては lotz さんのこちらが分かりやすいので、参考にしてください。
Haskell Relational Record とは
Haskell Relational Record は言語内 DSL によって SQL を生成するもので、正しくない SQL に相当するものは型エラーとなります。
この2つを組み合わせることで、ユーザーからのリクエストから DB 操作を経てレスポンスの返答まで型に守られて開発ができるようになります。
この記事で解説するソースコードはこのリポジトリーで公開しています。
Stack の resolver は 12.26 を使用しています。
作るもの
下記のようなインタフェースを持ったアプリを作ります。
/books で返る JSON は次のような形式です。
{ "ABC of Read": { "name": "ABC of Read", "auther": "Mary" }, "The Good Text": { "name": "The Good Text", "auther": "John" } }
/book/1 で返る JSON は次のような形式です。
{ "name": "The Good Text", "auther": "John" }
ハンドラーの型を拡張する
DB 接続を扱うということは、ハンドラー内で接続にアクセスできないといけません。ここでは Reader モナドトランスフォーマーを Servant のハンドラーに積みます。ロガーも使うのでその上に Logging モナドトランスフォーマーも積みました。
type Handler = LoggingT (ReaderT (Pool Connection) Servant.Handler)
Api
型とそれぞれのハンドラーが定義されている場合、ハンドラー拡張前では Application
型の値は次のようになっているでしょう。この部分は積んだモナドトランスフォーマーをはがすように書きかえなければいけません。
app :: Application app = serve api server api :: Proxy Api api = Proxy server :: Pool Connection -> Server Api server pool = Index.handler :<|> Books.handler :<|> Book.handler
次のように書きかえます。
makeApp :: IO Application makeApp = do pool <- createPool connect disconnect 1 -- stripes 1 -- time for keeping open 5 -- resource per stripe pure $ serve api $ server pool api :: Proxy Api api = Proxy server :: Pool Connection -> Server Api server pool = hoistServer api (flip runReaderT pool . runStdoutLoggingT) $ Index.handler :<|> Books.handler :<|> Book.handler
接続は再利用したいので resource-pool を用います。server
関数は hoistServer
関数を使ってモナドトランスフォーマーをはがす関数を埋め込みます。hoistServer
などについてはこちらを参考にしてください。リンク先の記事は最新版の Servant 0.12 に対応させました。
クエリーの発行
通常は runQuery'
関数に接続を渡して使用しますが、今回作ったハンドラーは Reader モナドで接続を持っていますので接続を渡す部分を隠すことができるはずです。次のようなラッパー関数を作りました。
runQuery' :: (ToSql SqlValue p, FromSql SqlValue a) => Query p a -> p -> Handler [a] runQuery' q p = do pool <- lift ask withResource pool $ \conn -> liftIO $ R.runQuery' conn q p
モジュール構成
今のところ次のようなモジュール構成にして開発しています。
- app
- Main.hs
- メイン関数を持つ
- Main.hs
- src
- ServantHrr.hs
この記事は IIJ の執務時間を使って書かれました。
Haskell Windows Ctrl-C 動作確認
コード
コードは前回記事と同じです(再掲)。
import Control.Concurrent import Control.Monad import System.Exit import System.IO import System.Win32.Console.CtrlHandler main :: IO () main = do tid <- myThreadId let handler event = do if event == cTRL_C_EVENT then do putStrLn "goodbye!" killThread tid pure True else pure False pHandler <- mkHandler handler success <- c_SetConsoleCtrlHandler pHandler True when (not success) $ do putStrLn "SetConsoleCtrlHandler failed" exitFailure let loop n = do putStr $ show n ++ ", " hFlush stdout threadDelay 1000000 loop (n+1) loop 0
これを次の4通りのオプションでビルドします。
name: windows-interruption dependencies: - base >= 4.7 && < 5 - Win32 executables: app-rtsopts-threaded: main: Main.hs source-dirs: . ghc-options: - -rtsopts - -threaded app-threaded: main: Main.hs source-dirs: . ghc-options: - -threaded app-rtsopts: main: Main.hs source-dirs: . ghc-options: - -rtsopts app: main: Main.hs source-dirs: .
実行
これを実行してみます。
app
タイミングによる。
$ app 0, 1, 2, goodbye! goodbye! app.exe: thread killed (応答がなくなる)
$ app 0, 1, 2, goodbye! goodbye! app.exe: thread killed (終了する)
$ app 0, goodbye! app.exe: thread killed app.exe: warning: too many hs_exit()s
また、GHC 8.6.3 でコンパイルしたときですが、下記のようなエラーが出ることもありました。そもそも GHC 8.6.3 は Windows でのビルドにバグがあるので、他は GHC 8.4.4 を使っています。
$ app 0, 1, 2, goodbye! goodbye! Access violation in generated code when writing 0x20 Attempting to reconstruct a stack trace... app.exe: internal error: scavenge_stack: weird activation record found on stack: 5212000 (GHC version 8.6.3 for x86_64_unknown_mingw32) Please report this as a GHC bug: http://www.haskell.org/ghc/reportabug Frame Code address * 0x484dd00 0x736b99
app-rtsopts
タイミングによる。
$ app-rtsopts 0, 1, 2, goodbye! goodbye! app-rtsopts.exe: thread killed
$ app-rtsopts 0, 1, 2, goodbye! app-rtsopts.exe: thread killed app-rtsopts.exe: warning: too many hs_exit()s
app-rtsopts +RTS --install-signal-handlers=no
--install-signal-handlers はデフォルトでは yes。
タイミングによる。
$ app-rtsopts +RTS --install-signal-handlers=no 0, 1, 2, goodbye!
$ app-rtsopts +RTS --install-signal-handlers=no 0, goodbye! app-rtsopts.exe: thread killed app-rtsopts.exe: warning: too many hs_exit()s
$ app-rtsopts +RTS --install-signal-handlers=no 0, 1, 2, goodbye! goodbye! app-rtsopts.exe: thread killed
app-threaded
想定通りの動作。
$ app-threaded 0, 1, 2, goodbye! app-threaded.exe: thread killed
app-rtsopts-threaded
想定通りの動作。
$ app-rtsopts-threaded 0, 1, 2, 3, goodbye! app-rtsopts-threaded.exe: thread killed
app-rtsopts-threaded +RTS --install-signal-handlers=no
想定通りの動作。
$ app-rtsopts-threaded +RTS --install-signal-handlers=no 0, 1, 2, 3, 4, 5, goodbye! app-rtsopts-threaded.exe: thread killed
まとめ
- 想定通りの動作
- app-threaded
- app-rtsopts-threaded
- app-rtsopts-threaded +RTS --install-signal-handlers=no
- タイミングによる
- app
- app-rtsopts
- app-rtsopts +RTS --install-signal-handlers=no
タイミングによるときの動作。
- ハンドラー → 終了する
- ハンドラー → ハンドラー → thread killed 例外 → 応答がなくなる
- ハンドラー → ハンドラー → thread killed 例外 → 終了する
- ハンドラー → thread killed 例外 → too many hs_exit()s 例外 → 終了する
今後
ハンドラーが2回呼ばれるときは killThread
も2回呼んでいるはずなので、その後がおかしくなることはありそう。また killThread
しているが、それは自分自身ではないのかの確認もしたい。
System.Win32.Console.CtrlHandler
とか GHC RTS を追うしかない気がするので追ってみます。
GHC RTS はこの辺(rts/win32/ConsoleHandler.c)からかなぁ。
Haskell で Ctrl-C を制御する(Windows)
Ctrl-C 等の割り込みの扱い方です。
tl;dr
System.Win32.Console.CtrlHandler を使います。
Ctrl-C
が押されたらクロージングの処理を伴って終了するプログラムを書いてみます。
import Control.Concurrent import Control.Monad import System.Exit import System.IO import System.Win32.Console.CtrlHandler main :: IO () main = do tid <- myThreadId let handler event = do if event == cTRL_C_EVENT then do putStrLn "goodbye!" killThread tid pure True else pure False pHandler <- mkHandler handler success <- c_SetConsoleCtrlHandler pHandler True when (not success) $ do putStrLn "SetConsoleCtrlHandler failed" exitFailure let loop n = do putStr $ show n ++ ", " hFlush stdout threadDelay 1000000 loop (n+1) loop 0
実行してみましょう
> runhaskell Main.hs 0, 1, 2, 3, 4, 5, goodbye! Main.hs: thread killed
ちゃんと goodbye と出力されて終了しました!killThread
は例外を伴って終了するので Main.hs: thread killed
というメッセージが出てしまっています。もし気になるなら例外を握りつぶすか MVar
を使って終了を監視する仕組みを作るといいでしょう。
肝心の割り込みを制御する関数は c_SetConsoleCtrlHandler
です。
c_SetConsoleCtrlHandler :: PHANDLER_ROUTINE -> BOOL -> IO BOOL mkHandler :: Handler -> IO PHANDLER_ROUTINE type BOOL = Bool type Handler = CtrlEvent -> IO BOOL type PHANDLER_ROUTINE = FunPtr Handler
c_SetConsoleCtrlHandler
の第1引数にはコールバック関数(のポインター)を、第2引数には追加時に True
を、削除時に False
を指定します。
CtrlEvent
の値は予め用意されていて下記があります。
cTRL_C_EVENT :: CtrlEvent cTRL_BREAK_EVENT :: CtrlEvent
Handler
の返り値は、イベントを処理して次のハンドラーにイベントを伝播させないなら True
を、そうでないなら False
を指定します。上の例では handler
という関数にメッセージの表示とメインスレッドの停止の処理を書いて Handler
として渡していました。
この記事は HaskellでCtrl-Cを制御する - Qiita のオマージュです。
Help wanted
runhaskell を使うと確かにこの動作をするのですが、ビルドして実行バイナリーを作ると Ctrl-C を2回打たないと止まりません。原因と背景を説明できる方いませんか?
> stack exec windows-interruption-exe 0, 1, 2, 3, goodbye! goodbye! windows-interruption-exe.EXE: thread killed
あと、Ctrl-Break だとハンドルせず終了するはずだけどしないような……
ちゃんと C のドキュメント読もう。→ 読んだ。理解は合ってそう。(追記)
議論は Haskell-jp Slack で。参加方法はこちら。
Windows で Haskell iconv をビルドする
GHC 8.2 以降で stack を使う場合をここではとりあげる。
確信はないのだが、GHC 8.2 から GHC 自体が iconv に依存しなくなったのか、$(stack path --programs)\ghc-8.0.2\mingw\lib から libiconv.a と libiconv.dll.a がなくなっているため GHC 8.0 以前のようにビルドができなくなっている。
なので、まず libiconv を取得する。
stack exec -- pacman -S libiconv-devel
インストールされる場所は stack がデフォルトでは見に行ってくれないので明示してやる。MSYS バージョンは将来的に変わることもあるだろう。
stack build --extra-include-dirs="$(stack path --programs)\msys2-20180531\usr\include" --extra-lib-dirs="$(stack path --programs)\msys2-20180531\usr\lib"
これでコンパイルはできるがリンクに失敗する。
`libiconv_open' に対する定義されていない参照です
iconv パッケージの cabal ファイルを編集してやる。
--- a/iconv.cabal +++ b/iconv.cabal @@ -26,7 +26,7 @@ library includes: hsiconv.h include-dirs: cbits c-sources: cbits/hsiconv.c - if os(darwin) || os(freebsd) + if os(darwin) || os(freebsd) || os(windows) -- on many systems the iconv api is part of the standard C library -- but on some others we have to link to an external libiconv: extra-libraries: iconv
iconv を利用するプロジェクトの stack.yaml で、編集後のリポジトリーを extra-deps
に指定して stack build
するとビルドできる。
Leica M3
Lomography Konstruktor F・Diana Mini から始まったフィルムカメラ熱ですが一瞬で行くところまで行ってしまった感じです。
Leica M3。
現在まで続く M 型 Leica の始祖を買ってしまいました。1962年製の56歳です。
(この写真を撮ったレンズも Asahi Super Takumar 55mm F1.8 なので60年代のレンズです。)
Leica 意識前
初めはフィルムカメラの入門機としていくつかの記事に紹介されていた Asahi Pentax SP か Olympus OM-1(M-1)かと考えて中古カメラ屋めぐりをしていました。
このころはひたすらサンライズカメラ*1の記事を読みあさっていました。
めぐったのは新宿・中野・秋葉原・御徒町・上野の次のお店です。(抜けがあるかも。)
東京は中古カメラ屋さん充実してますね。
で、東京カメラで Asahi Pentax SP か Olympus OM-1 が気になるんですよという話をしていたはずなのに、店員さん(昨日カメラさん)と話していたらいつのまにかどれが至高の Leica なのかとう話になり、帰るときにはそれぞれの Leica がどう違うのか調べないといなという気持ちになっていました。(Bessa R3M 気になってるとか言った気がするからかな。)
値段でいうと Asahi Pentax SP か Olympus OM-1 が3万あればレンズ含め買えるのに対して、Leica は M 型だと少なくとも10万円で本体が買えるかどうかというレベル。
どうしてこうなった。
Leica 意識後
それから Leica が気になって、昔の雑誌などを読んで(スキャンされたのが Kindle で出版社から売ってある)、やっぱり欲しいなぁという気持ちになったので、世界の中古カメラフェアで買うことにして買いました。
露出計付きの M6 にしようかと思ったんですけど、M6 修理してくれるところがほとんどないので、修理してもらえる M3 に外付け露出計を使った方がよいと昨日カメラさんから助言をもらい、M3 にすることにしました。
東京カメラには悪いんですけど(東京カメラの買うか悩んでいたのが売れてしまっていたのもあって)、結局早田カメラで買いました。(東京カメラにはお世話になったのでまたレンズなんかを買いに行きます。)
早田カメラは自店でオーバーホールもしていて永年保証してもらえるのがすごくいいですね。
25万円以上して綺麗な見た目のものと、傷・当たりがあるけど14万円のものがあって、さすがに25万円以上は払えないなぁと14万円の方にしました。
早田さんとお話ししたところによると、5年から10年ぐらい使うとシャッター音が変わったなということがあるので、そうすると修理に持ってきてほしいとのことでした。
Leica お迎えした pic.twitter.com/NunWUG6gia
— kakkun61@技術書典5 か61 (@kakkun61) 2018年9月15日
レンズは Elmar f = 9 cm 1:4 にしました。元々 APS-C で 55mm が好きだったのでじゃあ 90mm かなということでそうしました。Leica だと 35mm や 50mm が人気らしいですね。レンズ前玉に拭き傷と塗装剥げのせいで、無保証の B 級品の2.5万円ほどとやすいものでしたが、特に写りには問題なさそうです。
写真
フィルムは、富士フイルム 記録用 ISO 100 だったはず。
スキャン後、切り抜きだけしています。(理由は後述。)
これ以降は Lomography Color Negative 400。
使ってみて
9cm のレンズを使ったときのパララックスが結構ひどくて次の写真が分かりやすいんですが、これファインダーでは左右対称に撮ったはずなんですよね。左側に大きくずれています。それで上記の画像の何枚かは切り抜きしています。
それが分かってからは気持ち右にずらして撮っています。
あとは、レンジファインダーの二重像がちょっと上下にずれてて、それさえなければなという感じですね。これは本体を買うときにもっとお金を積むかどうかの問題ですね。
追記:上下像ずれはレンジファインダー機ならすぐ直せるようになっているらしく、数分で直してもらえました。
レンズとしてはゴーストが大きく出ますね。
なので、後で新宿中古カメラ市場でフードを買い足しました。Leica 純正フードが高いのなんの。金属の筒が1万円する。中国とかでプラスチックで作ってくれないかなという気がしてきますね。そうするとたぶん1000円もしないでしょう。量が売れないから高くなるかな?
あと、シャッター音は唯一オペラハウスでの使用が認められた静かさとのことですが、なんだか自分には腑抜けた音に思えます。別にいいんだけど。
その後
Elmar 50mm 1:2.8 が増えました。早い。
9cm 使っててやっぱり窮屈だなと思ってしまって。APS-C 55mm との差はわりとありました。これはレモン社で6.5万円ほどで買いました。(東京カメラじゃないんかい。9cmのフードを一緒に買いたくて新宿に行っちゃったので。)
50mm 使うときの問題としては、自分が眼鏡をかけているのでファインダーのブライトフレームがケラれてしまうことですね。視度補正レンズが Leica やマップカメラから出ているなんですけど -3 が限度で、どうも自分は -4 よりきついみたいなのでムリそうですね。今は眼鏡をかけてピントを合わせた後、眼鏡を上げて裸眼でぼんやり像でフレームしてます。これもうバルナックと手間変わらないな?
50mm の写真
フィルムは富士フイルム 記録用カラーフィルム ISO 400。F2.8 で ISO 400 なら夜も平気ですね。だいたい1/125秒で撮ってました。現像してみるまで本当に撮れているのか半信半疑でしたが。
夜の新宿です。
フィルムしてみて
フィルム代と現像・スキャン代が想像以上にかさむ……
やすい記録用フィルムが1本330円ほどで現像・スキャンが1本1000円。8月末にフィルムを始めてもう12本撮っていて、となると1.6万円。高え……
スキャンだけでも家でと考えてヨドバシカメラでスキャナーの話を聞いてきたんですが、スキャン時間がかなりかかる(1フレーム2分とか)みたいで断念。2分×36枚で72分しかもその間放置ではダメで作業が生じる。
デジカメでフィルムを撮るのはほこり除去が大変でおすすめしないと言われたが、実際どうなんでしょう?
しばらく撮りまくって満足したらデジカメの比率を上げることにします。
使ったフィルムは次の6種類。正直ネガは利きフィルムされてもどれがどれか分からないと思います。
- 富士フイルム 記録用カラーフィルム ISO 100
- 富士フイルム 記録用カラーフィルム ISO 400
- 富士フイルム Superia X-Tra 400
- 富士フイルム Superia Premium 400
- Lomography Color Negative 400
- Lomography Slide / X-Pro 200(クロスプロセスで現像待ち)
使ってないけど買ってあるのは次の4種類。
さて次はどこに撮りに行きますかね?