Clojure(1.3-1.4)のリスト/ベクタ(シーケンス)操作関数一覧

　何回使っても、気づいたら、忘れてしまうリスト/ベクタ系関数について調べたメモ。
Clojureでは、プログラムの大半はシーケンス操作になる可能性が高い為か、Clojureのシーケンス操作関数は、かなり充実していますが、たくさんありすぎて、使いこなせているか不安になります。オフィシャルのリファレンスに関数一覧が乗っていますが、リストとベクタの操作に限定してまとめました。
　ちなみに、リスト, ベクタ ⊆ シーケンスです。
zip(木構造), hashmap等は扱いません。

以下の9種類に大別。62個について調べました(まだあるかもしれません)。

1. 生成系(7)
2. cons系(3)
3. getter系(21)
4. observer系(8)
5. map系(6)
6. reduce系(2)
7. filter系(3)
8. リスト再構築(8)
9. リスト並び替え(4)

生成系

　遅延シーケンスを生成する。

list

　引数列のリストを返す。

(list 1 2 3) => (1 2 3)

(list "a" 2 [72 71] 'u) => ("a" 2 [72 71] u)

range

 自然数列のリストを生成する。

(range) => (0 1 2 3 ...　無限に続く。

(range 1 10) => (0 1 2 3 4 5 6 7 8 9 10)

repeat

　引数に与えられた要素を繰り返したリストを返す。

(repeat "val") => ("val" "val" "val" "val" ... ... 無限に続く。

(repeat 4 "val") => ("val" "val" "val" "val")

repeatedly

　引数に与えられた関数の実行結果を要素とするリストです。repeatが動詞でrepeatedlyが副詞なのは、それぞれ名詞と動詞を引数に持つからですか。

(repeatedly #(rand-int 10)) => (4 5 8 8 6 2 0 7 7 2 ... ... 無限に続く。

cycle

　引数に与えられたリストの要素を繰り返したリストを返す。

(repeat [1 2 3]) => (1 2 3 1 2 3 ... ... 無限に続く。

iterate

　n番目の要素が、xに対してn回fを適用したものであるリストを返す。x, f(x), f(f(x)) ... のリストを返す。

(iterate dec 0) => (0 -1 -2 -3 -4 -5 -6 ... ... 無限に続く。

for

　リスト内包表記(List Comprehension)です。:letは、内包表記内での変数定義、:whenはフィルターです。表記内で与えられたリストから別のリストを生成します。PythonやHaskellのList Comprehensionとくらべて、理解しづらいです。

(for [x [1 2 3] y '(a b c)] [x y]) => ([1 a] [1 b] [1 c] [2 a] [2 b] [2 c] [3 a] [3 b] [3 c])

(for [x [1 2 3] :let [y (* x x)]] y) => (1 4 9)

(for [x [1 2 3 4 5] :when (even? x)] x) => (2 4)

seq

　一部のデータ型をリストへキャストする。キャストできないものはエラー。seqは、遅延シーケンスではなく、通常のシーケンスを生成する。

(seq '()) => nil

(seq "abc") => (\a \b \c)

cons系

　リストを構築する。

cons

　先頭に与えられた要素を加えたリストを返す。

(cons 'a '(b c d)) => (a b c d)

(cons 1 [2 3 4]) => (1 2 3 4)

(cons [1] [2 3]) => ([1] 2 3)

conj

　シーケンスに、要素を加えたものを返す。consとの違いは、consが必ずリストの先頭に加えられるのに対して、conjは、リストやベクタによって新たな要素が加えられる位置が変わってくるという点。一番追加しやすい場所に追加されるようです。要素の順番に依存しないシーケンスを扱う時に使います。

(conj 1 [2 3 4]) => [2 3 4 1]

(conj 1 '(2 3 4)) => (1 2 3 4)

concat

　複数のシーケンスをすべて結合する。

(concat [1 2 3] [2 2 3]) => [1 2 3 2 2 3]

(concat [1] [2] [3]) => (1 2 3)

getter系

　シーケンスから要素を取り出す。

first/ffirst

 シーケンスの先頭の要素を取り出す。古いLisp系言語のcarに相当します。/シーケンスの先頭の先頭の要素を取り出す。古いLisp系言語のcaarに相当します。

(first [3 2 1]) => 3
(ffirst [[1 2 3] [2 2 3]]) => 1

second

　シーケンスの二番目の要素を取り出す。古いLisp系言語のcadrに相当します。

(second [1 2 3]) => 2
(second [1]) => nil

nth

　シーケンスのn番目の要素を取り出す。インデックスは0から始まります。

(nth [1 2 3] 2) => 3
(nth [1 2 3] 0) => 1

rand-nth

　リストからランダムに要素を選んで取り出す。

(rand-nth [:a :b :c]) => :a
(rand-nth [:a :b :c]) => :b

rest/ntresth

　リストの先頭の要素を除いた残りの要素を取り出す。古いLisp系言語のcdrに相当します。/リストのn番目の要素?

(rest [1 2 3]) => [2 3]
(rest []) => []

next/nthnext

　リストの先頭の要素を除いた残りの要素を取り出す。restとの違いは、リストの末尾に到達した時に、[]を返すのがrest、nilを返すのがnext。/リストのn番目までの要素を除いた残りの要素を取り出す。
(next [1 2 3 4]) => (2 3 4)
(next [1]) => nil
(nthnext [[1 2] [3 4 5] [6 7 8]] 2) => ([6 7 8])

fnext/nnext

　先頭を除いたリストの先頭の要素を取り出す。(fnext x) = (first (next x))/リストの先頭2つの要素を除いた残りの要素を取り出す。(nnext x) = (next (next x))
(fnext [[1 2] [3 4 5]]) => [3 4 5]
(nnext [[1 2] [3 4 5] [6 7 8]]) => ([6 7 8])

take/take-while/take-last

　先頭からn個要素を取り出す。/先頭から与えられた条件を満たさない要素になるまで取り出す。/末尾からn個要素を取り出す。

(take 3 (range 1 10)) => (1 2 3)
(take-while odd? [1 3 5 6 7 8]) => (1 3 5)
(take-last 3 (range 1 10)) => (7 8 9)

drop/drop-while/drop-last

　先頭からn個要素を省く。/先頭から与えられた条件を満たさない要素になるまで省く。/末尾からn個要素を省く。

(drop 3 (range 1 10)) => (4 5 6 7 8 9)
(drop-while odd? [1 3 5 6 7 8]) => (6 7 8)
(drop-last 3 (range 1 10)) => (1 2 3 4 5 6)

last/butlast

　最後の値を取り出す。/最後の値を取り除いたリストを返す。

(last [1 2 3 4 5]) => 5
(butlast [1 2 3 4 5]) => (1 2 3 4)

when-first

　リストの先頭の値をバインドする。
(when-first [a [1 2 3]] (* a 5)) => 5

observer系

リストから情報を取り出す。

count

　リストの要素を数える。lengthではなく、countとなっていて、「長さを計算する」という処理であることを明示的に表している点が良いですね。
(count [1 2 3]) => 3
(count '()) => 0

empty?

　リスト/ベクタが空かどうかを判定する。空でtrue。そうでなければfalse。Schemeにnull?という空リストの判定をする関数があって、Clojureにもnil?という似たような関数がありますが、nil?ではカラリストの判定はできない場合があるので注意。
(empty? []) => true
(empty? (range 1 10)) => false

empty/not-empty

　空のシーケンスを空にして返す。/リストがからであればnilを返す。それ以外の場合は、そのリスト自身を返す。
(empty [1 2 3]) => []
(not-empty [1 2 3]) => [1 2 3]
(not-empty []) => nil

some/not-any?

　与えられた要素を満たす要素が存在するか判定する。/与えられた条件を満たさない要素が存在しないか判定する。　
(some even? [1 1 2 3]) => true
(not-any? even? [1 1 2 3]) => false

every?/not-every?

　すべての要素が条件を満たすか判定する。/条件を満たさない要素が存在するか判定する。
(every? odd? [1 1 1 3]) => true
(not-every? odd? [1 1 2 3]) => true

map系

　mapは、[a, b, c, d, .......]に対して、[f(a), f(b), f(c), f(d), ......]を求めるような関数。

map

　与えられたリストに対して、それぞれの要素に与えられた関数を適用したリストを返す。
(map inc (range 1 10)) => (2 3 4 5 6 7 8 9 10)
(map even? (range 1 10)) => (false true false true false true false true false)

pmap

　 mapの処理を並列(parallel)に実行する。上手に使わないと逆に遅くなることもあります。
user=> (defn fibo[n] (if (< n 2) 1 (+ (fibo (- n 1)) (fibo (- n 2)))))
#'user/fibo
user=> (time (take 10 (doall (map fibo (range 1 30)))))
"Elapsed time: 363.431486 msecs"
(1 2 3 5 8 13 21 34 55 89)
user=> (time (take 10 (doall (pmap fibo (range 1 30)))))
"Elapsed time: 257.508792 msecs"
(1 2 3 5 8 13 21 34 55 89)
user=> (time (take 10 (doall (map inc (range 1 30)))))
"Elapsed time: 0.120742 msecs"
(2 3 4 5 6 7 8 9 10 11)
user=> (time (take 10 (doall (pmap inc (range 1 30)))))
"Elapsed time: 53.420469 msecs"
(2 3 4 5 6 7 8 9 10 11)

mapcat

　引数のリストをconcatしたものに対してmapした結果を返す。

(mapcat sort [[4 5 1 6] [7 8 3 2] [10 9]]) => (1 4 5 6 2 3 7 8 9 10)
(mapcat reverse [[1 2 3] [7 8 9] [4 5 6]]) => (3 2 1 9 8 7 6 5 4)

map-indexed

　mapした要素にインデックスを付ける。

(map-indexed list (range 1 10)) => ((0 1) (1 2) (2 3) (3 4) (4 5) (5 6) (6 7) (7 8) (8 9))

(map-indexed + (reverse (range 1 10))) => (9 9 9 9 9 9 9 9 9)

keep

　mapとほぼ同じ関数ですが、mapが返すリスト列は、nilを含むのに対して、keepは、nilを含まないリストを返します。つまり、 keep .... = (filter not-nil (map ....)のような感じでnil要素をフィルタリングします。
(keep next [[1] [] [2 3] [4 5 6] [] [7 8]]) => ((3) (5 6) (8))

keep-indexed

　keepした要素にインデックスを付ける。
(keep-indexed #(nnext (concat [%1] %2)) [[] [3 4] [] [] [5 6 7]]) => ((4) (6 7))

reduce系

畳み込み処理をします。

reduce

　二項演算をする関数とリストを引数にとり、畳み込み処理をします。
(reduce + (range 1 11)) => 55
(reduce * (range 1 10)) => 362880

reductions

　n回目の畳み込み処理の結果からなるリストを返す。

(reductions + (range 1 11)) => (1 3 6 10 15 21 28 36 45 55)
(reductions * (range 1 11)) => (1 2 6 24 120 720 5040 40320 362880 3628800)

filter系

リストから特定の要素を取り除きます。

filter

　与えられた関数がtrueを返すもののみからなるリストを返す。関数でフィルターします。
(filter even? (range 1 10)) => (2 4 6 8)
(filter next [[2 3] [] [2] [3 4]]) => ([2 3] [3 4])

remove

　与えられた関数がtrueを返すものを取り除く。filterの反対です。
(remove even? (range 1 10)) => (1 3 5 7 9)

(remove next [[2 3] [] [2] [3 4]]) => ([] [2])

distinct

　重複する要素を取り除く。
(distinct [1 2 3 2 3 4 4 5]) => (1 2 3 4 5)
(distinct (take 100 (cycle [1 2 3]))) => (1 2 3)

再構築

シーケンスの要素を分割したり結合したりする。

flatten

　ネストしたシーケンスを平な線形のリストにする。複雑にネストしていても、再帰的に取り出します。
(flatten [[1 2 3] [4 5 6]]) => (1 2 3 4 5 6)
(flatten [[1 2 [3 [4 5 [6]] 7] 8] 9]) => (1 2 3 4 5 6 7 8 9)

partition

　リストをn個づつ分割する。割り切れずに、余った要素は切り捨てる。
(partition 4 (range 15)) => ((0 1 2 3) (4 5 6 7) (8 9 10 11))
(partition 4 3 (range 15)) => ((0 1 2 3) (3 4 5 6) (6 7 8 9) (9 10 11 12))
(partition 4 3 ["pad" "pad"] (range 15)) => ((0 1 2 3) (3 4 5 6) (6 7 8 9) (9 10 11 12) (12 13 14 "pad"))

partition-all/partition-by

　すべて分割する。余った要素は最後に付加する。/条件がtrueとfalseが変わる瞬間で分割する。

(partition-all 4 (range 1 10)) => ((1 2 3 4) (5 6 7 8) (9))
(partition-by odd? [1 1 2 4 5 3 4 4 2]) => ((1 1) (2 4) (5 3) (4 4 2))

split-at/split-with

　n番目で分割する。/条件がfalseになったところで分割する。
(split-at 3 (range 1 10)) =>[(1 2 3) (4 5 6 7 8 9)]
(split-with #(< % 4) (range 1 10)) => [(1 2 3) (4 5 6 7 8 9)]

interleave/interpose

　2つのリストを折り込む。/リストのそれぞれの要素の間に要素を与える。

(interleave (range 1 10) (range 21 30)) => (1 21 2 22 3 23 4 24 5 25 6 26 7 27 8 28 9 29)
(interpose 0 (range 10)) => (0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9)

並び替え系

　シーケンスの要素を並び替える。

reverse

　シーケンスの順序を反転する。

(reverse (range 1 10)) => (9 8 7 6 5 4 3 2 1)
(reverse [1 3 2 4 6 5 7 9 8]) => (8 9 7 5 6 4 2 3 1)

shuffle

　シーケンスをシャッフルする。

(shuffle (range 15)) => [6 7 13 11 5 12 3 1 8 4 10 9 2 14 0]

sort

　シーケンスを並び替える。要素を評価する関数を指定できる。
(sort (shuffle (range 1 10))) => (1 2 3 4 5 6 7 8 9)
(sort > (shuffle (range 1 10))) => (9 8 7 6 5 4 3 2 1)

sort-by

　シーケンスを並び替える。要素の並び替えにつかう値を指定できる。
(sort-by first (map list (shuffle (range 1 10)) (shuffle (range 1 10))))
=> ((1 3) (2 4) (3 9) (4 7) (5 1) (6 2) (7 6) (8 8) (9 5))
(sort-by second (map list (shuffle (range 1 10)) (shuffle (range 1 10))))
=> ((1 1) (5 2) (3 3) (4 4) (9 5) (2 6) (8 7) (7 8) (6 9))

　一通り調べてみた結果、多くを使いこなしてないことが判明しました。orz ...

　(使ってなかったけど)これから使いそうなものから、どのように使うかよくわからないものまで、たくさんあります。maxやminのような引数の中から最大値、最小値を求めるような関数もリスト操作関数に近いですが、厳密にはリストを扱っているわけではないので、今回は省きました。全部網羅できると、スッキリします。

HaskellのパーサコンビネータParsecを使ってみた

※注意: この記事は古い記事です。import周り等、最新versionのparsecライブラリにし追随ていません。一応、2013年(7月10日)当時はこうだったという形で記録として残してあります。(追記: 2017/7/17)

Haskellの勉強がてらParsecを使ってみました。

　コードを眺めただけだと、再帰的下向き構文解析を手で書いているのとあまり変わらないように見えますが、実際に書いてみると非常に簡単ですね。モナド使ってるっていうのが、気に入りませんが。構文解析のコードしか書いてないのに、字句解析器もやってくれます。

　次の文法をS式に書き直すパーサを書いてみました。中置記法を前置記法に変換します。LLパーサなので、左再帰しないように気を使います。
Infix  → Exp
Exp    → Term "+" Exp | Term "-" Exp | Term
Term   → Factor "*" Term | Factor "/" Term | Factor
Factor → ident | number | "(" Exp ")"

さらに、これを変換して、
Infix  → Exp
Exp    → Term Exp*
Exp*   → "+" Term Exp* | "-" Term Exp* | ε
Term   → Factor Term*
Term*  → "*" Factor Term* | "/" Factor Term* | ε
Factor → ident | number | "(" Exp ")"

を構文解析させます。変換したのは、演算子の適用順序を正しくするためです。εは、空を表します。

以下が、コードと実行結果。実行環境はghci 7.4.2。

　Parsecは、ひたすら読めるまで読み続けて、パターンにマッチしない文字列が来たら、エラーを出さずに、マッチした部分の文字列の実行結果を返して、終了するようです。文字列を最後まで読み込み、エラーを出す為には、文法にEOF記号を混ぜる必要がありそうですね。Infix → Exp '$'、みたいな書き方にすればよかったってことでしょうか。

参考文献

• Parsec練習問題 : http://guppy.eng.kagawa-u.ac.jp/Seminar/Haskell/parsec.html
• tinyCの文法をParsecを使って書くというお話。大変勉強になりました。
• [Haskell]Parsecというパーサーライブラリで電卓を作る簡単な方法 : http://bugrammer.g.hatena.ne.jp/nisemono_san/20111117/1321555610
• parsec-3.0.1: Monadic parser combinators ,Text.Parsec : http://hackage.haskell.org/packages/archive/parsec/3.0.1/doc/html/Text-Parsec.html
• オフィシャルのドキュメント

Clojureで、Yahoo!の形態素解析APIを使う

・「日本の全エンジニアに捧ぐ！現在公開されているAPI一覧【2013年版】」

という記事を見つけたら、
Yahoo!の形態素解析APIを使ってたのを思い出したので、そのメモ。

Clojureから、Yahoo!のこのAPIを使って、任意の文字列を形態素解析できるようにします。

日本語の形態素解析
・Yahoo!日本語形態素解析API

テキストデータと言えば、青空文庫
・「青空文庫/夏目漱石/それから」

Clojure側ではとりあえず、

1. httpのリクエストを送リ、データを受け取る。
2. データをClojureの内部形式(ハッシュマップ、そして、リスト)に戻す。

という2つの処理が出来ればOK。簡単です。

リクエストは、Clojureのhttp-agentというラッパーを使います。

参考 : 逆引きClojure : 特定のURLからドキュメントを抽出する

　Yahoo!日本語形態素解析APIは、XML形式でデータを返してくれます。

　今回は、そのデータを一旦、ローカルに保存して、ClojureのXMLパーサを使って、データをハッシュマップにマッピングします。そこから、必要なデータだけ抜き出して、単語列にします。

以下が実行結果とコード。

user=> (load-file "use-yjma-api.clj")
#'user/tokenizer
user=> (tokenizer kana "誰か慌ただしく門前を馳けて行く足音がした時、代助の頭の中には、大きな俎下駄が空から、ぶら下つてゐた。けれども、その俎下駄は、足音の遠退くに従つて、すうと頭から抜して消えて仕舞つた。さうして眼が覚めた。")
("だれ" "か" "あわただしく" "もんぜん" "を" "はせ" "け" "て" "いく" "あしおと" "が" "し" "た" "とき" "、" "しろ" "たすけ" "の" "あたま" "の" "なか" "に" "は" "、" "おおきな" "まないた" "げた" "が" "そら" "から" "、" "ぶらさがり" "つて" "ゐ" "た" "。" "けれども" "、" "その" "まないた" "げた" "は" "、" "あしおと" "の" "とおのく" "に" "じゅう" "つて" "、" "すう" "と" "あたま" "から" "ぬき" "し" "て" "きえ" "て" "しまい" "つた" "。" "さ" "う" "し" "て" "め" "が" "さめ" "た" "。")
user=> (tokenizer kanji "誰か慌ただしく門前を馳けて行く足音がした時、代助の頭の中には、大きな俎下駄が空から、ぶら下つてゐた。けれども、その俎下駄は、足音の遠退くに従つて、すうと頭から抜して消えて仕舞つた。さうして眼が覚めた。")
("誰" "か" "慌ただしく" "門前" "を" "馳" "け" "て" "行く" "足音" "が" "し" "た" "時" "、" "代" "助" "の" "頭" "の" "中" "に" "は" "、" "大きな" "俎" "下駄" "が" "空" "から" "、" "ぶら下" "つて" "ゐ" "た" "。" "けれども" "、" "その" "俎" "下駄" "は" "、" "足音" "の" "遠退く" "に" "従" "つて" "、" "すう" "と" "頭" "から" "抜" "し" "て" "消え" "て" "仕舞" "つた" "。" "さ" "う" "し" "て" "眼" "が" "覚め" "た" "。")

• app-idには、yahooから与えられたアプリケーションIDを記述します。
• (平)仮名と漢字を選べます。(XMLデータには、両方の結果があります)
• リクエストの日本語のエンコードには、java.net.URLEncoder/encode
• take-tokensは、ネストしたハッシュマップから、単語の列を生成する。

こんな感じで、テキストデータが単語単位に分割できました。

trampolineでバックトラックパーサを作る

shift/resetと、(fnで囲った)closure/trampolineは、なんとなく似てます。

trampoline

trampolineは、末尾再帰をエミュレートする為の関数です。

clojureは、末尾再帰ができないので、loop-recur特殊形式で
ループを記述するのですが、これは、ほとんどJavaやCのwhile文か、
それ以下の表現力しかありません。
なので、相互再帰とか、複雑な末尾再帰は表現できません。

その代替手段としてtrampolineという関数があります。
以下のように使います。

1. まず、普通に末尾呼出形式で関数型言語風のプログラムを書きます。
2. 次に、その末尾呼出を全部無名関数で囲ってクロージャにします。
3. トランポリン関数の上で、相互再帰の関数を呼び出します。

トランポリンは、与えられた関数とその引数を起動して、関数を実行します。
関数の実行結果として、

1. クロージャが戻ってきたら、(それは、末尾呼出なので)そのクロージャを再び実行。
2. それ以外の値が戻ってきたら、終了。

これで、スタックを消費せずに、末尾再帰が、特に相互再帰のような
複雑な末尾再帰も実現できるという事で、非常にめでたいのですが。

この末尾呼出で戻ってきたクロージャってもしかして、
trampolineが終了するまでの残りの計算　 ... .... (限定)継続!?

というわけで、概念的に、というか理論的にどうなのかはわかりませんが、
直感的には、かなり似たものだという印象です。

trampolineがresetに対応していて、
「shiftが呼ぶ限定継続」が、「末尾再帰で送り出されるレキシカルクロージャ」に対応している、
と、考えます。

その証拠というか、例として、shift/resetの得意なバックトラックを
trampolineを使って簡単に書くことができます。
その例として、パーサ(構文解析器)を書きました。

バックトラックパーサ

バックトラックとは、その名の通り(?)後戻りをする機構のことです。構文解析とは、結局のところ、文法法則を(終端)記号列に対してうまく当てはまるかどうかを試すアルゴリズムに過ぎません。なので、当てはまりそうだったら、適当に当てはめてみて、ダメだったら、元に戻すというやり方でもOKなのです。(もちろん、それ相応の計算量がかかりますが。)
なので、適当にパターンマッチを繰り返して、辻褄があわなくなったらその時点まで戻るようなパーサを書くことができます。それがバックトラックパーサです。
で、今回のこの末尾呼出のクロージャを限定継続に見立てて、パターンマッチに失敗したら、この限定継続もどきを呼び出すことでバックトラックを実現します。

次の文法をParseするプログラムにしました。

E → T '+' E
T → F '*' T
E → T
T → F
F → num

backtracparser.clj


実行結果と利用例は、こんな感じ。
ちゃんと構文解析しています。
parse-with-stack-traceで、バックトラックしていることも確認出来ます。

user=> (load-file "backtrackparser.clj")
#'user/parse-with-stack-trace
user=> (parse [[:num] [:+] [:num] [:*] [:num] [:$]])
[:E :+ [:E [:T :* [:T [:F [:num]]] [:F [:num]]]] [:T [:F [:num]]]]
user=> (parse-with-stack-trace [[:num] [:+] [:num] [:*] [:num] [:$]])
[]
([:num])
([:F [:num]])
... ...
([:$] [:E [:T [:F [:num]]]] [:*] [:F [:num]] [:+] [:T [:F [:num]]])
back track !!
([:T :* [:T [:F [:num]]] [:F [:num]]] [:+] [:T [:F [:num]]])
([:E [:T :* [:T [:F [:num]]] [:F [:num]]]] [:+] [:T [:F [:num]]])
([:E :+ [:E [:T :* [:T [:F [:num]]] [:F [:num]]]] [:T [:F [:num]]]])
([:$] [:E :+ [:E [:T :* [:T [:F [:num]]] [:F [:num]]]] [:T [:F [:num]]]])
[:E :+ [:E [:T :* [:T [:F [:num]]] [:F [:num]]]] [:T [:F [:num]]]]

うーん、gistとブログの色合いが微妙......

ラムダ計算のYの使い方と不動点コンビネータの違い

1.YCombinatorの使い方

ハスケルのYコンビネータ
Y　≡　(λg. (λx. g(x x)) (λx. g(x x)))

は以下のように簡約されていき、

β→  (λg. (λx. g(x x)) (λx. g(x x))) f

β→  (λx. f(x x)) (λx. f(x x)))

β→  f((λx. f(x x)) (λx. f(x x))))

β→  f(f((λx. f(x x)) (λx. f(x x)))))

で、
Y' ≡(λx. f(x x)) (λx. f(x x))
とすると、
Yf ≡ fY' ≡ ffY' ≡ fffY'
みたいな感じに増えていきます。

引数として与える関数fは、
f = λhy. if condition? then <終了時の処理など> else <再帰呼び出しなど>
のようにして書きます。

・この時、f = h(つまり、再帰呼び出し的な自分自身)だと考える。
・上のラムダ抽象の変数yは、ラムダ抽象が表す関数の引数だと考える。

再帰呼出風に書くとちゃんとループになるというわけです。

Yコンビネータは、Yf ≡ fY' ≡ ffY' ≡ fffY'みたいに増えてい来ます。
しかし、fが表すラムダ抽象は、引数をあたえられた時のβ簡約において、
hを展開させないようにすることで、fffY'のY'を切り捨てます。
結果、ループが止まります。

2.他の不動点コンビネータ

ちなみに、
A ≡(λxy. x y x) (λyx. y (x y x))

このコンビネータは、

β→  (λxy. x y x) (λyx. y (x y x)) f
β→  (λy. (λyx. y (x y x)) y (λyx. y (x y x))) f

β→  (λyx. y (x y x)) f (λyx. y (x y x))

β→  (λx. f (x f x)) (λyx. y (x y x))
β→  f ((λyx. y (x y x)) f (λyx. y (x y x)))
β→  f ((λx. f (x f x)) (λyx. y (x y x)))

β→  f (f ((λyx. y (x y x)) f (λyx. y (x y x))))

でやっぱり、

A' ≡(λyx. y (x y x)) f (λyx. y (x y x))
とすると、
A f ≡ fA' ≡ ffA' ≡ fffA'
みたいな感じに増えていきます。

Θ ≡ (λxy. y(x x y)) (λxy. y(x x y))
これは、「チューリングの不動点コンビネータ」と呼ぶようです。

β→  (λxy. y(x x y)) (λxy. y(x x y)) f

β→  (λy. y((λxy. y(x x y)) (λxy. y(x x y)) y)) f
β→  f ((λxy. y(x x y)) (λxy. y(x x y)) f)
β→  f ((λy. y((λxy. y(x x y) (λxy. y(x x y) y)) f)

β→  f ( f((λxy. y(x x y) (λxy. y(x x y) f)

でやっぱり、

A' ≡((λxy. y(x x y)) (λxy. y(x x y)) f)
とすると、
A f ≡ fA' ≡ ffA' ≡ fffA'
みたいな感じに増えていきます。

違いというか、簡約された結果だけ見ると、全部同じですね。
与えられたラムダ式fを内包して増加増幅していきます。

文脈自由文法で文脈自由文法の記法を定義してみる。

文脈自由文法の記法は、自己言及的に記述すると以下のように書ける筈です。

CFG → pattern CFG
CFG → pattern

pattern → NTE "→" rightside

rightside → NTE
rightside → TE
rightside → NTE rightside
rightside → TE rightside

NTE → ident
TE → string

　この時、identは変数を表す文字列、stringは文字列を表す文字列とします。上記の略称はそれぞれ、
CFG = Context Free Grammer = 文脈自由文法、
NTE = None Terminal Expression = 非終端記号、
TE = Terminal Expression = 終端記号です。

　こう書ける筈なんだけど、実際にこんな定義は、教科書でもネットでも見たことない。間違ってるのかな? それとも、あまりに下らないので、誰も書かないだけなんだろうか、とか思って、Wikipediaとか読んで、思い出してたのですが。

　文脈自由文法の形式的な定義は、

G = (V, Σ, R, S)のタプルで、
Vは、非終端記号の有限集合
Σは、終端記号の有限集合
Rは、生成規則の集合
Sは、開始記号(生成される木構造のトップ)

で表されるんだそうです。
　そこで、生成規則の定義なのですが、

v → w

で、定義されて、v∈V, w∈(V∪Σ)*で表されるのだそうです。あっさりしてますね。

　確かにこれと比べたら、冒頭の定義は、無駄に長ったらしいです。
　ただ、文脈自由文法が文脈自由文法で表せるなら、プッシュダウンオートマトン上に別のプッシュダウンオートマトンが作れるってことでしょうか。なんだかチューリングマシンみたいで、面白いですね。

プログラム運算

(2015/01/07修正)

　プログラム運算というのがあるらしい。
最初に見た時は、演算のtypoかと思ったけど、それとは違うらしい。
英語では、「calculational programming」というらしい。
プログラムの最適化手法の一種で、あるプログラムをプログラムの意味を変えずに、変換していくことでより効率的なプログラムに書き換える手法なのだそうです。この手法とコンパイラにおける最適化との違いは、アルゴリズム(抽象)レベルで最適化するか、変換後のコードを最適化するかという違いのようです。

エレガントで綺麗なコード(ただし遅い) → 高速なコード(ただし、汚く読みにくい)

「→」は「数学的理論(プログラム意味論)に基づいた変換」です。
速度的な面から見た、プログラム/アルゴリズムのリファクタリングってことなのかな？

例えば、関数型言語で記述された(速度を考慮していない)フィボナッチ数列を返す関数は、数学的な表現をそのまま表すこができ、非常に綺麗ですが、重たいです。それを、プログラムの意味を数学的な表現に落とし込み、数学的に変形する(もちろん、高速化されることは大前提という)ことで、数学的な等価性から、プログラムの等価性を証明するってことのようです。 (フィボナッチ数列の計算が運算によって高速化できるのかはわかりません.)
最適化すると同時に、その最適化が適切であることを証明する(保証する)ことができると。
　ちなみに、この変換自体は、基本的に人が手で行う模様…… 
(以下, 2015/01/07追記)
 ある意味では, 関数型言語の実行速度のチューニングの一種と言えるのかもしれませんね.

 基本的に手作業に勝るプログラム運算はありませんが, 自動化するシステムもいくつか開発されているようです. 日本語で読める書籍としては, 少なくとも以下の二冊があります(他にもあるかもしれませんが).

• 関数プログラミングの楽しみ, Jeremy Gibbons & Oege de Moor(編集), 山下 伸夫 (翻訳)
• 関数プログラミング入門 ―Haskellで学ぶ原理と技法―, Richard Bird (著), 山下伸夫 (翻訳)

 『関数プログラミング入門』については, 自動運算器の解説があります. 『関数プログラミングの楽しみ』でも, 同様に運算(融合変換)の自動化とその実装例であるMAGシステムの説明がありました.

 手作業で出来る簡単な例として, このブログでは, map分配則と, hylomorphismについて紹介しています.

　以下の文献が見つかりました。まだ、読んでないのですが。
参考文献

定理証明支援系 Coq を用いたプログラム運算

融合変換による関数プログラムの最適化

構成的アルゴリズム論

ラムダ計算の使い方

　ラムダ計算の公理とかはすっ飛ばして、ラムダ計算で実際にどうプログラムを組めるのかをまとめてみました。ラムダ計算による数値の扱い、条件分岐、論理式、ループ構造、そしてリスト構造の作り方について説明します。

　ちなみに
β→はβ簡約、
λx.xはラムダ抽象、
M Nは、式の適用です。
=は、ここでは、同値を表す表現とします。
適宜applyの優先順位を表す為に括弧を用います。
例えば、λabc. x y zなど、ラムダ抽象は簡単のため、カリー化される前のた式として表します。(訂正 2016/05/02, λabc. x y z = λa.(λb.(λc. x y z))という意味です。)

1.チャーチ数

　まず、最初は数値です。チャーチ数とは、ラムダ式で自然数を表現する方法です。ラムダ計算は、数値を扱うことができないように見えますが、ちゃんとした（？）数値計算を自身の計算体系のみで表現することができます。

　まずは、数値の定義方法から紹介します。

　0と1は、次のようにして定義します。

0 = λfx. x

1 = λfx. f x

　ラムダ抽象の中で何回fがapplｙされるかで、数値を表します。2以降は、

2 = λfx. f (f x)

3 = λfx. f (f (f x))

4 = λfx. f (f (f (f x)))

n = λfx. f ( ... (f x) ...)  (fがn個)

........

　以上のようにして表現します。これだけだと表現しているだけですね。なぜ、このように表現するのか、必然性が無いと感じられるかも知れません。

　しかし、これに数値計算方法を組み合わせると面白くなってきます。

　加算は、次のように表します。

plus = λmnfx. m f (n f x)

　なんとなくイメージがつかめると思います。mとnが足し合わせる値です。mの内側にnを突っ込むようなイメージです。元の数値表現に戻ることが確認できるかと思います。
　こんな感じです。

意味 : 1+2

(plus 1 2)
β→  (λmnfx. m f (n f x)) (λfx. f x) (λfx. f (f x))

β→  (λnfx. (λfx. f x) f (n f x)) (λfx. f (f x))

β→  (λfx. (λfx. f x) f ((λfx. f (f x)) f x))

β→  (λfx. (λx. f x) ((λfx. f (f x)) f x))

β→  (λfx. f ((λfx. f (f x)) f x)))

β→  (λfx. f ((λx. f (f x)) x)))

β→  (λfx. f (f (f x)))

=3となります。

　乗算も簡単です。

mult = λmn. m (plus n) 0

　ラムダ抽象mが囲っているそれぞれのfに対して、plus nを適用して展開させます。
　最後に指数です。mのn乗とは次のように記述します。

exp = λmn. m (mult n) 1

　乗算と同じ考え方で、指数も表現出来ました。

　次に、定番なので、インクリメントを表す関数とデクリメントを表す関数を書いてみます。
　インクリメントを表す関数succは、以下のように定義できます。succという名前はペアノの公理に由来します。

succ = λnfx. f(n f x)

　デクリメントを表す関数predは、以下のように定義できます。ちょっと複雑ですね、理解に苦しみます。

pred = λnfx. n (λgh. h (g f)) (λy. x) (λy. y)

意味 : 2 - 1

pred 2
β→  (λnfx. n (λgh. h (g f)) (λy. x) (λy. y))(λfx. f (f x))

β→  (λfx. (λfx. f (f x)) (λgh. h (g f)) (λy. x) (λy. y))

β→  (λfx. (λx. (λgh. h (g f)) ((λgh. h (g f)) x)) (λy. x) (λy. y))

β→  (λfx. (λx. (λh. h (((λgh. h (g f)) x) f))) (λy. x) (λy. y)

β→  (λfx. (λh. h (((λgh. h (g f))  (λy. x)) f)) (λy. y))

β→  (λfx. (λy. y)(((λgh. h (g f))  (λy. x)) f))

β→  (λfx. (((λgh. h (g f))  (λy. x)) f))

β→  (λfx. ((λh. h ((λy. x) f)) f))
β→  (λfx. f ((λy. x) f))

β→  (λfx. f (x))

　こんな感じでしょうか。括弧を調整しようとすると目がしょぼしょぼします。とりあえず、デクリメントの関数ができたので、これを使って減算ができます。

　減算は次の様になります。

sub = λmn. n pred m

　あっけないです。m-nを表す関数でした。λfx. f(...f(x)...)でネストしてるfをpredに置き換え、xをｍに置き換えています。これにより、predがn回mに対して適用される仕組みです。

 注意 : この方法だと, sub 1 2 を簡約すると0になります. 上記の定義では, 負の数は扱えません.(2015/01/30追記, アンダースタンディング・コンピューテーションより.)

　同様の仕組みで、加算も定義ができます。predのところをsuccに変えるだけです。

plus = λmn. n succ m

2.分岐構造

　いわゆるif-else文をラムダ計算で表すことができます。次のように記述します。

true = λxy. x

false = λxy. y

if = λcxy. c x y

　if は、一番目の式にtrue/falseを表す要素を受け取り、二番目にtrueだった場合の式を受け取り、三番目にfalseだった場合の式を受け取ります。trueは、2つ式を受け取り、受け取った式のうち、前の式を返します。逆にfalseは、後ろの式を返します。これでif-elseが成立しています。trueやfalseが適宜、ifに与えられた不要な式を切り捨てることでうまく表現することができるようになるのです。

if true A Bについて、次のように簡約されていきます。

(((λcxy. c x y) (λxy. x)) A B)

β→  (((λxy. (λxy. x) x y)) A B)

β→  (((λy. (λxy. x) A y)) B)

β→  ((λxy. x) A B)

β→  ((λy. A) B)

β→  A

正しくtrueの方が選択されていますね。

3.論理式

　if-else についてやると今度は、notやandとかorについてもやってみたくなるが人情だと思います(?)。そこで、ラムダ計算でnot, and, orを表してみます。

not = λx. x false true
and = λxy. x y false
or = λxy. x true y
xor = λxy. x (not y) y

　notは、if文と原理的には同じです。andは、第一引数がfalseならfalse、trueなら、第二引数の値を返します。orは、逆で、第一引数がtrueならtrue、falseなら、第二引数の値を返します。なかなか、うまく表現できています。xorは、and, not, orを使っても書けるので、特に必要無いような気もします。

4.数値判定

　数値判定、具体的には、iszero?やequals?について判定するようなプログラムもかけちゃいます。数値表現とtrue/fasleができるようになったので、ここで紹介します。

　まずは、与えられた数値が0かどうかを判定するiszero?から。

iszero? = λz. z (λx. false) true

iszero? 1

β→ (λz. z (λx. false) true) (λfx. f x)

β→ ((λfx. f x) (λx. false) true)

β→ ((λx.  (λx. false) x) true)

β→ ((λx. false) true)

β→ false

　こんな感じでfalseをちゃんと返してくれます。iszero? 0の場合は自明ですね。0は、二番目に与えられたラムダ式を返す式と考えれば良いので、二番目のラムダ式=trueが帰ってきます。

　次に、あんまり扱われることのないequal?について実装してみたいと思います。その前に、mはn以上であるということを判定するgreater than equalについて実装する必要があります。名前は長いので、gte?にしましょう。

gte? = λmn. iszero? (sub n m)

より、equals?は、

equals? = λmn. and (gte? m n) (gte? n m)

だとわかります。

5.ループ構造

　ラムダ計算における、代表的なループ構造は、Yコンビネータと呼ばれるものです。if式と比較して若干難しいかも知れませんが、気のせいです。

Y = λf. (λx. f (x x)) (λx. f (x x))) 

このように定義されるのですが、これに何か値を渡して、β簡約すると面白いことが起きます。

(λf. (λx. f(x x)) (λx. f(x x))) A

β→  (λx. A(x x)) (λx. A(x x)))

β→  A((λx. A(x x)) (λx. A(x x))))

β→  A(A((λx. A(x x)) (λx. A(x x)))))

β→  A(A(A((λx. A(x x)) (λx. A(x x))))))

β→  A(A(A(A((λx. A(x x)) (λx. A(x x)))))))

　一度目のβ簡約では、自由変数fを記号Aに置き換えただけです。しかし、二度目のβ簡約では、先頭のラムダ式のxを後続のラムダ式に置き換えると、何も変化させていないように見えるのですが、実はよく見ると元の形に戻っています。

　(x x)のxを (λx. A(x x))に置き換えています。

　上記のようにして、無限にAを適用出来るため、この形の式がループ構造として用いることができるのです。

　上記の式ではβ簡約をいくら続けても止まりません。無限ループってやつですね。

　一般にこのようなコンビネータを不動点コンビネータ(もしくは、フィックスなど)と呼びます。

　上記の例以外にも次の式もまた、不動点コンビネータです。

Θ = (λxy. y(xxy)) (λxy. y(xxy))

　このようにして、ラムダ計算では、ループを定義します。

　ここで一瞬、普通の再帰呼び出しでもループを定義できるのでは？　と思うかもしれませんが、気のせいです。通常のプログラミング言語の再帰呼び出しの場合、自分自身の参照を呼び出し時にスコープが捉えています。しかし、ラムダ計算では、自分自身に付けられた名前が参照できるのは、それ自身が引数として与えられたラムダ抽象の内側だけです。したがって、ラムダ計算では直接的な再帰呼び出しを使うことができないのです。残念ですね。
　例えば、以下の例で、

(λx. a b c ...) (λy. x y z ...)

　右側のラムダ抽象で再帰呼び出しを行う場合、自分自身の名前を参照したいのですが、参照できるのは、左側のラムダ抽象だけです。こんな感じの違いがあります。

6.素朴なリスト構造

　関数型プログラミングにリスト構造は必須です。というか、リスト構造があれば、他の構造はリスト構造でだいたい間に合います。唯一データ構造的に不可能なのは、ハッシュマップくらいでしょうか。

　Lispでは、car/cdrとconsセルにお世話になっていますが、ラムダ計算においても、基本的にそのスタイルは変わっていません。consで、リストを作って、carとcdrでリストの要素にアクセスするだけです。

　carは、与えられたリストの先頭の要素を取り出します。

　cdrは、与えられたリストの後続の要素を取り出します。

　consは、第一引数を第二引数で与えられたリストの先頭に付加します。

　例えば、ls = (cons 1 (cons 2 '())で、ls = (1 2)のリストが生成されます。これに対して、(car ls) = 1であり、(cdr ls) = (2)です。Lispでcdrは基本的にリストを返しますし、ここでも2を要素に持つリストが帰ってきていますが、別に要素を返しても問題ありません。(注：イコールは同値関係を表しています。)

　ラムダ計算で上記３つのオペレータを表現するわけですが、実に可愛いものです。

car = λx. x true

cdr = λx. x false

cons = λabf. f a b

　これだけで、原理は、if-else式と似ていますね。consでリストの先頭要素と後続要素をエンクロージングして、最後に、carかcdrを与えて要素を取り出します。

　例えば、次のconsとcdrを使うとこうなります。

意味 : (cdr (cons 1 2))

((λx. x false) ((λabf. f a b) 1 2))

β→  ((λx. x false) ((λbf. f 1 b) 2))

β→  ((λx. x false) (λf. f 1 2))

β→  ((λf. f 1 2) false)

β→  (false 1 2)

β→  2

　要素が取り出せていることが確認できるでしょうか。carの場合は、falseがtrueになるだけなので、根本的な違いはありません。

　ところで、このリストには、まだnilが足りません。リストの終端を表してくれる大事な記号です。
この記号と、この記号を判定する関数を用意しましょう。

nil = false
isnil? = λx. x (λabc. false) true

　こんなので本当にnilと判定してくれるのでしょうか……。とりあえず、isnil?に渡された値がnilであれば正確に判定してくれることは見ればわかります。

(isnil? (cons 1 nil))についてテストしてみましょう。

(isnil? (cons 1 nil))
β→  ((λx. x (λabc. false) true) (cons 1 nil))

β→  ((λx. x (λabc. false) true) ((λabf. f a b) 1 nil))
β→  ((λx. x (λabc. false) true) (λf. f  1 nil))

β→  ((λf. f  1 nil) (λabc. false) true)

β→  ((λabc. false)  1 nil true)
β→  false

　若干β簡約の適用順序に一貫性がないような気がしますが、そこは、チャーチ・ロッサー性ってことで勘弁してもらいましょう。isnil?の真ん中にあるラムダ抽象のabcとは、それぞれリストの先頭(car部)、リストの後続(cdr部)、trueを取り除く為のものだったことがわかります。

これでリストの扱いも完璧になりました。

　以上が　ラムダ計算のざっくりとした使い方の解説でした。本当はリストの扱い方の別パターンも書きたかったのですが、それを書いていると書き終わりそうにないので、ココらへんで終わります。

　ラムダ計算を試すのに専用の処理系(ラムダ計算のエミュレータみたいなもの)は、要りません。Scheme(Racket or Gauche)やその他レキシカルクロージャをサポートしている言語で、無名関数をラムダ関数に見立てれば、簡単にエミュレートできます。ただし、簡約のステップを表示させることはできませんが……
((間違いまたは適切な書き方でなかった為、訂正 2013/07/25)　まず、ラムダ計算には、型付きと型なしの2種類あり、型付きのラムダ計算では、上記のような引き算や繰返し構造をそのまま表現することはできません。上記の説明は、型なしのラムダ計算を前提としています。従って、レキシカルクロージャをサポートしていても、型推論をする、HaskellやOCamlのような言語では、直接記述できるのは、加算と乗算など一部の計算だけです。ループに関しては、再帰型を定義することで実装可能になるようです。また、Clojure、SchemeやPythonのようなか動的型付け言語でも、再帰を扱う為には、不動点コンビネータの多相性を保証するようなテクニックが必要で、そのままラムダ式で直接記述できるわけではありません。)
　

参考文献

• 日英のWikipediaのラムダ計算の項目
• ここで扱っている内容の大半はここにあります。
• http://palmstroem.blogspot.jp/2012/05/lambda-calculus-for-absolute-dummies.htm
• equals?の実装など。
• 横内寛文著 『プログラム意味論』、共立出版、1994年

shift/reset

　限定継続という概念(制御構文)があって、これを使うと、バックトラックとかが簡単に実装できるのですが、その動作がやたらややこしい、という話のメモです。

限定継続では、shiftというオペレータとresetというオペレータを用いて、継続を扱います。shiftというオペレータは、継続の呼び出しです(Schemeのcall/ccのようなものです)。それに対して、resetは、その範囲を限定します。
例えば、以下のように使えます。

(+ 1 (reset (+ 10 (shift c (c 100)))))
:;==> 111

ここでは、resetが継続の取得する範囲を区切って、shiftのcに渡します。ここで渡される継続は、(lambda (x) (+ 10 x))の処理です。このラムダ式は、resetが用意してくれるようなイメージです。shiftは、resetで渡された限定継続(= 10を足すという処理)を受け取り、この継続をcにバインドします。call/ccで、継続をバインドするのと同じです。次にバインドされたcに対して、引数100を与えて評価するので、このshiftは、110を返します。その後、resetの外側にジャンプし、最後に1が足されて111と評価されます。
次に別の例です。

(+ 1 (reset (+ 10 (shift c 100))))
;;==> 101

ここでは、resetが継続の取得する範囲を区切って、shiftのcに渡します。 ここまでは、前の動作と同じです。今回も同じように、cに継続をバインドしているのですが、今回は、cを呼び出していないので、このcが切り捨てられます。つまり、10を足すという残りの処理がなくなります。shiftにより、resetのところまで、ジャンプし、結果、shiftが返す値100に1がたされて101と評価されます。
shift/resetが一組の場合は難しくないかと思われますが、shiftが2つ出てきたりすると一気にややこしくなります。
このような例です。

(+ 1 (reset (+ 10 (shift c (c 100)) (shift c 1000))))
;;==> 1001
(+ 1 (reset (+ 10 (shift c (c 100)) (shift c (c 1000)))))
;;==> 1111

上記の例の上の式では、(shift c 1000)が、ばっさりそれまでの式を切り捨てた上で1000と評価されるので、1001が帰ってきます。問題は、下の式ですが、継続渡しスタイルみたいになっているのが面白いですね。

こういうのって、手続き型言語風に書くとわかりやすかったりしますよね。なので、beginを使って表現してみました。Wikipediaの記事と似ていますが、そちらよりは若干原始的です。それぞれの動作とスコープが途切れる前後に数字を割り振っています。
1を出力 → reset → 2を出力 → shift → 3を出力 → 継続呼び出し → 4を出力 → shift終わり → 5を出力 → reset終わり → 6を出力というコードです。

(begin
    (display "1. before reset\n")
    (reset
     (begin
       (display "2. before shift\n")
       (shift cont
              (begin
                (display "3. before call-cont\n")
                (cont 0)
                (display "4. after call-cont\n")))
       (display "5. after shift\n")))
     (display "6. after reset\n"))

上記に対して、以下のような結果を出力します。

1. before reset
2. before shift
3. before call-cont
5. after shift
4. after call-cont
6. after reset

4と5が入れ替わっている以外は、順番どおりに実行されていることが確認できるかと思います。では、なぜ入れ替わったのかという点ですが、上記のプログラムにおいて継続が呼ばれたポイントに原因があります。3と4の間に継続が呼ばれています。なので、5が3と4の間に来ます。ただし、限定継続なので、resetで取得された範囲外にある6は、継続として呼ばれません。

ところで、限定継続は、ネイティブに固有の言語に実装されていません。shift/resetを文法として実装している言語なんてあるんでしょうか？　じゃあ使われてないじゃん、って突っ込まれたのですが、まあ、おそらくその通りかもしれません。ただし、SchemeでマクロとCall/cc(プリミティブの継続)を使えば、shift/resetを実装できるみたいです。『Final Shift for Call/cc: Direct Implementation of Shift and Reset』って、論文にその方法が書いてあります。
こんな感じです。

(define-syntax reset
  (syntax-rules ()
    ((reset ?e) (*reset (lambda () ?e)))))

(define-syntax shift
  (syntax-rules ()
    ((shift ?k ?e) (*shift (lambda (?k) ?e)))))

(define (*meta-continuation* v)
  (error "You forgot the top-level reset..."))

(define (*abort thunk)
  (let ((v (thunk)))
    (*meta-continuation* v)))

(define (*reset thunk)
  (let ((mc *meta-continuation*))
    (call-with-current-continuation
     (lambda (k)
       (begin
         (set! *meta-continuation*
               (lambda (v)
                 (set! *meta-continuation* mc)
                 (k v)))
         (*abort thunk))))))

(define (*shift f)
  (call-with-current-continuation
   (lambda (k)
     (*abort (lambda ()
               (f (lambda (v)
                    (reset (k v)))))))))

以上のコードを定義すると、Racket上でshift/resetの構文が使えるようになります。

上記のコードは、call/ccが多用されてて、読みにくいですが、resetとshiftの実際の使用例に照らし合わせて考えると読みやすくなります。例えば、shiftとresetのマクロですが、それぞれ、引数として渡されている処理をlambda式として囲い、関数形式の*shiftと*resetに渡しているだけです。

まず、*resetは、はじめに(普通の)継続が呼ばれています。ここで取得される継続はresetで囲った処理以降の計算で、それをkで表しています。そして、広域変数*meta-continuation*にresetの範囲が終わった後の処理を記述をset!しています。その処理とは、resetが再帰的に呼ばれることを想定した*meta-continuation*の値のリセットと、残りの計算を実行するようなlambda式です。set!の処理が終わった後、引数として与えられた限定継続の部分を実行します。

実際に実行するのが*abortの役割です。引数なし関数thunkを実行し、結果の値を*meta-continuation*関数に渡します。*meta-continuation*は、resetの後始末をしています。(ここで、let文が使われていて、一瞬、(*meta-continuation* (thunk))でもいいような気がしたのですが、気のせいでした。)

最後に*shiftですが、この*shiftの引数fは、(shift c 100)でいうところの、(lambda (c) 100)です。限定継続をバインドしたlambda式になります。つまり、(f (lambda (v) (reset (k v))))で与えられている、(lambda (v) (reset (k v)))が、限定継続だということです。そして(k v)の呼び出しにより、現在の継続を捨てるようです。この時、(k v)をresetで囲うことでこの時点の継続を*meta-continuation*の確保している継続に対して、上書きします。

数十行程度のコードだったのに、やけに重たかったのは気のせいでしょうか。これを使って実際にどんなバックトラックのコードが書けるのかは、また別の記事に書きます。

Clojureは継続渡しスタイルができない

　Clojureは、末尾再帰最適化ができない言語だというのは知っていましたが、まさか、継続渡しスタイルもダメだったとは。しかし、考えてみれば当然のことで、継続渡しスタイル自体が、末尾再帰最適化を期待している書き方なんですよね。

以下が、証拠のコードです。

(defn +& [a b cont]
  (cont (+ a b)))

(defn empty?& [a cont]
  (cont (empty? a)))

(defn cps-sum [sum ls cont]
  (empty?&
   ls
   (fn[empty]
     (if empty
       (cont sum)
       (+& sum (first ls)
           (fn[sum]
             (cps-sum sum (rest ls) cont)))))))

一見なんの変哲もない継続渡しスタイルのコードですが、スタックが消費されっぱなしになっているのは一目瞭然ですね。ちなみに、このコードは、wikipediaの記事を参考にしました。cps-sumは、引数に与えられたリストの合計値を計算するという、くだらない関数です。

上記のプログラムを実行すると、

user=> (cps-sum 0 (range 0 100) #(println %))
4950
nil
user=> (cps-sum 0 (range 0 10000) #(println %))
java.lang.StackOverflowError (NO_SOURCE_FILE:0)
user=>

こうなります。0～100の和を足している時は、正しい値を返しているのですが、0～1万の値の和を計算しようとすると、スタックオーバーフローになります。

このままでは、面白くないので、これを解決するようなアプローチを考えてみました。こんな感じになりました。

(defn +& [a b cont]
  #(cont (+ a b)))

(defn empty?& [a cont]
  #(cont (empty? a)))

(defn cps-sum [sum ls cont]
  (fn[] (empty?&
   ls
   (fn[empty]
     (fn[] (if empty
       (fn[] (cont sum))
       (fn[] (+& sum (first ls)
           (fn[sum]
             (fn[] (cps-sum sum (rest ls) cont)))))))))))

これを実行すると、

user=> (trampoline (fn[] (cps-sum 0 (range 0 10000) #(println %))))
49995000
nil

こうなります。ちゃんと動いてますね。

末尾呼び出しを全部無名関数で囲って、クロージャにして、トランポリンに送り込むような形にしただけです。オチは特にありません。