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の代数的データ型の表現力はそれに留まらず、文脈を付与されたデータ型に対して、その文脈において意味のある計算を自由に定義し、これを連ねていくことを記述できる。
MonadとMonad変換子
MonadのインスタンスはApplicativeのインスタンスであって、Monad則をみたす必要がある。(Control.Monad)
class Applicative m => Monad m where (>>=) :: forall a b. m a -> (a -> m b) -> m b (>>) :: forall 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と同じもの (つまり値を中に入れるだけで、文脈は操作しない)。
これだけでは何のことかわからないかもしれないが、Monadは元々はプログラムを純粋な関数によって構成しながらも、文脈 (状態) を伴った計算をすっきり記述するために導入されている。これを実現しようとした時、まずは文脈を引数で渡して行くことが考えられるが、常に引数で持ち回すのは煩雑だし、文脈を明示的に意識せず表の計算や計算の構成に集中したいこともある。そこで文脈を型に入れて、背景で自動的に処理される2つ目の計算ラインに移してしまったのがMonadだ。
FunctorやApplicativeとの違いは、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 the correct value!" return x > runMaybeT readPositiveInteger hello => Nothing > runMaybeT readPositiveInteger 1.0 => Nothing > runMaybeT readPositiveInteger 1 thank you for the 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記法だったりする。Monadを使うと純粋な関数のみでも表現力の高い言語内DSLを作ることができるので、そのうちそうした記事も書いてみたい。
実用的なMonad変換子の使い方についてはこちらの記事がわかりやすかった。
http://dev.stephendiehl.com/hask/#monad-transformers
MonadはHaskellの文法によって特殊な地位をあたえられている訳ではなく (構文糖衣doはあるが) 、こうした記述能力は型変数を持つHaskellの代数的データ型と型クラスの能力によって自然に実現されている。
メモ
Haskellのモナドの話には圏論の言葉がよく出てくるのですが、ざっくりとした理解しかできていません。自分の理解をまとめるためにメモを残します。間違っているかもしれないので、鵜呑みにはしないでください。圏論はなんとなく集合論をさらに抽象化したような印象です。
- 圏は対象と、対象から対象への射を持った構造
- 関手はある圏ともう1つの圏の間で、対象を対象に写し、射を射に写す
- その際、恒等な射と、射の結合法則を保存しなければいけない
これは、HaskellのFunctorにあてはめると以下のようになります。
- Haskellのすべての型の値を対象として、関数を射とすることで、圏にできる
- 関手はFunctorの値コンストラクタとfmapで、これで写すことで、Haskellのすべての型の圏はFunctorの圏に対応させることができる
- 関手で写す前後の、恒等な射と、射の結合法則の保存は、Functor則そのもの
fmap id ≡ id fmap (p . q) ≡ (fmap p) . (fmap q)
HaskellのMonadについてはもう少し複雑で、Haskellのすべての型の圏からMonadの圏への関手 (MonadもHaskellの型なので、自分から自分への自己関手になる) が、自然変換を射とすることでまた圏を為し、この関手の圏において、モノイドの性質を持つような対象であるMonadの値コンストラクタ (と自然変換の組) がモナドです。
- Haskellのすべての型の値を対象として、関数を射とすることで、圏にできる
- Monadの値コンストラクタを関手とすることで、Haskellのすべての型の圏はMonadの圏に対応させることができる
- この関手であるMonad (の値コンストラクタ, 以下では省略) に対して、自然変換を射として導入することで、圏にできる
- 自然変換は構造を保存したままMonadをMonadに写すような変換で、ここでは恒等関手をMonadに写すような変換returnと、Monadによって写したMonadを、Monadに写すような変換join
return :: a -> m a -- 自身に対応させる (何もしない) 関手を、mに写す関手に変換していると捉えられる join :: m (m a) -> m a
- returnやjoinはMonadの2重の適用という演算に対して単位元を存在させ、結合法則を成り立たせる必要があり、その時、Monadはモノイドの性質を持ちモナドになる
- この単位元の存在と結合法則の成立がMonad則そのもの
- (モノイドとは2項演算について、単位元が存在し、結合法則が成り立つもの)
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で数値計算
普段はJavaやFortranで数値計算をしているのだが、使える範囲でHaskellも使ってみたくなった。宣言的に書けるのでコードが簡潔になることや、副作用が厳格に管理されている上に、静的な型付けがしっかりしていてコンパイラが賢いので、バグが見つけやすいことなどがうれしい。ただ、自分で管理できるワークステーションならともかく、スパコンにGHCを入れて多次元の流体計算などしたいとなると、どうだろうか。Fortranよりも計算資源を効率的に使えていると説明できないといけないかもしれない。一方で、MathematicaやPythonでやっているような計算の一部は、Haskellでより柔軟に速くできることも多そうだ。ここでは、よく使われる簡単なアルゴリズムを書いてみた。
目次
準備と方針
処理系はGHC 8.0.2を使っている。また、行列計算のためにhmatrixパッケージを入れた。(ここではcabalを直接使っていますが、状況に応じてStackなどを使ってください。) 行列分解や連立線形方程式を解くアルゴリズムもいずれ紹介してみたい。
> cabal update > cabal install hmatrix
ここでは、そこまで速度やメモリにシビアではない状況を考えている。速度やメモリを気にする場合は、リストの代わりにData.Vector.UnboxedのVector (参照ではなく値の配列で、要素を辿るようなライブラリ関数はFusionが単一のループにしてくれたりするらしい) を使ったりすると良い。使い勝手もリストとそれほど変わらない。
Numeric Haskell: A Vector Tutorial - HaskellWiki
vectorパッケージはhmatrixを入れると付いてくる気がするが、個別にインストールすることもできる。
> cabal update > cabal install vector
また、アルゴリズムの選択は何より性能に影響をあたえると思うが、ここでは見通しを優先して逆行列を計算するライブラリ関数を素直に使っていたりするので、その辺りは必要に応じて適宜修正してほしい。hmatrixの逆行列関数はLU分解で逆行列を計算しているので、1000 1000程度までの行列を数十回計算する程度なら問題なさそうではある。並列計算についてもそのうち紹介してみたい。
4段4次の古典的Runge-Kutta法
まずは連立常微分方程式 (ODE) を解いてみる。4段4次の古典的Runge-Kutta法は簡単で精度や速度もそれなりなので、よく使われている。ただ陽解法なので、問題によっては適さないこともある。その場合、hを小さくしたり可変にしたりしてみて、それでもだめなら、ステップごとに非線形方程式を解くことになるが、1段2次から3段6次程度までの陰的Runge-Kutta法なども使えるかもしれない。
import Data.List (zipWith5) 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 = map ($ ps) dfs k2s = kf 0.5 0.5 k1s k3s = kf 0.5 0.5 k2s k4s = kf 1.0 1.0 k3s kf tc xc ks = map ($ (t + tc*h):zipWith (\x k -> x + xc*h*k) xs ks) dfs 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]
> 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]
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行列 (偏微分係数を並べた行列) に置き換えて、関数とパラメータをベクトル化しただけで、ほとんど同じに書ける。速度が必要な場合はリストをData.Vector.UnboxedのVectorやData.Vector.Unboxed.MutableのMVectorに置き換えて、ランダムアクセスやin placeな書き換えも使うと良いかもしれない。
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 = let (l, _:r) = splitAt i xs in l ++ (x : r) 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 (`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の紹介と内包表記マクロ
LispとS式
SchemeやCommon 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は楽しいと思う。
SchemeとCommon Lisp
SchemeとCommon 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人が作った参照実装なので、仕様を確認したい時に使える気がする。ただ深い再帰で止まってしまう。
vim-plugでSwiftとRustのプラグインを導入
VimにSwiftとRustのシンタックスカラーリングが欲しかったのでvim-plugでプラグインをインストールしてみた。Vimのプラグインマネージャは色々つくられているけれど、vim-plugはファイル1つで導入でき、記法もシンプルで軽いようです。
GitHub - junegunn/vim-plug: Minimalist Vim Plugin Manager
vim-plug のインストール
GitHubの公式ページに書かれているコマンドをコピペして実行する。プラグインのVimファイルをautoloadディレクトリにコピーするだけ。とても簡単です。
curl -fLo ~/.vim/autoload/plug.vim --create-dirs \
https://raw.githubusercontent.com/junegunn/vim-plug/master/plug.vim
