Journal InTime

_ Rubyで遅延評価 - delay, force, lazy

正格評価の言語で明示的に遅延評価を行う方法として、Schemeのdelay/forceがある。 Rubyで実装するとこんな感じ。

class Promise
  NULL = Object.new

  def initialize(&block)
    @value = NULL
    @block = block
  end

  def self.delay(&block)
    new(&block)
  end

  def force
    if @value == NULL
      @value = @block.call
    else
      @value
    end
  end
end

count = 0
x = Promise.delay { count += 1; 1 + 2 }
p x.force #=> 3
p x.force #=> 3
p count #=> 1

メモ化してくれるので、delayされた式は何回forceしても一度しか実行されないのがポイント。

しかし、この実装には問題があって、末尾呼び出しの最適化を有効にしても以下のコードがstack overflowになってしまう。

def loop
  Promise.delay { loop.force }
end
loop.force

この例だとエラーになっても害がないと思われるかもしれないが、遅延評価の言語で末尾再帰になるような関数をdelay/forceで書こうとすると、上記のようにPromise.delay { (...).force }という形が出て来るのでちと困る。

そこで、SchemeのSRFI-45でlazyという機能が導入されており、(delay (force ...))の代りに(lazy ...)とすることで解決できる。

Rubyでの実装は以下。

class Promise
  Box = Struct.new(:type, :value)

  def initialize(type, value)
    @box = Box.new(type, value)
  end

  private_class_method :new

  def self.lazy(&block)
    new(:lazy, block)
  end

  def self.eager(value)
    new(:eager, value)
  end

  def self.delay
    lazy {
      eager(yield)
    }
  end

  def force
    content = box
    case content.type
    when :eager
      content.value
    when :lazy
      promise = content.value.call
      content = box
      if content.type != :eager
        content.type = promise.box.type
        content.value = promise.box.value
        promise.box = content
      end
      force
    else
      raise ScriptError, "should not reach here"
    end
  end

  protected

  attr_accessor :box
end

$c = 0
def loop
  $c += 1
  Promise.lazy { loop }
end
at_exit { p $c }
loop.force

末尾呼び出しの最適化を有効にして実行すると、ちゃんと無限ループになる。 Ctrl+Cで止めると以下のように実行回数が表示される。

$  ruby-trunk -e 'RubyVM::InstructionSequence.compile_option = \
  {:tailcall_optimization => true, :trace_instruction => false}' \
  -e 'load(ARGV[0])' t.rb
^C133411
t.rb:34:in `force': Interrupt
	from -e:3:in `load'
	from -e:3:in `<main>'