Arc Ported to JavaScript(halogen.note.amherst.edu)

69 pointsby kfvor 18 Jahren23 comments

halogen.note.amherst.edu

http://halogen.note.amherst.edu/~jdtang/arclite/

24 comments

an important limitation of javascript means this will never quite be a complete implementation:

Continuations are not implemented. I had started on a CPS-based interpreter, but then realized that JavaScript lacks tail-call optimization and has a recursion limit of 1000 calls, which'll make any CPS-transformation blow the stack.

looks like a good piece of code otherwise, though.

tlrobinsonvor 18 Jahren

This guy implemented a continuation-based syntax highlighter in JavaScript:

http://marijn.haverbeke.nl/codemirror/story.html

I'm not sure how relevant it is to implementing Arc, but never say never. JavaScript is Turing complete, after all...

nostrademonsvor 18 Jahren

That approach could work. He's storing the current continuation as a global variable, which I never thought of, because typically you want your interpreters to be self-contained. (I was also working off Guy Steele's toy CPS interpreter, which passes cont in and then ends each function with a tailcall to another function or the invocation of the continuation.) But I can't see any real reason why the global won't work; it'll get stored in a data structure when the continuation is captured, and since stack frames are normal JavaScript objects in ArcLite, the garbage collector will hold on to them.

It'll mean that any loop that may call back into the interpreter has to be rewritten as a tail-recursive function though, with the tail call being saved into the global continuation variable. Could be quite a bit of overhead.

marijnvor 18 Jahren

That is not a global variable, it is a closed-over variable, which, in terms of self-containedness, is a whole different beast. See also http://marijn.haverbeke.nl/cps/ .

tlrobinsonvor 18 Jahren

I believe you can use the "with" operator in JavaScript to use any object as the global object (normally "window" in the browser). I'm not sure how useful that could be, but it might help make it self contained.

nostrademonsvor 18 Jahren

"with" is dangerous, because it makes it impossible to tell lexically whether you're assigning to an object or to a global variable. If you mistype a variable or pass an object of the wrong type in to "with", you can find yourself with very difficult-to-track-down bugs. In practice I'd only use it with a bunch of assertions, which could bloat the code significantly.

Chris Double suggested another alternative over on Proggit: tailcall to window.setTimeout with a delay of 0. This is effectively a trampoline; the continuation gets pushed onto a timer, the eval function returns, then JavaScript picks up again where it should. As a nice side effect, it gives the browser's event loop a chance to run, which eliminates any chance of locking up the machine. Pretty elegant solution, though I'm guessing there's a significant performance penalty.

marijnvor 18 Jahren

You can fake tail calls with window.setTimeout(continuation, 0)

cstejereanvor 18 Jahren

Although unrelated to my challenge (http://blog.offbytwo.com/2008/02/05/a-different-kind-of-arc-...)

this seems to be the first implementation of Arc in a language other than Scheme. I'm curious if others will follow.

nostrademonsvor 18 Jahren

I thought about that while I was writing it (I started before your challenge came out). Here's the results for ArcLite:

  > wc [^j]*.js
   66   147  1359 buffer.js
  369  1114 10672 eval.js
  149   488  4522 primitives.js
  188   509  4989 reader.js
  356  1145 11869 types.js
  136   370  3260 utils.js
 1264  3773 36671 total

 > wc [^d]*.scm
 1093  4404 36047 ac.scm
   16    30   242 as.scm
   48   152  1252 brackets.scm
 1157  4586 37541 total

So ArcLite is about 100 lines of code more. OTOH, if you take out the reader (which is supplied by Scheme but I had to write myself for ArcLite) it's -254 lines for ArcLite and -48 lines for Arc0. Which means the JavaScript version is actually smaller, at least in line count. (There's also the matter of the missing I/O primitives, but most of them just delegate to Scheme in Arc0 as well.)

I have no idea how it compares in code-tree count. Probably larger, as my JavaScript coding style is fairly dense. One could argue that that's the point of syntax though; it makes common operations take up very little space on the page.

anaphoricvor 18 Jahren

Cool, you deserve many up votes for this!

I just played around with it quickly, pasted in the recursive definition of factorial:

(def fact (x) (if (< x 1) 1 (* x (fact (- x 1)))))

It was fairly quick, but the results came back as floating point numbers. It broke on (fact 100).

Under arc-over-scheme it did better.

CLISP performed better than both, but the default limit in the call depth was easily exceeded (E.g. it busted on (fact 8000)). I don't recall exactly, but for around fact 5000 CLISP seemed about twice as fast as arc-over-scheme.

These are very rough estimates, but perhaps give people an intuition about performance.

Now what I am really waiting for is the arc-over-CLISP. I am too busy with other things to dare an attempt...

nostrademonsvor 18 Jahren

I tried factorial as one of my test cases. Up through factorial 10 it was still coming back as integers. You may have triggered some overflow condition. The interpreter uses the native JavaScript + operation, then checks whether result == Math.round(result) to see whether it should wrap it in an int or a num.

I'm truly amazed you got it to work up to (fact 100), and that it came back in a reasonable amount of time. Firefox has a recursion limit depth of 1000, which means that the interpreter overhead is only about a factor of 10. I was expecting much more...

anaphoricvor 18 Jahren

I think it worked for 50, but then it busted on 100. I only tried a couple of calls.

DaniFongvor 18 Jahren

That is quite something.

tac-ticsvor 18 Jahren

A scheme isn't a scheme without continuations. It's a shame they're such a pain in the ass to implement in platforms w/o gotos or TCO.

whacked_newvor 18 Jahren

nostrademons you are the man.

nostrademonsvor 18 Jahren

Thanks. :-)

apgwozvor 18 Jahren

While I didn't think it would be JavaScript, I think my prediction of "how long before there's another implementation out there" of a "few days" was only a little bit off.

nostrademonsvor 18 Jahren

I was shooting for a weekend but didn't quite make it. ;-)

fkruegervor 18 Jahren

Quite well done! I'm very impressed.

albertcardonavor 18 Jahren

Super cool, thanks a lot! Now if only we could push return to enter instead of having to use the mouse ...

byrneseyeviewvor 18 Jahren

Tab-return?

nostrademonsvor 18 Jahren

Yeah, that's what I do. I couldn't figure out how to get accesskeys to take "return" as the key. If anyone knows a better solution, I can change it.

tlrobinsonvor 18 Jahren

    document.getElementById("input").addEventListener("keypress", function(e) {
        e = e || window.event;
        if (e.keyCode == 13) {
            $('#eval').click();
            e.target.value = "";
    }}, false);

...or the equivalent in jQuery. Not IE compatible (no, I don't care)

In the meantime, here's a bookmarklet you can use to "patch" it:

javascript:(function(){document.getElementById("input").addEventListener("keypress", function(e) { e = e || window.event; if (e.keyCode == 13) { $('#eval').click(); e.target.value = ""; }}, false);})();

[deleted]vor 18 Jahren