Multi-return function call

ABSTRACT

It is possible to extend the basic notion of "function call" to allow functions to have multiple return points. This turns out to be a surprisingly useful mechanism. This paper conducts a fairly wide-ranging tour of such a feature: a formal semantics for a minimal λ -calculus capturing the mechanism; a motivating example; a static type system; useful transformations; implementation concerns and experience with an implementation; and comparison to related mechanisms, such as exceptions, sum-types and explicit continuations. We conclude that multiple-return function call is not only a useful and expressive mechanism, both at the source-code and intermediate-representation level, but is also quite inexpensive to implement.

REFERENCES

• 1: Andrew W. Appel, Modern Compiler Implementation: In ML, Cambridge University Press, New York, NY, 1998
• 2: Henk Barendregt. The Lambda Calculus. North Holland, revised edition, 1984.
• 3: Frank DeRemer , Thomas Pennello, Efficient Computation of LALR(1) Look-Ahead Sets, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.615-649, Oct. 1982 [doi>10.1145/69622.357187]
• 4: Charles N. Fischer , Richard J. LeBlanc, Jr., Crafting a compiler, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1988
• 5: Andrzej Filinksi. Declarative Continuations and Categorical Duality. Master's thesis, Computer Science Department, University of Copenhagen (August 1989). DIKU Report 89/11.
• 6: Cormac Flanagan , Amr Sabry , Bruce F. Duba , Matthias Felleisen, The essence of compiling with continuations, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.237-247, June 21-25, 1993, Albuquerque, New Mexico, United States
• 7: American National Standard Programming Language FOR-TRAN. X3.9-1978, American National Standards Institute, Inc., April, 1978. Available at http://www.fortran.com/F77_std/rjcnf.html
• 8: S. C. Johnson. Yacc-yet another compiler compiler. Tech report CSTR-32, AT&T Bell Laboratories, Murray Hill, NJ.
• 9: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, ACM SIGPLAN Notices, v.21 n.7, p.219-233, July 1986
• 10: R. Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17:348--375, August 1978.
• 11: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 12: D. Tarditi , G. Morrisett , P. Cheng , C. Stone , R. Harper , P. Lee, TIL: a type-directed optimizing compiler for ML, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.181-192, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 13: Thomas J. Pennello, Very fast LR parsing, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.145-151, June 25-27, 1986, Palo Alto, California, United States
• 14: Norman Ramsey , Simon Peyton Jones, A single intermediate language that supports multiple implementations of exceptions, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.285-298, June 18-21, 2000, Vancouver, British Columbia, Canada
• 15: Zhong Shao , John H. Reppy , Andrew W. Appel, Unrolling lists, Proceedings of the 1994 ACM conference on LISP and functional programming, p.185-195, June 27-29, 1994, Orlando, Florida, United States
• 16: Olin Shivers. SRFI-32: Sort libraries. Scheme Request for Implementation 32, available at URL http://srfi.schemers.org/. Forthcoming.
• 17: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 18: Mitchell Wand. Complete type inference for simple objects, In Proceedings of the Second Symposium on Logic in Computer Science, Ithaca, New York, pages 37--44, June 1987.

INDEX TERMS

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

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: Semantics; Syntax
      D.3.3 Language Constructs and Features
          Subjects: Recursion; Procedures, functions, and subroutines

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

General Terms:
Design, Languages, Performance, Theory

Keywords:
compilers, continuations, control structures, functional programming, lambda calculus, procedure call, programming languages