HomeBlogCategory: “lexical closures”

Showing only posts in category “lexical closures”.

Show all

Jul
22
2011
01:50

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.

    Filed in: javascript, lexical closures, lisp, programming, ymacsNo comments
    Apr
    09
    2011
    21:09

    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... ]

    Filed in: javascript, lexical closures, programming4 comments
    Apr
    07
    2011
    16:21

    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)
        fail();
    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... ]

    Filed in: javascript, lexical closures, programming15 comments
    Nov
    23
    2010
    00:07

    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... ]

    Filed in: javascript, lexical closures, lisp, node.js, programming, v811 comments
    Aug
    15
    2010
    23:18

    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! :-)

            Filed in: javascript, lexical closures, lisp, node.js, programming, v812 comments
            Jul
            10
            2010
            12:15

            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... ]

            Filed in: javascript, lexical closures, node.js, programming, redis, v811 comments
            Nov
            10
            2009
            23:00

            Ymacs — AJAX source code editor

            I just released a new project that I've been working on for about a month: Ymacs is an AJAX text editor, suitable for editing source code (currently there is support for JavaScript and XML, but more modes could be easily implemented).

            Ymacs is a DynarchLIB widget, which makes it easily embeddable into any DynarchLIB application.  This doesn't sound impressive, isn't it, but here's the real good news: I've decided to open source DynarchLIB and release it under a BSD-style license.  Some folks might believe this project is already dead, but this isn't so; it is true that there was no new release in almost two years, but the thing kept being improved and there are people using it in successful commercial applications.

            Well..  This should happen any minute, but I'm running out of time, as usual.  So it could take a few more days to push a new DL release.  In the mean time, go check Ymacs, it's pretty cool.  It has Emacs key bindings too. ;-)

            Filed in: emacs, firefox, javascript, lexical closures, lisp, programming, ymacsNo comments
            Aug
            24
            2009
            15:05

            Object oriented programming in JavaScript

            I'm pretty sure you know the Foo.prototype.bar = function(){ ... } syntax for declaring object methods, and also the Bar.prototype = new Foo stuff for setting up inheritance.  You also probably know that Prototype.js and jQuery have devised new, shorter/cleaner ways to declare objects.

            In the article below I'm presenting my own, which I developed around 2005 and kept refining it.  The described "syntax" is used in DynarchLIB (although not in the released version, which still uses the old eval()-based hacks).

            [ Read full article ]

            Filed in: javascript, lexical closures, programmingOne comment
            Feb
            02
            2007
            00:08

            The buzz of closures

            I found an interesting discussion about closures. I find this quote particularly true (and amusing):

            There has been a great deal of interest in closures lately, driven in great part by the fact that there is talk of adding some form of anonymous functions to the Java. Most of the time, people talk about “adding closures” to Java, and that prompts a flurry of questions of the form “what is a closure and why should I care?”

            Yes, why would they care? As someone put it, if you always programmed in Basic, you think you don't need recursion. You can't comprehend a complex language feature—such as recursion—unless you actually try to make some sense of it. Yes, no matter how many computer science courses you'd take, you can't do real programming unless, well, you do real programming. In other words, your teacher might have told you what recursion means, but unless you actually use it, you'll never know what is it good for.

            Consequently, I think there are 2 types of programmers.

            1. Some would spend a lot of their free time trying to understand and make use of some techniques that might—or might not, but usually will—serve them for real-world problems.

            2. The other camp is very boring: those are the people that are payed for some job and only do what their boss asks.

            Now, the boss will never ask you to use closures (or any other language feature for that matter). He'll just tell you “do this” ASAP, and you have to figure out how to finish it as soon as possible. Well, using closures, ASAP can mean a lot sooner than without them, no matter what language are you programming in (assuming of course that it supports this 30-years-old concept; some new and much hyped languages still don't.).

            I have former colleagues that have completed their B.S. in computer science (which I still didn't). One of the courses you do in the college is an AI course which, of course, uses Lisp as the supporting language. Well, the horror is that none of them understands what's a closure, and asks me every time I mention the word “OK, Java/C# might not have that, but why would I need it anyway?”.

            So after preaching functional programming for some time, and after I saw my fellows here ignore me, I've come to the conclusion that it's better for them not to understand it. A boss is a boss, and he'll favor someone who has a B.S. (which I don't). So I at least want to keep the technical advantage. :-p

            So, ya Java folks, don't even think about closures. You don't need them. Just focus on writing specs and UML-s and Factories and Managers and Listeners and Executors.

            Filed in: lexical closures, programming, rants13 comments
            See also