Free Monadで言語内DSLをつくろう

抽象構文木の構築とその評価の分離

インタプリタコンパイラでは最初に、コードの文字列を構文解析して抽象構文木 (AST) を構築する。その具体的な表現形式は変化して行くことも多いが、基本的にはこの抽象構文木に対して様々な最適化がほどこされる。インタプリタの場合にはこれが評価され実行されるが、コンパイラの場合にはこれがアセンブリの命令に置き換えられ、スケジューリングされ、レジスタが割り当てられ、最終的にはバイナリが生成される。こうした構文解析構文木の構築と、最適化、その評価の分離は、各工程をそれぞれ独立に作成し、必要に応じて取り替えられるという意味で、とても便利だ。

言語内DSLの処理系をそこまで重くするのは本末転倒感があるが、少なくとも構文木を構築しその評価と分離することは、抽象化の手段として適切な場合もあると思う。Haskellでは、言語内DSLのコードとその評価の分離には色々な方法 (型クラスによる抽象など) が考えられるが、ここではFree Monadを取り上げたい。自分で定義した、DSLを表現するデータ型をFunctorにし、Free Monadに入れれば、Monad計算で構文木を構築できる。これを評価するインタプリタは独立に複数用意できるし、評価先の型も自由に変えられる。

Free Monadで言語内DSLをつくる

構文木を表現するデータ型の準備

まずは、自分のDSL構文木を表現するデータ型を定義する。Freeに包むためにはFunctorである必要があるが、この場合その定義は自明なので、簡単のためGHCのDeriveFunctor拡張を使ってderiving Functorしている。(この導出では型コンストラクタの最後の型変数に対応する値を写すようなfmapをつくってくれる。) またこのあと使う予定のモジュールもimportしておく。Freeには色々な実装や、関連するライブラリ、派生形などがあるが、ここでは最初の素朴な物を使っている。(処理効率を考えて実装されたControl.Monad.Free.Churchや、ASTのデータ型からFreeのアクションを導出してくれるControl.Monad.Free.THなどを参照されたし。)

{-# LANGUAGE DeriveFunctor #-}

import Control.Monad.Free
import Control.Monad.State.Lazy
import Control.Monad.Writer.Lazy

data MyAST r = Open r
             | Elephant String r
             | Close r
             | End
  deriving Functor

値コンストラクタはノードのオペランドに対応し、型変数rは残りの木を表している。Freeに包むと、FreeとMyASTが交互に入ることになる。

構文木構築のための、FunctorからのFreeの作成

次に、MyASTの値から対応するFreeのアクションを作成する。Freeの値コンストラクタを使ってもいいが、liftFを使うと少し簡単に書ける。これらのFreeをつなげれば、Free MyAST a型の構文木が構築されていく。

{-
data Free f a = Pure a | Free (f (Free f a))
instance Functor f => Monad (Free f) where
  Free x >>= f = Free $ fmap (>>= f) x
  Pure a >>= f = f a
  return = Pure
liftF = Free . fmap return
-}

-- (対応するFreeの値) = liftF (DSLのデータ型の値)
-- (open = Free $ Open (Pure ()))
open  = liftF $ Open ()
close = liftF $ Close ()
end   = liftF End

putElephant :: String -> Free MyAST ()
putElephant name = liftF $ Elephant name ()

扉を開けて象を入れて扉を閉めてプログラムを終わらせるような命令を用意してみる。Freeは構文木の構築手段を用意しているだけなので、実際に何が行われるかはインタプリタが決める。

インタプリタの作成

最後に構文木を評価するためのインタプリタをつくる。Free MyAST a型の構文木を渡すと、最初のノードにパターンマッチして、何か処理を行い (例えばIntegerやStringなどの値に評価してもいいし、Monad計算に評価してもいい)、残りの木に対する処理を再帰的に呼び出す。葉はPureで表される。

interpretPrint :: Free MyAST a -> IO ()
interpretPrint f = case f of
  Free (Open r)       -> putStrLn "open" >> interpretPrint r
  Free (Elephant e r) -> putStrLn ("elephant: " ++ e) >> interpretPrint r
  Free (Close r)      -> putStrLn "close" >> interpretPrint r
  Free End            -> putStrLn "end"
  Pure _              -> return ()

DSLのプログラムを書く

準備ができたので、幾つかDSLのプログラムを書いて、インタプリタで評価してみる。

program1 :: Free MyAST ()
program1 = do
  open
  putElephant "Sally"
  putElephant "Emet"
  end

program2 :: Free MyAST ()
program2 = do
  open
  putElephant "Emet"
  close
  putElephant "Sally"
  end

先ほど定義した、MyASTの値が入ったFreeをつなげることで、このプログラムを表現する構文木が作成される。

> interpretPrint program1
open
elephant: Sally
elephant: Emet
end

これをインタプリタで評価すれば結果が返る。このインタプリタでは標準出力にプログラムの構成を表示するだけ。

色々なインタプリタをつくる

操作のログを取る

構文木の構築とその評価が分離されているので、同じプログラムを評価する色々なインタプリタをつくることができる。interpretPrintはプログラムをIOにしていたが、interpretNamesは象の名前のリストに評価してくれる。

interpretNames :: Free MyAST () -> Writer [String] ()
interpretNames f = case f of
  Free (Open r)       -> interpretNames r
  Free (Elephant e r) -> tell [e] >> interpretNames r
  Free (Close r)      -> interpretNames r
  Free End            -> return ()
  Pure _              -> return ()

WriterにMonoidをtellすると、後ろでmappendしてくれる。Monoidは単位元memptyを持ち、結合法則を満たす2項演算mappendが使えることを要請する型クラスで、例えばリストのmemptyは[]でmappendは(++)。完成したWriterをexecWriterすれば、このMonoidの演算結果を返してくれる。

> execWriter $ interpretNames program2
["Emet","Sally"]

操作の解析をする

冷蔵庫の状態を表現する型を用意してStateと一緒に使うことで、冷蔵庫が適切に使われているか、最後にどんな状態になっているかを調べてくれるようなinterpretRefもつくってみよう。

data Refregirator = Opened | Closed | Broken deriving (Show, Eq)

interpretRef :: Free MyAST () -> State Refregirator ()
interpretRef f = case f of
  Free (Open r) -> do x <- get
                      case x of Broken -> return ()
                                _ -> put Opened >> interpretRef r
  Free (Elephant _ r) -> do x <- get
                            case x of Opened -> interpretRef r
                                      _ -> put Broken
  Free (Close r) -> do x <- get
                       case x of Broken -> return ()
                                 _ -> put Closed >> interpretRef r
  Free End -> return ()
  Pure _ -> return ()

閉まっているのに象を入れると壊れてしまうことにした。Stateはputやget、stateで明示的に状態を操作できるMonadで、execStateに完成したStateと初期状態をあたえれば、最後の状態を返してくれる。

> execState (interpretRef program1) Closed
Opened
> execState (interpretRef program2) Closed
Broken

DSLのコードはそのままに、IOから切り離して、インタプリタを取り替えて色々なテストや検証もできそうだ。

動的な制御と状態の利用

分岐する木の構築と評価時の動的な制御

ここまでは構文木と言いながら、リストに近いものしか扱ってこなかった。プログラムは1列に並んだ命令列のような構造を持っていた。それというのも言語内DSLではその言語の制御構文がそのまま使えるので、制御フローが静的に決定できるなら、構文木の構築時に分岐のない1つの命令列を選択できるためである。(分岐条件などの値は、インタプリタでの評価時に構文木の構築時点に送り込むこともできる。) 一方で、どうしてもインタプリタでの評価時に制御フロー自体を動的に決定したい時は、構文木を分岐する木として表現したいこともあるかもしれない。

data ArithAST a r = Unitary (a -> a) r
                  | Binary (a -> a -> a) r r
                  | Branch (a -> Bool) r r r
                  | Val a
  deriving Functor

type FA a = Free (ArithAST a) ()

unitary :: (a -> a) -> FA a
unitary op = liftF $ Unitary op ()

binary :: (a -> a -> a) -> FA a -> FA a
binary op l = Free $ Binary op l (Pure ())

branch :: (a -> Bool) -> FA a -> FA a -> FA a
branch cp t f = Free $ Branch cp t f (Pure ())

val :: a -> FA a
val x = liftF $ Val x

ここでは簡単のため、単項演算と2項演算と条件分岐を含む1つの式を表現する構文木をつくり、Branchの制御フローを変えたインタプリタを用意してみる。

type ASTF = Free (ArithAST Double) ()

interpretArith :: ASTF -> Double
interpretArith f = case f of
  Free (Unitary f r)    -> f $ interpretArith r
  Free (Binary f r l)   -> f (interpretArith r) (interpretArith l)
  Free (Branch f l r c) -> if f (interpretArith c)
                             then interpretArith l else interpretArith r
  Free (Val x)          -> x
  Pure _                -> 0

interpretArithBr :: ASTF -> Double
interpretArithBr f = case f of
-- same as interpretArith ...
  Free (Branch f c l r) -> if f (interpretArith c)
                             then interpretArith l else interpretArith r
-- same as interpretArith ...

コードを書いてそれぞれのインタプリタで評価してみる。ノードに演算子があり、木が下向きに延びているので、計算の流れは下から上になる。

-- ((*3) (-2))
calc11 :: ASTF
calc11 = do
  unitary (*3)
  val (-2)

-- (log (max calc1 ((**2.5) 0.5)))
calc2 :: ASTF
calc2 = do
  unitary log
  binary max calc1
  unitary (**2.5)
  val 0.5

-- if (>0) 1.0 then calc1 else calc2 -- interpretArith
-- if (>0) calc1 then calc2 else 1.0 -- interpretArithBr
calc3 :: ASTF
calc3 = do
  branch (>0) calc1 calc2
  val 1.0

> interpretArith calc3
0.9535708819095106
> interpretArithBr calc3
-4.75415180475803e-2

状態の利用

それは入れ子の無名関数でしかないが、do記法の変数束縛記法は直感的で便利だ。ASTを表現するデータ型 (ここではStAST) で関数のフィールド (これがfmapされるようにする) を使えば、StateのようにStASTの文脈から値を取り出し、FreeのPureにわたすことが出来るので、Freeの中でStASTの文脈から変数束縛できる。

data StAST s cs r = Read (s -> r)
                  | Const (cs -> r)
                  | Write s r
  deriving Functor

readS :: Free (StAST s cs) s
readS = liftF $ Read id
-- (readS = Free $ Read (\x -> Pure x))

constS :: Free (StAST s cs) cs
constS = liftF $ Const id

writeS :: s -> Free (StAST s cs) ()
writeS x = liftF $ Write x ()

StASTに変化する状態を表現するフィールドsと、変化しない定数を表現するフィールドcsを作り、それぞれを操作するためのFreeのアクションを用意する。

interpretStAST :: Free (StAST s cs) a -> s -> cs -> s
interpretStAST f x c = case f of
  Free (Read g)    -> interpretStAST (g x) x c
  Free (Const h)   -> interpretStAST (h c) x c
  Free (Write y r) -> interpretStAST r y c
  Pure _           -> x

execStateに相当するインタプリタを作成する。FreeのプログラムとStASTの初期状態をあたえると、最後の状態を返してくれる。プログラムを書いて評価してみよう。

sproc1 :: Free (StAST Double Double) ()
sproc1 = do
  x <- readS
  if x < 0.0 then constS >>= writeS
    else writeS $ sqrt x
  y <- readS
  writeS (x + y)

> interpretStAST sproc1 2.0 0.0
3.414213562373095
> interpretStAST sproc1 (-2.0) 1.0
-1.0

こうした方法を使えば、StASTの状態をDSLの中から確認して制御を変えたりもできる。

まとめと参考文献

Freeを使うと、DSL構文木構築とその評価を分離できる。同じDSLのコードに対して複数のインタプリタを使い分けられるので、例えばIOから切り離してテストや検証などにも利用できる。Freeの中では評価時の状態を制御に組み込めるし、どうしても必要なら制御フロー自体を評価時に選ぶこともできる。Freeの便利さや使い方については、より進んだ内容についてもたくさんの良い記事が書かれているので、参照されたい。

free: Monads for free
Haskell for all: Why free monads matter
Haskell for all: Purify code using free monads
Dave Laing - Free for DSLs, cofree for interpreters
Free and Freer Monads

Haskellの代数的データ型

多相性の実現

Haskellでは型クラスによってアドホック多相が実現でき、型変数によってパラメータ多相が実現できる。また、部分型付けは型変数に対して型クラス制約を課すことで近しいことが実現できる。個人的な印象では、Haskellの型システムは強い型付けという意味で安全で、静的な強い型付けにも関わらず簡単に多相性を実現できるという意味で高機能だと思う。多相再帰も簡単に書けて便利なことがあった。

アドホック多相は同じ名前の関数を引数の型ごとに使い分ける抽象化。例えばDoubleでもIntegerでも(+)が使える。また、パラメータ多相は型によらない共通の処理を行う抽象化。例えばmapはどの型のリストに対しても使える。部分型付けは (オブジェクト指向言語で) 型の派生関係を利用して、共通して持つ処理を実際の型ごとに使い分ける。Haskellでは完全に同等な機能はないが、型クラス制約を付けた型変数を利用することに近い。また、GHC存在量化拡張または一般化代数的データ型拡張を利用すれば、部分型付けを実現できる。
ポリモーフィズム - Wikipedia

型変数を持つ代数的データ型

Haskellの代数的データ型では、要素を列挙したり、それぞれの要素に幾つかのフィールドを持たせたりできる。フィールドは再帰的にも定義できる。また、フィールドには名前を付けることもできる。

data (型名) = (値コンストラクタ名(型名と同じでも良い)) (フィールドの型名 ..) | ..
data Type0 = A | B | C
data Type1 = Recursive Integer String Type1 | Terminal
data Type2 = Type2 { filed1 :: Type0, field2 :: Integer -> Integer }

代数的データ型にも型変数を持たせることができて、例えばリストや木のような構造を定義して、中に入っている型に依らない抽象的な処理を記述することができる。

data (型コンストラクタ名) (型変数名 ..) = (値コンストラクタ名) (フィールドの型名(型変数名を含む) ..) | ..
data Tensor a = Tensor [Tensor a] | Elem a deriving (Eq)

instance Show a => Show (Tensor a) where
  show (Elem x) = show x
  show (Tensor []) = "[]"
  show (Tensor xs) = "[" ++ init (concatMap ((++ ",") . show) xs) ++ "]"

instance Functor Tensor where
  fmap f (Elem x) = Elem (f x)
  fmap f (Tensor xs) = Tensor $ map (fmap f) xs

型変数には自分で定義した代数的データ型でも関数でも何の型でも入れられるので、それをコンテナと解釈するか、何かの文脈と解釈するか、可能性は自由に広がっている。型変数を持つデータ型は、その型変数に入るHaskellの任意の型に対して、ラベルを付けているとも言える。そこで、こうしたラベル付きの型に対して、関数を適用してラベル付きのまま計算していく方法を考えてみたい。まず取り上げたいのが、そのデータ型の中身に関数を適用できるFunctorと、そのデータ型の中に入っている関数に、そのデータ型の中に入っている引数を適用していけるApplicativeという型クラス。(型クラスは、そのインスタンスとしたデータ型が指定の関数を持つことを要請してくれる。)

FunctorとApplicative Functor

データ型の中身に関数を適用して、別のものに写せることを要請する型クラスがFunctor。Functorのインスタンスはfmap関数を実装し、その関手としての意味からFunctor則を満たすことが要請されている。(fmap id == id (恒等変換で不変)、fmap f . fmap g == fmap (f . g) (関数合成の保存) Data.Functor)

class Functor f where
  fmap :: (a -> b) -> f a -> f b

cite #source

例としてTypeというデータ型を定義し、TypeをFunctorのインスタンスにし、fmapを実装してみる。

data Type a = Content a | Empty deriving (Show)

instance Functor Type where
  fmap f (Content x) = Content (f x)
  fmap _ Empty = Empty

> fmap (^2) (Content 7)
=> Content 49
> fmap (*2) Empty
=> Empty

Typeに入っていても、Haskellの普通の型 (ここではTypeの外の世界の型という意味。Typeも普通の型。) の値であるかのように、Typeの中身にfmapで普通の関数を適用できるようになった。いったい何が嬉しいのかわからないかもしれないが、例えばリストはFunctorでリストのfmapはmapである。そのデータ型の意味に応じて適切に定義されたfmapによって、データ型の中身を普通のHaskellの関数で写せることは役に立ちそうだ。

Functorでは、fmapに渡す関数はTypeの中から1つの引数しか取れないが、複数のTypeの中身を引数としてあたえたい時はどうしたら良いだろうか。Typeの中に関数を入れて、次に渡されたTypeの中身を部分適用した関数を、Typeに入れて返せるような仕組みを作れば良さそうである。こうした仕組みはApplicativeという型クラスが要請している。(ApplicativeのインスタンスはFunctorのインスタンスで、Applicative則を満たす必要がある。Control.Applicative)

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

cite #source

instance Applicative Type where
  pure = Content
  Content f <*> Content x = Content (f x)
  _ <*> _ = Empty

> pure (^) <*> Content 2 <*> Content 4
=> Content 16
> mod <$> Content 14 <*> Content 3
=> Content 2

pureは引数をTypeの中に入れ、<*>はTypeの中に入っている関数に次のTypeの中に入っている値を適用する。<$>はfmapの別名。Typeの中に部分適用された関数が入れば続けて適用を繰り返せる。Typeの中に入っていても、Haskellの普通の型の値のように、複数の引数を取る普通の関数に適用できるようになった。

FunctorやApplicative Functorはデータ型の中身を、そのデータ型が意味する文脈に応じて、普通の関数で操作するという意味合いが強いと思うが、Haskellの代数的データ型の表現力はそれに留まらず、文脈を付与されたデータ型に対して、その文脈において意味のある計算を自由に定義し、これを連ねていくことを記述できる。

MonadMonad変換子

MonadインスタンスはApplicativeのインスタンスであって、Monad則をみたす必要がある。(Control.Monad)

class Applicative m => Monad m where
  (>>=) :: forall a b. m a -> (a -> m b) -> m b
  
  (>>) :: formal a b. m a -> m b -> m b
  m >> k = m >>= \_ -> k
  
  return :: a -> m a
  return = pure

cite #source

forall a bはaとbが型変数であることを明示的に宣言しているが省略できる。Monadが要請するのはbindと呼ばれる演算子>>=の実装で、Monadの中身を取り出し、あたえられた関数 (a -> m b) に適用し、Monadとして返す。>>=にあたえる関数はMonadアクションと呼ばれている。>>は左の値を利用しないbindで (文脈の処理は行われる)、returnはpureと同じもの (つまり値を中に入れるだけで、文脈は操作しない)。

FunctorやApplicativeとの違いは、Monadでは>>=によって背景で自動的に文脈の処理が行われることや、その時、 (これらの演算子Monadの階層を削減する能力を持つことによって) アクションが文脈に働きかけることができる点にある。適切なアクションによる値の操作と文脈の供給を用意しておけば、文脈の処理はMonadにまかせることができ、そうした計算は好きなだけ連ねていくことができる。つまり、>>=を定義しMonadアクションを用意することは、Monadの文脈を処理する計算を行うためのDSLを用意することに近しい。

Typeを拡張して、Emptyが出てこない限り、計算の点数を数えるような計算という意味をTypeに追加してみる。

data Type a = Content a Int | Empty deriving (Show)

instance Functor Type where
  fmap f (Content x n) = Content (f x) n
  fmap _ Empty = Empty

instance Applicative Type where
  pure x = Content x 0
  (Content f n) <*> (Content x m) = Content (f x) (n + m)
  _ <*> _ = Empty

instance Monad Type where
  Empty >>= f = Empty
  (Content x n) >>= f = case f x of
                          Empty -> Empty
                          (Content y m) -> Content y (n + m)

このMonadでの文脈の処理として、>>=で中身を取り出しアクションにあたえて、その後ろで点数を足し合わせていく。>>では点数の加算のみが行われる。また、1度でもEmptyが出て来たら、常にEmptyになる。

アクションを定義して、計算しながら掛け算の数を数えてみる。

square :: Num a => a -> Type a
square n = Content (n * n) 1

fact :: Integral a => a -> Type a
fact n = Content (f n) (fromIntegral n - 1)
  where f m | m < 2 = 1
            | otherwise = m * f (m - 1)

> square 2 >>= fact >>= square
=> Content 576 5

addCount :: Int -> Type ()
addCount n = Content () n

calc :: Type Integer
calc = do
  x <- square 2
  y <- fact x
  addCount 3
  square y

> calc
=> Content 576 8

do記法はMonad計算を直感的に書くための構文糖衣。各式はそのMonadの型で、>>で結ばれていると見なせる。また、Monadの中身は<-で取り出して変数に束縛できる。 (その場合は、>>=で値を取り出し、無名のアクションの引数として変数に束縛しているような状態。) もっとたくさんのアクションが用意され、calcのdo記法の中身のような計算が大規模になって複雑になっても、点数の計算と失敗の記録はTypeが後ろで自動的に行ってくれるので、このMonadを使う人は、ただ値の計算に集中することができる。

こんな風に、自分のデータ型にあたえたい計算の意味に応じて、適切に>>=とアクションを定義すれば、文脈に沿った処理が簡単に書けるようになる。関数合成演算子 (.) のように、Monad計算におけるアクションの合成を行う演算子 (f >=> g = \x -> f x >>= g) を考えると、Monad則は、>=>による計算の合成において、returnが左単位元かつ右単位元となることと、>=>が結合法則をみたすことを意味している。(つまり、returnは文脈を変更せず、連続する>=>はどの2項から計算を合成しても結果が変わらない必要がある。) このように考えると、Monadをつくることは、単位元を持ち結合法則を満たす新しい計算の体系をつくっているとも捉えられる。自然数の掛け算で類推するなら、自然数Monadアクションで、*が>=> 、1がreturnになる。

Haskellのライブラリには、状態のStateやReaderやWriter、入出力のIO、失敗可能性のMaybeやEither、DSL構文木処理のFreeなど便利なMonadが色々用意されていて、必要に応じてMonad変換子で複数を組み合わせて使うこともできる。

import Control.Monad.Trans.Maybe
import Control.Monad.Trans.Class (lift)
import Control.Monad (guard)
import Text.Read (readMaybe)

readPositiveInteger :: MaybeT IO Integer
readPositiveInteger = do
  l <- lift getLine
  x <- (MaybeT . return) (readMaybe l)
  guard (x > 0)
  lift $ putStrLn "thank you for correct value!"
  return x

> runMaybeT readPositiveInteger
hello
=> Nothing
> runMaybeT readPositiveInteger
1.0
=> Nothing
> runMaybeT readPositiveInteger
1
thank you for correct value!
=> Just 1

MaybeTの中にIOが入っているが、MaybeTのdoの中でも、liftを使えば内側のIOの関数を使うことができる。guardは零元を持つ2項演算を抽象化したMonadPlus (零元はmzero、演算はmplus) の関数で、引数がFalseの時、零元になる。MaybeTでの実装では、MaybeT (return Nothing) が入る。ちなみにMonadPlusのApplicative版にAlternativeがあり、また単位元を持つ2項演算を抽象化したMonoid (単位元はmempty、演算はmappend) などもある。特定のMonadに依らない、抽象化されたMonad計算を用意したい時にはこうした型クラスも使える。Monadが便利に使われている身近な例としては、リストの内包表記もリストMonadのdo記法だったりする。Stateを使うだけでもかなり表現力の高い言語内DSLを書くことができるので、そのうちそうした記事も書いてみたい。

MonadHaskellの文法によって特殊な地位をあたえられている訳ではなく (構文糖衣doはあるが) 、こうした記述能力は型変数を持つHaskellの代数的データ型と型クラスの能力によって自然に実現されている。

メモ

Haskellモナドの話には圏論の言葉がよく出てくるのですが、ざっくりとした理解しかできていません。自分の理解をまとめるためにメモを残します。間違っているかもしれないので、鵜呑みにはしないでください。圏論はなんとなく集合論をさらに抽象化したような印象です。

  • 圏は対象と、対象から対象への射を持った構造
  • 関手はある圏ともう1つの圏の間で、対象を対象に写し、射を射に写す
  • その際、恒等な射と、射の結合法則を保存しなければいけない

これは、HaskellのFunctorにあてはめると以下のようになります。

  • Haskellのすべての型の値を対象として、関数を射とすることで、圏にできる
  • 関手はFunctorの値コンストラクタとfmapで、これで写すことで、Haskellのすべての型の圏はFunctorの圏に対応させることができる
  • 関手で写す前後の、恒等な射と、射の結合法則の保存は、Functor則そのもの
fmap id ≡ id
fmap (p . q) ≡ (fmap p) . (fmap q)

HaskellMonadについてはもう少し複雑で、Haskellのすべての型の圏からMonadの圏への関手 (MonadHaskellの型なので、自分から自分への自己関手になる) が、自然変換を射とすることでまた圏を為し、この関手の圏において、モノイドの性質を持つような対象であるMonadの値コンストラクタ (と自然変換の組) がモナドです。

  • Haskellのすべての型の値を対象として、関数を射とすることで、圏にできる
  • Monadの値コンストラクタを関手とすることで、Haskellのすべての型の圏はMonadの圏に対応させることができる
  • この関手であるMonad (の値コンストラクタ, 以下では省略) に対して、自然変換を射として導入することで、圏にできる
  • 自然変換は構造を保存したままMonadMonadに写すような変換で、ここでは恒等関手をMonadに写すような変換returnと、Monadによって写したMonadを、Monadに写すような変換join
return :: a -> m a -- 自身に対応させる (何もしない) 関手を、mに写す関手に変換していると捉えられる
join :: m (m a) -> m a
return x >>= f ≡ f x
m >>= return ≡ m
(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)
  • joinはbindと以下のように変換できるので、bindをつなげていくことは、Monadの適用を繰り返していくことに等しくなる。
m >>= f ≡ join $ fmap f m

まとめるとMonadの値コンストラクタはHaskellのすべての型の圏からMonadの圏への関手で、この関手自体が自然変換returnとjoinを射として圏をなし、モノイドの性質を持っています。モノイドなのでどこから演算を始めても結果は変わりません。

意識していませんでしたが、ここでは、型クラスFunctorやMonadインスタンスである型の値が対象である圏をそれぞれFunctorの圏やMonadの圏と呼んでいます。値コンストラクタについても同様です。

自分の語彙の使用は正確ではないかもしれない…。もっと正確で詳細な内容が知りたい方はこちらなどをご参照ください。
Haskell/圏論 - Wikibooks

Haskellで数値計算

普段はJavaFortran数値計算をしているのだが、使える範囲でHaskellも使ってみたくなった。宣言的に書けるのでコードが簡潔になることや、副作用が厳格に管理されている上に、静的な型付けがしっかりしていてコンパイラが賢いので、バグが見つけやすいことなどがうれしい。ただ、自分で管理できるワークステーションならともかく、スパコンGHCを入れて多次元の流体計算などしたいとなると、どうだろうか。Fortranよりも計算資源を効率的に使えていると説明できないといけないかもしれない。一方で、MathematicaPythonでやっているような計算の一部は、Haskellでより柔軟に速くできることも多そうだ。ここでは、よく使われる簡単なアルゴリズムを書いてみた。

準備と方針

処理系はGHC 8.0.2を使っている。また、行列計算のためにhmatrixパッケージを入れた。(ここではcabalを直接使っていますが、状況に応じてStackなどを使ってください。) 行列分解や連立線形方程式を解くアルゴリズムもいずれ紹介してみたい。

> cabal update
> cabal install hmatrix

ここでは、そこまで速度やメモリにシビアではない状況を考えている。速度やメモリを気にする場合は、Listの代わりにData.Vector.Unboxed (参照ではなく値の配列で、要素を辿るようなライブラリ関数はFusionが単一のループにしてくれたりするらしい) を使ったりすると良い。使い勝手もリストとそれほど変わらない。
Numeric Haskell: A Vector Tutorial - HaskellWiki
vectorパッケージはhmatrixを入れると付いてくる気がするが、個別にインストールすることもできる。

> cabal update
> cabal install vector

また、アルゴリズムの選択は何より性能に影響をあたえると思うが、ここでは見通しを優先して逆行列を計算するライブラリ関数を素直に使っていたりするので、その辺りは認識しておいて欲しい。並列計算についてもそのうち紹介してみたい。

4段4次の古典的Runge-Kutta法

まずは連立常微分方程式 (ODE) を解いてみる。4段4次の古典的Runge-Kutta法は簡単で精度や速度もそれなりなので、よく使われている。ただ陽解法なので、問題によっては適さないこともある。非線形方程式を解いてもいいなら、1段2次や、3段6次の陰的Runge-Kutta法などの方がいいかもしれない。

import Data.List

kf :: Double -> Double -> [[Double] -> Double] -> [Double] -> Double -> [Double] -> [Double]
kf tc xc fs (t:xs) h ks = map ($ rps) fs
  where rps = st:sx
        st = t + tc*h
        sx = zipWith (\x k -> x + xc*h*k) xs ks

rungekutta_44 :: [[Double] -> Double] -> Double -> Double -> [Double] -> IO ()
rungekutta_44 dfs h lim ps@(t:xs) = do
  print ps
  if t > lim then return ()
  else rungekutta_44 dfs h lim ((t + h):ss)
    where k1s = kf 0.0 0.0 dfs ps h (repeat 0.0)
          k2s = kf 0.5 0.5 dfs ps h k1s
          k3s = kf 0.5 0.5 dfs ps h k2s
          k4s = kf 1.0 1.0 dfs ps h k3s
          ss = zipWith5 sx xs k1s k2s k3s k4s
          sx x k1 k2 k3 k4 = x + (h/6.0)*(k1 + 2.0*k2 + 2.0*k3 + k4)

高階微分の方程式を解く場合、新しい変数を導入して1階微分の方程式を連立させることになるので、これを自動化してくれる関数も書いてみた。

rungekutta_44_s :: ([Double] -> Double) -> Double -> Double -> [Double] -> IO ()
rungekutta_44_s df h lim ps = rungekutta_44 (dfn ++ [df]) h lim ps
  where dfn = map dndt [0..(length ps - 3)]
        dndt n = (!! (n + 2))

簡単な方程式でテストしてみる。方程式や初期値はリストであたえているので、数や順番は自分で気をつけないといけない。ライブラリにする場合は別の方法を考えた方がいいかもしれない。

> -- 調和振動
> rungekutta_44 [\[t,x,v] -> v,\[t,x,v] -> -x] 0.1 100.0 [0.0,1.0,0.0]
> -- 減衰振動
> rungekutta_44_s (\[t,x,v] -> -x - 0.1*v) 0.1 100.0 [0.0,1.0,0.0]

f:id:lqtmirage:20170529112439p:plainf:id:lqtmirage:20170529232044p:plain
もう少し面白いローレンツアトラクタなども描いてみる。

> let l_dxdt [t,x,y,z] = -10.0*x + 10.0*y
> let l_dydt [t,x,y,z] = -x*z + 28.0*x - y
> let l_dzdt [t,x,y,z] = x*y - 8.0/3.0 * z
> rungekutta_44 [l_dxdt,l_dydt,l_dzdt] 0.01 100.0 [0.0,1.0,1.0,1.0]

f:id:lqtmirage:20170529232335p:plain

Newton-Raphson法

人間誰しも連立非線形方程式を解きたくなることがあるはずだ。Newton-Raphson法は微分係数を使って解に近づいていく収束が速いアルゴリズムで、適切な関数に対して適切な初期値をあたえれば、近くにある解を1つ見つけてくれる。ただ、収束しないこともあるし、自動的にすべての解を見つけてくれるわけではない。
まずは1変数の場合。微分係数は普通の関数なら十分小さいと思われる値での差分で近似している。より正確には、deltaを小さくしていった時差分の変化がある値より小さくなるというような収束判定を行ったりするとよい。

delta = 1.0e-9 :: Double

derivative :: (Double -> Double) -> Double -> Double
derivative f x = (f (x + delta) - f x) / delta

newton :: Int -> Double -> (Double -> Double) -> Double -> Maybe Double
newton lim err f x
  | lim <= 0 = Nothing
  | abs fx < err = Just x
  | otherwise = newton (lim - 1) err f sx
  where sx = x - (fx / dfdx)
        fx = f x
        dfdx = derivative f x

簡単な関数でテストしてみる。発散したらすぐに打ち切るべきか。

> newton 1000 1.0e-9 (\x -> x^2 - 4.0) 4.0
=> Just 2.0000000000000053
> newton 1000 1.0e-9 (\x -> x^2 - 4.0) 0.0
=> Nothing

多変数の場合に拡張する。微分係数をJacobi行列 (偏微分係数を並べた行列) に置き換えて、関数とパラメータをベクトル化しただけで、ほとんど同じに書ける。

import qualified Numeric.LinearAlgebra as L

delta = 1.0e-9 :: Double

derivative_p :: ([Double] -> Double) -> [Double] -> [Double]
derivative_p f xs = zipWith dfdx xs [0..]
  where dfdx x i = (f (replace xs i (x + delta)) - f xs) / delta
        replace xs i x = take i xs ++ [x] ++ drop (i + 1) xs

newton_m :: Int -> Double -> [[Double] -> Double] -> [Double] -> Maybe [Double]
newton_m lim err fs xs
  | lim <= 0 = Nothing
  | L.norm_2 fx < err = Just xs
  | otherwise = newton_m (lim - 1) err fs sx
  where sx = L.toList $ L.vector xs - (L.inv j L.#> fx)
        fx = L.vector $ map ($ xs) fs
        j = L.fromLists $ map (flip derivative_p xs) fs

適当な関数でテストしてみる。

> let vf0 [x,y,z,t] = 2.0*x^2 - y^3 + z - exp t
> let vf1 [x,y,z,t] = 3.0*x - 6.0*y^5 - 2.0*z*t
> let vf2 [x,y,z,t] = 2.0*x^2 - y - 2.0*z*t
> let vf3 [x,y,z,t] = x^4 + y*z - 2.0*t
> newton_m 1000 1.0e-9 [vf0,vf1,vf2,vf3] [1.0,2.0,3.0,4.0]
=> Just [1.066252215687592,0.7772738508955951,0.7861552762455988,0.9517927114657457]
> let a = [1.066252215687592,0.7772738508955951,0.7861552762455988,0.9517927114657457]
> map ($ a) [vf0,vf1,vf2,vf3]
=> [1.3322676295501878e-15,1.5543122344752192e-15,1.9984014443252818e-15,1.5543122344752192e-15]

Double程度の精度で解けていそうだ。適宜deltaやerrを調整する必要があるかもしれない。

Newton-Cotes型定積分

等間隔で関数値があたえられている時に積分値を計算する、Newton-Cotes型と呼ばれる一連のアルゴリズムがある。なかでも2次関数で補間するSimpson法はよく使われている気がする。4次関数で補間するBoole法もためしてみた。

newton_cotes :: [Double] -> Double -> (Double -> Double) -> Int -> Double -> Double -> Double
newton_cotes ces ce f n a b = ((b - a) / (r ^ n)) * ce * ig n a b
  where r = fromIntegral $ length ces - 1
        ig n a b
          | n == 1 = sum $ zipWith (*) (map f cs) ces
          | otherwise = sum $ zipWith (ig (n - 1)) cs (tail cs)
          where cs = map (\i -> a + i * ((b - a) / r)) [0.0..r]

simpson :: (Double -> Double) -> Int -> Double -> Double -> Double
simpson = newton_cotes [1.0,4.0,1.0] (1.0/3.0)

boole :: (Double -> Double) -> Int -> Double -> Double -> Double
boole = newton_cotes [7.0,32.0,12.0,32.0,7.0] (2.0/45.0)

分割位置のリスト生成について、数値誤差で長さが変わらないように冗長に見える方法をとってみた。簡単な関数でテストしてみる。

> simpson (\x -> x^4) 4 0.0 1.0
=> 0.20000203450520831
> boole (\x -> x^4) 2 0.0 1.0
=> 0.2

Boole法のほうが次数は高いが必ず精度が良いとは限らない。

Schemeの継続と環境

前回の記事で、call/cc は呼ばれた時点での継続を取り出してくれるということを書いたのだが、その時点での環境は保存されているのだろうか? 前回の記事に出て来た wayback 関数を少し書き換えて実験してみる。

(define cont #f)

(define (capture x)
  (call/cc (lambda (cc) (set! cont cc) x)))

(define (wayback2 n)
  (let* ((a 0) (x (capture n)))
    (display (list a x))
    (newline)
    (set! a 1)
    (if (> x 0) (cont (- x 1)) x)))

let* は前に束縛された変数を、後の変数束縛で参照したい時に使えるのだが、それゆえに実行順も決められる。ここでは、aに0が束縛された後、xに (capture n) が束縛される。capture はその時点での継続をcontに保存し、引数をそのまま返すような関数。その後、aとxを表示した後、aに1を代入する。これを実行すると、GaucheでもChibi-Schemeでも以下のような結果になった。

> (wayback2 3)
(0 3)
(1 2)
(1 1)
(1 0)
=> 0

継続 cont が呼び出されると、xへの引数の束縛以降の処理が行われるが、aへの0の束縛はそれ以前に終わっているので繰り返されない。しかし、もし継続が環境も保存しているなら、何度呼び出してもaは0に戻るはずだ。だが、結果はそうはならず、(set! a 1) の影響がその後の継続呼び出しにも反映されている。継続は環境を保存してはくれない。

評価順序と継続
ここに詳しく書いてあった。

Schemeと継続

継続とcall/cc

継続とは

Schemeでは継続を手続きとして取り出して利用することができる。継続とはプログラムの (基本的にはトップレベルに戻るまでの) 残りの処理のことで、例えば、以下の [] の部分には、(square 2) をかけて1を足すという処理が残されている。

(+ 1 (* [] (square 2)))

call/ccは継続を取り出してくれる

call/cc (call-with-current-continuation) を使うと、この残りの処理を手続きとして取り出し、この手続きを引数として関数を呼び出してくれる。

> (+ 1 (* (call/cc (lambda (cc) (cc 3))) (square 2)))
=> 13

現在の継続が取り出され、これを引数として (lambda (cc) ...) が呼び出されている。ここではこのccが継続で、それは普通の手続きである。ccが呼ばれると、(call/cc ...) が呼ばれた時点のその全体がccの引数で置き換えられる。先ほどの [] の部分がccの引数で埋められるとも言える。

(lambda (cc) ...) も普通の関数で、普通に呼び出されているので、もしccが呼ばれないなら最後に評価された式の値が返される。

> (+ 1 (* (call/cc (lambda (cc) 0)) (square 2)))
=> 1

継続はファーストクラスのオブジェクト

継続はファーストクラスのオブジェクトなので、変数に束縛したり、関数の引数や返り値として渡すこともできる。

> (define cont #f)
> (+ 1 (* (call/cc (lambda (cc) (set! cont cc) 0)) (square 2)))
=> 1
> (cont 3)
=> 13

時をさかのぼる

さて、継続が面白いのは、(その定義通り) 継続が取り出された時点のプログラムの残りの処理が保存されていることである。

(define cont #f)

(define (wayback n)
  (let ((x (call/cc (lambda (cc) (set! cont cc) n))))
    (begin (display `("wayback" ,x))
           (newline)
           (if (> x 0) (cont (- x 1)) x))))

xへの変数束縛以降の継続がcontに保存されており、1度waybackを抜けた後も、contを使って何度でも呼び直すことができる。

> (wayback 2)
(wayback 2)
(wayback 1)
(wayback 0)
=> 0
> (cont 3)
(wayback 3)
(wayback 2)
(wayback 1)
(wayback 0)
=> 0

まるで時間をさかのぼって、別の未来への処理をやり直しているように見える。継続の保存期間には制限がないので、束縛されている限りは何度でも呼び出せる。

どこでも取り出せる継続

あまり迷う人もいないかもしれないが、クロージャは定義された位置での環境を参照するのに対して、call/ccは呼ばれた時点での継続を取り出す。そこで、こんな手続きを使うこともできる。

(define cont #f)

(define (capture x)
  (call/cc (lambda (cc) (set! cont cc) x)))

(define (func n)
  (cond ((= n 0) (capture 1))
        (else (* n (func (- n 1))))))

captureは呼ばれた時点での継続をcontに束縛し、xを返す。そのため、コード中の好きな式aを (capture a) に置き換えれば、結果を変えずにその位置での継続をcontに束縛できる。

> (func 4)
=> 24
> (cont 5)
=> 120

Schemeではcall/ccを使えば、どこでもその時点の継続を取り出すことができ、それを変数に束縛したり、関数に渡したり返したりして、遠く離れた場所からも利用できる。これはなんだか大変な力に思える。

継続の利用

それでは、具体的には継続は何に使えるのだろうか?ここでは簡単なサンプルコードを示して継続の使い方を紹介してみたいと思う。

大域脱出

継続のわかりやすい使用例は大域脱出だ。継続がなくても同様の処理は書くことができるが、深い位置からの脱出ではコードがより簡潔になることもあるかもしれない。

(define (escape x lst)
  (call/cc (lambda (return)
             (map (lambda (l)
                    (if (= l 0) (return '()) (/ x l)))
                  lst))))

returnにescape関数の最も外側の継続が保存されているので、returnが呼ばれた時点で (残りの処理を飛ばして) その引数が直ちにescape関数の返り値となる。それゆえに、returnはCのような言語のreturn文のように使うことができる。

> (escape 2 '(1 2 3))
=> (2 1 2/3)
> (escape 2 '(0 1 2))
=> ()

処理の一時中断と再開

継続の力がより発揮される例の1つは、好きな位置で一時中断して、後で停止した位置から再開するような処理ではないだろうか。まずは以下のようなコードを考えてみる。

(define resume #f)

(define (resumable n)
  (call/cc (lambda (return)
             (display `("resumable" ,n))
             (newline)
             (call/cc (lambda (cc)
                        (set! resume (lambda () (cc #t)))
                        (return n)))
             (resumable (+ n 1)))))

resumable関数は内側のcall/ccが呼ばれた時点の継続をresumeの中に保存し、returnでnを返している。なので、resumeを呼び出せば、内側の (call/cc ...) が#tで置き換えられ、(resumable (+ n 1)) が呼ばれる。

> (resumable 0)
(resumable 0)
=> 0
> (resume)
(resumable 1)
=> 1
> (resume)
(resumable 2)
=> 2
...

ただ、このresumableはnを返して止まってしまうので、返り値を使うことはできず、例えば以下のようにリストを作ることはできない。

> (import (srfi 1))
> (fold (lambda (i l) (cons (resume) l)) '() (iota 10))
(resumable 3)
=> 3

それというのも、(resume) は前回の resumable 途中の継続に飛んで行ってしまって、呼び出し元の継続には帰って来ないからである。返り値を使いたい場合は、(resume) の中で取り出された継続に帰って来てくれないといけない。そこで、以下のように改良してみる。

(define yield #f)

(define (generator proc)
  (define current proc)
  (define (next)
    (call/cc (lambda (return)
               (set! yield (lambda (x)
                             (call/cc (lambda (cc)
                                        (set! current cc)
                                        (return x)))))
               (current))))
  next)

(define (endless)
  (let loop ((i 0))
    (begin (display `("endless" ,i))
           (newline)
           (yield i)
           (loop (+ i 1)))))

generator内のnext関数は、yieldの呼び出し時の継続をcurrentに保存し、yieldの引数xをreturnに返すような関数をyieldにセットし、currentを呼び出す。そのため、currentの呼び出し先でyieldが呼ばれると、currentはyieldへ戻るための継続に更新され、nextはxを返す。こうして、nextは呼ばれる度に、yieldまでの処理を実行し、xを返し、一時中断する。

> (define gen (generator endless))
> (gen)
(endless 0)
=> 0
> (gen)
(endless 1)
=> 1
...
> (import (srfi 1))
> (fold (lambda (i l) (cons (gen) l)) '() (iota 10))
=> (11 10 9 8 7 6 5 4 3 2)

こうした技術を使うと、重い処理や無限に続く処理などを適当なところで止めておいて、必要に応じて再開することができる。また、もっと対称的に2つの処理がお互いの継続を呼び合うような方法を考えることもできる。これらは実行順や範囲を意識的に制御される平行処理のようなものを実現する。

(define (coroutine-1 cont)
  (let loop ((i 3))
    (if (>= i 0)
      (begin (display `("c-1" ,i))
             (newline)
             (set! cont (call/cc cont))
             (loop (- i 1))))))

(define (coroutine-2 cont)
  (let loop ((i 0))
    (if (< i 4)
      (begin (display `("c-2" ,i))
             (newline)
             (set! cont (call/cc cont))
             (loop (+ i 1))))))

それぞれの (set! cont (call/cc cont)) ではその時点での自身の継続を引数に相手の継続を呼び出し、帰ってきた相手の継続をcontに束縛している。

> (coroutine-1 coroutine-2)
(c-1 3)
(c-2 0)
(c-1 2)
(c-2 1)
(c-1 1)
(c-2 2)
(c-1 0)
(c-2 3)

まとめと参考文献

Schemeではファーストクラスの継続を簡単に取り出して利用することができる。継続を使うと、プログラムを任意の時点で中断したり、再開したりすることができる。そのため、大域脱出や例外処理、ジェネレータやコルーチン、探索時のバックトラッキングなど、複雑な制御を比較的簡単に実現することができる。

ここまで継続について学んだことをまとめてみた。あまり実用的な例を紹介することはできなかったが、もし自分のような勉強中の方の参考になったらさいわいだ。最後に、参考にしたサイトや本を紹介しておきたい。ここで紹介したコードの多くは、これらの参考文献をもとに書かれている。より進んだ内容や、より正確な内容が知りたい方は参照してほしい。

call-with-current-continuation
Scheme/継続の種類と利用例 - Wikibooks
使いたい人のための継続入門
なんでも継続
独習 Scheme 三週間 Teach Yourself Scheme in Fixnum Days (Chapter 13, 14)
もうひとつの Scheme 入門 (16, Appendix 3)
On Lisp (20-23)
R7RS 日本語訳 (報告書 P49-52)

Schemeによる記号処理入門 | 森北出版株式会社
O'Reilly Japan - プログラミングGauche

Schemeの紹介と内包表記マクロ

LispとS式

SchemeCommon LispのようなLisp系言語の強みは強力なマクロ機能にある。LispではプログラムはS式と呼ばれる形式で記述され、それは、Lispがデータとして扱うリストと全く同じ構造を持っている。そのため、LispがデータとしてLispのプログラムを簡単に処理できるのだ。マクロを使うと、特定の問題に特化した、新しい言語とさえ呼べるような機能 (DSL) を簡単に作成して使うことができる。

Schemeのプログラムは基本的にはすべて以下のような構造を持っている。これ自体がS式であり、関数や引数の部分にはまたS式を入れることができる。関数の呼び出しでは引数は先に評価されて関数に渡されるが、マクロでは評価前の式がそのまま渡される。

(関数 引数 引数 ...)
(+ (apply * (iota 10 1)) (square *e*)) ; プログラムの例
1 ; 括弧なしの1つの式もS式

Schemeとマクロ

Schemeにはマクロ展開時の変数名の衝突を自動的に回避してくれる健全なマクロが用意されている。(意識的に衝突を起こしたり、展開時の環境に変数を束縛したりしたい場合は、処理系によっては、explicit renamingによるマクロやdefine-macroによるマクロなども利用できたりする。) syntax-rulesは独自のパターンマッチ言語を使ってコードを置き換える感じなので、簡単だがScheme自体でリストを操作していないという不満もあるらしい。R7RS-largeで入るとうわさされているexplicit renamingによるより低レベルなマクロではリストをより直接操作できる。

最近の言語では大抵用意されていたりするリストの内包表記。SchemeでもSRFI 42に用意されているが、なんとなく馴染む構文が欲しかったので実装してみた。また、Haskellのように[1..10]みたいにリスト生成したり、Fortranのようにa(2:5)でリストのスライスが欲しかったりしたのでこれも書いてみた。

(import (scheme base) (srfi 1))

; リスト生成マクロ
(define-syntax l:
  (syntax-rules (..)
    ((_ e) (l: 0 .. (- e 1)))
    ((_ s .. e) (if (> e s) (l: s (+ s 1) .. e) (l: s (- s 1) .. e)))
    ((_ s t .. e) (let ((diff (- t s)) (cp (if (> t s) > <)))
                    (let loop ((l `(,s)) (c t))
                      (if (cp c e) (reverse l) (loop (cons c l) (+ c diff))))))))

; リストのスライスを取るマクロ
(define-syntax l/s
  (syntax-rules (:)
    ((_ l s : e) (l/s (l/s l : e) s :))
    ((_ l s :) (drop l s))
    ((_ l : e) (take l (+ e 1)))
    ((_ l i) (list-ref l i))))

; 内包表記マクロ
(define-syntax l/c
  (syntax-rules (: <- .. :=)
    ((_ lm : (x <- xs) lc ...) (apply append (map (lambda (x) (l/c lm : lc ...)) xs)))
    ((_ lm : (x <- s .. e) lc ...) (l/c lm : (x <- (l: s .. e)) lc ...))
    ((_ lm : (x <- s t .. e) lc ...) (l/c lm : (x <- (l: s t .. e)) lc ...))
    ((_ lm : (d := ds) lc ...) (let ((d ds)) (l/c lm : lc ...)))
    ((_ lm : c lc ...) (if (not c) '() (l/c lm : lc ...)))
    ((_ lm :) `(,lm))))

実行例。

; 直角3角形を作る10以下の自然数の組とその面積
(l/c (list a b c area) : (a <- 1 .. 10) (b <- 1 .. a) (c <- 1 .. b) (= (* a a) (+ (* b b) (* c c))) (area := (/ (* b c) 2)))
=> ((5 4 3 6) (10 8 6 24))
; リストの生成
(l: 10) => (0 1 2 3 4 5 6 7 8 9)
(l: 1 .. 3) => (1 2 3)
(l: 2 4 .. 10) => (2 4 6 8 10)
; スライス
(l/s '(1 2 3 4 5) 1 : 3) => (2 3 4)
(l/s '(2 4 6 8 10) 2 :) => (6 8 10)

引数の評価については考えていないが、副作用を使わなければ大丈夫なはず。とりあえず動くので良しとしよう。こんな風に簡単に言語機能自体を拡張できるのを見るとやっぱりLispは楽しいと思う。

SchemeCommon Lisp

SchemeCommon Lispは現在でも広く利用されているLispの2大方言で、それぞれにたくさんの実装が存在する。もしかするとLispというとインタプリタのイメージが強いかもしれないが、コンパイラの実装もたくさんある。SBCLなどはコンパイルすればC並みの速度が出るのではないだろうか。Common Lispは使える機能は最初からとりあえず全て用意した大きな仕様で、Schemeは逆に(そこから全てを構成できる)より小さな機能を用意している気がする。ただ、Schemeは最初から継続が使える。また、Common Lispでは変数と関数の名前空間が分かれているのに対してSchemeではそれが同一なのも大きな違いだ。Schemeは変数と関数を同じように扱えるので関数の定義や高階関数も変数と同様に扱える。

(define *e* 2.718281828459045)
(define square (lambda (x) (* x x)))
(define (apply-f f x) (f x)) ; 関数定義用の構文も用意されているが、意味は無名関数の定義と束縛と同じ
(apply-f square *e*) => 7.3890560989306495

R7RSとSRFI

Schemeの最新の規格はR7RSで、R7RS-smallが2014年に策定され、R7RS-largeの策定作業が2017年現在も進められている。また、SchemeにはSRFIと呼ばれる標準ライブラリの規格があり、処理系が対応していれば利用できる。R7RSに対応した処理系は色々あるが、個人的におすすめなのは以下の3つ。

  • Gauche : 実用的な独自の拡張機能が充実している。
  • Sagittarius : SRFIへの対応度が高い気がする。
  • Chibi-Scheme : R7RSの策定グループの1人が作った参照実装なので、仕様を確認したい時に使える気がする。ただ深い再帰で止まってしまう。