The anatomy of a loop: a story of scope and control

ABSTRACT

Writing loops with tail-recursive function calls is the equivalent of writing them with goto's. Given that loop packages for Lisp-family languages have been around for over 20 years, it is striking that none have had much success in the Scheme world. I suggest the reason is that Scheme forces us to be precise about the scoping of the various variables introduced by our loop forms, something previous attempts to design ambitious loop forms have not managed to do.I present the design of a loop package for Scheme with a well-defined and natural scoping rule, based on a notion of control dominance that generalizes the standard lexical-scope rule of the λ-calculus. The new construct is powerful, clear, modular and extensible.The loop language is defined in terms of an underlying language for expressing control-flow graphs. This language itself has interesting properties as an intermediate representation.

REFERENCES

• 1: Jonathan Amsterdam, The Iterate Manual, Massachusetts Institute of Technology, Cambridge, MA, 1990
• 2: Jonathan Amsterdam. Don't Loop, Iterate. Working Paper 324, MIT AI Lab.
• 3: William Clinger , Jonathan Rees, Macros that work, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.155-162, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99607]
• 4: Ryan Culpepper, Scott Owens and Matthew Flatt. Syntactic abstraction in component interfaces. In Proceedings of the Fourth International Conference on Generative Programming and Component Engineering (GPCE'05), September 2005, Tallinn, Estonia.
• 5: Edsger W. Dijkstra, Letters to the editor: go to statement considered harmful, Communications of the ACM, v.11 n.3, p.147-148, March 1968 [doi>10.1145/362929.362947]
• 6: Sebastian Egner. Eager comprehensions in Scheme: The design of SRFI-42. In Proceedings of the ACM SIGPLAN 2005 Workshop on Scheme and Functional Programming (Scheme 2005), September 2005, Tallinn, Estonia. See also http://srfi.schemers.org/srfi-42/.
• 7: Leonard Gilman , Allen J. Rose, APL: An Interactive Approach, Krieger Publishing Co., Inc., Melbourne, FL, 1992
• 8: Erik Hilsdale and Daniel P. Friedman. Writing macros in continuation-passing style. In Proceedings of the Workshop on Scheme and Functional Programming (Scheme 2000), pages 53--61, Montreal, Canada September 2000. Rice Technical Report 00-368. September 2000.
• 9: Richard A. Kelsey, A correspondence between continuation passing style and static single assignment form, Papers from the 1995 ACM SIGPLAN workshop on Intermediate representations, p.13-22, January 23-25, 1995, San Francisco, California, United States
• 10: 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]
• 11: Alan J. Perlis. Epigrams on programming. Sigplan 17 #9, September 1980.
• 12: Kent M. Pitman. Common Lisp Issue LOOP-INITFORMENVIRONMENT: PARTIAL-INTERLEAVING-VAGUE. March 1991. http://www.lisp.org/HyperSpec/Issues/iss222-writeup.html
• 13: Olin Shivers, A Universal Scripting Framework or Lambda: The Ultimate "Little Language", Proceedings of the Second Asian Computing Science Conference on Concurrency and Parallelism, Programming, Networking, and Security, p.254-265, December 02-05, 1996
• 14: Guy L Steele , Gerald J Sussman, Lambda: The Ultimate Imperative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 15: Guy L Steele, LAMBDA: The Ultimate Declarative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 16: Guy L Steele, Debunking the ``Expensive Procedure Call'''' Myth or, Procedure Call Implementations Considered Harmful or, LAMDBA: The Ultimate GOTO, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 17: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 18: Guy L. Steele, Jr., Common LISP: the language (2nd ed.), Digital Press, Newton, MA, 1990
• 19: Philip Wadler. List comprehensions (Chapter 7). In The Implementation of Functional Programming Languages, Editor Simon L. Peyton Jones, Prentice Hall, 1987.
• 20: Richard C.Waters. LetS: An expressional loop notation. AI Memo 680A, MIT AI Lab, February 1983.
• 21: Richard C. Waters. Obviously synchronizable series expressions: Part I: User's manual for the OSS macro package. AI Memo 958A, MIT AI Lab, March 1988.
• 22: Richard C. Waters. Obviously synchronizable series expressions: Part II: Overview of the theory and implementation. AI Memo 959A, MIT AI Lab, March 1988.
• 23: Richard C. Waters, Automatic transformation of series expressions into loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.52-98, Jan. 1991 [doi>10.1145/114005.102806]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Syntax
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives; Functional constructs

General Terms:
Design, Languages, Performance, Theory

Keywords:
compilers, continuations, control structures, functional programming, iteration, lambda-calculus, macros, programming languages, scheme