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
Vimのコマンド
Vimの紹介
ブログに書けば忘れない気がする。VimはUnix系の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では名前付きのバッファを使うことができ、名前を指定してヤンクやプットすることができる。コードが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つのスクリーンの時と同じように操作できる。
VimとAtom
コードを書くのにずっとEclipseとVimを使ってきたのだが、最近Swiftを書いてみたくなったのをきっかけにXcodeも使いはじめた。そうしたら新しいエディタも色々と試してみたくなった。
Sublime Text、Light Table、Brackets、Atomなどなど、Vimのかわりに使ってもいいかなと思えるくらい高機能で拡張性にも優れたエディタが最近では色々と開発されているらしい。ここではAtomを使ってみることにした。AtomはGitHubがつくったエディタで基本的にC++とCoffeeScriptで書かれているらしい。コミュニティによって開発された拡張パッケージを追加していくことで、IDEのような機能も追加していくことができる。
言語のシンタックスなどはlanguage-haskellなどの名前のパッケージでだいたい提供されているようだ。最初に入れてみた言語対応以外のパッケージは以下のようなもの。
少し重いのとアップデートのたびに色々な拡張パッケージが動かなくなったりするらしいのが難点だが、綺麗だし高機能だし直感的に使えるし、vim-mode-plusを入れれば操作性もVimとそんなに変わらないので気に入った。しばらく使ってみようと思う。
