a posse ad esse from possibility to reality

297月/110

Parsecで数式のパーサを書いてみた(Applicative Functor版あり)

wvogel00のために、昔書いたParsecを使ったコードを載せてみます。コメントに書いてあるのはコードに直す前のEBNFです。

import Text.ParserCombinators.Parsec
 
run :: Show a => Parser a -> String -> IO ()
run p input =
    case (parse p "" input) of
            Left err -> do
                putStr "parse error at "
                print err
            Right x  -> print x
 
--expr = factor ('+' factor | '-' factor)*
expr :: Parser Float
expr = do
    l <- factor
    rs <- many ((do
                    char '+'
                    n <- factor
                    return $ (+) n
                    )
                <|>
                (do
                    char '-'
                    n <- factor
                    return $ flip (-) n
                ))
    return $ foldr ($) l rs
 
--factor = term ('*' term | '/' term)*
factor :: Parser Float
factor = do
    l <- term
    rs <- many ((do
                    char '*'
                    n <- term
                    return $ (*) n
                    )
                <|>
                (do
                    char '/'
                    n <- term
                    return $ flip (/) n
                ))
    return $ foldr ($) l rs
 
--term = number | '(' expr ')'
term :: Parser Float
term = do
    (do
        n <- many1 digit
        return $ read n
        )
    <|>
    (do
        char '('
        n <- expr
        char ')'
        return n
        )
 
main = do
    run expr "1+2*3/6-(12*12-8/4)"

これをApplicative Functorを使って書き直したのが以下ののものです。
kazu-yamamotoさんのエントリーを参考にして書きました。ちなみにParserがApplicativeのインスタンスになったのはParsec3以降なので、インポートしているモジュールが上とは違います。(Text.ParserCombinators.Parsec.*がParsec2、Text.Parsec.*がParsec3)

import Control.Applicative hiding ((<|>), many)
import Text.Parsec
import Text.Parsec.String
 
run :: Show a => Parser a -> String -> IO ()
run p input =
    case (parse p "" input) of
            Left err -> do
                putStr "parse error at "
                print err
            Right x  -> print x
 
expr :: Parser Float
expr = foldr ($) <$> factor <*> many (add <|> sub)
    where add = ((+) <$> (char '+' *> factor))
          sub = (flip (-) <$> (char '-' *> factor))
 
factor :: Parser Float
factor = foldr ($) <$> term <*> many (mul <|> div)
    where mul = ((*) <$> (char '*' *> factor))  
          div =  (flip (/) <$> (char '/' *> factor))
 
term :: Parser Float
term = number <|> paren
    where number = (read <$> many1 digit )
          paren =  (char '(' *> expr <* char ')')
 
main = do
    run expr "1+2*3/6-(12*12-8/4)"

たしかにコンパクトで可読性が上がってますね。このコードはテスト用に適当に書いたコードなのでパースしながら評価もしていて、けっこう汚いですが、ちゃんとしたパーサをつくるならASTを構築して返し、評価は別に行うのが良いと思います。

Filed under: Haskell No Comments
137月/113

HaskellでBMPファイルを読み込む

Haskellでバイナリファイルを扱うときは、Data.Binaryモジュールを用いるのが定石みたいです。この前pingをHaskellで書いたときはそれを知らず、ICMPヘッダをpeekとかpokeでガリガリ読み書きしてました…

というわけで友達が書こうとしているBMPファイルローダを、ヘッダ部分の読み出しだけ書いてみました。バイナリファイルの読み出しには、Data.Binary.GetにあるGetモナドを使用します。Getモナドは内部で入力のByteStringを持ち回してくれて、使用する側が明示的にByteStringに触らなくても良いようになっているみたいです。

Getモナドを構築したら、後はrunGetでByteStringを読み込ませ、パーサを走らせます。直感的で使いやすくて良いですね!書いててなんとなくParsecを思い出しました。まあData.Binary.Getもある意味パーサなわけですからね。

import qualified Data.ByteString.Lazy as L
import Data.Binary
import Data.Binary.Get
import Data.Word
 
data BitmapFileHeader = BitmapFileHeader {
    bfType      ::  Word16,
    bfSize      ::  Word32,
    bfOffBits   ::  Word32
} deriving (Show, Eq)
 
data BitmapInfoHeader = BitmapInfoHeader {
    biSize      ::  Word32,
    biWidth     ::  Word32,
    biHeight    ::  Word32,
    biBitCount  ::  Word16
} deriving (Show, Eq)
 
readBmpFileHeader :: Get BitmapFileHeader
readBmpFileHeader = do
    t <- getWord16le
    s <- getWord32le
    getWord32le
    ob <- getWord32le
    return BitmapFileHeader {bfType = t, bfSize = s, bfOffBits = ob}
 
readBmpInfoHeader :: Get BitmapInfoHeader
readBmpInfoHeader = do
    s <- getWord32le
    w <- getWord32le
    h <- getWord32le
    getWord16le
    bc <- getWord16le
    getBytes 24
    return BitmapInfoHeader {biSize = s, biWidth = w, biHeight = h, biBitCount = bc}
 
readBmpHeader :: Get (BitmapFileHeader, BitmapInfoHeader)
readBmpHeader = do
    f <- readBmpFileHeader
    i <- readBmpInfoHeader
 
    return (f, i)
 
main = do
    contents <- L.readFile "test.bmp"
    print $ runGet readBmpHeader contents

追記@2011.07.15

このソースコードでは不要な値を読み飛ばすのにgetWord16leなどを使ってますが、skipの方が良いのでは、という意見をもらいました。たしかにそっちの方がわかりやすい…っていうかskipを知らなかった。

Filed under: Haskell 3 Comments
77月/110

LaTeXの相互参照がおかしくなるとき

最近LaTeXで文章を書いていてはまったのでメモ。
LaTeXで次のように図を貼り、

\begin{figure}[htbp]
    \centering
    \includegraphics{some_figure.pdf}
    \caption{図のタイトル}
    \label{labelOfFigure}
\end{figure}

文章中で次のように参照を設定すると、その位置に図表番号が挿入されるはずです。

\ref{labelOfFigure}

ただしなぜか図表番号が章・節の番号となることがあります。その場合は、

\begin{figure}[htbp]
    \centering
    \includegraphics{some_figure.pdf}
    \label{labelOfFigure}
    \caption{図のタイトル}
\end{figure}

というように、labelがcaptionの書かれているからかもしれません。labelはcaptionの直後でないといけないみたいです。

Filed under: note No Comments
77月/110

HaskellでSQLiteを使う

HaskellでDBを操作するならHDBCを使うのが定石だとは思うんですが、やりたいことが簡単でかつSQLiteで十分だったので、Database.SQLiteを使ってみました。

使い方

SQL文を発行する

最初にsqlite3本体と、cabalでsqliteパッケージをインストールする必要があります。

使い方は簡単で、openConnectionで接続で開き、execStatementでSQL文を発行して、結果を取得します。execStatementの返値は多相で、Either String [[Row String]] 、Either String [[Row Value]]、Either String [[Row Value]]のいずれかを選べます。

Either String [[Row String]] ならLeftがエラーで、Rightなら列名と値のタプルのリストのリストのリストが返ってきます。詳しく書くと、Row Stringは[(String, String)]と同値で、列名と値のタプルのリストで、1行を表します。そして[Row String]は複数行をあらわします。そして[[Row String]]なんですが、これは"select * from urls;select * from profiles;"みたいな感じで複数のSQL文をまとめて実行したときに、各SQLの結果がリストにまとめられるみたいです。

module Main where
 
import Database.SQLite
 
printResult ::  Either String [[Row String]] -> IO ()
printResult result = 
    case result of
        Left error      ->  putStrLn error
        Right result    ->  print result
 
main = do
    h <- openConnection "test.db"
    result <- execStatement h "select * from urls;"
    printResult result
    closeConnection h

また、返値をEither String [[Row Value]]という型にすると、以下のようにValueという代数的データ型が定義されていて、元々のテーブルの各列の型のまま結果を受け取れます。

data Value
  = Double Double
  | Int    Int64
  | Text   String
  | Blob   ByteString
  | Null

パラメータ付きのSQL文を発行する

次にパラメータ付きのSQL文を実行する場合ですが、execParamStatement関数を使います。SQL文中でプレースホルダを:placeholderのように書き、execParamStatementの引数でプレースホルダと値のタプルのリストを与えます。

result <- execParamStatement h "select * from urls where id = :col_id;" [(":col_id", Int 1)]

返値はexecStatementと同様です。また、これらの関数の返値を捨てるバージョンexecStatement_やexecParamStatement_も存在します。他にも行を挿入するにはinsertRowや、テーブルを作成するならdefineTableという関数を使えばよいみたいです。また、コールバック関数を自分で定義することもできます。

参考

hackageDB::Database.SQLite

Filed under: Haskell No Comments
115月/110

LuaBindで静的メソッドをバインドする

LuaBindのドキュメンテーションには、

class_<foo>("foo")
    .def(constructor<>())
    .scope
    [
        class_<inner>("nested"),
        def("f", &f)
    ];

のようにバインドすると、fをfooの静的メソッドとしてバインドできるよ、と書いてありますが、実際にLua側からどのように使うのか明記されていません。まず、内部クラスが必要なければ、以下のようにscope定義がけ書けば良いようです。

class_<foo>("foo")
    .def(constructor<>())
    .scope
    [
        def("f", &f)
    ];

そしてLua側からこの静的メソッドを呼ぶときですが、

foo.f()

とすれば良いようです。普通のインスタンスメソッドの呼び出しは

hoge = foo()
hoge:g()

のようにコロンなので、C++が頭にあると、ちょっと混同しますね。

参考

Filed under: C++, programming No Comments
85月/110

LuaBindをMinGW上でbjamを使わずにビルドする

Windows 7 + MinGW + MSYSという環境で、どうしてもマニュアルに書いてあるbjamを使うデフォルトの方法でuaBindがビルドできなかったので(っていうかbjam自体何かおかしい)、Eclipseでライブラリをビルドしてみました。
スタティックライブラリとして作りましたが、シェアードの場合も(たぶん)同様にできるはず。

  1. MinGW+MSYS+Eclipse CDT+Luaインストール済みの環境が前提です
  2. LuaBindの公式サイトからソースコードのアーカイブを落とし、解凍するとINSTALL 、Jamroot 、LICENSE、doc、examples 、luabind 、src、 testというファイルとディレクトリが生成されるはずです。
  3. luabindの中にはヘッダファイルが入っているので、ディレクトリごと/mingw/includeにコピーします。
  4. srcの中にライブラリのソースが入っているので、これをEclipseでビルドします。
  5. EclipseでC++ Project > Static Library > Empty Projectを、luabindという名前で作成します。Debugビルドのチェックは外しておきます。
  6. このプロジェクトに、D&Dでsrc以下の全てのcppファイルを追加してから、プロジェクトをビルドします。
  7. ビルドが成功すれば、プロジェクトのディレクトリ/Releaseにlibluablind.aというライブラリファイルが生成されるので、これを/mingw/libにコピーします。
  8. 完成!
Filed under: 未分類 No Comments
85月/110

MinGW+MSYSの環境でLuaをビルド

最近MinGWで開発環境を構築しているので、自分用のメモとして書いておきます。まずはLuaのビルドについて。

公式サイトのダウンロードページか(http://www.lua.org/download.html)からソースコードのアーカイブを落として、解凍します。
Makefileの

# Where to install. The installation starts in the src and doc directories,
# so take care if INSTALL_TOP is not an absolute path.
INSTALL_TOP= /usr/local

# Where to install. The installation starts in the src and doc directories,
# so take care if INSTALL_TOP is not an absolute path.
INSTALL_TOP= /mingw

に書き換え、シェルで

make mingw
make install

と実行します。以上で/mingw/includeと/mingw/libにヘッダファイルとライブラリがインストールされます。

Filed under: programming No Comments
174月/110

SVNリポジトリが停止中

サーバメンテにより、2chViewerやNicovideoUtilなどを公開していたSVNリポジトリが現在停止しています。
近日中に復旧する予定ではありますが、ご迷惑をおかけします。

Filed under: server No Comments
124月/110

F#でMaybeモナド

最近F#を使っていなかったのでちょっと書いてみました。Computation Expression使ってます。

open System
 
type 'A Maybe =
    | Just of 'A
    | Nothing
 
type MaybeBuilder() = class
    member self.Bind(ex, f) =
        match ex with
            | Just x    -> f x
            | Nothing   -> Nothing
 
    member self.Return(x) =
        Just x
 
    member self.Delay(f) =
        f ()
end
 
let maybe = new MaybeBuilder ();;
 
let alist = [ ("A","B"); ("B","C"); ("C","D")]
 
let rec lookup list key =
    match list with
        | []            -> Nothing
        | (k, v) :: xs  -> if k = key then Just v else lookup xs key
 
let search = maybe {
    let! x = lookup alist "Bob"
    let! y = lookup alist x
    let! z = lookup alist y
    return z
}
 
search |> printfn "%A"
 
Console.ReadLine () |> ignore
Filed under: F#, programming No Comments
114月/110

Mac OSXでGtk2hsを使う

Mac OS 10.6でGtk2Hsを使ったときのメモ。HaskellWikiに書いてある方法だとgtk2hsをmakeするときに失敗したので、代替案を考えました。

  1. まずはsudo port install gtk +universalでgtkをインストールします。universalを指定せずにインストールした場合は、uninstallしてから+universalしてインストールし直す必要があります。
  2. 次に
    cabal update
    cabal install gtk2hs-buildtools
    cabal install gtk

    でgtk2hsをインストールします。ここでgtk2hsC2hsが見つからない、みたいなエラーが出る場合は、~/.cabal/binにパスが通っていない可能性が高いです。~/.bash_profileに

    export PATH=~/.cabal/bin:$PATH

    と追記しましょう

  3. そしてテスト用に
    import Graphics.UI.Gtk
     
    main :: IO ()
    main = do
      initGUI
      window <- windowNew
      widgetShowAll window
      mainGUI

    と書いたファイルをmain.hsとして保存します。

  4. これを

    ghc --make main.hs

    でコンパイルしますが、私の環境では

    Linking main ...
    Undefined symbols:
      "_iconv_open", referenced from:
          _hs_iconv_open in libHSbase-4.2.0.2.a(iconv.o)
         (maybe you meant: _hs_iconv_open)
      "_iconv", referenced from:
          _hs_iconv in libHSbase-4.2.0.2.a(iconv.o)
         (maybe you meant: _hs_iconv_open, _hs_iconv , _hs_iconv_close )
      "_iconv_close", referenced from:
          _hs_iconv_close in libHSbase-4.2.0.2.a(iconv.o)
         (maybe you meant: _hs_iconv_close)
    ld: symbol(s) not found
    collect2: ld returned 1 exit status

    のようなリンクエラーを吐きました。このようなときは、

    ghc --make main.hs -L/usr/lib

    とすると上手くいきました。もちろんlibiconvを+universalでインストールしていないといけません。

  5. これでmainを起動するとウィンドウが開くはずです。X11なので、ちょっとデザインがださいです…OSXネイティブのAquaなUIにするためには、GTK-OSXをインストールしてGtk2Hsをビルドし直す必要がありそうです。これの詳しい方法はHaskellWikiに書いてあります。