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
こんな風に宣言したところでエラー。String
はtype 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記法的な何かだと理解した。いろんな表現の集合。いずれかのコンストラクタで表されているもの。
問題は、それぞれが何を意味しているか。Number
やString
、Bool
はいいとして、問題はそれ以外の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 digit
はParse 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を書こう、に挑戦することにした。 HaskellもSchemeも全く知らないところからのスタートでかなり無謀感漂う。
参考元:48時間でSchemeを書こう
構文解析
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
のインスタンスとして宣言されているのは、比較とかを行うため。
というのも、以下のように、==
とか、>
とかは、Eq
やOrd
インスタンスの引数を受け取る関数として定義されているから。引数と引数の間に置ける関数を
中置関数というらしく、==
や+
などが該当する。これらは、通常の関数呼び出しのように引数の前におけて、(==) 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に手をだす事に相成りました。
ということで、HaskellでPascalのコンパイラを作成することを最終目標に、まずは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>
うん、動いてる。問題無い。
続けて、VimでHaskellを書く環境を整えます。
.vimrc
に、とりあえず以下の3つのプラグインを追加
" for Haskell {{{ "便利なghcmodなるコマンドをvimから便利に使うためのプラグイン NeoBundle 'eagletmt/ghcmod-vim' "補完用 NeoBundle 'eagletmt/neco-ghc' "インデントを賢くしてくれる NeoBundle 'kana/vim-filetype-haskell' "}}}
Haskellのパッケージシステムcabal
でghc-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のドキュメント翻訳作業を行いました。
- 元のサイト:Passport
- 日本語訳版:Passport 日本語版
OAuthが何たるものかよくわからないままTwitterのAPIを利用していたりしたので、翻訳作業を通じて多少理解が深まったかなと思います。ちょっと曖昧な部分も多いため、誤訳や誤植等ありましたらissue投げてもらえないかなぁと思います。
あとは雑記。
Passportの翻訳をしていて、只の翻訳で終わっては意味がないので何かしらのサービスに対するpassport-*を作ってみたかったけども、有名どころはすべてモジュールが作成されていたので少し残念。