継続による時間操作まとめ

研究開発 草稿 scheme 妄想

前回までのフィラデルフィア・エミュレータ作りで考えた事の要約。
まだ考え途中。


以下の文章で使っている「call/cc」は、よくあるgotoやreturnの用途で使うcall/ccではなく、

(call/cc
  (lambda (cont)
    ...
    ...
    ...))
xxx
xxx
xxx

の、「...」の外側(「xxx」以降)にcontを持ち出した時の事に限定している。
紛らわしいので、あとで清書する時に直す事(もし、そんな時があるなら)。

  • (手続き型言語での)プログラムの実行は、評価順(大抵の場合は、ソースコードの上から下への順)を時間軸と見做す事が出来る。
    • この事は手続き型言語では空気のように当たり前の事なので見落されがち。しかし、非・手続き型言語をいじってみる事で、以下の事が実感できた。
      • この性質によって、手続き型言語が(そうでない言語よりも)普通の人に分かりやすくなっている大きな要因となっている(と共に、大きな足枷にもなっている)。
  • call/ccは、この時間の流れを跳躍できる、タイムマシンのような役目を果たす(この時、タイムマシン搭乗者はプログラムを実行しているcpuになる)。但し、フィクションに出てくるタイムマシンとは違い、以下のような制約がある。
    • 設置型タイムマシンである。つまり、特定のポイントに設置し(以下、タイムポイントと呼ぶ)、そのタイムポイントと対になる装置(cont)を持ち歩き、好きな時にそれを発動すれば、設置した箇所/時刻に戻る事が出来るというもの。
      • よって、「まだ見ぬ未来」へと、いきなり時間移動する事は出来ない。が、例えば、今ここでタイムポイントを設置し、それとは別に以前に設置しておいたタイムポイントを使って過去に戻り、さっき設置したタイムポイントを使って「元々居た未来」に戻る事は可能(但し、実装上の制約で、それが出来ないschemeバリアントもある)。
  • この時間跳躍の際には、「破壊的更新」を起こすものについては勝手に一緒についてくるが、単なる変数束縛で示されているものについてはその場に留まる。
    • 具体的には、グローバル変数は時間跳躍してもロールバックされない。letで確保し、破壊的更新を起こさずに利用している変数は時間跳躍と共にロールバック(未来への移動の場合はロールフォワード？)される。
      • つまり、cpuと一緒に、グローバル変数や破壊的更新を行った変数が勝手にタイムマシン内に乗り込んでしまうようなイメージ(勿論、実際の実装としては、世界の方がロールバックされているだけだが)。
    • この性質の為、call/ccを使う状況では、「破壊的更新」(そして副作用)を起こさないように世界を構築する必要がある。超重要。
  • しかし、タイムマシンを使いたいという状況は、「まだ見ぬ未来を見てきて、もし上手く行かなかったら、それはなかった事にして、やり直したい」またはそれに類する状況が多いと思われるので、完全に副作用無しに構築してしまうと、「せっかく過去に戻ったのにまた同じ行動をしてしまう」事になってしまう。これでは意味が無い。つまり、call/ccの周辺では、(広い意味での)副作用が起こる必要がある。
    • 具体的には、例えば、(call/cc ...)の返り値が一つに集束しなくなる(集束しないようにする)事になる。更に具体的に言うと、初回実行時と、contを使って戻ってきた時とで違う値を返すとか。で、一つの手続きが返す値が単一の値に集束しなくなるので、参照透過性が失われてしまう(=広い意味での副作用が起こる)。また、(call/cc ...)の返り値を使っていなくとも、グローバル変数や破壊的更新によって状況を変更しているなら、同様に参照透過性は失われている(筈、多分)。
    • つまり、タイムマシン(的用途に使われるcall/cc)は、副作用を持つ(または、持つ必要がある)。
  • ここまでで、以下の三つの重要項目が示された。
    1. グローバル変数や破壊的更新は、タイムトラベル時にタイムマシン内に一緒に持ち込まれる(つまり、タイムトラベル環境とでもいうものに保存されてしまう)。
    2. 「世界」は、「破壊的更新」無しに実装される必要がある(副作用は、目に見えない副作用であれば、あっても一応は大丈夫、な筈。例えば、世界外へのエラーログ出力とか)。
    3. 「タイムマシン」は、「副作用」無しには実装できない(事はないが、副作用無しだと役に立たない)。
  • 次に、タイムトラベラーが二人居た場合を考える。
    • 具体的には、将棋風ゲームでの特定盤面から始まるcpu vs cpu対戦で、お互いが最善手を尽くす為に、タイムマシンを使って最適手検索を行うような状況。
    • 互いに、未来の可能性に対して木検索を行い、自分が勝てる可能性がなくなるpathを削っていく事になる。
    • ここで、指し手Aが、自分の王を動かしたら、その未来ではどうやっても勝てなくなる事を発見したとする。そこで、タイムマシンを使って前の手に戻ったとする。
    • さて、前述の重要項目の3と1より、指し手Aがタイムマシンで前の手に戻る際に、相手の指し手Bも一緒にタイムマシンに乗り込んでしまう事になる。
    • これがどういう事になるかと言うと、要するに、相手の指し手Bのpath検索状況を狂わせてしまう。相手の指し手Bもタイムマシンによる最適手検索を行っているので、指し手Aが自身の王を動かした後、次に自分がどの駒をどう動かすかをタイムマシン検索し、「こう動かせばAに勝てないが、ああ動かせばAに勝てる」という内部状態を得た段階になっている筈。しかし、Aがタイムマシンで前の手に戻った為に、Bはその内部状態を持ったまま、一つ前の手に戻されてしまう事になる。
    • この内部状態を、「盤面の最初からの、互いの指し順全て」として持っているならば、一つ前の手に戻されても、まだそっちのpathは検索していない筈なので、また一つずつ検索していけばいいだけの話となる。しかし、「この局面」しか見ていないのであれば、Aが違う手を指し始めたにも関わらず「こっちのpathはもう検索して勝てないのが分かってる」と勘違いして、最適手を見逃してしまう可能性が出てきてしまう。
    • よって、call/ccを使って木の全検索を*交互に*行う場合は、検索方法の実装に気を付ける必要があるように思われる。


なんかよく分からなくなってきたので、今日はここまでにする。
最後の方がなんか怪しい。