第一級の継続とローカル名前環境の変更は相性悪い

Ruby Scheme

限定継続であれ、無限定の継続であれ、第一級の継続と、ローカル名前環境の変更は相性が悪い、ということに気づきました。お酒を飲んだのでたぶん思考がゆるいですが、だらだら書きます。

名前環境の変更

たとえば次のRubyプログラムは、「x = 1」によってローカル名前環境に新しい変数xが、 *1「y = 2」によってyが追加されるので、この時点でローカル名前環境が変更されている、ということにします。

def foo
  # local-env = {}
  x = 1  # local-env = {x: 1}
  y = 2  # local-env = {x: 1, y: 2}
  return x + y
end

Scheme/Racketプログラムでは、普通はローカル名前環境は変更されません。下記プログラムでは、変数yに2が代入された時点で、名前環境が変更されるのではなく、新しい名前環境が導入されます。

(define (foo)
  (let [(x 1)]
    (let [(y 2)]
      (+ x y))))

; あるいは
(define (foo)
  (let* [(x 1) (y 2)] (+ x y)))

次のようにset!を使えば、それぞれ呼び出した時点で名前環境が変更されます。

(define (foo)
  (let* [(x #f) (y #f)]
    (set! x 1)
    (set! y 2)
    (+ x y)))

継続と名前環境の変更

Rubyでのshift/resetを次のように定義します *2。

require 'continuation'

def shift(&block)
  callcc {|shift_cont|
    lambda {|v| $cont[v] }[
      block[lambda {|v|
        reset {
          shift_cont[v]
        }
      }]
    ]
  }
end

def reset(&block)
  orig_cont = $cont
  callcc {|reset_cont|
    $cont = lambda {|v|
      $cont = orig_cont
      reset_cont[v]
    }
    lambda {|v| $cont[v] }[block[]]
  }
end

3引数を取ってリストを作って返す関数を、カリー化したようなメソッドを、shift/resetで作ってみます。これは問題ないバージョン。

def triple(first)
  reset {
    [first,
     shift {|k1| k1 },
     shift {|k2| k2 }]
  }
end

foo = triple(:foo)
foo_bar = foo[:bar]

# (1)
p foo_bar[:baz]  # => [:foo, :bar, :baz]

# (2)
p foo[:X][:Y]    # => [:foo, :X, :Y]

# (3)
p foo_bar[:baz]  # => [:foo, :bar, :baz]

次は同じ関数の、しかし危険なバージョン。(2)でfoo[:X]を呼び出した瞬間に、呼び出された限定継続はtriple_unsafeのローカル名前環境をfoo_barと共有しているので、secondへの:Xの代入が、foo_barにも影響を与えてしまいます。したがって、(1)と(3)は同じ形の呼び出しであるにもかかわらず、(3)の結果のリストの二番目の要素は:Xに変わってしまっています。

def triple_unsafe(first)
  reset {
    second = shift {|k1| k1 }
    third = shift {|k2| k2 }
    [first, second, third]
  }
end

foo = triple_unsafe(:foo)
foo_bar = foo[:bar]

# (1)
p foo_bar[:baz]  # => [:foo, :bar, :baz]

# (2)
p foo[:X][:Y]    # => [:foo, :X, :Y]

# (3)
p foo_bar[:baz]  # => [:foo, :X, :baz]  !!!

結論

同じ名前環境で同じ箇所のコードが複数回実行されて、その名前空間が変更されると、たとえば一見して関数的な限定継続が副作用を持ってしまうので、痛い。

lambda {|second| ...}[shift{|k1| k1 }]のように、letをエミュレートする手もあるけど、普通のRubyコードではなくなってしまいます。

2017-03-30 追記

Shiro Kawaiさんから次のコメントをいただきました。ShiroさんはScheme処理系Gaucheの開発者です。

*1:2017-03-30 追記。

*2:2017-03-30 定義がぶっ壊れていたので直しました。