Hatena::ブログ(Diary)

think and error このページをアンテナに追加 RSSフィード

2015-12-30

最低限必要な言語機能

00:11 |  最低限必要な言語機能を含むブックマーク

チーム開発で必要な最低限の機能、条件を見極めたいと以前からずっと思っていた。その後の手法も考えているけど今は省略。現状の仮説は以下だ:

  • Parametric polymorphism
  • Closures
  • nullが存在しないこと

この条件を満たすとなると途端にHaskellOCamlあたりしかなくなるという現実。特に三番目がなかなかのネックだ。

早くnullが無い言語が主流になってほしい。

2015-11-25

Parametricity

23:35 |  Parametricityを含むブックマーク

最近parametricityについてジャバを書きながらずっと考えていたのだけど、割と便利な結論が出てきたと思う。

継承を用いたデザインパターンはできないだろ、とか突っ込まれそうだけど実質同じ用途だったら同じとする。そこの差異に興味はない。

デザインパターンの定義はなんだよ、とかparametricityはなんだよとかも突っ込まれそうだけどまあそのうち。


論自体はまだまだ続くのだけど。例えば型クラス拡張版は簡単に導出できる。後はhigher-order-kindの型パラメータどうするかとか、Theorems for free!を基に考えてみるとか。あとプログラミングだけでなく一般の思考メソッドとしても用いることが出来る。


そのうちまとめてどこかで発表するかもしれない。


今まで設計に関する議論で気になってたことは、ドメインに踏み込めないことだ。そこをなんとかしたいとずっと考えていた。しかしparametricityならドメインの問題に踏み込みつつドメイン情報を排除し、問題の構造パターンを正しく構築し、間違えずに再利用することが出来る。パターンを組み合わせても問題なく動く。素晴らしいじゃないか。


幸い現在は関数プログラミング周辺が賑やかになっている。parametric polymorphismを活用するには静的型付き関数型言語はOOPLより良いものだ。その理由は関数オブジェクトに比べて十分に小さいからだ。

最近関数型言語のデザインパターンに関して本も出版されたし、これから設計手法、実装手法がもっと発達しそうだ。


2015-11-04

関数プログラミング交流会で発表した

23:54 |  関数プログラミング交流会で発表したを含むブックマーク

ブログに書くという行為を忘れがちな昨今。

9/13に関数プログラミング交流会があったので発表してきました。

http://connpass.com/event/16193/

関数プログラミングという題目のため、参加者はかなり広いと思われました。そのためわかり易い話題とわかり易い遷移を心がけつつコアな人にも何か持って帰るものがあるといいなーと作成しました。まあしかし発表時間の短さ故にかなり早口で喋ったため、置いて行かれたように感じた方もいたようです...


twitterで質問がありましたが、スタックオーバーフローとかネタとしてはもう少しあったのですが流石に詰まりすぎかなと断念。並行プログラミングネタをもっと前面に押し出さないと題名負けかなーと思ったけどこれも色々あって断念。並行プログラミング関係なく継続モナドが便利なだけでは?という心の声を無視しつつスライドを完成させました。まあ非同期例外にも触れられたし後はheyhey Haskell本を読めばわかるでしょう。


並行周りは何かもう少しありそうだし色々試したいですね。

STM良いですよねSTM。

2015-05-14

Haskellの遅延評価についてメモ

11:00 |  Haskellの遅延評価についてメモを含むブックマーク

以前から考えていたことを吐き出したのでメモしておく。

あとで検証してまとめたい。

実用上知っておくべき部分はもっと少なくていいはずだし、そちらも出来るならまとめたい。


2015-05-13

宣言的とは、宣言とは

10:16 |  宣言的とは、宣言とはを含むブックマーク

「宣言的」というあやふやな言葉にもう少しまともな定義はつけられないかという試み。

宣言とはInvariantであるとして、対象のシステムを明示した方がいいのでは、という話。


参考link:

2014-10-28

函数型なんたらの集い2014でモナドについて話してきた

00:52 |  函数型なんたらの集い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

懇親会

懇親会では@notogawaさんにAgdaについて教えてもらったり名古屋の型とワイワイしたりしてました。

Agdaは多分20-30分くらいしか話してないですけど独学3ヶ月分くらい進んだのではーと思いますねいや適当ですよ。

まあVimmerとしては一番の問題Emacsだったりします。

2014-09-21

GHCの末尾再帰最適化をCore上で確認してみる

01:31 |  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と関数適用についてだ。

  1. case式はネストした評価に対応する。「case e of _ {...}」を実行する際は、戻りアドレススタックにプッシュした上でeの評価を開始する。評価が終わって、プッシュしておいたアドレスに制御が戻ると、戻り値を調べて分岐する。eが単純なプリミティブ演算の場合は、呼び出しを経ずにインラインで直接それを実行する。
  2. 関数適用はジャンプ(末尾呼び出し)に対応する。「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読むけど。