HomeBlogCategory: “javascript”

Showing only posts in category “javascript”.

Show all


SS-Lisp — run Lisp in your browser

SS-Lisp is an experiment I've worked on in my free time, rather sporadically, for several months.

It's a Lisp compiler that runs in a browser.  It compiles Lisp to an intermediary “bytecode” and it provides a virtual machine to run the compiled code with acceptable speed (I recommend Chrome or a derivative browser for “acceptable” to stand true).

It provides an “IDE” which mimics Emacs/SLIME, via my Ymacs editor.  The IDE has some interesting features, like symbol completion and cross-reference—if you used Emacs/SLIME you should feel fairly comfortable with it, though do not expect it to be that competent. ;)

I made a screen-cast here: https://vimeo.com/42070553 (that's without voice because I totally suck at making screen-casts).

While just a toy, as far as my research goes, I think it's the best one at the moment.  It beats BiwaScheme by orders of magnitude in terms of speed and development environment, and most other Lisp interpreters for the browser, including my own previous attempts, are not worth mentioning—except one, which actually inspired me to work on this: http://norstrulde.org/ilge10/.  Great job Eric!

Update: fellow from Germany suggested that I should rename the project, since the SS abbreviation brings up painful memories in some parts of the world...  I believe he's right so I'll rename it in the following days.  Any ideas for a name are welcome. :-)

Followup: done with that, the new name is “SLip”.  The old URL will redirect to the new one (slip.lisperator.net).

Filed in: emacs, javascript, lisp, programming, v8, ymacs5 comments

Dynamic scope & lexical scope — how?

Some time back I started working on a Lisp interpreter in JavaScript.  That's because I've been going through SICP, and section 4.1 is extraordinarily inspiring—if you read that, you want to write a Scheme interpreter.  Except that, being already a Common Lisp programmer, I wanted to write a Common Lisp interpreter.  Or at least a tiny part of it.

The version that's published on Github right now has both static (lexical) and dynamic scope, but it's somewhat cheating.  To implement dynamic scope I used JavaScript's try/finally, in order to pop dynamic bindings once a LET block that established them finished execution.  However, that version has a show-stopper bug: because JavaScript doesn't have tail call optimization (and even if it would)—it ruins the stack quite easily and you can't generally do loops via recursion.

So I started a new branch (which will be on Github pretty soon); on this new version all the interpreter is implemented in “continuation-returning-style”, if I may say so—instead of calling another function, or returning a value, each expression returns a function that knows what to do next.  The evaluation means to call a function, and the returned function, and the function returned from the returned function, until the cows come home.  (trampoline-style)

This incidentally gave me call/cc “for free”, which is nice (I already gave up my dreams of implementing a subset of Common Lisp, so I'll implement a superset instead :-p).  However dynamic variables turn out to be quite a hassle now.  I don't have the luxury of using the exceptions of the underlying language, because the stack is cleared after each expression evaluates.  Somehow I need to catch the moment when a scope exits, in order to restore the dynamic variables that it modified, but I'm not quite sure how—and the problem is exaggerated by having continuations...   Grr, I'll think of it some more this weekend.

Anyway, I'll publish a toy Lisp environment, with an Ymacs demo for the browser.  Soon.  It will be totally useless for practical purposes, of course.  It can solve WOTF in 10 seconds, with a Schemeish amb macro. (100 times slower than the plain JavaScript implementation).

Update: this is it:

Still no dynamic scope.


    Amb() in JavaScript, take two

    (this is a follow-up on a first article I wrote about amb in JavaScript).

    I kept reflecting on this—mostly because the first version was unable to help solving “Einstein's puzzle”, and I got determined to find a fix.

    So what, in fact, should amb do?  It has to pick a value and make sure something succeeds with that value.  What is something?  In the Scheme version of the operator, it's the “current continuation”.  That is, if you use amb multiple times in your program, when one fails only that one restarts (well, and subsequent ones) — it doesn't trigger a restart for the previous amb calls which didn't (yet?) fail.

    When taken to the simplest description, it's clear that it should look like this:

    [ read more... ]


    Amb() in JavaScript

    You might have heard of the mysterious “ambiguous operator”.  Just for fun, I wrote an implementation of it in JavaScript.  It might even be useful. ;-)

    So what is amb?  Given a list of values, amb nondeterministically returns one of them in such a way that the rest of the program succeeds.  When it is possible, of course.  If it's not possible, then the program fails.

    Say what?  So it picks one value from a list, such that the rest of the program is successful!

    Here is a hypothetical use for this operator:

    var a = amb([ 1, 3, 5 ]);
    var b = amb([ 7, 8, 9 ]);
    if (a + b <= 10)
    console.log(a, b); // 3 and 8, or maybe 5 and 9, etc.

    The exact usage will actually be a bit different in JavaScript, but the above is the way you could write it in Scheme (except the syntax) because Scheme has first class continuations.  A continuation is an "abstraction of the rest of the program" — so amb is able to “test” the rest of the program multiple times, giving it each value from the list, until it succeeds.  I find this really cool.

    I've seen a nice implementation for Common Lisp at Rosetta Code, even though Lisp doesn't have first-class continuations.  With macros it can be made to look almost as a part of the language.  That inspired me to try the JavaScript version.  Following there are some examples of usage, and at the bottom of this article you can find the full amb code.

    [ read more... ]


    What's missing from NodeJS

    Every now and then I keep thinking of this. What got me started to write it all down was this thread on the mailing list. Some guy who enjoys pain takes the trouble to write an E4X extension to Node (it really should be an extension to V8, but let alone that). Then another guy replies:

    “We aren't interested in language features, we're building a platform and not concerning ourselves with the language and vm allows us to build and iterate on this platform significantly faster than if we were building a language.”  (Mikeal Rogers)

    “We aren't interested in language features”! I'm not personally a fan of E4X and don't care much about having that in the language, but I do think that JavaScript needs to evolve. When I say needs I mean right now, it's not good enough.

    [ read more... ]


    On Automatic Semicolon Insertion

    (this started as a reply to this thread in NodeJS, but it got rather long so I'm posting it here)

    Before doing JavaScript, I was doing C/C++. There semicolons were required, and you got an error from the compiler when they were missing. I rarely got such errors though because when a semicolon was missing, Emacs would indent badly the following line; bad indentation was always a sign of syntax errors.

    So when I moved to JavaScript, semicolons at end of statements made very much sense. The Emacs JS options at that time weren't nearly as good as the C/C++ mode, so sometimes I forgot the semicolon.  Although usually the program ran fine, I still went through all sorts of scary bugs because of the automatic semicolon insertion. Oh how I missed that compiler error!

    So I got quite religious about using semicolons (also because I was using a simple regexp-based scanner to minify JS, and that was easily screwed by missing semicolons). Nowadays I use Emacs with js2-mode, which contains a full JS parser, and is able to warn about various things during editing, such as missing semicolons.

    As a matter of taste, I find code that uses semicolons at the beginning of lines a bit silly:

    ;(x || y).doSomething()
    ;[a, b, c].forEach(doSomething)
    for (var i = 0; i < 10; i ++) {

    I'm doing a lot of Lisp hacking lately, and the first two lines look like comments to me (intentionally turned off syntax highlighting above).

    Using the comma at BOL looks a bit better, because it makes it possible to comment out the line without forgetting a trailing comma:

    var magicWords = [ "abracadabra"
                     , "gesundheit"
                     //, "ventrilo"

    but still (continuing paste from npm's coding style):

      , spells = { "fireball" : function () { setOnFire() }
                 , "water" : function () { putOut() }

    you can't comment out the spells = line in the same way, because it spans multiple lines. So this argument fades away and let's just say it looks silly.

    So as far as my advice goes:

    1. Use an editor with good JS support. If it's just decent, it doesn't qualify. GEdit is decent, but not good enough. Emacs is supremely great.

    2. Configure your editor to warn you about “poor practice”. Again, in Emacs it's possible to do that. For example, my setup warns me if I assign to a variable that's not defined (creating globals is almost always a source of errors), if I forget semicolons, or if I assign in a conditional (where most likely the case is that you want "==" instead of "="). Details on my setup here.

    3. Do insert semicolons and save yourself from the pain of debugging "automatic semicolon insertion".

    4. Be happy. ;-)


    UglifyJS — a JS parser/compressor/beautifier

    ... for NodeJS.

    With minimal changes it should work on any JavaScript engine, but currently NodeJS is the main development platform.

    It implements a JavaScript parser which produces a clean abstract syntax tree from JS code (this part is ported from parse-js, a great JS parser for Common Lisp).  Then it contains a few functions that manipulate the AST to compress variable names to single characters, and provide various other compression techniques such as:

    • join consecutive var declarations:

      var a = 10; var b = 20;  ==>  var a = 10, b = 20;
    • remove block brackets {} where possible

    • transform foo["bar"] into foo.bar

    • various optimizations for IF statements:

      • remove "else" where possible (when the last statement in an IF block is "return", "throw", "break" or "continue")

      • transform simple IF-s like:

        if (foo) bar(); else baz();  ==>  foo?bar():baz();
        if (!foo) bar(); else baz();  ==>  foo?baz():bar();
        if (foo) bar();  ==>  foo&&bar();
        if (!foo) bar();  ==>  foo||bar();

    and some others.

    It compresses better than the YUI compressor, and safer than Google Closure.  And it's a lot faster than any of these.

    Get the code here: http://github.com/mishoo/UglifyJS and spread the word! :-)


            Writing a Redis client library for Node.js

            I'm playing with Node.js lately.  Node is an asynchronous environment that allow you to use JavaScript on the server.  The asynchronous nature makes it a bit different from other programming environments, and I'll describe in this article how I'm using some obvious features of the language (closures and exceptions) to accomplish something not-quite-trivial.  In short, I've written a Redis client library and a WebSocket library (and yes, I know these things exist already, but I suffer from the NIH syndrome).

            JavaScript has exceptions, and JavaScript has closures—combining them you can get “restarts”.  It's not the same as Lisp's condition/restarts system, in that once it throws an exception a function can not return anymore.

            In order to make use of this technique you have to write your code in “continuation-passing style” and avoid iterative loops.  While this might seem too complicated, it's easier and more natural than it sounds (and it's almost a requirement in environments such as NodeJS).

            [ read more... ]


            Yet Another JavaScript Template Engine

            I had to do this. :-)

            I mean, I don't like any existing template systems.

            I don't like mine either.  But still I think it's better than others.  I was looking at Tenjin and they have something like this:

            <?js for (var i = 0; i < list.length; ++i) { ?>
            <?js     var el = list[i] ?>
            <?js } ?>

            Functional, maybe, but downright ugly.  In YAJET, we can write it like this:

            $(FOREACH (el => list)  <li>$el</li>  $)

            which I think is a lot better.  YAJET compiles the templates into JavaScript code, so for your template you get a function that runs blazing fast.  It tries hard to do this The Right Way, so you don't have weird variable name clashes, or side effects.

            Give it a try.  There's a jQuery plugin too, for those who can't live without jQuery. :-)

            Filed in: javascript, programming5 comments

            The Bazon Fractal

            Here is a JavaScript implementation (using the <canvas> element) of an idea that my father discovered like 20 years ago. To the best of our knowledge, the idea wasn't known at the time. We recently found a similar image in Knuth's “The Art of Programming”, vol. 4, which according to Wikipedia was not published until 2005. Hence, in lack of a better name, I'm going to call this “the Bazon fractal”.

            The idea is simple. To draw the pixel (x, y) of the image, you compute the value of some function and select a color based on that value. Certain functions lead to impressive results. But you need to be either too lucky, or a truly passionated mathematician, to discover a function that returns something meaningful.

            [ read more... ]

            Filed in: javascript, programming4 comments
            See also