Static analysis for syntax objects

ABSTRACT

We describe an s-expression based syntax-extension framework much like Scheme macros, with a key additional facility: the ability to define static semantics, such as type systems or program analysis, for the new, user-defined forms or embedded languages, thus allowing us to construct "towers" of language levels. In addition, the static semantics of the languages at two adjacent levels in the tower can be connected, allowing improved reasoning power at a higher (and perhaps more restricted) level to be reflected down to the static semantics of the language level below. We demonstrate our system by designing macros for an assembly language, together with some example static analyses (termination analysis, type inference and control-flow analysis).

REFERENCES

• 1: Alan Bawden, Reification without evaluation, Proceedings of the 1988 ACM conference on LISP and functional programming, p.342-349, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62726]
• 2: 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]
• 3: R. Kent Dybvig , Robert Hieb , Carl Bruggeman, Syntactic abstraction in Scheme, Lisp and Symbolic Computation, v.5 n.4, p.295-326, Dec. 1992 [doi>10.1007/BF01806308]
• 4: Robert Bruce Findler , John Clements , Cormac Flanagan , Matthew Flatt , Shriram Krishnamurthi , Paul Steckler , Matthias Felleisen, DrScheme: a programming environment for Scheme, Journal of Functional Programming, v.12 n.2, p.159-182, March 2002 [doi>10.1017/S0956796801004208]
• 5: Matthew Flatt, Composable and compilable macros:: you want it when?, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.72-83, October 04-06, 2002, Pittsburgh, PA, USA
• 6: Dan Friedman. Object-oriented style. Invited talk at International LISP Conference, October 2003.
• 7: Daniel P. Friedman , William E. Byrd , Oleg Kiselyov, The Reasoned Schemer, The MIT Press, 2005
• 8: Kathryn E Gray and Matthew Flatt. Compiling Java to PLT Scheme. In Proceedings of the 2004 Scheme Workshop, September 2004.
• 9: Graham Hutton , Erik Meijer, Monadic parsing in Haskell, Journal of Functional Programming, v.8 n.4, p.437-444, July 1998 [doi>10.1017/S0956796898003050]
• 10: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams Iv , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand, Revised Report on the Algorithmic Language Scheme, Higher-Order and Symbolic Computation, v.11 n.1, p.7-105, August 1998 [doi>10.1023/A:1010051815785]
• 11: Shriram Krishnamurthi , Yan-David Erlich , Matthias Felleisen, Expressing Structural Properties as Language Constructs, Proceedings of the 8th European Symposium on Programming Languages and Systems, p.258-272, March 22-28, 1999
• 12: Shriram Krishnamurthi , Matthias Felleisen, Toward a formal theory of extensible software, Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering, p.88-98, November 01-05, 1998, Lake Buena Vista, Florida, United States
• 13: Shriram Krishnamurthi , Matthias Felleisen , Bruce F. Duba, From Macros to Reusable Generative Programming, Proceedings of the First International Symposium on Generative and Component-Based Software Engineering, p.105-120, September 28-30, 1999
• 14: Daan Leijen and Erik Meijer. Parsec: Direct style monadic parser combinators for the real world. Technical Report UU-CS-2001-27, Department of Computer Science, Universiteit Utrecht, 2001.
• 15: William Maddox, Semantically-Sensitive Macroprocessing, University of California at Berkeley, Berkeley, CA, 1989
• 16: Greg Morrisett , David Walker , Karl Crary , Neal Glew, From system F to typed assembly language, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.3, p.527-568, May 1999 [doi>10.1145/319301.319345]
• 17: Ravi A. Nanavati. Extensible syntax in the presence of static analysis. MasterÆs thesis, Massachusetts Institute of Technology, September 2000.
• 18: Benjamin C. Pierce, Advanced Topics in Types and Programming Languages, The MIT Press, 2004
• 19: Francois Pottier and Didier Remy. The Essence of ML Type Inference, pages 389--489. In Pierce {18}, 2005.
• 20: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 21: Olin Shivers, The anatomy of a loop: a story of scope and control, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 22: Randall B. Smith , David Ungar, Programming as an Experience: The Inspiration for Self, Proceedings of the 9th European Conference on Object-Oriented Programming, p.303-330, August 07-11, 1995
• 23: Walid Taha , Tim Sheard, Multi-stage programming with explicit annotations, Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.203-217, June 12-13, 1997, Amsterdam, The Netherlands
• 24: David Ungar , Randall B. Smith, Self: The power of simplicity, Conference proceedings on Object-oriented programming systems, languages and applications, p.227-242, October 04-08, 1987, Orlando, Florida, United States
• 25: Dale Vaillancourt. ACL2 in DrScheme. http://www.ccs.neu.edu/home/dalev/acl2-drscheme/.
• 26: Mitchell Wand. Complete type inference for simple objects. In Proceedings of the IEEE Symposium on Logic in Computer Science, June 1987.
• 27: Daniel Weise , Roger Crew, Programmable syntax macros, ACM SIGPLAN Notices, v.28 n.6, p.156-165, June 1993
• 28: Eric Van Wyk , Oege de Moor , Kevin Backhouse , Paul Kwiatkowski, Forwarding in Attribute Grammars for Modular Language Design, Proceedings of the 11th International Conference on Compiler Construction, p.128-142, April 08-12, 2002

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Extensible languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Macro and assembly languages
      D.3.3 Language Constructs and Features
          Subjects: Classes and objects; Frameworks; Polymorphism; Constraints; Control structures; Inheritance

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Design, Languages

Keywords:
domain-specific languages, extensible programming languages, flow analysis, language towers, lazy delegation, macros, static analysis, type inference