アロー記法

アローはモナドの一般化であり、John Hughesによって導入された。詳細については、以下のものを見よ。

-XArrowsフラグが与えられると、GHCは二番目の論文に記述されているアロー記法をサポートする。この記法は、Control.Arrowモジュールのコンビネータを使って通常のHaskellに翻訳される。以下に示すのは、この記法の短い紹介である。Hughesの論文を読まないとあまり意味が分からないだろう。

この拡張によって、アローを定義するための新しい種類の式が追加される。

exp10 ::= ...
       |  proc apat -> cmd

ここで、procは新しいキーワードである。パターン中の変数はproc式の本体において束縛されている。本体は、コマンドと呼ばれる、新しい種類のものである。コマンドの構文は以下のとおりである。

cmd   ::= exp10 -<  exp
       |  exp10 -<< exp
       |  cmd0

加えて、cmd0からcmd9までが、式の場合と同じように、中置演算子を使って定義される。

cmd10 ::= \ apat ... apat -> cmd
       |  let decls in cmd
       |  if exp then cmd else cmd
       |  case exp of { calts }
       |  do { cstmt ; ... cstmt ; cmd }
       |  fcmd

fcmd  ::= fcmd aexp
       |  ( cmd )
       |  (| aexp cmd ... cmd |)

cstmt ::= let decls
       |  pat <- cmd
       |  rec { cstmt ; ... cstmt [;] }
       |  cmd

ここで、caltsaltsと同様だが、本体が式ではなくコマンドだという点が異なる。

コマンドは値を生み出すが、(モナドな計算と同じく)複数の値を生み出すこともあるし、零個のこともあるし、同時に別のことを行うこともある。大部分において、モナド記法に親しんでいればコマンドを使う上での良い助けになる。ただし、式(モナドなものも含めて)の値は含まれる変数の値によって決定されるのに対し、コマンドでは必ずしもそうではない。

次に示すのは、この新しい記法の簡単な例である。

proc x -> f -< x+1

これを、手続きまたはアロー抽象と呼ぶ。ラムダ式の場合と同様、変数xproc式の内部で束縛される新しい変数である。この変数はアローへの入力を参照する。上の例で、-<は識別子ではなく、新しい予約シンボルであり、アロー型の式とそのアローに食わせる式とからコマンドを構築するのに使う。(見た目が変だが、これについてはあとで納得できるだろう)。これはアローの適用に相当するものだと考えることもできる。上の例は次のHaskellの式に等しい。

arr (\ x -> x+1) >>> f

これは、-<の左の式に束縛変数xが現れていたらおかしなことになる。一般に、-<の左側の式には局所変数(現在のアロー抽象で束縛された変数)が現れてはならない。このような場合のために、-<<という変種があり、次のように使える。

proc x -> f x -<< x+1

これは以下のものと同じである。

arr (\ x -> (f x, x+1)) >>> app

よってこの場合のアローはArrowApplyクラスに属していなければならない。このようなアローはモナドと同等なので、モナドとして定式化した方が便利かも知れない。

コマンドのdo記法

コマンドはdo記法の形をとることもある。例えば次のように書くことができる。

proc x -> do
        y <- f -< x+1
        g -< 2*y
        let z = x+y
        t <- h -< x*z
        returnA -< t+z

これは通常のdo記法と大体同じように読むことができる。ただし、モナドな式の代わりにコマンドが使われている。最初の行では、x+1の値がアローfに入力として送られ、出力がyに対して照合される。次の行では、出力は捨てられている。returnAというアローは、Control.Arrowモジュールで、arr idとして定義されている。上の例は次のものの略記として扱われる。

arr (\ x -> (x, x)) >>>
        first (arr (\ x -> x+1) >>> f) >>>
        arr (\ (y, x) -> (y, (x, y))) >>>
        first (arr (\ y -> 2*y) >>> g) >>>
        arr snd >>>
        arr (\ (x, y) -> let z = x+y in ((x, z), z)) >>>
        first (arr (\ (x, z) -> x*z) >>> h) >>>
        arr (\ (t, z) -> t+z) >>>
        returnA

それ以降使われない変数は射影で捨てられていることに注意。これにControl.Arrowで定義されている書き換え規則(7.14. 書き換え規則 を見よ)を使って単純化を施すと、以下のように簡約される。

arr (\ x -> (x+1, x)) >>>
        first f >>>
        arr (\ (y, x) -> (2*y, (x, y))) >>>
        first g >>>
        arr (\ (_, (x, y)) -> let z = x+y in (x*z, z)) >>>
        first h >>>
        arr (\ (t, z) -> t+z)

手で書くなら最初からこう書いたであろう。アロー記法を使えば、GHCがあなたの代わりにこれらの変数のタプルたちを管理してくれる。

なお、上の変換では、let束縛された変数(たとえばz)が単相的でなければならないように見えるが、実際の変換で生成されるのはcoreなので、変数は多相的であり得る。

相互再帰的な束縛を使うこともできる。これには、recという新しいキーワードを使う。以下のようになる。

counter :: ArrowCircuit a => a Bool Int
counter = proc reset -> do
        rec     output <- returnA -< if reset then 0 else next
                next <- delay 0 -< output+1
        returnA -< output

このような形式は、変換すると、loopコンビネータを使ったものになるので、その場合のアローはArrowLoopクラスに属していなければならない。

条件コマンド

前の例では、アローへの入力を構築するために条件式を使った。場合によっては、以下のように、条件によって異なるコマンドを実行したいことがある。

proc (x,y) ->
        if f x y
        then g -< x+1
        else h -< y+2

これは次のように変換される。

arr (\ (x,y) -> if f x y then Left x else Right y) >>>
        (arr (\x -> x+1) >>> f) ||| (arr (\y -> y+2) >>> g)

変換結果で|||が使われているので、この場合のアローはArrowChoiceクラスに属していなければならない。

以下のようなcaseコマンドもある。

case input of
    [] -> f -< ()
    [x] -> g -< x+1
    x1:x2:xs -> do
        y <- h -< (x1, x2)
        ys <- k -< xs
        returnA -< y:ys

構文はcase式と同じであるが、選択肢の本体が式でなくコマンドである点が異なる。変換はifで行われるものに似ている。

制御構造を自分で定義する

既に見たように、アロー記法には、逐次実行、値再帰、および条件分岐について、式のものを手本とした構文要素が提供されている。しかし、適切なコンビネータ(これはHaskellで普通に定義できる)があれば、それを、既存のコマンドから新しいコマンドをつくり出すのに使うこともできる。基本的な考え方としては、コマンドを、環境から値へのアローとみなすのである。環境は、コマンド中の自由な局所変数に値を割り当てる。これにより、アローからアローをつくり出すコンビネータは、コマンドからコマンドを構築するのにも使える。例えば、ArrowChoiceクラスには次のコンビネータがある。

ArrowChoice a => (<+>) :: a e c -> a e c -> a e c

よって、これを使ってコマンドを組み立てることができる。

expr' = proc x -> do
                returnA -< x
        <+> do
                symbol Plus -< ()
                y <- term -< ()
                expr' -< x + y
        <+> do
                symbol Minus -< ()
                y <- term -< ()
                expr' -< x - y

(最初の行のdoは、最初の<+> ...が、直前の行の式の一部だとみなされるのを防ぐために必要である)。これは以下のものと同等である。

expr' = (proc x -> returnA -< x)
        <+> (proc x -> do
                symbol Plus -< ()
                y <- term -< ()
                expr' -< x + y)
        <+> (proc x -> do
                symbol Minus -< ()
                y <- term -< ()
                expr' -< x - y)

この演算子がe(そのコマンドへの環境入力。必然的にそのサブコマンドへの環境入力にもなる)について多相的であって、少なくとも正格なkについては以下の自然性を満たす、ということが本質的に重要である。

arr k >>> (f <+> g) = (arr k >>> f) <+> (arr k >>> g)

(seqを使っていないなら自動的にこうなるはずである)。これにより、サブコマンドが見る環境がコマンド全体の環境と同じだということ、および変換において環境のうちの不要な部分を捨てても安全だということが保証される。また、この演算子は、現在のアロー抽象の中で定義された変数を使っていてはならない。

次のように自分で演算子を定義し、同様の方法で使うこともできる。

untilA :: ArrowChoice a => a e () -> a e Bool -> a e ()
untilA body cond = proc x ->
        b <- cond -< x
        if b then returnA -< ()
        else do
                body -< x
                untilA body cond -< x

もちろん、この中置記法の構文は二項演算子についてしかうまく働かない。特別な括弧を使った、より一般的な構文が存在する。

proc x -> do
        y <- f -< x+1
        (|untilA (increment -< x+y) (within 0.5 -< x)|)

プリミティブな構成要素

演算子によっては、サブコマンドに追加の引数を渡す必要がある。例えば、例外を扱えるアローにおいて、例外ハンドラを付加する演算子では、発生した例外をハンドラに渡したいと思うだろう。このような演算子は次のような型を持っていると考えられる。

handleA :: ... => a e c -> a (e,Ex) c -> a e c

ここで、Exは扱われる例外の型である。このとき、次のようなコマンドを書くことで、これをアロー記法中で使うことができる。

body `handleA` \ ex -> handler

意図は、コマンドbodyが例外を発生させたら、変数exがその例外の値に束縛され、コマンドhandler(通常exを参照する)に進入する、というものである。この構文は関数のラムダに似ているが、ここで扱われているのはコマンドであって、やっていることが異なる。コマンドが表すアローの入力は、コマンド中の自由な局所変数の値に加えて、無名の値のスタックから成る。ここまでの例ではこのスタックは全て空だった。handleAの第二引数では、このスタックは一つの値、すなわち例外の値から成る。コマンド用のラムダはこの値に名前を与えているに過ぎない。

より具体的にいうと、このスタック中の値は環境と一緒に対にされる。値は右側である。handleAのような、サブコマンドに追加の入力を渡す演算子は、その値を環境と一緒に対にすることでこの記法で使えるようになる。正確に言うと、演算子のそれぞれの引数(および結果)の型は以下の形をしているべきである。

a (...(e,t1), ... tn) t

ここで、eは(環境を表す)多相変数であり、tiはスタック中の値の型であり、t1が「先頭」である。多相変数eatitに現れてはならない。一方、関係するアローが同じである必要はない。適切な演算子の例をもう少し示す。

bracketA :: ... => a e b -> a (e,b) c -> a (e,c) d -> a e d
runReader :: ... => a e c -> a' (e,State) c
runState :: ... => a e c -> a' (e,State) (c,State)

後ろ二者で作られたコマンドが必要とする追加の引数は、そのコマンドを通常の式に適用することで与えることができる。次のように。

proc x -> do
        s <- ...
        (|runReader (do { ... })|) s

これは、runReaderを使って作られたコマンドの入力のスタックにsを加えている。

コマンド版のラムダ抽象と適用は式におけるそれに似ている。特に、β規則とη規則がコマンドの同等性を記述する。これらの三つの機能(演算子、ラムダ抽象、適用)がこの記法の核である。他のものは全てこれらを使って(不格好になるだろうが)構築することができる。例えば、次のように定義することによってdo記法をシミュレートできる。

bind :: Arrow a => a e b -> a (e,b) c -> a e c
u `bind` f = returnA &&& u >>> f

bind_ :: Arrow a => a e b -> a e c -> a e c
u `bind_` f = u `bind` (arr fst >>> f)

次のように定義することでifをシミュレートできる。

cond :: ArrowChoice a => a e b -> a e b -> a (e,Bool) b
cond f g = arr (\ (e,b) -> if b then Left e else Right e) >>> f ||| g

論文との差異

  • 一種類のアロー適用(アロー尾部)に二通りの変換を用意する代わりに、実装では二種類、すなわち「-<」(一階)と「-<<」(高階)が提供されている。

  • ユーザ定義の演算子を明示するのに、formという新しいキーワードではなく、バナナ括弧を使っている。

可搬性

アロー記法を直接実装しているのはGHCだけであるが、アロー記法をHaskell 98に変換することで別のHaskellシステムでも使える前処理器(arrows web pageから入手可能)もある。それでも、アローを使ったプログラムをGHCで検査したいと思うかもしれない。前処理器の出力から型エラーを追跡するのは簡単ではないからである。モジュールを、GHCとこの前処理器の両方で使えるようにする場合、いくつか余分な制約が科せられる。

  • モジュールはControl.Arrowをインポートしなければならない。

  • 前処理器は他のHaskell拡張に対応していないので、そういうものは別のモジュールに置かなければならない。

  • 前処理器の出力はHaskell(Coreではなく)なので、let束縛された変数は単相的になる。