From: Thomas Hafner <thomas@...>
Date: 2009-01-28T05:42:46+09:00
Subject: replacing callcc by catch/throw

Hello,

in his book ``The Ruby Programming Language'' Mats discourages from
using continuations. Nevertheless I've found a real world example,
where at a first look callcc could be easily replaced by catch and
throw, but indeed it's a little bit problematic:

  #!/usr/bin/env ruby
  # -*-mode: ruby; coding: utf-8;-*-

  require 'jcode'
  require 'pp'

  $-K='U'

  module MultiLine
    def transform( input )
      document( input, 0 ){ |p, value| value.flatten }
    end

    private
    def document( input, p, acc = [] )
      loop {
        callcc { |proceed|
          return yield( p, acc ) unless input[p]
          multiline( input, p ){ |p0, v0|
            p = p0
            acc << v0
            proceed.call
          }
          character( input, p ){ |p1, v1|
            p = p1
            acc << v1
            proceed.call
          }
          return nil
        }
      }
    end

    def multiline( input, p )
      '(' == input[p] && multiline_tail( input, p+1 ){ |p2, v2|
        return yield( p2, v2 )
      }
    end

    def multiline_tail( input, p, acc=[] )
      loop {
        callcc { |proceed|
          case input[p]
          when nil
            return nil
          when ')'
            return yield( p+1, acc )
          when "\n", "\r"
            p += 1
            acc << ' '
            proceed.call
          end
          multiline( input, p ){ |p2, v2|
            p = p2
            acc << v2
            proceed.call
          }
          character( input, p ){ |p4, v4|
            p = p4
            acc << v4
            proceed.call
          }
          return nil
        }
      }
    end

    def character( input, p )
      case input[p]
      when nil
        return nil
      when '\\'
        case input[p+1]
        when nil
          return nil
        when '\\', '(', ')'
          return yield( p+2, input[p+1] )
        end
      end
      return yield( p+1, input[p] )
    end

    extend( self )
  end

  if __FILE__ == $0
    input = STDIN.read.split(//)
    output = MultiLine.transform( input )
    print output
  end

The problem is, that the methods can be called recursively, and
catching from a throw should continue at the correct recursion level.
No symbol that has to be thrown/cached should be reused. How about
providing each ``catch'' with an individual symbol?:

    # ...
    def document( input, p, acc = [] )
      proceed = gensym
      loop { catch proceed do
          return yield( p, acc ) unless input[p]
          multiline( input, p ){ |p0, v0|
            p = p0
            acc << v0
            throw proceed          
          }
          character( input, p ){ |p1, v1|
            p = p1
            acc << v1
            throw proceed
          }
          return nil
        end }
    end
    # ... a.s.o. ...
    def multiline_tail( input, p, acc=[] )
      proceed = gensym
      loop { catch proceed do
          case input[p]
          when nil
            return nil
          when ')'
            return yield( p+1, acc )
          when "\n", "\r"
            p += 1
            acc << ' '
            throw proceed
          end
          multiline( input, p ){ |p2, v2|
            p = p2
            acc << v2
            throw proceed
          }
          character( input, p ){ |p4, v4|
            p = p4
            acc << v4
            throw proceed
          }
          return nil
        end }
    end
    # ... a.s.o. ...

A new method is needed to generate the unique symbols:

    def gensym
      [].object_id.to_s.to_sym
    end

The catch/throw solution seems uglier to me than the callcc solution.
Do you have other suggestions?

Regards
  Thomas