e-mon

備忘録

HaskellでSchemeを書く#3

評価器の作成

今回から評価器の作成に移る。

まず最初に引っかかるのが以下。

instance Show LispVal where show = showVal

Show型クラスの中に、LispValを受け取ったときの動作を加えますよ、という意味合いらしいのだけど、どうやらこのあたりで型クラスについてさらりとでも触れたほうが良いのではないかと思う。

Haskellにおける型クラスとは、データ型に対する振る舞いの集合、のようだ。ある型クラスのインスタンスに属していれば、型クラス特有の関数(クラスメソッド)を利用出来る。また、そのメソッドの振る舞いはデータ型ごとに指定出来る、という理解。

とりあえず試す。
何か引数を2つとり、文字列を返すメソッドを持つ、型クラスをつくろう。

Prelude> class Hoge a where (<?>) :: Show a => a -> a -> String; a<?>b = "null"
Prelude> :t (<?>)
(<?>) :: (Show a,Hoge a) => a -> a -> String
Prelude> 

メソッドの宣言部分(シグネチャというらしい。)は必ず必要で、またデフォルト動作の定義は任意。今回はデフォルト動作は"null"を返すことにしておいた。
そして、今現在は、型クラスを抽象的に宣言しているだけなので、実際の動作を記述していく。

instance Hoge String where
x:xs <?> b = x:b 

こんな風に宣言したところでエラー。Stringtype String = [Char]と宣言されているからで、[]は代数的データ型(!!)なので、[] Charみたいに解釈されるけども、Charは型変数じゃないから受け付けないよ、ということらしい。(参考'Why can I not make String an instance of a typeclass?' - Stack Overflow)

これの対策は、newtype newString = newString Stringみたいにラッピングする型を宣言することで回避出来る。newtypeは型クラスのインスタンスを新しく宣言し直せるらしい。ちなみに、typeはシノニム(ただのエイリアス?)としての意味しかないので、この2つは似て非なるもの。

Prelude> instance Hoge Integer where a <?> b = show a ++ " ? " ++ show b
Prelude> instance Hoge Char
Prelude> 1<?>2
"1 ? 2"
Prelude> 'a'<?>'b'
"null"

ということで、型クラスについてちょっとだけ理解した。

次は例外とかのハンドリング!

HaskellでSchemeを書く#2

構文解析その2

前回は、基本的な関数の表現などをまとめた。 今回も続けて構文解析について進めていく。 既に10時間は経過している気がするけど、48時間で終わるのか!

何はともあれ、まずは以下の定義から。

data LispVal = Atom String
             | List [LispVal]
             | DottedList [LispVal] LispVal
             | Number Integer
             | String String
             | Bool Bool

これは代数的データ型と呼ばれるものらしく、恐らくEither型も代数的データ型なのかな?|で接続された、例えばAtomみたいな部分がコンストラクタのタグ名で、その後に続いているのがそのコンストラクタに格納可能であるデータ型、ということだった。

代数的データ型とはなんぞや?ということでwikiで調べてみると、以下のような素晴らしい例が出てきた。

Prelude> data Node = Leaf Integer | Branch Node Node deriving (Show)
Prelude> Leaf 1
Leaf 1
Prelude> Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 3) (Leaf 4))
Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 3) (Leaf 4))
Prelude> 

なんかBNF記法的な何かだと理解した。いろんな表現の集合。いずれかのコンストラクタで表されているもの。

問題は、それぞれが何を意味しているか。NumberStringBoolはいいとして、問題はそれ以外の3つだ。

Schemeでの表現は、全てS式と呼ばれるもので、そのS式を構成しているのが、リストと、リスト以外のモノを指すアトム(参考:Schemeのお勉強 (S式と評価,式と文,リテラル))。Listは、Haskellでのデータ型表現が[LispVal]とLispValのリストになっているので、 そういうことなんだろう。

Schemeでは、リストとはcons(construct語源?)セルによって構成されるらしい。 (wiki:Cons)

(1 . 2)が最小単位のコンスセルで、ドット対の S式、ということだ・・・また知らない単語が出てきてしまったので調べると、まあ単純にこの形式のデータのことをそう呼ぶらしい。コンスセルでドット対じゃあないものが存在するということか?と思ったけどそういうことでもないらしい。じゃあコンスセルでいいやん。コンスセルの表現方法としてLispではドット対という、と。まあそういうことらしい。

ふと疑問に思ったのが、このLispValをリストとして持つと、リストの中の型がコンストラクタによってぐちゃぐちゃになっちゃうんじゃ?と思ったんだけど、リストには'純リスト'と'純でないリスト'というのがあるらしく、純リストは、並べられたデータの型を制限しないリストのことらしい。凄い。

そんなこんなで、次がDottedList [LispVal] LispValなんだけども、これってDottedList List LispValという書き方じゃダメなんだろうか。ダメだった。type constructor でも classでもないからダメよ、というふうに見える。

Prelude> data LispVal = Atom String | List [LispVal] | DottedList List LispVal

<interactive>:118:58:
    Not in scope: type constructor or class `List'
    A data constructor of that name is in scope; did you mean -XDataKinds?

この代数的データ型にはそれぞれ呼び方があるらしく、data 型コンストラクタ(type constuctor) = 値コンストラクタ(data constructor) データ型という並びになっているらしい(参考:Haskellのコンストラクタとデータ型)。値コンストラクタはさだめられたデータ型を返す関数なんだって。

DottedListは、ドット対で表現されたリストのことかな?だから、Listのほうは、(1 2 3 4)みたいなやつのことか。

残るはAtomだけども、こいつは何を指しているんだろう。式そのものを一時的に文字列で受け取るためのものだろうか。

文字列をパース

少し疑問は残ったものの次へ。次は、文字列として表現されるものをパースする。ここも難所だった・・。

parseString :: Parser LispVal
parseString = do char '"'
                 x <- many (noneOf "\"")
                 char '"'
                 return $ String x

2行目のdoは各行を適切に>>>>=で接続しますよーってなことらしい。そんでcharは、

Prelude Text.ParserCombinators.Parsec> :t char
char
  :: Text.Parsec.Prim.Stream s m Char =>
     Char -> Text.Parsec.Prim.ParsecT s u m Char

こんな風に定義されてて、与えられたChar型の文字とマッチしたらポインタを一個進めて文字列を次に渡す、とかなのかなぁ。この辺、関数の定義がわからない分具体的になにしてるのかわからん。manyは次のnoneOfと併せて、"が出てこない間の文字列にマッチさせる。最終的にreturnするのだけれど、ここでreturnが必要な理由は、manyが返してくるデータ型はStringなので、この関数のデータ型であるParse LispValとしてまとめあげるためにreturnしているらしい。まだ深淵に触れたくないのでさらっと見てみると、

class Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  return :: a -> m a

あるaをモナドとして返してくれる関数?らしい。LispValはParserモナドじゃないから、全体としてParserモナドのアクションになるようにしましょうね、ということかしら。

Atomのパース

ついに出ました、謎のAtom

parseAtom :: Parser LispVal
parseAtom = do first <- letter <|> symbol
               rest <- many (letter <|> digit <|> symbol)
               let atom = first:rest
               return $ case atom of
                          "#t" -> Bool True
                          "#f" -> Bool False
                          _    -> Atom atom

<|>が目新しいくらい?letterは大文字か小文字の英字をパースしてくれるやつで、これは1文字目が英字もしくはsymbolに指定した記号始まりで、その後に続く文字列が、英字、記号、数字のいずれかであることを判定、つまりはアトムであるかを見ているわけだな?で、真偽値だったらBoolコンストラクタTrue or False として格納してそれ以外はAtomとして格納すると。だいぶ読めるようになってきたぞ?

数字のパーサ

数字のパーサは見た目がとてもシンプル。ただやってることは難しい。

parseNumber :: Parser LispVal
parseNumber = liftM (Number . read) $ many1 digit

これは(Number . read) という、String -> LispValというふうに合成された関数を、many1 digit関数から返される値に適用したいんだけども、many1 digitParse Stringという、Monad Stringな値を持ってしまっているので、そのままでは適用できないと。となると、String -> LispValの関数を、Monad String -> Monad LispValという関数にしたい・・・・・!ということでそれを担うのがliftMということですね・・。実際に、

Prelude Control.Monad> :t (Number . read)
(Number . read) :: String -> LispVal
Prelude Control.Monad> :t liftM (Number . read)
liftM(Number . read) :: Monad m => m String -> m LispVal

こんな感じになる。

あとはこれらのパーサを組み合わせてひとまずは完了!!

HaskellでSchemeを書く#1

HakellでSchemeを書く

Haskellを覚えるのに、以下の48時間でSchemeを書こう、に挑戦することにした。 HaskellSchemeも全く知らないところからのスタートでかなり無謀感漂う。

参考元:48時間でSchemeを書こう

構文解析

構文解析では、PerSecライブラリでパーサーを書く。

symbol :: Parser Char
symbol = oneOf "!#$%&|*+-/:<=>?@^_~"

この1つ前の1.最初の一歩の章から考えるに、これは、symbol という名の関数を Parser Char という型として宣言、2行目の代入式(束縛する、というらしい)の右辺値で定義される動作の結果の値を返す関数となる、という理解。

関数の宣言は、

関数名 :: 型シグネチャ
関数名 引数 = 式の定義

となる。

そして、Parserとはモナドなるものらしい。進めていくうちに理解出来るハズ。

readExpr :: String -> String
readExpr input = case parse symbol "lisp" input of
    Left err -> "No match: " ++ show err
    Right val -> "Found value"

で、symbol というパーサで文字列をパースして結果を得るための関数が、これ。

readExpr という関数は、String 型を引数で受けて、Stringで返すんだよ、という宣言をしている。

これは複数の引数もこの形式で書くらしく、textFunction :: String -> String -> Stringと書くと、Stringを2つ引数として受け取り、Stringを返す関数として宣言されて、function "abc" "def"みたいな書き方が出来るようになる。

カリー化というものらしく、要は、引数->(引数->返り値)のようになっていて、一つ目の引数を受け取った後、(引数->返り値)という型宣言を持つ関数を返す、という風に解釈されるらしい。

higher order functions - Learn Your Haskell for Grate Goodに、ものすごいわかりやすい例があった。

ghci> let multTwoWithNine = multThree 9  
ghci> multTwoWithNine 2 3  
54  
ghci> let multWithEighteen = multTwoWithNine 2  
ghci> multWithEighteen 10  
180  

で、だいぶ寄り道したけども、readExpr input = case parse symbol "lisp" input of~~という部分は、以下の構文で表されてる。これは単に、inputっていうStringの引数を受け取り、parse symbol "lisp" inputというparse関数を実行するということで、parse関数は多分、parse :: Parser某型関数 -> String -> String -> Eitherなる型という宣言になるのではないか、ということで確認してみた。

ghci上では、:m module名という感じでモジュールのインポートが行えるらしい、ので、以下を実行。

Prelude> :m Text.ParserCombinators.Parsec
Prelude Text.ParserCombinators.Parsec> :t parse
parse
  :: Text.Parsec.Prim.Stream s Data.Functor.Identity.Identity t =>
     Text.Parsec.Prim.Parsec s () a
     -> SourceName -> s -> Either ParseError a

type => aっていう書き方は、以降登場するaなる文字は、typeという型なんですよーという宣言ならしい、けど、丁度その部分が何書いてるかよくわからん。 多分、Text.Parsec.Prim.Parsec sとして定義される関数の値の返り値の型をaとして、SourceNameと、sを引数に、Either型を返している気がする。宿題。

Eitherは、 data Either a b = Left a | Right b deriving (Eq, Ord, Read, Show) のように宣言されていて、deriving修飾子によってある型クラスのインスタンスである、ということを指定するらしい。 EqとかOrdインスタンスとして宣言されているのは、比較とかを行うため。

というのも、以下のように、==とか、>とかは、EqOrdインスタンスの引数を受け取る関数として定義されているから。引数と引数の間に置ける関数を 中置関数というらしく、==+などが該当する。これらは、通常の関数呼び出しのように引数の前におけて、(==) 100 200みたいなことが出来る。

また、中置関数も前置出来て、その際は128 \max` 256`のように書くことが出来る。(あんまりいい例じゃないけど。)

Prelude> :t (==)
(==) :: Eq a => a -> a -> Bool
Prelude> :t (>)
(>) :: Ord a => a -> a -> Bool

Eitherは名前の通り、Left or Rightのどちらかが格納されているデータ型なんだな、という理解でとりあえず進む。

そんな感じでStringを受けてパースしてStringを返す関数が実装されたので、IOモナドなるものによって定義されているmain関数?に 受け渡しをして、完了

だいぶ寄り道してしまった感あるけど、全然理解出来てない感じがやばい。

Haskell事始め#1

Pascalのプログラミング文法を学ぶ機会があり、丁度良いのでこれを機に何か触れたことのない言語でPascalコンパイラを作成しようと、 Haskellに手をだす事に相成りました。

ということで、HaskellPascalコンパイラを作成することを最終目標に、まずはHaskellチュートリアルを進めて行きたいと思います。

環境構築

環境:OS X 10.9.3

GHCコンパイラを使おうと思い、おもむろにbrew install ghcすると、haskell-platformをインストールしたほうがいいよ、というようなメッセージが出たので(確か)、続けて、

brew isntall haskell-platform

多分、後者だけで問題無い

$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> putStrLn "Hello World!"
Hello World!
Prelude> 

うん、動いてる。問題無い。

続けて、VimHaskellを書く環境を整えます。 .vimrcに、とりあえず以下の3つのプラグインを追加

" for Haskell {{{
"便利なghcmodなるコマンドをvimから便利に使うためのプラグイン
NeoBundle 'eagletmt/ghcmod-vim'
"補完用
NeoBundle 'eagletmt/neco-ghc'
"インデントを賢くしてくれる
NeoBundle 'kana/vim-filetype-haskell'
"}}}

Haskellのパッケージシステムcabalghc-modはインストールできるらしいので、

$ cabal update
$ cabal install ghc-mod
$ echo 'export PATH=$PATH:~/.cabal/bin' >> ~/.bash_profile
$ source ~/.bash_profile

こんなかんじで導入してパスを通す。

で、とりあえずは完了。

この作業中、neco-ghsのエラーが発生

module Main where
import System.Enviroment

System.Enviromentはミスタイプで、こんなモジュールは存在しないんだけど、 この状態で他の行で補完を発生させると、以下のようなエラーが出る。

Error occured in source's gather_candidates()!
function neocomplete#handler#_do_auto_complete..neocomplete#complete#_get_results..neocomplete#complete#_set_results_words..199..necoghc#get
_complete_words..necoghc#browse..<SNR>176_ghc_mod_caching_browse..<SNR>176_ghc_mod, 行 6
Vim(if):E684: リストのインデックスが範囲外です: 0
Source name is ghc

こういう時、プラグインのソース読めないのは本当に不便だなーと思いつつ、ソースを見てみるけどやっぱりわからない。

今回は、以下のようなHello,Worldなものを書いて終了。次回から本格始動予定。

module Main where
import System.Environment

main :: IO()
main = do
  args <- getArgs
  putStrLn ("Hello , " ++ args !! 0)
$ ghc hello.hs
$ ./hello.hs e-mon
Hello,e-mon
$

node.js用認証モジュール Passport(日本語版:非公式)を公開

あるwebアプリケーション作成のため、passportのドキュメント翻訳作業を行いました。

OAuthが何たるものかよくわからないままTwitterAPIを利用していたりしたので、翻訳作業を通じて多少理解が深まったかなと思います。ちょっと曖昧な部分も多いため、誤訳や誤植等ありましたらissue投げてもらえないかなぁと思います。

あとは雑記。

Passportの翻訳をしていて、只の翻訳で終わっては意味がないので何かしらのサービスに対するpassport-*を作ってみたかったけども、有名どころはすべてモジュールが作成されていたので少し残念。