Interruptible iterators

ABSTRACT

This paper introduces interruptible iterators, a language feature that makes expressive iteration abstractions much easier to implement. Iteration abstractions are valuable for software design, as shown by their frequent use in well-designed data structure libraries such as the Java Collections Framework. While Java iterators support iteration abstraction well from the standpoint of client code, they are awkward to implement correctly and efficiently, especially if the iterator needs to support imperative update of the underlying collection, such as removing the current element. Some languages, such as CLU and C# 2.0, support iteration through a limited coroutine mechanism, but these mechanisms do not support imperative updates. Interruptible iterators are more powerful coroutines in which the loop body is able to interrupt the iterator with requests to perform updates. Interrupts are similar to exceptions, but propagate differently and have resumption semantics. Interruptible iterators have been implemented as part of the JMatch programming language, an extended version of Java. A JMatch reimplementation of the Java Collections Framework shows that implementations can be made substantially shorter and simpler; performance results show that this language mechanism can also be implemented efficiently.

REFERENCES

• 1: Chad Fowler Dave Thomas and Andy Hunt. Programming Ruby: The Pragmatic Programmers' Guide. The Pragmatic Programmers, 2nd edition, 2004. ISBN 0-974-51405-5.
• 2: Ralph E. Griswold , David R. Hanson , John T. Korb, Generators in Icon, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.2, p.144-161, April 1981 [doi>10.1145/357133.357136]
• 3: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 4: John B. Goodenough, Exception handling design issues, ACM SIGPLAN Notices, v.10 n.7, July 1975 [doi>10.1145/987305.987313]
• 5: Emden R. Gansner , John H. Reppy, The standard ML basis library, Cambridge University Press, New York, NY, 2002
• 6: Steven Gregory. Parallel Programming in PARLOG. Addison-Wesley, 1987.
• 7: Christopher T Haynes , Daniel P Friedman , Mitchell Wand, Obtaining coroutines with continuations, Computer Languages, v.11 n.3-4, p.143-153, 1986 [doi>10.1016/0096-0551(86)90007-X]
• 8: Anders Hejlsberg, Scott Wiltamuth, and Peter Golde. The C# Programming Language. Addison-Wesley, 1st edition, October 2003. ISBN 0321154916.
• 9: N. I. Adams, IV , D. H. Bartley , G. Brooks , R. K. Dybvig , D. P. Friedman , R. Halstead , C. Hanson , C. T. Haynes , E. Kohlbecker , D. Oxley , K. M. Pitman , G. J. Rozas , G. L. Steele, Jr. , G. J. Sussman , M. Wand , H. Abelson, Revised5 report on the algorithmic language scheme, ACM SIGPLAN Notices, v.33 n.9, p.26-76, Sept. 1, 1998 [doi>10.1145/290229.290234]
• 10: Bjorn Kirkerud, Object-Oriented Programming with SIMULA, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 11: Barbara Liskov, CLU Reference Manual, Springer-Verlag New York, Inc., Secaucus, NJ, 1983
• 12: Butler Lampson. A description of the Cedar language: A Cedar language reference manual. Technical Report CSL-83-15, Xerox PARC, December 1983.
• 13: Russell R. Atkinson , Barbara H. Liskov , Robert W. Scheifler, Aspects Of Implementing CLU, Proceedings of the 1978 annual conference, p.123-129, December 04-06, 1978, Washington, D.C., United States [doi>10.1145/800127.804079]
• 14: Jed Liu and Andrew C. Myers. JMatch: Java plus pattern matching. Technical Report TR2002-1878, Computer Science Department, Cornell University, October 2002. Software release at http://www.cs.cornell.edu/projects/jmatch.
• 15: Jed Liu , Andrew C. Myers, JMatch: Iterable Abstract Pattern Matching for Java, Proceedings of the 5th International Symposium on Practical Aspects of Declarative Languages, p.110-127, January 13-14, 2003
• 16: Barbara Liskov , Alan Snyder , Russell Atkinson , Craig Schaffert, Abstraction mechanisms in CLU, Communications of the ACM, v.20 n.8, p.564-576, Aug. 1977 [doi>10.1145/359763.359789]
• 17: Joseph A. Bank , Andrew C. Myers , Barbara Liskov, Parameterized types for Java, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.132-145, January 15-17, 1997, Paris, France [doi>10.1145/263699.263714]
• 18: David R. Musser , Gilmer J. Derge , Atul Saini, STL tutorial and reference guide, second edition: C++ programming with the standard template library, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 19: Microsoft Corporation, Microsoft C# Language Specifications, Microsoft Press, Redmond, WA, 2001
• 20: Andrew C. Myers, Barbara Liskov, and Nicholas Mathewson. PolyJ: Parameterized types for Java. Software release, at http://www.cs.cornell.edu/polyj, July 1998.
• 21: Ole Lehrmann Madsen , Birger Mø-Pedersen , Kristen Nygaard, Object-oriented programming in the BETA programming language, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 22: Stephan Murer , Stephen Omohundro , David Stoutamire , Clemens Szyperski, Iteration abstraction in Sather, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.1, p.1-15, Jan. 1996 [doi>10.1145/225540.225541]
• 23: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 24: Nathaniel Nystrom, Michael Clarkson, and Andrew C. Myers. Polyglot: An extensible compiler framework for Java. In Görel Hedin, editor, Compiler Construction, 12th International Conference, CC 2003, number 2622 in Lecture Notes in Computer Science, pages 138--152, Warsaw, Poland, April 2003. Springer-Verlag.
• 25: The SML/NJ Fellowship. Standard ML of New Jersey. http://www.smlnj.org/.
• 26: Bjarne Stroustrup, The C++ programming language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 27: Sun Microsystems. JDK 5 Java Language Documentation, 2004. http://java.sun.com/j2se/1.5.0/docs/guide/language.
• 28: Mary Shaw , William A. Wulf , Ralph L. London, Abstraction and verification in Alphard: defining and specifying iteration and generators, Communications of the ACM, v.20 n.8, p.553-564, Aug. 1977 [doi>10.1145/359763.359782]
• 29: Guido van Rossum. The Python Language Reference Manual. Network Theory, Ltd., September 2003.
• 30: Niklaus Wirth, Programming in MODULA-2 (3rd corrected ed.), Springer-Verlag New York, Inc., New York, NY, 1985
• 31: David H D Warren , Luis M. Pereira , Fernando Pereira, Prolog - the language and its implementation compared with Lisp, Proceedings of the 1977 symposium on Artificial intelligence and programming languages, p.109-115, August 15-17, 1977

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Coroutines

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming
      D.1.6 Logic Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Multiparadigm languages

General Terms:
Design, Languages

Keywords:
JMatch, Java, coroutine, exception, logic programming