Down with Emacs Lisp: dynamic scope analysis

ABSTRACT

It is possible to translate code written in Emacs Lisp or another Lisp dialect which uses dynamic scoping to a more modern programming language with lexical scoping while largely preserving structure and readability of the code. The biggest obstacle to such an idiomatic translation from Emacs Lisp is the translation of dynamic binding into suitable instances of lexical binding: Many binding constructs in real programs in fact exhibit identical behavior under both dynamic and lexical binding. An idiomatic translation needs to detect as many of these binding constructs as possible and convert them into lexical binding constructs in the target language to achieve readability and efficiency of the target code. The basic prerequisite for such an idiomatic translation is thus a dynamic scope analysis which associates variable occurrences with binding constructs. We present such an analysis. It is an application of the Nielson/Nielson framework for flow analysis to a semantics for dynamic binding akin to Moreau's. Its implementation handles a substantial portion of Emacs Lisp, has been applied to realistic Emacs Lisp code, and is highly accurate and reasonably efficient in practice.

REFERENCES

• 1: Alexander Aiken, Set Constraints: Results, Applications, and Future Directions, Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, p.326-335, May 02-04, 1994
• 2: Alexander Aiken , Edward L. Wimmers, Type inclusion constraints and type inference, Proceedings of the conference on Functional programming languages and computer architecture, p.31-41, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165188]
• 3: P. Bothner. JEmacs-the java/scheme-based emacs. In Proceedings of the FREENIX Track; 2000 USENIX Annual Technical Conference (FREENIX-00), pages 271-278, Berkeley, CA. June 18-23 2000. USENIX Ass.
• 4: P. Bothner. JEmacs --the Java/Scheme-based Erases text editor. http://jemacs.sourceforge.net/. Feb. 2001.
• 5: H. B. Curry and R. Feys. Combinatory Logic, volume I. North-Holland, Amsterdam, 1958.
• 6: M. Felleisen and D. P. Friedman, Control operators, the SECD-machine, and the A-calculus. In M. Wirsing, editor, Formal Description of Programming Concepts III, pages 193-217. NorthHolland, 1986.
• 7: C. Flanagan and M. Felleisen. Set-based analysis for full scheme and its use in soft-typing. Technical Report TR95-254, Rice University, Oct., 1995.
• 8: Cormac Flanagan , Matthias Felleisen, Componential set-based analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.2, p.370-416, March 1999 [doi>10.1145/316686.316703]
• 9: Michael J.C. Gordon, Programming language theory and its implementation, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1988
• 10: Guile Emacs. http://gemacs.sourceforge.net/, July 2000.
• 11: R. Harper and C. Stone. An interpretation of Standard ML in type theory. Technical Report CMU-CS-97- i47, Carnegie Mellon University, Pittsburgh, PA, June 1997. (Also published as Fox Memorandum CMU-CS-FOX-97-01.).
• 12: Nevin Heintze, Set-based analysis of ML programs, Proceedings of the 1994 ACM conference on LISP and functional programming, p.306-317, June 27-29, 1994, Orlando, Florida, United States
• 13: J. Roger Hindley , Jonathan P. Seldin, Introduction to combinators and &lgr;-calculus, Cambridge University Press, New York, NY, 1986
• 14: Suresh Jagannathan , Stephen Weeks, A unified treatment of flow analysis in higher-order languages, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.393-407, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199536]
• 15: Richard A. Kelsey , Jonathan A. Rees, A tractable Scheme implementation, Lisp and Symbolic Computation, v.7 n.4, p.315-335, Dec. 1994 [doi>10.1007/BF01018614]
• 16: B. Lewis, D. LaLiberte, R. Stallman, and the GNU Manual Group. GNU Emacs Lisp reference manual. http //vww gnu. org/manual/elisp-manual-20-2 .5/ elisp.html, 1785.
• 17: Jeffrey R. Lewis , John Launchbury , Erik Meijer , Mark B. Shields, Implicit parameters: dynamic scoping with static types, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.108-118, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325708]
• 18: Robin Milner , Mads Tofte, Co-induction in relational semantics, Theoretical Computer Science, v.87 n.1, p.209-220, Sept. 16, 1991 [doi>10.1016/0304-3975(91)90033-X]
• 19: John C. Mitchell , Gordon D. Plotkin, Abstract types have existential type, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.3, p.470-502, July 1988 [doi>10.1145/44501.45065]
• 20: Luc Moreau, A Syntactic Theory of Dynamic Binding, Higher-Order and Symbolic Computation, v.11 n.3, p.233-279, 1998 [doi>10.1023/A:1010087314987]
• 21: M. Neubauer. Dynamic scope analysis for Emacs Lisp. Master's thesis, Ebcrhard-KarlsUniversitt Tuhirigen, Dec. 2000. http: //www. ml ormatik. uni-freiburg. de/Theubauer/diplom.ps.gz.
• 22: Flemming Nielson , Hanne Riis Nielson, Infinitary control flow analysis: a collecting semantics for closure analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.332-345, January 15-17, 1997, Paris, France [doi>10.1145/263699.263745]
• 23: G. D. Plotkin. A structural approach to operational semantics. Technical Report DAIMI FN19. Computer Science Department, Aarhus University, Aarhus, Denmark. Sept. 1981.
• 24: Christian Queinnec , Kathleen Callaway, Lisp in small pieces, Cambridge University Press, New York, NY, 1996
• 25: K. Raeburn. Guile-based Emacs. http: //www.mit.edu/raeburn/guilemacs/, July 1999.
• 26: Manuel Serrano , Marc Feeley, Storage use analysis and its applications, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.50-61, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 27: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 28: R. Stallman. GNU extension language plans. Usenet article. Oct. 1994.
• 29: B. Wing. XEmacs Lisp Reference Manual, ftp://ftp.xemacs.org/pub/xemacs/docs!a4/ lispref-a4.pdf.gz, May 1999. Version 3.4.
• 30: Andrew K. Wright , Matthias Felleisen, A syntactic approach to type soundness, Information and Computation, v.115 n.1, p.38-94, Nov. 15, 1994 [doi>10.1006/inco.1994.1093]
• 31: Andrew K. Wright , Matthias Felleisen, A syntactic approach to type soundness, Information and Computation, v.115 n.1, p.38-94, Nov. 15, 1994 [doi>10.1006/inco.1994.1093]
• 32: Andrew K. Wright , Suresh Jagannathan, Polymorphic splitting: an effective polyvariant flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.1, p.166-207, Jan. 1998 [doi>10.1145/271510.271523]

INDEX TERMS

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

          Nouns: LISP

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Syntax

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages

General Terms:
Algorithms, Languages