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]
A. Aiken. Set constraints: Results. applications and future directions. Lecture Notes in Computer Science, 874:326-335, 1994.
[2]
A. Aiken and E. Wimniers. Type inclusion constraints and type inference. In Proceedings of the FPCA 1993, pages 31-41, 1993.
[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]
C. Flanagan and M. Felleisen. Componential set-based analysis. ACM Transactions on Programming Languages and Systems, 21(2):370-416, Mar. 1999.
[9]
M. J. C. Gordon. Programming Language Theory and its Implementation. Prentice-Hall, 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]
N. Heintze. Set-based analysis of ML programs. In ACM Conference on Lisp and Functional Programming, pages 306 -317, 1994.
[13]
R. Hindley and J. Seldin. Introduction to Combinators and A-Calculus, volume 1 of London Mathematical Society Student Texts. Cambridge University Press, 1986.
[14]
S. Jagannathan and S. Weeks. A Unified Treatment of Flow Analysis in Higher-Order Languages. In POPL, 1995.
[15]
R. A. Kelsey and J. A. Rees. A tractable Scheme implementation. Lisp and Symbolic Computation, 7(4):315-335, 1995.
[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]
J. Lewis, M. Shields, E. Meijer, and J. Launchbury. Implicit parameters: Dynamic scoping with static types. In Proceedings of the 27th Annual ACM SICPLAN-SICACT Symposium on Principles of Programming Languages, Boston, Massachusetts, pages 108-118, Jan 2000.
[18]
R. Milner and M. Tofte. Co-induction in relational semantics. Theoretical Computer Science, 87:209-220. 1991.
[19]
J. C. Mitchell and G. D. Plotkin. Ahstact types have existantial type. In ACM Transcations on Programmin Languages and Systems. volume 10. pages 470-502, July 1988.
[20]
L. Moreau. A Syntactic Theory of Dynamic Binding. Higher-Order and Symbolic Computation, 11(3):233-279. Dec. 1998.
[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]
F. Nielson and H. R. Nielson. Infinitary control flow analysis: a collecting semantics for closure analysis. In Proc. POPL 'p7, pages 332-345. ACM Press, 1997.
[23]
G. D. Plotkin. A structural approach to operational semantics. Technical Report DAIMI FN19. Computer Science Department, Aarhus University, Aarhus, Denmark. Sept. 1981.
[24]
C. Queinnec. Lisp in Small Pieces. Cambridge University Press, 1996.
[25]
K. Raeburn. Guile-based Emacs. http: //www.mit.edu/raeburn/guilemacs/, July 1999.
[26]
M. Serrano and M. Feeley. Storage use analysis and its applications. In Proceedings of the lfst International Conference on Functional Programming, page 12, Philadelphia, June 1996.
[27]
0. Shivers. Control-Flow Analysis of Higher-Order Languages. PhD thesis, CarnegieMellon University, May 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]
A. K. Wright and M. Felleisen. A syntactic approach to type soundness. Technical Report 91160, Rice University, Apr. 1991. Final version in Information and Computation 115 (1), 1994, 38-94.
[31]
A. K. Wright and M. Felleisen. A syntactic approach to type soundness. Information and Computation, 1i5(l):38-94, 1994. Preliminary version in Rice TR 91-160.
[32]
A. K. Wright arid S. Jagannathan. Polymorphic splitting: an effective polyvariant flow analysis. ACM Transactions on Programming Languages and Systems, 20(l):166-207, Jan. 1998.
Index Terms
- Down with Emacs Lisp: dynamic scope analysis
Recommendations
Evolution of Emacs Lisp
While Emacs proponents largely agree that it is the world’s greatest text editor, it is almost as much a Lisp machine disguised as an editor. Indeed, one of its chief appeals is that it is programmable via its own programming language. Emacs Lisp is a ...
Down with Emacs Lisp: dynamic scope analysis
ICFP '01: Proceedings of the sixth ACM SIGPLAN international conference on Functional programmingIt 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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2001 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 October 2001
Published in SIGPLAN Volume 36, Issue 10
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 531Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in