命令型言語Haskell - Pixel Pedals of Tomakomai

※これはHaskell Advent Calendar 2012の12/12分の記事です。

こんにちわ、Perlのプログラマの@hirataraです。関数型言語はまともに使ったことがないので、命令型言語の話を書きます。

Haskellでのふつうの"関数"

Haskellは純粋関数型言語なので、例えば、add1 :: Int -> Intのような型の関数で副作用を発生することはできません。ここでいう副作用とは、ログを出力したりネットワークにアクセスしたりといったoutputだけではなく、ファイルを読み込んだり環境変数を参照するといったinputも含みます。add1は数学の関数と同じように振る舞います。もっときつい言い方をすれば、add1は単なる辞書(Dictionary or Map or HashTable, etc.)のように、キーに対して決まった値を返すような働きしかしません。(ただし、全ての整数をキーとする可算無限個のエントリを持つ辞書なので、実際に辞書として実装することはできません)

しかし、他の言語に慣れた人であれば、辞書が"関数"たり得ないことはわかるでしょう。では、普段から"関数"と呼んでいるものはHaskellではなんなのか。その問いに答えるのが、3日目に@igrepさんが説明されたIO型です。Haskellでa -> bという関数を定義すると、キーの型がaで値の型がbの辞書として振る舞います。それに対し、他の言語で普段使い慣れている"関数"は、a -> IO bのような型で定義をします。例えば、環境変数名を渡してその値を受け取る"関数"はJavaだとString getenv(String name)のように引数も戻り値もString型として定義できますが、Haskellではこの"関数"はString -> StringではなくString -> IO Stringという型で定義されます。また、文字列の長さを返すstrlenはC言語だとint strlen(char s[])のような型で書けますが、Haskellの場合はstrlen :: [Char] -> IO Intと表現されます。もっとも、strlenのように副作用がまったくなく辞書として振る舞っても構わないものをIO型にする必要はなくオススメもしませんが、IO型にしておけば後からファイルを読んだりログを吐いたりと言った副作用を伴う記述を自由に追加することができます。まさに命令型言語を使う人にとってのふつうの"関数"です。

ここで、戻り値にだけIOをつけるということに気をつけて下さい。なぜ戻り値にだけつけるのかと聞かれれば「そういうもんだ」と思うのが一番簡単です。しかし、念のため簡単に説明しておきます。まずIO Intという型の値は、環境によって値が変わります。加えて、IO Int型の値から値を取り出すと、環境を変化させます。この2つの性質により、引数に特別な仕掛けをしなくても戻り値だけで副作用を全て表すことができます。GHC/Types.hs内のIO a型のコンストラクタを見ると以下のようになっています。

newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #))

これを見ると環境(RealWorld)が引数と戻り値にある関数となっており、このことからも環境の影響を受けて環境を変化させる力を持つ値であることが見て取れると思います。

ふつうの"関数"を組み合わせる

命令型言語では、なんらかの処理を実行する様々な"関数"を作り、それらを組み合わせてプログラムを作ります。Haskellでもその事情は同じです。基本的には色々な仕事をしてくれる"関数"を書いておき、do記法を使って"関数"を並べておけば、Haskellの処理系が上から順番に実行してどんどん副作用を発生させてくれます。

ただしここで1つ大きな問題があります。printのように副作用を起こすことが目的の"関数"であれば戻り値を利用しないのですが、通常プログラムを書くときは戻り値を利用します。もう少し具体的に言えば、戻り値を別の"関数"に渡す必要があります。

他の言語であれば、"関数"はString -> IntとかInt -> BoolのようにIOをつけずに定義されているのでした。そのため、前の関数の結果を後ろの関数に直接渡すことができます。しかし、HaskellではこれらはString -> IO IntとInt -> IO Boolとなります。戻り値はIO Intですが、次の"関数"の引数がIntであるためそのまま値を渡すことができません。

このギャップを埋める方法は色々ありますが、do記法内で<-記法を使うのが一番直感的でしょう。

f :: String -> IO Int
f x = ...
g :: Int -> IO Bool
g x = ...

main :: IO ()
main = do
    n <- f "ABCDE"
    b <- g n
    ...

<-の右側にIO a型の値を書くと、左側の変数にa型の値が束縛されます。こうすることで型が合い、gに引数として渡すことができるようになります。ただ、一般的な命令型言語であれば、g(f("ABCDE"))と書けるものを1行ずつ別々に書くのがアホらしいと思うこともあるでしょう。そういう人は、以下のようにApplicativeを使って型をあわせる方法もあります。

import Control.Applicative

f, g :: String -> IO Int
f = ...
g = ...
h :: Int -> Int -> IO Bool
h = ...

main :: IO ()
main = do
  result <- join $ h <$> f "ABC" <*> g "EFG"
  ...

今度は先ほどの<-とは逆の発想で、引数をa型ではなくIO a型に統一してしまおうという戦術です。まず、joinについては最後に適用するものなので、説明を後回しにします。<$>はhの型をIO Int -> IO (Int -> IO Bool)に持ち上げ、IO Int型を受けれるようにしてくれます。ここで<$>はa -> bのような引数が1つの関数に作用することに気をつけて下さい。なので、<$>を使ってもhがIO Int -> IO Int -> IO (IO Bool)とはなりません。この点も副作用を伴う"関数"の合成の難しさの一因でしょう。

さて、<$>で持ち上げたhにf "ABC"を適用すると、今度はIO (Int -> IO Bool)という型になります。<*>はこのIOを括弧を外して中に突っ込んでくれるもので、IO Int -> IO (IO Bool)という型に変換します。こうするとg "EFG"の型と引数の型が揃い、関数適用できるようになります。

これで無事fとgの結果をhに適用することができました。しかし、よく見ると最後の結果の型がIO (IO Bool)とIO型が2重になっています。とは言え、IOはモナドなので型が入れ子になってしまっても心配することはありません。モナドであれば最初に触れたjoin :: m (m a) -> m aという関数により入れ子になった型を1つ外すことができます。ということで最後にjoinを実行し、IOの入れ子を剥がすことでIO Boolという型を得ることができました。

ふつうの"変数"

Haskellの変数は、命令型言語の定数に近いものです。変数が指し示す値は1つであり、それを変更することはできません。命令型言語に染まった人が求める"変数"は、HaskellではIORef型の値となります。名前にIOがついていますが、これはSTモナド内で振る舞うSTRefなどとの対比のためについているだけなので、深く考えずに無視しましょう。要は"Ref"erenceであり、C言語がわかる人であればポインタだと思えばよいです。

IORefを操作する関数はふつうの"関数"なので、戻り値は全てIOで包まれた型です。慣れないうちはIOを見ずに読むといいでしょう。例えば、newIORefはa -> IO (IORef a)という型ですが、これは他の言語でいえば引数の型がaで、戻り値の型がIORef aです。IORefはポインタなので、C言語的に言い換えれば(a *)という型だと見なせます。

import Data.IORef

swap :: IORef a -> IORef a -> IO ()
swap refN refM = do
   n <- readIORef refN
   m <- readIORef refM
   writeIORef refN m
   writeIORef refM n

main :: IO ()
main = do
    refN <- newIORef "N"
    refM <- newIORef "M"
    swap refN refM
    n <- readIORef refN
    m <- readIORef refM
    print $ "n => " ++ n ++ ", m => " ++ m

関数名が長かったりread/writeが同時にできなくて冗長ですが、処理は書けますね。

後、命令型の言語に慣れ親しんでいると、使っちゃ駄目だ使っちゃ駄目だ使っちゃ駄目だ使っちゃ駄目だ・・・と思いつつグローバル変数を使いたくなる局面があると思います。これを実現するのはHaskellではきついです。GHCを使うのであれば、参照したページにある以下のイディオムで一応実現は可能です。NOINLINEが必要なのは、myGlobalVarがβ簡約で展開されてしまうと2カ所でリファレンスができてしまい、2つの別の"変数"と見なされてしまうためです。

myGlobalVar :: IORef Int
{-# NOINLINE myGlobalVar #-}
myGlobalVar = unsafePerformIO (newIORef 17)

ふつうのループ

Haskellでループを表現する場合は再帰を使いますが、末尾再帰最適化のない言語を使っている命令型プログラマはそこまで再帰に慣れていません。ふつうのループを書きたければforM_やreplicateM_が使えます。

main :: IO ()
main = do
  forM_ [1 .. 9] $ \y -> do
      forM_ [1 .. 9] $ \x -> do
          let xy = x * y
          putStr $ if xy < 10 then "  " else " "
          putStr . show $ x * y
      putStrLn ""

しかし、これだとまだ決まった回数を繰り返すだけ。命令型言語のループにはbreakとcontinueがあります。まず、Maybeモナドを組み合わせるとループを抜けるbreakが実現できます。

import Control.Monad
import Control.Monad.Trans
import Control.Monad.Trans.Maybe

main :: IO ()
main = do
    runMaybeT $ forM_ [1..] $ \i -> do
        when (i > 4) $ (MaybeT . return) Nothing
        lift . putStrLn . show $ i
    return ()

continueも欲しい、って人は継続モナドに手を出すことになるんでしょうか。継続渡しな関数を扱うのでフローをコントロールする能力があるってことですが、命令型言語の頭ではこの辺まで来るとだいぶ苦しいですね＞＜

import Prelude hiding (break)
import Control.Monad
import Control.Monad.Trans
import Control.Monad.Trans.Cont

main :: IO ()
main = do
    (runContT $ for_in [1..] $ \loop i -> do
         when (i < 3) $ loop True
         when (i > 6) $ loop False
         lift . print $ i
         ) return

for_in :: [t] -> ((Bool -> ContT r m b) -> t -> ContT r m a) -> ContT r m ()
for_in []     f = return ()
for_in (x:xs) f = do r <- callCC $ \loop -> f loop x >> return True
                     when r $ for_in xs f

そしてふつうの命令型言語へ...

Haskellをもっと命令型言語っぽく使いたければ、Control.Monad.Imperativeを使うといいでしょう。継続モナドでbreak'、continue'、return'をサポートしつつ、GADTによって右辺値と左辺値を表現することで自然な代入の構文を実現しています。

{-# LANGUAGE NoMonomorphismRestriction #-}
import Control.Monad.Imperative

main :: IO ()
main = runImperative $ do
    x  <- new 0
    y  <- new 0
    for' (x =: Lit 1, x <=. Lit 9, x +=: Lit 1) $ do
        for' (y =: Lit 1, Lit True, y +=: Lit 1) $ do
            if' (y >. Lit 9) break'
            xy <- new 0
            xy =: x *. y
            print' " "
            if' (xy <. Lit 10) $ print' " "
            print' . show =<< val xy
        print' "\n"
    return' $ Lit ()
    where
      print' = io . putStr

特にTemplateHaskellを使ったり裏技のようなことをしなくても、関数と型だけでこのようなパッケージが作れるのがHaskellの恐ろしいとこですね！