Revised report on the algorithmic language scheme

ABSTRACT

The report gives a defining description of the programming language Scheme. Scheme is a statically scoped and properly tail-recursive dialect of the Lisp programming language invented by Guy Lewis Steele Jr. and Gerald Jay Sussman. It was designed to have an exceptionally clear and simple semantics and few different ways to form expressions. A wide variety of programming paradigms, including imperative, functional, and message passing styles, find convenient expression in Scheme.

REFERENCES

• 1: Harold Abelson , Gerald Jay Sussman, LISP: a language for stratified design, BYTE, v.13 n.2, p.207-218, February 1988
• 2: Harold Abelson , Gerald Jay Sussman , Julie Sussman, Structure and interpretation of computer programs, MIT Press, Cambridge, MA, 1985
• 3: Norman Adams , Jonathan Rees, Object-oriented programming in scheme, Proceedings of the 1988 ACM conference on LISP and functional programming, p.277-288, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62720]
• 4: David H. Bartley , John C. Jensen, The implementation of PC Scheme, Proceedings of the 1986 ACM conference on LISP and functional programming, p.86-93, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319852]
• 5: [5] John Batali, Edmund Goodhue, Chris Hanson, Howie Shrobe, Richard M. Stallman, and Gerald Jay Sussman. The Scheme-81 architecture--system and chip. In Proceedings, Conference on Advanced Research in VLSI, pages 69-77. Paul Penfield, Jr., editor. Artech House, 610 Washington Street, Dedham MA, 1982.
• 6: Alan Bawden , Jonathan Rees, Syntactic closures, Proceedings of the 1988 ACM conference on LISP and functional programming, p.86-95, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62687]
• 7: William Clinger, The scheme 311 compiler an exercise in denotational semantics, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.356-364, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802052]
• 8: [8] William Clinger, editor. The revised revised report on Scheme, or an uncommon Lisp. MIT Artificial Intelligence Memo 848, August 1985. Also published as Computer Science Department Technical Report 174, Indiana University, June 1985.
• 9: William Clinger, Semantics of Scheme, BYTE, v.13 n.2, p.221-227, February 1988
• 10: William D. Clinger, How to read floating point numbers accurately, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.92-101, June 1990, White Plains, New York, United States
• 11: W Clinger , D P Friedman , M Wand, A scheme for a higher-level semantic algebra, Algebraic methods in semantics, Cambridge University Press, New York, NY, 1986
• 12: Will Clinger , Anne Hartheimer , Eric Ost, Implementation strategies for continuations, Proceedings of the 1988 ACM conference on LISP and functional programming, p.124-131, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62692]
• 13: 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]
• 14: Pavel Curtis , James Rauen, A module system for scheme, Proceedings of the 1990 ACM conference on LISP and functional programming, p.13-19, June 27-29, 1990, Nice, France [doi>10.1145/91556.91573]
• 15: R. Kent Dybvig, The SCHEME programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 16: [16] R. Kent Dybvig and Daniel P. Friedman and Christopher T. Haynes. Expansion-passing style: a general macro mechanism. Lisp and Symbolic Computation 1(1): 53-76, June 1988.
• 17: R. Kent Dybvig , Robert Hieb, A variable-arity procedural interface, Proceedings of the 1988 ACM conference on LISP and functional programming, p.106-115, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62689]
• 18: R. K. Dybvig , R. Hieb, Engines from continuations, Computer Languages, v.14 n.2, p.109-123, Aug. 1989 [doi>10.1016/0096-0551(89)90018-0]
• 19: R. Hieb , R. Kent Dybvig, Continuations and concurrency, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.128-136, March 14-16, 1990, Seattle, Washington, United States
• 20: [20] Michael A. Eisenberg. Bochser: an integrated Scheme programming system. MIT Laboratory for Computer Science Technical Report 349, October 1985.
• 21: [21] Michael Eisenberg. Harold Abelson, editor. Programming In Scheme. Scientific Press, Redwood City, California, 1988.
• 22: Michael Eisenberg , William Clinger , Anne Hartheimer, Programming in MacScheme, MIT Press, Cambridge, MA, 1990
• 23: [23] Marc Feeley. Deux approches à l'implantation du language Scheme. M.Sc. thesis, Département d'Informatique et de Recherche Opérationelle, University of Montreal, May 1986.
• 24: Marc Feeley , Guy Lapalme, Using closures for code generation, Computer Languages, v.12 n.1, p.47-66, Jan. 1987 [doi>10.1016/0096-0551(87)90012-9]
• 25: Marc Feeley , James S. Miller, A parallel virtual machine for efficient scheme compilation, Proceedings of the 1990 ACM conference on LISP and functional programming, p.119-130, June 27-29, 1990, Nice, France [doi>10.1145/91556.91606]
• 26: Matthias Felleisen, Reflections on Landin's J-operator: a partly historical note, Computer Languages, v.12 n.3-4, p.197-207, November 1, 1987 [doi>10.1016/0096-0551(87)90022-1]
• 27: [27] Matthias Felleisen and Daniel P. Friedman. Control operators, the SECD-machine, and the lambda-calculus. In 3rd Working Conference on the Formal Description of Programming Concepts, pages 193- 219, August 1986.
• 28: Matthias Felleisen , Daniel P Friedman, A closer look at export and import statements, Computer Languages, v.11 n.1, p.29-37, 1986 [doi>10.1016/0096-0551(86)90015-9]
• 29: Mattias Felleisen , D. P. Friedman, A calculus for assignments in higher-order languages, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.314, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41654]
• 30: M Felleisen , D P Friedman, A reduction semantics for imperative higher-order languages, Volume II: Parallel Languages on PARLE: Parallel Architectures and Languages Europe, p.206-223, March 1987, Eindhoven, The Netherlands
• 31: [31] Matthias Felleisen, Daniel P. Friedman, Eugene Kohlbecker, and Bruce Duba. Reasoning with continuations. In Proceedings of the Symposium on Logic in Computer Science, pages 131-141. IEEE Computer Society Press, Washington DC, 1986.
• 32: Mattias Felleisen , D. P. Friedman , E. Kohlbecker , B. Duba, A syntactic theory of sequential control, Theoretical Computer Science, v.52 n.3, p.205-237, June 1987 [doi>10.1016/0304-3975(87)90109-5]
• 33: Matthias Felleisen , Mitch Wand , Daniel Friedman , Bruce Duba, Abstract continuations: a mathematical semantics for handling full jumps, Proceedings of the 1988 ACM conference on LISP and functional programming, p.52-62, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62684]
• 34: [34] Carol Fessenden, William Clinger, Daniel P. Friedman, and Christopher Haynes. Scheme 311 version 4 reference manual. Indiana University Computer Science Technical Report 137, February 1983. Superseded by [40].
• 35: John Franco , Daniel P. Friedman, Towards a facility for lexically scoped, dynamic mutual recursion in Scheme, Computer Languages, v.15 n.1, p.55-64, Jan. 1990 [doi>10.1016/0096-0551(90)90019-L]
• 36: D. P. Friedman , Mattias Felleisen, The little LISPer, MIT Press, Cambridge, MA, 1987
• 37: D. P. Friedman , Mattias Felleisen, The little LISPer, MIT Press, Cambridge, MA, 1987
• 38: Daniel P. Friedman , Christopher T. Haynes, Constraining control, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.245-254, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318654]
• 39: [39] Daniel P. Friedman, Christopher T. Haynes, and Eugene Kohlbecker. Programming with continuations. In Program Transformation and Programming Environments, pages 263-274. P. Pepper, editor. Springer-Verlag, 1984.
• 40: [40] D. Friedman, C. Haynes, E. Kohlbecker, and M. Wand. Scheme 84 interim reference manual. Indiana University Computer Science Technical Report. 153, January 1985.
• 41: Daniel P. Friedman , Mitchell Wand, Reification: Reflection without metaphysics, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.348-355, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802051]
• 42: Christopher T. Haynes, Logic Continuations, Proceedings of the Third International Conference on Logic Programming, p.671-685, July 14-18, 1986
• 43: Christopher T. Haynes , Daniel P. Friedman, Engines build process abstractions, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.18-24, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802018]
• 44: Christopher T. Haynes , Daniel P. Friedman, Abstracting timed preemption with engines, Computer Languages, v.12 n.2, p.109-121, Aug. 1987 [doi>10.1016/0096-0551(87)90003-8]
• 45: Christopher T. Haynes , Daniel P. Friedman, Embedding continuations in procedural objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.582-598, Oct. 1987 [doi>10.1145/29873.30392]
• 46: 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]
• 47: Peter Henderson, Functional geometry, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.179-187, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802148]
• 48: R. Hieb , R. Kent Dybvig , Carl Bruggeman, Representing control in the presence of first-class continuations, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.66-77, June 1990, White Plains, New York, United States
• 49: [49] IEEE Standard 754-1985. IEEE Standard for Binary Floating-Point Arithmetic. IEEE, New York, 1985.
• 50: CORPORATE IEEE, Inc. Staff, IEEE Std 1178-1990, IEEE Standard for the Scheme Programming Language, IEEE Standards Office, New York, NY, 1991
• 51: [51] Eugene Edmund Kohlbecker Jr. Syntactic Extensions in the Programming Language Lisp. PhD thesis, Indiana University, August 1986.
• 52: Eugene Kohlbecker , Daniel P. Friedman , Matthias Felleisen , Bruce Duba, Hygienic macro expansion, Proceedings of the 1986 ACM conference on LISP and functional programming, p.151-161, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319859]
• 53: Norman Adams , David Kranz , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.219-233, June 25-27, 1986, Palo Alto, California, United States
• 54: David Andrew Kranz , Paul Hudak, Orbit: an optimizing compiler for scheme, Yale University, New Haven, CT, 1988
• 55: P. J. Landin, Correspondence between ALGOL 60 and Church's Lambda-notation: part I, Communications of the ACM, v.8 n.2, p.89-101, Feb. 1965 [doi>10.1145/363744.363749]
• 56: Drew McDermott, An efficient environment allocation scheme in an interpreter for a lexically-scoped LISP, Proceedings of the 1980 ACM conference on LISP and functional programming, p.154-162, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802801]
• 57: [57] MIT Department of Electrical Engineering and Computer Science. Scheme manual, seventh edition. September 1984.
• 58: Steven S. Muchnick , Uwe F. Pleban, A semantic comparison of LISP and SCHEME, Proceedings of the 1980 ACM conference on LISP and functional programming, p.56-64, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802790]
• 59: J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger , P. Naur, Revised report on the algorithm language ALGOL 60, Communications of the ACM, v.6 n.1, p.1-17, Jan. 1963 [doi>10.1145/366193.366201]
• 60: Paul Penfield, Jr., Principal values and branch cuts in complex APL, ACM SIGAPL APL Quote Quad, v.12 n.1, p.248-256, September 1981
• 61: [61] Kent M. Pitman. Exceptional situations in Lisp. MIT Artificial Intelligence Laboratory Working Paper 268, February 1985.
• 62: [62] Kent M. Pitman. The revised Mac Lisp manual (Saturday evening edition). MIT Laboratory for Computer Science Technical Report 295, May 1983.
• 63: Kent M. Pitman, Special forms in Lisp, Proceedings of the 1980 ACM conference on LISP and functional programming, p.179-187, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802804]
• 64: [64] Uwe F. Pleban. A Denotational Approach to Flow Analysis and Optimization of Scheme, A Dialect of Lisp. PhD thesis, University of Kansas, 1980.
• 65: [65] Jonathan A. Rees. Modular Macros. M.S. thesis, MIT, May 1989.
• 66: Jonathan A. Rees , Norman I. Adams IV, T: a dialect of Lisp or LAMBDA: The ultimate software tool, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.114-122, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802142]
• 67: [67] Jonathan A. Rees, Norman I. Adams IV, and James R. Meehan. The T manual, fourth edition. Yale University Computer Science Department, January 1984.
• 68: J Rees , W Clinger, Revised report on the algorithmic language scheme, ACM SIGPLAN Notices, v.21 n.12, p.37-79, Dec. 1986 [doi>10.1145/15042.15043]
• 69: John C. Reynolds, Definitional interpreters for higher-order programming languages, Proceedings of the ACM annual conference, p.717-740, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800194.805852]
• 70: [70] Guillermo a. Rozas. Liar, an Algol-like compiler for Scheme. S.B. thesis, MIT Department of Electrical Engineering and Computer Science, January 1984.
• 71: O. Shivers, Control flow analysis in scheme, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.164-174, June 20-24, 1988, Atlanta, Georgia, United States
• 72: Dorai Staram , Matthias Felleisen, Control delimiters and their hierarchies, Lisp and Symbolic Computation, v.3 n.1, p.67-99, Jan. 1990 [doi>10.1007/BF01806126]
• 73: [73] Brian C. Smith. Reflection and semantics in a procedural language. MIT Laboratory for Computer Science Technical Report 272, January 1982.
• 74: George Springer , Daniel P. Friedman, Scheme and the art of programming, MIT Press, Cambridge, MA, 1989
• 75: [75] Amitabh Srivastava, Don Oxley, and Aditya Srivastava. An(other) integration of logic and functional programming. In Proceedings of the Symposium on Logic Programming, pages 254-260. IEEE, 1985.
• 76: [76] Richard M. Stallman. Phantom stacks--if you look too hard, they aren't there. MIT Artificial Intelligence Memo 556, July 1980.
• 77: [77] Guy Lewis Steele Jr. Lambda, the ultimate declarative. MIT Artificial Intelligence Memo 379, November 1976.
• 78: Guy Lewis Steele, Jr., Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO, Proceedings of the 1977 annual conference, p.153-162, January 1977 [doi>10.1145/800179.810196]
• 79: Guy Lewis Steele, Jr., Macaroni is better than spaghetti, Proceedings of the 1977 symposium on Artificial intelligence and programming languages, p.60-66, August 15-17, 1977
• 80: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 81: [81] Guy Lewis Steele Jr. Compiler optimization based on viewing LAMBDA as RENAME + GOTO. In AI: An MIT Perspective. Patrick Henry Winston Richard Henry Brown, editor. MIT Press, 1980.
• 82: Guy L. Steele, Jr., An overview of COMMON LISP, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.98-107, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802140]
• 83: Guy L. Steele, Jr., Common LISP: the language, Digital Press, Newton, MA, 1984
• 84: [84] Guy Lewis Steele Jr. and Gerald Jay Sussman. Lambda, the ultimate imperative. MIT Artificial Intelligence Memo 353, March 1976.
• 85: [85] Guy Lewis Steele Jr. and Gerald Jay Sussman. The revised report on Scheme, a dialect of Lisp. MIT Artificial Intelligence Memo 452, January 1978.
• 86: [86] Guy Lewis Steele Jr. and Gerald Jay Sussman. The art of the interpreter, or the modularity complex (parts zero, one, and two). MIT Artificial Intelligence Memo 453, May 1978.
• 87: Guy Lewis Steele, Jr. , Gerald Jay Sussman, Design of a LISP-based microprocessor, Communications of the ACM, v.23 n.11, p.628-645, Nov. 1980 [doi>10.1145/359024.359031]
• 88: Guy Lewis Steele, Jr. , Gerald Jay Sussman, The dream of a lifetime: A lazy variable extent mechanism, Proceedings of the 1980 ACM conference on LISP and functional programming, p.163-172, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802802]
• 89: Guy L. Steele, Jr. , Jon L. White, How to print floating-point numbers accurately, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.112-126, June 1990, White Plains, New York, United States
• 90: [90] Gerald Jay Sussman. Lisp, programming and implementation. In Functional Programming and its Applications . Darlington, Henderson, Turner, editor. Cambridge University Press, 1982.
• 91: [91] Gerald Jay Sussman and Guy Lewis Steele Jr. Scheme: an interpreter for extended lambda calculus. MIT Artificial Intelligence Memo 349, December 1975.
• 92: [92] Gerald Jay Sussman, Jack Holloway, Guy Lewis Steele Jr., and Alan Bell. Scheme-79--Lisp on a chip. IEEE Computer 14(7):10-21, July 1981.
• 93: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 94: [94] Texas Instruments, Inc. TI Scheme Language Reference Manual. Preliminary version 1.0, November 1985.
• 95: Steven R. Vegdahl , Uwe F. Pleban, The runtime environment for Scheme, a Scheme implementation on the 88000, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.172-182, April 03-06, 1989, Boston, Massachusetts, United States
• 96: Mitchell Wand, Continuation-Based Program Transformation Strategies, Journal of the ACM (JACM), v.27 n.1, p.164-180, Jan. 1980 [doi>10.1145/322169.322183]
• 97: Mitchell Wand, Continuation-based multiprocessing, Proceedings of the 1980 ACM conference on LISP and functional programming, p.19-28, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802786]
• 98: Mitchell Wand, Finding the source of type errors, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.38-43, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512648]
• 99: Mitchell Wand , Daniel P. Friedman, The mystery of the tower revealed: a non-reflective description of the reflective tower, Proceedings of the 1986 ACM conference on LISP and functional programming, p.298-307, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319871]
• 100: [100] Mitchell Wand and Daniel P. Friedman. Compiling lambda expressions using continuations and factorizations. Journal of computer Languages 3:241-263, 1978.
• 101: [101] Mitchell Wand and Daniel P. Friedman. The mystery of the tower revealed. a non-reflective description of the reflective tower. In Meta-level Architectures and Reflection, pages 111-134. P. Maes and D. Nardi, editor. Elsevierr Sci. Publishers B.V. (North Holland), 1988.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Documentation, Languages