Comments
Description
Transcript
Free Download: PDF
i
目次
年末年始 Prolog 入門モドキ
1
今夜はお前と俺でマルチパラダイムだからな
11
REAL PROGRAMMER STORY
21
シャロでも分かる！Iteratee 入門
31
計算機肉体派宣言
41
時間を制するものがゲームを制す Game Seeker Vol. 3
47
1
年末年始 Prolog 入門モドキ
ranha
1. 本文書の位置づけ
Prolog の意味論の 1 つ, 宣言的意味論への入門的内容にしたいと思っています. したい…というよりぼくが単に
書き散らかしたかったというのが動機なのですが. Prolog と言えばホーン論理なわけですが, 無理矢理に自然な流
れ (エルブランモデルやらの導入) を作るため, まず 1 階述語論理全般に対する (自動) 定理証明戦略としても使う
ことの出来るスコーレムの基本定理 (エルブランの定理) を証明したいと思います.
後半は普通に Prolog といいますか, ホーン論理を対象にするつもりです.
2. スコーレムの基本定理
スコーレムの基本定理とは次の定理のことです.
定理 1 (等号を含まない) 述語論理で, 文 σ のスコーレム標準形 σ S を ∀⃗
xφ(⃗x) とする. このとき,¬σ が恒真である
ための必要十分条件は,L(φ) のエルブラン領域 U の要素の組 t⃗i (i ≤ k) が存在して,¬φ(t⃗1 ) ∨ ... ∨ ¬φ(t⃗k ) がトート
ロジーになることである. ただし,L(φ) が定数をもたない場合は,U に新しい定数を入れるものとする. (ゲーデル
と 20 世紀の論理学 2 巻 I 章 スコーレムの標準形とエルブランの定理より)
細かい所は抜きにして, この定理の言わんとしていることを無理矢理書くとすると.
この定理は, 述語論理のある文が恒真であることは, 命題論理のトートロジーであることに還元することが出来
る, ということを述べています. ゲーデルの完全性定理を用いれば, 文 σ が証明可能である為にはそれが恒真であ
ることを言えば良いのでした. 更にスコーレムの基本定理を用いることで, 恒真であることを言うには, エルブラ
ン領域のみを考え, そこでトートロジーであるかを調べれば済むという話です.
ここで, 命題論理のトートロジーは決定可能ですから, ¬φ(t⃗1 ) ∨ ... ∨ ¬φ(t⃗k ) の形の論理式を小さい方からどん
どん作り上げて行けば, 「もし文 σ が恒真であったとすると」いつかはこの形の, トートロジーとなる論理式を見
つけられます.
一方, そもそも σ が恒真でないならばどこまでも論理式を作り続けるわけですから, どれだけ計算機をまわして
も…. これは別に悪い話ではなくて, 述語論理はそもそも決定不能であることが分かっているので, 単にそれ以上
のことは出来ないと言っているだけです.
2.1. スコーレム化とスコーレム標準形
PlanetMath.org のスコーレム化のページ1 も参照. スコーレム化とは, 端的に言えば関数記号を新たに導入し言
語を拡張しつつ, 存在量化子の除去を行うものです. 天下り的ですが, 先に冠頭標準形 (prenex normal form , PNF)
を導入しましょう.
1 http://planetmath.org/encyclopedia/Skolemization.html
2
定義 1 量化記号を含まない論理式 φ の前に量化記号を付けた論理式 Q1 x1 Q2 x2 ...Qn xn φ を冠頭標準形という. た
だし,Qi で ∀ または ∃ をあらわす.
定理 2 任意の論理式 φ に対し,φ ↔ φ′ が恒真となる φ の冠頭標準形 φ′ が存在する.
証明 1 適宜論理学の本を参考にしてください (結構大変なので…).
次に, 冠頭標準形をもとにスコーレム化とスコーレム標準形を定義します.
定義 2 (スコーレム化) 論理式 φ の冠頭標準形 φ′ ≡ Q1 x1 Q2 x2 ...Qn xn θ において
• 存在記号がなければ何もしない
• 先頭, つまり Q1 が ∃ であれば,Q1 x1 を消去し, 他の x1 の出現を fresh な定数 c で置き換える. 特にこのよう
な c をスコーレム定数と呼ぶ.
• 最左の存在記号を Qi (ただし i > 1) とする. Qi xi を消去し, 他の xi の出現を f (x1 , ..., xi−1 ) で置き換える.
f は fresh な関数記号である. 特にこのような f をスコーレム関数と呼ぶ.
以上の 3 つに場合分けされた操作をスコーレム化 (の 1 ステップ) とする.
定義 3 (スコーレム標準形) 論理式 φ の冠頭標準形 φ′ ≡ Q1 x1 Q2 x2 ...Qn xn θ に対し, スコーレム化を存在記号が
無くなるまで繰り返し適用して得られた論理式を, スコーレム標準形 (Skolem normal form , SNF) と呼ぶ. 以下
で, 論理式 φ のスコーレム標準形を SNF(φ) であらわすこととする.
さて, 元の論理式とその SNF の間にはどんな関係があるでしょうか? 簡単な例として, 論理式 ∃xp(x) を考えて
みましょう. この論理式の SNF は,p(c) ですね. ここで構造 M を,
• 領域 M = {0, 1}
• M 上の定数記号 c に対して,cM = 1
• M 上の 1 項関係記号 p に対して,pM = {0}
として定義しましょう. 元々の論理式 ∃xp(x) を扱うだけであれば定数は必要ありませんが, スコーレム定数と
して c を導入したので, 構造 M ではこれを付け加えています. いま,M |= ∃xp(x) は明らかですが, 一方 M ̸|= p(c)
となります. よって M |= ∃xp(x) → p(c) ではありません.
ここから論理式とその SNF では同値にならないことが直ちに分かります. 同値にはならないのですが, 次の関
係が成り立つことは証明出来ます.
定理 3 論理式 φ について, φ が充足可能 ↔ SNF(φ) が充足可能である.
証明 2 まず,φ の冠頭標準形を φ′ ≡ Q1 x1 ...Qz xz p(x1 , ..., xz ) とする. φ とその冠頭標準形 φ′ は定理 2 より同値
であることが分かっている. スコーレム化の回数 n について帰納法を用い, n 回適用した結果について必要十分条
件が満たされることを示す. そうすれば,SNF(φ) を得るのに高々z 回の適用で済むので,SNF(φ) が充足可能であ
ることは明らかである.
n=0 の時, すなわち, 一度もスコーレム化を行わない時は自明.
n=m+1 の時を考える. φ′ に m 回スコーレム化を適用した結果は一般に
∀y1 ...∀yi ∃xm+1 Qm+2 xm+2 ...Qz xz p(y1 , ..., yi , xm+1 , xm+2 , ..., xz )
である. 帰納法の仮定より,”φ′ は充足可能 ↔ この論理式が充足可能” である. ここで示すべきは,
φ′ が充足可能 ↔
∀y1 ...∀yi Qm+2 xm+2 ...Qz xz p(y1 , ..., yi , f (y1 , .., yi ), xm+2 , ..., xz ) が充足可能
3
である. (→) を示す. 帰納法の仮定と φ′ の充足可能性より,
∀y1 ...∀yi ∃xm+1 Qm+2 xm+2 ...Qz xz p(y1 , ..., yi , xm+1 , xm+2 , ..., xz )
が充足可能なのでモデル M が存在. この時, 任意の y1 , ..., yi について集合
S = { e | M |= Qm+2 xm+2 ...Qz xz p(y1 , ..., yi , e, xm+2 , ..., xz ) }
が空ではない事は明らか. したがって選択公理を用いて,i 引数関数記号 f の解釈で f M (y1 , .., yi ) ∈ S を満たすよ
うに定義出来る. このようにすれば,
∀y1 ...∀yi Qm+2 xm+2 ...Qz xz p(y1 , ..., yi , f (y1 , .., yi ), xm+2 , ..., xz )
はモデルを持つので (→) は成り立つ.
(←) については明らかである.
■
2.2. エルブラン構造
少なくとも 1 つ定数を持つ言語 L に対し次のようにエルブラン領域とエルブラン基底を定義します.
定義 4 (エルブラン領域 (Herbrand Universe)) L における閉項の全体をエルブラン領域と呼ぶ. L の閉項とは
1. L の定数は閉項である
2. L の関数記号 f について,x1 , ..., xn がすべて閉項ならば f (x1 , ..., xn ) も閉項
3. 以上の繰り返しによって得られるものだけが閉項
として定義される. つまり変数が出現しないような項のこと.
定義 5 (エルブラン基底 (Herbrand base)) L の述語記号と L のエルブラン領域の要素 (すなわち L の閉項) か
らなる原始論理式全体をエルブラン基底と呼ぶ.
定義 6 (エルブラン構造 (Herbrand structure)) 言語 L のエルブラン構造 U とは次のような構造である.
• その領域を, エルブラン領域とする.
• 定数記号 c の解釈,cU = c
U
• 関数記号 f の解釈,f U (tU
1 , ..., tn )) = f (t1 , ..., tn )
• 述語記号 p の解釈 これは適当に与えられていれば良い.
簡単な例として, 言語 L = {c; f ; p} という定数記号 c, 関数記号 f (1-arity), 述語記号 p(1-arity) を持つ言語でエ
ルブラン領域, エルブラン基底, そしてエルブラン構造の例を考えてみます.
• エルブラン領域は定義より {c, f (c), f (f (c)), f (f (f (c))), ...} です.
• エルブラン基底については {p(c), p(f (c)), p(f (f (c))), p(f (f (f (c)))), ...} です.
• エルブラン構造について.
構造を作るには, 述語記号の解釈を定義する必要があります. これは単純にエルブラン基底の部分集合を考
え, その要素について真, 要素でなければ偽とみることとしましょう. 例えば,{p(f 2n (c))|n ≥ 0} はエルブラ
ン基底の部分集合となり, この場合は p(c) = ⊤, p(f (c)) = ⊥, p(f (f (c))) = ⊤, p(f (f (f (c)))) = ⊥, ... と解釈
を定義したことになります.
4
2.3. 述語論理と命題論理の橋渡し
さて, いよいよスコーレムの基本定理の証明にとりかかります. まずは次の補題.
補題 1 言語 L において, そのエルブラン領域を H であらわすとする. L の論理式 ∀x1 ...∀xn p(x1 , ..., xn ) につい
て, ∀x1 ...∀xn p(x1 , ..., xn ) が充足不能 ↔ L の閉項 tij ∈ H(1 ≤ i ≤ m, 1 ≤ j ≤ n) が存在し, p(t11 , ..., t1n ) ∧ ... ∧
p(tm1 , ..., tmn ) が (命題論理として) 充足不能.
この補題が証明出来れば, 述語論理と命題論理の間につながりを生む事が出来ます.
証明 3 (←) 対偶を取れば明らか.
(→) これを証明する為に, 次の補題を証明する.
補題 2 ∀x1 ...∀xn p(x1 , ..., xn ) がエルブラン構造で充足可能 ↔ 命題論理式の集合 Γ = {p(t1 , ..., tn )|t1 , ..., tn ∈ H}
(H はエルブラン領域) が命題論理式の集合として充足可能.
証明 4 (→) 仮定より解釈 pU が存在する. ここで, 命題論理の真偽値関数 V を次のように定義出来るのが肝である.
V (p(t1 , ..., tn )) = pU (t1 , ..., tn )
この様に定義出来るのは, エルブラン構造上での述語記号の解釈を考えるからで, つまりは p(t1 , ..., tn ) は原始論理
式であり, これを原始命題としてみることにより, 命題論理の範疇となる. この時, 明らかに Γ は充足可能.
(←) 今度は逆に, 命題論理の真偽値関数 V を用いて pU を定義すれば良い.
■
さて, 元の定理に戻る.
証明 5 (証明 3 のやり直し) (→) ∀x1 ...∀xn p(x1 , ..., xn ) が充足不能ということは, エルブラン構造でも当然充足
不能. すると定理 4.6 から Γ = {p(t1 , ..., tn )|t1 , ..., tn ∈ H} が命題論理として充足不能ということになる. ところ
で, 命題論理のコンパクト性定理によれば論理式の集合 Γ が充足不能であるという事は,Γ の有限部分集合で充足
不能なものが存在. この充足不能な有限部分集合がすなわち, 求めるべき p(t11 , ..., t1n ) ∧ ... ∧ p(tm1 , ..., tmn ) と出
来るから (→) がいえた.
■
いま, スコーレムの基本定理を証明することが出来ます.
定理 4 (スコーレムの基本定理) 言語 L の文 σ の SNF(σ) を ∀x1 , ..., xn φ(x1 , ..., xn ) とする. また L のエルブラン
領域を H と書く. このとき,
¬σ が恒真である ↔ tij ∈ H(1 ≤ i ≤ m, 1 ≤ j ≤ n) が存在し ¬φ(t11 , ..., t1n ) ∨ ... ∨ ¬φ(tm1 , ..., tmn ) がトートロ
ジになる.
証明 6 ¬σ が恒真 ↔ σ が充足不能 ↔ SNF(σ) が充足不能. また, 任意の t 達に対し,¬φ(t11 , ..., t1n ) ∨ ... ∨
¬φ(tm1 , ..., tmn ) がトートロジ ↔ φ(t11 , ..., t1n ) ∧ ... ∧ φ(tm1 , ..., tmn ) が充足不能である. あとは, 補題 1 から
明らか.
3. 論理プログラムと宣言的意味論
以下, 言語 L を固定して考える.
定義 7 (リテラル) L の原始論理式 φ とその否定 ¬φ をリテラルと呼ぶ.
定義 8 (節 (clause)) L のリテラルの有限集合 {l1 , ..., ln } を節と呼び, これでリテラルの選言, すなわち ∀l1 ∨...∨ln
をあらわす. (ここでの ∀ の出現は, 自由変数の出現を全て ∀ で束縛したものを意味する)
5
例として, 節 {p(X), p(Y ), q(X, Y )} は,∀X∀Y (p(X) ∨ p(Y ) ∨ q(X, Y )) という論理式を表すということである.
Prologっぽく, 大文字から始まる識別子は変数を, 小文字から始まる識別子は定数を表す約束にします.
定義 9 (確定節 (definite clause) A, B1 , ..., Bn を L の原始論理式とする. この時, ∀A ∨ ¬B1 ∨ ... ∨ ¬Bn の形の
論理式, すなわち, {A, ¬B1 , ..., ¬Bn } という節を確定節と呼ぶ. また, n = 0 でも良い.
注意 1 確定節 {A, ¬B1 , ..., ¬Bn } は, ∀(B1 ∧ ... ∧ Bn → A) とすることが出来, これを A ← B1 , ..., Bn と書く時が
ある. 特に, n = 0 の時は確定節 {A} は単に A と書く.
定義 10 (ゴール節 (goal clause)) B1 , ..., Bn を L の原始論理式とし, 論理式 ¬B1 ∨...∨¬Bn すなわち節 {B1 , ..., Bn }
をゴール節と呼ぶ.
注意 2 ゴール節 {B1 , ..., Bn } は,∀(B1 ∧ ... ∧ Bn → ⊥) とすることが出来, これを ← B1 , ..., Bn と書く時がある.
とくに ∀(B1 ∧ ... ∧ Bn → ⊥) は ¬∃B1 ∧ ... ∧ Bn とも出来る.
定義 11 (ホーン節) 確定節 または ゴール節である節をホーン節と呼ぶ.
注意 3 ホーン節を上のように定義しましたが, 今回は確定節しか考えません….
定義 12 (論理プログラム) L の論理プログラムとは,L の確定節の有限集合のこと. 論理プログラム P = {C1 , ..., Cn }
は, 論理式として C1 ∧ ... ∧ Cn をあらわすこととする.
例として L の論理プログラム P = {list(nil), list(cons(X, Y )) ← list(Y )} は論理式としては list(nil) ∧
∀X∀Y list(Y ) → list(cons(X, Y )) である. ここで先に, エルブランモデルという概念を定義する.
定義 13 (エルブランモデル) 言語 L のエルブラン構造をつくるのにおいて, 述語記号の解釈の定め方だけに余地
があると言える. 先に述語記号を,L のエルブラン基底の部分集合を考え, その要素となる原始論理式, かつそれの
みを構造において真とするよう解釈すれば良いとした. この考えをもとに,L の論理プログラム P の任意の確定節
を真とする解釈を与えるエルブラン基底の部分集合を,P のエルブランモデルと呼ぶ.
さて, ホーン論理による論理プログラムでは, エルブランモデルの共通部分をとると, それがまたエルブランモデ
ルとなる性質があります.
定理 5 (model intersection* property) 言語 L の論理プログラム P で, {Mi |i ∈ I} をエルブランモデルの
族とする. この時, 共通部分 ∩{Mi |i ∈ I} は P のエルブランモデルとなる.
ところで, カジュアルに ∩{Mi |i ∈ I} などと書きましたが, エルブラン構造で異なるのは述語記号の解釈のみで
す. 述語記号の解釈は, エルブラン基底の部分集合として与えましたから, モデル達の共通部分の述語解釈を, モデ
ル達の述語解釈の共通部分とするという事に成ります. インフォーマルになりましたがまぁそんな感じで.
証明 7 M ≡ ∩{Mi |i ∈ I} とする.P の確定節としては A と A ← B1 , ..., Bn が考えられるが, ここでは A ←
B1 , ..., Bn について M がエルブランモデルとなることを言う.
A ← B1 , ..., Bn は論理式としては ∀(B1 ∧ ... ∧ Bn → A) という自由変数を全て ∀ で束縛したものである. これ
が真であることを言うには, 任意の自由変数への L のエルブラン領域 H の要素 (すなわち L の閉項) による代入
で Bi (1 ≤ i ≤ n) が真となるならば,A もまた真となることを言えば良い.
自由変数への代入を 1 つ固定して考える. いま仮定より, この代入のもと Bi (1 ≤ i ≤ n) が M で真である. M
で真であることから, 任意の Mi について Bi (1 ≤ i ≤ n) が真であることが分かる. また, 任意の Mi について
∀(B1 ∧ ... ∧ Bn → A) も真なので, 今考えている代入のもとで A が真. よって M でも A は真となる.
この定理の系として明らかであるが, ある特別なエルブランモデルを得る
■
6
系 1 (最小エルブランモデル) 言語 L の論理プログラム P の全てのエルブランモデル {M |M |= P} の共通部分
∩{M |M |= P} は P のエルブランモデルとなる. 特にこのモデルは, 全エルブランモデルで (順序として ⊆ を入れ
た時に) 最小となり, 最小エルブランモデル (least Herbrand model) と呼ぶ. 論理プログラム P の最小エルブラン
モデルを LHM(P) で表す.
最小エルブランモデルに対して, 次の定理が言える
定理 6 言語 L で,P を論理プログラムと Bi を原始論理式の集合とする. この時, P |= ∃x1 ...∃xm B1 ∧ ... ∧ Bn ⇔
LHM(P) |= ∃x1 ...∃xm B1 ∧ ... ∧ Bn となる.
証明 8 (⇒) 仮定より,P のモデルは ∃B1 ∧ ... ∧ Bn を真とすることが分かっている. この時,P の最小エルブラン
モデル LHM(P) は上の定理より存在する. そして LHM(P) は P のモデルであるから, ∃x1 ...∃xm B1 ∧ ... ∧ Bn を
真とする.
(⇐) P のモデルを M とする (これは当然, エルブランモデルではないかもしれない). この時,M で ∃x1 ...∃xm B1 ∧
... ∧ Bn が真となることを言えば良い.
さて, ここで M に対応する次のようなエルブラン構造 M′ を考える. エルブラン構造を作るには, 述語記号の解
釈を考えれば良いのであるから n-arity 述語記号 p の M′ での解釈を次のように定義する.
′
pM (t1 , ..., tn ) = pM (t1 M , ..., tn M )
このように述語記号に対してモデル M を用いてつくった M′ は P のエルブランモデルになることは明らか. さ
て,LHM(P) が ∃x1 ...∃xm B1 ∧...∧Bn を真にするという事は, ある代入 x1 ← t1 , ..., xm ← tm のもとで B1 ∧...∧Bn
が真になるということである. この時,B1 ∧ ... ∧ Bn は M′ でも真となる. ここで H を L のエルブラン領域とする
と,ti ∈ H である. なので,x1 ← t1 M , ..., xm ← tm M という代入のもとでは, M で B1 ∧ ... ∧ Bn は真となる. 従っ
て,∃x1 ...∃xm B1 ∧ ... ∧ Bn は M で真.
系 2 言語 L の論理プログラムを P とする.L のエルブラン基底を B とし,p ∈ B とすると, (ここで p には変数が
一切含まれないことに注意) LHM(P) |= p ⇔ P |= p は上の定理より明らか. 特に,LHM(P) = {p ∈ B | P |= p}
となる.
これはつまり, 論理プログラム P の意味する所は, その最小エルブランモデルそのものであるということを述べ
ているわけです.
例えば, 自然数を表現するプログラム P = {nat(z), nat(s(X)) ← nat(X)} を考えてみたいと思います. このプ
ログラムの最小エルブランモデルはどうなるでしょうか…? というのが私たちの知りたいことです. まぁこれは
LHM(P ) = {nat(z), nat(s(z)), nat(s(s(z))), ..., } = {nat(sn (z))|n ∈ N } となるわけですが.
このプログラムに対する他のエルブランモデルは, つまり LHM(P) に何か付け足したもので妥当になっていれ
ば良いわけですが…例えば nat(s) なんかは項ではないのでまぁダメで…と考えて行くと無いですね.
プログラム P ′ = {nat(z), nat(s(X)) ← nat(X), iszero(z)} だとどうでしょうか. この最小エルブランモデルは
LHM(P ′ ) = {nat(sn (z))|n ∈ N } ∪ {iszero(z)} となります. この時には本質的に異なるエルブランモデルとして
LHM(P ′ ) ∪ {iszero(s(z))} や, LHM(P ′ ) ∪ {iszero(s(z)), iszero(s(s(z)))} があります.
だらだらと例を示しましたが, 論理プログラムの意味する所は必要十分に最小エルブランモデルが語ってくれる
というのは分かってもらえたと思います.
では, 最小エルブランモデルさえ手元に置いておけば, ある論理式が論理プログラムの帰結となるかどうかは, 最
小エルブランモデルに属すかどうかで分かりそうなものです. さて, 最小エルブランモデルはどのように計算する
事が出来るでしょうか…? という事をここから書きたかったのですが完全に時間切れです!! 締め切り的な意味で!!
そもそも, 上の最小エルブランモデルの証明は, 全てのエルブランモデルの共通部分を取ったわけですが, この
全てのエルブランモデルの中に最小エルブランモデルは含まれている訳ですから, 全てのエルブランモデルを手
に入れる術があれば, そもそも最小エルブランモデルもその中にあるわけで云々という事に成ります.
で, どうするのかというと不動点意味論とかいうのがありまして∼という話なのですが. 具体例を用いていきま
しょう. 先ほどと同じく, P = {nat(z), nat(s(X)) ← nat(X)} を考えます.
7
まず何も分かっていない所からスタートです! 何も分かっていない現時点で新たに獲得出来る事は {nat(z)} です.
少し賢くなりました. 新たに得たことを利用して,{nat(z), nat(s(z))} が分かります. 更に {nat(z), nat(s(z)), nat(s(s(z)))}
が分かります. これを延々と繰り返すと, 徐々に最小エルブランモデル ({nat(sn (z))|n ∈ N }) に近づいて行くこ
とが分かります. なおかつ, 最小エルブランモデルを元に新たに何か分かる事があるかというと, まぁこれが無い
ワケで…. ということで, 新たに何も獲得出来なくなったところでやめれば良いと.
今分かっていることを元に, 新たに正しいと分かることを関数 F として書き直せば
F(ϕ) = {nat(z)}
F({nat(z)}) = {nat(z), nat(s(z))}
F({nat(z), nat(s(z))}) = {nat(z), nat(s(z)), nat(s(s(z)))}
..
.
F({nat(sn (z))|n ∈ N }) = {nat(sn (z))|n ∈ N }
あれ…こういうのみたことあるぞ…??
アッ！
！F の不動点だ!!
ということで, 不動点意味論なるものがあって, こういう「正しいと分かることを増やして行く」関数の不動点が,
実は最小エルブランモデルと一致するというお話がこの後続くところでした.
まぁどう考えても時間が足りないです. 比較的入手可能な参考文献をあげたいと思いますので, この後の話はそ
こで補ってもらえればと思います.
4. おわりに
そもそもナンデこんな記事を書こうと思ったのかと言いますとえーと. 皆様は SWI-Prolog の library 中に,coin-
duction.pl というファイルがあるの2 をご存知でしょうか? 実は私, 恥ずかしながら夏休みの丁度前あたりにこの
ファイルの存在に気付きまして, 非常に面白そうなのでなんとかして遊ぶしか無いと思い立ったものでした.
Luke Simon らによる”Co-Logic Programming: Extending Logic Programming with Coinduction”を元にして
書かれたモジュールらしいのです. その論文 (上記タイトルで検索すると出てくるそれっぽいものを読めば良いと
思いますが) を見ても, 宣言的意味論の部分が今ひとつ分からなかったので, 折角だからそもそも Prolog の宣言的
意味論をちゃんとおさらいしよう!という気持ちだったわけです.
Co-Logic で何かずば抜けて目新しく面白い事がここで紹介出来るかと言われると弱りますが, まぁ機会があれ
ばブログなんかでもうちょっとちゃんとした話を書ければ良いと考えています.
今回はこんなところで許してくださいよ!
2 http://www.swi-prolog.org/pldoc/doc/swi/library/coinduction.pl
9
関連図書
まず数理論理全般の文献, 特に本稿を書くにあたって参考にしたものを挙げたいと思います.
[1] 田中一之編 ゲーデルと 20 世紀の論理学 2 巻 完全性定理とモデル理論 第 I 部
東京大学出版会 2006
この本の第 I 部を特に参考にして書きました. もっと言えば第 I 部付録です. 「スコーレムの基本定理」という
定理名にしたのは, この本にならっての事です.
[2] 萩谷 昌己, 西崎 真也著 論理と計算のしくみ 岩波書店 2007
[3] 小野 寛晰著 情報科学における論理 日本評論社 1994
上記 2 冊は, 特にプログラムを書く人が読むと面白いと思います. ゲーデルと 20 世紀の論理学はタイトルから
して辛そうだぞ…という方は下の二冊を. 本稿で証明を省略した, 定理 2 の証明もあります.
以下は数理論理学というより Prologっぽい話について参考になると思います.
[4] 有川 節夫, 原口 誠著 述語論理と論理プログラミング オーム社 1988
[5] 森下 真一著 知識と推論 共立出版 1994
両方とも不動点意味論の話が書かれています. どちらも似た構成に成っていますが, この 2 冊の異なる点はホー
ン論理に否定の概念を導入するあたりにあります. 前者ではプログラムの完備化を行うのに対して, 後者では
(非) 層状論理プログラムという概念を導入し云々. これらのキーワードが気になった方は, 比較的入手しやす
い書だと思いますので是非読んでみてください.
[6] 横内 寛文著 プログラム意味論 共立出版 1994
[7] Carl A. Gunter , Semantics of Programming Languages: Structures and Techniques
The MIT Press 1992
この 2 冊は Prolog とは関係ありませんが, 不動点意味論とは関係があります. cpo という特別な順序集合の上
における連続関数というもので, プログラムにおけるデータと関数を特徴付け, 特に再帰関数の意味を不動点
で表示するという, いわゆる表示的意味論で用いられる領域理論 (domain theory) について取り扱った本です.
不動点が存在する, 及び不動点が極限で表現されるということはどちらも変わりませんので, プログラマの人
としてはこちらも興味があるかな∼というその程度です. 横内先生の本は最近復刊されて個人的に非常に嬉し
かったのですが, それも今現在 (2011 年 12 月 28 日) 確認したところ在庫切れで Amazon でも高くなっていま
すので, 割とちゃんと読みたいという人は Gunter の方をどうぞ….
11
今夜はお前と俺でマルチパラダイムだからな
lyrical logical
はじめに
これは, オブジェクト指向言語の持つ性質のうちの一つ ”Open Recursion” について詳しく切り込みつつ, 関数
型言語とオブジェクト指向言語それぞれについて, 理解を深めようという趣旨の記事であり, マスクド・ライダー・
スピリッツとは実際無関係ですし, ニンジャとも実際無関係です. ニンジャもペケロッパもカチグミもマケグミも
オイランもロブスターもブッダもゲイのサディストも, ご照覧あれ！
！
サルでも分かり実際簡単な
記事を読むのに特別な知識は必要ありません.Java と Scala と OCaml がある程度分かれば読めると思います.
分からなくてもなんか読めると思います.
フィボナッチ関数
古来より, プログラミングはフィボナッチ関数の定義から始まると決まっています. 古事記にも書いてあります.
（おお, 見よ！フィボナッチ関数を扱っている星の数ほどの論文を！）フィボナッチ関数とは, フィボナッチ数を計
算する関数です. フィボナッチ数は F n を n 番目のフィボナッチ数とすると, 以下のように定義されます.
F 0 = 0
F 1 = 1
F (n + 2) = F (n) + F (n + 1)
例えば OCaml ではフィボナッチ関数は以下のように定義できます.
1
let rec fib n = if n <= 1 then n else fib ( n - 1) + fib ( n - 2)
一方 Java では以下のように定義できます.
1
2
3
4
5
public class Fib {
public int fib ( int n ) {
return n <= 1 ? n : fib ( n - 1) + fib ( n - 2);
}
}
これらは, 一見した限りでは特別面白い定義には見えません. しかし, よくよく両者を比較してみると Java 側
のコードには面白い性質が備わっていることがわかります.
12
メモ化
ナイーブな実装のフィボナッチ関数は, 与えられた引数が大きくなると, かなり計算に時間がかかってしまいま
す. これは, 同じフィボナッチ数を何度も繰り返し計算しているためです. 高速化するには, 一度計算したフィボ
ナッチ数を再度計算してしまうのを防ぐ必要があります. 再計算を防ぐために, 通常は関数のメモ化を行います.
メモ化とは, 計算結果を記憶しておき, 同一の引数の場合に記憶しておいた計算結果を返す手法のことです.
兎に角, フィボナッチ関数といえばメモ化なのです！古事記にも書いてあります.（おお, 見よ！フィボナッチ関
数のメモ化を扱っている星の数ほどの論文を！）とはいえ, 普通にメモ化するのは面白くないので, ここは**元の
フィボナッチ関数の定義には一切変更を加えずに**メモ化を行ってみることにしましょう. Java なら, これは素
直にクラス Fib を継承した新しいクラス MemoFib を定義する形で実現できます.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java . util . HashMap ;
public class MemoFib extends Fib {
private HashMap < Integer , Integer > table = new HashMap < Integer , Integer >();
@Override
public int fib ( int n ) {
if ( table . containsKey ( n )) {
return table . get ( n );
} else {
int result = super . fib ( n );
table . put (n , result );
return result ;
}
}
}
ところが OCaml ではそう簡単にはいきません.
1
2
3
4
5
6
7
8
9
10
11
module IntMap = Map . IntMap (* 簡 単 の た め に Batteries Included ラ イ ブ ラ リ を 使 っ て い ま す *)
let memofib =
let table = ref IntMap . empty in
let ret fib n =
if IntMap . mem n ! table then
IntMap . find n ! table
else
let result = fib n in
table := IntMap . add n result ! table ;
result
in ret
なんとなくメモ化しているような雰囲気がありますが, これではメモ化はうまく機能しません. 関数 fib 内で呼
び出されるのはあくまで fib のままですから, テーブルに値を記録したり, テーブルから値を参照したりするのは
最初の呼び出しのみの時だけです. これでは無駄な計算を省くことは当然できません. 何故 OCaml ではうまく書
けなかったものが Java では自然に書くことができたのか, 少し考えてみましょう.
ネイキッド・メソッド
Java によるメソッド fib の定義を振り返ってみましょう.
1
2
3
4
5
public class Fib {
public int fib ( int n ) {
return n <= 1 ? n : fib ( n - 1) + fib ( n - 2);
}
}
重要なのは fib は OCaml と違い, 関数ではなくメソッドだということです. よって, メソッドのレシーバを省
略せずに書くと, 以下のようになります.
1
2
3
4
5
public class Fib {
public int fib ( int n ) {
return n <= 1 ? n : this . fib ( n - 1) + this . fib ( n - 2);
}
}
メソッドというのは, 暗黙のうちに引数 this を取る関数といえるわけですが, その引数に「実際に呼び出すメ
ソッド」が依存しています. 直接的な再帰呼び出しのように見えていたものは, 実際には this を通した, 間接的な
13
再帰呼び出しだったのです. そのため this に渡す値を変えてやることで, メソッド内で呼び出されるメソッドを
差し替えることができた, というわけです.
Open Recursion
直接的な再帰呼び出しに見えていたものは, 実際には呼び出すメソッドを後から入れ替えることができる,「開い
た」再帰関数になっていた, ということがわかりました. このような, オブジェクト指向の持つ外部に対して「開
いた」性質は ”Open Recursion” と呼ばれています. オブジェクト指向は, 様々な便利な性質を持っていますが
”Open Recursion” はそのうちの一つです. この性質は大変強力かつ有用なものなので OCaml のような関数型言
語でも利用したいですよね？してみましょう.
OCaml による ”Open Recursion” の実現
ようは, 実際に呼び出す関数を引数として明示的に取ってしまえばいいわけです. これは以下のような定義で表
現することができます.
1
let fib f n = if n <= 1 then n else f ( n - 1) + f ( n - 2)
引数 f が, 外部から抽入される関数になります. さて, この関数 fib から, オリジナルの関数 fib のように振る舞
う関数をつくりだすことができるでしょうか？
\# fib fib;;
Characters 4-7:
fib *fib*;;
Error: This expression has type (int -> int) -> int -> int
but an expression was expected of type int -> int
叱られてしまいました…関数 fib の型は (int -¿ int) -¿ int -¿ int です. 関数 fib の引数の型は int -¿ int なの
で, 関数 fib は関数 fib の引数としては不適当です. int -¿ int の値を作るには関数 fib に対して引数を渡してやる
必要があります. しかし, その引数として関数 fib は矢張り不適当です. …ならば, 必要な分だけ fib を渡し続けま
しょう！
(fib (fib (fib (fib (fib ...
無限長のコードを書くわけにはいきませんから, これではなんともしようがありませんね.
マジカル☆ファンクション
さて, 突然ですがここで下のような関数について考えてみましょう. 1
let rec fix f = f ( fix f )
何だかよく分からないですね（これが何か分かる人は飛ばしてもらって結構です）. 一つずつ関数適用を進めて
いきましょう.
fix f = f (fix f) = f (f (fix f)) = f (f (f (fix f))) = ...
おお…なんかそれっぽいですね！これを使えばうまくいきそうです.
関数 fix のような関数は不動点演算子と呼ばれています. f n = n となるような n を関数 f の不動点と呼び, 関
数をとりその関数の不動点を返すような関数が不動点演算子です.
14
関数適用の遅延
難しいことはさておいて, 早速使ってみましょう.
\# fix fib;;
Stack overflow during evaluation (looping recursion?).
はい, スタックがあふれてしまいました. 無限に再帰呼び出ししてしまうので当然の結果です. さて, これは一体
どうしたものでしょうか？ここでは関数 fib が引数を取ることを利用して, 以下のような定義に変えることでうま
く解決することができます.
1
2
3
(* ど ち ら で も よ い *)
let rec fix f = f ( fun x -> fix f x )
let rec fix f x = f ( fix f ) x
関数 fix の中ですぐに関数 fix を f に対して適用してしまっているのが問題になっていました. そこで一つ目の
定義では, 関数 fix を f に適用するタイミングを, 無名関数を使い, 実際に関数 f が必要とするまで遅らせてやるこ
とで, 問題を回避しています. 二つ目の定義では, 関数 fix の引数を増やし, 完全適用ではなく部分適用にしてやる
ことで, 問題を回避しています.
Haskell のような非正格評価を採用した言語ならこのような小細工は必要ありませんが, ほとんどの言語は正格
評価を採用しているので, このようにうまく定義してやる必要があります.
OCaml よる ”Open Recursion” の実現 - 解決編
さてこれで準備は整いました. 問題の改善された関数 fix を使って計算してみましょう.
> \# fix fib;;
> - : int -> int = \<fun>
> \# fix fib 30;;
> - : int = 832040
やりました！しかし, 問題はこれからです. 関数 fib の定義に手を加えることなく, メモ化を行うことができるで
しょうか？Java による実装をもう一度振り返ってみましょう.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java . util . HashMap ;
public class MemoFib extends Fib {
private HashMap < Integer , Integer > table = new HashMap < Integer , Integer >();
@Override
public int fib ( int n ) {
if ( table . containsKey ( n )) {
return table . get ( n );
} else {
int result = super . fib ( n );
table . put (n , result );
return result ;
}
}
}
Java のクラス MemoFib に対応する OCaml コードは以下のようになります.
1
2
3
4
5
6
7
8
9
10
11
module IntMap = Map . Make ( Int )
let memo =
let table = ref IntMap . empty in
let ret f n =
if IntMap . mem n ! table then
IntMap . find n ! table
else
let result f n in
table := Intmap . add n result ! table ;
result
in ret
15
細部は異なりますが, 全体の構造は, ほとんど Java のコードと同じですね.
あとは関数 fib と関数 memo の第一引数をそれぞれ埋めてやればよいわけですが, 関数 memo の第一引数には
関数 fib を, 関数 fib の第一引数には関数 memo を渡してやりたいので,
(fib (memo (fib (memo (fib (memo ...
のようなものが欲しいわけです. このような値はどのようにすれば作り出すことができるでしょうか？
(fib (memo
(fib (memo
(fib (memo
(...
上記のように見てみれば分かりやすいかもしれません. そう, 関数 memo と関数 fib を組み合わせたものに不動
点演算子を適用してやればいいのです.
\# fix (fun n -> fib (memo n));;
- : IntMap.key -> int = \<fun>
これは所謂関数合成ですから, 以下のようにしてよりスマートに定義できます.
\# let compose f g n = g (f n);;
value compose : (’a -> ’b) -> (’b -> ’c) -> ’a -> ’c = \<fun>
\# fix (compose fib memo) 42;;
- : int = 267914296
やりました！Java のような「開いた」再帰呼び出しが OCaml でも実現できました.
相互再帰の場合
現実には, 一つのクラスには複数のメソッドが定義されることがあります. それらは, お互いを再帰的に呼び出し
を行っているかもしれません. これは相互再帰と呼ばれる, 再帰呼び出しの一種です. あまり面白くない例ですが
（めんどくさくなってきた）, 偶数かどうかを判定するメソッド even と奇数かどうかを判定するメソッド odd を
持つ EvenOdd クラスを定義します.
1
2
3
4
5
6
7
8
public class EvenOdd {
public bool even ( int n ) {
return n == 0 ? true : odd ( n - 1);
}
public bool odd ( int n ) {
return n == 0 ? false : even ( n - 1);
}
}
これに対応する OCaml コードはどのように書くことができるでしょうか？素直に定義すれば以下のようにな
ります.
1
2
3
4
5
type even_odd_t = { even : int -> bool ; odd : int -> bool }
let even_odd eo =
let even n = if n == 0 then true else eo . odd ( n - 1) in
let odd n = if n == 0 then false else eo . even ( n - 1) in
{ even ; odd }
しかし, この定義では関数 fix によりうまく値を作り出すことができません.
16
\# fix *even_odd*;;
Characters 4-12:
fix *even_odd*
Error: This expression has type even_odd_t -> even_odd_t
but an expression was expected of type (’a -> ’b) -> ’a -> ’b
スタックオーバーフローを避けるために, 関数 fix は関数の不動点を計算する関数として定義されていたのでし
た. 関数 even odd に unit 等のダミーの引数を追加することも可能ですが, ここでは評価の遅延を行うために予
め用意されている Lazy モジュールを利用してみましょう.
1
2
3
4
5
let rec fix f n = f ( lazy ( fix f ))
let even_odd eo =
let even n = if n == 0 then true else ( Lazy . force eo ). odd ( n - 1) in
let odd n = if n == 0 then false else ( Lazy . force eo ). even ( n - 1) in
{ even = even ; odd = odd }
少しまどろっこしい定義になってしまいましたが, これでうまく値を作り出すことができます.
\# fix even_odd;;
- : even_odd_t = {even = \<fun>; odd = \<fun>}
\# (fix even_odd).even 42;;
- : bool = true
\# (fix even_odd).odd 42;;
- : bool = false
再帰呼び出しを行わない場合
再帰呼び出しを行わない場合にも ”Open Recursion” のテクニックは有用です. 例えば, 部分関数を組み合わ
せて, 全域関数を定義する, などといったことが可能になります. 以下は全く面白みのない例です.（めんどくさく
なってきた）
1
2
3
4
5
6
type kind = N | Z | P
let positive f n = if n > 0 then P else f n
let zero f n = if n == 0 then Z else f n
let negative f n = if n < 0 then N else f n
let check f n = assert false
let kind_of_int = fix ( compose check ( compose zero ( compose negative positive )))
本当に全域関数になっているかどうかは, うまく型付けしてやらない限りは, プログラマが保障する必要があり
ます.
他にも, アスペクト指向プログラミングのためのテクニックとしても利用できるそうなのですが, アスペクト指
向よく知らないので…成せば成る, 成せば成るんだからぁ…
オブジェクト指向言語の敗北？
OCaml のような関数型言語でも ”Open Recursion” を扱うことができるようになったわけですが, これは Java の
ものと完全に同等の性質を持つのでしょうか？例えば, 関数呼び出しのトレースがしたくなったとしましょう.OCaml
では以下のような関数を定義すればトレースすることができます.
1
2
3
4
5
let trace f n =
print_endline ( " Entering fib ( " ^ ( string_of_int n ) ^ " ) " );
let result = f n in
print_endline ( " Entering fib ( " ^ ( string_of_int n ) ^ " ) = " ^ ( string_of_int result ));
result
定義してやった関数 trace を合成してやれば, やはり関数 memo や関数 fib には手を加えることなくトレース
を実現することができます.
17
\# fix (compose fib (compose trace memo)) 5;;
トレースは長くなるので省略します. 関数引数の評価順序のおかげで, 一見正しくないように見えますが, ちゃん
とトレースされているはずです. 上記の関数の合成順では, メモ化により省略された関数呼び出しは出力されなく
なっています. この振る舞いが気に食わない場合には, 関数の合成順を変えてやれば全ての関数呼び出しをトレー
スすることができます.
\# fix (compose fib (compose memo trace)) 5;;
トレースは長くなるので省略します. 重要なのは OCaml の場合, 関数の合成順序, つまり関数の「組み合わせ
方」を自由に変えることができる, ということです. では Java ではどうでしょうか.
1
2
3
4
5
class
class
class
class
class
Fib { ... }
MemoFib extends Fib { ... }
TraceMemoFib extends MemoFib { ... }
TraceFib extends Fib { ... }
MemoTraceFib extends Fib { ... }
クラス MemoFib とクラス MemoTraceFib で, クラス TraceMemoFib とクラス TraceFib で定義の重複が起
こってしまいます. これはうまくないですね. 問題は抽入されるメソッドが, クラス定義の時点で継承関係により
決まってしまう点にあります. 抽入されるメソッド, つまり ”super.fib” がクラス定義の時点で決まっていないよ
うなクラスを定義する方法は Java にはありません. そのため Java では OCaml のように複数の機能を自由に
「組み合わせる」ことはできません. 関数型言語でオブジェクト指向言語の言語機能を模倣していたら, オリジナ
ルよりも強力な性質を手に入れることができてしまったようです. スゴイ！やはり, オブジェクト指向言語は関数
型言語より劣った存在なのでしょうか…？
オブジェクト指向言語の逆襲
いいえ, オブジェクト指向言語も負けてはいません. ここで満を持して Scala の登場です！Java には退場して頂
きましょう. Scala は関数型言語の要素も備えた言語ですが,Java のようなオブジェクト指向からのアプローチで,
この問題を解決することができます. Scala には, トレイト内で抽象メソッドを override した抽象メソッドを定義
するための言語機能 ”abstract override” があります. 何のことだか分からない？何はともあれ, 早速コードをご
覧頂きましょう！
（めんどくさくなってきた）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
trait AbstractFib {
def fib ( n : Int ) : Int
}
class Fib extends AbstractFib {
def fib ( n : Int ) : Int = if ( n <= 1) n else fib ( n - 1) + fib ( n - 2)
}
trait Memo extends AbstractFib {
import collection . mutable . Map
private val table : Map [ Int , Int ] = Map ()
abstract override def fib ( n : Int ) : Int =
if ( table . contains ( n )) {
table ( n )
} else {
val result = super . fib ( n )
table ( n ) = result
result
}
}
trait Trace extends AbstractFib {
abstract override def fib ( n : Int ) : Int = {
println ( " Entering fib ( " + n + " ) " )
val result = super . fib ( n )
println ( " Exiting fib ( " + n + " ) = " + result )
result
}
}
Scala を知らない人のために簡単に説明すると, トレイトというのはメソッドの定義が可能なインターフェース
のようなものです.
18
トレイト Memo とトレイト Trace で定義されているメソッド fib に abstract override 修飾子が付いている点に
注目してください. トレイト AbstractFib はメソッド fib の定義を持ちません. にも関わらず, トレイト AbstractFib
を継承したトレイト Memo とトレイト Trace のメソッド fib 内で, 定義されていないはずのメソッド fib が呼び
出されているようにみえます. 通常のクラスのメソッド定義ならこれはエラーになるところですが, トレイト内で
は abstract override 修飾子により, このような抽象メソッドの呼び出しが許されるため, エラーにはなりません.
では, 各トレイト内で呼び出される「本当の」メソッドは一体どのメソッドで, どのように決定されるのでしょう
か？これは, 実際に実行例を見てもらうのが一番早いと思います.（めんどくさくなってきた）
scala> new Fib with Trace with Memo fib 42
Entering fib(42)
Entering fib(41)
Entering fib(40)
...
Exiting fib(42) = 102334155
Exiting fib(41) = 165580141
Exiting fib(42) = 267914296
res17: Int = 267914296
scala> new Fib with Memo with Trace fib 42
Entering fib(42)
Entering fib(41)
Entering fib(40)
...
Entering fib(40)
Exiting fib(40) = 102334155
Exiting fib(42) = 267914296
res18: Int = 267914296
トレイトは, クラスや他のトレイトに対して mix-in することで利用します. トレイトの親クラスは, トレイトが
mix-in されるまでは決定されません. これは継承ツリーの線形化により決定されます…が, 線形化とかそういう難
しいことは忘れて, 単に右から実行される, と覚えてしまってもいいと思います. 兎に角, これで OCaml のように
複数の機能を自由に「組み合わせる」ことができました！
トレイトの問題点
実は, これでもまだ OCaml と完全に同等とはいえません. 例えば, 何らかの抽象構文に対して最適化を行うこ
とを考えましょう.
1
2
3
4
5
6
7
8
9
10
let inline f ast = ...
let const_fold f ast = ...
let some_opt f ast = ...
let stopper n =
let c = ref 0 in
let ret f ast =
incr c ;
if ! c < n then f ast else ast
in ret
let opt n = fix ( compose ( stopper n ) ( compose const_fold ( compose some_opt inline )))
ここで some opt の後にもう一度インライン展開を施したほうが, より良い結果が得られることが分かったとし
ます. 実際には, どのみち何度も繰り返し適用するわけで, そういうことはあまりないとは思いますが…そんなと
きには opt の定義を少し変えやれば, インライン展開をもう一度行うことができます.
1
let opt n = fix ( compose ( stopper n ) ( compose const_fold ( compose inline ( compose some_opt inline ))))
19
何気ない変更ですが, これは Scala では素直にはできません. 適当に対応するコードを書いてみます.
1
2
3
4
5
6
class
trait
class
trait
trait
trait
Ast { ... }
AbstractOpt { def opt ( ast : Ast ) : Ast }
Stopper ( n : Int ) extends AbstractOpt { def opt ( ast : Ast ) : Ast = ... }
Inline extends AbstractOpt { abstract override def opt ( ast : Ast ) : Ast = ... }
ConstFold extends AbstractOpt { abstract override def opt ( ast : Ast ) : Ast = ... }
SomeOpt extends AbstractOpt { abstract override def opt ( ast : Ast ) : Ast = ... }
さてどうでしょうか.
scala> new Stopper(n) with ConstFold with Inline with SomeOpt with Inline opt ast
\<console>:12: error: trait Inline is inherited twice
new Stopper(n) with ConstFold with Inline with SomeOpt with Inline opt ast
叱られてしまいました.Scala では, 同じトレイトを二度 mix-in することが許されていないためです. これは少
し残念ですが, 複数のトレイトを定義することで回避するしかないでしょう.
まとめ
ニンジャスレイヤーを知らない人はまず @NJSLYR をフォローしましょう.
外部に「開いた」再帰である ”Open Recursion” を紹介しました. これは大変強力かつ有用な性質を持ってい
ます. また関数型言語で ”Open Recursion” を実現するためのテクニックと, オブジェクト指向言語である Java
の ”Open Recursion” と関数型言語の ”Open Recursion” の「隙間」を埋める言語機能として,Scala の ”abstract
override” を紹介しました.
元は, はてなダイアリ（http://d.hatena.ne.jp/lyrical logical/20111107）で書こうとして, 書ききる前に力尽き
た話です. この記事が完全版ということになります.
関数型言語でオブジェクト指向プログラミングを実現するところから始め, 逆輸入的に関数型言語からオブジェ
クト指向言語に何かを持って帰ってくる, というのがやりたかったのですが, いかがだったでしょうか. 視点を変え
てみると, なんか色々良い, みたいな話ですね. 巷では, 関数型言語だ, いやオブジェクト指向言語だ, と頻繁に聖戦
が繰り広げられていますが, 非常に嘆かわしいことだと思います. もっと仲良くしていきたいですね. ユウジョウ！
ということで, 論理型言語もその輪に加わるといいなーと思ったりするんですが…そこは編集長の記事に期待し
ましょう！
ちなみにタイトルの「お前」と「俺」は「関数型」と「オブジェクト指向」です.
21
REAL PROGRAMMER STORY
m0h1can
REAL3 を扱うプログラマが格闘している多くの問題は, 型推論やモデル検証技術が今くらい進化しても, 値が
主役であるために未だ上手くハンドリング出来ないものが多くあります. そんな中にあって, 計算機の理論とは
ちょっと違う切り口で解決出来る題材を中心に, アトランダムに綴っていきたいと思います.
直接法は速い
シミュレーションでは線形問題に帰着して解く場合が多くあります. その際には連立方程式を解くか固有値分
解を求めることになります. 特に連立方程式を解く場合, 数学的には逆行列を求めるわけですが, 行列の次元 n に
対してメモリは O(n2 ) 必要となります. 次元が非常に大きい4 場合にこれは非現実的です. さいわい物理的に導
出される係数行列は大半がゼロ (疎行列) となる傾向があるので, これを利用して少ないメモリで解くアルゴリズ
ムが考えられてきました.
疎行列に対するアルゴリズムに限定しても, 大別して 2 つのアプローチがあります. 一つは逆行列を計算する方
法で, Gauss の掃き出し法など線形代数の教科書でよく紹介されているものなどです. もう一つが逆行列を求めず
右辺ベクトルを利用して解ベクトルを漸近される方法です. 前者を直接法, 後者を反復法と言います. 反復法だけ
では解の収束が次元の大きさに比例するため, 不完全な逆行列 (前処理) を利用して収束を加速する手法が多く採
用されてきました. これは消費メモリを n の定数倍程度に抑えることが出来るため好んで使われています.
しかし昨今では計算機がコモディティ化し, 以前と比較して非常に多くのメモリが利用出来るようになりまし
た. 一方で通信コストが相対的に増大しており, 単位メモリ当たりの演算数が多いアルゴリズムを好む傾向にあり
ます. このような環境で再び直接法の有効性が確認されるようになってきました. また直接法では反復法と異なり
悪条件5 であっても解けるというメリットがあります.
直接法は簡単に言えば逆行列として LU 分解を行なうものです. ここで行列 L は対角から下三角の行列, 行列 U
は対角から上三角の行列です.
A = LU
−1
A
= U −1 L−1
この形で分解出来ると解ベクトルは次のように求まります.
Ax = b
A−1 Ax = A−1 b = U −1 y
y = L−1 b
3 FORTRAN
で言うところの実数型
4 どれくらいの大きさかは振舞いを見たい現象に依ります.
連立方程式として記述した時点で系を線形化しているため, 非線形な効果が線
形近似でも十分に近しい (誤差の上限が小さい) ように, 離散化の粒度を細かくする必要があります. ザックリとした話ですが, 音の解析では
数億次元でないと現象が現われないことがあります. また根本的に空間が巨大な場合ですと数十億次元など簡単に到達します.
5 行列の最大固有値と最小固有値の比率として条件数が定義されます. 誤差を解に対する摂動として与えた場合に, 条件数が大きい行列で
は誤差が増大し, 逆に小さな行列では誤差に対して寛容であることが分かります. 反復法では解を漸近的に近似するため, 条件数が大きい場合
には誤差が解ベクトルを支配して収束が遅くなります.
22
Left-looking LU
Right-looking LU
Crout LU
図 1: LU 分解の分類
L および U は三角行列であるため y = L−1 b と x = U −1 y は繰り返しの代入で済みます. それぞれ前進代入, 後
退代入と呼びます.
さて LU 分解を求める方法は大きく分けて三種類存在します. 参照する係数と更新する係数の位置関係で分類
し, 参照する列ベクトルより左側の列ベクトルを更新する Left-Looking 法, 参照する列ベクトルより右側のブロッ
ク行列を更新する Right-Looking 法, そして更新する列ベクトルと行ベクトルより左側と上側を参照する Crout
法があります. それぞれの手法を, 参照領域と更新領域で分類したものが図 1 となります.
Crout 法は LU 分解が出来たものとして係数を展開し, 行列 U の 1 行目, 行列 L の 1 列目, 行列 U の 2 行目,…
という順番で分解を進めます. 具体的には L = {lij } と U = {uij } に対し,
uij = aij −
i−1
∑
lik ukj
k=1
∑
1
lik ukj )
(aij −
ujj
j−1
lij =
k=1
として与えられます. 式から明かなように, 係数の更新時にベクトルの内積を計算するため, 最内ループを長く取
ることで効率が上がるベクトル計算機で好んで利用されます. しかし階層的なメモリ構造 (特にキャッシュ) を持
つ昨今のプロセッサでは, メモリ・キャッシュ間の転送コストが相対的に増大するため望ましくありません.
Left-Looking 法も Crout 法同様に係数を展開し, 依存が少ない順番に分解をします. 成分で言えば,
u11 → u12 → l21 → u22 → u13 → · · ·
というように, 可能な限り係数の更新を遅らせます. 最内ループではやはり内積計算を行いますが, 係数の決定が遅
延出来ることを逆手に取って演算量を減らす工夫が施せます. 疎行列に対して非ゼロ構造が同じ列を Super-node
としてまとめておくことで, Left-Looking 法は他の直接法と比較して非常に少ないメモリで計算を行ないます.
6
Right-Looking 法は Gauss の消去法そのものです. 消去に用いる行ベクトルが, それより下のブロック行列全体
を更新するため, 過去には最も遅い手法と考えられていました (実際演算量は多いです). しかし先に述べたように
単位メモリ当たりの演算回数を増やす方が, 広範なメモリを参照し通信を増やすよりリーズナブルな選択肢となっ
て来たため, 状況は逆転しています. 特に疎行列では依存する係数が少なく, これをまとめて小行列 (フロンタル
行列) を作成出来ます. このフロンタル行列は実際小さく分解が可能であるため, 複数のフロンタル行列をキャッ
シュ内で分解することで演算効率が飛躍的に向上します.
7
具体的には次のように Gauss の消去法を行列積で表
6 もっとも実績のある実装は SuperLU です. http://crd-legacy.lbl.gov/ xiaoye/SuperLU/ 素粒子実験に用いる装置の解析など, 非常に
巨大な系を解くに際し, 必要となるメモリを抑えるために活用されています.
7 複数のフロンタル行列によって演算効率を稼ぐ手法をマルチフロンタル法と呼びます. 並列化を考えた場合, フロンタル行列をタス
クとしてワーカに振れば良いため, 並列化効率も他の直接法より良い傾向があります. 特に実績があるのは MUMPS という実装です.
http://graal.ens-lyon.fr/MUMPS/
23
現し, 小行列を密行列として計算します (このため演算量は他の手法より増えます).
1
..
.
(k−1)
1
aik
Rk =
r
=
−
ik
(k−1)
rik 1
aii
..
..
.
.
rnk
1
A(n−1) = Rn−1 Rn−2 · · · R1 A(0)
桁落ちが起こす特異性
REAL は実数型と言うものの, 実態は浮動小数点フォーマットであり, 有限精度のデータ8 です. このため数学的
には解けるハズのものが実際解けなくなる場合があります.
簡単のため 2 次元で考えます. 次のような行列です.
(
A=
1+ε
−1
−1
1
)
det(A) = ε
行列式が非ゼロであるので A は本来解けるハズです. しかし ε が 1 より非常に小さい場合9 には桁落ちを起こ
し, 次のような特異行列となってしまい解けません.
(
A=
)
1 −1
−1 1
det(A) = 0
何かしらの計算から結果的にこのような行列が生成された場合には手に負えませんが, 予め危険な要素の判断
が付く場合には対処が可能です. 次のように行列を変形します.
(
1+ε
A −→
ε
P1
)
(
)
−1 P2
−1 1 + ε
−→
0
0
ε
det(A) = −ε
ここで操作 P1 は 1 行目を 2 行目に加算し,P2 は 1 列目と 2 列目を交換します. 当然ですが係数を決定した後で
すと特異行列になってしまいますから, 以上の操作が施されたものと見做して係数を求めることが肝要です.
(
P1 =
(
P2 =
1 0
1 1
0 1
1 0
)
)
(AP1 P2 )y = b
P2−1 P1−1 x = y
8 多倍長演算という形で無限の精度を保証する計算手法も存在します.
しかし特定の用途でなければこれを用いることはあまりありません.
離散化した式の段階で理論的に誤差を評価する方が, 計算時間の点で好まれます. また一般的に無限精度の演算は決定不能問題となります.
9 倍精度では仮数部が 56-bit なので有効桁数は 15 桁 (log
52+1 ≃ 15) です. 単精度では仮数部が 23-bit で有効桁数は 7 桁 (log
23+1 ≃
10 2
10 2
7) となります. 有効桁数を越える 2 つの数を加減算すると桁落ちが生じます.
24
グラフ問題が数値計算に役立つ
連立方程式を直接法で解こうと反復法で解こうと, 計算の途中では加減算が入ってきます. 悪条件の行列では桁
落ちを起こすことになるので注意が必要です. 実績のある解析プログラムでは桁落ちを考慮して, 極端に小さな
(大きな) 値に対する演算順序を変更し, 出来るだけ最後の段階で計算する工夫があります. しかしこれは並列化に
際して障害となりますし, またメモリの要求を厳しくする一因ともなります. そして何より, 計算結果の精度を悪
化させることになります.
幸い乗算は桁落ちを回避出来ます (もちろん有効桁数を越える精度は失いますが). そこで係数をスケーリング
するという対策が考えられます. 定数による行列全体のスケーリングに意味はありませんが, 行列によるスケーリ
ングで係数間のマグニチュードの差を縮めることが出来ます. ちなみに行列の乗算は非可換ですから, スケーリン
グは 2 種類考えられます. 左から乗じると行方向のスケーリング, 右から乗じると列方向のスケーリングです.
a11 . . . a1n
d11 a11 . . . d11 a1n
d11
.
..
..
..
..
..
.
.
.
.
.
. = ..
.
.
dnn
an1 . . . ann
dnn an1 . . . dnn ann
a11 . . . a1n
d11
d11 a11 . . . dnn a1n
.
.
..
..
..
..
..
.
= .
.
.
.
.
.
.
.
an1 . . . ann
dnn
d11 an1 . . . dnn ann
ところがスケーリングを施したとしても非対角な位置に対角より大きな要素が残ると, 依然として解き難い問
題となります. 条件数が大きいため反復法では顕著に解き辛くなりますが, 直接法においても分解の過程で大きな
非対角係数は対角係数に対して桁落ちを誘発し, 得られる解の精度を悪化させるためです. そこで更なる工夫とし
て行列要素の並び替えが考えられます.
理想的な行列は, 対角に大きな係数が並んだ (非対角には対角より小さい係数が並ぶ) ものです. このような行
列を対角優位な行列と呼びます. 乗算の非可換性から, 行列の並び替えも 2 種類のものが考えられます. 置換行列
を左から乗じると行方向の並べ替え, 右からだと列方向の並び替えです. たとえば置換 σ : (1 2 3 4) → (1 3 2 4) に
対して,
1
0
1
1
0
a11
a21
a
31
1
a41
a11
a21
a
31
a12
a22
a32
a13
a23
a33
a41
a42
a43
a12
a13
a22
a32
a23
a33
a14
a11
a14
a23
= a31
a34
a21
a12
a13
a32
a22
a33
a23
a34
a23
a42 a43 a44
a41
a14
1
a11
0 1 a21
a23
=
a34
1 0 a31
a44
1
a41
a42
a43
a44
a13
a23
a33
a12
a22
a32
a14
a23
a34
a43
a42
a44
となります. またこれを両側から乗じると, 対角要素の順番を並び替えることが出来, 専門用語でリオーダリング10
と呼ぶ操作となります.
行列要素を置換することで対角優位な並びに変換し, これをスケーリングすることで数値的に解き易い問題に
出来そうだと分かりました. しかしこの置換はどう決定すれば良いのでしょうか？一般に決め手は存在しません
10 リオーダリングは連立方程式を解く上で重要な 2 つの性質を左右します. 1 つはフィルインが変わること. もう 1 つは係数の依存関係を
変えることです. 前者は消費メモリを左右すると同時に条件数にも影響します. 後者は並列性に影響し, 高い並列性を持った行列は条件数が
改悪する傾向があります.
25
8
3*atan(x-1)+x/4
6
4
2
0
-2
-4
-6
-8
-10
-5
0
5
10
図 2: Newton 法が振動する関数
が, 経験的には次のような方針を立てることが出来ます.
max
σ
n
∑
ciσ(i)
i=1
log a − log |a | a ̸= 0
i
ij
ij
cij =
inf
otherwise
つまり係数行列を重み付きグラフの隣接行列表現と見做し, コスト関数を最小化するように完全マッチング問題
を解くわけです. 完全マッチング問題の計算量は O(n3 ) に対し, 連立方程式の計算量も O(n3 )
11
です. しかし元々
の行列が疎行列であるため, マッチング問題はほぼ O(n log n) で解くことが出来ます.
Newton 法が苦手な関数 1
非線形方程式を解くときに Newton 法は 2 次収束12 するため好んで用いられます. しかしこれは局所的な収束
性であり, 大域的には安定しません. よく知られているのが図 2 のような場合です.
図のようなムズカシい関数で無くとも, 例えば,
x3 − 2x + 2 = 0
という簡単な方程式を考えます.
初期値として x0 = 0 を選択13 すると, 次のように計算出来ます.
x0 = 0
(3x0 − 2)∆x1 = x30 − 2x0 + 2
x1 = x0 + ∆x1 = 1
(3x1 − 2)∆x2 = x31 − 2x1 + 2
x2 = x1 + ∆x2 = 0
11 実際のアルゴリズムはもっと速く,
直接法で O(n1.8 ), 反復法で O(n) です.
導関数が正確に求まる場合は,2 次収束します. しかし導関数が求まらない場合や近似的な導関数を用いた場合, Newton
法は 1 次収束となります.
13 初期値として 0 を選択することはよくあります. しかし Newton 法は大域的な収束の安定性が無いため, 初期値を任意に与えてしまうこ
とは望ましくありません. …とは言うものの, 多次元の場合には有効な初期値を探すのも一苦労.
12 厳密に言えば,
26
4e-35
(x-1)**8
3.5e-35
3e-35
2.5e-35
2e-35
1.5e-35
1e-35
5e-36
0
0.99996
0.99998
1
1.00002
1.00004
図 3: Newton 法の収束が遅い関数
なんと 2 回目の反復で初期値に戻ってしまいました. このような場合には改善量として数値摂動 (例えば機械イプ
シロン等) を与えるか, 2 分法で少し範囲を狭めた後に Newton 法に切り替えるというアプローチが有効です.
Newton 法が苦手な関数 2
収束する場合であっても, 非常に遅くなるような場合があります. 典型的なものが図 3 です. 方程式としては,
(x − 1)10 = 0
となります. 解は明らかに x = 1 です. 何故収束が遅くなるのでしょう？
実際に計算してみましょう. 方程式の導関数は容易に求まり,
10(x − 1)9
となります. たとえば近似解が x = 0.8 まで求まっていたとして, この導関数を用いて解の改善量が次のように定
まります.
10(0.8 − 1)9 ∆x = −(0.8 − 1)10
∆x = 2.0 × 10−2
真の解は x = 1 ですから, 今回の改善で解は 2% 近付いた14 ことになります. そして次の改善量は 2% を切ります.
残差が非常に小さく, また微分係数も小さいため, 反復を重ねる毎に改善量は減少し, x = 0.9 を越えた辺りでは
1% 以下の改善15 となります. この調子では,1% 以下の高精度な解を要求するとなかなか収束しません.
ここで注意しなければならないのは, 収束が遅いからと言って, 改善量が十分小さいときに収束したと判定する
のは間違いだということです. 今回であれば改善量が 1% と小さい場合でも, 真の解との誤差は 10% もあり, 実際
には全く異なる解16 であることが分かります. このような問題は指を咥えて収束を待つしかありません. 特に厄介
なのが, このように残差と微分係数が小さい領域の先で様子が激変する関数です. Newton 法を使って問題を解く
限り, この手の暗闇の中を手探りで進む感覚は拭えません. 精進しましょう.
14 ここでは例として真の解が分かっているものを使い, 近似解の改善の度合いを測っています. 当然ですが実際には解は未知ですから, どの
程度改善しているのか知る由はありません.
15 ちなみに数字のキリが良いのはわざとそういう方程式を選んだからで, 一般的には相対残差を見る必要があります.
16 もちろん逆の見方も出来ます. 関数値として見れば, 残差が十分に小さいため解と見做して良い場合です.
27
関数空間の使いどころ
Newton 法の収束を判断において, 解の改善量 ∆x と, 関数値としての残差 F (x) とでは, 異なることが先の例か
らも分かります. 特に実用上は数百万次元などの多次元空間を取り扱うことがあるため, どの段階で収束を止めて
良いのか (解の妥当性) は難しい問題です.
こんなときに威力を発揮するのが関数空間論です. 解の反復改良を作用素として Banach 空間で評価すること
で, 誤差の上限を見積ることが可能となります.
一般の n 次元で定義される関数 F (x) = {fk (x1 , · · · , xn )} x ∈ Ω の根を求めます. 一次導関数として Fréchet 微
分 Df (x) を次で定義します.
Df (x) = Lx
||f (x + h) − f (x) − Lx h||
=0
||h||
||h||→0
lim
いま何かしらの方法で近似解 x̂ が得られた場合, 次なる正の数 δ と 0 ≤ κ ≤ 1 が存在するとする.
Ω ≡ {x; ||x − x̂|| < δ} ⊂ Ω
δ
κ
, ∀x ∈ Ωδ
||Df (x) − Df (x̂)|| ≤ M
Mr ≤ δ
1−κ
s.t. ||F (x̂)|| ≤ r, ||Df (x̂)|| ≤ M
このとき a ∈ Ω が存在し,
||x̂ − a|| ≤
Mr
1−κ
であることが Kantrovich-Urabe の定理17 より言えます.
試しに簡単な 2 次元の場合に適用してみましょう. 次のような方程式を考えます.
f (x, y) = x2 − y 2 − 3x + 2 = 0
g(x, y) = 2xy − 3y = 0
ある計算のもとで近似解が x0 = 1.001, y0 = 0.0 と求まっています. この解の精度はいくらでしょうか？
まず F (x0 , y0 ) = (f (x0 , y0 ), g(x0 , y0 )) の Fréchet 微分を求めます.
(
)
2x − 3 −2y
∂(f, g)
DF (x, y) =
=
∂(x, y)
2y
2x − 3
(
)
2x − 2.002
−2y
DF (x, y) − DF (x0 , y0 ) =
2y
2x − 2.002
ここで近似解 x0 の δ 近傍を考えて,
√ √
√
||DF (x, y) − DF (x0 , y0 )|| = 2 2 (x − 1.001)2 + y 2 ≤ 2 2δ
と評価を得ます. またこの点で一度 Newton 法を解く (導関数の逆写像を求める) ことにより,
√
2
−1
||DF (x0 , y0 ) || =
0.998
√
となるので M = 2/0.998 と r = 0.000999 と決めて良さそうです. あとは Kantrovich-Urabe の定理を適用する
ため, 次なる δ と κ を探します.
√
2 2δ ≤ 0.998
√ κ
2
√
2
0.000999 1
1−κ 0.998 ≤ δ
17 証明は少し長いため割愛しますが大まかな流れとしては次のようになります. まず Banach 空間 B の線形写像 M : B → B と恒等写像
1
であることを利用して逆写像を評価します. 次にこの評価を用い,Newton 法によって定まる近
I : B → B について, (I − M )−1 ≤ 1−||M
||
似解の列が, 適当な閉包のもと Cauchy 列であることを言います. そして Cauchy 列に対する評価から上述の定理が導かれます.
28
δ について不等式を解くことで 0.00142
≤ δ ≤ 0.2495κ と求まります. 詳細を飛ばしますが 0 < 1 − κ から
1−κ
Mr
0.005742 · · · ≤ κ ≤ 0.994275 · · · となります. そこで下限と上限において 1−κ
を評価すると,
||(x0 , y0 ) − a|| ≤
Mr
= 0.001447 · · ·
1−κ
を得て, 近似解 (x0 , y0 ) の誤差は 0.15% 未満であることが分かります.
それはまた別のお話
今回は連立方程式の直接法や桁落ちの取扱いを主として書いてみました. 線形代数に絡んだ数値計算のお話と
しては, まだまだ沢山の話があります. 中でも重要なのは Jordan 形式をはじめとする標準形式の理論, そして固
有値の分布のお話です. また応用的な題材としても Krylov 部分空間の理論, そして局所 Fourier 解析と繋がる
Multigrid 法などがあります.
また最後に取りあげた関数空間論ですが, 専門書を紐解くと無限次元における形式的な記述に気後れしがちで
す. しかし実際には有限次元での議論18 にたいへん役立ち, 補間関数系の扱いや誤差論に直接応用が可能です.
ほかにも微分幾何に現われる主ファイバー束の自己同型写像は, タンパク質解析や素粒子など昨今の先端的問題
において重要なテクニックであり, 数学的な奥深さと応用上の効果があるという非常に美味しい題材です.
それらはまた, 次の機会に.
18 そもそも無限次元 (作用素など) では区別の着く別個の振舞いが, 有限次元 (行列など) では縮退を起こしてしまうという場合があります.
このような場合に, 無限次元での議論を有限次元に適用する意義があります.
29
30
31
シャロでも分かる！Iteratee 入門
lyrical logical
はじめに
この記事では、ここ最近一部界隈を賑わしている Iteratee とは何なのかを、可能な限り分かり易く、一から説
明します。実際の Iteratee ライブラリの使い方などには一切触れません。説明のためのコードには Scala を使い
ます。ある程度 Scala の知識がないと難しいと思います。また、Scala を使う都合上 Haskell での IO などの都合
についても触れません。トイズも必要ありません。
シャロっていうのは、ミルキィホームズのシャーロック・シェリンフォードさんのことです。かわいいですね。
Iteratee の目的と特徴
Iteratee は Haskell の従来の Lazy IO に比べ、速度、メモリ使用量ともに優秀で、かつ安全な入力処理の手法
として提案されました。これは Haskell における事情ですが、その他の重要な特徴として、記述力が高く、また
供給と消費の責任の分担が綺麗に行われているため、リソース管理やエラーのハンドリングを適切に行える、と
いう点があります。
主演は以下の二人です。
• Iteratee 型
• Enumerator 型
Iteratee とは、Enumerator とは何なのか？それぞれ順に説明します。
入力を処理する
Iteratee とは、入力を処理するものです。入力の処理というのは、単純に考えれば、入力を受け取り、何らか
の結果を返すものとして表すことができそうです。なんだかよくわからない、という人は次のようなメソッドを
イメージしてください。
1
def process [ Input , Result ]( input : Input ) : Result
ここでは入力は文字列、つまり String 型の値として与えられる、と仮定しましょう。
1
type Input = String
すると Iteratee 型は単純に以下のように定義できます。
1
case class Iteratee [ Result ]( process : Input = > Result )
与えられた文字列の先頭文字を返す Iteratee peek は以下のように定義できます。
32
1
2
3
4
val peek : Iteratee [ Option [ Char ]] = Iteratee {
case " "
= > None
case input = > Some ( input . head )
}
入力が残っていなかった場合には None を返し、残っていた場合には先頭文字を返しています。簡単ですね。
入力を消費する
Iteratee とは、入力を消費するものです。先ほど定義した peek を実際に使ってみます。
scala> peek.process("input")
res0: Option[Char] = Some(i)
この場合、消費された入力と、消費されなかった入力は何でしょうか？手続き形言語などでは、入力を「破壊」
することで消費を表現したりもしますが、String 型の値は変更することができません。何が消費されたのか分か
るように、結果だけでなく、消費されなかった入力も返すよう Iteratee 型の定義を変更しましょう。
1
case class Iteratee [ Result ]( process : Input = > ( Result , Input ))
peek は入力を消費しない処理なので、以下のような定義になります。
1
2
3
4
val peek : Iteratee [ Option [ Char ]] = Iteratee {
case " "
= > ( None , " " )
case input = > ( Some ( input . head ) , input )
}
これで、消費されなかった入力が返されるようになりました。
scala> peek.process("input")
res1: (Option[Char], String) = (Some(i),input)
現実の入力
ここまで、理想的な前提の下で話を進めてきました。ここで一度、現実世界ときちんと向き合いましょう。入
力というのは、一度に全て取得できるものでしょうか？答えは勿論ノーです。入力は、通常小さなブロックに分
けて届けられます。標準入力やファイルの読み込み、ソケット間の通信について考えてみてください。
効率を気にしないのであれば、全ての入力をメモリ上に読み込んでから、処理することはできます。しかし
Iteratee ではそれはしません。Iteratee は、効率的な入力処理を目標としているためです。よって、Iteratee は細
切れに与えられる入力のそれぞれについて処理しなければいけない、ということになります。
細切れに与えられる入力が、どのような型として表現できるかを考えてみます。まずは Byte 型の値、つまり
入力がバイト単位で与えられると仮定しましょう。
1
type Input = Byte
入力はいずれ尽きます。Byte 型の値では、入力の終端を表現することはできません。終端を表現できるよう、
入力を終端の場合とそうでない場合に分けて定義することにしましょう。
1
2
3
sealed abstract class Input
case class Chunk ( chunk : Byte ) extends Input
case object EOF extends Input
実際には、入力はバイト単位で与えられるとは限りません。Char 型や Array[Byte] 型や、String 型などの値
として与えられる可能性があります。チャンクが扱う値の型は、型パラメタとしてとるようにしましょう。
33
1
2
3
sealed abstract class Input [ Elem ]
case class Chunk [ Elem ]( chunk : Elem ) extends Input [ Elem ]
case object EOF extends Input [ Nothing ]
本来ならばこのようなジェネリックな定義にすべきなのですが、簡単のために以下では Elem = String に限定
して話を進めたいと思います。
1
2
3
sealed abstract class Input
case class Chunk ( chunk : String ) extends Input
case object EOF extends Input
入力を要求する
Iteratee とは、入力を要求するものです。といっても、これだけでは何のことか分からないと思います。ひと
まず、新しい Input 型の定義に従い peek を再び定義し直してみましょう。
1
2
3
4
5
val peek
case s
case s
case s
}
:
@
@
@
Iteratee [ Option [ Char ]] = Iteratee {
Chunk ( " " )
= > ( None , s )
Chunk ( chunk ) = > ( Some ( chunk . head ) , s )
EOF
= > ( None , s )
この新しい定義は、本当に peek の処理として妥当なものでしょうか？最初のパターンに注目してください。空
文字列を持つチャンクは、最早終端を表すものではありません。それは EOF で表されます。空文字列を持つチャ
ンクは、単に「現在供給されている入力はもう残っていない」という状態を表しています。つまり、供給されてい
ないだけで、まだ入力が残っている可能性がある、ということです。それを無視して「先頭文字はない」と None
を返してしまうのは、適切な振る舞いではありません。
処理に必要な分の入力が供給されていないということは、次の入力を要求しなければなりません。さて、入力
の要求はどのようにして表現すべきでしょうか？まだ処理が終了していないことを Option 型を用いて表現して
みるとします。
1
case class Iteratee [ Result ]( process : Input = > ( Option [ Result ] , Input ))
このような定義にしてしまうと、Iteratee は処理の進捗を、状態として管理せざるを得なくなってしまいます。
できれば状態は排除したいものです。処理に必要な分の入力が供給されなかったため、入力を要求している。こ
れは、まだ必要な処理が残っている、という風に言い換えることができます。それならば、残ってしまった処理
を返してしまうことで、入力を要求してみましょう。処理とは…Iteratee そのものです！
1
case class Iteratee [ Result ]( process : Input = > ( Iteratee [ Result ] , Input ))
これはうまい定義に見えますが、この定義では処理が終了しても結果を返すことができません。少し整理しま
しょう。Iteratee には、処理が終了した状態と、処理が終了しなかった状態がある、ということが分かりました。
これを、そのまま素直に定義してみましょう。
1
2
3
sealed abstract class Iteratee [ Result ]
case class Done [ Result ]( result : Result ) extends Iteratee [ Result ]
case class Continue [ Result ]( step : Input = > ( Iteratee [ Result ] , Input )) extends Iteratee [ Result ]
この定義では、Iteratee は処理の進捗を状態として管理する必要はありません。綺麗に状態を排除することが
できました。新しい Iteratee の定義に従い peek を三度定義しなおしてみましょう。
1
2
3
4
5
val peek
case s
case s
case s
}
:
@
@
@
Continue [ Option [ Char ]] = Continue {
Chunk ( " " )
= > ( peek , s )
Chunk ( chunk ) = > ( Done ( Some ( chunk . head )) , s )
EOF
= > ( Done ( None ) , s )
空文字列の場合には、入力が足りなかったためにできなかった残りの処理、つまり peek 自身を返しています。
scala> peek.step(Chunk(""))
res6: (Iteratee[Option[Char]], Input) = (Continue(\<function1>),Chunk())
34
エラーを返す
Iteratee とは、エラーを返すものです。例えば peek と異なり、入力を消費し、先頭文字列を返す Iteratee head
を定義してみましょう。これは String 型（正確には WrappedString 型）の持つメソッド head 同様に Char を
返すようにします。
1
2
3
4
5
val head
case s
case s
case s
}
:
@
@
@
Continue [ Char ] = Continue {
Chunk ( " " )
= > ( head , s )
Chunk ( chunk ) = > ( Done ( chunk . head ) , Chunk ( chunk . tail ))
EOF
= > (??? , s )
さて困りました。head は EOF を入力として渡された時、何を返せばいいのでしょうか？空文字列の場合には
peek 同様に自身を返せば問題ありません。しかし EOF が入力として与えられたということは、入力の終端に達
し、もう入力は残っていないということです。peek ならば None を返せばよかったところですが、head は Char
を返す Iteratee です。Char 型の値で、返すことができる妥当なものはありません。かといって空文字列の場合
同様に自身を返すのは間違いです。入力はもう残っていないのだから、要求してももう入力が与えられることは
ありません。
結局のところ、これはエラーとして処理すべきです。エラーはどのように表現すべきでしょうか？最初に思い
つくのは、Iteratee の返す結果の型を Either 型にしてしまうことです。
1
2
3
4
5
val head
case s
case s
case s
}
:
@
@
@
Continue [ Either [ String , Char ]] = Continue {
Chunk ( " " )
= > ( head , s )
Chunk ( chunk ) = > ( Done ( Right ( chunk . head )) , Chunk ( chunk . tail ))
EOF
= > ( Done ( Left ( " EOF " )) , s )
これは一見妥当なように見えますが、果たして本当にそうでしょうか？エラーについて、もう少しについて考
えてみましょう。
エラーには、回復可能なエラーと、回復不可能なエラーが存在します。回復不可能なエラーが発生した場合に
は、それ以上できることはありませんから、残りの処理が失われても特に問題はありません。しかし、回復可能
なエラーが発生した場合には、残りの処理は失われて欲しくありません。何故なら、適切にエラーを処理した後
で、処理を再開する必要があるかもしれないからです。
Either 型を使った定義の場合、残りの処理を返すことはできません。Iteratee の中には回復可能なエラーを発
生するものもあるでしょうから、これは問題になります。エラーと同時に残りの処理を返すことができるよう、
Continue 型の定義を変更してやることにしましょう。
1
case class Continue [ Result ]( step : Input = > ( Iteratee [ Result ] , Input ) , error : Option [ String ] = None ) extends Iteratee
これで head は以下のように定義できます。
1
2
3
4
5
6
7
8
val head : Continue [ Char ] = {
lazy val step : Input = > ( Iteratee [ Char ] , Input ) = {
case s @ Chunk ( " " )
= > ( Continue ( step ) , s )
case s @ Chunk ( chunk ) = > ( Done ( chunk . head ) , Chunk ( chunk . tail ))
case s @ EOF
= > ( Continue ( step , Some ( " EOF " )) , s )
}
Continue ( step )
}
これでエラーを扱うことができるようになりました。といっても、このエラーは回復不可能でしょうが…
処理を変換する
Iteratee とは、変換されるものです。変換とは、ある型の値を結果として返す Iteratee から、別の型の値を結
果として返す Iteratee を作ることです。これは List などのコレクション型における map メソッドに相当します。
1
2
3
sealed abstract class Iteratee [ Result ] {
def map [ A ]( f : Result = > A ) : Iteratee [ A ]
}
35
Done と Continue のそれぞれについてメソッドを実装しましょう。Done の定義は、単に関数を適用するだけ
です。
1
def map [ A ]( f : Result = > A ) : Iteratee [ A ] = Done ( f ( result ))
Continue の定義は少し複雑に見えますが、処理が終了するまで関数をたらい回ししているだけです。
1
2
3
4
5
6
7
def map [ A ]( f : Result = > A ) : Iteratee [ A ] = {
val s : Input = > ( Iteratee [ A ] , Input ) = { input = >
val ( next , unconsumed ) = step ( input )
( next . map ( f ) , unconsumed )
}
Continue (s , error )
}
忘れずにエラーを伝播することが重要です。
これで、先頭文字を Char 型ではなく String 型として返す Iteratee を head を変換することで作りだすことが
できます。
scala> head.map(_.toString)
res8: Iteratee[java.lang.String] = Continue(\<function1>,None)
処理を合成する
Iteratee とは、合成されるものです。変換の次は合成です。合成とは、ある Iteratee の処理をした後、残りの
入力に対して別の Iteratee の処理を行う Iteratee を作ることです。合成ではなく連結と表現したほうが分かりや
すいかもしれません。これは List などのコレクション型における flatMap メソッドに相当します。
1
def flatMap [ A ]( f : Result = > Iteratee [ A ]) : Iteratee [ A ]
また Done と Continue のそれぞれについてメソッドを実装しましょう。Done の定義は map 同様、単に関数
を適用するだけです。
1
def flatMap [ A ]( f : Result = > Iteratee [ A ]) : Iteratee [ A ] = f ( result )
Continue の定義は少し難しいものになっています。
1
2
3
4
5
6
7
8
9
10
11
12
13
def flatMap [ A ]( f : Result = > Iteratee [ A ]) : Iteratee [ A ] = {
val s : Input = > ( Iteratee [ A ] , Input ) = { input = >
step ( input ) match {
case ( Done ( result ) , unconsumed ) = >
f ( result ) match {
case Continue (s , None ) = > s ( unconsumed )
case iteratee = > ( iteratee , unconsumed )
}
case ( iteratee , unconsumed ) = > ( iteratee . flatMap ( f ) , unconsumed )
}
}
Continue (s , error )
}
合成された Iteratee は、まず最初の Iteratee に入力を与えます。ここで何らかの結果が得られた場合には、そ
の結果から次の Iteratee を作り出します。次の Iteratee が入力を処理できる状態であれば、一つ目の Iteratee
が消費しなかった残りの入力をここで処理します。次の Iteratee が入力を処理できる状態になければ、一つ目の
Iteratee が消費しなかった残りの入力は処理せずに、Iteratee と共に返します。最初の Iteratee に入力を与え、結
果が得られなかった場合には、一つ目の Iteratee が消費しなかった残りの入力は処理せずに、再度合成しなおし
た Iteratee と共に返します。ここでも矢張りエラーの伝播を忘れてはいけません。
これで、先頭二文字を返す Iteratee を二つの head を合成することで作ることができます。
scala> head.flatMap(c1 => head.map(c2 => c1.toString + c2))
res4: Iteratee[java.lang.String] = Continue(\<function1>,None)
二つの処理を合成する上で、入力の再要求や、エラーの伝播のための煩雑なコードを書く必要は一切ありませ
ん。それらは flatMap が全てうまく面倒をみてくれます。とはいえ、これはいささか記述性が悪すぎます。
36
for 内包表記による変換と合成
Scala には、map や flatMap などの一部のメソッドの呼び出しを簡潔に書くための言語機能として、for 内包
表記が備わっています。これを使うことで Iteratee の変換や合成を、より簡単に記述することが可能になります。
for 内包表記を使えば、先頭二文字を返す Iteratee は、次のように作ることができます。
1
2
3
for {
c1 <- head ; c2 <- head
} yield c1 . toString + c2
可読性、記述性共にかなりよくなりました。
説明の都合上、peek と head 以外の Iteratee はここでは定義しません。peek と head この二つの Iteratee を
組み合わせるだけでは、現実の入力処理を書くことは難しいでしょう。実際にはより多くの Iteratee を予め定義
しておく必要があります。しかし、兎に角重要なのは、Iteratee を変換、合成しながらより大きな Iteratee を定
義することができる、ということです。
責任の分担
ここまで、入力の処理を行う Iteratee について説明してきました。Iteratee は、処理のために入力を要求しま
す。入力がどのように供給されるかを気にせずに、処理を記述できるのが Iteratee の持つ良い性質の一つでもあ
ります。では、一体誰が入力を供給する役目を負うのでしょうか？この役目を負うのが Enumerator です。
入力を供給する
Enumerator とは、Iteratee に入力を供給するものです。これは単純に考えれば以下のような型で表現できそう
です。
1
2
3
abstract class Enumerator {
def feed [ Result ] : Iteratee [ Reuslt ] = > Result
}
ところが、この定義では問題が生じます。例えば、引数に指定された文字列をチャンクとして供給する Enumerator
を定義してみましょう。
1
2
3
4
5
6
7
8
9
10
def enumChunk ( chunk : String ) ; Enumerator = new Enumerator {
def feed [ Result ] = {
case Done ( result ) = > result
case Continue ( step , None ) = >
step ( Chunk ( str )) match {
case ( Done ( result ) , _ ) = > result
case i = > ???
}
}
}
入力を供給せずとも、既に処理が終了していることもあります。この場合には、単に結果を取り出せば問題あ
りません。入力が要求されている場合には、入力を供給してやります。ここで処理が終了すれば、結果を取り出
すことができます。しかし、入力を供給しても、処理が終了するとは限りません。これは困りました。
処理を進める
Enumerator とは、Iteratee の処理を進めるものです。Iteratee は処理の進捗を状態として管理しない、という
ことを思い出してください。状態を管理してやるのは Enumerator なのです。
Iteratee はその性質上、入力を供給しても、結果が得られるとは限りません。これは既に見たとおりです。そ
のため Enumerator は、単に結果を返すものとしてではなく、処理の進んだ Iteratee を返すものとして定義する
必要があります。
37
1
2
3
abstract class Enumerator {
def feed [ Result ] : Iteratee [ Reuslt ] = > Iteratee [ Result ]
}
新しい定義にあわせて enumChunk を定義しなおしてみましょう。
1
2
3
4
5
6
def enumChunk ( str : String ) : Enumerator = new Enumerator {
def feed [ Result ] = {
case Continue ( step , None ) = > step ( Chunk ( str )). _1
case iteratee = > iteratee
}
}
Iteratee に入力を要求されている時にのみ、チャンクを供給してやります。Enumerator は、基本的に既に処理
が終了している、もしくはエラーが発生している場合には、入力を供給せずそのまま iteratee を返す形の定義に
なります。
次は入力の終端を通知する、つまり EOF を供給する Enumerator を定義してみましょう。
1
2
3
4
5
6
7
8
9
10
11
val enumEOF : Enumerator = new Enumerator {
def feed [ Result ] = {
case Continue ( step , None ) = >
step ( EOF ) match {
case ( Continue ( step , None ) , _ ) = >
throw new I l l e g a l S t a t e E x c e p t i o n ( " Iteratee must not request more inputs " )
case ( iteratee , _ ) = > iteratee
}
case iteratee = > iteratee
}
}
これも enumChunk 同様の単純な定義にしてもよいのですが、ここではもう少し色々なことをしています。EOF
が供給されたにも関わらず、エラーが起きたわけでもないのに更に入力を要求してくる Iteratee は、行儀の悪い
Iteratee です。これは Iteratee 側の明らかなバグですから、例外を投げてしまうことにしましょう。
入力を連結する
Enumerator とは、入力を連結するものです。これまで定義してきた Enumerator は、入力を一度しか供給しな
いものでした。しかし実際には、入力は繰り返し供給する必要があります。何より enumChunk だけでは入力の
終端を通知することができません。enumChunk と enumEOF を使い、いくつかのチャンクを供給した後、EOF
で入力の終端を通知してみましょう。
scala> enumEOF.feed(enumChunk("b").feed(enumChunk("a").feed(head)))
res8: Iteratee[Char] = Done(a)
こんな風にしか書けないのでは、記述性に難が有ると言わざるを得ません。Enumerator も、文字列などのコ
レクションのように、連結を定義したいところです。Enumerator の連結は、以下のような定義になります。
1
2
3
4
5
6
abstract class Enumerator { self = >
def feed [ Result ] : Iteratee [ Result ] = > Iteratee [ Result ]
def ++( other : Enumerator ) = new Enumerator {
def feed [ Result ] = other . feed . compose ( self . feed )
}
}
Enumerator は、入力そのものというよりは、入力を供給する「関数」です。そのため、複数の Enumerator を
連結することは、入力を供給する関数の合成として定義することができるわけです。
scala> (enumChunk("a") ++ enumChunk("b") ++ enumEOF).feed(head)
res9: Iteratee[Char] = Done(a)
定義したメソッドを使うことで、例えば与えられた Iterable[String] から、各要素をチャンクとして供給する
Enumerator を作ることができます。
38
1
2
3
val enumNothing : Enumerator = new Enumerator { def feed [ Result ] = identity }
def enumIterable ( iterable : Iterable [ String ]) : Enumerator =
iterable . foldLeft ( enumNothing ) { ( acc , chunk ) = > acc ++ enumChunk ( chunk ) }
入力を一切供給しない Enumerator をシードに、Iterable を畳みこむことで、より大きな Enumerator を作り
出しています。
副作用を伴う
Enumerator とは、副作用を伴うものです。これまで定義してきた Enumerator は、どれも副作用を伴いませ
ん。何度入力を Iteratee に供給しようと、結果は変わりませんでした。
scala> val enum = enumIterable(List("a", "b")) ++ enumEOF
enum: Enumerator = Enumerator$$anon$1@184747e
scala> enum.feed(head) == enum.feed(head)
res6: Boolean = true
では、Iterator[String] から各要素をチャンクとして供給する、次のような Enumerator ではどうでしょうか。
1
2
3
4
5
6
7
8
9
10
11
def enumIterator ( iterator : Iterator [ String ]) : Enumerator = new Enumerator {
def feed [ Result ] = { iteratee = >
if ( iterator . isEmpty )
iteratee
else
iteratee match {
case Continue ( step , None ) = > feed ( step ( Chunk ( iterator . next )). _1 )
case iteratee = > iteratee
}
}
}
Iterator クラスの next は、副作用を伴います。そのため、一度チャンクとして供給した入力は失われてしまい
ます。
scala> val enum = enumIterator(List("a", "b").iterator) ++ enumEOF
enum: Enumerator = Enumerator$$anon$1@bcf47
scala> enum.feed(head) == enum.feed(head)
res8: Boolean = false
Enumerator は入力を供給するために、実際のリソースを扱います。リソースに対する操作は、通常何らかの
副作用を伴います。
Iteratee と Enumerator
Iteratee は、入力ストリームに含まれる小さなチャンクを一つずつ処理します。入力や処理の進捗の管理は行
いません。それを行うのは Enumerator です。Iteratee に入力を繰り返し供給し、結果が得られるまで処理を進
めます。この記述がすっと理解できれば、Iteratee とは何なのかが分かった、と胸をはっていえると思います。お
つかれさまでした！
扱わなかったこと
この記事は Iteratee に対する初歩的な理解の手助けを目的としていたため、扱わなかったことがいくつかあり
ます。ここで、それらまとめて簡単に紹介、説明したいと思います。
39
より多くの Iteratee の定義
記事では peek と head の二つの Iteratee だけを定義しましたが、これだけでは全く足りません。drop や
takeWhile などの基本的な操作を自分で定義してみるのは、Iteratee をより深く理解する上でいい練習になると
思います。本当はちゃんと扱いたかったんですが、コードもそれに対する説明も長くなってしまうので、仕方な
くやめました。
より一般的な Iteratee と Enumerator
ここまで、チャンクの持つ値型を String に限定して話を進めてきました。これも矢張り、現実には困ります。
とはいえ、チャンクの持つ値型をジェネリックにすると、Iteratee の定義が難しくなります。例えば head を定義
することはできるでしょうか。
1
2
3
4
5
6
7
def head [ Elem ] : Continue [ Elem , Char ] = {
lazy val step : Input = > ( Iteratee [ Elem , Char ] , Input ) = {
case s @ Chunk ( chunk ) = > ???
case s @ EOF
= > ( Continue ( step , Some ( " EOF " )) , s )
}
Continue ( step )
}
チャンクの持つ値に対する操作が何も提供されていないので、これはどうやっても定義できません。そのため、
ジェネリックな Iteratee を定義する際には、ある程度の制約を型に課してやる必要があります。Scala なら Iterable
に対する view bound を利用するのが妥当でしょう。
1
2
3
4
5
6
7
8
def head [A , Elem <% Iterable [ A ]] : Iteratee [ Elem , A ]
lazy val step : Input = > ( Iteratee [ Elem , A ] , Input ) = {
case s @ Chunk ( chunk ) if chunk . isEmpty = > ( Continue ( step ) , s )
case s @ Chunk ( chunk ) = > ( Done ( chunk . head ) , Chunk ( chunk . tail ))
case s @ EOF
= > ( Continue ( step , Some ( " EOF " )) , s )
}
Continue ( step )
}
設計上の選択
チャンクの持つ値型だけでなく、Continue 型の持つエラー型についても同じことがいえます。Option[String]
では、エラーの判別が余りにも大変です。とはいえ、エラーの表現をジェネリックにすると、型パラメタが増え
すぎてしまいます。Exception 型あたりにしておくのが無難かもしれません。Iteratee には、このような設計上
の選択肢がいくつもあります。
例えば、バイト単位の入力の表現として、さらりと次のような定義を行っていました。
1
2
3
sealed abstract class Input
case class Chunk ( chunk : Byte ) extends Input
case object EOF extends Input
実は、この定義には問題があります。Byte 型の値では、「入力が消費されつくした状態」を表現することがで
きないのです。Byte 型を直接扱うのでなく Option[Byte] にするということもできますが、これは正直イマイチ
です。そこで、Input 型で「消費されつくした状態」を表現できるようにしよう、という選択肢もあります。
1
2
3
4
sealed abstract class Input [ Elem ]
case class Chunk [ Elem ]( chunk : Elem ) extends Input [ Elem ]
case object Empty extends Input [ Nothing ]
case object EOF extends Input [ Nothing ]
しかしこうすると、Elem が「消費されつくした状態」を表現できる場合に、コードの重複が発生してしまう、
という問題があります。
そもそも Iteratee や Enumerator の定義には、次のようなパターンが頻出します。
40
1
2
case iteratee = > ( iteratee , s )
case iteratee = > iteratee
他にも、Enumerator 側で入力の供給中にエラーが発生した場合には、そのエラーを Iteratee 側に通知しよう
とか、Iteratee 側から Enumerator 側にシークのような注文をつけられるようにしようとか、Continue にエラー
を持たせずにエラーはエラーで別に表現しようとか、とかとか…
そんなわけなので、実際の Iteratee ライブラリにも様々な差異があって、なんならバージョン毎にも色々違っ
ていて…大変ですね！
モナド
Iteratee は Haskell 生まれの入力処理の手法です。Haskell といえばモナドです。Iteratee も当然モナドとの関
連があります。Continue 型の持つ関数は実際 State モナドですし、for 内包表記が利用できることからも分かる
ように Iteratee 自身もモナドです。モナド変換子でもあります。ただ、最初からモナドってなんだかよくわから
ないよ、という人にも分かるようなものを書こうという気持ちがあったので、モナディックな要素は一切排除し
ました。そのあたりが知りたい人からすれば、少し物足りなかったかもしれません。
Enumeratee 型
現実には、入力ストリームをそのまま扱うことは稀です。バッファリングや暗号、圧縮の復元、エンコーディ
ングなど、何らかの「前処理」を施した上で処理を行います。これを行うのが Enumeratee 型です。大体次のよ
うな定義になります。
1
2
type Enumeratee [ InnerElem , OuterElem , Result ] =
Iteratee [ InnerElem , Result ] = > Iteratee [ OuterElem , Iteratee [ InnerElem , Result ]]
なんだか難しいそうですね。ところがどっこい！これが…難しいです、ハイ。型を素直に見れば、これは Iteratee
を引数として取る Iteratee として見ることができます。一方で、Iteratee を取り Iteratee を返す、ということで
Enumerator 型に似ているわけですが、実際 Enumeratee は特殊な Enumerator として見ることも可能です。こ
れはモナディックな視点からみてみると、その傾向がより顕著になります。
本当は Enumeratee も詳しく説明したかったのですが、色んな余裕が足りませんでした。ごめんなさい！
まとめ
扱わなかったことがいくつかあります
いくつかだって？と思うほどに、たくさん扱わなかったことがありますね。Iteratee は、より正確には Iteratee
が解決しようとしている現実の入力処理は、それだけ複雑だということがいえると思います。ボクがサボったと
か、そういうことではないのです、エエ、本当です。信じてください！
この記事で Iteratee の基本的な概念を理解したら、次は Enumeratee を理解する、Iteratee ライブラリを自分
で設計してみる、実際の Iteratee ライブラリを使ってみる、ニンジャセッションを行いカラテを高める、ミルキィ
ホームズ二期に備えて精神統一する、何をするかはあなた次第！ボクはミルキィホームズ二期を推しますけどね！
41
計算機肉体派宣言
m0h1can
1. 計算機肉体派宣言
計算機に関して現代に生きる我々は 2 つの異なる源流を辿ることが出来る. 1 つは G. W. Leibniz を端とする
普遍言語による万物の記述であり, K. Gödel そして A. M. Turing によって記念碑が打ち立てられた. もう 1 つは
C. Babbage を祖とする計算機械の歴史であり, V. Bush や J. von Neumann そしてまた A. M. Turing が大きな
足跡を残している. 科学技術の発達と共に足を進めてきた計算機にとってこの 2 つの流れは両輪であったが, 今や
我々は計算の多くを計算機上で抽象化された論理に依っている. しかし一度両輪が歩みを乱せば, 堆く築き上げた
抽象の塔は底が抜け, 大地に穿たれた深き穴から混沌とした物理的強度を伴った体躯が顔を覗かせる.
我々は片輪に依拠してはならない. 清貧たる高邁な精神を糧とし, 結晶のような整然とした理の塔を築く一方で,
屈強なる筋肉を軽やかに弾ませ, 自然に在る幾万の原子を統率して道を拓くのだ. ここに私は良き精神を宿す良き
肉体の追求を提唱する. “健全なる計算は健全なる機械に宿る”
2. 究極の秤を求めて
C. Babbage は歯車を選んだ. 当時の加工技術における最良の選択肢だったに違いない. V. Bush は電気仕掛け
の歯車で 18 変数の微分解析器を創造した. だが見よ, 今や我々は 1cm 四方の空間に 25e8 個の半導体ゲートを容
易に埋め込める. その結果, かつて先人が築き上げた初期の計算機は, この半導体の中で計算として表現されるに
至った. これこそが, 健全なる計算の姿である.
いま再び宣言を思い出そう-“健全なる計算は健全なる機械に宿る”-そうである！我々はこの崇高な計算のため
に神を代弁する高貴なる肉体を必要としている！
！選り優りの肉体を, 精緻にして強靭な肉体を, 豪奢かつ () たる
肉体を！
！
！
・
・
・斯くたる肉体を得るために我々は秤を必要とする. 神の天秤を！
！
！
！
根源的にして妥協の無い神の計量のみが, 真に健全なる肉体を知り得るのである. そしてこのための秤を構築す
ることこそが, 我々人類に与えられた至上命題であろう. よろしい, ならばつくろう. 究極の秤を.
3. 真実の源泉
神が定めし真理を測るために俗世の慣習が立ち入る隙は無い. ただ原理的に必然, 定義として一意なるもののみ
が神の世に棲まうことができよう. ならば, このケイ素の塊もまた原理的にのみ記述し尽さねばならぬ. 石ころに
詰まった神の意思, 電子と正孔が折り成す雷の営み, これを知らねばらなぬ. まずはキャリア (電子あるいは正孔)
∫
が分子中に分布している様子を考える.
n(x, t) =
f (v, x, t)dv
ここではキャリアの分布 n(x, t) はキャリアの取る全ての速度で確率密度関数 f (v, x, t) を積分して定義する. 3 次
元空間を考えると関数 f (v, x, t) は 6 次元の相空間となる. 関数 f (v, x, t) の全微分から平衡状態を求める.
df (v, x, t)
=0
dt
42
これを各成分による偏微分で展開すると,
∂f
∂f ∂x ∂f ∂v
+
+
=0
∂t
∂x ∂t
∂v ∂t
ここで F = m ∂v
∂t および v =
∂x
∂t
より,
∂f
∂f
F ∂f
+v
+
=0
∂t
∂x m ∂v
と書ける. 力 F は粒子の衝突により生じる力 Fcoll と, 系外部より与えられる外力 Fext に分けることで次のように
書き直せる.
∂f
∂f
F ext ∂f
F coll ∂f
∂f +v
+
=−
=
∂t
∂x
m ∂v
m ∂v
∂t coll
これは Boltzmann 輸送方程式 (BTE) である.
確率論に従えば確率密度関数はモーメント展開できる. そこで物理的な意味との対応を見るために, 各モーメン
ト Y (x, t) を n(x, t) で正規化する. すなわち,
Y (x, t) =
1
n(x, t)
∫
Y (x, t)f (v, x, t)dv
としてモーメントを記述する. ここで Y (v, t) = 1 とすれば, この 0 次モーメントはキャリアの分布量19 を与える.
逐次的に高次モーメントを求めることで観測可能な各物理量が求まる. このとき, ある次数以上のモーメントは物
理的に不要となることを以降で確認する.
3.1. 質量の保存
Y (x, t) = 1 として BTE の 0 次モーメント Y に関する式を求める.
∫
∫
∫
∫
∂f
∂f
F ext ∂f
∂f Y
dv + Y v
dv + Y
dv = Y
dv
∂t
∂x
m ∂v
∂t coll
項毎に分けて考える.
まず第一項はモーメントの定義より,
∫
∫
∂
∂
∂n
∂f
dv =
Y f dv = (n(x, t)Y ) =
Y
∂t
∂t
∂t
∂t
となる.
次に第二項だが, 粒子の速度 v をランダムな成分 u とドリフト成分 v d に分けて計算する. ランダムな速度成分
は u = 0 であることに留意し,
∫
Yv
∂f
dv = ∇
∂x
∫
Y vf dv = ∇(nY v) = n∇v d
と求まる.
第三項はポテンシャル ϕ が速度に依存しないためにゼロとなる.
右辺に目を向けると, キャリアの衝突に関して分布の変化を全速度で積分する必要がある. 残念ながら BTE か
らは衝突の力学について情報を得ることは出来ないため, この項は後ほど検討する. 結論だけ先に述べておくと,
キャリアの生成 G と消滅 R が起こり, その差分 G − R が分布として残る. なおキャリアとして電子を考えた場合
と正孔を考えた場合は正負が逆転する.
以上よりキャリアの分布量に関する式, すなわち質量の保存式を得る.
∂n
+ n∇v d = G − R
∂t
19 n(x, t)
で正規化されていることに注意.
43
3.2. 運動量の保存
Y (v, t) = mv として BTE の 1 次モーメント Y に関する式を求める.
第一項はランダム速度とドリフト速度の関係を用い,
∫
∂f
∂v d
Y
dv = mn
∂t
∂t
である.
第二項はランダム速度の二乗はゼロとならないことに留意する必要がある. またモーメントがベクトルである
ので第二項はテンソル T となる. 各テンソル成分 Ti を計算するためには速度を (vx , vy , vz ) として成分展開し,
∫∫∫
∫
∂f
∂f
∂f
∂f
dv =
Y (vx
+ vy
+ vz
)dvx dvy dvz
Yv
∂x
∂x
∂y
∂z
を解かなくてはならない. ランドム速度に関するテンソルの非対角項は線形近似 (つまり無視) することにより,
(
)
∂vdi vdy
∂vdi vdz
∂u2i
∂vdi vdx
Ti = mn
+
+
+
∂x
∂y
∂z
∂xi
と書ける. この u2i の項は, 元の分布関数 f が Boltzmann 統計に従うものとして,
∫
mu2i f du = nkB T
という関係を用いて消去出来る. すなわち,
∫
∂f
Yv
dv = mn∇v 2d + nkB ∇T
∂x
である.
また第三項は,
∫
Y
F ext ∂f
dv = −nFext
m ∂v
である.
以上より運動量の保存式が次で定まる.
∂v d
+ mn∇v 2d + nkB ∇T − nFext =
mn
∂t
∫
∂f mv
dv
∂t coll
3.3. エネルギーの保存
Y (v, t) = 12 mv 2 として BTE の 2 次モーメント Y に関する式を求める.
第一項はこれまで同様に速度のランダム成分とドリフト成分を考え,
∫
)
∂f
mn ∂v
mn ∂ ( 2
Y
dv =
=
v d + u2
∂t
2 ∂t
2 ∂t
となる. ここでランダム成分の項は半導体中のキャリアの位置によって振舞が変わるが, これらは後ほど必要に応
じて考慮する.
第二項も同様に計算20 すると,
∫
mn
1
∂f
dv = ∇{nv d m(v 2d + u2 ) + mn(v d u)u} =
∇{v d (v 2d + u2 )} + nkB ∇v d T
Yv
∂x
2
2
と展開され, 速度 v d で電子および熱エネルギーを輸送していること (熱流束の存在) が分かる.
20 ランダム速度の奇数次項は平均化によって全てゼロとなることに留意.
44
BTE の 2 次モーメントを求めると熱流束が現われることが分かった. するとこれまでの議論で近似していた運
動量テンソルの非対角成分が必要となり, 常に更なる高次モーメントを計算しなくてはならない. そこで熱伝導が
温度勾配に比例するという現象論を用い, 熱流束に対して制約条件を施す. すなわち熱流量 Jq を,
Jq =
mn 2
u u
2
として記述する一方で, 現象論的に,
Jq = −κ∇T
により与える. ここで熱伝導率を κ とした. これにより第二項は補正され,
∫
∂f
mn
Yv
dv =
∇{v d (v 2d + u2 )} + nkB ∇v d T − κ∇T
∂x
2
と定まる. これにより 3 次以上のモーメントは不要となる.
なお第三項は速度に依存しないため次のように計算出来る.
∫
F ext ∂f
dv = −nv d F ext
Y
m ∂v
以上をまとめるとエネルギーの保存に関する式は,
∂w
n
+ ∇(nv d w + nkB v d T − κ∇T ) − nv d F ext =
∂t
w=
∫
1
2 ∂f mv
dv
2
∂t coll
m(v 2d + u2 )
2
となる. そしてこれ以上のモーメントは不要となる.
4. 世界を律する力
BTE およびそのモーメントから求まる保存式は, キャリア分布の平衡状態を考えると原理的に求まる式であっ
た. しかし以上の式は外力 F ext と記述してきたものに言及していない. 我々が今手にしている半導体ゲートは数
十 nm から数百 µm のサイズである. このスケールではキャリアとなる電子・正孔に働く力は電磁気力がほとん
どである.
4.1. 静かなる電場
電磁気力は Maxwell 方程式によって記述される. 特に電荷 q を持ったキャリアに働く静電力 E = −∇ϕ につい
て解けば,
ε∇ · ∇ϕ = ρ
としてキャリアに働く力の関係式を定めることが出来る.
4.2. 静電場における粒子
ここで改めて外力について考えると,
F ext = −qE = q∇ϕ
である. また内部に生じる力はキャリアの衝突によるものであった. そこで Boltzmann 統計に従い衝突の頻度を
求める必要があるが, これに関しては別の項目で検討するとし, さしあたり 1 粒子がドリフト速度 v d で運動する
時間を τ で与える. この時間はエネルギーに依存する関数である.
45
1 次モーメントにより与えられた運動量の保存式は以上の設定により, 電子の流束ベクトル J に関する式とし
て書き直せる.
J = −nv d = µnE + D∇n +
kB µn
∇T
q
qτ
m
kB T
D=
µ
q
µ=
5. 小休止
以上で健全なる肉体を識別する究極の秤が得られた. 特に熱輸送が微小である場合には 1 次モーメントまでを
制約条件と課し,
−∇ · (ε∇ϕ)
1
∂n
∂t − q ∇ · Jn
∂p + 1 ∇ · J
∂t
q
p
= q(−n + p − NA + ND )
=G−R
=R−G
を解くことで半導体中のキャリアを力学的運動として捉えることが出来る. それを計算機中のトランジスタの配
置の元に解くことで, 計算する肉体の躍動が観察される.
しかし実際の計算に進む前に, ドリフト時間 τ やキャリアの内部衝突に伴なう生成・消滅現象の詳細を決めな
くてはならない.
to be continued..
47
時間を制するものがゲームを制す Game Seeker
Vol. 3
mascalade
最近 PSP など携帯ゲーム機で遊んでいるとき, 画面が急に暗くなってびっくりしたことはないだろうか?
PSP の場合は省電力設定が働いていて,5 分間操作がないと自動的にバックライトがオフになるようにデフォル
トで設定されているからだ.
しかし不思議じゃないですか?ゲームで遊んでいるはずなのに 5 分も操作しない時間があるなんて. それだけ
の時間操作しないゲームはゲームの設計として正しいのだろうか?そもそも, そんなゲームは本当に楽しいんだろ
うか?
最初に言葉の定義をしておこう.
「ゲームをプレイ中, ユーザが何も操作していない時間」のことを「無操作時間」ということとする.
ただしここで言う「何も操作していない」というのは, ゲームの進行のためにユーザの操作が制限されていて何
もできない状態のことを言い, 例えばタイミングをはかるためにプレイヤーが意図的に何もしないで画面をじっと
見つめているのは対象外とする.
また問題であることは間違いないのだが, 最近の RPG で多い「ムービーシーンを見る」という行為も問題の方
向性が異なるため, 今回の「何もしていない時間」の対象から外すこととする.
まずは「なぜ無操作が起こるのか?」について考えてみよう.
結論から言えば, 多くのテレビゲームは複数人のプレイヤーとの間, もしくはプレイヤーとコンピュータとの間
でインタラクションが行われるため, 自分以外の誰かが考え, 行動する時間, つまりプレイヤーが操作できない時間
が発生するのは当然のことである (図 4 参照).
ならば昔からインタラクションによる無操作時間に悩まされていたはずだが, 実際に無操作時間を意識するよう
になったのはここ数年ぐらいからだろう.
なぜ急に無操作時間のことを意識するようになったか?個人的に一番顕著な例として, ファイナルファンタジー
やドラゴンクエストといったベーシック RPG の戦闘シーンの遷移から考えてみよう.
最初にファミコンソフトの時代から見てみよう.
FF1 や DQ1 の戦闘シーンは効果音と共に画面が光ったり揺れたりすることで攻撃を表現するという軽い演出
のみであった. また敵の数も比較的少なく, ファミコン後期にスライム 8 匹やマドハンドが大量に出てくることは
あったが, やはり軽い演出のおかげでテンポの速い戦闘が行われていた.
次はスーパーファミコンの時代を見てみよう.
FF4 や DQ5 の戦闘シーンになると属性にあわせたグラフィックが効果音と共に現れ, どんな攻撃が行われたの
かイメージしやすくなった分,1 回の攻撃にかかる時間が長くなった.
その結果, 大量の雑魚敵が出現するシーンでは一匹ごとにこの演出が行われ, 敵のターンが終わるまで「待つ」
という状態が出てきた.
さらに SFC 後期になると, 強力な攻撃ほど派手なエフェクトになり, ゲーム後半になるほど 1 回の攻撃にかかる
演出時間が長くなっていく傾向が現れ始めた.
そして PlayStation（以下,PS）の時代になると, この演出がさらに進化することになる. FF7 や DQ7 の戦闘で
は, 味方キャラはもちろん敵キャラも個性豊かに動くようになり, 強力な攻撃はエフェクトにとどまらず, ちょっと
したムービーシーンで表現されるようになり, 何をするにも演出待ちが当たり前になっていった.
48
図 4: インタラクションと無操作時間
象徴的なのは, これまでの RPG の戦闘ではキャラが敵を攻撃しても遠くで武器を振ってるだけだったのが, こ
のころからキャラが敵のところまで移動して武器を当てるようになったことだろう.
従来のようにキャラが自分の立ち位置から剣を振ると, なぜか相手に斬撃のあとが表示されてダメージを与える
よりも, 剣を持ったキャラが相手のそばに移動し, 剣を敵に当てることでダメージを与える方が正しく, 分かりや
すい表現なのは間違いないが, 当然キャラの移動や剣を振るアクションのために攻撃の演出時間はさらに長くなっ
てしまった.
1 キャラの攻撃演出が長くなったと言うことは,1 ターンが終わるまでの時間もそれにあわせて長くなったと言
うことだ. 例えば 1 キャラ平均 20 秒の演出があり, それが敵 8 体分行われたとすると 20 秒 ×8 体＝ 160 秒, つま
り敵のターンだけで 2 分 40 秒も消費されることになる.
さらに後半の敵には強力な攻撃のエフェクトという追加演出時間があることを考えたら, このユーザの待ち時間
の長さが分かるだろう.
これ以降は PSP,PS2,PS3 と新しいハードが出てきたが, よりキレイなグラフィック, より派手なアクション演出
を行うことに重点が置かれ, ベーシック RPG に新しい戦闘の表現スタイルが加わることはなかった.
この遷移 (図 5 参照) を見て分かる通り, ベーシック RPG で操作せずに「待つこと」を意識するようになった
のは,SFC のころからだが, ハード性能の関係で凝ったことがしづらく気になるほどではなかった. やはりハード性
能の飛躍的向上によって戦闘がよりリアルに, 派手な演出をすることができるようになった PS の時代から「無操
作時間」を意識するようになったのだと考えられる.
次に無操作時間の必要性と面白さの関係について考えてみよう.
無操作時間があることでプレイヤーが暇になるのならば, 常にユーザが何らかの操作するようなゲームデザイン
にした方がいいのではないか? そもそもゲームを遊んでいるのはプレイヤーなんだから, システムが主導権を握っ
てゲームを進行するのは間違っているのではないか? そう考えるかもしれないが, 結論から言えば“ No ”だ
先ほど述べたとおり, 無操作時間を意識するようになったのが PS 時代だとすると, その後, 現在までの 15 年間
も無操作時間が生き残っていることになる. 無操作時間自体が問題なのだとすれば, この 15 年間でゲームクリエイ
ターは必死になって無操作時間を無くすことに力を注ぎ, 今のゲームで無操作時間を見かけることはなくなってい
るはずだ.
それではなぜ無操作時間がなくならなかったのか?イメージがしやすい例として, オンライン RPG を例に考え
てみよう.
ベーシック RPG の流れが強いオンライン RPG といえば FF11 や 14 だろう.
49
図 5: 世代ごとの戦闘の演出と時間の遷移
このうち無操作時間の必要性を強く感じるのは FF14(発売当初のユーザインタフェース) の方だ.
FF14 の戦闘は登録されたアクションゲージが溜まったら, 実行したいアクションボタンを押すことで攻撃や魔
法が発動するタイプのインタフェースを実装している.
これだけならば特に問題はないかもしれないのだが, 実際にはこれに敵の部位損傷をおこすための位置取りやオ
ンラインゲームなので他プレイヤーとのチャットコミュニケーションが加わるため, 特に戦闘中はユーザになんら
かの操作を常に求められ, 非常に忙しいシステムとなっている (図 6 参照).
結果, 位置取りに夢中になって攻撃ボタンを押し忘れたり, コミュニケーションを取らずにモクモクと戦闘して
オンラインの醍醐味が希薄になったり, 逆に会話をしようとキーボードを叩いている間に絶好のタイミングを逃し
てしまい, うまく立ち回れなかったりと, 様々な部分で中途半端なプレイをしてしまう状況が起こった.
つまり, ユーザに無操作時間を与えないで, 常に何らかの操作ができるようにすると, あまりにも忙しすぎてミス
を誘発し, その結果ゲームをすることに大きなストレスを感じたり, うまく操作することだけに注力して楽しむこ
とを忘れたりと良い結果にはならないのだ.
発売から約 1 年が経ち,FF14 の通常攻撃がオートアタックに変わったことを考えると, 無操作時間を完全になく
すことが必ずしもゲームを楽しむために必要なものではないことを示していると言ってもいいだろう.
このようにベーシック RPG において, 敵の攻撃が終わるまでただ待つという行為に繰り返し遭遇することはプ
レイヤーのやる気を削ぎ, 逆に常にプレイヤーになんらかの操作を求め続けることはプレイヤーを疲れさせてしま
い, どちらであってもプレイヤーからゲームを楽しむ心が奪い, 最悪ゲームを続ける気持ちすらなくしてしまいか
ねない.
つまり, プレイヤーにゲームを楽しみ, 面白いと感じてもらうためには, プレイヤーに無操作時間があると感じさ
せないようにしながら, しっかり操作をしない休憩時間を与えるという非常に難しい時間のバランス配分が要求さ
れるのだ.
ここまで見てきたように, ベーシック RPG において無操作時間は生かさず殺さずの難しい舵取りが必要となる
のだが, 話をすごく簡単化してしまうと, プレイヤーにとってほどよい無操作時間の長さを調べ, その範囲内で演出
したゲームを作ればプレイヤーにとってフレンドリーな作品になるということではないだろうか?
いや, そんな無操作時間の長さだけを気にしながら演出を考えたゲームを作っていては, どのゲームも代わり映
えせず,「これってあのゲームと似てるね」と言われてしまい, 遊んでみようという気が緩やかに失われていきそ
うだ.
そのため現代のゲームクリエイターは知恵を絞り,RPG というジャンルでありながら演出重視のベーシックな
戦闘スタイルから脱却し, 新しいスタイルの提案が行われている.
50
図 6: ユーザが戦闘中にすること
もちろん人によって成功している, 失敗していると評価が分かれる部分もあるだろうが, ここにいくつか例を挙
げたいと思う.
１）いつでも動き出せるアクティブターンバトル
ベーシック RPG の王道を歩き続けた FinalFantasy シリーズが提案してきたのは「待ち時間の逆転の発想」だ.
従来のベーシック RPG はコマンドを入力すると, ある一定の時間が経過する（処理が行われる）までプレイ
ヤーは待ち状態となるのだが,FF13 ではコマンドを入力するとすぐに次のコマンドが入力できる状態になるため,
プレイヤーの待ち状態である時間が大幅に減っている.
これだけならば常にコマンド入力をすることになりプレイヤーが疲れてしまうが,FF13 ではコマンド入力を待
つ (ATB ゲージがたまるのを待つ) ことで複数回連続攻撃ができるというボーナスをつけることで, ユーザが意図
的に待ち状態になる (タイミングを図る) 理由を与え, 待たされている感がなく, 適度な休みがあるため疲れること
もないという工夫がなされている. このようにコマンドを入力できるタイミングをゲージが“ たまった後 ”から
“ たまる前 ”にすることで, 実際にはコマンドが実行されるまでは以前と同等の待ち時間があったとしても, それ
を無操作時間と感じさせないようにできている.
ただこのバトルシステムでは 1 キャラしか操作することができず, たくさんの仲間にうまく指示を出して敵を効
率的に倒すといった, ベーシック RPG の醍醐味の一つが失われているのも確かであり, この点については賛否が
分かれそうだ.
しかし, 従来のベーシック RPG の使い古されたバトルシステムから脱却し, 新しいスタイルで戦闘を楽しませ
てくれたことは間違いない.
２）待ち時間を有効活用
同じスクウェア作品だがパラサイト・イヴでも「待ち時間にキャラを移動して有利な位置取りをする」という
新しい試みがなされている.
そもそもベーシック RPG の無操作時間というのは, コマンドを入力してから次に自分のターンがやってくるま
で, その操作の結果をみているしかないため起こっている. ならば, コマンドを入力したあとの待ち時間の間, タク
ティクス系のゲームのようにキャラを自由に動かし, 敵から攻撃を受けない位置や敵の背後など大ダメージを与え
られる位置に移動するという攻撃以外の別の目的をプレイヤーに与えることで常にユーザは何かを操作し, 待たさ
れている感がなくなっている. このようにコマンド入力時は“ 攻撃 ”,ATB ゲージがたまるまでの待ち時間は“ 防
御 ”と明確な役割を持たせることでメリハリがつくようになっている.
ただし, このバトルシステムは無操作時間の削減により力が入っているため, あまりにもスムーズでスピード感
のある内容にすると, 先に挙げたように常に操作し続けてプレイヤーの落ち着く時間がなくなってしまう危険性が
51
図 7: 無操作時間対策と共通点
高い. 当時は PS で比較的ゆっくりな時間経過だったため気にならなかったが, 今の時代のゲームで同じシステム
を使おうとする場合, 自分のターンが回ってきてコマンドを選択しているときは時間が止まったり, 敵が攻撃して
きそうになるとスローになってプレイヤーが判断と操作がしやすいように忙しさを緩和する対策が必要となるだ
ろう.
結果的にはやや後手に回ったシステムではあるが, 待ち時間を有効活用して別の目的のためにプレイヤーに操作
を促すという考えは良いと思う.
３）コマンドバトルではなくキャラを直接操作
１）と２）は新しい取り組みをしているが, ベーシック RPG でおなじみのターン制バトルであることには変わ
りない. そもそもこのターン制バトルが待ち時間, つまり無操作時間ができる原因と言っても過言ではないため,
ターン制バトルからの脱却が無操作時間問題の解決になるとも言える. このターン制バトルからの脱却を行ったの
がテイルズ オブ シリーズの“ リニアモーションバトルシステム ”だ. テイルズの戦闘は従来のコマンドを入力す
ればキャラが自動で動いて攻撃するのではなく, まるでアクションゲームのようにキャラを自由に移動させ, 攻撃,
防御, 魔法の詠唱を矢印キーとボタンの組み合わせでプレイヤーの好きなタイミングで行えるようになっている.
もちろん RPG で遊ぶ人がみんなアクションゲームも得意というわけではないので, 矢印キーとボタンを押せば自
動で敵を攻撃しに行くセミオート操作もある.
このようにそもそも待ち時間がなく, 常にキャラを動かせるので無操作時間のように待たされている時間は非常
に少なく, またセミオート操作のように簡単な入力操作をすると, あとは勝手にキャラが動くのを眺めていれば快
適なバトルができるという, 待ち時間対策も疲労抑制もできるバトルシステムとなっている.
ただし, アクションバトルの場合, キャラが敵からの連続攻撃で硬直し, 長い時間操作を受け付けない状態となる
場合があり, これが起こるとプレイヤーは非常に大きなストレスを受けてしまうため, こういったハメ攻撃が起こ
らない攻撃の設計や, 万が一ハメ状態になった場合でも回避できる手段をプレイヤーに用意するといった RPG ら
しくない部分での調整に気をつかわなければならない.
このように従来のベーシック RPG のバトルスタイルから脱却し, 新しいスタイルへの挑戦が続けられ, さらに
一度提案されたスタイルもプレイヤーからの意見などを参考にさらに進化し続けている. 特にテイルズシリーズに
ついては新作が出るたびに少しずつ改良が加えられ,1 作目のファンタジアと新作のエクシリアではもはや別物と
思うほど変化している. このまま RPG のバトルスタイルが進化していけばどんな形になっていくのだろうか?
今回挙げた 3 つの新しいバトルスタイルをよく見ると“ プレイヤーはキャラクター 1 人だけを操作する ”とい
う共通点があることに気づく (図 7 参照).
FF13 はゲージが貯まるタイミングを図るため一人のキャラに集中する必要があり, パラサイト・イヴはリアル
タイムに動く中で攻撃・防御を交互に行うため他のキャラに順番を回すことが難しく, テイルズもやはりアクショ
ン操作を行うため, 同時に複数のキャラを操作することはできない. このように無操作時間を伴う従来のベーシッ
クスタイルから離れようとすると一度に操作できるキャラが一人に限定される傾向にあるようだ.
しかしせっかく RPG で遊ぶならメインキャラだけでなく他の味方キャラも直接指示 (操作) したくないだろう
か?攻撃がうまく繋がり強敵を倒せたときや, 味方に指示していた回復が絶好のタイミングでできたときの爽快感
52
図 8: 連携攻撃の遷移
は, きっと 1 キャラだけを操作していては味わえないはずだ.
そこで今回, 私から“ 味方キャラを操作しつつ, 無操作時間対策を行った ”現代バトルシステムのアレンジを行っ
たものを提案してみる.
『キャラクターに対応したボタンを押したタイミングで結果が変わるオート戦闘』
戦闘の流れは FF13 の ATB ゲージのように, ゲージが貯まらないうちにコマンドを入力すると単発攻撃を, ゲー
ジが多く貯まればそれだけ複数回攻撃できるものとする.FF13 ではキャラの行動をマニュアルでコマンド入力が
できる部分を残しており, バトルスピードの速さに対応できるように操作キャラを 1 キャラに限定しているが, 実
際のところオートでコマンドを選択するのが主流と思われる. つまり, プレイヤーは自分が出した攻撃方針に沿っ
て妥当な行動が行われるならば, 特に異論はないということだ. ならば, どんな攻撃を行うのかはシステムがオート
で選択し, プレイヤーは攻撃に参加するキャラを選ぶことに集中すれば複数キャラでこれまでと同じような戦闘が
できるのではないだろうか?
例えば, ゲージがたまって複数攻撃ができる状態のとき,FF13 のように一人のキャラが連続して行動するだけで
なく, 味方キャラを順番に選択すると複数のキャラが連携して攻撃が行われればきっと楽しいはずだ.
そこで, たまった ATB ゲージ（行動回数）の数だけコントローラのボタンを押すことで対応したキャラクター
が攻撃を開始し, 同じボタンを押せば一人のキャラが単独で連続攻撃を, 違うボタンを押せば異なるキャラ同士で
連携攻撃ができるようにする. またボタンを押したときの敵の状態, 攻撃している味方キャラの特性によって様々
な技が発生するようにすることで, ユーザにタイミング良くボタンを押す楽しみが生まれるのではないかと考え
る. 例えば剣を使うキャラが最初に攻撃をしかけると, 敵がニュートラルな状態で浮くタイプの敵なので「切り上
げ」で敵を浮かし, 次に銃を使うキャラが浮いている状態の敵を攻撃すると「狙い撃ち」の技が出て大ダメージ
(気絶) を与え, 最後に魔法を使うキャラが宙に浮き気絶している敵を攻撃すると「重力魔法」で地面にたたき落と
す, という攻撃を敵の状態にあわせてボタンをタイミングよく押すことで行うことができるようにする. ちなみに
最初の攻撃は敵の特性で発生する技が変化し, 例えば浮き上がらない敵を攻撃する場合は「切り払い」のように敵
の体制を崩す技が発生し, その後に続くキャラの技も敵の状態に合わせて変化するようにすれば連携のバリエー
ションを増やすこともできるだろう (図 8 参照).
さらにストーリーに絡めて特定の味方キャラでは特殊な連係動作が発生したり, 敵の状態を特定の順番で変化さ
せると必殺技のような連携技が出せるようにすれば, ボタンの押し方はいつもと変わらないのに様々な演出の攻撃
が行われるので, 攻撃のマンネリ化が抑えられ, プレイヤーのモチベーションも維持できると考えられる.
このシステムでは複数のキャラで連携攻撃を行うために ATB ゲージが貯まるのを意図的に待つ, また待ちたく
なければ単発攻撃をすぐにできるようにするということで無操作時間のような待たされている時間が解消でき,
しかも様々な連係動作による大ダメージの演出を行うことで, ゲージがたまるのを待つ魅力を作ることで, スピー
ディーなバトル展開であっても忙しすぎて作業化してしまったり, 疲れてゲームをすぐにやめてしまうようなこと
を回避することができると考える.
もちろんこれはあくまで基本システムなので, 例えば順番に攻撃するだけではなく, 同時にボタンを押して攻撃
53
することでクロノトリガーの X 斬りのような技が発生するようにすればさらにバリエーションが増え,FF13 のオ
プティマようにオートで選択されるコマンドの方針が簡単に変更できるようにすれば幅が広がり楽しくなると考
えられる.
以上のようにゲーム作りにおいて無操作時間をどう扱っていくかを考えることは, プレイヤーに面白いと思って
もらい, 長く遊んでもらえる作品に仕上げるためには非常に重要なものだ.
今回は RPG をメインに話をしてきたが, 無操作時間はインタラクションがあれば (戦う相手がいれば) どんな
ジャンルのゲームでも存在する.
例えばスーパーロボット大戦のような戦略シミュレーションゲームは明確にプレイヤーと敵のターンが存在し,
交互にユニットを操作するため, 必ず敵のターン時に待ち時間が発生する. さらに戦略シミュレーションゲームは
物語が進むにつれてお互い操作するユニット数が増加し, ボスユニットは非常に派手な演出の攻撃が行われるよう
になるため, どんどん敵のターンが, つまり待ち時間も長くなってしまう傾向がある.
初期のスーパーロボット大戦もこの傾向にあったが,
1. 移動, 攻撃モーションの早送り
2. 攻撃モーションそのものをカットするか選択可能に
3. 敵からの攻撃に対してプレイヤーが都度対処方法を選択可能に
これらを導入することで, ユーザが操作できない時間を減らしたり, 敵のターンであってもユーザに何らかの操
作を求めることで無操作時間の削減を, それでも残るわずかな無操作時間でプレイヤーに休息を与え, プレイヤー
は遊ぶモチベーションを維持している.（それでもまだ待たされている感は残っているが）
ちなみにここまでプレイヤーと敵といった分かりやすいインタラクションがあるゲームについて述べたが, ア
ドベンチャーゲームにも無操作時間が存在する. アドベンチャーゲームでは初見の文章は読み,2 周目以降の既読
文章は次の選択肢 (未読文章) までスキップするという遊び方が主流だと思うが, 次の選択肢までのテキスト量が
多ければいくらスキップしていてもプレイヤーが操作できない時間が長くなっていた. そのため, 最近のアドベン
チャーゲームでは物語を最初から始めるのではなく, シーンセレクト, チャプター, クイックセーブ機能など様々な
名前があるが, 要するに物語が大きく動く分岐点の手前から始めることができるようにすることで無操作時間の短
縮ができるようになっている.
ただ, このように様々なジャンルに無操作時間があるのだが, 各ジャンルによって原因と対策が異なるため, 共通
の対策といった無操作時間の解消の近道はなさそうだ. よって無操作時間の設計こそゲームクリエイターの腕の見
せ所なのかもしれない. まとめるとプレイヤーと相手 (人間や CPU) とのインタラクションがあるゲームには,
必ず無操作時間が存在する.
インタラクションがある以上, プレイヤーが操作できない時間があるのは当然なので, ゲームクリエイターはい
かにこの無操作時間を活用するかがゲームの面白さ, プレイを続けるモチベーションの維持のために重要である.
ゲーム機の急激な進化により, これまでは待ち時間を美麗グラフィックで魅せて楽しませようという道もあったか
もしれないが, もうグラフィックに目が慣れた多くのプレイヤーには通用しなくなってくるだろう. そんな今だか
らこそ, 王道のシステムをリスペクトしつつも, 従来とは考え方を逆にしてみたり, 他のゲーム要素と融合してみた
りすることで現代のユーザにマッチした新しいスタイルのゲームが生まれてきてほしいものだ.