<!DOCTYPE html>
<script>var __pbpa = true;</script><script>var translated_warning_string = 'Warning: Never enter your Tumblr password unless \u201chttps://www.tumblr.com/login\u201d\x0ais the address in your web browser.\x0a\x0aYou should also see a green \u201cTumblr, Inc.\u201d identification in the address bar.\x0a\x0aSpammers and other bad guys use fake forms to steal passwords.\x0a\x0aTumblr will never ask you to log in from a user\u2019s blog.\x0a\x0aAre you absolutely sure you want to continue?';</script><script type="text/javascript" language="javascript" src="http://assets.tumblr.com/assets/scripts/pre_tumblelog.js?_v=289ca146962d7f79251f9df647c84ce1"></script>
<!DOCTYPE html>
<html>
<head prefix="og: http://ogp.me/ns# fb: http://ogp.me/ns/fb# blog: http://ogp.me/ns/blog#">
<meta charset="UTF-8">
<title>Discover Lisp in Your Web Browser with Javascript - alan dipert</title>
<link rel="shortcut icon" href="http://24.media.tumblr.com/avatar_4ae064934cfd_16.png">
<link rel="alternate" type="application/rss+xml" href="http://alan.dipert.org/rss">
<meta name="description" content="Discover Lisp in Your Web Browser with Javascript This post is available as a PDF Many ideas introduced originally in Lisp, such as conditional execution (the if-then-else construct), garbage..." />
<meta name="if:Show notes" content="1">
<meta name="text:Disqus Shortname" content="" />
<meta name="color:Post Background" content="#F2F2F2" />
<link rel="stylesheet" href="http://static.tumblr.com/26l8vc7/ej3lr0jwd/style.css">
<style type="text/css">
.post{background: #F2F2F2;}
</style>
<script type="text/javascript" src="http://shjs.sourceforge.net/sh_main.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_css.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_html.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_java.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_sh.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_c.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_scala.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_cpp.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_php.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_ruby.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_javascript.min.js">
</script>
<link type="text/css" rel="stylesheet" href="http://shjs.sourceforge.net/sh_style.css">
<script type="text/javascript">
var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-965358-1']);
_gaq.push(['_trackPageview']);
(function() {
var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
})();
</script>
<!-- BEGIN TUMBLR FACEBOOK OPENGRAPH TAGS -->
<!-- If you'd like to specify your own Open Graph tags, define the og:url and og:title tags in your theme's HTML. -->
<!-- Read more: http://ogp.me/ -->
<meta property="fb:app_id" content="48119224995" />
<meta property="og:title" content="Discover Lisp in Your Web Browser with Javascript" />
<meta property="og:url" content="http://alan.dipert.org/post/7193534410/discover-lisp-in-your-web-browser-with-javascript" />
<meta property="og:description" content="This post is available as a PDF
Many ideas introduced originally in Lisp, such as conditional execution (the if-then-else construct), garbage collection, and first-class functions1, can be found in..." />
<meta property="og:type" content="tumblr-feed:entry" />
<!-- END TUMBLR FACEBOOK OPENGRAPH TAGS -->
<!-- TWITTER TAGS -->
<meta charset="utf-8">
<meta name="twitter:card" content="summary" />
<meta name="twitter:description" content="This post is available as a PDF
Many ideas introduced originally in Lisp, such as conditional execution (the if-then-else construct), garbage collection, and first-class functions1, can be found in modern non-Lisp programming languages.
Other ideas pioneered by Lisp, like the idea that programs can be composed solely of expressions, and homoiconicity, or the idea that a program can be written in its own data structures, are rarer.
Learning a Lisp dialect, whether it&#8217;s Clojure, Scheme, or Common Lisp, is a great way to see for yourself how powerful all of these ideas can be when combined.
An even better way to understand the ideas is to implement your own Lisp23.
After we explore some fundamental concepts, we&#8217;ll look at how a language like Javascript works.
Then, we&#8217;ll build our own small Lisp to Javascript compiler on top of Javascript in about 32 lines of Javascript code.
Expression vs. Statement
Programs in languages like Javascript are composed of two things:
statements
expressions
Lisp programs are composed only of expressions.
Both statements and expressions are, in some sense, instructions for the computer to do some piece of work. The difference between them is that a statement does not return a value, but an expression does.
Consider Javascript&#8217;s if-then-else statement:
if (x &gt; 10) {
alert("x was bigger than 10!");
} else {
alert("x was not bigger than 10!")
}
We call alert inside both the then and else bodies of the expression because if does not return a value. If it did, we could pass it directly to a single alert call, as this wishful pseudo-Javascript demonstrates:
alert(if (x &gt; 10) {
return "x was bigger than 10!"
} else {
return "x was not bigger than 10!"
});
If we eliminate statements from our wishful pseudo-Javascript entirely, there&#8217;s no longer a need for the return operator. It&#8217;s assumed that values &#8220;return&#8221; themselves:
alert(if (x &gt; 10) {
"x was bigger than 10!"
} else {
"x was not bigger than 10!"
});
Javascript actually provides an if-then-else construct that returns a value, the ternary operator4, but it is seldom used and often discouraged5.
With expressions, it&#8217;s possible to write code in the imperative style the first example demonstrated. The opposite, writing expressions in terms of statements, is not.
If we agree that &#8220;power&#8221; means &#8220;possibility&#8221;, then languages like Lisp, which are based on expressions instead of statements, might be considered powerful.
Homoiconicity
Homoiconicity is a property of a programming language&#8217;s syntax, and means that programs in a language are expressed using that language&#8217;s own data structures. The property of homoiconicity is key to the way Lisp empowers the programmer to fabricate and manipulate syntax.
Homoiconicity might be understood by exploring the properties of source code and interpretation of that source code in a non-homoiconic language first.
Javascript, while influenced by Lisp in other ways6, is not homoiconic, and its popularity, availability, and conventional syntax make it a candidate for exploration.
Implementing Javascript
How a Javascript Interpreter Works
Consider this fragment of Javascript code, which passes the sum of 1 and the product of 2 and 3 to a web browser&#8217;s alert function:
alert(1 + 2 * 3);
When a browser passes this code, or data, as a string to its Javascript interpreter, something like the following happens:
The interpreter lexically analyzes7 the string, turning it into a stream of tokens. Tokens are objects in source code upon which other constructs are defined, such as function names, operators, and literals like numbers or strings. The tokens in the above fragment might be:
alert
(
1
+
2
*
3
)
;
The interpreter parses the token stream, attempting, recursively, to match the pattern of tokens to known language constructs. For instance, when the interpreter sees the function name alert followed by (, it knows to expect zero or more tokens that must be succeeded by a closing ).
The interpreter evaluates the constructs it found from the inside out:
2 * 3 happens first, because, * has higher precedence than + and because the interpreter knows it needs a value or identifier to pass to alert.
The product, 6, is returned.
1 + 6 is evaluated, returning 7.
Finally, alert(7) is evaluated, and a message is displayed.
If you were to write your own Javascript interpreter or compiler, you would need to implement a lexical analyzer, a parser, and an evaluator in order to complete the above steps.
Even if you were to implement your interpreter in Javascript, you&#8217;d have a long way to go, because none of these functions are provided by Javascript interpreters to Javascript programmers.
Javascript provides the eval function, but it accepts only strings, and you need to create source code strings yourself. Creating source code strings to pass to eval is effectively compilation, and done correctly could be as difficult as writing a compiler.
The task is not as daunting if we take the Lisp approach and build our programs in a data format richer than strings. Let&#8217;s meet the problem half way, and invent a Javascript syntax based on Javascript data.
A Homoiconic Javascript Subset: JSONScript
S-expressions
Consider this alternative representation of the code fragment, in a language we just invented, JSONScript:
['alert', ['+', 1, ['*', 2, 3]]]
Unlike the earlier example, which was a string that required multiple phases of analysis to understand and run, the above code is written using data structures native to Javascript: string, number, and array.
JSON, which stands for &#8220;Javascript Object Notation&#8221;, is a notation for expressing data in terms of Javascript data structures. JSON is expressive enough for us to use it to represent code for a simple programming language.
We could easily write a function called compile_jsonjs that converted this representation into a string that could be passed to eval, because:
We don&#8217;t need to write a lexical analyzer or parser: our code is already rich enough to express how it should be evaluated.
compile_jsonjs doesn&#8217;t need to know about operator precedence because we&#8217;re using s-expressions.
S-expressions, short for &#8220;symbolic expressions&#8221;, are a convention for writing code that allows us to represent a function call with an array. This convention is also known as prefix notation. The first element of the array is the function, and subsequent elements are arguments to that function that are evaluated first.
S-expressions leave no ambiguity about the order in which functions must be applied. In the original example, the expression 1 + 2 * 3 evaluated to 7 because it&#8217;s in the Javascript specificaton that * must evaluate before +.
In JSONScript, we express our intent to multiply first by making ['*', 2, 3] an argument to +.
S-expressions don&#8217;t have to be arrays. 42 and "hamster dance" are also s-expressions, because they also evaluate, but to themselves.
Lisp uses lists instead of arrays as s-expressions, but the idea is the same.
Some Implementation Details
There are at least two implementation details we face in implementing compile_jsonjs:
In JSONScript, as in Lisp, there is no distinction between function and operator. Functions, whether they are alert or *, must only appear as a string and as the first element of an array.
compile_jsonjs needs to recognize functions that Javascript considers to be operators, and return the correct syntax for them.
In Javascript, functions are identified by symbols, not strings. For instance, this syntax is not correct: 'alert'(7).
compile_jsonjs must return function names as symbols.
Conflating symbol and string is necessary but has unfortunate implications. For instance, it will be impossible to pass a function name as an argument to a function in JSONScript.
Adding the ability to pass function names as arguments equires us to go beyond JSON as our source data format, because JSON permits symbol literals only as an object field names.
Building the Compiler
We&#8217;re now equipped to reason about how compile_jsonjs will work.
First, we check if the input is an array.
If it is an array, we:
Compile the arguments
Check if the first element is an operator like * or +
If it is an operator, interpose the compiled arguments with the operator, and concatenate everything into a single string. compile_jsonjs(['+', 1, 2]) should return "1+2".
If it&#8217;s not an operator, like alert, we return a function call. compile_jsonjs(['alert', 'hello']) should return "alert('hello')"
If it isn&#8217;t an array, we return it as a string. compile_jsonjs(42) should return "42".
The Implementation
Next, we can translate our plan into code. We know that compile_jsonjs will need helper functions for:
Testing if an object is an array: This is how we&#8217;ll determine at the beginning of compile_jsonjs whether we&#8217;re compiling a function call or a literal. Literals are data that evaluate to themselves, like numbers or strings.
Testing if an array contains a particular object: We&#8217;ll need to make a list of functions that are Javascript operators, because we must emit different Javascript syntax for them.
The first helper function we need, isArray(), isn&#8217;t available on some browsers, and is actually difficult to write in a widely compatible way.
So, we can borrow it from the underscore.js8 library:
var isArray = function (obj) {
return Object.prototype.toString.call(obj) === '[object Array]';
}
Next, we need a function for testing if an object is in an array. Such a function is also not available in some browsers, but we can implement it like so:
var inArray = function(array, item) {
for(var i = 0; i &lt; array.length; i++)
if (array[i] === item) return true;
return false;
}
With these functions in place, we can finally write our compiler:
var compile_jsonjs = function(expression) {
var operators = ['*', '+'];
if (isArray(expression)) {
var func_name = expression[0];
var func_args = expression.slice(1);
var compiled_args = [];
for (var i = 0; i &lt; func_args.length; i++)
compiled_args.push(compile_jsonjs(func_args[i]));
if(inArray(operators, func_name)) {
return compiled_args.join(func_name);
} else {
return func_name + "(" + compiled_args.join(',') + ")";
}
} else {
return expression.toString()
}
}
The full source listing, which you can copy and paste into a web browser&#8217;s Javascript console, follows:
var isArray = function (obj) {
return Object.prototype.toString.call(obj) === '[object Array]';
}
var inArray = function(array, item) {
for(var i = 0; i &lt; array.length; i++)
if (array[i] === item) return true;
return false;
}
var compile_jsonjs = function(expression) {
var operators = ['*', '+'];
if (isArray(expression)) {
var func_name = expression[0];
var func_args = expression.slice(1);
var compiled_args = [];
for (var i = 0; i &lt; func_args.length; i++)
compiled_args.push(compile_jsonjs(func_args[i]));
if(inArray(operators, func_name)) {
return compiled_args.join(func_name);
} else {
return func_name + "(" + compiled_args.join(',') + ")";
}
} else {
return expression.toString()
}
}
Trying it Out
We can test our compiler by seeing what code it generates with our JSONScript fragment:
compile_jsonjs(['alert', ['+', 1, ['*', 2, 3]]]);
And we can evaluate our compiled code by passing that result to eval:
eval(compile_jsonjs(['alert', ['+', 1, ['*', 2, 3]]]));
Going Further
JSONScript probably isn&#8217;t a language you would want to use for your next programming project, but hopefully you now have a better understanding of what Lisp is and why it is different.
Further extending JSONScript will help you understand Lisp even more.
You can begin by adding support for other Javascript operators.
Next, you might implement lambda and quote. These will allow you to define functions in JSONScript, and to pass arrays to functions without evaluating them.
Once you have lambda and quote, you can implement other special forms, using Paul Graham&#8217;s The Roots of Lisp as a guide9.
If you&#8217;re feeling particularly ambitious, you might consider adding support for one of Lisp&#8217;s most famous and unique features - macros, or functions that:
are run before evaluation
do not evaluate their arguments
return JSONScript code
What Made Lisp Different by Paul Graham ↩
The Roots of Lisp by Paul Graham ↩
Lisp in Small Pieces ↩
Wikipedia: Ternary operation (Javascript) ↩
jQuery Core Style Guide: Blocks ↩
Popularity by Brendan Eich ↩
Wikipedia: Lexical analysis ↩
_.isArray in underscore.js ↩
The Roots of Lisp by Paul Graham ↩
" />
<meta name="twitter:title" content="Discover Lisp in Your Web Browser with Javascript" />
<meta name="twitter:url" content="http://alan.dipert.org/post/7193534410/discover-lisp-in-your-web-browser-with-javascript" />
<meta name="twitter:site" content="tumblr" />
<meta name="twitter:app:name:iphone" content="Tumblr" />
<meta name="twitter:app:name:ipad" content="Tumblr" />
<meta name="twitter:app:name:googleplay" content="Tumblr" />
<meta name="twitter:app:id:iphone" content="305343404" />
<meta name="twitter:app:id:ipad" content="305343404" />
<meta name="twitter:app:id:googleplay" content="com.tumblr" />
<meta name="twitter:app:url:iphone" content="tumblr://x-callback-url/blog?blogName=alandipert&postID=7193534410&referrer=twitter-cards" />
<meta name="twitter:app:url:ipad" content="tumblr://x-callback-url/blog?blogName=alandipert&postID=7193534410&referrer=twitter-cards" />
<meta name="twitter:app:url:googleplay" content="tumblr://x-callback-url/blog?blogName=alandipert&postID=7193534410&referrer=twitter-cards" />
<script type="text/javascript" src="http://assets.tumblr.com/assets/scripts/tumblelog.js?_v=dae58aa57407c7d7e8848a80145008fa"></script><meta http-equiv="x-dns-prefetch-control" content="off"/></head>
<body>
<div id="wrapper">
<div id="header" role="banner">
<h1><a href="/">alan dipert</a></h1>
<div id="description">
<p><p><a href = "http://twitter.com/alandipert/">twitter</a> <a href = "http://github.com/alandipert/">github</a> <a href = "mailto:adipert@acm.org">email</a></p></p>
</div>
</div>
<div id="content" role="main">
<div class="post text">
<div class="date">
<p><span class="day">03</span> 7 / 2011</p>
</div>
<div class="content">
<h2>Discover Lisp in Your Web Browser with Javascript</h2>
<p><em>This post is <a href="http://tailrecursion.com/~alan/writing/discover-lisp-in-your-browser.pdf">available as a PDF</a></em></p>
<p>Many ideas introduced originally in Lisp, such as conditional execution (the <code>if-then-else</code> construct), garbage collection, and first-class functions<sup><a id="fnref1" href="#fn1">1</a></sup>, can be found in modern non-Lisp programming languages.</p>
<p>Other ideas pioneered by Lisp, like the idea that programs can be composed solely of <em>expressions</em>, and <em>homoiconicity</em>, or the idea that a program can be written in its own data structures, are rarer.</p>
<p>Learning a Lisp dialect, whether it’s Clojure, Scheme, or Common Lisp, is a great way to see for yourself how powerful all of these ideas can be when combined.</p>
<p>An even better way to understand the ideas is to implement your own Lisp<sup><a id="fnref2" href="#fn2">2</a></sup><sup><a id="fnref3" href="#fn3">3</a></sup>.</p>
<p>After we explore some fundamental concepts, we’ll look at how a language like Javascript works.</p>
<p>Then, we’ll build our own small Lisp to Javascript compiler on top of Javascript in about 32 lines of Javascript code.</p>
<h2 id="expression-vs.-statement">Expression vs. Statement</h2>
<p>Programs in languages like Javascript are composed of two things:</p>
<ul><li>statements</li>
<li>expressions</li>
</ul><p>Lisp programs are composed only of expressions.</p>
<p>Both statements and expressions are, in some sense, instructions for the computer to do some piece of work. The difference between them is that a statement does not return a value, but an expression does.</p>
<p>Consider Javascript’s <code>if-then-else</code> statement:</p>
<pre><code>if (x > 10) {
alert("x was bigger than 10!");
} else {
alert("x was not bigger than 10!")
}
</code></pre>
<p>We call <code>alert</code> inside both the <code>then</code> and <code>else</code> bodies of the expression because <code>if</code> does not return a value. If it did, we could pass it directly to a single <code>alert</code> call, as this wishful pseudo-Javascript demonstrates:</p>
<pre><code>alert(if (x > 10) {
return "x was bigger than 10!"
} else {
return "x was not bigger than 10!"
});
</code></pre>
<p>If we eliminate statements from our wishful pseudo-Javascript entirely, there’s no longer a need for the <code>return</code> operator. It’s assumed that values “return” themselves:</p>
<pre><code>alert(if (x > 10) {
"x was bigger than 10!"
} else {
"x was not bigger than 10!"
});
</code></pre>
<p>Javascript actually provides an <code>if-then-else</code> construct that returns a value, the <em>ternary operator</em><sup><a id="fnref4" href="#fn4">4</a></sup>, but it is seldom used and often discouraged<sup><a id="fnref5" href="#fn5">5</a></sup>.</p>
<p>With expressions, it’s possible to write code in the <em>imperative style</em> the first example demonstrated. The opposite, writing expressions in terms of statements, is not.</p>
<p>If we agree that “power” means “possibility”, then languages like Lisp, which are based on expressions instead of statements, might be considered powerful.</p>
<h2 id="homoiconicity">Homoiconicity</h2>
<p><em>Homoiconicity</em> is a property of a programming language’s syntax, and means that programs in a language are expressed using that language’s own data structures. The property of homoiconicity is key to the way Lisp empowers the programmer to fabricate and manipulate syntax.</p>
<p>Homoiconicity might be understood by exploring the properties of source code and interpretation of that source code in a non-homoiconic language first.</p>
<p>Javascript, while influenced by Lisp in other ways<sup><a id="fnref6" href="#fn6">6</a></sup>, is not homoiconic, and its popularity, availability, and conventional syntax make it a candidate for exploration.</p>
<h2 id="implementing-javascript">Implementing Javascript</h2>
<h3 id="how-a-javascript-interpreter-works">How a Javascript Interpreter Works</h3>
<p>Consider this fragment of Javascript code, which passes the sum of 1 and the product of 2 and 3 to a web browser’s <code>alert</code> function:</p>
<pre><code>alert(1 + 2 * 3);
</code></pre>
<p>When a browser passes this code, or data, as a string to its Javascript interpreter, something like the following happens:</p>
<ul><li>The interpreter <em>lexically analyzes</em><sup><a id="fnref7" href="#fn7">7</a></sup> the string, turning it into a stream of <em>tokens</em>. Tokens are objects in source code upon which other constructs are defined, such as function names, operators, and literals like numbers or strings. The tokens in the above fragment might be:
<ul><li><code>alert</code></li>
<li><code>(</code></li>
<li>1</li>
<li><code>+</code></li>
<li>2</li>
<li><code>*</code></li>
<li>3</li>
<li><code>)</code></li>
<li><code>;</code></li>
</ul></li>
<li>The interpreter <em>parses</em> the token stream, attempting, recursively, to match the pattern of tokens to known language constructs. For instance, when the interpreter sees the function name <code>alert</code> followed by <code>(</code>, it knows to expect zero or more tokens that must be succeeded by a closing <code>)</code>.</li>
<li>The interpreter <em>evaluates</em> the constructs it found from the inside out:
<ul><li><code>2 * 3</code> happens first, because, <code>*</code> has higher precedence than <code>+</code> and because the interpreter knows it needs a value or identifier to pass to <code>alert</code>.</li>
<li>The product, 6, is returned.</li>
<li><code>1 + 6</code> is evaluated, returning 7.</li>
<li>Finally, <code>alert(7)</code> is evaluated, and a message is displayed.</li>
</ul></li>
</ul><p>If you were to write your own Javascript interpreter or compiler, you would need to implement a <code>lexical analyzer</code>, a <code>parser</code>, and an <code>evaluator</code> in order to complete the above steps.</p>
<p>Even if you were to implement your interpreter in Javascript, you’d have a long way to go, because none of these functions are provided by Javascript interpreters to Javascript programmers.</p>
<p>Javascript provides the <code>eval</code> function, but it accepts only strings, and you need to create source code strings yourself. Creating source code strings to pass to <code>eval</code> is effectively compilation, and done correctly could be as difficult as writing a compiler.</p>
<p>The task is not as daunting if we take the Lisp approach and build our programs in a data format richer than strings. Let’s meet the problem half way, and invent a Javascript syntax based on Javascript data.</p>
<h2 id="a-homoiconic-javascript-subset-jsonscript">A Homoiconic Javascript Subset: JSONScript</h2>
<h3 id="s-expressions">S-expressions</h3>
<p>Consider this alternative representation of the code fragment, in a language we just invented, JSONScript:</p>
<pre><code>['alert', ['+', 1, ['*', 2, 3]]]
</code></pre>
<p>Unlike the earlier example, which was a string that required multiple phases of analysis to understand and run, the above code is written using data structures native to Javascript: string, number, and array.</p>
<p><em>JSON</em>, which stands for “Javascript Object Notation”, is a notation for expressing data in terms of Javascript data structures. JSON is expressive enough for us to use it to represent code for a simple programming language.</p>
<p>We could easily write a function called <code>compile_jsonjs</code> that converted this representation into a string that could be passed to <code>eval</code>, because:</p>
<ul><li>We don’t need to write a lexical analyzer or parser: our code is already rich enough to express how it should be evaluated.</li>
<li><code>compile_jsonjs</code> doesn’t need to know about operator precedence because we’re using <em>s-expressions</em>.</li>
</ul><p>S-expressions, short for “symbolic expressions”, are a convention for writing code that allows us to represent a function call with an array. This convention is also known as <em>prefix notation</em>. The first element of the array is the function, and subsequent elements are arguments to that function that are evaluated first.</p>
<p>S-expressions leave no ambiguity about the order in which functions must be applied. In the original example, the expression <code>1 + 2 * 3</code> evaluated to 7 because it’s in the Javascript specificaton that <code>*</code> must evaluate before <code>+</code>.</p>
<p>In JSONScript, we express our intent to multiply first by making <code>['*', 2, 3]</code> an argument to <code>+</code>.</p>
<p>S-expressions don’t have to be arrays. <code>42</code> and <code>"hamster dance"</code> are also s-expressions, because they also evaluate, but to themselves.</p>
<p>Lisp uses lists instead of arrays as s-expressions, but the idea is the same.</p>
<h3 id="some-implementation-details">Some Implementation Details</h3>
<p>There are at least two implementation details we face in implementing <code>compile_jsonjs</code>:</p>
<ul><li>In JSONScript, as in Lisp, there is no distinction between function and operator. Functions, whether they are <code>alert</code> or <code>*</code>, must only appear as a string and as the first element of an array.
<ul><li><code>compile_jsonjs</code> needs to recognize functions that Javascript considers to be operators, and return the correct syntax for them.</li>
</ul></li>
<li>In Javascript, functions are identified by symbols, not strings. For instance, this syntax is not correct: <code>'alert'(7)</code>.
<ul><li><code>compile_jsonjs</code> must return function names as symbols.</li>
<li>
<p>Conflating symbol and string is necessary but has unfortunate implications. For instance, it will be impossible to pass a function name as an argument to a function in JSONScript.</p>
</li>
<li>
<p>Adding the ability to pass function names as arguments equires us to go beyond JSON as our source data format, because JSON permits symbol literals only as an object field names.</p>
</li>
</ul></li>
</ul><h3 id="building-the-compiler">Building the Compiler</h3>
<p>We’re now equipped to reason about how <code>compile_jsonjs</code> will work.</p>
<ul><li>First, we check if the input is an array.</li>
<li>If it is an array, we:
<ul><li>Compile the arguments</li>
<li>Check if the first element is an operator like <code>*</code> or <code>+</code>
<ul><li>If it is an operator, interpose the compiled arguments with the operator, and concatenate everything into a single string. <code>compile_jsonjs(['+', 1, 2])</code> should return <code>"1+2"</code>.</li>
<li>If it’s not an operator, like <code>alert</code>, we return a function call. <code>compile_jsonjs(['alert', 'hello'])</code> should return <code>"alert('hello')"</code></li>
</ul></li>
</ul></li>
<li>If it isn’t an array, we return it as a string. <code>compile_jsonjs(42)</code> should return <code>"42"</code>.</li>
</ul><h3 id="the-implementation">The Implementation</h3>
<p>Next, we can translate our plan into code. We know that <code>compile_jsonjs</code> will need helper functions for:</p>
<ul><li>Testing if an object is an array: This is how we’ll determine at the beginning of <code>compile_jsonjs</code> whether we’re compiling a function call or a <em>literal</em>. Literals are data that evaluate to themselves, like numbers or strings.</li>
<li>Testing if an array contains a particular object: We’ll need to make a list of functions that are Javascript operators, because we must emit different Javascript syntax for them.</li>
</ul><p>The first helper function we need, <code>isArray()</code>, isn’t available on some browsers, and is actually difficult to write in a widely compatible way.</p>
<p>So, we can borrow it from the <code>underscore.js</code><sup><a id="fnref8" href="#fn8">8</a></sup> library:</p>
<pre><code>var isArray = function (obj) {
return Object.prototype.toString.call(obj) === '[object Array]';
}
</code></pre>
<p>Next, we need a function for testing if an object is in an array. Such a function is also not available in some browsers, but we can implement it like so:</p>
<pre><code>var inArray = function(array, item) {
for(var i = 0; i < array.length; i++)
if (array[i] === item) return true;
return false;
}
</code></pre>
<p>With these functions in place, we can finally write our compiler:</p>
<pre><code>var compile_jsonjs = function(expression) {
var operators = ['*', '+'];
if (isArray(expression)) {
var func_name = expression[0];
var func_args = expression.slice(1);
var compiled_args = [];
for (var i = 0; i < func_args.length; i++)
compiled_args.push(compile_jsonjs(func_args[i]));
if(inArray(operators, func_name)) {
return compiled_args.join(func_name);
} else {
return func_name + "(" + compiled_args.join(',') + ")";
}
} else {
return expression.toString()
}
}
</code></pre>
<p>The full source listing, which you can copy and paste into a web browser’s Javascript console, follows:</p>
<pre><code>var isArray = function (obj) {
return Object.prototype.toString.call(obj) === '[object Array]';
}
var inArray = function(array, item) {
for(var i = 0; i < array.length; i++)
if (array[i] === item) return true;
return false;
}
var compile_jsonjs = function(expression) {
var operators = ['*', '+'];
if (isArray(expression)) {
var func_name = expression[0];
var func_args = expression.slice(1);
var compiled_args = [];
for (var i = 0; i < func_args.length; i++)
compiled_args.push(compile_jsonjs(func_args[i]));
if(inArray(operators, func_name)) {
return compiled_args.join(func_name);
} else {
return func_name + "(" + compiled_args.join(',') + ")";
}
} else {
return expression.toString()
}
}
</code></pre>
<h3 id="trying-it-out">Trying it Out</h3>
<p>We can test our compiler by seeing what code it generates with our JSONScript fragment:</p>
<pre><code>compile_jsonjs(['alert', ['+', 1, ['*', 2, 3]]]);
</code></pre>
<p>And we can evaluate our compiled code by passing that result to <code>eval</code>:</p>
<pre><code>eval(compile_jsonjs(['alert', ['+', 1, ['*', 2, 3]]]));
</code></pre>
<h2 id="going-further">Going Further</h2>
<p>JSONScript probably isn’t a language you would want to use for your next programming project, but hopefully you now have a better understanding of what Lisp is and why it is different.</p>
<p>Further extending JSONScript will help you understand Lisp even more.</p>
<p>You can begin by adding support for other Javascript operators.</p>
<p>Next, you might implement <code>lambda</code> and <code>quote</code>. These will allow you to define functions in JSONScript, and to pass arrays to functions without evaluating them.</p>
<p>Once you have <code>lambda</code> and <code>quote</code>, you can implement other <em>special forms</em>, using Paul Graham’s <em>The Roots of Lisp</em> as a guide<sup><a id="fnref9" href="#fn9">9</a></sup>.</p>
<p>If you’re feeling particularly ambitious, you might consider adding support for one of Lisp’s most famous and unique features - <em>macros</em>, or functions that:</p>
<ul><li>are run before evaluation</li>
<li>do not evaluate their arguments</li>
<li>return JSONScript code</li>
</ul><hr><ol><li id="fn1">
<p><a href="http://www.paulgraham.com/diff.html">What Made Lisp Different</a> by Paul Graham <a title="Jump back to footnote 1" href="#fnref1">↩</a></p>
</li>
<li id="fn2">
<p><a href="http://www.paulgraham.com/rootsoflisp.html">The Roots of Lisp</a> by Paul Graham <a title="Jump back to footnote 2" href="#fnref2">↩</a></p>
</li>
<li id="fn3">
<p><a href="http://pagesperso-systeme.lip6.fr/Christian.Queinnec/WWW/LiSP.html">Lisp in Small Pieces</a> <a title="Jump back to footnote 3" href="#fnref3">↩</a></p>
</li>
<li id="fn4">
<p><a href="http://en.wikipedia.org/wiki/Ternary_operation#C.2C_C.2B.2B.2C_C.23.2C_Vala.2C_Objective-C.2C_Java.2C_JavaScript.2C_ActionScript">Wikipedia: Ternary operation (Javascript)</a> <a title="Jump back to footnote 4" href="#fnref4">↩</a></p>
</li>
<li id="fn5">
<p><a href="http://docs.jquery.com/JQuery_Core_Style_Guidelines#Blocks">jQuery Core Style Guide: Blocks</a> <a title="Jump back to footnote 5" href="#fnref5">↩</a></p>
</li>
<li id="fn6">
<p><a href="http://weblogs.mozillazine.org/roadmap/archives/2008/04/popularity.html">Popularity</a> by Brendan Eich <a title="Jump back to footnote 6" href="#fnref6">↩</a></p>
</li>
<li id="fn7">
<p><a href="http://en.wikipedia.org/wiki/Lexical_analysis">Wikipedia: Lexical analysis</a> <a title="Jump back to footnote 7" href="#fnref7">↩</a></p>
</li>
<li id="fn8">
<p><a href="https://github.com/documentcloud/underscore/blob/96dbdaf9295f5598b631411d1553b04b43594152/underscore.js#L641">_.isArray in underscore.js</a> <a title="Jump back to footnote 8" href="#fnref8">↩</a></p>
</li>
<li id="fn9">
<p><a href="http://www.paulgraham.com/rootsoflisp.html">The Roots of Lisp</a> by Paul Graham <a title="Jump back to footnote 9" href="#fnref9">↩</a></p>
</li>
</ol>
</div>
<div class="info">
<p><a href="http://alan.dipert.org/post/7193534410/discover-lisp-in-your-web-browser-with-javascript">Permalink</a> <span class="notes">8 notes</span> <span style="float: right;"><a class="dsq-comment-count" href="http://alan.dipert.org/post/7193534410/discover-lisp-in-your-web-browser-with-javascript#disqus_thread"></a></span></p>
</div>
</div>
<div class="notecontainer">
<div id="disqus_thread"></div>
<script type="text/javascript" src="http://disqus.com/forums/alandipert/embed.js"></script>
<noscript><a href="http://alandipert.disqus.com/?url=ref">View the discussion thread</a></noscript>
</div>
<div id="pagination" role="navigation">
<p>
<a href="http://alan.dipert.org/post/17375691572" class="newer">Next post »</a>
<a href="http://alan.dipert.org/post/1606016275" class="older">« Previous post</a>
</p>
</div>
</div>
</div>
<div id="footer">
<div class="wrapper">
<ul class="links" role="navigation">
<li><a href="/archive">Archive</a></li>
<li><a href="http://alan.dipert.org/rss">RSS</a></li>
</ul>
<p class="info-theme" role="contentinfo">Powered by <a href="http://www.tumblr.com">Tumblr</a> and designed by <a href="http://kcmr.tumblr.com">Kcmr</a>.</p>
</div>
</div>
<script type="text/javascript">
//<![CDATA[
(function() {
var links = document.getElementsByTagName('a');
var query = '?';
for(var i = 0; i < links.length; i++) {
if(links[i].href.indexOf('#disqus_thread') >= 0) {
query += 'url' + i + '=' + encodeURIComponent(links[i].href) + '&';
}
}
document.write('<script charset="utf-8" type="text/javascript" src="http://disqus.com/forums/alandipert/get_num_replies.js' + query + '"></' + 'script>');
})();
//]]>
</script>
<!-- BEGIN TUMBLR CODE -->
<iframe id="tumblr_controls" width="330" height="25" style="position:absolute; z-index:2147483647; top:0; right:0; border:0; background-color:transparent; overflow:hidden; " src="http://assets.tumblr.com/assets/html/iframe.html?src=http%3A%2F%2Falan.dipert.org%2Fpost%2F7193534410%2Fdiscover-lisp-in-your-web-browser-with-javascript%3F9ec9b148&pid=7193534410&rk=uzo3u7lk&lang=en_US&name=alandipert&brag=false&avatar=http%3A%2F%2F25.media.tumblr.com%2Favatar_4ae064934cfd_64.png&title=alan+dipert&url=http%3A%2F%2Falan.dipert.org%2F&_v=dcf1c0a578dbfd6678efa6e9b3e760bc"></iframe>
<!--[if IE]><script type="text/javascript">document.getElementById('tumblr_controls').allowTransparency=true;</script><![endif]-->
<!-- END TUMBLR CODE -->
<iframe src="http://assets.tumblr.com/analytics.html?4344dcb6da7e8742c4c5ab1d76ffafae" scrolling="no" width="1" height="1" frameborder="0" style="background-color:transparent; overflow:hidden; position:absolute; top:0; left:0 z-index:9999;" id="ga_target"></iframe>
<script>
var COMSCORE = true;
window.setTimeout(function() {
var analytics_frame = document.getElementById('ga_target');
analytics_frame.contentWindow.postMessage('enable_comscore;' + window.location, analytics_frame.src.split('/analytics.html')[0]);
}, 1000);
</script>
<script type="text/javascript">
var _qevents = _qevents || [];
(function() {
var elem = document.createElement('script');
elem.src = (document.location.protocol == "https:" ? "https://secure" : "http://edge") + ".quantserve.com/quant.js";
elem.async = true;
elem.type = "text/javascript";
var scpt = document.getElementsByTagName('script')[0];
scpt.parentNode.insertBefore(elem, scpt);
})();
</script>
<script type="text/javascript">
_qevents.push( { qacct: 'p-19UtqE8ngoZbM' } );
</script>
<noscript>
<div style="display: none;"><img src="//pixel.quantserve.com/pixel/'p-19UtqE8ngoZbM'.gif" height="1" width="1" alt="Quantcast"/></div>
</noscript>
<script type="text/javascript">var s=new Image(1,1);s.src=((r='http://www.tumblr.com/impixu?T=1370272799&J=eyJ0eXBlIjoidXJsIiwidXJsIjoiaHR0cDpcL1wvYWxhbi5kaXBlcnQub3JnXC9wb3N0XC83MTkzNTM0NDEwXC9kaXNjb3Zlci1saXNwLWluLXlvdXItd2ViLWJyb3dzZXItd2l0aC1qYXZhc2NyaXB0PzllYzliMTQ4IiwicmVxdHlwZSI6MH0=&U=MHFEJBIGOP&K=df9e132f29d41632ac5520b4dddad4875d9576e0265ff9d8ffffd30681e46d37&R=http%3A%2F%2Falan.dipert.org%2Fpost%2F7193534410%2Fdiscover-lisp-in-your-web-browser-with-javascript'.replace(/&R=[^&$]*/,'')) + ('&R='+escape(document.referrer)).substr(0, 2000-r.length).replace(/%.?.?$/,''));</script><noscript><img style="position:absolute;z-index:-3334;top:0px;left:0px;visibility:hidden;" src="http://www.tumblr.com/impixu?T=1370272799&J=eyJ0eXBlIjoidXJsIiwidXJsIjoiaHR0cDpcL1wvYWxhbi5kaXBlcnQub3JnXC9wb3N0XC83MTkzNTM0NDEwXC9kaXNjb3Zlci1saXNwLWluLXlvdXItd2ViLWJyb3dzZXItd2l0aC1qYXZhc2NyaXB0PzllYzliMTQ4IiwicmVxdHlwZSI6MCwibm9zY3JpcHQiOjF9&U=MHFEJBIGOP&K=5249fbae6254476416f9f1248d587f3a6fb355b753a880a96708da0d416edc98&R=http%3A%2F%2Falan.dipert.org%2Fpost%2F7193534410%2Fdiscover-lisp-in-your-web-browser-with-javascript"></noscript><script type="text/javascript">var s=new Image(1,1);s.src=((r='http://www.tumblr.com/impixu?T=1370272799&J=eyJ0eXBlIjoicG9zdCIsInVybCI6Imh0dHA6XC9cL2FsYW4uZGlwZXJ0Lm9yZ1wvcG9zdFwvNzE5MzUzNDQxMFwvZGlzY292ZXItbGlzcC1pbi15b3VyLXdlYi1icm93c2VyLXdpdGgtamF2YXNjcmlwdD85ZWM5YjE0OCIsInJlcXR5cGUiOjAsInBvc3RzIjpbeyJwb3N0aWQiOiI3MTkzNTM0NDEwIiwiYmxvZ2lkIjoiNDM5NDY4Iiwic291cmNlIjozM31dfQ==&U=PDCMJJJGFP&K=196f227d0da3af14aa86bce9a541d9aa6bcada58436db67290d6003a60f66a70&R=http%3A%2F%2Falan.dipert.org%2Fpost%2F7193534410%2Fdiscover-lisp-in-your-web-browser-with-javascript'.replace(/&R=[^&$]*/,'')) + ('&R='+escape(document.referrer)).substr(0, 2000-r.length).replace(/%.?.?$/,''));</script><noscript><img style="position:absolute;z-index:-3334;top:0px;left:0px;visibility:hidden;" src="http://www.tumblr.com/impixu?T=1370272799&J=eyJ0eXBlIjoicG9zdCIsInVybCI6Imh0dHA6XC9cL2FsYW4uZGlwZXJ0Lm9yZ1wvcG9zdFwvNzE5MzUzNDQxMFwvZGlzY292ZXItbGlzcC1pbi15b3VyLXdlYi1icm93c2VyLXdpdGgtamF2YXNjcmlwdD85ZWM5YjE0OCIsInJlcXR5cGUiOjAsInBvc3RzIjpbeyJwb3N0aWQiOiI3MTkzNTM0NDEwIiwiYmxvZ2lkIjoiNDM5NDY4Iiwic291cmNlIjozM31dLCJub3NjcmlwdCI6MX0=&U=PDCMJJJGFP&K=07092b556e6c5a44e6edd2d19ef171768d00c995a4fe562ea29fcbf7af19096b&R=http%3A%2F%2Falan.dipert.org%2Fpost%2F7193534410%2Fdiscover-lisp-in-your-web-browser-with-javascript"></noscript></body>
</html>