| author | Alan Dipert
<alan@dipert.org> 2020-02-20 20:09:34 UTC |
| committer | Alan Dipert
<alan@dipert.org> 2020-02-20 20:09:34 UTC |
| parent | fe6f3d0dfd0cf288c83df31eb813db0831724c35 |
| paper/jacl-els-2020.bib | +15 | -7 |
| paper/jacl-els-2020.tex | +286 | -179 |
diff --git a/paper/jacl-els-2020.bib b/paper/jacl-els-2020.bib index 1afaf8d..8e22061 100644 --- a/paper/jacl-els-2020.bib +++ b/paper/jacl-els-2020.bib @@ -185,11 +185,19 @@ date = {2019-02-07}, } -@online{Rees84, - author={Jonathan A. Rees}, - year={1984}, - title="Thread: Using EQ instead of EQL to compare catch tags", - url="https://cl-su-ai.cddddr.org/msg00552.html", - lastaccessed="February 12, 2020", - note = "Discussion on CL design mailing list regarding TAGBODY implementation" +@online{MozLabel, + author={{Mozilla, Inc.}}, + year={2020}, + title="label - JavaScript | MDN", + url="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/label", + lastaccessed="February 19, 2020", +} + +@book{Bolin10, + author = {Michael Bolin}, + title = {Closure: The Definitive Guide: Google Tools to Add Power to Your JavaScript}, + year = {2010}, + isbn = {978-1449381875}, + publisher = {O'Reilly Media}, + address = {Sebastopol, CA, USA}, } \ No newline at end of file diff --git a/paper/jacl-els-2020.tex b/paper/jacl-els-2020.tex index c552069..041db8a 100644 --- a/paper/jacl-els-2020.tex +++ b/paper/jacl-els-2020.tex @@ -1,3 +1,4 @@ + \documentclass[sigconf]{acmart} \usepackage{booktabs} @@ -25,6 +26,13 @@ \email{alan@dipert.org} \begin{abstract} + This paper introduces JavaScript-Assisted Common Lisp (JACL), a new + Web-browser based implementation of an extended subset of Common + Lisp. JACL --- which is under active development and approaching + utility --- is an effort to facilitate the use of Common Lisp in + overcoming the challenges of Single-page Web Application (SPA) + development. + Single-page Web Applications (SPAs) are a popular technique for implementing responsive Web-based User Interfaces (UIs). Google's GMail, introduced in 2007, was one of the first well-known @@ -36,12 +44,6 @@ limitations imposed by the browser's security model, the asynchronous nature of I/O in JavaScript, and the difficulties inherent in managing large code bases. - - This paper introduces JavaScript-Assisted Common Lisp (JACL), a new - Web-browser based implementation of an extended subset of Common - Lisp. JACL --- which is incomplete and under active development --- - is an effort to facilitate the use of Common Lisp in overcoming the - challenges of SPA development. \end{abstract} \begin{CCSXML} @@ -56,19 +58,13 @@ <concept_desc>Software and its engineering~Runtime environments</concept_desc> <concept_significance>500</concept_significance> </concept> - <concept> - <concept_id>10003120.10003121.10003124.10010868</concept_id> - <concept_desc>Human-centered computing~Web-based interaction</concept_desc> - <concept_significance>300</concept_significance> - </concept> </ccs2012> \end{CCSXML} \ccsdesc[500]{Software and its engineering~Dynamic compilers} \ccsdesc[500]{Software and its engineering~Runtime environments} -\ccsdesc[300]{Human-centered computing~Web-based interaction} -\keywords{Common Lisp, web applications} +\keywords{Common Lisp, JavaScript, web applications} \maketitle @@ -78,29 +74,21 @@ The demand for SPAs in the past decade has only grown, and users and stakeholders continually expect larger and more sophisticated applications. Unfortunately, large-scale development on the Web browser platform presents a particular set of challenges that are not -easily overcome. - -Developers have responded to these challenges by creating a widening -variety of special-purpose programming languages that compile to -JavaScript \cite{Somasegar12,Czaplicki12,wiki:ReasonML}. Each new -language promotes one or more paradigms, application architectures, or +easily overcome. Developers have responded to these challenges by +creating a widening variety of special-purpose programming languages +that compile to JavaScript +\cite{Somasegar12,Czaplicki12,wiki:ReasonML}. Each new language +promotes one or more paradigms, application architectures, or development workflows, and claim some advantage relative to the status quo. This paper presents one new such language, JavaScript-Assisted Common -Lisp (JACL), an implementation of an extended subset of Common Lisp. - -Unlike contemporary languages, Lisp is closely associated with a -history of innovation and success in the field of large-scale UI -development that predates the existence of the Web -\cite{Cannon07,Garnet90}. The design of Common Lisp is informed by the -lessons learned in pursuit of those and other innovations. - -The primary goal of the JACL project is to ease SPA development by -applying Common Lisp --- a proven substrate for UI development success ---- 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: +Lisp (JACL), an implementation of an extended subset of Common +Lisp. The primary goal of the JACL project is to ease SPA development +by applying Common Lisp --- a proven\cite{Cannon07,Garnet90} substrate +for UI development success --- 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: \begin{itemize} \item Compelling interactive development experience. @@ -110,36 +98,30 @@ the following ancillary affordances: \item Ability to produce fast and small deliverable executables. \end{itemize} -First, previous, similar efforts to facilitate the use of Lisp on the -Web browser platform will be surveyed. Then, novel aspects of JACL's -design and implementation with respect to those previous works wil be -introduced. Finally, the current state of JACL's implementation, and -plans for future work, will be elaborated upon. +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. \section{Previous Work} Many Lisps exist that either compile to JavaScript or are interpreted -by a JavaScript program. In order to focus my comparison, I will -survey only Lisps that have either demonstrated industrial utility or -that implement a significant subset of Common Lisp. +by a JavaScript program. Here, only Lisps that have either +demonstrated industrial utility or that implement a significant subset +of Common Lisp are featured. \subsection{Parenscript} Released in 2005\cite{Baringer05}, Parenscript\footnote{Also known as ParenScript.}\cite{ParenScriptManual} was the first Common Lisp -compiler to target JavaScript. - -Parenscript is not bootstrapped and its compiler is not written in -JavaScript, and so it relies on a hosting Common Lisp system for -compilation. - -Only JavaScript types are available to Parenscript programs at -runtime, and so Parenscript is more of a syntax frontend for -JavaScript than it is an interactive Lisp system. - -While Parenscript is not positioned to facilitate large-scale SPA -development, it remains popular way for adding dynamic -JavaScript-behaviors to static Web sites. +compiler to target JavaScript. Parenscript is not bootstrapped and its +compiler is not written in JavaScript, and so it relies on a hosting +Common Lisp system for compilation. Only JavaScript types are +available to Parenscript programs at runtime, and so Parenscript is +more of a syntax frontend for JavaScript than it is an interactive +Lisp system. While Parenscript is not positioned to facilitate +large-scale SPA development, it remains popular way to add dynamic +JavaScript-based behaviors to static Web sites. \subsection{SLip} @@ -149,21 +131,20 @@ intentionally diverges\cite{SLipVsCl} from Common Lisp in certain ways. It offers a stunning array of powerful features including a self-hosting compiler, a full set of control operators, JavaScript Foreign-Function Interface (FFI), tail-call optimization, green -threads, and perhaps most impressively, a resident Emacs clone. - -SLip is based originally on the compiler and bytecode interpreter -presented in Chapter 23 of \emph{Paradigms of Artificial Intelligence - Programming: Case studies in Common Lisp}\cite{Norvig92}. +threads, and perhaps most impressively, a resident Emacs clone, +\emph{Ymacs}. SLip is based originally on the compiler and bytecode +interpreter presented in Chapter 23 of \emph{Paradigms of Artificial + Intelligence Programming: Case studies in Common + Lisp}\cite{Norvig92}. Lisp files may be batch-compiled to FASLs. FASLs represent code as JavaScript code instead of as Lisp data. The browser is able to load FASLs faster than SLip code because the browser's native JavaScript -parser is much faster than SLip's reader. - -Despite the ability to produce FASLs, the interpreted nature of SLip -precludes the system from producing competitively fast or small -application deliverables. Consequently, SLip does not satisfy the JACL -project goal of facilitating large-scale industrial SPA development. +parser is much faster than SLip's reader. Despite the ability to +produce FASLs, the interpreted nature of SLip precludes the system +from producing competitively fast or small application +deliverables. Consequently, SLip does not satisfy the JACL project +goal of facilitating large-scale industrial SPA development. \subsection{JSCL} @@ -172,12 +153,10 @@ aligned most closely with the JACL project goal. Unlike Parenscript, JSCL is a genuine Lisp system. And unlike SLip, JSCL compiles directly to JavaScript instead of to an interpreted bytecode. It is self-hosting, includes the major control operators, and integrates -tightly with JavaScript. - -JSCL includes a reader, compiler, and printer, and evaluation is -performed by JavaScript's \texttt{eval()} function. Between these, a -Read Eval Print Loop (REPL) is possible, and the JSCL distribution -includes a reference implementation of one. +tightly with JavaScript. JSCL includes a reader, compiler, and +printer, and evaluation is performed by JavaScript's \texttt{eval()} +function. Between these, a Read Eval Print Loop (REPL) is possible, +and the JSCL distribution includes an implementation of one. \subsubsection{Synchronous reader} @@ -186,28 +165,24 @@ from which characters may be synchronously consumed are not an abstraction supported by JavaScript in Web browsers. With a few obscure exceptions\footnote{\texttt{window.prompt()} and \texttt{window.confirm()}}, JavaScript programs may only receive -input asynchronously. - -An error is signaled if the end of a string-backed input stream is -encountered before the reader has finished reading a datum. +input asynchronously. An error is signaled if the end of a +string-backed input stream is encountered before the reader has +finished reading a datum. Because input strings may not contain partial data, the REPL necessitates a ``pre''-reader process that accumulates characters in response to asynchronous input events, and invokes the reader only -once a complete form --- as a string --- has been accumulated. - -Such a pre-reader can be found in the JSCL REPL implementation. It -handles standard Lisp atoms and list syntax, but has the potential to -be stymied by extended syntax, such as that added by reader macros. As +once a complete form --- as a string --- has been accumulated. Such a +pre-reader can be found in the JSCL REPL implementation. It handles +standard Lisp atoms and list syntax, but has the potential to be +stymied by extended syntax, such as that added by reader macros. As such, the pre-reader is a separate, degenerate reader that limits what's capable of being read by the underlying, full-featured synchronous reader. -Incidentally, SLip's reader is also synchronous, and its Emacs clone, -Ymacs, also includes a pre-reader as part of its Lisp interaction -mode. - -JSCL and SLip demonstrate that when the underlying reader facility is +SLip's reader is also synchronous, and its Emacs clone, Ymacs, also +includes a pre-reader as part of its Lisp interaction mode. JSCL and +SLip both demonstrate that when the underlying reader facility is synchronous, a REPL cannot effectively be made available at run-time because of the asynchrony of input events in JavaScript. In the best case, the reader is only partially available through a pre-reader that @@ -218,8 +193,8 @@ accumulates characters asynchronously. JSCL compilation involves the following two high-level stages: \begin{itemize} - \item Conversion from Lisp to JavaScript AST represented as - S-expressions. + \item Conversion from Lisp to a JavaScript Abstract Syntax Tree + (AST) represented as S-expressions. \item Conversion from JavaScript AST to JavaScript strings. \end{itemize} @@ -233,30 +208,26 @@ descends into Lisp code and produces JavaScript AST. Code for \texttt{TAGBODY} is generated in the first stage, and the generated code is much slower than comparable JavaScript code for -looping. - -Only the general, dynamic case of \texttt{TAGBODY} is +looping. Only the general, dynamic case of \texttt{TAGBODY} is implemented. Every control transfer initiated by \texttt{GO} results in a JavaScript exception being thrown, which is an expensive -operation. - -Since many Common Lisp operators have \emph{implicit tagbodies}, and -since most other iteration operators are expressed in terms of -\texttt{TAGBODY}, this performance problem pervades the JSCL system. - -More efficient ways of implementing \texttt{TAGBODY} are -known\cite{Rees84}, but the implementation of optimizations is not -facilitated by JSCL. Support for subsequent optimization passes over -some high-level intermediate representation (IR) is not implemented. - -High-level optimizations are important for a Lisp to JavaScript -compiler to perform, because they are exactly the kind that a -JavaScript optimizer could not later perform, provided only JavaScript -code. +operation. Since many Common Lisp operators have \emph{implicit + tagbodies}, and since most other iteration operators are expressed +in terms of \texttt{TAGBODY}, this performance problem pervades the +JSCL system. + +More efficient ways of implementing \texttt{TAGBODY} are not hard to +imagine, but the JSCL compiler does not amene itself to the +implementation of this or other high-level optimizations, as JSCL +lacks a sufficiently expressive intermediate representation +(IR). High-level, semantic optimizations and transformations are +important for a 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 could easily be -performed by a JavaScript optimizer. +performed by the second, code-generation stage of the JSCL compiler +could easily be performed by a JavaScript optimizer. \subsection{ClojureScript} @@ -277,10 +248,10 @@ deliverables amenable to aggressive optimization by the Google Closure Compiler. In this respect, ClojureScript aligns closely with the JACL project -goal of competitive application performance. In fact, the author's -experience with, and admiration for, ClojureScript is the reason the -ability to produce high-performance deliverables is considered a -crucial capability of JACL. +goal of competitive application performance. In fact, experience with, +and admiration for, ClojureScript is the reason the ability to produce +high-performance deliverables is considered a crucial capability of +JACL. Other than the fact that JACL is a Common Lisp and ClojureScript is not, the biggest difference between the two is JACL's promotion of a @@ -293,21 +264,18 @@ host. From a design perspective, JACL is an effort to balance the requirements of an interactive and practical Lisp development -environment with the constraints imposed by the Web browser platform. - -JACL proposes several innovations with respect to previous work in -pursuit of this balance. +environment with the constraints imposed by the Web browser +platform. JACL proposes several innovations with respect to previous +work in pursuit of this balance. \subsection{Asynchronous reader} The basis for interactive development in Lisp is undeniably the REPL, -but as JSCL's ``pre-reader'' conundrum 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. +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. JACL's reader is implemented as a JavaScript class, \texttt{Reader}. \texttt{Reader} instances are parameterized by an @@ -320,12 +288,12 @@ its subscribers of the availability of the datum. The JACL reader implementation makes extensive use of modern JavaScript features to support asynchronous programming including Promises, iterators, async functions, async iterators, and the -\texttt{await} keyword. - -These features simplify the JACL implementation and aid its -performance \cite{V8async}. It is hoped that JACL will eventually be -written in itself, and that these features will be accessible from -Lisp. +\texttt{await} keyword. These features simplify the JACL +implementation and aid its performance \cite{V8async}. It is hoped +that JACL will eventually be written in itself, and that these +features will be accessible from Lisp, perhaps as a set of +implementation-dependent \emph{declaration specifiers} available in +\texttt{DECLARE} expressions. The following example demonstrates, in JavaScript, the mechanism by which the JACL reader consumes characters and produces Lisp objects. A @@ -364,8 +332,7 @@ function that returns such a Promise. Once \texttt{rdr} has completed a form --- in this case, the number 123, after about 4000 milliseconds have elapsed --- execution -continues, and the number \texttt{123} is printed to the JavaScript -console. +continues, and \texttt{123} is printed to the JavaScript console. The ``read'' portion of JACL's REPL is satisfied by first establishing \texttt{BufferedStream} and \texttt{Reader} objects. Then, in an @@ -382,10 +349,9 @@ applications. Because of the platform and implementation-dependent nature of JACL's reader, JACL does not support Common Lisp's streams abstraction, nor -its standard \texttt{READ} and \texttt{READ-FROM-STRING} functions. - -Additionally, standard interfaces for extending the reader, such as -the \texttt{SET-MACRO-CHARACTER} function, are not directly +its standard \texttt{READ} and \texttt{READ-FROM-STRING} +functions. Standard interfaces for extending the reader, such as the +\texttt{SET-MACRO-CHARACTER} function, are not directly supported. However, the JACL reader does provide an implementation-specific way to define reader macros. @@ -400,25 +366,20 @@ interested people, from the comfort of their Web browsers. It's also a useful debugging feature of a deployed application. However, most developers already have a preferred text editor and a -refined REPL interaction workflow, and so it's not within the JACL -project scope to build a resident text editor or IDE in the style of -SLip. Even if a resident editor was a goal, the file system access -restrictions imposed by the browser would present significant -challenges. +REPL interaction workflow, and so it's not within the JACL project +scope to build a resident IDE in the style of SLip. Even if a resident +IDE was a goal, the file system access restrictions imposed by the +browser would present significant challenges. Instead, JACL offers an alternative development REPL approach that -requires minimal host tooling: the DevTools-based REPL. - -For each tab, Google Chrome is capable of hosting a WebSocket-based -debug server that implements the DevTools Protocol \cite{GDevTools}. - -DevTools Protocol clients may then connect to the server and interact -with the tab's environment, such as by evaluating arbitrary JavaScript -within the context of the tab. - -JACL leverages the DevTools Protocol to deliver a command-line REPL -client that may be run on the developer's host machine. The workflow -is the following: +requires minimal host tooling: the DevTools-based REPL. Google Chrome +is capable of hosting a WebSocket-based debug server that implements +the DevTools Protocol \cite{GDevTools}. DevTools Protocol clients may +then connect to the server and interact with open tabs, such as by +evaluating arbitrary JavaScript within the context of the tab. JACL +leverages the DevTools Protocol to deliver a command-line REPL client +that may be run on the developer's host machine. The workflow is the +following: \begin{enumerate} \item Run Google Chrome from the shell with the \linebreak @@ -432,10 +393,12 @@ is the 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. +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. An advantage of the reader approach taken by JACL with respect to the implementation of \texttt{jacl-client} is that the REPL client is @@ -445,31 +408,30 @@ Lisp system, and displays characters output from Lisp. While \texttt{jacl-client} presents a synchronous input/output interface, it is actually the frontend for bidirectional asynchronous data transfer. -\texttt{jacl-repl} is currently an R\cite{Rstats} script requiring an -R installation and installation of the -\texttt{chromote}\cite{Rchromote} package. A standalone binary -executable is imagined in the future. - -JACL has yet to define a printer for its native types, or an -extensible print protocol. Currently, object string representations -are obtained by calling the generic JavaScript \texttt{toString()} -method, which doesn't always produce a representation that can be read -back in. +There are various obvious way the JACL REPL experience could be +improved. For example, \texttt{jacl-repl} is currently an +R\cite{Rstats} script requiring an R installation and installation of +the \texttt{chromote}\cite{Rchromote} package. A standalone binary +executable is imagined in the future in order to make it easier for +developers to start working on JACL projects. Additionally, JACL has +yet to define a printer for its native types, or an extensible print +protocol. Object string representations are obtained by calling the +generic JavaScript \texttt{toString()} method, which doesn't always +produce a representation that can be read back in. \subsection{High-level analyzing compiler} Unlike JSCL, the JACL compiler is organized to facilitate high-level -optimizations such as those that would support efficient compilation -of \texttt{TAGBODY}/\texttt{GO}. - -Low level optimizations are deferred to (optional) JavaScript -optimizers that may be applied to deliverable executables. +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}. 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: +then converted to JavaScript strings by a code generation step. 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. @@ -484,16 +446,16 @@ are provided for modifying and merging these objects so as only to produce new objects. This convention reduces the possibility of optimization passes interfering with one another. It also eases understanding the AST, since every AST node contains a copy of all -relevant context. - -As JavaScript objects, AST nodes are easily introspected using the Web -browser's object inspector. +relevant context. As JavaScript objects, AST nodes are easily +introspected using the Web browser's object inspector. Currently, the \texttt{Env} object tracks lexical variables and \texttt{TAGBODY} tags. In the future, it will track the remaining aspects of the lexical environment, such as lexical functions and macros. +\subsubsection{Embedding JavaScript with \texttt{JACL:\%JS}} + Unlike JSCL or SLip, JACL's compiler supports a special operator for constructing fragments of JavaScript code, verbatim, from Lisp. The semantics of this operator, \texttt{JACL:\%JS}, are inspired by a @@ -504,8 +466,92 @@ following JACL code displays the number 3 in an alert box: (JACL:%JS "window.alert(~{})" 3) \end{verbatim} -The character sequence \texttt{\textasciitilde\{\}} is distinct from any plausible -JavaScript sequence and so is used as placeholder syntax. +The character sequence \texttt{\textasciitilde\{\}} is distinct from +any plausible JavaScript syntax and so is used as placeholder +syntax. There must be as many placeholders as there are arguments to +\texttt{JACL:\%JS}. + +\subsubsection{Other interoperation support} + +In addition to \texttt{JACL:\%JS}, the JACL compiler currently +supports three more special operators for interacting with the host +platform, \texttt{JACL:\%NEW}, \texttt{JACL:\%DOT} and +\texttt{JACL:\%CALL}. They perform JavaScript object instantiation, +field access, and function calls, respectively. Since JACL functions +compile into JavaScript functions, \texttt{JACL:\%CALL} is the basis +for JACL's \texttt{FUNCALL}, and for function calls generally. + +JACL also supplies a convenience macro, \texttt{JACL:\textbackslash.} +or ``the dot macro'' for performing a series of field accesses and +method calls\footnote{Strictly speaking, JavaScript ``method calls'' + are normal function calls but with a particular value of + \texttt{this}} concisely. Dot takes direct inspiration from +Clojure's \texttt{..} macro. \texttt{JACL:\textbackslash.} expands to +zero or more nested \texttt{JACL:\%DOT} or \texttt{JACL:\%CALL} +forms. Here is an example of a \texttt{JACL:\textbackslash.} form --- +equivalent to the JavaScript expression +\texttt{(123).toString().length} --- and its expansion: + +\begin{verbatim} +(\. 123 (|toString|) |length|) +(%DOT (%CALL 123 |toString|) |length|) ; 3 +\end{verbatim} + +Note that JavaScript identifiers are case sensitive, and so +case-preserving, pipe-delimited Lisp symbols must be used to refer to +field and method names. The dot macro also can also recognize Lisp or +JavaScript strings as JavaScript identifiers. + +\subsubsection{\texttt{TAGBODY} compilation strategy} + +JSCL implements \texttt{TAGBODY} as the combination of: + +\begin{itemize} + \item A local JavaScript \texttt{branch} variable containing the tag + of the next branch to execute. + \item A labeled \texttt{while(true) { ... }} loop containing a + \texttt{try/catch} statement. The \texttt{catch} arm of the + \texttt{try/catch} inspects the type of thrown exception, and if + it is of the marker type \texttt{TagNLX}, \texttt{branch} is set + to the tag carried by the \texttt{TagNLX} object. The \texttt{try} + arm of the \texttt{try/catch} contains a \texttt{switch} statement + that dispatches on \texttt{branch}. Each arm of the + \texttt{switch} corresponds to code associated with a \texttt{GO} + tag. The \texttt{switch} falls through to a \texttt{break} to the + enclosing labeled \texttt{while} loop, concluding execution of the + \texttt{TAGBODY}. + \item An implementation of \texttt{GO} that throws a JavaScript + exception of type \texttt{TagNLX} that contains the target tag. +\end{itemize} + +This mechanism is ingenious and general. Unfortunately, every jump +requires a JavaScript exception be thrown, severely penalizing nearly +every iteration construct in JSCL. Fortunately, a slight improvement +in the \texttt{GO} compilation strategy can yield a tremendous +performance benefit. The improvement follows from the observation that +any \emph{local jump} --- such as from a \texttt{GO} form to its +relevant \texttt{TAGBODY}, with no lexically-intervening +\texttt{LAMBDA} forms --- may rely on JavaScript's +\texttt{continue}\cite{MozLabel} operator with a label argument +instead of on throwing an exception in order to transfer control. + +JACL's rich AST will facilitate the identification of usages of +\texttt{GO} that are amenable to improvement. The availability of a +high-level AST will also facilitate further optimizations, such as +\texttt{GO} tag escape\footnote{Such as by use within a + \texttt{LAMBDA} form that is assigned as the value of a global + variable or passed to a function} analysis. It should be possible to +identify \texttt{TAGBODY}s that consist only of local jumps, and to +avoid generating \texttt{try/catch} boilerplate for them, thereby +reducing generated code size. + +Code generated for \texttt{TAGBODY} in JACL will still generally +require a \texttt{switch}, and so a slowdown relative to hand-coded +JavaScript loops would not be unexpected. However, preliminary +benchmarking \ref{appendix:benchmarks} of a factorial function on a +recent version of Google Chrome revealed only a very small discrepancy +between JACL's proposed approach and a hand-coded JavaScript +\texttt{while} loop-based approach. \subsection{Delivery} @@ -598,5 +644,66 @@ beautiful wife, Sandra Dipert, for her skillful editing. \bibliographystyle{ACM-Reference-Format} \bibliography{jacl-els-2020} +\appendix + +\section{Loop Performance Benchmarks} +\label{appendix:benchmarks} + +\begin{verbatim} +function fact1(n) { + var prod = 1; + while(n) prod *= n--; + return prod; +} + +function GoTag(tag) { + this.tag = tag; + return this; +} + +function fact2(n) { + var branch = 0; + var prod = 1; + loop1: + while(true) { + try { + switch(branch) { + case 0: + if(n) { + prod *= n--; + branch = 0; + continue loop1; + } + case 1: + return prod; + } + } catch (e) { + if (e instanceof GoTag) { + branch = e.tag; + continue loop1; + } else { + throw e; + } + } + } +} + +var start; + +start = performance.now(); +for (var i = 0; i < 1e8; i++) { + fact1(20); +} +console.log("fact1", performance.now() - start); +// fact1 1860.9749999595806 + +start = performance.now(); +for (var i = 0; i < 1e8; i++) { + fact2(20); +} +console.log("fact2", performance.now() - start); +// fact2 1981.7150000017136 +\end{verbatim} + \end{document} \endinput