git » jacl.git » commit 73f9497

diff --git a/paper/jacl-els-2020.bib b/paper/jacl-els-2020.bib
index 8768202..227887d 100644
--- a/paper/jacl-els-2020.bib
+++ b/paper/jacl-els-2020.bib
@@ -22,6 +22,14 @@
  note = "[Online; accessed February 12, 2020]"
 }
 
+@misc{wiki:TreeShaking,
+ author = "{Wikipedia contributors}",
+ title = "Tree shaking --- {W}ikipedia{,} The Free Encyclopedia",
+ year = "2020",
+ url = "https://en.wikipedia.org/w/index.php?title=Tree_shaking&oldid=908332079",
+ note = "[Online; accessed February 22, 2020]"
+}
+
 @online{Cannon07,
  author={Howard I. Cannon},
  year=2007,
@@ -201,6 +209,14 @@
  lastaccessed="February 19, 2020",
 }
 
+@online{EventLoop,
+ author={{Mozilla, Inc.}},
+ year={2020},
+ title="Concurrency model and the event loop",
+ url="https://developer.mozilla.org/en-US/docs/Web/JavaScript/EventLoop",
+ lastaccessed="February 22, 2020",
+}
+
 @book{Bolin10,
  author = {Michael Bolin},
  title = {Closure: The Definitive Guide: Google Tools to Add Power to Your JavaScript},
diff --git a/paper/jacl-els-2020.tex b/paper/jacl-els-2020.tex
index 1db40ac..fd9485c 100644
--- a/paper/jacl-els-2020.tex
+++ b/paper/jacl-els-2020.tex
@@ -88,22 +88,20 @@ Lisp. The primary goal of the JACL project is to ease SPA development
 by applying Common Lisp --- a proven\cite{Cannon07,Garnet90,Action}
 substrate for UI innovation --- to the difficult challenges now faced
 by developers. The JACL language is envisioned as the means to that
-goal, and to have at least the following ancillary affordances:
+goal.
 
-\begin{itemize}
-  \item Compelling interactive development experience.
-  \item Ability to load code from the host filesystem during
-    development.
-  \item Fluent interoperation with external JavaScript libraries.
-  \item Ability to produce fast and small deliverable executables.
-\end{itemize}
+Most popular, contemporary compile-to-JavaScript languages are
+oriented around the affordances of static type checking; JACL, as a
+Lisp, is not. Compared to similar languages that \emph{are} Lisps,
+JACL differentiates itself in two particular ways: with its approach
+to the REPL, and with its compilation techniques.
 
-First, similar efforts will be surveyed. Then, novel aspects of JACL's
-design and implementation with respect to those efforts will be
-introduced. Finally, details about the current state of JACL's
-implementation, and plans for future work, will be elaborated upon.
+In this paper, similar efforts will first be surveyed. Then, novel
+aspects of JACL's design and implementation with respect to those
+efforts will be introduced. Finally, conclusions will be drawn and
+future work will be outlined.
 
-\section{Previous Work}
+\section{Related Work}
 
 Many Lisps exist that either compile to JavaScript or are interpreted
 by a JavaScript program. Here, only Lisps that have either
@@ -222,10 +220,6 @@ Lisp to JavaScript compiler to perform, because they are exactly the
 kind that a JavaScript optimizer could not later perform, provided
 only JavaScript code.
 
-On the other hand, the arithmetic expression code-size optimizations
-performed by the second, code-generation stage of the JSCL compiler
-could effectively be performed by a JavaScript optimizer.
-
 \subsection{ClojureScript}
 
 A discussion of industrial Lisp technology in the SPA setting would be
@@ -268,9 +262,15 @@ work in pursuit of this balance.
 The basis for interactive development in Lisp is undeniably the REPL,
 but as JSCL's ``pre-reader'' demonstrates, even the direct approach to
 this simple mechanism is hampered by JavaScript's asynchronous model
-of input. To resolve this difficulty, JACL's reader facility is
-completely asynchronous. Conceptually, it is the JSCL REPL
-``pre-reader'' taken to its inevitable conclusion.
+of input\cite{EventLoop}. Traditionally, Lisp readers are implemented
+in environments with a blocking function for obtaining input, like
+\texttt{getc(1)} on Unix. The blocking nature of input consumption
+allows the reader to consume nested input recursively, using the call
+stack to accumulate structures. In JavaScript, input arrives
+asynchronously, and only when the call stack is empty. To mitigate
+this difficulty, JACL's reader facility is completely
+asynchronous. Conceptually, it is the JSCL REPL ``pre-reader'' taken
+to its inevitable conclusion.
 
 JACL's reader is implemented as a JavaScript class,
 \texttt{Reader}. \texttt{Reader} instances are parameterized by an
@@ -382,12 +382,12 @@ following:
 As a simple command-line application with a textual interface,
 \texttt{jacl-repl} can be run in various contexts. For example, it
 could be run within an Emacs ``inferior-lisp'' buffer, and then Lisp
-forms could sent from other Emacs buffers for evaluation in the
-REPL. It could be also be run as part of a build process that pipes
-Lisp sources over the WebSocket for batch compilation. It is
-anticipated that additional host-side tools that depend on
-\texttt{jacl-client} will be necessary in the future to support
-loading source files in dependency order.
+forms could be sent from other Emacs buffers for evaluation in the
+REPL. It could also be run as part of a build process that pipes Lisp
+sources over the WebSocket for batch compilation. It is anticipated
+that additional host-side tools that depend on \texttt{jacl-client}
+will be necessary in the future to support loading source files in
+dependency order.
 
 Unlike the pre-readers of SLip and JSCL, \texttt{jacl-client} is
 completely ignorant of Lisp syntax. \texttt{jacl-client} merely
@@ -409,15 +409,12 @@ produce a representation that can be read back in.
 
 Unlike JSCL, the JACL compiler is organized to facilitate high-level
 optimizations such as those that could support efficient compilation
-of \texttt{TAGBODY} and other Common Lisp operators. Low-level
-optimizations are deferred to users, who may optionally run
-deliverables produced by JACL through third-party JavaScript
-optimizers such as Google Closure Compiler \cite{Bolin10}.
+of \texttt{TAGBODY} and other fundamental Common Lisp operators.
 
-The compiler has one analysis pass that results in an AST. The AST is
-then converted to JavaScript strings by a code generation step. AST
-nodes are represented by generic JavaScript objects with at least the
-following keys:
+The first compiler pass expands macros and produces an AST. The second
+compiler pass performs optimizations and produces a new AST. The final
+pass produces JavaScript code. AST nodes are represented by generic
+JavaScript objects with at least the following keys:
 
 \begin{itemize}
   \item \texttt{op}: The node's name, as a JavaScript string.
@@ -501,7 +498,7 @@ variable \texttt{X} 10 times:
   (tagbody
     start
     (when (zerop x) (go end))
-    (decf x)
+    (setq x (1- x))
     (go start)
     end))
 \end{verbatim}
@@ -528,7 +525,7 @@ LOOP: while (true) {
     switch(label) {
       case 0:
         if (X === 0) throw new Jump(id, 1);
-        X--;
+        X = X-1;
         throw new Jump(id, 0);
       case 1:
       default:
@@ -544,31 +541,44 @@ LOOP: while (true) {
 }
 \end{verbatim}
 
-The mechanism is ingenious and general. \texttt{GO} tags became
-\texttt{switch} labels, and jumps are performed by throwing an
-instance of \texttt{Jump} containing the destination label.
-
-Unfortunately, every jump requires a JavaScript exception be thrown,
-severely penalizing iteration constructs built on
-\texttt{TAGBODY}. Fortunately, a slight improvement in the compilation
-strategy can yield a tremendous performance benefit. The improvement
-follows from the observation that any \emph{local jump} --- such as
-that from a \texttt{GO} to its relevant enclosing \texttt{TAGBODY},
-with no lexically-intervening \texttt{LAMBDA} forms --- may rely on
-JavaScript's \texttt{continue}\cite{MozLabel} operator with a label
-argument for control transfer, instead of on throwing an exception.
-
-Additionally, \texttt{TAGBODY} forms that are determined statically to
-contain \emph{only} local jumps need not generate a \texttt{try/catch}
-block, saving on generated code size.
-
-The following is an example of what the generated code would look like
-after applying local jump optimization. Cursory benchmarks run on
-Google Chrome \ref{appendix:benchmarks} show it runs several orders of
-magnitude faster than the previous, unoptimized version, and is nearly
-as fast as the JavaScript statement \texttt{while(X--)}:
-
-\newpage
+The mechanism is ingenious and general, as it results in correct
+behavior of both \emph{local} (to a lexically-enclosing
+\texttt{TAGBODY} tag) and \emph{non-local} (to a dynamically-enclosing
+\texttt{TAGBODY} tag) jumps. \texttt{GO} tags became \texttt{switch}
+labels, and jumps are performed by throwing an instance of
+\texttt{Jump} containing the destination label.
+
+Unfortunately, in this scheme, every jump requires a JavaScript
+exception be thrown, severely penalizing \texttt{TAGBODY} as
+previously discussed. Fortunately, a straightforward \emph{local jump
+  optimization} can be applied that yields a tremendous performance
+benefit. Local jump optimization is a known
+technique\cite{SICLTagbody}, but JACL is the first Lisp targeting
+JavaScript to apply it.
+
+In order to perform this optimization, the JACL compiler first
+identifies local \texttt{GO}s in its analysis pass. These are
+\texttt{GO} nodes with no intervening \texttt{LAMBDA}
+nodes\footnote{Note that \texttt{LAMBDA} doesn't necessarily preclude
+  local jump optimization if the \texttt{LAMBDA} is inlined, but JACL
+  currently does not inline functions.} between them and their
+respective, lexically-enclosing \texttt{TAGBODY}s. Then,
+\texttt{TAGBODY}s are identified that consist of only local
+\texttt{GO}s.
+
+JavaScript generated for local \texttt{GO}s does not throw an
+exception, but instead leverages the labeled form of JavaScript's
+\texttt{continue}\cite{MozLabel} statement to transfer control
+appropriately. JavaScript generated for \texttt{TAGBODY}s that have
+been determined to consist only of local jumps omits the
+\texttt{try/catch} block, saving on generated code size.
+
+The following code is similar\footnote{Once more, actual compiler
+  output has been significantly modified and reformatted for brevity.}
+to that generated by the JACL compiler. Cursory benchmarks
+\ref{appendix:benchmarks} show JACL's code runs several orders of
+magnitude faster than JSCL's, and that JACL's code is almost as fast
+as the JavaScript statement \texttt{while(X--)}:
 
 \begin{verbatim}
 var X = 10;
@@ -580,7 +590,7 @@ LOOP: while (true) {
         label = 1;
         continue LOOP;
       }
-      X--;
+      X = X - 1;
       label = 0;
       continue LOOP;
     case 1:
@@ -590,105 +600,57 @@ LOOP: while (true) {
 }
 \end{verbatim}
 
-JACL's AST will facilitate the identification of usages of
-\texttt{TAGBODY} that are amenable to local jump optimization, and the
-transformation of such code into a dramatically faster
-equivalent. Local \texttt{GO} optimization is a known technique
-\cite{SICLTagbody}, but its implementation using JavaScript's
-\texttt{continue} is not.
-
-\subsection{Delivery}
-
-All of the JACL features described so far are in the very early stages
-of implementation, but JACL's delivery capabilities have yet to be
-implemented at all.
-
-Fortunately, since JACL development is image-based, JACL should
-support the traditional approach of specifying a Lisp function
-entrypoint and dumping the Lisp image to native (JavaScript)
-code. SBCL's \texttt{SAVE-LISP-AND-DIE}\cite{SBCLManual} and
-LispWork's \texttt{DELIVER}\cite{LispWorksDeliver} functions are two
-examples of this in other implementations.
-
-It is imagined that JACL's \texttt{DELIVER} function will be called in
-a REPL at development time by a developer, or by an automated build
-script. When the function is called, a JavaScript deliverable will be
-produced, and the Web browser will either prompt the user to accept a
-download, or the JavaScript code will be written to standard output by
-\texttt{jacl-client}.
-
-JavaScript whole-program optimization tools such as Babel or Google
-Closure Compiler may then be optionally applied to the
-executable. Such tools perform sophisticated optimizations such as
-dead-code elimination, loop invariant code motion, and constant
-folding.
-
-It is anticipated that one important high-level optimization must be
-performed in order for dumped images to be amenable to further
-optimization by JavaScript tools: global symbol and function
-references must be converted to static references. In order to perform
-this optimization, JACL will need to retain the ASTs associated with
-global definitions, so that statically-linked code for these
-definitions can be generated at delivery time. Alternatively,
-statically-linked code could be created automatically whenever
-dynamically-linked code, and stored as an implementation-specific
-attribute of the function object.
-
-\section{Conclusions and Future Work}
+\section{Conclusion}
 
 JACL, a new Common Lisp created to ease SPA development, was
-introduced. Four novel aspects of JACL were described with respect to
-other, comparable Lisp implementations:
-
-\begin{enumerate}
-  \item An asynchronous reader that doesn't necessitate a pre-reader
-    and is suitable for embedded use.
-  \item An analyzing compiler and AST to support high-level
-    optimizations, such as those necessary for a high-performance
-    \texttt{TAGBODY} implementation.
-  \item \texttt{jacl-client}, the Chrome DevTools-based REPL that
-    complements the asynchronous reader to provide a command-line REPL
-    facility on the host.
-  \item The tentative delivery facility design, which will support the
-    creation of competitively small and fast application artifacts.
-\end{enumerate}
-
-Most of Common Lisp that JACL will be capable of supporting remains
-unimplemented. However, JACL is nearly in a state in which it can be
-used for application development.
-
-The most immediate body of remaining work is population of the
-\texttt{COMMON-LISP} package, towards the end goal of supporting MIT
-\texttt{LOOP}. Such support would imply comprehensive support for many
-fundamental Lisp operators.
-
-A longer term goal is support for the Common Lisp Object System
-(CLOS). Key historical Lisp innovations were achieved with CLOS or one
-of its predecessors \cite{Cannon07}, and so its inclusion is a high
-priority.
-
-Many other design and implementation tasks remain, such as support for
+introduced. JACL is designed as an efficient, practical tool, with the
+needs of industrial SPA developers in mind. JACL integrates tightly
+with the Web browser platform and interoperates easily with
+JavaScript. Compared to other browser-based Lisps, JACL places a
+higher emphasis on the value of the REPL, and introduces new
+techniques for integrating the REPL into the development workflow.
+
+\section{Future Work}
+
+In order to be practical for application development, JACL must
+support the creation of standalone executables. In JACL's case, these
+would be single JavaScript files that may be included in an HTML page
+and are executed on page load. Fortunately, since JACL development is
+image-based, JACL should support the traditional approach of
+specifying a Lisp function entrypoint and dumping the Lisp image to
+native (JavaScript) code. SBCL's
+\texttt{SAVE-LISP-AND-DIE}\cite{SBCLManual} and LispWork's
+\texttt{DELIVER}\cite{LispWorksDeliver} functions are two examples of
+this in other implementations.
+
+JACL should be able to perform rudimentary optimizations such as
+global function and variable tree shaking\cite{wiki:TreeShaking} in
+order to reduce the size of generated executables. In addition, JACL
+should make dynamic function and variable references in executables
+static, so that third party tools like Google Closure
+Compiler\cite{Bolin10} may optionally be used to perform additional
+optimization.
+
+Other than the ability to produce optimized standalone executables,
+many other design and implementation tasks remain, such as support for
 special variables in lambda lists, \texttt{EVAL-WHEN}, macro lambda
-lists, \texttt{DECLARE} et al, various other data types, compiler
-macros, etc. The list of tasks is enormous, but it is anticipated that
-these features can be implemented over time, in the order demanded by
-application development.
-
-Bootstrapping is a desirable milestone, but since the fact that JACL
-is not currently bootstrapped doesn't preclude its use for application
-development, bootstrapping is not a high priority.
+lists, \texttt{DECLARE} et al, CLOS, various other data types,
+compiler macros, etc. The list of tasks is enormous, but it is
+anticipated that these features can be implemented over time, in the
+order demanded by application development.
 
 \section{Acknowledgments}
 
-The author wishes to thank Micha Niskin, Bart Botta, and Kevin Lynagh
-for invaluable feedback on early versions of this paper.
+The author wishes to thank Micha Niskin, Bart Botta, Kevin Lynagh,
+Lionel Henry, and Andy Keep for invaluable feedback on early versions
+of this paper.
 
 The author wishes to express particular thanks to Robert Strandh not
-only for his feedback, but also for the encouragement and guidance he
-provided throughout the writing process.
+only for his feedback, but also for his guidance on the writing
+process.
 
 Finally, the author wishes to express special gratitude to his
-beautiful wife, Sandra Dipert, for her skillful editing.
+beautiful wife, Sandra Dipert, for her encouragement and support.
 
 \bibliographystyle{ACM-Reference-Format}
 \bibliography{jacl-els-2020}
@@ -716,7 +678,7 @@ function tagbody_unoptimized(X) {
       switch(label) {
         case 0:
           if (X === 0) throw new Jump(id, 1);
-          X--;
+          X = X - 1;
           throw new Jump(id, 0);
         case 1:
         default:
@@ -742,7 +704,7 @@ function tagbody_optimized(X) {
           label = 1;
           continue LOOP;
         }
-        X--;
+        X = X - 1;
         label = 0;
         continue LOOP;
       case 1:
@@ -759,17 +721,17 @@ function baseline_js(X) {
 var start = performance.now();
 for (var i = 0; i < 1e6; i++) tagbody_unoptimized(10);
 console.log("tagbody_unoptimized", performance.now() - start);
-// tagbody_unoptimized 61572.78000000224
+// tagbody_unoptimized 58994.43500000052
 
 var start = performance.now();
 for (var i = 0; i < 1e6; i++) tagbody_optimized(10);
 console.log("tagbody_optimized", performance.now() - start);
-// tagbody_optimized 26.714999999967404
+// tagbody_optimized 23.61499999812804
 
 var start = performance.now();
 for (var i = 0; i < 1e6; i++) baseline_js(10);
 console.log("baseline_js", performance.now() - start);
-// baseline_js 21.240000001853332
+// baseline_js 15.055000003427267
 \end{verbatim}
 
 \end{document}