Rope: An Alternative to Ruby's String

Presented November 2, 2007

This talk was given at RubyConf 2007 in Charlotte, NC.

I had a number of somewhat disparate goals for this talk:

• Provide a basic understanding of the Rope data structure to those who'd not seen it before.
• Show how some of the nice elements of Ruby made some implementation details trivial.
• Emphasize the benefit to the Ruby community of having a large number of “drop-in” data structures available.
• Remind Rubyists that data structures (and the computational complexity associated with them) often trump the inherent speed of any given language.
• Encourage the Ruby community to participate in the annual International Conference on Functional Programming (ICFP) Programming Contest.

You can view this presentation as either a QuickTime movie or as a Flash movie:

• QuickTime version (7.9 MB, low resolution, full animations)
• Flash version (3.3 MB, high resolution, reduced animations)

There are a number of links that go with the talk:

• The Rope project on RubyForge
  http://rubyforge.org/projects/rope
• Ropes: an Alternative to Strings
  by Hans-Juergen Boehm, Russ Atkinson, and Michael Plass
  The original paper on ropes.
  http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol25/issue12/spe986.pdf
• Documentation for SGI's C++ rope library
  http://www.sgi.com/tech/stl/Rope.html)
• ICFP Programming Contest
  I particularly recommend the report (PDF file) linked from that page that describes the process of creating the contest. It's impressive!
  http://www.icfpcontest.org
• The Ruby Quiz
  http://rubyquiz.com