From: Brian Marick <marick@...>
Date: 2001-08-24T07:03:02+09:00
Subject: [ruby-talk:20212] Lazy computation (was: breaking out of nested loops)

At 03:18 AM 8/23/01, you wrote:
>I'd still like to find a way to suspend an arbitrary computation, get a 
>"resumer" that can be passed around and called anywhere to return the next 
>value.

Here's one. This one has ruby-unit tests, so is more likely to work. It's 
pretty terse (except for the documentation) and seems clean. But consider 
this a submission to the Code Amelioration contest.
If anyone wants the tests, ask.

% cat lazy.rb
=begin

A LazyComputation is an object that wraps the state of an ongoing
computation. Each time the computation calls
LazyComputation#value=, it is suspended. That value is delivered
to a caller who requests it with LazyComputation#value, which
should only be called if LazyComputation#has_value is true.

Here is a simple example: a stream that generates all the
integers. (See example_integers below.)

   # Wrap an infinite loop:
   lazy = LazyComputation.new { | lazy |
     i = 0
     loop {
       lazy.value = i
       i += 1
     }
   }

   # Print the first few integers.
   for i in 0..10
     puts lazy.value
   end

That example didn't show the use of LazyComputation#has_value, so
here's one that does. It also shows that 'value' has a synonym,
push.  With it, recursive methods that use an array accumulator can be
made lazy without changing the code. (See example_tree below.)

This example flattens the list below into [1, 2, 3, 4, 5, 6, 7, 8].

   tree = [ [1, 2], [3, [4, [5, 6], 7], 8]]

   def atoms(tree, accumulator=[])
     if tree.is_a?(Array)
       tree.each { | e | atoms(e, accumulator) }
     else
       accumulator.push(tree)
     end
     accumulator
   end

   puts "Here is the eager version."
   puts atoms(tree).inspect

   # Now do it lazily
   lazy = LazyComputation.new { | lazy |
     atoms(tree, lazy)
   }

   result = []
   while lazy.has_value
     result.push(lazy.value)
   end
   puts "Here is the lazy version."
   puts result.inspect

Problems to Brian Marick (marick@visibleworkings.com)
Thanks to Pit Capitain for cleaner continuation-calling code.

=end

class LazyComputation

   # How does this work? @compute_next_value is the continuation of the
   # wrapped computation. @return_from_API is the continuation of the
   # initializer or of a call to value(). A call to value() sets
   # @return_from_API and jumps to the wrapped computation. That
   # normally finds the next value, saves the continuation state, and
   # jumps back to @return_from_API. If the computation runs out of
   # values, it falls out of its block, which returns to initialize(),
   # which jumps to the continuation of the most recent API call
   # (@return_from_API), which is most likely a call to value().

   attr_reader :has_value

   def initialize()
     @has_value = callcc { | @return_from_API |
       yield self
       @return_from_API.call(false)
     }
   end

   def value
     raise IndexError.new("There is no next value.") unless @has_value

     retval = @next
     @has_value = callcc { | @return_from_API |
       @compute_next_value.call
       raise RuntimeError, "Statement should never be reached."
     }
     return retval
   end

   def value=(retval)
     @next = retval
     callcc do | @compute_next_value |
       @return_from_API.call(true)
       raise RuntimeError, "Statement should never be reached."
     end
   end

   # Allows a function that normally would push onto an array
   # to be automagically turned lazy. See example_tree below.
   alias_method :push, :value=

end


## EXAMPLES

class LazyExamples

   def example_integers
     puts '== Lazily create all the integers.'
     lazy = LazyComputation.new { | lazy |
       i = 0
       loop {
         lazy.value = i
         i += 1
       }
     }
     for i in 0..10
       puts lazy.value
     end
   end

   # Plain-vanilla function that flattens a tree
   # into a list (array). Thank you, John McCarthy.
   def atoms(tree, accumulator=[])
     if tree.is_a?(Array)
       tree.each { | e | atoms(e, accumulator) }
     else
       accumulator.push(tree)
     end
     accumulator
   end

   def example_tree
     puts '== Lazily descend a tree.'
     tree = [ [1, 2], [3, [4, [5, 6], 7], 8]]

     puts "Here is the eager version."
     puts atoms(tree).inspect

     # Now do it lazily
     lazy = LazyComputation.new { | lazy |
       atoms(tree, lazy)
     }

     result = []
     while lazy.has_value
       result.push(lazy.value)
     end
     puts "Here is the lazy version."
     puts result.inspect
   end

end

if __FILE__ == $0
   LazyExamples.new.example_integers
   LazyExamples.new.example_tree
end


--
Brian Marick, marick@testing.com
www.testing.com - Software testing services and resources
www.testingcraft.com - Where software testers exchange techniques
www.visibleworkings.com - Adequate understanding of system internals