<   2011年 12月 ( 40 )   > この月の画像一覧

48時間でSchemeを書こう/Scheme関数の定義

『48時間でSchemeを書こう』チュートリアルのチュートリアル記事もいよいよ大詰めだ。『Scheme関数の定義48時間でSchemeを書こう/Scheme関数の定義』でユーザー定義の関数を使えるようになる。

これから何が行われるのかを概観してみよう。

まずは、LispVal 型のデータに PrimitiveFunc と Func という2つのデータコンストラクタが追加される。つぎにそれらのデータを文字列にするための show 関数を定義する。

つぎに関数の評価をする関数 apply を関数名で検索していたのを LispVal で実行するように変更する。そうして変更された apply でユーザ定義関数のボディを評価できるようにする。

最後に labmda と define を評価器の中でサポートするように編集する。

これで Scheme インタプリタの完成だ。完成したプログラムは listing9.hs のようになる。それでは早速試してみよう。今度はコンパイルしてhscheme.exe という実行ファイルを作る。

C:\Users\******\Documents\>ghc -XExistentialQuantification --make -o hscheme listing9.hs

C:\Users\******\Documents\>hscheme
Lisp>>> (define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))
(lambda ("n") ...)
Lisp>>> (fact 5)
120

それでは、一つ一つのプログラムを追いかけてみよう。最初は LispVal に追加されたデータコンストラクタだ。

   | PrimitiveFunc ([LispVal] -> ThrowsError LispVal)
   | Func {params :: [String], vararg :: (Maybe String),
            body :: [LispVal], closure :: Env}

primitiveFunc はあらかじめ定義されている関数用で、データコンストラクタのパラメータに引き数のリストをとる。Func はユーザ定義関数用で、次の4つの情報をコンテナのレコード型として保持している。これは、Haskell のレコード型の例になっている。

  1. 関数のボディの中で束縛されるような、パラメーターの名前。
  2. 可変長の引数のリストが使われているかどうか。使われているなら、束縛されている変数の名前
  3. 関数のボディ。リストとして表現されている。
  4. 関数が作られる環境
次にプログラムされているのが、これらのデータ型を文字列にするための show 関数だが普通のプログラムなので省略する。

次は LispVal を評価する apply を改造して、関数名の文字列型の代わりにそれに相当する LispVal 型を引き数に取るようにする。

apply :: LispVal -> [LispVal] -> IOThrowsError LispVal
apply (PrimitiveFunc func) args = liftThrows $ func args

Func の場合はユーザ定義の関数を処理するので少しややこしくなる。

apply (Func params varargs body closure) args =
    if num params /= num args && varargs == Nothing
       then throwError $ NumArgs (num params) args
       else (liftIO $ bindVars closure $ zip params args) >>= bindVarArgs varargs >>= evalBody
    where remainingArgs = drop (length params) args
          num = toInteger . length
          evalBody env = liftM last $ mapM (eval env) body
          bindVarArgs arg env = case arg of
              Just argName -> liftIO $ bindVars env [(argName, List $ remainingArgs)]
              Nothing -> return env

if 文でやっているのは引き数の数のチェックを行い、定義のパラメータ数とマッチしていなければエラー例外を発生させ、マッチしていれば、定義関数のボディの部分を実行することだ。ユーザ定義関数の実行はまず、 zip params args で仮引数と実引数のペアを作り、それを関数のクロージャー(closure) と一緒にリストにして >>= で次の処理に渡す。次の処理は 仮引数に実際に実引数の値を代入した環境のリストを作り、>>= で evalBody に渡す。

evalBody は body の環境リストを次々に評価して、最後の値を IOThrowsError モナド値にして戻す。

where で定義された補助関数のうち remainingArgs は実引数のうち仮引数の数を超えた部分を取り出す。num は引き数の数を整数にする。bindVarArgs は仮引数に実引数の値を代入した新しい環境(変数のリスト)を作る。

これで既定の関数や、ユーザ定義関数を実行するしくみが作れたが、既定の関数もユーザ定義関数と同じように扱うため、Scheme プログラムの最初で、既定の関数を新たに評価できる形で環境に設定する必要ができてくる。

primitiveBindings :: IO Env
primitiveBindings = nullEnv >>= (flip bindVars $ map makePrimitiveFunc primitives)
    where makePrimitiveFunc (var, func) = (var, PrimitiveFunc func)

さらにコードを1回だけ実行する runOne とコンソールで繰り返し実行する runRepel の修正を行い、関数を環境に追加する Func を補助する関数 makeFunc, makeNormalFunc, makeVarargs を記述する。

最後に評価器 eval を define と lambda が使えるように変更し、Scheme インタプリタ作成の作業は終了だ。

これでチュートリアル『48時間でSchemeを書こう』のチュートリアル記事は終了する。『48時間でSchemeを書こう』の内容は盛りだくさんで、Parsec の使い方に始まって、代数的データ型による多形データ型を統一的に扱うやり方、プリミティブな関数をテーブルを使って管理することで追加の拡張を容易にする方法、エラー処理モナドの使い方、DataIORef による代入可能な変数の導入の仕方、エラー処理モナドやMaybe モナドやIOモナドなど複数のモナドからなる複合モナドの扱い方など実践的なテクニックがてんこ盛りだった。

管理人の知識では?な所が多く、チュートリアルのチュートリアルにもならなかった所が多かったかもしれない。しかし、Haskell のプログラムを作るためには何が必要なのかという概観は得られたと思う。

この作業をやっていて思ったのは、プログラムは頭で分かるものではなく、手で考えるものだということだ。本文の説明のわかりづらい所があったとき、ghci でスニペットを作って動かしてみるとすっと頭に入るのを何回も経験した。Real World Haskell の記事も、極力 ghci で確認できるように書かれているような気がする。

プログラムは手で学習する方がやさしい。
[PR]
by tnomura9 | 2011-12-30 17:17 | Haskell | Comments(0)

48時間でSchemeを書こう/変数と代入 (4)

48時間でSchemeを書こう/変数と代入』のエラー処理の仕組みが分かったのでいよいよ変数と代入に関連する関数を見ることができる。この章で記述されているそれらの関数を概観すると次のようになる。
isBound
変数名が変数リスとに登録されているかどうかを判断する関数
getVar
変数の現在の値をとりだす関数
setVar
変数に値をセットする関数
defineVar
Scheme の define を実行する関数
bindVars
ユーザー定義の関数の実効に関する関数?
名前を見るとなんとなく関数の機能がわかる。

それでは、まず、isBound から眺めてみよう。

isBound :: Env -> String -> IO Bool
isBound envRef var = readIORef envRef >>= return . maybe False (const True) . lookup var

isBound の型をみると、Env型とString型の引数をとり、IO Bool 型の戻り値を返す。戻り値が IO a 型だから、この間数は IO モナド型の関数だ。

readIORef envRef で環境の変数テーブルを取り出し、それを lookup var に渡している。lookup は環境(変数テーブル)に変数名 var があるかどうかを検索し結果を Maybe モナド値として maybe 関数に渡す。maybe は lookup から渡された値が Nothing なら True を返し、Just x なら x に関数 (const True) を関数適用させた値を返す。この場合は const True だから、True が返る。最後に return でこの Bool 値を IO で包んで最終的な戻り値にしている。

関数 maybe の型は次のようになる。

Prelude> :t maybe
maybe :: b -> (a -> b) -> Maybe a -> b

第3引き数が、Nothing のとき第1引き数を返し、Just x の時は、x に第2引き数の関数を関数適用する。実行例は次のようになる。

Prelude> maybe 1 (*2) Nothing
1
Prelude> maybe 1 (*2) (Just 2)
4

Maybe モナド型の関数を記述するときにパターンで定義したり、if 文を使わなくてもいいので便利だ。

つぎは、getVar 関数だ。プログラムは次のようになる。

getVar :: Env -> String -> IOThrowsError LispVal
getVar envRef var  =  do
  env <- liftIO $ readIORef envRef
  maybe (throwError $ UnboundVar "Getting an unbound variable: " var)
    (liftIO . readIORef)
    (lookup var env)

getVar 関数の型を見ると、Env型 (環境)とString型の引き数をとり、IOTrowsError LispVal 型の戻値を返す。したがって、環境のリストenvRef の中から変数名が var であるものを検索して、合致するものがあればその値を返し(liftIO . readIORef)、合致するものがなければエラーの例外を発生させる (throwError)。

liftIO という関数は Control.Monad.Trans に記述されており、型は次のようになる。

Prelude Control.Monad.Trans> :t liftIO
liftIO :: (MonadIO m) => IO a -> m a

これは IO a 型の値を、モナド型 m a に変換してくれる便利なものだ。上の例では、readIORef は IO (IORef a) の型の戻値を返すが、liftIO を適用することによって IOTrowsError 型モナドの値に変換している。そこで、listing8.hs をロードして試してみた。

Prelude> :set -XExistentialQuantification
Prelude> :l listing8.hs
Ok, modules loaded: Main.
*Main> :t liftIO . readIORef
liftIO . readIORef :: (MonadIO m) => IORef a -> m a

liftIO でモナド変換できるモナド m は MonadIO クラスのインスタンスでなくてはならない。つまり、IOモナドとの複合モナドである必要があるようだ。

getVar の次は、setVar だが、処理は getVar とだいたい同じだ、変数の値を書きこむのに writeIORef が使われている。setVar はエラーがないときは LispVar を戻す。setVar は本文のコードをみればわかるので、型だけを次に示す。

setVar :: Env -> String -> LispVal -> IOThrowsError LispVal

次は defineVarだが、型は次のようになる。

defineVar :: Env -> String -> LispVal -> IOThrowsError LispVal

setVar と型が同じだが、setVar が変数名がないときはエラーになるのに対し、defineVar では変数名が環境のリストにないときは新しく作ってリストに連結する。

最後に bindVars だが、型は次のようになる。

bindVars :: Env -> [(String, LispVal)] -> IO Env

型から分かる通り、変数名と値のリストを一気に環境リストに連結する関数だ。

仕上げは評価関数 eval と main 関数の改造だが省略する。

これまでの編集はhttp://jonathan.tang.name/files/scheme_in_48/code/listing8.hs に反映されているので、:load して実行してみた。

Prelude> :set -XExistentialQuantification
Prelude> :l listing8.hs
Ok, modules loaded: Main.
*Main> :main
Lisp>>> (define a 2)
2
Lisp>>> (+ (* a 3) 5)
11
Lisp>>> quit

listing8.hs は358行だ。たったこれだけで、関数の定義以外のSchemeのかなりの部分を動作させてしまう。

今回の記事は複合モナド関連だったので、正直しんどかった。まだ、しっかりとは把握できていない。複合モナドについてもう少し要素的な実例があればうれしい。ただ、このチュートリアルのお陰で、IOモナドを扱いながら Error モナドを活用していくというような、入出力でよく出くわすであろう状況に対する対処の仕方のヒントをもらったような気がする。

今更ながら、熟練したHaskellerの技量に感銘をうけた。Haskell はとりつきは簡単なようで奥が深い。
[PR]
by tnomura9 | 2011-12-30 09:44 | Haskell | Comments(0)

48時間でSchemeを書こう/変数と代入 (3)

48時間でSchemeを書こう/変数と代入』で次に出てくるプログラムは、エラー処理のための新しい型 IOThrowsError の定義だ。名前から、エラーを検出して例外を発生させるためのデータ型ではないかと見当がつく。

IOThrowsError の定義は次のようになっている。

type IOThrowsError = ErrorT LispError IO

本来なら、

type IOThrowsError a = ErrorT LispError IO a

と書くべきだろうが、最後のパラメータの a は省略されている。この定義で重要なのは ErrorT というタイプ・コンストラクタだ。これは、Control.Monad.Error に定義されている。本文にリンクが貼ってあった ErrorT の説明では、この型のデータに対し、runErrorT は m (Either e a) 型の戻値を戻す。

Prelude> :m Control.Monad.Error
Prelude Control.Monad.Error> :t runErrorT
runErrorT :: ErrorT e m a -> m (Either e a)

要するに、IOThrowsError a 型のデータが使われていれば、runErrorT 関数がエラー処理の結果を IO モナドにくるんで返してくれるということだ。ErrorT モナド変換子のお陰で、自動的にIOモナドが LispError 型のエラー処理機能を獲得することになる。このときに、LispError のコードは一切書き換える必要がない。liftM のときと同じように、元々の関数をモナド対応に書き換えなくても自動的にモナドに変換してくれるのだ。

ちなみに、lift M の例を次に示す。整数の引き数を2倍にする関数 (*2) をリストモナド用に書き換えることなく、リストの要素を全て2倍にしてくれる。

Prelude Control.Monad.Error> liftM (*2) [1,2,3,4,5]
[2,4,6,8,10]

本題に戻るが、IOThrowsError 型を定義した理由が、runErrorT を使うためであるのなら、本文のどこかにこれを使ったコードがあるはずだと思って検索したら、あった。runIOThrows 関数がそれだ。

runIOThrows :: IOThrowsError String -> IO String
runIOThrows action = runErrorT (trapError action) >>= return . extractValue

これは、IOThrowsError String 型の引き数をとり、IO String を戻値として戻す。おそらく、Scheme の式を IOThrowsError でくるんで、runIOThrows 関数に渡すと、エラー処理も含めた評価が行われ、IO String 型の戻値として返されるのではないだろうか。

そこで、runIOThrows 関数のコードをよく見ると、引き数の action はまず trapError 関数で処理され、その結果が、extractValue 関数に bind 演算子で伝達され、最後に return で IO String 型にして返されるようだ。

そこで、trappError 関数を探したが、この章にはなく、『48時間でSchemeを書こう/エラー処理と例外』で見つかった。

trapError action = catchError action (return . show)

catchError 関数は Control.Monad.Error モジュールの MonadError クラスの関数で、「Eitherアクションと、エラーを引数としてEitherアクションを返す関数を取って、アクションがエラーを表していれば与えられた関数を適用します。その関数では、例えばreturnを使ってエラーを普通の値に変えたり、違うエラーとして再度投げたりします。」ということらしい。この辺りの事情はもう一度エラー処理と例外の記事を読みなおす必要があるような気がしてきた。

catchError :: m a -> (e -> m a) -> m a

いずれにせよ、trapError 関数が処理の中心であることは間違いないだろう。この章のテーマがモナド変換であることは間違いない。

さて、変数と代入を持ち込んだことで変更されるエラー処理の変更の最終の詰めだ。IORef 導入前のエラー処理のデータ型は ThrowsError だった。しかし、これはIOモナド内での使用は想定されていない。そこで ThrowsError を IOThrowsError に変換する関数 liftThrows が記述されている。

liftThrows :: ThrowsError a -> IOThrowsError a
liftThrows (Left err) = throwError err
liftThrows (Right val) = return val

liftThrows は Scheme の式を評価する eval 関数の改造に使われている。

変数の導入によって、エラー処理のようなモナドを必要とする処理を IO モナドの中で実行しなくてはならなくなった。このため、モナド変換子や lift を用いたモナド変換が必要となった。モナド変換によってエラーモナドをIOモナド内で活用するための仕組みができたので、あとは、それを用いて環境に変数を登録したり、変数の値を読み出したり変更をしたりする関数を記述することができる。しかし、それについては、次回の記事で調べてみたい。
[PR]
by tnomura9 | 2011-12-29 20:04 | Haskell | Comments(0)

48時間でSchemeを書こう/変数と代入 (2)

48時間でSchemeを書こう/変数と代入』の最初のプログラムは、(変数名、変数の値) のペアのリストである環境(Env)型の定義だ。本文を見ると次のように定義してある。

import Data.IORef

type Env = IORef [(String, IORef LispVal)]

(変数名, 変数の値) のペアの型は普通に考えれば、(String, LispVal) だが、代入可能な変数は IORef 型に閉じ込められているので、(String, IORef LispVal) になる。同じように、このペアのリストである Env も代入可能でないといけないので、[(String, IORef LispVal)] 型ではなく、IORef [(String, IORef LispVal)] でなければならない。

上の定義は、当然のように思われるが、ここに既に最初の落とし穴がある。

IORef a という型のデータを作成する唯一の方法は newIORef a だが、newIORef の型を見ると次のようになる。

Prelude> :m Data.IORef
Prelude Data.IORef> :t newIORef
newIORef :: a -> IO (IORef a)

つまり、代入のように副作用の生じるものは IO モナドに閉じ込められなければならないので、newIORef の戻値は当然のように IO a 型になっている。したがって、コンテナ内の IORef a を取り出すためには、do 記法内で refVal <- newIORef 1 のように <- 演算子を使って取り出す以外には方法がない。

次のように直接リストを作ってみても、ペアの型は (String, IO (IORef a)) 型になってしまうからだ。

Prelude Data.IORef> let env = [("a", newIORef 1), ("b", newIORef 2)]
Prelude Data.IORef> :t env
env :: [([Char], IO (IORef Integer))]

上の Env の定義のような値を作りたければ、次のように do 記法内で処理するしかない。

Prelude Data.IORef> let env3 = do a <- newIORef 1; b <- newIORef 2; newIORef [("a", a), ("b", b)]
Prelude Data.IORef> :t env3
env3 :: IO (IORef [([Char], IORef Integer)])

しかし、作成できた IORef [(Stirng, IORef a)] リストもやはり、IO にくるまれて戻ってくる。

このように Env 型の値を直接に作る方法がないので、これを行う関数がどこかにあるはずだと思って探してみたら、bindVars という関数があった。

bindVars :: Env -> [(String, LispVal)] -> IO Env
bindVars envRef bindings = readIORef envRef >>= extendEnv bindings >>= newIORef
    where extendEnv bindings env = liftM (++ env) (mapM addBinding bindings)
          addBinding (var, value) = do ref <- newIORef value
                                       return (var, ref)

bindVars の型を見ると、Env と [(String, LispVaL)] を引数に取り、IO Env を戻値として返しているから、この関数が目的の関数だ。

ただ、これだと少し問題がある。引き数に当然のように Env が使われているが、上で見てきたように Env を直接的に作る方法はない。しかし、最初に空のリストを収めた Env 型の値があれば、これを起点に、数珠つなぎに bindVars を関数適用することによって、Env 型の値を更新していくことができる。

このような初期値を作る関数もあるはずだと探したら、nullEnv という関数がそれのようだ。

nullEnv :: IO Env
nullEnv = newIORef []

data Env と bindVars と nullEnv がバラバラに本文の中で散らばっているので、わかりにくかったのだが、説明しようとする側の思考の流れと、理解する側の思考の流れとが異なるので仕方がない。逆に言うと、理解する側の思考の流れに沿った形の説明をすれば、分かりやすい文章が書けるのかもしれない。

初っ端から大変だったが、変数と代入を導入しようなどという試みを、Haskell の女神の怒りをかいくぐってやろうとすれば、それなりの苦労を覚悟しないといけない。

注:

bindVars に出てきた liftM は Control.Monad モジュールの関数で、型は次のようになる。

Prelude Data.IORef> :m +Control.Monad
Prelude Data.IORef Control.Monad> :t liftM
liftM :: (Monad m) => (a1 -> r) -> m a1 -> m r

つまり、第1引き数に「型 a1 をとり型 r の戻値を戻す」関数を、第2引き数にモナドにくるまれた型 a1 の値をとり、戻値をモナドにくるんだ mr を返す。もっとわかりやすく図式を変更すると、

m a1 -> liftM (a1->r) -> mr

つまり、liftM は (a1 -> r) 型の関数を、モナド圏の関数に変換して、モナド値 m a1 に関数適用させることになる。liftM は Haskell 圏の関数をモナド圏の関数に写像する関手のような働きをしていると考えることが出来る。おそらく、これが lift という名の由来だろう。

リストモナドで試してみる。

Prelude Data.IORef Control.Monad> liftM (^2) [1,2,3]
[1,4,9]

mapM 関数の型は次のようになる。

Prelude Data.IORef Control.Monad> :t mapM
mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]

つまり、map の第1引き数がモナド型の関数になったものだ。

Prelude Data.IORef Control.Monad> mapM putStrLn ["apple", "bannana", "orange"]
apple
bannana
orange
[(),(),()]

関数の型は便利なもので、使い方の分からない関数も型を見れば何となく動作がわかる。自分のプログラムを記述するときも関数の型宣言はこまめに記述しておいたほうがいいのかもしれない。
[PR]
by tnomura9 | 2011-12-29 05:22 | Haskell | Comments(0)

48時間でSchemeを書こう/変数と代入

『48時間でSchemeを書こう』も後半に入ってきた。『48時間でSchemeを書こう/変数と代入』は変数と代入の導入だ。

手続き型プログラム言語なら、変数の名前と値のペアのリストを作って、それに登録したり検索したりするだけでそう難しいプログラムにもならないのだが、Haskell には変数も代入もない。手続き型言語と同じようなプログラムを組むのに、いちいちモナドを操作しなければならない。

Haskell で状態を保持するモナドというと、State モナドが頭に浮かぶが、標準ライブラリの Data.IORef モジュールを使うと楽ができるのは前回の記事で述べた。これは変数への代入を IORef モナドとして取り扱うようになっている。また IORef モナドのコンテナからの値の取り出しは IO モナド値としてしか取り出せないので、IORef の関数は IOモナド内でしか使えないようになっている。

変数名の検索を Haskell では lookup 関数で行うが、この戻値は Maybe モナドだ。また、変数名が無いときなどエラーが起きた場合の処理を Error モナドで行わなければならない。また、代入可能な変数の処理は、IOモナドの中で行わなければ、純粋関数の参照透過性が壊されてしまう。

したがって、Haskell で変数と代入を取り扱うには、2重にも3重にもなったモナドの取り扱いが必要だ。この『48時間でSchemeを書こう/変数と代入』の章のプログラムをわかりにくくしているのはこのような入れ子になったモナドの取り扱いだ。この場合は、

IORef モナド -> Maybe モナド -> ThrowsError モナド -> IO モナド

という入れ子構造になるように見える。

ややこしいが、入れ子になったモナドの取り扱いに慣れるのは、Haskell で実用的なプログラムを作るのに避けては通れない関門だ。
[PR]
by tnomura9 | 2011-12-28 11:55 | Haskell | Comments(0)

Data.IORef モジュール

Data.IORef モジュールをインポートすると、IOモナドの中で書き換え可能な変数が使えるようになる。Haskell としては反則技だが、プログラマは楽をできる。使い方は例によって、説明書を読んでもさっぱり分からないので、ghci で試してみた。

まず、Data.IORef モジュールをインポートする。

Prelude> :m Data.IORef

新しいオブジェクトを作って a に束縛し、a のデータを読みだす。

Prelude Data.IORef> do a <- newIORef 0; readIORef a
0

新しいオブジェクトを作って a に束縛し、a の値を書き換えたあと、a のデータを読みだす。

Prelude Data.IORef> do a <- newIORef 0; writeIORef a 3; readIORef a
3

新しいオブジェクトを作って a に束縛し、a の値に加工を加えた後、a のデータを読みだす。

Prelude Data.IORef> do a <- newIORef 0; modifyIORef a (+1); readIORef a
1

readIORef の戻値は IO a 型なので、putStrLn に渡すためには、コンテナから生の値を取り出す必要がある。

Prelude Data.IORef> do a <- newIORef "hello"; modifyIORef a (++ " world"); c <- readIORef a; putStrLn c
hello world
[PR]
by tnomura9 | 2011-12-27 16:08 | Haskell | Comments(0)

ひま

ソロ

【ひま】メグメグ☆ファイアーエンドレスナイトを踊ってみた
【ひま】ステキな日曜日~Gyu Gyu グッデイ!を踊ってみた
【ひま】恋ゴコロを踊ってみた【おまけあり】
【ひま】ハートキャッチ☆パラダイスを踊ってみた【Xmas ver.】
【ひま】メランコリックを踊ってみた【NICOLE ver.】
【ひま】ぐーぐーを踊ってみた
【ひま】恋はきっと急上昇☆を踊ってみた
【ひま】ハロ/ハワユを踊ってみた
【ひま】ハピハピバースデーを踊ってみた
【ひま】te-yut-teを踊ってみた
【ひま】Only youを踊ってみた
【ひま】波乗りかき氷を踊ってみた【復活】
【ひま】Bad Apple!!を踊ってみた
【ひま】うにを踊ってみた
【ひま】ストロベリー☆を踊ってみた【50作目】
【ひま】純情☆ファイターを踊ってみた【100万再生記念】

比較画像

Aikawa Kozue & Hima! Megu-Megu Fire.
【HIMA&IKURA】galaxias!
【 DANCEROID + HIMA 】galaxias!
[ Melochin + Ry☆ ] and Hima! Jyunjyou☆Fighter

12分間

【ひま】リリリリ★メグメグ☆ルカルカ★【ノンストップ】

ブログ

ひまりんノート

次々に才能が現れてくる。「踊ってみた」には驚かされる。
[PR]
by tnomura9 | 2011-12-25 23:56 | ボーカロイド | Comments(0)

48時間でSchemeを書こう/REPLの作成

48時間でSchemeを書こう/REPLの作成』では、Scheme の式を実行して結果を表示するコンソールをプログラムする。難しいテクニックはないが、文章を読むだけでは実感がわかないので、逐次、関数を実行して実験してみた。

以下の例が、本文の関数を実際に ghci で実行してみた結果だ。個々の関数を実際に動かしてみることで本文の説明が何を意図しているかがわかる。Haskell の場合はこのようなフラグメントのテストが割りに実行しやすいので開発が楽に感じられる。

まずは実行環境の整備

forall を使うための -XExistentialQuantification オプションのセットと、try を使うための System.IO モジュールのインクルードをして、今までに記述した listing6.4 のインポートをする。

Prelude> :set -XExistentialQuantification
Prelude> :m System.IO
Prelude System.IO> :l listing6.4.hs
[1 of 1] Compiling Main ( listing6.4.hs, interpreted )

listing6.4.hs:176:0:
Warning: Pattern match(es) are overlapped
In the definition of `cdr': cdr [DottedList [xs] x] = ...
Ok, modules loaded: Main.

flushStr のテスト

flushSrt は putStr で標準入出力のバッファに文字列を出力した後それが画面に確実に出力されるようにバッファーを hFlush でフラッシュする。

*Main System.IO> let flushStr str = putStr str >> hFlush stdout
*Main System.IO> flushStr "hello\n"
hello

readPrompt のテスト

readPrompt では引き数にプロンプトの文字列を与え、それを画面に表示した後 getLine で取り込む。プロンプトの表示には先に定義した flushStr を使う。インタラクティブなプログラムを作るときの定跡。

*Main System.IO> let readPrompt prompt = flushStr prompt >> getLine
*Main System.IO> readPrompt "prompt> "
prompt> hello
"hello"

evalString のテスト

evalString は、引き数の文字列を評価してその結果を文字列にして戻す。結果の中にはエラー処理も含まれている。listing6.4 の関数を使用している。

*Main System.IO> let evalString expr = return $ extractValue $ trapError (liftM show $ readExpr expr >>= eval)
*Main System.IO> evalString "(+ 1 2)"
"3"

evalAndPrint のテスト

引き数の文字列を evalString で評価した後、結果をコンソールに表示する。

*Main System.IO> let evalAndPrint expr = evalString expr >>= putStrLn
*Main System.IO> evalAndPrint "(+ 1 2)"
3

until_ の定義

until_ はループのプログラム。引き数 pred に脱出条件を指定し、prompt にプロンプトを指定し、action に上で作成した evalAndPrint を指定してやると、入力->評価->出力をループする。

*Main System.IO> let until_ pred prompt action = do result <- prompt; if pred result then return () else action result >> until_ pred prompt action

runRepl のテスト

runRepl は until_ を使ってループを実行する。

*Main System.IO> let runRepl = until_ (== "quit") (readPrompt "Lisp>>> ") evalAndPrint
*Main System.IO> runRepl
Lisp>>> (+ 1 2)
3

ここまでのプログラムは listing7.hs に反映されている。

実行例

Prelude> :set -XExistentialQuantification
Prelude> :l listing7.hs
[1 of 1] Compiling Main ( listing7.hs, interpreted )

listing7.hs:178:0:
Warning: Pattern match(es) are overlapped
In the definition of `cdr': cdr [DottedList [xs] x] = ...
Ok, modules loaded: Main.
*Main> :main
Lisp>>> (+ 1 2)
3
Lisp>>> quit
*Main>
[PR]
by tnomura9 | 2011-12-25 19:16 | Haskell | Comments(0)

48時間でSchemeを書こう/評価: 第二部 (2)

48時間でSchemeを書こう/評価: 第二部』に戻ろう。『Equal?と弱い型付け: 異型リスト』の節だ。ここでは、equal? 関数を定義している。equal? では、"2" == 2 のように型の異なるデータの比較ができる。

それでは、equal? 関数を実現するための要件を整理してみよう。Haskell 版 Scheme ではデータは、LispVal データ型のコンテナの中に入っている。これをコンテナから取り出して文字列のデータ (ThrowError Str) として戻す関数が unpackNum, unpackStr, unpackBool だった。

上の3つの unpacker は戻り値として ThrowError String 型を戻す。この戻り値のコンテナの中の文字列が一致したときに equal? が #t を返すようにすればいい。

いまここに arg1 と arg2 の二つの LispVal があるとする。これが、equal? 的に等しいかどうかを確かめるにはどうしたらよいだろうか。まず、上の3つの unpacker を arg1 と arg2 に関数適用しなければならない。そこで、まず arg1 に3つの unpacker を順に関数適用することを考える。

また、3つの unpacker を順番に arg1 に関数適用するためにはどうすればいいだろうか。思いつくのは、unpacker のリスト [unpackNum, unpackStr, unpackBool] に map を適用することだ。たとえば、関数のリスト [(+1), (*2), (^3)] を整数 2 に順に関数適用するためには、次のように整数と関数を引数とする関数 functions を定義し、これを部分適用した (functions 2) を map してやると、3つの関数を整数 2 に適用した結果のリストができる。

Prelude> let functions arg1 fun = fun arg1
Prelude> map (functions 2) [(+1), (*2), (^3)]
[3,4,8]

しかし、問題は3つの unpacker の型がすべて違うということだ、型が違うとリストにして扱うことができない。そこで、存在型を利用して Unpacker 型を定義し、すべての unpacker を AnyUnpacker データコンストラクターで包んでしまう。

data Unpacker = forall a. Eq a => AnyUnpacker (LispVal -> ThrowsError a)

存在型を使わなければならないのは、AnyUnpacker コンストラクタのパラメータの型がひとつではないからだ。

これらの準備をすれば、arg1、arg2 という二つの引数をとり、それに unpacker を関数適用させて、等しいかどうかを判断する unpackEquals を読むことができる。

unpackEquals :: LispVal -> LispVal -> Unpacker -> ThrowsError Bool
unpackEquals arg1 arg2 (AnyUnpacker unpacker) =
             do unpacked1 <- unpacker arg1
                unpacked2 <- unpacker arg2
                return $ unpacked1 == unpacked2
        `catchError` (const $ return False)

最後に、equal?をこれらの補助関数を使って定義する。

equal :: [LispVal] -> ThrowsError LispVal
equal [arg1, arg2] = do
    primitiveEquals <- liftM or $ mapM (unpackEquals arg1 arg2)
                      [AnyUnpacker unpackNum, AnyUnpacker unpackStr, AnyUnpacker unpackBool]
    eqvEquals <- eqv [arg1, arg2]
    return $ Bool $ (primitiveEquals || let (Bool x) = eqvEquals in x)
equal badArgList = throwError $ NumArgs 2 badArgList

これまでのプログラムは listing6.4.hs に記述されている。ghci で試したのが次の例だ。

Prelude> :set -XExistentialQuantification
Prelude> :l listing6.4.hs
*Main> :main "(equal? 2 \"2\")"
#t

ただ、ひとつ疑問が残る。unpackEquals のコードを見る限り、arg1 と arg2 の unpack が成功したかどうかを判定する記述がないということだ。おそらく、それは、エラー処理と遅延評価を活用して行われているのだろうが、本文の説明にもそのことに関しては詳しい説明がない。Haskeller への道はまだ遠い。

これは想像だが、unpackEquals の unpacked1 <- unpacker arg1 のところでエラーが起きるとすぐに`catchError` (const $ return False) で後の作業を中断して次の unpacker を試すのだろう、パターンマッチで値が帰って unpacked1 に値が設定されると次の命令の unpacked2 <- unpacker arg2 に移って最初からやり直すのだろう。そこでもエラーではなく戻り値が unpacked2 に束縛されてはじめてつぎの命令にうつることができる。こういう仕組みではないだろうか。

こういう仕組みを良い工夫と見るか、繰り返しの記述になっても普通に unpack1 と unpack2 を求めるプログラムにしたほうがいいのかは、作業を分担して開発する場合などでは意見が分かれるところだろう。
[PR]
by tnomura9 | 2011-12-25 01:27 | Haskell | Comments(0)

存在型 (Existentially quantified data constructors)

Haskell の存在型というのは一体どういう意味なのだろうか。文字列型や整数型なら意味がわかる。しかし、存在型の存在という言葉にどんな意味がこめられているのか見当もつかない。

探し回っていたら、GHCのマニュアルの

7.4. Extensions to data types and type synonyms

というページを見つけた。このページの 7.4.5. Existentially quantified data constructors に存在型の説明が書いてあった。これを読んだら疑問が氷解した。どうも存在型 (Existetial type) の「存在 (Existential) 」というのは、述語論理学の存在量化子の「存在」らしい。たとえば、「ある自然数 n について、n * n は25である」という命題を述語論理学の記号で書くと下のようになる。

∃n (n ∈ N, n * n = 25)

この「あるn」を表す∃記号が、「存在量化子」だ。Existential がこういう意味だとわかると、次の定義の意味もわかってくる。

data Foo = forall a. MkFoo a (a -> Bool)
           | Nil

Foo 型のデータのひとつは Nil だが、もうひとつは「ある a があって、(a -> Bool) のように、Bool型の戻り値を返す関数を持つものは MkFoo型 のデータ」だ。このときのデータ・コンストラクタ MkFoo は型変数 forall a. a と 関数 a -> Bool を引数にとる。つまり次のようになる。

MkFoo :: forall a. a -> (a -> Bool) -> Foo
Nil :: Foo

文字通りに読めば、「すべての a について、MkFoo のパラメータが a と (a -> Bool) 型の関数であれば Foo型のデータである」だが、a に具体的なデータを持ってくれば、「ある a について、MkFoo のパラメータに a と (a -> Bool) を指定できればそのデータは Foo型のデータだ」というのと同じ意味になる。forall は全称量化子だが、上のような使い方では、意味は存在量化子になる。exists などという新しいキーワードを導入する必要がないので記憶の節約になる。

それでは、MkFoo をどのように使うのかというと、次のような使い方をする。

[MkFoo 3 even, MkFoo 'c' isUpper] :: [Foo]

つまりいろんな型のデータを、Bool型を返す関数と組にしてやることで、ひとつのリストとしてまとめることができる。

多型リストについては、代数型を使って次のようにすれば、

data Bar a = BarString String | BarInt Int

[BarString "hello", BarInt 3] というリストを作ることができるが、データコンストラクタのパラメータの型はコンパイルの段階で規定されている。しかし存在型の場合は次のように動的にパターンマッチが行われる時も val の型は規定されない。

f :: Foo -> Bool
f (MkFoo val fn) = fn val

すなわち、val も fn も型が不定で、fn を val に関数適用した時のみ戻値が Bool 型になる。従って val と fn を単独で取り出すことはできず、パターンマッチで取り出せるのは fn val の関数適用の値のみだ。逆に言えば戻値が Bool 型をとる関数をペアで持っていれば、val は実行時にどのような型も取り得るということだ。

データコンストラクタのパラメータを2つのデータの組みにすることで、単独ではコンパイル時に型指定をしなくてもコンパイルエラーにならないようにできる。上の例で言えば、実行時 val がどのような型であっても、fn を val に関数適用した戻値が一様に Bool 型であれば、型の整合性を乱すことはない。アヒルのように振舞えばアヒルと認めるオブジェクト指向型のダック・タイピングが、型チェックの厳しい Haskell でも使えてしまうということになる。

参考ページに小さな用例があったので ghci で動かしてみた。

ファイル名: existential.hs

data Baz =
    forall a. Eq a => Baz1 a a
  | forall b. Show b => Baz2 b (b -> b)

f :: Baz -> String
f (Baz1 p q)
  | p == q = "Yes"
  | otherwise = "No"
f (Baz2 v fn) = show (fn v)

実行例: (forall を使うためには -XExistentialQuantification フラグをセットする必要がある。)

Prelude> :set -XExistentialQuantification
Prelude> :l existential.hs
[1 of 1] Compiling Main ( existential.hs, interpreted )
Ok, modules loaded: Main.
*Main> f (Baz1 "hello" "hello")
"Yes"
*Main> f (Baz1 1 2)
"No"
*Main> f (Baz2 2 (*2))
"4"

Haskell じゃなくて Ruby を使っているのではないかという気がしてきた。
[PR]
by tnomura9 | 2011-12-22 06:06 | Haskell | Comments(0)