メモ

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 = \ps -> ps !! (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 (\f -> derivative_p f 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,1.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人が作った参照実装なので、仕様を確認したい時に使える気がする。ただ深い再帰で止まってしまう。

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

プラグインのインストー

1. .vimrcファイルに以下のようなコマンドを追加する。

call plug#begin('~/.vim/plugged')

Plug 'rust-lang/rust.vim' " Rustのプラグインを追加
Plug 'keith/swift.vim' " Swiftのプラグインを追加

call plug#end()

2. vimを起動し、:PlugInstallを実行する。

Plugコマンドでは、GitのURLやレポジトリ名、ファイルへのパスなど色々な方法でプラグインの指定ができるようです。

遅延読み込み

プラグインをたくさんインストールすると、起動が重くなってしまうことがある。そこで、vim-plugでは、特定のファイルタイプが開かれた時や、特定のコマンドが実行された時など、必要に応じてプラグインを読み込むような設定にすることもできる。

call plug#begin('~/.vim/plugged')

Plug 'rust-lang/rust.vim', { 'for': 'rust' } 
Plug 'keith/swift.vim', { 'for': 'swift' }

call plug#end()

プラグインの状態は:PlugStatusで確認できる。

Vimのコマンド

Vimの紹介

ブログに書けば忘れない気がする。VimUnix系のOSなら大抵どこでも最初から入っている軽量なエディタ。普通のエディタと同じように使える入力モードと、コマンドを打つことで操作するコマンドモードがあって、iとEscで切り替えられる。最初は奇妙に感じるかもしれないが、慣れるとコマンドモードでの編集がとても便利なことに気づくはず。

基本コマンド

vi [file] "fileを開く
view [file] "fileを読み込みモードで開く
i "入力モードに (insert)
Esc "コマンドモードに
:w "保存 (write)
:q "終了 (quit)
:e [file] "fileを開く (edit)
:e! "変更をすべて取り消す
:q! "変更をすべて取り消して終了
:wq! "読み込みモードで開いていても書き込んで終了

[]はオプションまたは変数とする。:wと:qで:wqのようにコマンドは大体組み合わせて使える。!を付けると、強制的に実行する意味合いが付加される。また、:付きのコマンドは最後にEnterをタイプする。

:r [file] "現在の位置にfileを読み込み
:![cmd] "シェルのcmdを実行

移動

Vimの強みのひとつは、コードやテキストの構造をある程度理解してくれるので、構造単位で操作ができること。後で紹介する編集コマンドを移動コマンドと組み合わせることで、その範囲のテキストを一気に編集することができる。

←↓↑→ "それぞれ左下上右に移動
hjkl "それぞれ左下上右に移動
w "次の単語に
b "前の単語に
% "対応する括弧に [] () {} などの対の間で移動する
0 "行頭に
$ "行末に
^ "最初の空白でない文字に
{ "前の段落に
} "次の段落に
Ctrl + F "次の画面に
Ctrl + B "前の画面に
gg "1行目に
[num]G "num行目に
G "最終行に

また、コマンドは数字と組み合わせることで繰り返せる。

5j "5行下に移動
7w "7語右に移動

ここまでの機能でも、入力モードしか持たない普通のエディタよりも強力そうな気がしてくる。覚えることは多いが、一度覚えてしまえば操作はとても速くなるはず。

編集

実は入力モードへの切り替えが行われるのはiだけではない。

i "現在の位置から入力
I "行頭から入力
a "次の位置から入力
A "行末から入力
o "次の行から入力
O "前の行から入力
r "1文字を置換 (上書き)
R "置換 (上書き) モードに Escでコマンドモードに戻る
c[移動コマンド] "移動範囲を置換 その範囲の文字が消されて入力モードに
S "行を置換 現在の行が消えて入力モードに
J "次の行と現在の行を連結
~ "大文字と小文字を変換
x "1文字削除
d[移動コマンド] "移動範囲を削除
dd "現在の行を削除

どちらのモードにいるのかわからなくなったら、とりあえずEscを押せばいい。

u "undo 1つ前の変更を取り消す 繰り返せる
Ctrl + R "redo uで取り消した変更を取り消す 繰り返せる
. "直前のコマンドを繰り返す

ここまでくるともう後戻りはできないのではないだろうか。普通のエディタを使っている時にも、Vimのコマンドが使いたくなってしまうかも。

ヤンク (コピー) とプット (ペースト)

コピーとペーストはヤンクとプットと呼ばれている。削除したテキストは自動的にヤンクされておりプットできる。

y[移動コマンド] "移動範囲をヤンク
yy "現在の行をヤンク
p "現在の位置にプット

Vimにはaからzの名前付きのバッファがあり、名前を指定してヤンクやプットすることもできる。コードがVimモードなので"以降がすべてコメントになってしまった。

"[name]y[移動コマンド] "移動範囲をnameバッファにヤンク
"[name]p "nameバッファをプット

検索と置換

ここではregはすべて正規表現が使える。

/[reg] "正規表現regを検索
n "次の一致した検索結果に
N "前の一致した検索結果に
:/[reg] "regを含む行を検索
:g/[reg] "regを含むすべての行を検索
:g/[reg]/d "regを含むすべての行を削除
:s/[reg]/[to] "regをtoに置換
:s/[reg]/[to]/g "現在の行のすべてのregをtoに置換
:%s/[reg]/[to]/g "ファイル中のすべてのregをtoに置換
:noh "検索のハイライトを消す

:コマンドは行の位置や範囲の指定に使うことができる。編集コマンドと組み合わせることで、指定された行の範囲を編集できる。

:[start],[end][編集コマンド] "start行からend行までを編集
:7,$d "7行からファイル末尾までを削除
:0,.y "ファイル先頭から現在の行までをヤンク
:%y "ファイル全体をヤンク

使える正規表現は以下のようなもの。

[0-9] "数字
[a-z] "文字
\+ "1回以上の繰り返し
\{n} "n回の繰り返し
\{n,m} "n回以上m回以下の繰り返し
\s "空白文字
\t "タブ
\n "改行

画面分割とタブ

Vimでも画面を分割したりタブを使ったりできる。

:sp "水平方向に分割
:vs "垂直方向に分割
Ctrl + h "左の画面に移動
Ctrl + j "下の画面に移動
Ctrl + k "上の画面に移動
Ctrl + l "右の画面に移動
:tabnew "新しいタブを開く
:gt "次のタブに
:gT "前のタブに

カーソルがいる時、それぞれの画面やタブは、1つのスクリーンの時と同じように操作できる。

.vimrcファイルの編集

ホームディレクトリに.vimrcファイルを作成することで、Vimの起動時に様々な設定を行うことができる。Vimのインストール先ディレクトリなどにvimrc_example.vimなどがあれば、まずはこれを~/.vimrcとしてコピーすると良い。.vimrcの設定内容についてはいずれ書き足したい。