lib/lazy.rb

   1 # = lazy.rb -- Lazy evaluation in Ruby
   2 #
   3 # Author:: MenTaLguY
   4 #
   5 # Copyright 2005-2006  MenTaLguY <mental@rydia.net>
   6 #
   7 # You may redistribute it and/or modify it under the same terms as Ruby.
   8 #
   9
  10 module Lazy
  11
  12 # Raised when a demanded computation diverges (e.g. if it tries to directly
  13 # use its own result)
  14 #
  15 class DivergenceError < Exception
  16   def initialize( message="Computation diverges" )
  17     super( message )
  18   end
  19 end
  20
  21 # Wraps an exception raised by a lazy computation.
  22 #
  23 # The reason we wrap such exceptions in LazyException is that they need to
  24 # be distinguishable from similar exceptions which might normally be raised
  25 # by whatever strict code we happen to be in at the time.
  26 #
  27 class LazyException < DivergenceError
  28   # the original exception
  29   attr_reader :reason
  30
  31   def initialize( reason )
  32     @reason = reason
  33     super( "Exception in lazy computation: #{ reason } (#{ reason.class })" )
  34     set_backtrace( reason.backtrace.dup ) if reason
  35   end
  36 end
  37
  38 # A handle for a promised computation.  They are transparent, so that in
  39 # most cases, a promise can be used as a proxy for the computation's result
  40 # object.  The one exception is truth testing -- a promise will always look
  41 # true to Ruby, even if the actual result object is nil or false.
  42 #
  43 # If you want to test the result for truth, get the unwrapped result object
  44 # via Kernel.demand.
  45 #
  46 class Promise
  47   alias __class__ class #:nodoc:
  48   instance_methods.each { |m| undef_method m unless m =~ /^__/ }
  49
  50   def initialize( &computation ) #:nodoc:
  51     @computation = computation
  52   end
  53   def __synchronize__ #:nodoc:
  54     yield
  55   end
  56
  57   # create this once here, rather than creating a proc object for
  58   # every evaluation
  59   DIVERGES = lambda { raise DivergenceError.new } #:nodoc:
  60   def DIVERGES.inspect #:nodoc:
  61     "DIVERGES"
  62   end
  63
  64   def __result__ #:nodoc:
  65     __synchronize__ do
  66       if @computation
  67         raise LazyException.new( @exception ) if @exception
  68
  69         computation = @computation
  70         @computation = DIVERGES # trap divergence due to over-eager recursion
  71
  72         begin
  73           @result = demand( computation.call( self ) )
  74           @computation = nil
  75         rescue DivergenceError
  76           raise
  77         rescue Exception => exception
  78           # handle exceptions
  79           @exception = exception
  80           raise LazyException.new( @exception )
  81         end
  82       end
  83
  84       @result
  85     end
  86   end
  87
  88   def __bind__(object)
  89     self.class.new(@computation.bind(object))
  90   end
  91
  92   def inspect #:nodoc:
  93     __synchronize__ do
  94       if @computation
  95         "#<#{ __class__ } computation=#{ @computation.inspect }>"
  96       else
  97         @result.inspect
  98       end
  99     end
 100   end
 101
 102   def respond_to?( message ) #:nodoc:
 103     message = message.to_sym
 104     message == :__result__ or
 105     message == :inspect or
 106     __result__.respond_to? message
 107   end
 108
 109   def method_missing( *args, &block ) #:nodoc:
 110     __result__.__send__( *args, &block )
 111   end
 112 end
 113
 114 end
 115
 116 module Kernel
 117
 118 # The promise() function is used together with demand() to implement
 119 # lazy evaluation.  It returns a promise to evaluate the provided
 120 # block at a future time.  Evaluation can be demanded and the block's
 121 # result obtained via the demand() function.
 122 #
 123 # Implicit evaluation is also supported: the first message sent to it will
 124 # demand evaluation, after which that message and any subsequent messages
 125 # will be forwarded to the result object.
 126 #
 127 # As an aid to circular programming, the block will be passed a promise
 128 # for its own result when it is evaluated.  Be careful not to force
 129 # that promise during the computation, lest the computation diverge.
 130 #
 131 def promise( &computation ) #:yields: result
 132   Lazy::Promise.new &computation
 133 end
 134
 135 # Forces the result of a promise to be computed (if necessary) and returns
 136 # the bare result object.  Once evaluated, the result of the promise will
 137 # be cached.  Nested promises will be evaluated together, until the first
 138 # non-promise result.
 139 #
 140 # If called on a value that is not a promise, it will simply return it.
 141 #
 142 def demand( promise )
 143   if promise.respond_to? :__result__
 144     promise.__result__
 145   else # not really a promise
 146     promise
 147   end
 148 end
 149
 150 end