Gauche > Archives > February 16, 2007

# nobsun
# 話は換るけど。2chのHaskellスレ
# at 4:57am (February 16)
# http://pc10.2ch.net/test/read.cgi/tech/1162902266/
# at 4:58am (February 16)
# 735あたりからのモナドの解説すばらしい。

なんか，読んでたら，世界は広いのー (日本だけど) という気がしてきたよ．

Haskell とかまでくると，本当に数学科の方が情報系よりも強い気が．というか，物理学科でも，普通に情報系よりも計算機わかってる人はゴロゴロしてそうだしなぁ．やっぱり，体系化のレベルが全く違う．歴史の重みを感じる．

だって，数学科の人よりも数学わかる素人とか，物理学科の人よりも物理わかる素人って (学部のレベルでさえ) ほとんどいないよね，たぶん．それらに比べたら，ソフトウェアとかプログラミングなんつーのは，はるかに誰でもできる度が高いと思う (逆に言うと，数学科や物理学科に入れば，誰でも到達できる程度のレベルにさえ，今の (普通の) 情報系学科は学生を育てて押し上げることができてないとも言える．属人性が高すぎるというか (とりあえず〜性を付けておけばそれっぽく見えるブログ論法) まぁ，もともと大学ってそんなもんかもしれないけど)．実際，僕の尊敬する人々の中には，非情報系が多い気がする (というか，主に 3 人ぐらいだけど)．

# 俺は全く物理をやってないので，理学部の人は (後輩でも) 無条件に尊敬してしまうという傾向がある．

781 ：デフォルトの名無しさん ：2007/02/16(金) 15:09:47
    続き．本当は以下の例は正しい Haskell の計算モデルでないし
    定義もいくらか怪しいけれど，イメージということで許していただきたく．

    >>778
    例として
    　sqr x = x * x，dup x = 2 * x
    という関数を考え，sqr (dup 3) という『計算』を考えてみる．
    いわゆる手続き言語ではこの式は
    　sqr (dup 3) = sqr 6 = 36
    と『計算』を次々と『値』に潰していくので
    型は常に整合しているんだけど，Haskell では
    　sqr (dup 3) = (dup 3) * (dup 3) = ...
    『計算』そのものを『計算』していく．これは sqr の型を
    考えるとちょっと奇妙．だけど monad (T,η,*) を
    　T：X を「X を返す『計算」にうつす函手
    　η：『値』をその値を取り続ける『計算』にする自然変換
    　*：『値』を取る『計算』から『計算』をとる『計算』への変換
    と定義してやり，sqr (dup 3) が本当は
    　sqr* (dup* (η3))
    を意味していると思うと，きれいに理解できる．
    （この η, * は Kleisli triple の条件を満たしている．
    　ほかの計算モデルでも η， * は同じような役割を果たすので
    　Kleisli triple の条件が必要なのが理解できる） 

とりあえず，自然変換という概念の導入が大変素晴らしいということが，この 1 レスだけでわかった．

あと，これ．

279 ：デフォルトの名無しさん ：2006/12/09(土) 23:52:51
    >>278
    >つまり、IOならIOについて(fmap calc)をひとかたまりとみなすべきであり、
    >そういうスタイルを奨励するためにcalcIOという名前を付ける、ということか。

    いや、そこまで強くは言っていない。名前付けたのはわかりやすくするためで
    >>273みたいな名前付けない使い方が一般的だと思う。
    というか経験的にすでにわかってることなんだと思う。

    >ただ、相変わらずこのように書くことの現実的利益がわからない。

    考えを整理できるとかそういう部類で現実的利益といわれると無いね・・・。

    >「圏論を知らないとHaskellを使うのにどれくらい支障があるか」という点については、
    >はっきりさせておきたかった。俺としてはHaskelll(のような言語)が
    >真に一般に普及してほしいと思っているので、経験だけではカバーできない
    >重大な困難があるかどうかが気になった。

    Haskell使用するというレベルでは圏論の知識の有無による
    困難は表面的には無い。が根源的には結構困難があると思う。
    おそらく人のコードを読むという段階であらわに出てくるハズ。
    fmapにしたってファンクタの概念をつかって圏論チックな考え方で
    使おう思っている人と、そうじゃない人だと使い方が違う。
    そういうのが積み重なって人によってはその書き方の意図が
    読めないコードというのが出てくると思う。
    そういう意味では結構困難がある。
    まぁ要するにコーディングスタイルの問題。
    圏論的なものを取り入れたHaskellコーディングスタイルを確立する
    のかあくまで経験的なコーディングスタイルを確立するのか。 

これはまぁ，いろいろ仕方ない気もする．

たとえば C なんて，計算機アーキテクチャに対する知識が全く無くても，とりあえずオマジナイと慣習だけ習得してしまえば，なんとなく書いて行くこともできるけど．

強力な言語，というか，ハッカーに好まれるタイプの言語ってのは，(それが良いか悪いかはおいといて) 恐らく背景知識の量とか経験とかが，モロにコードに反映されるような類の言語なのでは無いだろうか．コードを見れば，その人の力量が一目瞭然のような．逆に，企業というかスーツというかは，誰が書いても同じようになる道具と，交換可能な部品を求める．

例えば (って，思いっきり特定の人物二人を念頭において喋ってるけど)，qsort の第四引数に文字列渡すとか，main=195; とか，NULL を mmap するとか，kichig*i じみた codeGolf とかなんてのは，単なる経験的なコーディングスタイルからは永遠に生まれてこないだろうなと思う (まぁ，ここまで極端なコードってのは普通は表には現れてはこないだろうけど)．

それと同じようなことが，Haskell なんかでもあるのではなかろうかと．というか，極論を言えば，Haskell をプログラミング言語だとか思っているようなうちは，まだ何も理解して無いのかもしれない (笑) し，そうでもないのかもしれない．

ま，とりあえず，The Haskell Programmer's Guide to the IO Monad ― Don't Panic でも読んで，自然変換って何なのかを学んでみるか．

まだ The implementation of the Gofer functional programming system も読み終わってないんだけど．

# 毎晩寝る前にチビチビ読んでるんだけど，この論文は面白い．

なにやらマックレーンの黄色い本を nobson は薦めてたけど，ネット上の評判を見てると普通に無理くさい気が．代数学とか全然知識無いからなぁ．

ちなみに，TAPL の Pierce の薄い本は，パンピーには無理げらしい．

771 ：デフォルトの名無しさん ：2007/02/16(金) 01:46:57
    >>756
    すごく大雑把に言うと，チューリングマシンや
    λ計算などがあったところに，新しい定式化として
    圏論に基づくものが現れたという背景がある．

    現在，普通のプログラマはチューリングマシンや
    λ計算を知らなくても特に問題は起きないけれど，
    それと同じようなものだと考えるのが順当だと思う．
    （もちろん知ってたほうが良いのは確かだけど，
    　とりあえず大雑把なところを抑えておけば十分．）

    ラーニングコストが高いのは，まだ新しい理論である
    ということと，従来の手法よりも数学的に取り扱いやすい
    枠組みとして導入されたことがあるので，教育用に
    整理されてない現段階では，好きな人がやるものだと
    思ったほうがよいと，個人的には思う． 

ふむ．いろいろロマンティックではある．

---

All About Monads Haskell におけるモナドプログラミングの理論と実践に関する包括的ガイド Version 1.1.0

昔さっぱり理解不能だったトラウマがある文章なんだけど，ようするに，モナド以前に，Haskell （特に代数データ型とか型クラスの概念） を知らなかった，というだけのことだったみたい．

ある程度 Haskell でプログラミングをした今だと，ふつーにびっくりするぐらいよくわかる．むしろ，なんで昔はあんなにわからなかったのかわからないぐらい．

まぁ，ふつけるにせよ，この文章にせよ，ある程度モナドの有用性というか，ようするに何がしたいのか，ということがわかってないと，独特の慎重な言葉まわし (わかってる人は，厳密に書かないと気持ち悪いだろうし，うかつなことを書いて誤解を広めると非常にやっかいなので，それを恐れているのだと思う．あるいは，単に翻訳だから ?) とかが何を言いたいのかさっぱりわからないので，意味があるのか無いのかは微妙．一度ブートストラップに成功したら，後は加速度的に理解は進むと思うけど．

とりあえず，Maybe モナドは非常に有用でかつ御利益がわかりやすくて素晴らしいものなので，Maybe から説明する戦略というの良いと思うんだけど．Maybe とか List ってのは，単に統一的に計算を構造化するための枠組なので，モナドで包むのも値を取り出すのも自由にできるんだけど．むしろこっちの方が特殊なのかな ?

一般には，IO モナドみたいに，一方向，包むのはできるけど，外すのは (unsafePerformIO 使えばできるけど) できないという方が普通のようだ．

んで，これはボクが低能過ぎるのか，常識過ぎて誰も書かないのかはわからないんだけど，「IO モナドを使うと参照透明性を破壊することなく入出力を実現できる」 とかは，まぁ，誰もが書いてることなんだけど．なんでそうなるのか ? ってことは，ほとんど書かれてないような気がする．

わかってしまえば簡単なことなんだけど，そもそも参照透明性の概念ってのは．

関数が同じ引数で呼ばれたら，必ず同じ値を返す （から，自由にプログラム中に出現する関数とか，関数の返り値に束縛した変数を，等しい (プログラム = 等式の集まりだから) もの同士で置き換えて良い）

肝は，一度しか呼ばれないことが （何らかの手段によって） 保証できれば，あとはどうでも良いということだと思う．

そもそも関数が，絶対に一回しか呼ばれなければ，関数が副作用を持つかどうかを観測する術は （定義からして） 無いので．

外界との IO なり破壊的更新なりで，計算途中で内部状態が変わったとしても，一度 IO モナドの世界に入った値に直接変数を束縛することは （バックドアを使わない限り） できないし，>= とか return でつながれたモナドシーケンスの中には外界から触れることはできないんだから，同じ引数で関数が呼ばれるということは二度と不可能になる．

出口はない

すべての関数は同じ引数で呼ばれれば必ず同じ値を返すというのは Haskell が純粋な関数型言語であるための本質的な性質です。しかし、IO モナド中で、I/O関数 getChar :: IO Char を使うことには 全く問題ありません。一方向モナド内の一つのシーケンス中では一度しか使われないからです。これを使うどのような関数のシグネチャーからも、型構築子 IO を除去する方法はありません。

いや，もちろん頭では理解してたつもりだったんだけど，これが実感を持って感じられるようになるまではけっこう時間がかかった気がする．普通はつまづかない，どうでもよいところなのかもしれないけど．俺はけっこう引っかかったから，恥ずかしいけど誰かの参考になるかもしれないので，念のために書いておく．

CLEAN の一意型ってのも，たぶん同じことを実現するための手段だと思う．より直接的になってるぶん，IO モナドよりは部分的にはわかりやすい手段なんだろうけど，複雑で副作用を含む高階関数の計算を統一的に組合せるための構造化の枠組というほど汎用的なものではない気がする （線形論理とかよく知らないので，気がするだけ）．これは，CLEAN が実装よりの中間言語だった，という歴史に由来するのかもしれない （し，全然関係ないのかもしれない．Haskell だって，最初からモナドが採用されていたわけじゃないし）．

まぁ，まだ一章を読んだだけなんだけど．二章はともかくとして，三章はモナドの合成とかでてきて，いろいろとステキなことになってる感じ．寝不足で半分死んでる脳にはつらいですのう．

# 昨日は 17:00 に起きて （飲みすぎ），今日は 10:30 に起きたという．いきなり半日ズラして生活ペースを元に戻すという暴挙．ていうか，最近堕落しすぎ．このまま順調に推移すれば，明日は 5:00 とかに起きることが可能になりそうですが，たぶん僕の起床時間関数はノンモノトーンだと思います．

---

オードリー ﾀｿ の Haskell の紹介スライドを眺めていたら，思っていたよりも Haskell の FFI とか Eval は簡単っぽいなと思ったので試してみた．

たぶん GHC 限定の拡張を使ってるっぽいので，とりあえず GHC6 をインストールする．

# apt-get install ghc6
パッケージリストを読み込んでいます... 完了
依存関係ツリーを作成しています... 完了
以下の特別パッケージがインストールされます:
haskell-utils libgmp3-dev libgmp3c2 libgmpxx4
提案パッケージ:
ghc6-prof ghc6-doc haskell-doc libgmp3-doc libmpfr-dev
以下のパッケージは「削除」されます:
libgmp3 zinc-compiler
以下のパッケージが新たにインストールされます:
ghc6 haskell-utils libgmp3-dev libgmp3c2 libgmpxx4
アップグレード: 0 個、新規インストール: 5 個、削除: 2 個、保留: 0 個。
24.1MB 中 0B のアーカイブを取得する必要があります。
展開後に追加で 103MB のディスク容量が消費されます。
続行しますか [Y/n]?

さようなら… Zinc ，さようならカレー．そしてこんにちはグラスゴー．

そのほかにも，libghc6-src-exts-dev ってのが必要っぽいので apt-get しておく．

んで，System.Eval.Haskell を使うためには，hs-plugins ってやつが必要っぽいんだけど，apt-cache してもみつからないので，テキトーにここから libghc6-plugins-dev_0.9.10-3.4_i386.deb ってやつを持ってきて dpkg -i してみた．

あとは，とかとかを参考に… (ていうか，Web 上にびっくりするぐらい情報が無いよ…)

$ cat eval.hs
import System.Eval.Haskell

main = do i <- eval "1 + 2 :: Int" [] :: IO (Maybe Int)
          if isJust i then putStrLn (show (fromJust i)) else return ()

$ ghc eval.hs
compilation IS NOT required
eval.o: In function `r1aT_info':
(.text+0x46): undefined reference to `pluginszm0zi9zi10_SystemziEvalziHaskell_eval_closure'
eval.o: In function `r1aT_info':
(.text+0x4d): undefined reference to `altdatazm0zi9zi10_AltDataziTypeable_zdf15_closure'
eval.o: In function `r1aT_srt':
(.rodata+0x0): undefined reference to `pluginszm0zi9zi10_SystemziEvalziHaskell_eval_closure'
eval.o: In function `r1aT_srt':
(.rodata+0x4): undefined reference to `altdatazm0zi9zi10_AltDataziTypeable_zdf15_closure'
collect2: ld はステータス 1 で終了しました

ありゃ… 駄目か．う〜ん，難しい．AltData/Typeable と System/Eval/Haskell のライブラリがリンクできないぞ ！ とか怒られてるみたい．たぶんインストールが間違ってるんだろうけど，面倒なので諦めよう （駄目）

次は FFI やってみよう．もう gauche とか Ruby とか Common Lisp みたいな動的言語では散々やってきたことだけど，Haskell は強く型付けされるので微妙に面倒．

Haskell の文字列は，文字のリストだから，まずは CString を作らないと駄目．んで，ヌル終端の C 文字配列を作るためには，Foreign.C.String の newCString が必要 (via haskellのある暮らし FFI: Foreign Function Interface)

しっかし，なぜかこいつが，IO CString とかいう謎の型を返すので，型が合わなくて困った… まぁ，とりあえず困ったら，いつもの unsafePerformIO で ！！

$ cat ffi.hs

{-# OPTIONS -fglasgow-exts #-}

import Foreign
import Foreign.C.String
import System.IO.Unsafe (unsafePerformIO)

foreign import ccall "stdio.h printf" _printf :: CString -> IO ()

main = _printf $ unsafePerformIO $ newCString "hello, ffi!\n"

$ ghc ffi.hs

$ ./a.out
hello, ffi!

うわー，マジかよ．コンパイル通って，うごいちゃったよ… どうみても無理矢理型合わせただけなんだけど，こんなんで良いのかよ，Haskell …

とりあえず void の C 関数は IO () ってことにしとけば良いのかね．あと，なんで stdio.h の場所が，C コンパイラでも何でもない ghc が認識してるの ? (ghc のバックエンドは gcc らしいから，そのせいかも) 謎過ぎる．

しっかし，newCString でアロケートしたメモリは，Foreign.Marshal.Allocの free 関数を使って明示的に開放してやらないと駄目らしい．面倒過ぎる．

まぁ，Haskell も，がんばれば何でもできるということがわかったのが収穫であった．


結論 : IO モナドが無くても，Haskell で入出力は可能．メモリ管理も全部手動でできる．

---

追記 : FFI 呼出しの後，自動的に領域を開放してくれる withCString という便利な変換関数があるそうです．詳しくはコメント欄を

---

b2ox 先生曰く，これが Haskell らしい解法らしいです ｗ

module Main where
import Text.ParserCombinators.Parsec
import System.IO.Unsafe ( unsafePerformIO )
import Data.Char ( isNumber )
data AST = INT Integer
         | REAL Double
         | SYMBOL String
         | LIST [AST] deriving (Eq, Show)
symbol :: Parser String
symbol = many1 (alphaNum  <|> (oneOf ".%_!$#|+-*/:<=>?@^&~"))
intOrRealOrSymbol :: String -> IO AST
intOrRealOrSymbol s = catch (readIO s >>= return . INT)
                            (\ _ -> catch (readIO s >>= return . REAL)
                            (\ _ -> return (symbolOrReal s)))
                        where
                          symbolOrReal s = let (n, m) = span isNumber s in
                                             if length n > 0 && m == "."
                                              then REAL (read n)
                                              else SYMBOL s
atom :: Parser AST
atom = symbol >>= return . unsafePerformIO . intOrRealOrSymbol
list :: Parser AST
list = between (char '(') (char ')') (sepBy (atom <|> list) spaces) >>= return . LIST
test = parseTest list "(abc 1 12. 1.2.3 (1.2 1) 1.2)"

between とか使って，多少小手先の改良を加えたつもり．

   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.6, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( C:/Documents and Settings/aloha/??????????
??/haskell/intOrFloatOrSymbol.hs, interpreted )
Ok, modules loaded: Main.
*Main> test
Loading package parsec-2.0 ... linking ... done.
LIST [SYMBOL "abc",INT 1,REAL 12.0,SYMBOL "1.2.3",LIST [REAL 1.2,INT 1],REAL 1.2]

僕は Haskell のレイアウト規則とかあんまりわかってないので，微妙にインデントに苦労した… セミコロンとプレース万歳 ！！

# というわけで，C 脳 S 式脳の僕はたぶん Python や Ruby や JS は一生使わないと思います．インデントで意味が変わるような言語は，自動生成の時 pretty print が面倒だし (ぉ

readIO で Integer 型に強制しつつ無理やり読み込んで，駄目だったら例外キャッチしつつ Double 型で無理やり読み込んで，それでも駄目だったらシンボルとして読み込んだ後，unsafePerformIO でモナドを剥ぎ取るという荒技 ｗｗｗ

readIO って便利だな〜，例外を吐くし実行も止まらない〜と．

いやぁ，Haskell は奥が深い．副作用の織り成す美の，なんと神秘的なことよ (感嘆)

結論 : 本物のプログラマは unsafePerformIO を恐れずに使う．みんな大人なんだから．

---

ものすごく基本的なんだけど，整数と浮動小数点数のパースがけっこう面倒だった．

これくらい，最初から用意しておいて欲しいな… と思いつついろいろやってみた．

面倒の原因は，Parsec が，なぜか文字を消費しない一文字先読みができないっぽい （いや，そんなバナナって感じなので，オイラが何か大きな勘違いをしてる可能性大だけど） ということ．

さらに LISP のリーダなんかだと，数字で始まっていてもシンボルである可能性すらある (例えば，1.2ab とか) から，さらに面倒になる．

一文字先読みさえできれば，まず最初は整数としてパースを進めていって，'.' が表れたら try でバックトラックして浮動小数点数扱いでパースを進めていって，数字以外が表れたら try でシンボルとして最後までパースするということが簡単にできるんだけど．

とりあえず．

module Main where

import Text.ParserCombinators.Parsec

data AST = INT Integer
         | REAL Double
         | SYMBOL String
         | LIST [AST] deriving (Eq, Show)

symbolParser::Parser AST
symbolParser = do { s <- many1 (letter <|> digit <|> (oneOf ".%_!$+-*/&~"))
                  ; return (SYMBOL s)}

realParser::Parser AST
realParser = do { a <- number
                ; char '.'
                ; b <- number
                ; space
                ; return (REAL ((read (a ++ "." ++ b))::Double))}

intParser::Parser AST
intParser = do { i <- number
               ; space
               ; return (INT (read i))}

number::Parser String
number = do { n <- many1 digit
            ; return n}

elmParser::Parser AST
elmParser = do i <- try intParser    ; return i
        <|> do r <- try realParser   ; return r
        <|> do s <- try symbolParser ; return s

listParser::Parser AST
listParser = do { char '('
                ; l <- sepBy sexpParser spaces
                ; char ')'
                ; return (LIST l)}

sexpParser::Parser AST
sexpParser =  do e <- elmParser  ; return e
          <|> do l <- listParser ; return l

オブジェクトの最後にかならず空白を開けないといけないのが非常にダサいけど．一応できてるっぽい．

$ hugs parseSexp.hs

Main> parseTest listParser "(abc 1 12. 1.2.3 (1.2 1 ) 1.2 )"
LIST [SYMBOL "abc",INT 1,SYMBOL "12.",SYMBOL "1.2.3",LIST [REAL 1.2,INT 1],REAL 1.2]

oneOf の中に，EOF とか，正規表現や boost::spirit みたいに文字集合の集合演算が直接書ければ良いんだけど…

あと，"12." が，12.0 じゃなくてシンボル扱いになってるのがダサい (gauche とかだと，ちゃんと 12.0 になる)．でもこれをちゃんとやろうとすると，Haskell の read の仕様とかを見る限り，微妙に面倒になりそうな気もする．

# 今書いてて気付いた．(read ("12." ++ "0"))::Double とかするだけで良いね．全然面倒じゃなかった．

ていうか，これはパーサじゃなくてレキサで解決すべき問題のような気がしてきた．レキサとパーサを分けなくて良いってのが，Parsec の利点だったはずなのに ！！ （たぶんボクがクズ過ぎるだけだろうけど）

naturalOrFloat とかいう，いかにもいかにもな香りがする関数は見つかった (wo さんの，a24z の Persec パーサから発見) んだけど，import qualified Text.ParserCombinators.Parsec.Token as PT あたりの使いかたがさっぱりわからんし，ウェブ上にもやたらでかいコード例しか無いよ ＞＜

だれか整数と浮動小数点だけレキシカルアナライズするような最小のサンプルを書いてください ！！ （他力本願）

あと，Ruby の Parsec パーサをパクろうと思ったら，RType のサイトが落ちてた… orz

ParsecLanguage モジュールの中に，java-style とか haskell-style だけじゃなくて，もっと大量の言語の定義が入ってたらいろいろ面白いのに．とりあえず，青木さんにはふつけるの付録として，ruby-style と ruby のパーサを付けておいて欲しかった （無茶）

というか，ParsecLanguage の中にどんな言語が入ってるかを調べる方法すらよくわからん．やっぱりソース見るしか無いの ?

---